From: havoc Date: Wed, 25 Aug 2004 20:31:17 +0000 (+0000) Subject: changed Collision_NewBrushFromPlanes to use new polygon.c code, this got rid of the... X-Git-Tag: xonotic-v0.1.0preview~5693 X-Git-Url: http://de.git.xonotic.org/?p=xonotic%2Fdarkplaces.git;a=commitdiff_plain;h=2824a71dcb6cb3568f87b9a3dae340c342865669 changed Collision_NewBrushFromPlanes to use new polygon.c code, this got rid of the winding allocations and moved everything onto the stack, a little cleaner (and the new polygon.c code is faster than winding.c) git-svn-id: svn://svn.icculus.org/twilight/trunk/darkplaces@4384 d7cf8633-e32d-0410-b094-e92efae38249 --- diff --git a/collision.c b/collision.c index 35e13d4e..105571f1 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) @@ -402,24 +402,21 @@ 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 numpoints = 0, maxpoints = 256, numplanes = 0, maxplanes = 256, numelements = 0, maxelements = 256, numtriangles = 0; colbrushf_t *brush; colpointf_t pointsbuf[256]; colplanef_t planesbuf[256]; int elementsbuf[1024]; int polypointbuf[256]; + int pmaxpoints = 64; + int pnumpoints; + float p[2][3*64]; // 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) @@ -430,82 +427,73 @@ colbrushf_t *Collision_NewBrushFromPlanes(mempool_t *mempool, int numoriginalpla if (k < numplanes) continue; // check if there are too many and skip the brush - if (numplanes >= 256) + if (numplanes >= maxplanes) { 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; + PolygonF_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; + PolygonF_Divide(pnumpoints, p[w], -originalplanes[k].normal[0], -originalplanes[k].normal[1], -originalplanes[k].normal[2], -originalplanes[k].dist, 1.0/32.0, maxpoints, p[!w], &pnumpoints, 0, NULL, NULL); + w = !w; } } // if nothing is left, skip it - if (!w->numpoints) + if (!pnumpoints) continue; - // copy off the number of points for later when the winding is freed - numpolypoints = w->numpoints; - // 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 (numelements + (pnumpoints - 2) * 3 > maxelements) { 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) + if (VectorDistance2(&p[w][k*3], pointsbuf[m].v) < COLLISION_SNAP) break; // if there is no match, add a new one if (m == numpoints) { // check if there are too many and skip the brush - if (numpoints >= 256) + if (numpoints >= maxpoints) { 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); + VectorCopy(&p[w][k*3], pointsbuf[numpoints].v); numpoints++; } // 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]; diff --git a/collision.h b/collision.h index f13f7223..9b7748b6 100644 --- a/collision.h +++ b/collision.h @@ -91,7 +91,7 @@ colbrushf_t; colbrushf_t *Collision_AllocBrushFloat(mempool_t *mempool, int numpoints, int numplanes, int numtriangles, int supercontents); void Collision_CalcPlanesForPolygonBrushFloat(colbrushf_t *brush); colbrushf_t *Collision_AllocBrushFromPermanentPolygonFloat(mempool_t *mempool, int numpoints, float *points, int supercontents); -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); void Collision_TraceBrushBrushFloat(trace_t *trace, const colbrushf_t *thisbrush_start, const colbrushf_t *thisbrush_end, const colbrushf_t *thatbrush_start, const colbrushf_t *thatbrush_end); void Collision_TraceBrushPolygonFloat(trace_t *trace, const colbrushf_t *thisbrush_start, const colbrushf_t *thisbrush_end, int numpoints, const float *points, int supercontents); void Collision_TraceBrushTriangleMeshFloat(trace_t *trace, const colbrushf_t *thisbrush_start, const colbrushf_t *thisbrush_end, int numtriangles, const int *element3i, const float *vertex3f, int supercontents, const vec3_t segmentmins, const vec3_t segmentmaxs); diff --git a/darkplaces.dev b/darkplaces.dev index 7812e957..68f31b9a 100644 --- a/darkplaces.dev +++ b/darkplaces.dev @@ -1,7 +1,7 @@ [Project] FileName=DARKPL~1.DEV Name=DarkPlaces -UnitCount=158 +UnitCount=162 Type=0 Ver=1 ObjFiles= @@ -1629,6 +1629,26 @@ Priority=1000 OverrideBuildCmd=0 BuildCmd= +[Unit161] +FileName=polygon.c +CompileCpp=0 +Folder=Source Files +Compile=1 +Link=1 +Priority=1000 +OverrideBuildCmd=0 +BuildCmd= + +[Unit162] +FileName=polygon.h +CompileCpp=0 +Folder=Header Files +Compile=1 +Link=1 +Priority=1000 +OverrideBuildCmd=0 +BuildCmd= + [VersionInfo] Major=0 Minor=1 diff --git a/darkplaces.dsp b/darkplaces.dsp index 82125bad..5780d4d2 100644 --- a/darkplaces.dsp +++ b/darkplaces.dsp @@ -284,6 +284,10 @@ SOURCE=.\palette.c # End Source File # Begin Source File +SOURCE=.\polygon.c +# End Source File +# Begin Source File + SOURCE=.\portals.c # End Source File # Begin Source File @@ -596,6 +600,10 @@ SOURCE=.\palette.h # End Source File # Begin Source File +SOURCE=.\polygon.h +# End Source File +# Begin Source File + SOURCE=.\portals.h # End Source File # Begin Source File diff --git a/makefile.inc b/makefile.inc index 5d4a35ba..4b00184a 100644 --- a/makefile.inc +++ b/makefile.inc @@ -70,6 +70,7 @@ OBJ_COMMON= \ model_sprite.o \ netconn.o \ palette.o \ + polygon.o \ portals.o \ pr_cmds.o \ pr_edict.o \ diff --git a/model_brush.c b/model_brush.c index 591e9ef4..c0a7345e 100644 --- a/model_brush.c +++ b/model_brush.c @@ -3831,7 +3831,6 @@ static void Mod_Q3BSP_LoadBrushes(lump_t *l) q3mbrush_t *out; int i, j, n, c, count, maxplanes; mplane_t *planes; - winding_t *temp1, *temp2; in = (void *)(mod_base + l->fileofs); if (l->filelen % sizeof(*in)) @@ -3842,9 +3841,6 @@ static void Mod_Q3BSP_LoadBrushes(lump_t *l) loadmodel->brushq3.data_brushes = out; loadmodel->brushq3.num_brushes = count; - temp1 = Winding_New(64); - temp2 = Winding_New(64); - maxplanes = 0; planes = NULL; @@ -3875,12 +3871,10 @@ static void Mod_Q3BSP_LoadBrushes(lump_t *l) planes[j].dist = out->firstbrushside[j].plane->dist; } // make the colbrush from the planes - out->colbrushf = Collision_NewBrushFromPlanes(loadmodel->mempool, out->numbrushsides, planes, out->texture->supercontents, temp1, temp2); + out->colbrushf = Collision_NewBrushFromPlanes(loadmodel->mempool, out->numbrushsides, planes, out->texture->supercontents); } if (planes) Mem_Free(planes); - Winding_Free(temp1); - Winding_Free(temp2); } static void Mod_Q3BSP_LoadEffects(lump_t *l) diff --git a/polygon.c b/polygon.c new file mode 100644 index 00000000..8133dce3 --- /dev/null +++ b/polygon.c @@ -0,0 +1,220 @@ + +/* +Polygon clipping routines written by Forest Hale and placed into public domain. +*/ + +#include +#include "polygon.h" + +void PolygonF_QuadForPlane(float *outpoints, float planenormalx, float planenormaly, float planenormalz, float planedist, float quadsize) +{ + float d, quadright[3], quadup[3]; + if (planenormalz > planenormalx && planenormalz > planenormaly) + { + quadup[0] = 1; + quadup[1] = 0; + quadup[2] = 0; + } + else + { + quadup[0] = 0; + quadup[1] = 0; + quadup[2] = 1; + } + // d = -DotProduct(quadup, planenormal); + d = -(quadup[0] * planenormalx + quadup[1] * planenormaly + quadup[2] * planenormalz); + // VectorMA(quadup, d, planenormal, quadup); + quadup[0] += d * planenormalx; + quadup[1] += d * planenormalx; + quadup[2] += d * planenormalx; + // VectorNormalize(quadup); + d = 1.0 / sqrt(quadup[0] * quadup[0] + quadup[1] * quadup[1] + quadup[2] * quadup[2]); + quadup[0] *= d; + quadup[1] *= d; + quadup[2] *= d; + // CrossProduct(quadup,planenormal,quadright); + quadright[0] = quadup[1] * planenormalz - quadup[2] * planenormaly; + quadright[1] = quadup[2] * planenormalx - quadup[0] * planenormalz; + quadright[2] = quadup[0] * planenormaly - quadup[1] * planenormalx; + // make the points + outpoints[0] = planedist * planenormalx - quadsize * quadright[0] + quadsize * quadup[0]; + outpoints[1] = planedist * planenormaly - quadsize * quadright[1] + quadsize * quadup[1]; + outpoints[2] = planedist * planenormalz - quadsize * quadright[2] + quadsize * quadup[2]; + outpoints[3] = planedist * planenormalx + quadsize * quadright[0] + quadsize * quadup[0]; + outpoints[4] = planedist * planenormaly + quadsize * quadright[1] + quadsize * quadup[1]; + outpoints[5] = planedist * planenormalz + quadsize * quadright[2] + quadsize * quadup[2]; + outpoints[6] = planedist * planenormalx + quadsize * quadright[0] - quadsize * quadup[0]; + outpoints[7] = planedist * planenormaly + quadsize * quadright[1] - quadsize * quadup[1]; + outpoints[8] = planedist * planenormalz + quadsize * quadright[2] - quadsize * quadup[2]; + outpoints[9] = planedist * planenormalx - quadsize * quadright[0] - quadsize * quadup[0]; + outpoints[10] = planedist * planenormaly - quadsize * quadright[1] - quadsize * quadup[1]; + outpoints[11] = planedist * planenormalz - quadsize * quadright[2] - quadsize * quadup[2]; +} + +void PolygonD_QuadForPlane(double *outpoints, double planenormalx, double planenormaly, double planenormalz, double planedist, double quadsize) +{ + double d, quadright[3], quadup[3]; + if (planenormalz > planenormalx && planenormalz > planenormaly) + { + quadup[0] = 1; + quadup[1] = 0; + quadup[2] = 0; + } + else + { + quadup[0] = 0; + quadup[1] = 0; + quadup[2] = 1; + } + // d = -DotProduct(quadup, planenormal); + d = -(quadup[0] * planenormalx + quadup[1] * planenormaly + quadup[2] * planenormalz); + // VectorMA(quadup, d, planenormal, quadup); + quadup[0] += d * planenormalx; + quadup[1] += d * planenormalx; + quadup[2] += d * planenormalx; + // VectorNormalize(quadup); + d = 1.0 / sqrt(quadup[0] * quadup[0] + quadup[1] * quadup[1] + quadup[2] * quadup[2]); + quadup[0] *= d; + quadup[1] *= d; + quadup[2] *= d; + // CrossProduct(quadup,planenormal,quadright); + quadright[0] = quadup[1] * planenormalz - quadup[2] * planenormaly; + quadright[1] = quadup[2] * planenormalx - quadup[0] * planenormalz; + quadright[2] = quadup[0] * planenormaly - quadup[1] * planenormalx; + // make the points + outpoints[0] = planedist * planenormalx - quadsize * quadright[0] + quadsize * quadup[0]; + outpoints[1] = planedist * planenormaly - quadsize * quadright[1] + quadsize * quadup[1]; + outpoints[2] = planedist * planenormalz - quadsize * quadright[2] + quadsize * quadup[2]; + outpoints[3] = planedist * planenormalx + quadsize * quadright[0] + quadsize * quadup[0]; + outpoints[4] = planedist * planenormaly + quadsize * quadright[1] + quadsize * quadup[1]; + outpoints[5] = planedist * planenormalz + quadsize * quadright[2] + quadsize * quadup[2]; + outpoints[6] = planedist * planenormalx + quadsize * quadright[0] - quadsize * quadup[0]; + outpoints[7] = planedist * planenormaly + quadsize * quadright[1] - quadsize * quadup[1]; + outpoints[8] = planedist * planenormalz + quadsize * quadright[2] - quadsize * quadup[2]; + outpoints[9] = planedist * planenormalx - quadsize * quadright[0] - quadsize * quadup[0]; + outpoints[10] = planedist * planenormaly - quadsize * quadright[1] - quadsize * quadup[1]; + outpoints[11] = planedist * planenormalz - quadsize * quadright[2] - quadsize * quadup[2]; +} + +void PolygonF_Divide(unsigned int innumpoints, const float *inpoints, float planenormalx, float planenormaly, float planenormalz, float planedist, float epsilon, unsigned int outfrontmaxpoints, float *outfrontpoints, unsigned int *neededfrontpoints, unsigned int outbackmaxpoints, float *outbackpoints, unsigned int *neededbackpoints) +{ + unsigned int i, frontcount, backcount; + const float *n, *p; + float frac, pdist, ndist; + frontcount = 0; + backcount = 0; + p = inpoints + (innumpoints - 1) * 3; + n = inpoints; + pdist = p[0] * planenormalx + p[1] * planenormaly + p[2] * planenormalz - planedist; + for (i = 0;i < innumpoints;i++) + { + ndist = n[0] * planenormalx + n[1] * planenormaly + n[2] * planenormalz - planedist; + if (pdist >= -epsilon) + { + if (frontcount < outfrontmaxpoints) + { + *outfrontpoints++ = p[0]; + *outfrontpoints++ = p[1]; + *outfrontpoints++ = p[2]; + } + frontcount++; + } + if (pdist <= epsilon) + { + if (backcount < outbackmaxpoints) + { + *outbackpoints++ = p[0]; + *outbackpoints++ = p[1]; + *outbackpoints++ = p[2]; + } + backcount++; + } + if ((pdist > epsilon && ndist < -epsilon) || (pdist < -epsilon && ndist > epsilon)) + { + frac = pdist / (pdist - ndist); + if (frontcount < outfrontmaxpoints) + { + *outfrontpoints++ = p[0] + frac * (n[0] - p[0]); + *outfrontpoints++ = p[1] + frac * (n[1] - p[1]); + *outfrontpoints++ = p[2] + frac * (n[2] - p[2]); + } + frontcount++; + if (backcount < outbackmaxpoints) + { + *outbackpoints++ = p[0] + frac * (n[0] - p[0]); + *outbackpoints++ = p[1] + frac * (n[1] - p[1]); + *outbackpoints++ = p[2] + frac * (n[2] - p[2]); + } + backcount++; + } + p = n; + n += 3; + pdist = ndist; + } + if (neededfrontpoints) + *neededfrontpoints = frontcount; + if (neededbackpoints) + *neededbackpoints = backcount; +} + +void PolygonD_Divide(unsigned int innumpoints, const double *inpoints, double planenormalx, double planenormaly, double planenormalz, double planedist, double epsilon, unsigned int outfrontmaxpoints, double *outfrontpoints, unsigned int *neededfrontpoints, unsigned int outbackmaxpoints, double *outbackpoints, unsigned int *neededbackpoints) +{ + unsigned int i, frontcount, backcount; + const double *n, *p; + double frac, pdist, ndist; + frontcount = 0; + backcount = 0; + p = inpoints + (innumpoints - 1) * 3; + n = inpoints; + pdist = p[0] * planenormalx + p[1] * planenormaly + p[2] * planenormalz - planedist; + for (i = 0;i < innumpoints;i++) + { + ndist = n[0] * planenormalx + n[1] * planenormaly + n[2] * planenormalz - planedist; + if (pdist >= -epsilon) + { + if (frontcount < outfrontmaxpoints) + { + *outfrontpoints++ = p[0]; + *outfrontpoints++ = p[1]; + *outfrontpoints++ = p[2]; + } + frontcount++; + } + if (pdist <= epsilon) + { + if (backcount < outbackmaxpoints) + { + *outbackpoints++ = p[0]; + *outbackpoints++ = p[1]; + *outbackpoints++ = p[2]; + } + backcount++; + } + if ((pdist > epsilon && ndist < -epsilon) || (pdist < -epsilon && ndist > epsilon)) + { + frac = pdist / (pdist - ndist); + if (frontcount < outfrontmaxpoints) + { + *outfrontpoints++ = p[0] + frac * (n[0] - p[0]); + *outfrontpoints++ = p[1] + frac * (n[1] - p[1]); + *outfrontpoints++ = p[2] + frac * (n[2] - p[2]); + } + frontcount++; + if (backcount < outbackmaxpoints) + { + *outbackpoints++ = p[0] + frac * (n[0] - p[0]); + *outbackpoints++ = p[1] + frac * (n[1] - p[1]); + *outbackpoints++ = p[2] + frac * (n[2] - p[2]); + } + backcount++; + } + p = n; + n += 3; + pdist = ndist; + } + if (neededfrontpoints) + *neededfrontpoints = frontcount; + if (neededbackpoints) + *neededbackpoints = backcount; +} + diff --git a/polygon.h b/polygon.h new file mode 100644 index 00000000..d4a21064 --- /dev/null +++ b/polygon.h @@ -0,0 +1,14 @@ + +#ifndef POLYGON_H +#define POLYGON_H + +/* +Polygon clipping routines written by Forest Hale and placed into public domain. +*/ + +void PolygonF_QuadForPlane(float *outpoints, float planenormalx, float planenormaly, float planenormalz, float planedist, float quadsize); +void PolygonD_QuadForPlane(double *outpoints, double planenormalx, double planenormaly, double planenormalz, double planedist, double quadsize); +void PolygonF_Divide(unsigned int innumpoints, const float *inpoints, float planenormalx, float planenormaly, float planenormalz, float planedist, float epsilon, unsigned int outfrontmaxpoints, float *outfrontpoints, unsigned int *neededfrontpoints, unsigned int outbackmaxpoints, float *outbackpoints, unsigned int *neededbackpoints); +void PolygonD_Divide(unsigned int innumpoints, const double *inpoints, double planenormalx, double planenormaly, double planenormalz, double planedist, double epsilon, unsigned int outfrontmaxpoints, double *outfrontpoints, unsigned int *neededfrontpoints, unsigned int outbackmaxpoints, double *outbackpoints, unsigned int *neededbackpoints); + +#endif