newlines fixed

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

1 files changed, 978 insertions, 978 deletions

diff --git a/code/bspc/faces.c b/code/bspc/faces.c
index bcd3ef9..f05f5ae 100755
--- a/code/bspc/faces.c
+++ b/code/bspc/faces.c
@@ -1,978 +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);

-}

+/*
+===========================================================================
+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);
+}