changed Collision_NewBrushFromPlanes to use new polygon.c code, this got rid of the...
authorhavoc <havoc@d7cf8633-e32d-0410-b094-e92efae38249>
Wed, 25 Aug 2004 20:31:17 +0000 (20:31 +0000)
committerhavoc <havoc@d7cf8633-e32d-0410-b094-e92efae38249>
Wed, 25 Aug 2004 20:31:17 +0000 (20:31 +0000)
git-svn-id: svn://svn.icculus.org/twilight/trunk/darkplaces@4384 d7cf8633-e32d-0410-b094-e92efae38249

collision.c
collision.h
darkplaces.dev
darkplaces.dsp
makefile.inc
model_brush.c
polygon.c [new file with mode: 0644]
polygon.h [new file with mode: 0644]

index 35e13d4..105571f 100644 (file)
@@ -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];
index f13f722..9b7748b 100644 (file)
@@ -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);
index 7812e95..68f31b9 100644 (file)
@@ -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
index 82125ba..5780d4d 100644 (file)
@@ -284,6 +284,10 @@ SOURCE=.\palette.c
 # End Source File\r
 # Begin Source File\r
 \r
+SOURCE=.\polygon.c\r
+# End Source File\r
+# Begin Source File\r
+\r
 SOURCE=.\portals.c\r
 # End Source File\r
 # Begin Source File\r
@@ -596,6 +600,10 @@ SOURCE=.\palette.h
 # End Source File\r
 # Begin Source File\r
 \r
+SOURCE=.\polygon.h\r
+# End Source File\r
+# Begin Source File\r
+\r
 SOURCE=.\portals.h\r
 # End Source File\r
 # Begin Source File\r
index 5d4a35b..4b00184 100644 (file)
@@ -70,6 +70,7 @@ OBJ_COMMON= \
        model_sprite.o \
        netconn.o \
        palette.o \
+       polygon.o \
        portals.o \
        pr_cmds.o \
        pr_edict.o \
index 591e9ef..c0a7345 100644 (file)
@@ -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 (file)
index 0000000..8133dce
--- /dev/null
+++ b/polygon.c
@@ -0,0 +1,220 @@
+
+/*
+Polygon clipping routines written by Forest Hale and placed into public domain.
+*/
+
+#include <math.h>
+#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 (file)
index 0000000..d4a2106
--- /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