First version of the SOurce SDK 2013

1 files changed, 1810 insertions, 0 deletions

diff --git a/mp/src/utils/vbsp/faces.cpp b/mp/src/utils/vbsp/faces.cpp
new file mode 100644
index 00000000..13ed9d61
--- /dev/null
+++ b/mp/src/utils/vbsp/faces.cpp
@@ -0,0 +1,1810 @@
+//========= Copyright Valve Corporation, All rights reserved. ============//

+//

+// Purpose: 

+//

+// $NoKeywords: $

+//

+//=============================================================================//

+// faces.c

+

+#include "vbsp.h"

+#include "utlvector.h"

+#include "utilmatlib.h"

+#include <float.h>

+#include "mstristrip.h"

+#include "tier1/strtools.h"

+#include "materialpatch.h"

+/*

+

+  some faces will be removed before saving, but still form nodes:

+

+  the insides of sky volumes

+  meeting planes of different water current volumes

+

+*/

+

+// undefine for dumb linear searches

+#define	USE_HASHING

+

+#define	INTEGRAL_EPSILON	0.01

+#define	POINT_EPSILON		0.1

+#define	OFF_EPSILON			0.25

+

+int	c_merge;

+int	c_subdivide;

+

+int	c_totalverts;

+int	c_uniqueverts;

+int	c_degenerate;

+int	c_tjunctions;

+int	c_faceoverflows;

+int	c_facecollapse;

+int	c_badstartverts;

+

+#define	MAX_SUPERVERTS	512

+int	superverts[MAX_SUPERVERTS];

+int	numsuperverts;

+

+face_t		*edgefaces[MAX_MAP_EDGES][2];

+int		firstmodeledge = 1;

+int		firstmodelface;

+

+int	c_tryedges;

+

+Vector	edge_dir;

+Vector	edge_start;

+vec_t	edge_len;

+

+int		num_edge_verts;

+int		edge_verts[MAX_MAP_VERTS];

+

+

+float	g_maxLightmapDimension = 32;

+

+

+face_t *NewFaceFromFace (face_t *f);

+

+// Used to speed up GetEdge2(). Holds a list of edges connected to each vert.

+CUtlVector<int> g_VertEdgeList[MAX_MAP_VERTS];

+

+

+//===========================================================================

+

+typedef struct hashvert_s

+{

+	struct hashvert_s	*next;

+	int		num;

+} hashvert_t;

+

+#define HASH_BITS	7

+#define	HASH_SIZE	(COORD_EXTENT>>HASH_BITS)

+

+

+int	vertexchain[MAX_MAP_VERTS];		// the next vertex in a hash chain

+int	hashverts[HASH_SIZE*HASH_SIZE];	// a vertex number, or 0 for no verts

+

+//face_t		*edgefaces[MAX_MAP_EDGES][2];

+

+//============================================================================

+

+

+unsigned HashVec (Vector& vec)

+{

+	int			x, y;

+

+	x = (MAX_COORD_INTEGER + (int)(vec[0]+0.5)) >> HASH_BITS;

+	y = (MAX_COORD_INTEGER + (int)(vec[1]+0.5)) >> HASH_BITS;

+

+	if ( x < 0 || x >= HASH_SIZE || y < 0 || y >= HASH_SIZE )

+		Error ("HashVec: point outside valid range");

+	

+	return y*HASH_SIZE + x;

+}

+

+#ifdef USE_HASHING

+/*

+=============

+GetVertex

+

+Uses hashing

+=============

+*/

+int	GetVertexnum (Vector& in)

+{

+	int			h;

+	int			i;

+	Vector		vert;

+	int			vnum;

+

+	c_totalverts++;

+

+	for (i=0 ; i<3 ; i++)

+	{

+		if ( fabs(in[i] - (int)(in[i]+0.5)) < INTEGRAL_EPSILON)

+			vert[i] = (int)(in[i]+0.5);

+		else

+			vert[i] = in[i];

+	}

+	

+	h = HashVec (vert);

+	

+	for (vnum=hashverts[h] ; vnum ; vnum=vertexchain[vnum])

+	{

+		Vector& p = dvertexes[vnum].point;

+		if ( fabs(p[0]-vert[0])<POINT_EPSILON

+		&& fabs(p[1]-vert[1])<POINT_EPSILON

+		&& fabs(p[2]-vert[2])<POINT_EPSILON )

+			return vnum;

+	}

+	

+// emit a vertex

+	if (numvertexes == MAX_MAP_VERTS)

+		Error ("Too many unique verts, max = %d (map has too much brush geometry)\n", MAX_MAP_VERTS);

+

+	dvertexes[numvertexes].point[0] = vert[0];

+	dvertexes[numvertexes].point[1] = vert[1];

+	dvertexes[numvertexes].point[2] = vert[2];

+

+	vertexchain[numvertexes] = hashverts[h];

+	hashverts[h] = numvertexes;

+

+	c_uniqueverts++;

+

+	numvertexes++;

+		

+	return numvertexes-1;

+}

+#else

+/*

+==================

+GetVertexnum

+

+Dumb linear search

+==================

+*/

+int	GetVertexnum (Vector& v)

+{

+	int			i, j;

+	dvertex_t	*dv;

+	vec_t		d;

+

+	c_totalverts++;

+

+	// make really close values exactly integral

+	for (i=0 ; i<3 ; i++)

+	{

+		if ( fabs(v[i] - (int)(v[i]+0.5)) < INTEGRAL_EPSILON )

+			v[i] = (int)(v[i]+0.5);

+		if (v[i] < MIN_COORD_INTEGER || v[i] > MAX_COORD_INTEGER)

+			Error ("GetVertexnum: outside world, vertex %.1f %.1f %.1f", v.x, v.y, v.z);

+	}

+

+	// search for an existing vertex match

+	for (i=0, dv=dvertexes ; i<numvertexes ; i++, dv++)

+	{

+		for (j=0 ; j<3 ; j++)

+		{

+			d = v[j] - dv->point[j];

+			if ( d > POINT_EPSILON || d < -POINT_EPSILON)

+				break;

+		}

+		if (j == 3)

+			return i;		// a match

+	}

+

+	// new point

+	if (numvertexes == MAX_MAP_VERTS)

+		Error ("Too many unique verts, max = %d (map has too much brush geometry)\n", MAX_MAP_VERTS);

+	VectorCopy (v, dv->point);

+	numvertexes++;

+	c_uniqueverts++;

+

+	return numvertexes-1;

+}

+#endif

+

+

+/*

+==================

+FaceFromSuperverts

+

+The faces vertexes have beeb added to the superverts[] array,

+and there may be more there than can be held in a face (MAXEDGES).

+

+If less, the faces vertexnums[] will be filled in, otherwise

+face will reference a tree of split[] faces until all of the

+vertexnums can be added.

+

+superverts[base] will become face->vertexnums[0], and the others

+will be circularly filled in.

+==================

+*/

+void FaceFromSuperverts (face_t **pListHead, face_t *f, int base)

+{

+	face_t	*newf;

+	int		remaining;

+	int		i;

+

+	remaining = numsuperverts;

+	while (remaining > MAXEDGES)

+	{	// must split into two faces, because of vertex overload

+		c_faceoverflows++;

+

+		newf = NewFaceFromFace (f);

+		f->split[0] = newf;

+

+		newf->next = *pListHead;

+		*pListHead = newf;

+

+		newf->numpoints = MAXEDGES;

+		for (i=0 ; i<MAXEDGES ; i++)

+			newf->vertexnums[i] = superverts[(i+base)%numsuperverts];

+

+		f->split[1] = NewFaceFromFace (f);

+		f = f->split[1];

+

+		f->next = *pListHead;

+		*pListHead = f;

+

+		remaining -= (MAXEDGES-2);

+		base = (base+MAXEDGES-1)%numsuperverts;

+	}

+

+	// copy the vertexes back to the face

+	f->numpoints = remaining;

+	for (i=0 ; i<remaining ; i++)

+		f->vertexnums[i] = superverts[(i+base)%numsuperverts];

+}

+

+

+/*

+==================

+EmitFaceVertexes

+==================

+*/

+void EmitFaceVertexes (face_t **pListHead, face_t *f)

+{

+	winding_t	*w;

+	int			i;

+

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

+		return;

+

+	w = f->w;

+	for (i=0 ; i<w->numpoints ; i++)

+	{

+		if (noweld)

+		{	// make every point unique

+			if (numvertexes == MAX_MAP_VERTS)

+				Error ("Too many unique verts, max = %d (map has too much brush geometry)\n", MAX_MAP_VERTS);

+			superverts[i] = numvertexes;

+			VectorCopy (w->p[i], dvertexes[numvertexes].point);

+			numvertexes++;

+			c_uniqueverts++;

+			c_totalverts++;

+		}

+		else

+			superverts[i] = GetVertexnum (w->p[i]);

+	}

+	numsuperverts = w->numpoints;

+

+	// this may fragment the face if > MAXEDGES

+	FaceFromSuperverts (pListHead, f, 0);

+}

+

+/*

+==================

+EmitNodeFaceVertexes_r

+==================

+*/

+void EmitNodeFaceVertexes_r (node_t *node)

+{

+	int		i;

+	face_t	*f;

+

+	if (node->planenum == PLANENUM_LEAF)

+	{

+		// leaf faces are emitted in second pass

+		return;

+	}

+

+	for (f=node->faces ; f ; f=f->next)

+	{

+		EmitFaceVertexes (&node->faces, f);

+	}

+

+	for (i=0 ; i<2 ; i++)

+	{

+		EmitNodeFaceVertexes_r (node->children[i]);

+	}

+}

+

+void EmitLeafFaceVertexes( face_t **ppLeafFaceList )

+{

+	face_t *f = *ppLeafFaceList;

+

+	while ( f )

+	{

+		EmitFaceVertexes( ppLeafFaceList, f );

+		f = f->next;

+	}

+}

+

+

+#ifdef USE_HASHING

+/*

+==========

+FindEdgeVerts

+

+Uses the hash tables to cut down to a small number

+==========

+*/

+void FindEdgeVerts (Vector& v1, Vector& v2)

+{

+	int		x1, x2, y1, y2, t;

+	int		x, y;

+	int		vnum;

+

+#if 0

+{

+	int		i;

+	num_edge_verts = numvertexes-1;

+	for (i=0 ; i<numvertexes-1 ; i++)

+		edge_verts[i] = i+1;

+}

+#endif

+

+	x1 = (MAX_COORD_INTEGER + (int)(v1[0]+0.5)) >> HASH_BITS;

+	y1 = (MAX_COORD_INTEGER + (int)(v1[1]+0.5)) >> HASH_BITS;

+	x2 = (MAX_COORD_INTEGER + (int)(v2[0]+0.5)) >> HASH_BITS;

+	y2 = (MAX_COORD_INTEGER + (int)(v2[1]+0.5)) >> HASH_BITS;

+

+	if (x1 > x2)

+	{

+		t = x1;

+		x1 = x2;

+		x2 = t;

+	}

+	if (y1 > y2)

+	{

+		t = y1;

+		y1 = y2;

+		y2 = t;

+	}

+#if 0

+	x1--;

+	x2++;

+	y1--;

+	y2++;

+	if (x1 < 0)

+		x1 = 0;

+	if (x2 >= HASH_SIZE)

+		x2 = HASH_SIZE;

+	if (y1 < 0)

+		y1 = 0;

+	if (y2 >= HASH_SIZE)

+		y2 = HASH_SIZE;

+#endif

+	num_edge_verts = 0;

+	for (x=x1 ; x <= x2 ; x++)

+	{

+		for (y=y1 ; y <= y2 ; y++)

+		{

+			for (vnum=hashverts[y*HASH_SIZE+x] ; vnum ; vnum=vertexchain[vnum])

+			{

+				edge_verts[num_edge_verts++] = vnum;

+			}

+		}

+	}

+}

+

+#else

+/*

+==========

+FindEdgeVerts

+

+Forced a dumb check of everything

+==========

+*/

+void FindEdgeVerts (Vector& v1, Vector& v2)

+{

+	int		i;

+

+	num_edge_verts = numvertexes-1;

+	for (i=0 ; i<num_edge_verts ; i++)

+		edge_verts[i] = i+1;

+}

+#endif

+

+/*

+==========

+TestEdge

+

+Can be recursively reentered

+==========

+*/

+void TestEdge (vec_t start, vec_t end, int p1, int p2, int startvert)

+{

+	int		j, k;

+	vec_t	dist;

+	Vector	delta;

+	Vector	exact;

+	Vector	off;

+	vec_t	error;

+	Vector	p;

+

+	if (p1 == p2)

+	{

+		c_degenerate++;

+		return;		// degenerate edge

+	}

+

+	for (k=startvert ; k<num_edge_verts ; k++)

+	{

+		j = edge_verts[k];

+		if (j==p1 || j == p2)

+			continue;

+

+		VectorCopy (dvertexes[j].point, p);

+

+		VectorSubtract (p, edge_start, delta);

+		dist = DotProduct (delta, edge_dir);

+		if (dist <=start || dist >= end)

+			continue;		// off an end

+		VectorMA (edge_start, dist, edge_dir, exact);

+		VectorSubtract (p, exact, off);

+		error = off.Length();

+

+		if (error > OFF_EPSILON)

+			continue;		// not on the edge

+

+		// break the edge

+		c_tjunctions++;

+		TestEdge (start, dist, p1, j, k+1);

+		TestEdge (dist, end, j, p2, k+1);

+		return;

+	}

+

+	// the edge p1 to p2 is now free of tjunctions

+	if (numsuperverts >= MAX_SUPERVERTS)

+		Error ("Edge with too many vertices due to t-junctions.  Max %d verts along an edge!\n", MAX_SUPERVERTS);

+	superverts[numsuperverts] = p1;

+	numsuperverts++;

+}

+

+

+// stores the edges that each vert is part of

+struct face_vert_table_t

+{

+	face_vert_table_t()

+	{

+		edge0 = -1;

+		edge1 = -1;

+	}

+

+	void AddEdge( int edge )

+	{

+		if ( edge0 == -1 )

+		{

+			edge0 = edge;

+		}

+		else

+		{

+			// can only have two edges

+			Assert(edge1==-1);

+			edge1 = edge;

+		}

+	}

+

+	bool HasEdge( int edge ) const

+	{

+		if ( edge >= 0 )

+		{

+			if ( edge0 == edge || edge1 == edge )

+				return true;

+		}

+		return false;

+	}

+	

+	int	edge0;

+	int	edge1;

+};

+

+// if these two verts share an edge, they must be collinear

+bool IsDiagonal( const face_vert_table_t &v0, const face_vert_table_t &v1 )

+{

+	if ( v1.HasEdge(v0.edge0) || v1.HasEdge(v0.edge1) )

+		return false;

+

+	return true;

+}

+

+

+void Triangulate_r( CUtlVector<int> &out, const CUtlVector<int> &inIndices, const CUtlVector<face_vert_table_t> &poly )

+{

+	Assert( inIndices.Count() > 2 );

+

+	// one triangle left, return

+	if ( inIndices.Count() == 3 )

+	{

+		for ( int i = 0; i < inIndices.Count(); i++ )

+		{

+			out.AddToTail( inIndices[i] );

+		}

+		return;

+	}

+

+	// check each pair of verts and see if they are diagonal (not on a shared edge)

+	// if so, split & recurse

+	for ( int i = 0; i < inIndices.Count(); i++ )

+	{

+		int count = inIndices.Count();

+

+		// i + count is myself, i + count-1 is previous, so we need to stop at i+count-2

+		for ( int j = 2; j < count-1; j++ )

+		{

+			// if these two form a diagonal, split the poly along 

+			// the diagonal and triangulate the two sub-polys

+			int index = inIndices[i];

+			int nextArray = (i+j)%count;

+			int nextIndex = inIndices[nextArray];

+			if ( IsDiagonal(poly[index], poly[nextIndex]) )

+			{

+				// add the poly up to the diagonal

+				CUtlVector<int> in1;

+				for ( int k = i; k != nextArray; k = (k+1)%count )

+				{

+					in1.AddToTail(inIndices[k]);

+				}

+				in1.AddToTail(nextIndex);

+

+				// add the rest of the poly starting with the diagonal

+				CUtlVector<int> in2;

+				in2.AddToTail(index);

+				for ( int l = nextArray; l != i; l = (l+1)%count )

+				{

+					in2.AddToTail(inIndices[l]);

+				}

+

+				// triangulate the sub-polys

+				Triangulate_r( out, in1, poly );

+				Triangulate_r( out, in2, poly );

+				return;

+			}

+		}

+	}

+

+	// didn't find a diagonal

+	Assert(0);

+}

+

+/*

+==================

+FixFaceEdges

+

+==================

+*/

+void FixFaceEdges (face_t **pList, face_t *f)

+{

+	int		p1, p2;

+	int		i;

+	Vector	e2;

+	vec_t	len;

+	int		count[MAX_SUPERVERTS], start[MAX_SUPERVERTS];

+	int		base;

+

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

+		return;

+

+	numsuperverts = 0;

+

+	int originalPoints = f->numpoints;

+	for (i=0 ; i<f->numpoints ; i++)

+	{

+		p1 = f->vertexnums[i];

+		p2 = f->vertexnums[(i+1)%f->numpoints];

+

+		VectorCopy (dvertexes[p1].point, edge_start);

+		VectorCopy (dvertexes[p2].point, e2);

+

+		FindEdgeVerts (edge_start, e2);

+

+		VectorSubtract (e2, edge_start, edge_dir);

+		len = VectorNormalize (edge_dir);

+

+		start[i] = numsuperverts;

+		TestEdge (0, len, p1, p2, 0);

+

+		count[i] = numsuperverts - start[i];

+	}

+

+	if (numsuperverts < 3)

+	{	// entire face collapsed

+		f->numpoints = 0;

+		c_facecollapse++;

+		return;

+	}

+

+	// we want to pick a vertex that doesn't have tjunctions

+	// on either side, which can cause artifacts on trifans,

+	// especially underwater

+	for (i=0 ; i<f->numpoints ; i++)

+	{

+		if (count[i] == 1 && count[(i+f->numpoints-1)%f->numpoints] == 1)

+			break;

+	}

+	if (i == f->numpoints)

+	{

+		f->badstartvert = true;

+		c_badstartverts++;

+		base = 0;

+

+	}

+	else

+	{	// rotate the vertex order

+		base = start[i];

+	}

+

+	// this may fragment the face if > MAXEDGES

+	FaceFromSuperverts (pList, f, base);

+

+	// if this is the world, then re-triangulate to sew cracks

+	if ( f->badstartvert && entity_num == 0 )

+	{

+		CUtlVector<face_vert_table_t> poly;

+		CUtlVector<int> inIndices;

+		CUtlVector<int> outIndices;

+		poly.AddMultipleToTail( numsuperverts );

+		for ( i = 0; i < originalPoints; i++ )

+		{

+			// edge may not have output any points.  Don't mark

+			if ( !count[i] )

+				continue;

+			// mark each edge the point is a member of

+			// we'll use this as a fast "is collinear" test

+			for ( int j = 0; j <= count[i]; j++ )

+			{

+				int polyIndex = (start[i] + j) % numsuperverts;

+				poly[polyIndex].AddEdge( i );

+			}

+		}

+		for ( i = 0; i < numsuperverts; i++ )

+		{

+			inIndices.AddToTail( i );

+		}

+		Triangulate_r( outIndices, inIndices, poly );

+		dprimitive_t &newPrim = g_primitives[g_numprimitives];

+		f->firstPrimID = g_numprimitives;

+		g_numprimitives++;

+		f->numPrims = 1;

+		newPrim.firstIndex = g_numprimindices;

+		newPrim.firstVert = g_numprimverts;

+		newPrim.indexCount = outIndices.Count();

+		newPrim.vertCount = 0;

+		newPrim.type = PRIM_TRILIST;

+		g_numprimindices += newPrim.indexCount;

+		if ( g_numprimitives > MAX_MAP_PRIMITIVES || g_numprimindices > MAX_MAP_PRIMINDICES )

+		{

+			Error("Too many t-junctions to fix up! (%d prims, max %d :: %d indices, max %d)\n", g_numprimitives, MAX_MAP_PRIMITIVES, g_numprimindices, MAX_MAP_PRIMINDICES );

+		}

+		for ( i = 0; i < outIndices.Count(); i++ )

+		{

+			g_primindices[newPrim.firstIndex + i] = outIndices[i];

+		}

+	}

+}

+

+/*

+==================

+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 ( g_bAllowDetailCracks )

+	{

+		FixEdges_r (headnode);

+		EmitLeafFaceVertexes( &pLeafFaceList );

+		FixLeafFaceEdges( &pLeafFaceList );

+	}

+	else

+	{

+		EmitLeafFaceVertexes( &pLeafFaceList );

+		if (!notjunc)

+		{

+			FixEdges_r (headnode);

+			FixLeafFaceEdges( &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 ("Too many edges in map, max == %d", 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;

+}

+

+//-----------------------------------------------------------------------------

+// Purpose:

+//-----------------------------------------------------------------------------

+bool OverlaysAreEqual( face_t *f1, face_t *f2 )

+{

+	// Check the overlay ids - see if they are the same.

+	if ( f1->originalface->aOverlayIds.Count() != f2->originalface->aOverlayIds.Count() )

+		return false;

+

+	int nOverlayCount = f1->originalface->aOverlayIds.Count();

+	for ( int iOverlay = 0; iOverlay < nOverlayCount; ++iOverlay )

+	{

+		int nOverlayId = f1->originalface->aOverlayIds[iOverlay];

+		if ( f2->originalface->aOverlayIds.Find( nOverlayId ) == -1 )

+			return false;

+	}

+

+	return true;

+}

+

+//-----------------------------------------------------------------------------

+// Purpose:

+//-----------------------------------------------------------------------------

+bool FaceOnWaterBrush( face_t *face )

+{

+	side_t *pSide = face->originalface;

+	if ( !pSide )

+		return false;

+

+	if ( pSide->contents & ( CONTENTS_WATER | CONTENTS_SLIME ) )

+		return true;

+

+	return false;

+}

+

+/*

+=============

+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;

+    if ( f1->originalface->smoothingGroups != f2->originalface->smoothingGroups )

+        return NULL;

+	if ( !OverlaysAreEqual( f1, f2 ) )

+		return NULL;

+	if ( nomergewater && ( FaceOnWaterBrush( f1 ) || FaceOnWaterBrush( f2 ) ) )

+		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 = &g_MainMap->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);

+	}

+}

+

+

+//-----------------------------------------------------------------------------

+// Assigns the bottom material to the bottom face

+//-----------------------------------------------------------------------------

+static bool AssignBottomWaterMaterialToFace( face_t *f )

+{

+	// NOTE: This happens *after* cubemap fixup occurs, so we need to get the

+	// fixed-up bottom material for this

+	texinfo_t *pTexInfo = &texinfo[f->texinfo];

+	dtexdata_t *pTexData = GetTexData( pTexInfo->texdata );

+	const char *pMaterialName = TexDataStringTable_GetString( pTexData->nameStringTableID );

+

+	char pBottomMatName[512];

+	if ( !GetValueFromPatchedMaterial( pMaterialName, "$bottommaterial", pBottomMatName, 512 ) )

+	{

+		if( !Q_stristr( pMaterialName, "nodraw" ) && !Q_stristr( pMaterialName, "toolsskip" ) )

+		{

+			Warning("error: material %s doesn't have a $bottommaterial\n", pMaterialName );

+		}

+		return false;

+	}

+

+	//Assert( mapplanes[f->planenum].normal.z < 0 );

+	texinfo_t newTexInfo;

+	newTexInfo.flags = pTexInfo->flags;

+	int j, k;

+	for (j=0 ; j<2 ; j++)

+	{

+		for (k=0 ; k<4 ; k++)

+		{

+			newTexInfo.textureVecsTexelsPerWorldUnits[j][k] = pTexInfo->textureVecsTexelsPerWorldUnits[j][k];

+			newTexInfo.lightmapVecsLuxelsPerWorldUnits[j][k] = pTexInfo->lightmapVecsLuxelsPerWorldUnits[j][k];

+		}

+	}

+	newTexInfo.texdata = FindOrCreateTexData( pBottomMatName );

+	f->texinfo = FindOrCreateTexInfo( newTexInfo );

+

+	return true;

+}

+

+

+//===========================================================================

+

+int	c_nodefaces;

+

+static void SubdivideFaceBySubdivSize( face_t *f, float subdivsize );

+void SubdivideFaceBySubdivSize( face_t *f );

+

+/*

+============

+FaceFromPortal

+

+============

+*/

+extern int FindOrCreateTexInfo( const texinfo_t &searchTexInfo );

+

+face_t *FaceFromPortal (portal_t *p, int pside)

+{

+	face_t	*f;

+	side_t	*side;

+	int		deltaContents;

+

+    // portal does not bridge different visible contents

+	side = p->side;

+	if (!side)

+		return NULL;	

+

+    // allocate a new face

+	f = AllocFace();

+

+    // save the original "side" from the map brush -- portal->side

+    // see FindPortalSide(...)

+    f->originalface = side;

+

+    //

+    // save material info

+    //

+	f->texinfo = side->texinfo;

+	f->dispinfo = -1;					// all faces with displacement info are created elsewhere

+	f->smoothingGroups = side->smoothingGroups;

+

+    // save plane info

+	f->planenum = (side->planenum & ~1) | pside;

+	if ( entity_num != 0 )

+	{

+		// the brush model renderer doesn't use PLANEBACK, so write the real plane

+		// inside water faces can be flipped because they are generated on the inside of the brush

+		if ( p->nodes[pside]->contents & (CONTENTS_WATER|CONTENTS_SLIME) )

+		{

+			f->planenum = (side->planenum & ~1) | pside;

+		}

+		else

+		{

+			f->planenum = side->planenum;

+		}

+	}

+

+    // save portal info

+	f->portal = p;

+	f->fogVolumeLeaf = NULL;

+

+	deltaContents = VisibleContents(p->nodes[!pside]->contents^p->nodes[pside]->contents);

+	

+	// don't show insides of windows or grates

+	if ( ((p->nodes[pside]->contents & CONTENTS_WINDOW) && deltaContents == CONTENTS_WINDOW) ||

+		((p->nodes[pside]->contents & CONTENTS_GRATE) && deltaContents == CONTENTS_GRATE) )

+	{

+		FreeFace( f );

+		return NULL;

+	}

+

+	if ( p->nodes[pside]->contents & MASK_WATER )

+	{

+		f->fogVolumeLeaf = p->nodes[pside];

+	}

+	else if ( p->nodes[!pside]->contents & MASK_WATER )

+	{

+		f->fogVolumeLeaf = p->nodes[!pside];

+	}

+

+	// If it's the underside of water, we need to figure out what material to use, etc.

+	if( ( p->nodes[pside]->contents & CONTENTS_WATER ) && deltaContents == CONTENTS_WATER )

+	{

+		if ( !AssignBottomWaterMaterialToFace( f ) )

+		{

+			FreeFace( f );

+			return NULL;

+		}

+	}

+

+    //

+    // generate the winding for the face and save face contents

+    //

+	if( pside )

+	{

+		f->w = ReverseWinding(p->winding);

+		f->contents = p->nodes[1]->contents;

+	}

+	else

+	{

+		f->w = CopyWinding(p->winding);

+		f->contents = p->nodes[0]->contents;

+	}

+

+	f->numPrims = 0;

+	f->firstPrimID = 0;

+	

+	// return the created face

+	return f;

+}

+

+/*

+===============

+MakeFaces_r

+

+If a portal will make a visible face,

+mark the side that originally created it

+

+  solid / empty : solid

+  solid / water : solid

+  water / empty : water

+  water / water : none

+===============

+*/

+void MakeFaces_r (node_t *node)

+{

+	portal_t	*p;

+	int			s;

+

+	// recurse down to leafs

+	if (node->planenum != PLANENUM_LEAF)

+	{

+		MakeFaces_r (node->children[0]);

+		MakeFaces_r (node->children[1]);

+

+		// merge together all visible faces on the node

+		if (!nomerge)

+			MergeFaceList(&node->faces);

+		if (!nosubdiv)

+			SubdivideFaceList(&node->faces);

+

+		return;

+	}

+

+	// solid leafs never have visible faces

+	if (node->contents & CONTENTS_SOLID)

+		return;

+

+	// see which portals are valid

+	for (p=node->portals ; p ; p = p->next[s])

+	{

+		s = (p->nodes[1] == node);

+

+		p->face[s] = FaceFromPortal (p, s);

+		if (p->face[s])

+		{

+			c_nodefaces++;

+			p->face[s]->next = p->onnode->faces;

+			p->onnode->faces = p->face[s];

+		}

+	}

+}

+

+typedef winding_t *pwinding_t;

+

+static void PrintWinding( winding_t *w )

+{

+	int i;

+	Msg( "\t---\n" );

+	for( i = 0; i < w->numpoints; i++ )

+	{

+		Msg( "\t%f %f %f\n", w->p[i].x, w->p[i].y, w->p[i].z );

+	}

+}

+

+//-----------------------------------------------------------------------------

+// Purpose: Adds a winding to the current list of primverts

+// Input  : *w - the winding

+//			*pIndices - The output indices

+//			vertStart - the starting vert index

+//			vertCount - current count

+// Output : int - output count including new verts from this winding

+//-----------------------------------------------------------------------------

+int AddWindingToPrimverts( const winding_t *w, unsigned short *pIndices, int vertStart, int vertCount )

+{

+	for( int i = 0; i < w->numpoints; i++ )

+	{

+		int j;

+		for( j = vertStart; j < vertStart + vertCount; j++ )

+		{

+			Vector tmp = g_primverts[j].pos - w->p[i];

+

+			if( tmp.LengthSqr() < POINT_EPSILON*POINT_EPSILON )

+			{

+				pIndices[i] = j;

+				break;

+			}

+		}

+		if ( j >= vertStart + vertCount )

+		{

+			pIndices[i] = j;

+			g_primverts[j].pos = w->p[i];

+			vertCount++;

+			g_numprimverts++;

+			if ( g_numprimverts > MAX_MAP_PRIMVERTS )

+			{

+				Error( "Exceeded max water verts.\nIncrease surface subdivision size or lower your subdivision size in vmt files! (%d>%d)\n", 

+					( int )g_numprimverts, ( int )MAX_MAP_PRIMVERTS );

+			}

+		}

+	}

+

+	return vertCount;

+}

+

+

+

+#pragma optimize( "g", off )

+#define USE_TRISTRIPS

+

+// UNDONE: Should split this function into subdivide and primitive building parts

+// UNDONE: We should try building strips of shared verts for all water faces in a leaf

+//			since those will be drawn concurrently anyway.  It should be more efficient.

+static void SubdivideFaceBySubdivSize( face_t *f, float subdivsize )

+{

+	// garymcthack - REFACTOR ME!!!

+	

+	vec_t dummy;

+	Vector hackNormal;

+	WindingPlane( f->w, hackNormal, &dummy );

+

+	// HACK - only subdivide stuff that is facing up or down (for water)

+	if( fabs(hackNormal[2]) < .9f )

+	{

+		return;

+	}

+

+	// Get the extents of the surface.

+	// garymcthack - this assumes a surface of constant z for now (for water). . can generalize later.

+	subdivsize = ( int )subdivsize;

+	winding_t *w;

+	w = CopyWinding( f->w );

+

+	Vector min, max;

+	WindingBounds( w, min, max );

+

+#if 0

+	Msg( "START WINDING: \n" );

+	PrintWinding( w );

+#endif

+	int xStart, yStart, xEnd, yEnd, xSteps, ySteps;

+	xStart = ( int )subdivsize * ( int )( ( min[0] - subdivsize ) / subdivsize );

+	xEnd = ( int )subdivsize * ( int )( ( max[0] + subdivsize ) / subdivsize );

+	yStart = ( int )subdivsize * ( int )( ( min[1] - subdivsize ) / subdivsize );

+	yEnd = ( int )subdivsize * ( int )( ( max[1] + subdivsize ) / subdivsize );

+	xSteps = ( xEnd - xStart ) / subdivsize;

+	ySteps = ( yEnd - yStart ) / subdivsize;

+	int x, y;

+	int xi, yi;

+	winding_t **windings = ( winding_t ** )new pwinding_t[xSteps * ySteps];

+	memset( windings, 0, sizeof( winding_t * ) * xSteps * ySteps );

+

+	for( yi = 0, y = yStart; y < yEnd; y += ( int )subdivsize, yi++ )

+	{

+		for( xi = 0, x = xStart; x < xEnd; x += ( int )subdivsize, xi++ )

+		{

+			winding_t *tempWinding, *frontWinding, *backWinding;

+			float planeDist;

+			Vector normal;

+			normal.Init( 1.0f, 0.0f, 0.0f );

+			planeDist = ( float )x;

+			tempWinding = CopyWinding( w );

+			ClipWindingEpsilon( tempWinding, normal, planeDist, ON_EPSILON, 

+				&frontWinding, &backWinding );

+			if( tempWinding )

+			{

+				FreeWinding( tempWinding );

+			}

+			if( backWinding )

+			{

+				FreeWinding( backWinding );

+			}

+			if( !frontWinding )

+			{

+				continue;

+			}

+			tempWinding = frontWinding;

+

+			normal.Init( -1.0f, 0.0f, 0.0f );

+			planeDist = -( float )( x + subdivsize );

+			ClipWindingEpsilon( tempWinding, normal, planeDist, ON_EPSILON, 

+				&frontWinding, &backWinding );

+			if( tempWinding )

+			{

+				FreeWinding( tempWinding );

+			}

+			if( backWinding )

+			{

+				FreeWinding( backWinding );

+			}

+			if( !frontWinding )

+			{

+				continue;

+			}

+			tempWinding = frontWinding;

+

+			normal.Init( 0.0f, 1.0f, 0.0f );

+			planeDist = ( float )y;

+			ClipWindingEpsilon( tempWinding, normal, planeDist, ON_EPSILON, 

+				&frontWinding, &backWinding );

+			if( tempWinding )

+			{

+				FreeWinding( tempWinding );

+			}

+			if( backWinding )

+			{

+				FreeWinding( backWinding );

+			}

+			if( !frontWinding )

+			{

+				continue;

+			}

+			tempWinding = frontWinding;

+

+			normal.Init( 0.0f, -1.0f, 0.0f );

+			planeDist = -( float )( y + subdivsize );

+			ClipWindingEpsilon( tempWinding, normal, planeDist, ON_EPSILON, 

+				&frontWinding, &backWinding );

+			if( tempWinding )

+			{

+				FreeWinding( tempWinding );

+			}

+			if( backWinding )

+			{

+				FreeWinding( backWinding );

+			}

+			if( !frontWinding )

+			{

+				continue;

+			}

+

+#if 0

+			Msg( "output winding:\n" );

+			PrintWinding( frontWinding );

+#endif

+			

+			if( frontWinding )

+			{

+				windings[xi + yi * xSteps] = frontWinding;

+			}

+		}

+	}

+	FreeWinding( w );

+	dprimitive_t &newPrim = g_primitives[g_numprimitives];

+	f->firstPrimID = g_numprimitives;

+	f->numPrims = 1;

+	newPrim.firstIndex = g_numprimindices;

+	newPrim.firstVert = g_numprimverts;

+	newPrim.indexCount = 0;

+	newPrim.vertCount = 0;

+#ifdef USE_TRISTRIPS

+	newPrim.type = PRIM_TRISTRIP;

+#else

+	newPrim.type = PRIM_TRILIST;

+#endif

+

+	CUtlVector<WORD> triListIndices;

+	int i;

+	for( i = 0; i < xSteps * ySteps; i++ )

+	{

+		if( !windings[i] )

+		{

+			continue;

+		}

+		unsigned short *pIndices = 

+			( unsigned short * )_alloca( windings[i]->numpoints * sizeof( unsigned short ) );

+		// find indices for the verts.

+		newPrim.vertCount = AddWindingToPrimverts( windings[i], pIndices, newPrim.firstVert, newPrim.vertCount );

+

+		// Now that we have indices for the verts, fan-tesselate the polygon and spit out tris.

+		for( int j = 0; j < windings[i]->numpoints - 2; j++ )

+		{

+			triListIndices.AddToTail( pIndices[0] );

+			triListIndices.AddToTail( pIndices[j+1] );

+			triListIndices.AddToTail( pIndices[j+2] );

+		}

+	}

+

+	delete [] windings;

+	// We've already updated the verts and have a trilist. . let's strip it!

+	if( !triListIndices.Size() )

+	{

+		return;

+	}

+	

+#ifdef USE_TRISTRIPS

+	int numTristripIndices;

+	WORD *pStripIndices = NULL;

+	Stripify( triListIndices.Size() / 3, triListIndices.Base(), &numTristripIndices, 

+		&pStripIndices );

+	Assert( pStripIndices );

+

+	// FIXME: Should also call ComputeVertexPermutation and reorder the verts.

+

+	for( i = 0; i < numTristripIndices; i++ )

+	{

+		Assert( pStripIndices[i] >= newPrim.firstVert && 

+			pStripIndices[i] < newPrim.firstVert + newPrim.vertCount );

+		g_primindices[newPrim.firstIndex + newPrim.indexCount] = pStripIndices[i];

+		newPrim.indexCount++;

+		g_numprimindices++;

+		if( g_numprimindices > MAX_MAP_PRIMINDICES )

+		{

+			Error( "Exceeded max water indicies.\nIncrease surface subdivision size! (%d>%d)\n", g_numprimindices, MAX_MAP_PRIMINDICES );

+		}

+	}

+	delete [] pStripIndices;

+#else

+	for( i = 0; i < triListIndices.Size(); i++ )

+	{

+		g_primindices[newPrim.firstIndex + newPrim.indexCount] = triListIndices[i];

+		newPrim.indexCount++;

+		g_numprimindices++;

+		if( g_numprimindices > MAX_MAP_PRIMINDICES )

+		{

+			Error( "Exceeded max water indicies.\nIncrease surface subdivision size! (%d>%d)\n", g_numprimindices, MAX_MAP_PRIMINDICES );

+		}

+	}

+#endif

+	g_numprimitives++; // don't increment until we get here and are sure that we have a primitive.

+	if( g_numprimitives > MAX_MAP_PRIMITIVES )

+	{

+		Error( "Exceeded max water primitives.\nIncrease surface subdivision size! (%d>%d)\n", ( int )g_numprimitives, ( int )MAX_MAP_PRIMITIVES );

+	}

+}

+

+void SubdivideFaceBySubdivSize( face_t *f )

+{

+	if( f->numpoints == 0 || f->split[0] || f->split[1] || f->merged || !f->w )

+	{

+		return;

+	}

+	// see if the face needs to be subdivided.

+	texinfo_t *pTexInfo = &texinfo[f->texinfo];

+	dtexdata_t *pTexData = GetTexData( pTexInfo->texdata );

+	bool bFound;

+	const char *pMaterialName = TexDataStringTable_GetString( pTexData->nameStringTableID );

+	MaterialSystemMaterial_t matID = 

+		FindOriginalMaterial( pMaterialName, &bFound, false );

+

+	if( !bFound )

+	{

+		return;

+	}

+	const char *subdivsizeString = GetMaterialVar( matID, "$subdivsize" );	

+	if( subdivsizeString )

+	{

+		float subdivSize = atof( subdivsizeString );

+		if( subdivSize > 0.0f )

+		{

+			// NOTE: Subdivision is unsupported and should be phased out

+			Warning("Using subdivision on %s\n", pMaterialName );

+			SubdivideFaceBySubdivSize( f, subdivSize );

+		}

+	}

+}

+

+void SplitSubdividedFaces_Node_r( node_t *node )

+{

+	if (node->planenum == PLANENUM_LEAF)

+	{

+		return;

+	}

+	face_t *f;

+	for( f = node->faces; f ;f = f->next )

+	{

+		SubdivideFaceBySubdivSize( f );

+	}

+

+	//

+	// recursively output the other nodes

+	//	

+	SplitSubdividedFaces_Node_r( node->children[0] );

+	SplitSubdividedFaces_Node_r( node->children[1] );

+}

+

+void SplitSubdividedFaces( face_t *pLeafFaceList, node_t *headnode )

+{

+	// deal with leaf faces.

+	face_t *f = pLeafFaceList;

+	while ( f )

+	{

+		SubdivideFaceBySubdivSize( f );

+		f = f->next;

+	}

+

+	// deal with node faces.

+	SplitSubdividedFaces_Node_r( headnode );

+}

+

+#pragma optimize( "", on )

+

+/*

+============

+MakeFaces

+============

+*/

+void MakeFaces (node_t *node)

+{

+	qprintf ("--- MakeFaces ---\n");

+	c_merge = 0;

+	c_subdivide = 0;

+	c_nodefaces = 0;

+

+	MakeFaces_r (node);

+

+	qprintf ("%5i makefaces\n", c_nodefaces);

+	qprintf ("%5i merged\n", c_merge);

+	qprintf ("%5i subdivided\n", c_subdivide);

+}
\ No newline at end of file