#include "quakedef.h"
-#include "winding.h"
+#include "polygon.h"
#define COLLISION_SNAPSCALE (32.0f)
#define COLLISION_SNAP (1.0f / COLLISION_SNAPSCALE)
}
-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)
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];
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);
[Project]
FileName=DARKPL~1.DEV
Name=DarkPlaces
-UnitCount=158
+UnitCount=162
Type=0
Ver=1
ObjFiles=
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
# 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
# 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
model_sprite.o \
netconn.o \
palette.o \
+ polygon.o \
portals.o \
pr_cmds.o \
pr_edict.o \
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))
loadmodel->brushq3.data_brushes = out;
loadmodel->brushq3.num_brushes = count;
- temp1 = Winding_New(64);
- temp2 = Winding_New(64);
-
maxplanes = 0;
planes = NULL;
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)
--- /dev/null
+
+/*
+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;
+}
+
--- /dev/null
+
+#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
projects / xonotic / darkplaces.git / commitdiff