Fix line endings. WHAMMY.

1 files changed, 1809 insertions, 1809 deletions

diff --git a/mp/src/utils/vbsp/faces.cpp b/mp/src/utils/vbsp/faces.cpp
index 13ed9d61..f6ec3ee3 100644
--- a/mp/src/utils/vbsp/faces.cpp
+++ b/mp/src/utils/vbsp/faces.cpp
@@ -1,1810 +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);

+//========= 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