faces.c

quakeIII源码这个不用我多说吧

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