faces.c

quakeIII源码这个不用我多说吧

		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 <[e-mail]>
			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);
}