faces.cpp

hl2 source code. Do not use it illegal.

		c_badstartverts++;
		base = 0;
	}
	else
	{	// rotate the vertex order
		base = start[i];
	}

	// this may fragment the face if > MAXEDGES
	FaceFromSuperverts (pList, f, base);
}

/*
==================
FixEdges_r
==================
*/
void FixEdges_r (node_t *node)
{
	int		i;
	face_t	*f;

	if (node->planenum == PLANENUM_LEAF)
	{
		return;
	}

	for (f=node->faces ; f ; f=f->next)
		FixFaceEdges (&node->faces, f);

	for (i=0 ; i<2 ; i++)
		FixEdges_r (node->children[i]);
}


//-----------------------------------------------------------------------------
// Purpose: Fix the t-junctions on detail faces
//-----------------------------------------------------------------------------
void FixLeafFaceEdges( face_t **ppLeafFaceList )
{
	face_t *f;

	for ( f = *ppLeafFaceList; f; f = f->next )
	{
		FixFaceEdges( ppLeafFaceList, f );
	}
}

/*
===========
FixTjuncs

===========
*/

face_t *FixTjuncs (node_t *headnode, face_t *pLeafFaceList)
{
	// snap and merge all vertexes
	qprintf ("---- snap verts ----\n");
	memset (hashverts, 0, sizeof(hashverts));
	memset (vertexchain, 0, sizeof(vertexchain));
	c_totalverts = 0;
	c_uniqueverts = 0;
	c_faceoverflows = 0;
	EmitNodeFaceVertexes_r (headnode);

	// UNDONE: This count is wrong with tjuncs off on details - since 

	// break edges on tjunctions
	qprintf ("---- tjunc ----\n");
	c_tryedges = 0;
	c_degenerate = 0;
	c_facecollapse = 0;
	c_tjunctions = 0;
	if (!notjunc)
	{
		FixEdges_r (headnode);

		// UNDONE: What we really want to do here is not add any world-only tjuncs to the details
		// But you'd have to know which verts were in each set in the hash in order to build the
		// proper edges for the leaf faces.
		EmitLeafFaceVertexes( &pLeafFaceList );
		FixLeafFaceEdges( &pLeafFaceList );
	}
	else
	{
		EmitLeafFaceVertexes( &pLeafFaceList );
	}


	qprintf ("%i unique from %i\n", c_uniqueverts, c_totalverts);
	qprintf ("%5i edges degenerated\n", c_degenerate);
	qprintf ("%5i faces degenerated\n", c_facecollapse);
	qprintf ("%5i edges added by tjunctions\n", c_tjunctions);
	qprintf ("%5i faces added by tjunctions\n", c_faceoverflows);
	qprintf ("%5i bad start verts\n", c_badstartverts);

	return pLeafFaceList;
}


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

int		c_faces;

face_t	*AllocFace (void)
{
	static int s_FaceId = 0;

	face_t	*f;

	f = (face_t*)malloc(sizeof(*f));
	memset (f, 0, sizeof(*f));
	f->id = s_FaceId;
	++s_FaceId;

	c_faces++;

	return f;
}

face_t *NewFaceFromFace (face_t *f)
{
	face_t	*newf;

	newf = AllocFace ();
	*newf = *f;
	newf->merged = NULL;
	newf->split[0] = newf->split[1] = NULL;
	newf->w = NULL;
	return newf;
}

void FreeFace (face_t *f)
{
	if (f->w)
		FreeWinding (f->w);
	free (f);
	c_faces--;
}


void FreeFaceList( face_t *pFaces )
{
	while ( pFaces )
	{
		face_t *next = pFaces->next;

		FreeFace( pFaces );
		pFaces = next;
	}
}

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

void GetEdge2_InitOptimizedList()
{
	for( int i=0; i < MAX_MAP_VERTS; i++ )
		g_VertEdgeList[i].RemoveAll();
}


void IntSort( CUtlVector<int> &theList )
{
	for( int i=0; i < theList.Size()-1; i++ )
	{
		if( theList[i] > theList[i+1] )
		{
			int temp = theList[i];
			theList[i] = theList[i+1];
			theList[i+1] = temp;
			if( i > 0 )
				i -= 2;
			else
				i = -1;
		}
	}
}


int AddEdge( int v1, int v2, face_t *f )
{
	if (numedges >= MAX_MAP_EDGES)
		Error ("numedges == MAX_MAP_EDGES");

	g_VertEdgeList[v1].AddToTail( numedges );
	g_VertEdgeList[v2].AddToTail( numedges );
	IntSort( g_VertEdgeList[v1] );
	IntSort( g_VertEdgeList[v2] );
			  
	dedge_t *edge = &dedges[numedges];
	numedges++;
    
    edge->v[0] = v1;
    edge->v[1] = v2;
    edgefaces[numedges-1][0] = f;
	return numedges - 1;
}


/*
==================
GetEdge

Called by writebsp.
Don't allow four way edges
==================
*/
int GetEdge2 (int v1, int v2,  face_t *f)
{
	dedge_t	*edge;

	c_tryedges++;

	if (!noshare)
	{
		// Check all edges connected to v1.
		CUtlVector<int> &theList = g_VertEdgeList[v1];
		for( int i=0; i < theList.Size(); i++ )
		{
			int iEdge = theList[i];
			edge = &dedges[iEdge];
			if (v1 == edge->v[1] && v2 == edge->v[0] && edgefaces[iEdge][0]->contents == f->contents)
			{
				if (edgefaces[iEdge][1])
					continue;

				edgefaces[iEdge][1] = f;
				return -iEdge;
			}
		}
	}

	return AddEdge( v1, v2, f );
}

/*
===========================================================================

FACE MERGING

===========================================================================
*/

#define	CONTINUOUS_EPSILON	0.001

/*
=============
TryMergeWinding

If two polygons share a common edge and the edges that meet at the
common points are both inside the other polygons, merge them

Returns NULL if the faces couldn't be merged, or the new face.
The originals will NOT be freed.
=============
*/
winding_t *TryMergeWinding (winding_t *f1, winding_t *f2, Vector& planenormal)
{
	Vector		*p1, *p2, *p3, *p4, *back;
	winding_t	*newf;
	int			i, j, k, l;
	Vector		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->p[i];
		p2 = &f1->p[(i+1)%f1->numpoints];
		for (j=0 ; j<f2->numpoints ; j++)
		{
			p3 = &f2->p[j];
			p4 = &f2->p[(j+1)%f2->numpoints];
			for (k=0 ; k<3 ; k++)
			{
				if (fabs((*p1)[k] - (*p4)[k]) > EQUAL_EPSILON)
					break;
				if (fabs((*p2)[k] - (*p3)[k]) > EQUAL_EPSILON)
					break;
			}
			if (k==3)
				break;
		}
		if (j < f2->numpoints)
			break;
	}
	
	if (i == f1->numpoints)
		return NULL;			// no matching edges

	//
	// check slope of connected lines
	// if the slopes are colinear, the point can be removed
	//
	back = &f1->p[(i+f1->numpoints-1)%f1->numpoints];
	VectorSubtract (*p1, *back, delta);
	CrossProduct (planenormal, delta, normal);
	VectorNormalize (normal);
	
	back = &f2->p[(j+2)%f2->numpoints];
	VectorSubtract (*back, *p1, delta);
	dot = DotProduct (delta, normal);
	if (dot > CONTINUOUS_EPSILON)
		return NULL;			// not a convex polygon
	keep1 = (qboolean)(dot < -CONTINUOUS_EPSILON);
	
	back = &f1->p[(i+2)%f1->numpoints];
	VectorSubtract (*back, *p2, delta);
	CrossProduct (planenormal, delta, normal);
	VectorNormalize (normal);

	back = &f2->p[(j+f2->numpoints-1)%f2->numpoints];
	VectorSubtract (*back, *p2, delta);
	dot = DotProduct (delta, normal);
	if (dot > CONTINUOUS_EPSILON)
		return NULL;			// not a convex polygon
	keep2 = (qboolean)(dot < -CONTINUOUS_EPSILON);

	//
	// build the new polygon
	//
	newf = AllocWinding (f1->numpoints + f2->numpoints);
	
	// copy first polygon
	for (k=(i+1)%f1->numpoints ; k != i ; k=(k+1)%f1->numpoints)
	{
		if (k==(i+1)%f1->numpoints && !keep2)
			continue;
		
		VectorCopy (f1->p[k], newf->p[newf->numpoints]);
		newf->numpoints++;
	}
	
	// copy second polygon
	for (l= (j+1)%f2->numpoints ; l != j ; l=(l+1)%f2->numpoints)
	{
		if (l==(j+1)%f2->numpoints && !keep1)
			continue;
		VectorCopy (f2->p[l], newf->p[newf->numpoints]);
		newf->numpoints++;
	}

	return newf;
}

/*
=============
TryMerge

If two polygons share a common edge and the edges that meet at the
common points are both inside the other polygons, merge them

Returns NULL if the faces couldn't be merged, or the new face.
The originals will NOT be freed.
=============
*/
face_t *TryMerge (face_t *f1, face_t *f2, Vector& planenormal)
{
	face_t		*newf;
	winding_t	*nw;

	if (!f1->w || !f2->w)
		return NULL;
	if (f1->texinfo != f2->texinfo)
		return NULL;
	if (f1->planenum != f2->planenum)	// on front and back sides
		return NULL;
	if (f1->contents != f2->contents)
		return NULL;
    
	nw = TryMergeWinding (f1->w, f2->w, planenormal);
	if (!nw)
		return NULL;

	c_merge++;
	newf = NewFaceFromFace (f1);
	newf->w = nw;

	f1->merged = newf;
	f2->merged = newf;

	return newf;
}

/*
===============
MergeFaceList
===============
*/
void MergeFaceList(face_t **pList)
{
	face_t	*f1, *f2, *end;
	face_t	*merged;
	plane_t	*plane;

	merged = NULL;
	
	for (f1 = *pList; f1 ; f1 = f1->next)
	{
		if (f1->merged || f1->split[0] || f1->split[1])
			continue;
		for (f2 = *pList; f2 != f1 ; f2=f2->next)
		{
			if (f2->merged || f2->split[0] || f2->split[1])
				continue;

			plane = &mapplanes[f1->planenum];
			merged = TryMerge (f1, f2, plane->normal);
			if (!merged)
				continue;

			// add merged to the end of the face list 
			// so it will be checked against all the faces again
			for (end = *pList; end->next ; end = end->next)
			;
			merged->next = NULL;
			end->next = merged;
			break;
		}
	}
}

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

/*
===============
SubdivideFace

Chop up faces that are larger than we want in the surface cache
===============
*/
void SubdivideFace (face_t **pFaceList, face_t *f)
{
	float		mins, maxs;
	vec_t		v;
	vec_t		luxelsPerWorldUnit;
	int			axis, i;
	texinfo_t	*tex;
	Vector		temp;
	vec_t		dist;
	winding_t	*w, *frontw, *backw;

	if ( f->merged || f->split[0] || f->split[1] )
		return;

// special (non-surface cached) faces don't need subdivision
	tex = &texinfo[f->texinfo];

	if( tex->flags & SURF_NOLIGHT )
	{
		return;
	}

	for (axis = 0 ; axis < 2 ; axis++)
	{
		while (1)
		{
			mins = 999999;
			maxs = -999999;
			
			VECTOR_COPY (tex->lightmapVecsLuxelsPerWorldUnits[axis], temp);
			w = f->w;
			for (i=0 ; i<w->numpoints ; i++)
			{
				v = DotProduct (w->p[i], temp);
				if (v < mins)
					mins = v;
				if (v > maxs)
					maxs = v;
			}
#if 0
			if (maxs - mins <= 0)
				Error ("zero extents");
#endif
			if (maxs - mins <= g_maxLightmapDimension)
				break;
			
		// split it
			c_subdivide++;
			
			luxelsPerWorldUnit = VectorNormalize (temp);	

			dist = ( mins + g_maxLightmapDimension - 1 ) / luxelsPerWorldUnit;

			ClipWindingEpsilon (w, temp, dist, ON_EPSILON, &frontw, &backw);
			if (!frontw || !backw)
				Error ("SubdivideFace: didn't split the polygon");

			f->split[0] = NewFaceFromFace (f);
			f->split[0]->w = frontw;
			f->split[0]->next = *pFaceList;
			*pFaceList = f->split[0];

			f->split[1] = NewFaceFromFace (f);
			f->split[1]->w = backw;
			f->split[1]->next = *pFaceList;
			*pFaceList = f->split[1];

			SubdivideFace (pFaceList, f->split[0]);
			SubdivideFace (pFaceList, f->split[1]);
			return;
		}
	}
}

void SubdivideFaceList(face_t **pFaceList)
{
	face_t	*f;

	for (f = *pFaceList ; f ; f=f->next)
	{
		SubdivideFace (pFaceList, f);
	}
}

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