vis.c

quake3工具源码。包括生成bsp文件

// vis.c

#include "vis.h"
#include "threads.h"
#include "stdlib.h"
#ifdef _WIN32
#include "../libs/pakstuff.h"
#endif


#define	VIS_HEADER_SIZE	8

extern	char		outbase[32];

int			numportals;
int			portalclusters;
int			numfaces;

char		inbase[32];

vportal_t	*portals;
leaf_t		*leafs;

vportal_t	*faces;
leaf_t		*faceleafs;

int			c_portaltest, c_portalpass, c_portalcheck;

int		leafbytes;				// (portalclusters+63)>>3
int		leaflongs;

int		portalbytes, portallongs;

qboolean		fastvis;
qboolean		nopassagevis;
qboolean		mergevis;
qboolean		nosort;
qboolean		saveprt;

int			testlevel = 2;

int		totalvis;

vportal_t	*sorted_portals[MAX_MAP_PORTALS*2];


//=============================================================================

void PlaneFromWinding (winding_t *w, plane_t *plane)
{
	vec3_t		v1, v2;

// calc plane
	VectorSubtract (w->points[2], w->points[1], v1);
	VectorSubtract (w->points[0], w->points[1], v2);
	CrossProduct (v2, v1, plane->normal);
	VectorNormalize (plane->normal, plane->normal);
	plane->dist = DotProduct (w->points[0], plane->normal);
}


/*
==================
NewWinding
==================
*/
winding_t *NewWinding (int points)
{
	winding_t	*w;
	int			size;
	
	if (points > MAX_POINTS_ON_WINDING)
		Error ("NewWinding: %i points", points);
	
	size = (int)((winding_t *)0)->points[points];
	w = malloc (size);
	memset (w, 0, size);
	
	return w;
}



void prl(leaf_t *l)
{
	int			i;
	vportal_t	*p;
	plane_t		pl;
	
	for (i=0 ; i<l->numportals ; i++)
	{
		p = l->portals[i];
		pl = p->plane;
		_printf ("portal %4i to leaf %4i : %7.1f : (%4.1f, %4.1f, %4.1f)\n",(int)(p-portals),p->leaf,pl.dist, pl.normal[0], pl.normal[1], pl.normal[2]);
	}
}


//=============================================================================

/*
=============
SortPortals

Sorts the portals from the least complex, so the later ones can reuse
the earlier information.
=============
*/
int PComp (const void *a, const void *b)
{
	if ( (*(vportal_t **)a)->nummightsee == (*(vportal_t **)b)->nummightsee)
		return 0;
	if ( (*(vportal_t **)a)->nummightsee < (*(vportal_t **)b)->nummightsee)
		return -1;
	return 1;
}
void SortPortals (void)
{
	int		i;
	
	for (i=0 ; i<numportals*2 ; i++)
		sorted_portals[i] = &portals[i];

	if (nosort)
		return;
	qsort (sorted_portals, numportals*2, sizeof(sorted_portals[0]), PComp);
}


/*
==============
LeafVectorFromPortalVector
==============
*/
int LeafVectorFromPortalVector (byte *portalbits, byte *leafbits)
{
	int			i, j, leafnum;
	vportal_t	*p;
	int			c_leafs;


	for (i=0 ; i<numportals*2 ; i++)
	{
		if (portalbits[i>>3] & (1<<(i&7)) )
		{
			p = portals+i;
			leafbits[p->leaf>>3] |= (1<<(p->leaf&7));
		}
	}

	for (j = 0; j < portalclusters; j++)
	{
		leafnum = j;
		while (leafs[leafnum].merged >= 0)
			leafnum = leafs[leafnum].merged;
		//if the merged leaf is visible then the original leaf is visible
		if (leafbits[leafnum>>3] & (1<<(leafnum&7)))
		{
			leafbits[j>>3] |= (1<<(j&7));
		}
	}

	c_leafs = CountBits (leafbits, portalclusters);

	return c_leafs;
}


/*
===============
ClusterMerge

Merges the portal visibility for a leaf
===============
*/
void ClusterMerge (int leafnum)
{
	leaf_t		*leaf;
	byte		portalvector[MAX_PORTALS/8];
	byte		uncompressed[MAX_MAP_LEAFS/8];
	int			i, j;
	int			numvis, mergedleafnum;
	vportal_t	*p;
	int			pnum;

	// OR together all the portalvis bits

	mergedleafnum = leafnum;
	while(leafs[mergedleafnum].merged >= 0)
		mergedleafnum = leafs[mergedleafnum].merged;

	memset (portalvector, 0, portalbytes);
	leaf = &leafs[mergedleafnum];
	for (i = 0; i < leaf->numportals; i++)
	{
		p = leaf->portals[i];
		if (p->removed)
			continue;

		if (p->status != stat_done)
			Error ("portal not done");
		for (j=0 ; j<portallongs ; j++)
			((long *)portalvector)[j] |= ((long *)p->portalvis)[j];
		pnum = p - portals;
		portalvector[pnum>>3] |= 1<<(pnum&7);
	}

	memset (uncompressed, 0, leafbytes);

	uncompressed[mergedleafnum>>3] |= (1<<(mergedleafnum&7));
	// convert portal bits to leaf bits
	numvis = LeafVectorFromPortalVector (portalvector, uncompressed);

//	if (uncompressed[leafnum>>3] & (1<<(leafnum&7)))
//		_printf ("WARNING: Leaf portals saw into leaf\n");
		
//	uncompressed[leafnum>>3] |= (1<<(leafnum&7));

	numvis++;		// count the leaf itself

	totalvis += numvis;

	qprintf ("cluster %4i : %4i visible\n", leafnum, numvis);

	memcpy (visBytes + VIS_HEADER_SIZE + leafnum*leafbytes, uncompressed, leafbytes);
}


/*
==================
CalcPortalVis
==================
*/
void CalcPortalVis (void)
{
#ifdef MREDEBUG
	_printf("%6d portals out of %d", 0, numportals*2);
	//get rid of the counter
	RunThreadsOnIndividual (numportals*2, qfalse, PortalFlow);
#else
	RunThreadsOnIndividual (numportals*2, qtrue, PortalFlow);
#endif

}

/*
==================
CalcPassagePortalVis
==================
*/
void PassageMemory(void);

void CalcPassagePortalVis(void)
{
	PassageMemory();

#ifdef MREDEBUG
	_printf("%6d portals out of %d", 0, numportals*2);
	RunThreadsOnIndividual (numportals*2, qfalse, CreatePassages);
	_printf("\n");
	_printf("%6d portals out of %d", 0, numportals*2);
	RunThreadsOnIndividual (numportals*2, qfalse, PassagePortalFlow);
	_printf("\n");
#else
	RunThreadsOnIndividual (numportals*2, qtrue, CreatePassages);
	RunThreadsOnIndividual (numportals*2, qtrue, PassagePortalFlow);
#endif
}

/*
==================
CalcFastVis
==================
*/
void CalcFastVis(void)
{
	int		i;

	// fastvis just uses mightsee for a very loose bound
	for (i=0 ; i<numportals*2 ; i++)
	{
		portals[i].portalvis = portals[i].portalflood;
		portals[i].status = stat_done;
	}
}

/*
==================
CalcVis
==================
*/
void CalcVis (void)
{
	int		i;

	RunThreadsOnIndividual (numportals*2, qtrue, BasePortalVis);

//	RunThreadsOnIndividual (numportals*2, qtrue, BetterPortalVis);

	SortPortals ();

	if (fastvis)
		CalcFastVis();
	else if (nopassagevis)
		CalcPortalVis ();
	else
		CalcPassagePortalVis();
	//
	// assemble the leaf vis lists by oring and compressing the portal lists
	//
	_printf("creating leaf vis...\n");
	for (i=0 ; i<portalclusters ; i++)
		ClusterMerge (i);
		
	_printf ("Average clusters visible: %i\n", totalvis / portalclusters);
}

/*
==================
SetPortalSphere
==================
*/
void SetPortalSphere (vportal_t *p)
{
	int		i;
	vec3_t	total, dist;
	winding_t	*w;
	float	r, bestr;

	w = p->winding;
	VectorCopy (vec3_origin, total);
	for (i=0 ; i<w->numpoints ; i++)
	{
		VectorAdd (total, w->points[i], total);
	}
	
	for (i=0 ; i<3 ; i++)
		total[i] /= w->numpoints;

	bestr = 0;		
	for (i=0 ; i<w->numpoints ; i++)
	{
		VectorSubtract (w->points[i], total, dist);
		r = VectorLength (dist);
		if (r > bestr)
			bestr = r;
	}
	VectorCopy (total, p->origin);
	p->radius = bestr;
}

/*
=============
Winding_PlanesConcave
=============
*/
#define WCONVEX_EPSILON		0.2

int Winding_PlanesConcave(winding_t *w1, winding_t *w2,
							 vec3_t normal1, vec3_t normal2,
							 float dist1, float dist2)
{
	int i;

	if (!w1 || !w2) return qfalse;

	// check if one of the points of winding 1 is at the front of the plane of winding 2
	for (i = 0; i < w1->numpoints; i++)
	{
		if (DotProduct(normal2, w1->points[i]) - dist2 > WCONVEX_EPSILON) return qtrue;
	}
	// check if one of the points of winding 2 is at the front of the plane of winding 1
	for (i = 0; i < w2->numpoints; i++)
	{
		if (DotProduct(normal1, w2->points[i]) - dist1 > WCONVEX_EPSILON) return qtrue;
	}

	return qfalse;
}

/*
============
TryMergeLeaves
============
*/
int TryMergeLeaves(int l1num, int l2num)
{
	int i, j, k, n, numportals;
	plane_t plane1, plane2;
	leaf_t *l1, *l2;
	vportal_t *p1, *p2;
	vportal_t *portals[MAX_PORTALS_ON_LEAF];

	for (k = 0; k < 2; k++)
	{
		if (k) l1 = &leafs[l1num];
		else l1 = &faceleafs[l1num];
		for (i = 0; i < l1->numportals; i++)
		{
			p1 = l1->portals[i];
			if (p1->leaf == l2num) continue;
			for (n = 0; n < 2; n++)
			{
				if (n) l2 = &leafs[l2num];
				else l2 = &faceleafs[l2num];
				for (j = 0; j < l2->numportals; j++)
				{
					p2 = l2->portals[j];
					if (p2->leaf == l1num) continue;
					//
					plane1 = p1->plane;
					plane2 = p2->plane;
					if (Winding_PlanesConcave(p1->winding, p2->winding, plane1.normal, plane2.normal, plane1.dist, plane2.dist))
						return qfalse;
				}
			}
		}
	}
	for (k = 0; k < 2; k++)
	{
		if (k)
		{
			l1 = &leafs[l1num];
			l2 = &leafs[l2num];
		}
		else
		{
			l1 = &faceleafs[l1num];
			l2 = &faceleafs[l2num];
		}
		numportals = 0;
		//the leaves can be merged now
		for (i = 0; i < l1->numportals; i++)
		{
			p1 = l1->portals[i];
			if (p1->leaf == l2num)
			{
				p1->removed = qtrue;
				continue;
			}
			portals[numportals++] = p1;
		}
		for (j = 0; j < l2->numportals; j++)
		{
			p2 = l2->portals[j];
			if (p2->leaf == l1num)
			{
				p2->removed = qtrue;
				continue;
			}
			portals[numportals++] = p2;
		}
		for (i = 0; i < numportals; i++)
		{
			l2->portals[i] = portals[i];
		}
		l2->numportals = numportals;
		l1->merged = l2num;
	}
	return qtrue;
}

/*
============
UpdatePortals
============
*/
void UpdatePortals(void)
{
	int i;
	vportal_t *p;

	for (i = 0; i < numportals * 2; i++)
	{
		p = &portals[i];
		if (p->removed)
			continue;
		while(leafs[p->leaf].merged >= 0)
			p->leaf = leafs[p->leaf].merged;
	}
}

/*
============
MergeLeaves

try to merge leaves but don't merge through hint splitters
============
*/
void MergeLeaves(void)
{
	int i, j, nummerges, totalnummerges;
	leaf_t *leaf;
	vportal_t *p;

	totalnummerges = 0;
	do
	{
		nummerges = 0;
		for (i = 0; i < portalclusters; i++)
		{
			leaf = &leafs[i];
			//if this leaf is merged already
			if (leaf->merged >= 0)
				continue;
			//
			for (j = 0; j < leaf->numportals; j++)
			{
				p = leaf->portals[j];
				//
				if (p->removed)
					continue;
				//never merge through hint portals
				if (p->hint)
					continue;
				if (TryMergeLeaves(i, p->leaf))
				{
					UpdatePortals();
					nummerges++;
					break;
				}
			}
		}
		totalnummerges += nummerges;
	} while (nummerges);
	_printf("%6d leaves merged\n", totalnummerges);
}

/*
============
TryMergeWinding
============
*/
#define	CONTINUOUS_EPSILON	0.005

winding_t *TryMergeWinding (winding_t *f1, winding_t *f2, vec3_t planenormal)
{
	vec_t		*p1, *p2, *p3, *p4, *back;
	winding_t	*newf;
	int			i, j, k, l;
	vec3_t		normal, delta;
	vec_t		dot;
	qboolean	keep1, keep2;
	

	//
	// find a common edge
	//	
	p1 = p2 = NULL;	// stop compiler warning
	j = 0;			// 
	
	for (i = 0; i < f1->numpoints; i++)
	{
		p1 = f1->points[i];
		p2 = f1->points[(i+1) % f1->numpoints];
		for (j = 0; j < f2->numpoints; j++)
		{
			p3 = f2->points[j];
			p4 = f2->points[(j+1) % f2->numpoints];
			for (k = 0; k < 3; k++)
			{
				if (fabs(p1[k] - p4[k]) > 0.1)//EQUAL_EPSILON) //ME
					break;
				if (fabs(p2[k] - p3[k]) > 0.1)//EQUAL_EPSILON) //ME
					break;
			} //end for
			if (k==3)
				break;
		} //end for
		if (j < f2->numpoints)
			break;
	} //end for