faces.cpp

hl2 source code. Do not use it illegal.

// faces.c

#include "vbsp.h"
#include "utlvector.h"
#include "utilmatlib.h"
#include <float.h>
#include "mstristrip.h"
#include "vstdlib/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.25
#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;

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 ("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 (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");
	}

	// 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 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 ("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 ("MAX_SUPERVERTS");
	superverts[numsuperverts] = p1;
	numsuperverts++;
}

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

	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;