Itsa me, quake3io!

git-svn-id: svn://svn.icculus.org/quake3/trunk@2 edf5b092-35ff-0310-97b2-ce42778d08ea

1 files changed, 978 insertions, 0 deletions

diff --git a/code/bspc/faces.c b/code/bspc/faces.c
new file mode 100755
index 0000000..bcd3ef9
--- /dev/null
+++ b/code/bspc/faces.c
@@ -0,0 +1,978 @@
+/*

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

+Copyright (C) 1999-2005 Id Software, Inc.

+

+This file is part of Quake III Arena source code.

+

+Quake III Arena source code is free software; you can redistribute it

+and/or modify it under the terms of the GNU General Public License as

+published by the Free Software Foundation; either version 2 of the License,

+or (at your option) any later version.

+

+Quake III Arena source code is distributed in the hope that it will be

+useful, but WITHOUT ANY WARRANTY; without even the implied warranty of

+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the

+GNU General Public License for more details.

+

+You should have received a copy of the GNU General Public License

+along with Foobar; if not, write to the Free Software

+Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA

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

+*/

+// faces.c

+

+#include "qbsp.h"

+#include "l_mem.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.5

+#define	OFF_EPSILON			0.5

+

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

+

+vec3_t	edge_dir;

+vec3_t	edge_start;

+vec_t	edge_len;

+

+int		num_edge_verts;

+int		edge_verts[MAX_MAP_VERTS];

+

+face_t *NewFaceFromFace (face_t *f);

+

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

+

+typedef struct hashvert_s

+{

+	struct hashvert_s	*next;

+	int		num;

+} hashvert_t;

+

+

+#define	HASH_SIZE	64

+

+

+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 (vec3_t vec)

+{

+	int			x, y;

+

+	x = (4096 + (int)(vec[0]+0.5)) >> 7;

+	y = (4096 + (int)(vec[1]+0.5)) >> 7;

+

+	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 (vec3_t in)

+{

+	int			h;

+	int			i;

+	float		*p;

+	vec3_t		vert;

+	int			vnum;

+

+	c_totalverts++;

+

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

+	{

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

+			vert[i] = Q_rint(in[i]);

+		else

+			vert[i] = in[i];

+	}

+	

+	h = HashVec (vert);

+	

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

+	{

+		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 ("numvertexes == 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 (vec3_t 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] < -4096 || v[i] > 4096)

+			Error ("GetVertexnum: outside +/- 4096");

+	}

+

+	// 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 ("MAX_MAP_VERTS");

+	VectorCopy (v, dv->point);

+	numvertexes++;

+	c_uniqueverts++;

+

+	return numvertexes-1;

+}

+#endif

+

+

+/*

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

+FaceFromSuperverts

+

+The faces vertexes have been 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 (node_t *node, 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 = f->split[0] = NewFaceFromFace (f);

+		newf = f->split[0];

+		newf->next = node->faces;

+		node->faces = 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 = node->faces;

+		node->faces = 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 (node_t *node, 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 ("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 (node, f, 0);

+}

+

+/*

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

+EmitVertexes_r

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

+*/

+void EmitVertexes_r (node_t *node)

+{

+	int		i;

+	face_t	*f;

+

+	if (node->planenum == PLANENUM_LEAF)

+		return;

+

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

+	{

+		EmitFaceVertexes (node, f);

+	}

+

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

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

+}

+

+

+#ifdef USE_HASHING

+/*

+==========

+FindEdgeVerts

+

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

+==========

+*/

+void FindEdgeVerts (vec3_t v1, vec3_t 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 = (4096 + (int)(v1[0]+0.5)) >> 7;

+	y1 = (4096 + (int)(v1[1]+0.5)) >> 7;

+	x2 = (4096 + (int)(v2[0]+0.5)) >> 7;

+	y2 = (4096 + (int)(v2[1]+0.5)) >> 7;

+

+	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 (vec3_t v1, vec3_t 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;

+	vec3_t	delta;

+	vec3_t	exact;

+	vec3_t	off;

+	vec_t	error;

+	vec3_t	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 = VectorLength (off);

+

+		if (fabs(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 ("MAX_SUPERVERTS");

+	superverts[numsuperverts] = p1;

+	numsuperverts++;

+}

+

+/*

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

+FixFaceEdges

+

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

+*/

+void FixFaceEdges (node_t *node, face_t *f)

+{

+	int		p1, p2;

+	int		i;

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

+

+	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 (node, f, base);

+}

+

+/*

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

+FixEdges_r

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

+*/

+void FixEdges_r (node_t *node)

+{

+	int		i;

+	face_t	*f;

+

+	if (node->planenum == PLANENUM_LEAF)

+		return;

+

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

+		FixFaceEdges (node, f);

+

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

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

+}

+

+/*

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

+FixTjuncs

+

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

+*/

+void FixTjuncs (node_t *headnode)

+{

+	// snap and merge all vertexes

+	qprintf ("---- snap verts ----\n");

+	memset (hashverts, 0, sizeof(hashverts));

+	c_totalverts = 0;

+	c_uniqueverts = 0;

+	c_faceoverflows = 0;

+	EmitVertexes_r (headnode);

+	qprintf ("%i unique from %i\n", c_uniqueverts, c_totalverts);

+

+	// break edges on tjunctions

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

+	c_tryedges = 0;

+	c_degenerate = 0;

+	c_facecollapse = 0;

+	c_tjunctions = 0;

+	if (!notjunc)

+		FixEdges_r (headnode);

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

+}

+

+

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

+

+int		c_faces;

+

+face_t	*AllocFace (void)

+{

+	face_t	*f;

+

+	f = GetMemory(sizeof(*f));

+	memset (f, 0, sizeof(*f));

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

+	FreeMemory(f);

+	c_faces--;

+}

+

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

+

+/*

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

+GetEdge

+

+Called by writebsp.

+Don't allow four way edges

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

+*/

+int GetEdge2 (int v1, int v2,  face_t *f)

+{

+	dedge_t	*edge;

+	int		i;

+

+	c_tryedges++;

+

+	if (!noshare)

+	{

+		for (i=firstmodeledge ; i < numedges ; i++)

+		{

+			edge = &dedges[i];

+			if (v1 == edge->v[1] && v2 == edge->v[0]

+			&& edgefaces[i][0]->contents == f->contents)

+			{

+				if (edgefaces[i][1])

+	//				printf ("WARNING: multiple backward edge\n");

+					continue;

+				edgefaces[i][1] = f;

+				return -i;

+			}

+	#if 0

+			if (v1 == edge->v[0] && v2 == edge->v[1])

+			{

+				printf ("WARNING: multiple forward edge\n");

+				return i;

+			}

+	#endif

+		}

+	}

+

+// emit an edge

+	if (numedges >= MAX_MAP_EDGES)

+		Error ("numedges == MAX_MAP_EDGES");

+	edge = &dedges[numedges];

+	numedges++;

+	edge->v[0] = v1;

+	edge->v[1] = v2;

+	edgefaces[numedges-1][0] = f;

+	

+	return numedges-1;

+}

+

+/*

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

+

+FACE MERGING

+

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

+*/

+

+/*

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

+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, vec3_t planenormal)

+{

+	face_t		*newf;

+	winding_t	*nw;

+

+	if (!f1->w || !f2->w)

+		return NULL;

+	if (f1->texinfo != f2->texinfo)

+		return NULL;

+	if (f1->planenum != f2->planenum)	// on front and back sides

+		return NULL;

+	if (f1->contents != f2->contents)

+		return NULL;

+		

+

+	nw = TryMergeWinding (f1->w, f2->w, planenormal);

+	if (!nw)

+		return NULL;

+

+	c_merge++;

+	newf = NewFaceFromFace (f1);

+	newf->w = nw;

+

+	f1->merged = newf;

+	f2->merged = newf;

+

+	return newf;

+}

+

+/*

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

+MergeNodeFaces

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

+*/

+void MergeNodeFaces (node_t *node)

+{

+	face_t	*f1, *f2, *end;

+	face_t	*merged;

+	plane_t	*plane;

+

+	plane = &mapplanes[node->planenum];

+	merged = NULL;

+	

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

+	{

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

+			continue;

+

+		for (f2 = node->faces ; f2 != f1 ; f2=f2->next)

+		{

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

+				continue;

+

+			//IDBUG: always passes the face's node's normal to TryMerge()

+			//regardless of which side the face is on. Approximately 50% of

+			//the time the face will be on the other side of node, and thus

+			//the result of the convex/concave test in TryMergeWinding(),

+			//which depends on the normal, is flipped. This causes faces

+			//that shouldn't be merged to be merged and faces that

+			//should be merged to not be merged. 

+			//the following added line fixes this bug

+			//thanks to: Alexander Malmberg <alexander@malmberg.org>

+			plane = &mapplanes[f1->planenum];

+			//

+			merged = TryMerge (f1, f2, plane->normal);

+			if (!merged)

+				continue;

+

+			// add merged to the end of the node face list 

+			// so it will be checked against all the faces again

+			for (end = node->faces ; 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 (node_t *node, face_t *f)

+{

+	float		mins, maxs;

+	vec_t		v;

+	int			axis, i;

+	texinfo_t	*tex;

+	vec3_t		temp;

+	vec_t		dist;

+	winding_t	*w, *frontw, *backw;

+

+	if (f->merged)

+		return;

+

+// special (non-surface cached) faces don't need subdivision

+	tex = &texinfo[f->texinfo];

+

+	if ( tex->flags & (SURF_WARP|SURF_SKY) )

+	{

+		return;

+	}

+

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

+	{

+		while (1)

+		{

+			mins = 999999;

+			maxs = -999999;

+			

+			VectorCopy (tex->vecs[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 (axis == 2)

+			{	// allow double high walls

+				if (maxs - mins <= subdivide_size/* *2 */)

+					break;

+			}

+			else if (maxs - mins <= subdivide_size)

+				break;

+			

+		// split it

+			c_subdivide++;

+			

+			v = VectorNormalize (temp);

+

+			dist = (mins + subdivide_size - 16)/v;

+

+			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 = node->faces;

+			node->faces = f->split[0];

+

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

+			f->split[1]->w = backw;

+			f->split[1]->next = node->faces;

+			node->faces = f->split[1];

+

+			SubdivideFace (node, f->split[0]);

+			SubdivideFace (node, f->split[1]);

+			return;

+		}

+	}

+}

+

+void SubdivideNodeFaces (node_t *node)

+{

+	face_t	*f;

+

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

+	{

+		SubdivideFace (node, f);

+	}

+}

+

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

+

+int	c_nodefaces;

+

+

+/*

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

+FaceFromPortal

+

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

+*/

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

+{

+	face_t	*f;

+	side_t	*side;

+

+	side = p->side;

+	if (!side)

+		return NULL;	// portal does not bridge different visible contents

+

+	f = AllocFace ();

+

+	f->texinfo = side->texinfo;

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

+	f->portal = p;

+

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

+		&& VisibleContents(p->nodes[!pside]->contents^p->nodes[pside]->contents) == CONTENTS_WINDOW )

+		return NULL;	// don't show insides of windows

+

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

+	}

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

+			MergeNodeFaces (node);

+		if (!nosubdiv)

+			SubdivideNodeFaces (node);

+

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

+		}

+	}

+}

+

+/*

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

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

+}