X-Git-Url: http://de.git.xonotic.org/?a=blobdiff_plain;f=collision.c;h=7387a9e597a73f178aa57c4501b1562751022e7e;hb=bce4204c780051d1db25c6fef768315b4c217dd4;hp=11300643e15966f6eba5fea4eb9826ff5f0c3f26;hpb=340c4d637bbc0346e545c0ef5f8509c651aa72c6;p=xonotic%2Fdarkplaces.git

diff --git a/collision.c b/collision.c
index 11300643..7387a9e5 100644
--- a/collision.c
+++ b/collision.c
@@ -1,6 +1,6 @@
 
 #include "quakedef.h"
-#include "winding.h"
+#include "polygon.h"
 
 #define COLLISION_SNAPSCALE (32.0f)
 #define COLLISION_SNAP (1.0f / COLLISION_SNAPSCALE)
@@ -328,7 +328,7 @@ void Collision_PrintBrushAsQHull(colbrushf_t *brush, const char *name)
 
 void Collision_ValidateBrush(colbrushf_t *brush)
 {
-	int j, k, pointsoffplanes, printbrush;
+	int j, k, pointsoffplanes, pointonplanes, pointswithinsufficientplanes, printbrush;
 	float d;
 	printbrush = false;
 	if (!brush->numpoints)
@@ -347,11 +347,14 @@ void Collision_ValidateBrush(colbrushf_t *brush)
 	if (brush->numplanes)
 	{
 		pointsoffplanes = 0;
+		pointswithinsufficientplanes = 0;
 		for (k = 0;k < brush->numplanes;k++)
-		{
 			if (DotProduct(brush->planes[k].normal, brush->planes[k].normal) < 0.0001f)
 				Con_Printf("Collision_ValidateBrush: plane #%i (%f %f %f %f) is degenerate\n", k, brush->planes[k].normal[0], brush->planes[k].normal[1], brush->planes[k].normal[2], brush->planes[k].dist);
-			for (j = 0;j < brush->numpoints;j++)
+		for (j = 0;j < brush->numpoints;j++)
+		{
+			pointonplanes = 0;
+			for (k = 0;k < brush->numplanes;k++)
 			{
 				d = DotProduct(brush->points[j].v, brush->planes[k].normal) - brush->planes[k].dist;
 				if (d > (1.0f / 8.0f))
@@ -359,9 +362,18 @@ void Collision_ValidateBrush(colbrushf_t *brush)
 					Con_Printf("Collision_ValidateBrush: point #%i (%f %f %f) infront of plane #%i (%f %f %f %f)\n", j, brush->points[j].v[0], brush->points[j].v[1], brush->points[j].v[2], k, brush->planes[k].normal[0], brush->planes[k].normal[1], brush->planes[k].normal[2], brush->planes[k].dist);
 					printbrush = true;
 				}
-				if (fabs(d) > 0.01f)
+				if (fabs(d) > 0.125f)
 					pointsoffplanes++;
+				else
+					pointonplanes++;
 			}
+			if (pointonplanes < 3)
+				pointswithinsufficientplanes++;
+		}
+		if (pointswithinsufficientplanes)
+		{
+			Con_Print("Collision_ValidateBrush: some points have insufficient planes, every point must be on at least 3 planes to form a corner.\n");
+			printbrush = true;
 		}
 		if (pointsoffplanes == 0) // all points are on all planes
 		{
@@ -402,135 +414,169 @@ float furthestplanedist_float(const float *normal, const colpointf_t *points, in
 }
 
 
-colbrushf_t *Collision_NewBrushFromPlanes(mempool_t *mempool, int numoriginalplanes, const mplane_t *originalplanes, int supercontents, winding_t *temp1, winding_t *temp2)
+colbrushf_t *Collision_NewBrushFromPlanes(mempool_t *mempool, int numoriginalplanes, const mplane_t *originalplanes, int supercontents)
 {
-	int j, k, m;
-	int numpoints, maxpoints, numplanes, maxplanes, numelements, maxelements, numtriangles, numpolypoints, maxpolypoints;
-	winding_t *w, *temp, *othertemp;
+	int j, k, m, w;
+	int numpointsbuf = 0, maxpointsbuf = 256, numplanesbuf = 0, maxplanesbuf = 256, numelementsbuf = 0, maxelementsbuf = 256;
 	colbrushf_t *brush;
 	colpointf_t pointsbuf[256];
 	colplanef_t planesbuf[256];
 	int elementsbuf[1024];
 	int polypointbuf[256];
+	int pmaxpoints = 64;
+	int pnumpoints;
+	double p[2][3*64];
+#if 0
+	// enable these if debugging to avoid seeing garbage in unused data
+	memset(pointsbuf, 0, sizeof(pointsbuf));
+	memset(planesbuf, 0, sizeof(planesbuf));
+	memset(elementsbuf, 0, sizeof(elementsbuf));
+	memset(polypointbuf, 0, sizeof(polypointbuf));
+	memset(p, 0, sizeof(p));
+#endif
 	// construct a collision brush (points, planes, and renderable mesh) from
 	// a set of planes, this also optimizes out any unnecessary planes (ones
 	// whose polygon is clipped away by the other planes)
-	numpoints = 0;maxpoints = 256;
-	numplanes = 0;maxplanes = 256;
-	numelements = 0;maxelements = 1024;
-	numtriangles = 0;
-	maxpolypoints = 256;
 	for (j = 0;j < numoriginalplanes;j++)
 	{
 		// add the plane uniquely (no duplicates)
-		for (k = 0;k < numplanes;k++)
+		for (k = 0;k < numplanesbuf;k++)
 			if (VectorCompare(planesbuf[k].normal, originalplanes[j].normal) && planesbuf[k].dist == originalplanes[j].dist)
 				break;
 		// if the plane is a duplicate, skip it
-		if (k < numplanes)
+		if (k < numplanesbuf)
 			continue;
 		// check if there are too many and skip the brush
-		if (numplanes >= 256)
+		if (numplanesbuf >= maxplanesbuf)
 		{
 			Con_Print("Mod_Q3BSP_LoadBrushes: failed to build collision brush: too many planes for buffer\n");
 			return NULL;
 		}
 
 		// create a large polygon from the plane
-		w = temp1;
-		othertemp = temp2;
-		BufWinding_NewFromPlane(w, originalplanes[j].normal[0], originalplanes[j].normal[1], originalplanes[j].normal[2], originalplanes[j].dist);
+		w = 0;
+		PolygonD_QuadForPlane(p[w], originalplanes[j].normal[0], originalplanes[j].normal[1], originalplanes[j].normal[2], originalplanes[j].dist, 1024.0*1024.0*1024.0);
+		pnumpoints = 4;
 		// clip it by all other planes
-		for (k = 0;k < numoriginalplanes && w->numpoints;k++)
+		for (k = 0;k < numoriginalplanes && pnumpoints && pnumpoints <= pmaxpoints;k++)
 		{
 			if (k != j)
 			{
 				// we want to keep the inside of the brush plane so we flip
 				// the cutting plane
-				BufWinding_Divide(w, -originalplanes[k].normal[0], -originalplanes[k].normal[1], -originalplanes[k].normal[2], -originalplanes[k].dist, othertemp, NULL, NULL, NULL);
-				temp = w;
-				w = othertemp;
-				othertemp = temp;
+				PolygonD_Divide(pnumpoints, p[w], -originalplanes[k].normal[0], -originalplanes[k].normal[1], -originalplanes[k].normal[2], -originalplanes[k].dist, 1.0/32.0, pmaxpoints, p[!w], &pnumpoints, 0, NULL, NULL);
+				w = !w;
 			}
 		}
 		// if nothing is left, skip it
-		if (!w->numpoints)
+		if (pnumpoints < 3)
+		{
+			//Con_Printf("Collision_NewBrushFromPlanes: warning: polygon for plane %f %f %f %f clipped away\n", originalplanes[j].normal[0], originalplanes[j].normal[1], originalplanes[j].normal[2], originalplanes[j].dist);
 			continue;
+		}
 
-		// copy off the number of points for later when the winding is freed
-		numpolypoints = w->numpoints;
+		for (k = 0;k < pnumpoints;k++)
+		{
+			int l, m;
+			m = 0;
+			for (l = 0;l < numoriginalplanes;l++)
+				if (fabs(DotProduct(&p[w][k*3], originalplanes[l].normal) - originalplanes[l].dist) < 1.0/8.0)
+					m++;
+			if (m < 3)
+				break;
+		}
+		if (k < pnumpoints)
+		{
+			Con_Printf("Collision_NewBrushFromPlanes: warning: polygon point does not lie on at least 3 planes\n");
+			//return NULL;
+		}
 
 		// check if there are too many polygon vertices for buffer
-		if (numpolypoints > maxpolypoints)
+		if (pnumpoints > pmaxpoints)
 		{
 			Con_Print("Collision_NewBrushFromPlanes: failed to build collision brush: too many points for buffer\n");
 			return NULL;
 		}
 
 		// check if there are too many triangle elements for buffer
-		if (numelements + (w->numpoints - 2) * 3 > maxelements)
+		if (numelementsbuf + (pnumpoints - 2) * 3 > maxelementsbuf)
 		{
 			Con_Print("Collision_NewBrushFromPlanes: failed to build collision brush: too many triangle elements for buffer\n");
 			return NULL;
 		}
 
-		for (k = 0;k < w->numpoints;k++)
+		for (k = 0;k < pnumpoints;k++)
 		{
 			// check if there is already a matching point (no duplicates)
-			for (m = 0;m < numpoints;m++)
-				if (VectorDistance2(w->points[k], pointsbuf[m].v) < COLLISION_SNAP)
+			for (m = 0;m < numpointsbuf;m++)
+				if (VectorDistance2(&p[w][k*3], pointsbuf[m].v) < COLLISION_SNAP)
 					break;
 
 			// if there is no match, add a new one
-			if (m == numpoints)
+			if (m == numpointsbuf)
 			{
 				// check if there are too many and skip the brush
-				if (numpoints >= 256)
+				if (numpointsbuf >= maxpointsbuf)
 				{
 					Con_Print("Collision_NewBrushFromPlanes: failed to build collision brush: too many points for buffer\n");
-					Winding_Free(w);
 					return NULL;
 				}
 				// add the new one
-				VectorCopy(w->points[k], pointsbuf[numpoints].v);
-				numpoints++;
+				VectorCopy(&p[w][k*3], pointsbuf[numpointsbuf].v);
+				numpointsbuf++;
 			}
 
 			// store the index into a buffer
 			polypointbuf[k] = m;
 		}
-		w = NULL;
-		othertemp = NULL;
-		temp = NULL;
 
 		// add the triangles for the polygon
 		// (this particular code makes a triangle fan)
-		for (k = 0;k < numpolypoints - 2;k++)
+		for (k = 0;k < pnumpoints - 2;k++)
 		{
-			numtriangles++;
-			elementsbuf[numelements++] = polypointbuf[0];
-			elementsbuf[numelements++] = polypointbuf[k + 1];
-			elementsbuf[numelements++] = polypointbuf[k + 2];
+			elementsbuf[numelementsbuf++] = polypointbuf[0];
+			elementsbuf[numelementsbuf++] = polypointbuf[k + 1];
+			elementsbuf[numelementsbuf++] = polypointbuf[k + 2];
 		}
 
 		// add the new plane
-		VectorCopy(originalplanes[j].normal, planesbuf[numplanes].normal);
-		planesbuf[numplanes].dist = originalplanes[j].dist;
-		numplanes++;
+		VectorCopy(originalplanes[j].normal, planesbuf[numplanesbuf].normal);
+		planesbuf[numplanesbuf].dist = originalplanes[j].dist;
+		numplanesbuf++;
+	}
+
+	// validate plane distances
+	for (j = 0;j < numplanesbuf;j++)
+	{
+		float d = furthestplanedist_float(planesbuf[j].normal, pointsbuf, numpointsbuf);
+		if (fabs(planesbuf[j].dist - d) > (1.0f/32.0f))
+			Con_Printf("plane %f %f %f %f mismatches dist %f\n", planesbuf[j].normal[0], planesbuf[j].normal[1], planesbuf[j].normal[2], planesbuf[j].dist, d);
 	}
 
 	// if nothing is left, there's nothing to allocate
-	if (numtriangles < 4 || numplanes < 4 || numpoints < 4)
+	if (numelementsbuf < 12 || numplanesbuf < 4 || numpointsbuf < 4)
+	{
+		Con_Printf("Collision_NewBrushFromPlanes: failed to build collision brush: %i triangles, %i planes (input was %i planes), %i vertices\n", numelementsbuf / 3, numplanesbuf, numoriginalplanes, numpointsbuf);
 		return NULL;
+	}
 
 	// allocate the brush and copy to it
-	brush = Collision_AllocBrushFloat(mempool, numpoints, numplanes, numtriangles, supercontents);
-	memcpy(brush->points, pointsbuf, numpoints * sizeof(colpointf_t));
-	memcpy(brush->planes, planesbuf, numplanes * sizeof(colplanef_t));
-	memcpy(brush->elements, elementsbuf, numtriangles * sizeof(int[3]));
-	// recalc distances
+	brush = Collision_AllocBrushFloat(mempool, numpointsbuf, numplanesbuf, numelementsbuf / 3, supercontents);
+	for (j = 0;j < brush->numpoints;j++)
+	{
+		brush->points[j].v[0] = pointsbuf[j].v[0];
+		brush->points[j].v[1] = pointsbuf[j].v[1];
+		brush->points[j].v[2] = pointsbuf[j].v[2];
+	}
 	for (j = 0;j < brush->numplanes;j++)
-		brush->planes[j].dist = furthestplanedist_float(brush->planes[j].normal, brush->points, brush->numpoints);
+	{
+		brush->planes[j].normal[0] = planesbuf[j].normal[0];
+		brush->planes[j].normal[1] = planesbuf[j].normal[1];
+		brush->planes[j].normal[2] = planesbuf[j].normal[2];
+		brush->planes[j].dist = planesbuf[j].dist;
+	}
+	for (j = 0;j < brush->numtriangles * 3;j++)
+		brush->elements[j] = elementsbuf[j];
 	VectorCopy(brush->points[0].v, brush->mins);
 	VectorCopy(brush->points[0].v, brush->maxs);
 	for (j = 1;j < brush->numpoints;j++)
@@ -571,7 +617,7 @@ colbrushf_t *Collision_AllocBrushFloat(mempool_t *mempool, int numpoints, int nu
 void Collision_CalcPlanesForPolygonBrushFloat(colbrushf_t *brush)
 {
 	int i;
-	float edge0[3], edge1[3], edge2[3], normal[3], dist, bestdist, temp[3];
+	float edge0[3], edge1[3], edge2[3], normal[3], dist, bestdist;
 	colpointf_t *p, *p2;
 
 	if (brush->numpoints == 3)
@@ -641,6 +687,8 @@ void Collision_CalcPlanesForPolygonBrushFloat(colbrushf_t *brush)
 			{
 				// validation code
 #if 0
+				float temp[3];
+
 				VectorSubtract(brush->points[0].v, brush->points[1].v, edge0);
 				VectorSubtract(brush->points[2].v, brush->points[1].v, edge1);
 				CrossProduct(edge0, edge1, normal);
@@ -777,7 +825,7 @@ void Collision_TraceBrushBrushFloat(trace_t *trace, const colbrushf_t *thisbrush
 					return;
 				}
 				f = furthestplanedist_float(startplane->normal, thisbrush_start->points, thisbrush_start->numpoints);
-				if (fabs(f - startplane->dist) > 0.01f)
+				if (fabs(f - startplane->dist) > 0.125f)
 					Con_Printf("startplane->dist %f != calculated %f (thisbrush_start)\n", startplane->dist, f);
 			}
 			d1 = nearestplanedist_float(startplane->normal, thisbrush_start->points, thisbrush_start->numpoints) - furthestplanedist_float(startplane->normal, thatbrush_start->points, thatbrush_start->numpoints) - collision_startnudge.value;
@@ -796,7 +844,7 @@ void Collision_TraceBrushBrushFloat(trace_t *trace, const colbrushf_t *thisbrush
 					return;
 				}
 				f = furthestplanedist_float(startplane->normal, thatbrush_start->points, thatbrush_start->numpoints);
-				if (fabs(f - startplane->dist) > 0.01f)
+				if (fabs(f - startplane->dist) > 0.125f)
 					Con_Printf("startplane->dist %f != calculated %f (thatbrush_start)\n", startplane->dist, f);
 			}
 			d1 = nearestplanedist_float(startplane->normal, thisbrush_start->points, thisbrush_start->numpoints) - startplane->dist - collision_startnudge.value;
@@ -925,7 +973,7 @@ void Collision_TraceLineBrushFloat(trace_t *trace, const vec3_t linestart, const
 			if (thatbrush_start->numpoints)
 			{
 				f = furthestplanedist_float(startplane->normal, thatbrush_start->points, thatbrush_start->numpoints);
-				if (fabs(f - startplane->dist) > 0.01f)
+				if (fabs(f - startplane->dist) > 0.125f)
 					Con_Printf("startplane->dist %f != calculated %f\n", startplane->dist, f);
 			}
 		}