l_poly.c

quakeIII源码这个不用我多说吧

		sprintf(windingerror, "winding %f area", area);
		return WE_SMALLAREA;
	} //end if

	WindingPlane (w, facenormal, &facedist);
	
	for (i=0 ; i<w->numpoints ; i++)
	{
		p1 = w->p[i];

		for (j=0 ; j<3 ; j++)
		{
			if (p1[j] > BOGUS_RANGE || p1[j] < -BOGUS_RANGE)
			{
				sprintf(windingerror, "winding point %d BUGUS_RANGE \'%f %f %f\'", j, p1[0], p1[1], p1[2]);
				return WE_POINTBOGUSRANGE;
			} //end if
		} //end for

		j = i+1 == w->numpoints ? 0 : i+1;
		
	// check the point is on the face plane
		d = DotProduct (p1, facenormal) - facedist;
		if (d < -ON_EPSILON || d > ON_EPSILON)
		{
			sprintf(windingerror, "winding point %d off plane", i);
			return WE_POINTOFFPLANE;
		} //end if
	
	// check the edge isnt degenerate
		p2 = w->p[j];
		VectorSubtract (p2, p1, dir);
		
		if (VectorLength (dir) < ON_EPSILON)
		{
			sprintf(windingerror, "winding degenerate edge %d-%d", i, j);
			return WE_DEGENERATEEDGE;
		} //end if
			
		CrossProduct (facenormal, dir, edgenormal);
		VectorNormalize (edgenormal);
		edgedist = DotProduct (p1, edgenormal);
		edgedist += ON_EPSILON;
		
	// all other points must be on front side
		for (j=0 ; j<w->numpoints ; j++)
		{
			if (j == i)
				continue;
			d = DotProduct (w->p[j], edgenormal);
			if (d > edgedist)
			{
				sprintf(windingerror, "winding non-convex");
				return WE_NONCONVEX;
			} //end if
		} //end for
	} //end for
	return WE_NONE;
} //end of the function WindingError
//===========================================================================
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
void RemoveEqualPoints(winding_t *w, float epsilon)
{
	int i, nump;
	vec3_t v;
	vec3_t p[MAX_POINTS_ON_WINDING];

	VectorCopy(w->p[0], p[0]);
	nump = 1;
	for (i = 1; i < w->numpoints; i++)
	{
		VectorSubtract(w->p[i], p[nump-1], v);
		if (VectorLength(v) > epsilon)
		{
			if (nump >= MAX_POINTS_ON_WINDING)
				Error("RemoveColinearPoints: MAX_POINTS_ON_WINDING");
			VectorCopy (w->p[i], p[nump]);
			nump++;
		} //end if
	} //end for

	if (nump == w->numpoints)
		return;

	w->numpoints = nump;
	memcpy(w->p, p, nump * sizeof(p[0]));
} //end of the function RemoveEqualPoints
//===========================================================================
// adds the given point to a winding at the given spot
// (for instance when spot is zero then the point is added at position zero)
// the original winding is NOT freed
//
// Parameter:				-
// Returns:					the new winding with the added point
// Changes Globals:		-
//===========================================================================
winding_t *AddWindingPoint(winding_t *w, vec3_t point, int spot)
{
	int i, j;
	winding_t *neww;

	if (spot > w->numpoints)
	{
		Error("AddWindingPoint: num > w->numpoints");
	} //end if
	if (spot < 0)
	{
		Error("AddWindingPoint: num < 0");
	} //end if
	neww = AllocWinding(w->numpoints + 1);
	neww->numpoints = w->numpoints + 1;
	for (i = 0, j = 0; i < neww->numpoints; i++)
	{
		if (i == spot)
		{
			VectorCopy(point, neww->p[i]);
		} //end if
		else
		{
			VectorCopy(w->p[j], neww->p[i]);
			j++;
		} //end else
	} //end for
	return neww;
} //end of the function AddWindingPoint
//===========================================================================
// the position where the new point should be added in the winding is
// stored in *spot
//
// Parameter:				-
// Returns:					true if the point is on the winding
// Changes Globals:		-
//===========================================================================
#define MELT_ON_EPSILON		0.2

int PointOnWinding(winding_t *w, vec3_t normal, float dist, vec3_t point, int *spot)
{
	int i, j;
	vec3_t v1, v2;
	vec3_t edgenormal, edgevec;
	float edgedist, dot;

	*spot = 0;
	//the point must be on the winding plane
	dot = DotProduct(point, normal) - dist;
	if (dot < -MELT_ON_EPSILON || dot > MELT_ON_EPSILON) return false;
	//
	for (i = 0; i < w->numpoints; i++)
	{
		j = (i+1) % w->numpoints;
		//get a plane orthogonal to the winding plane through the edge
		VectorSubtract(w->p[j], w->p[i], edgevec);
		CrossProduct(normal, edgevec, edgenormal);
		VectorNormalize(edgenormal);
		edgedist = DotProduct(edgenormal, w->p[i]);
		//point must be not too far from the plane
		dot = DotProduct(point, edgenormal) - edgedist;
		if (dot < -MELT_ON_EPSILON || dot > MELT_ON_EPSILON) continue;
		//vector from first point of winding to the point to test
		VectorSubtract(point, w->p[i], v1);
		//vector from second point of winding to the point to test
		VectorSubtract(point, w->p[j], v2);
		//if the length of the vector is not larger than 0.5 units then
		//the point is assumend to be the same as one of the winding points
		if (VectorNormalize(v1) < 0.5) return false;
		if (VectorNormalize(v2) < 0.5) return false;
		//point must be between the two winding points
		//(the two vectors must be directed towards each other, and on the
		//same straight line)
		if (DotProduct(v1, v2) < -0.99)
		{
			*spot = i + 1;
			return true;
		} //end if
	} //end for
	return false;
} //end of the function PointOnWinding
//===========================================================================
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
int FindPlaneSeperatingWindings(winding_t *w1, winding_t *w2, vec3_t dir,
											vec3_t normal, float *dist)
{
	int i, i2, j, j2, n;
	int sides1[3], sides2[3];
	float dist1, dist2, dot, diff;
	vec3_t normal1, normal2;
	vec3_t v1, v2;

	for (i = 0; i < w1->numpoints; i++)
	{
		i2 = (i+1) % w1->numpoints;
		//
		VectorSubtract(w1->p[i2], w1->p[i], v1);
		if (VectorLength(v1) < 0.1)
		{
			//Log_Write("FindPlaneSeperatingWindings: winding1 with degenerate edge\r\n");
			continue;
		} //end if
		CrossProduct(v1, dir, normal1);
		VectorNormalize(normal1);
		dist1 = DotProduct(normal1, w1->p[i]);
		//
		for (j = 0; j < w2->numpoints; j++)
		{
			j2 = (j+1) % w2->numpoints;
			//
			VectorSubtract(w2->p[j2], w2->p[j], v2);
			if (VectorLength(v2) < 0.1)
			{
				//Log_Write("FindPlaneSeperatingWindings: winding2 with degenerate edge\r\n");
				continue;
			} //end if
			CrossProduct(v2, dir, normal2);
			VectorNormalize(normal2);
			dist2 = DotProduct(normal2, w2->p[j]);
			//
			diff = dist1 - dist2;
			if (diff < -0.1 || diff > 0.1)
			{
				dist2 = -dist2;
				VectorNegate(normal2, normal2);
				diff = dist1 - dist2;
				if (diff < -0.1 || diff > 0.1) continue;
			} //end if
			//check if the normal vectors are equal
			for (n = 0; n < 3; n++)
			{
				diff = normal1[n] - normal2[n];
				if (diff < -0.0001 || diff > 0.0001) break;
			} //end for
			if (n != 3) continue;
			//check on which side of the seperating plane the points of
			//the first winding are
			sides1[0] = sides1[1] = sides1[2] = 0;
			for (n = 0; n < w1->numpoints; n++)
			{
				dot = DotProduct(w1->p[n], normal1) - dist1;
				if (dot > 0.1) sides1[0]++;
				else if (dot < -0.1) sides1[1]++;
				else sides1[2]++;
			} //end for
			//check on which side of the seperating plane the points of
			//the second winding are
			sides2[0] = sides2[1] = sides2[2] = 0;
			for (n = 0; n < w2->numpoints; n++)
			{
				//used normal1 and dist1 (they are equal to normal2 and dist2)
				dot = DotProduct(w2->p[n], normal1) - dist1;
				if (dot > 0.1) sides2[0]++;
				else if (dot < -0.1) sides2[1]++;
				else sides2[2]++;
			} //end for
			//if the first winding has points at both sides
			if (sides1[0] && sides1[1])
			{
				Log_Write("FindPlaneSeperatingWindings: winding1 non-convex\r\n");
				continue;
			} //end if
			//if the second winding has points at both sides
			if (sides2[0] && sides2[1])
			{
				Log_Write("FindPlaneSeperatingWindings: winding2 non-convex\r\n");
				continue;
			} //end if
			//
			if ((!sides1[0] && !sides1[1]) || (!sides2[0] && !sides2[1]))
			{
				//don't use one of the winding planes as the seperating plane
				continue;
			} //end if
			//the windings must be at different sides of the seperating plane
			if ((!sides1[0] && !sides2[1]) || (!sides1[1] && !sides2[0]))
			{
				VectorCopy(normal1, normal);
				*dist = dist1;
				return true;
			} //end if
		} //end for
	} //end for
	return false;
} //end of the function FindPlaneSeperatingWindings
//===========================================================================
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
#define WCONVEX_EPSILON		0.2

int WindingsNonConvex(winding_t *w1, winding_t *w2,
							 vec3_t normal1, vec3_t normal2,
							 float dist1, float dist2)
{
	int i;

	if (!w1 || !w2) return false;

	//check if one of the points of face1 is at the back of the plane of face2
	for (i = 0; i < w1->numpoints; i++)
	{
		if (DotProduct(normal2, w1->p[i]) - dist2 > WCONVEX_EPSILON) return true;
	} //end for
	//check if one of the points of face2 is at the back of the plane of face1
	for (i = 0; i < w2->numpoints; i++)
	{
		if (DotProduct(normal1, w2->p[i]) - dist1 > WCONVEX_EPSILON) return true;
	} //end for

	return false;
} //end of the function WindingsNonConvex
//===========================================================================
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
/*
#define VERTEX_EPSILON		0.5

qboolean EqualVertexes(vec3_t v1, vec3_t v2)
{
	float diff;

	diff = v1[0] - v2[0];
	if (diff > -VERTEX_EPSILON && diff < VERTEX_EPSILON)
	{
		diff = v1[1] - v2[1];
		if (diff > -VERTEX_EPSILON && diff < VERTEX_EPSILON)
		{
			diff = v1[2] - v2[2];
			if (diff > -VERTEX_EPSILON && diff < VERTEX_EPSILON)
			{
				return true;
			} //end if
		} //end if
	} //end if
	return false;
} //end of the function EqualVertexes

#define	CONTINUOUS_EPSILON	0.001

winding_t *AAS_MergeWindings(winding_t *w1, winding_t *w2, vec3_t windingnormal)
{
	int n, i, k;
	vec3_t normal, delta;
	winding_t *winding, *neww;
	float dist, dot;
	int p1, p2;
	int points[2][64];
	int numpoints[2] = {0, 0};
	int newnumpoints;
	int keep[2];

	if (!FindPlaneSeperatingWindings(w1, w2, windingnormal, normal, &dist)) return NULL;

	//for both windings
	for (n = 0; n < 2; n++)
	{
		if (n == 0) winding = w1;
		else winding = w2;
		//get the points of the winding which are on the seperating plane
		for (i = 0; i < winding->numpoints; i++)
		{
			dot = DotProduct(winding->p[i], normal) - dist;
			if (dot > -ON_EPSILON && dot < ON_EPSILON)
			{
				//don't allow more than 64 points on the seperating plane
				if (numpoints[n] >= 64) Error("AAS_MergeWindings: more than 64 points on seperating plane\n");
				points[n][numpoints[n]++] = i;
			} //end if
		} //end for
		//there must be at least two points of each winding on the seperating plane
		if (numpoints[n] < 2) return NULL;
	} //end for

	//if the first point of winding1 (which is on the seperating plane) is unequal
	//to the last point of winding2 (which is on the seperating plane)
	if (!EqualVertexes(w1->p[points[0][0]], w2->p[points[1][numpoints[1]-1]]))
	{
		return NULL;
	} //end if
	//if the last point of winding1 (which is on the seperating plane) is unequal
	//to the first point of winding2 (which is on the seperating plane)
	if (!EqualVertexes(w1->p[points[0][numpoints[0]-1]], w2->p[points[1][0]]))
	{
		return NULL;
	} //end if
	//
	// check slope of connected lines
	// if the slopes are colinear, the point can be removed
	//
	//first point of winding1 which is on the seperating plane
	p1 = points[0][0];
	//point before p1
	p2 = (p1 + w1->numpoints - 1) % w1->numpoints;
	VectorSubtract(w1->p[p1], w1->p[p2], delta);
	CrossProduct(windingnormal, delta, normal);
	VectorNormalize(normal, normal);

	//last point of winding2 which is on the seperating plane
	p1 = points[1][numpoints[1]-1];
	//point after p1
	p2 = (p1 + 1) % w2->numpoints;
	VectorSubtract(w2->p[p2], w2->p[p1], delta);
	dot = DotProduct(delta, normal);
	if (dot > CONTINUOUS_EPSILON) return NULL; //merging would create a non-convex polygon
	keep[0] = (qboolean)(dot < -CONTINUOUS_EPSILON);

	//first point of winding2 which is on the seperating plane
	p1 = points[1][0];
	//point before p1
	p2 = (p1 + w2->numpoints - 1) % w2->numpoints;
	VectorSubtract(w2->p[p1], w2->p[p2], delta);
	CrossProduct(windingnormal, delta, normal);
	VectorNormalize(normal, normal);

	//last point of winding1 which is on the seperating plane
	p1 = points[0][numpoints[0]-1];
	//point after p1
	p2 = (p1 + 1) % w1->numpoints;
	VectorSubtract(w1->p[p2], w1->p[p1], delta);
	dot = DotProduct(delta, normal);
	if (dot > CONTINUOUS_EPSILON) return NULL; //merging would create a non-convex polygon
	keep[1] = (qboolean)(dot < -CONTINUOUS_EPSILON);

	//number of points on the new winding
	newnumpoints = w1->numpoints - numpoints[0] + w2->numpoints - numpoints[1] + 2;
	//allocate the winding
	neww = AllocWinding(newnumpoints);
	neww->numpoints = newnumpoints;
	//copy all the points
	k = 0;
	//for both windings
	for (n = 0; n < 2; n++)
	{
		if (n == 0) winding = w1;
		else winding = w2;
		//copy the points of the winding starting with the last point on the
		//seperating plane and ending before the first point on the seperating plane
		for (i = points[n][numpoints[n]-1]; i != points[n][0]; i = (i+1)%winding->numpoints)
		{
			if (k >= newnumpoints)
			{
				Log_Print("numpoints[0] = %d\n", numpoints[0]);
				Log_Print("numpoints[1] = %d\n", numpoints[1]);
				Error("AAS_MergeWindings: k = %d >= newnumpoints = %d\n", k, newnumpoints);
			} //end if
			VectorCopy(winding->p[i], neww->p[k]);
			k++;
		} //end for
	} //end for
	RemoveEqualPoints(neww);
	if (!WindingIsOk(neww, 1))
	{
		Log_Print("AAS_MergeWindings: winding not ok after merging\n");
		FreeWinding(neww);
		return NULL;
	} //end if
	return neww;
} //end of the function AAS_MergeWindings*/
//#endif //ME