-/*\r
-Copyright (C) 1999-2007 id Software, Inc. and contributors.\r
-For a list of contributors, see the accompanying CONTRIBUTORS file.\r
-\r
-This file is part of GtkRadiant.\r
-\r
-GtkRadiant is free software; you can redistribute it and/or modify\r
-it under the terms of the GNU General Public License as published by\r
-the Free Software Foundation; either version 2 of the License, or\r
-(at your option) any later version.\r
-\r
-GtkRadiant is distributed in the hope that it will be useful,\r
-but WITHOUT ANY WARRANTY; without even the implied warranty of\r
-MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the\r
-GNU General Public License for more details.\r
-\r
-You should have received a copy of the GNU General Public License\r
-along with GtkRadiant; if not, write to the Free Software\r
-Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA\r
-*/\r
-\r
-#include "cmdlib.h"\r
-#include "inout.h"\r
-#include "mathlib.h"\r
-#include "polylib.h"\r
-\r
-\r
-extern int numthreads;\r
-\r
-// counters are only bumped when running single threaded,\r
-// because they are an awefull coherence problem\r
-int c_active_windings;\r
-int c_peak_windings;\r
-int c_winding_allocs;\r
-int c_winding_points;\r
-\r
-#define BOGUS_RANGE 8192\r
-\r
-void pw(winding_t *w)\r
-{\r
- int i;\r
- for (i=0 ; i<w->numpoints ; i++)\r
- printf ("(%5.1f, %5.1f, %5.1f)\n",w->p[i][0], w->p[i][1],w->p[i][2]);\r
-}\r
-\r
-\r
-/*\r
-=============\r
-AllocWinding\r
-=============\r
-*/\r
-winding_t *AllocWinding (int points)\r
-{\r
- winding_t *w;\r
- int s;\r
-\r
- if (numthreads == 1)\r
- {\r
- c_winding_allocs++;\r
- c_winding_points += points;\r
- c_active_windings++;\r
- if (c_active_windings > c_peak_windings)\r
- c_peak_windings = c_active_windings;\r
- }\r
- s = sizeof(vec_t)*3*points + sizeof(int);\r
- w = malloc (s);\r
- memset (w, 0, s); \r
- return w;\r
-}\r
-\r
-void FreeWinding (winding_t *w)\r
-{\r
- if (*(unsigned *)w == 0xdeaddead)\r
- Error ("FreeWinding: freed a freed winding");\r
- *(unsigned *)w = 0xdeaddead;\r
-\r
- if (numthreads == 1)\r
- c_active_windings--;\r
- free (w);\r
-}\r
-\r
-/*\r
-============\r
-RemoveColinearPoints\r
-============\r
-*/\r
-int c_removed;\r
-\r
-void RemoveColinearPoints (winding_t *w)\r
-{\r
- int i, j, k;\r
- vec3_t v1, v2;\r
- int nump;\r
- vec3_t p[MAX_POINTS_ON_WINDING];\r
-\r
- nump = 0;\r
- for (i=0 ; i<w->numpoints ; i++)\r
- {\r
- j = (i+1)%w->numpoints;\r
- k = (i+w->numpoints-1)%w->numpoints;\r
- VectorSubtract (w->p[j], w->p[i], v1);\r
- VectorSubtract (w->p[i], w->p[k], v2);\r
- VectorNormalize(v1,v1);\r
- VectorNormalize(v2,v2);\r
- if (DotProduct(v1, v2) < 0.999)\r
- {\r
- VectorCopy (w->p[i], p[nump]);\r
- nump++;\r
- }\r
- }\r
-\r
- if (nump == w->numpoints)\r
- return;\r
-\r
- if (numthreads == 1)\r
- c_removed += w->numpoints - nump;\r
- w->numpoints = nump;\r
- memcpy (w->p, p, nump*sizeof(p[0]));\r
-}\r
-\r
-/*\r
-============\r
-WindingPlane\r
-============\r
-*/\r
-void WindingPlane (winding_t *w, vec3_t normal, vec_t *dist)\r
-{\r
- vec3_t v1, v2;\r
-\r
- VectorSubtract (w->p[1], w->p[0], v1);\r
- VectorSubtract (w->p[2], w->p[0], v2);\r
- CrossProduct (v2, v1, normal);\r
- VectorNormalize (normal, normal);\r
- *dist = DotProduct (w->p[0], normal);\r
-\r
-}\r
-\r
-/*\r
-=============\r
-WindingArea\r
-=============\r
-*/\r
-vec_t WindingArea (winding_t *w)\r
-{\r
- int i;\r
- vec3_t d1, d2, cross;\r
- vec_t total;\r
-\r
- total = 0;\r
- for (i=2 ; i<w->numpoints ; i++)\r
- {\r
- VectorSubtract (w->p[i-1], w->p[0], d1);\r
- VectorSubtract (w->p[i], w->p[0], d2);\r
- CrossProduct (d1, d2, cross);\r
- total += 0.5 * VectorLength ( cross );\r
- }\r
- return total;\r
-}\r
-\r
-void WindingBounds (winding_t *w, vec3_t mins, vec3_t maxs)\r
-{\r
- vec_t v;\r
- int i,j;\r
-\r
- mins[0] = mins[1] = mins[2] = 99999;\r
- maxs[0] = maxs[1] = maxs[2] = -99999;\r
-\r
- for (i=0 ; i<w->numpoints ; i++)\r
- {\r
- for (j=0 ; j<3 ; j++)\r
- {\r
- v = w->p[i][j];\r
- if (v < mins[j])\r
- mins[j] = v;\r
- if (v > maxs[j])\r
- maxs[j] = v;\r
- }\r
- }\r
-}\r
-\r
-/*\r
-=============\r
-WindingCenter\r
-=============\r
-*/\r
-void WindingCenter (winding_t *w, vec3_t center)\r
-{\r
- int i;\r
- float scale;\r
-\r
- VectorCopy (vec3_origin, center);\r
- for (i=0 ; i<w->numpoints ; i++)\r
- VectorAdd (w->p[i], center, center);\r
-\r
- scale = 1.0/w->numpoints;\r
- VectorScale (center, scale, center);\r
-}\r
-\r
-/*\r
-=================\r
-BaseWindingForPlane\r
-=================\r
-*/\r
-winding_t *BaseWindingForPlane (vec3_t normal, vec_t dist)\r
-{\r
- int i, x;\r
- vec_t max, v;\r
- vec3_t org, vright, vup;\r
- winding_t *w;\r
- \r
-// find the major axis\r
-\r
- max = -BOGUS_RANGE;\r
- x = -1;\r
- for (i=0 ; i<3; i++)\r
- {\r
- v = fabs(normal[i]);\r
- if (v > max)\r
- {\r
- x = i;\r
- max = v;\r
- }\r
- }\r
- if (x==-1)\r
- Error ("BaseWindingForPlane: no axis found");\r
- \r
- VectorCopy (vec3_origin, vup); \r
- switch (x)\r
- {\r
- case 0:\r
- case 1:\r
- vup[2] = 1;\r
- break; \r
- case 2:\r
- vup[0] = 1;\r
- break; \r
- }\r
-\r
- v = DotProduct (vup, normal);\r
- VectorMA (vup, -v, normal, vup);\r
- VectorNormalize (vup, vup);\r
- \r
- VectorScale (normal, dist, org);\r
- \r
- CrossProduct (vup, normal, vright);\r
- \r
- VectorScale (vup, 8192, vup);\r
- VectorScale (vright, 8192, vright);\r
-\r
-// project a really big axis aligned box onto the plane\r
- w = AllocWinding (4);\r
- \r
- VectorSubtract (org, vright, w->p[0]);\r
- VectorAdd (w->p[0], vup, w->p[0]);\r
- \r
- VectorAdd (org, vright, w->p[1]);\r
- VectorAdd (w->p[1], vup, w->p[1]);\r
- \r
- VectorAdd (org, vright, w->p[2]);\r
- VectorSubtract (w->p[2], vup, w->p[2]);\r
- \r
- VectorSubtract (org, vright, w->p[3]);\r
- VectorSubtract (w->p[3], vup, w->p[3]);\r
- \r
- w->numpoints = 4;\r
- \r
- return w; \r
-}\r
-\r
-/*\r
-==================\r
-CopyWinding\r
-==================\r
-*/\r
-winding_t *CopyWinding (winding_t *w)\r
-{\r
- int size;\r
- winding_t *c;\r
-\r
- c = AllocWinding (w->numpoints);\r
- size = (int)((winding_t *)0)->p[w->numpoints];\r
- memcpy (c, w, size);\r
- return c;\r
-}\r
-\r
-/*\r
-==================\r
-ReverseWinding\r
-==================\r
-*/\r
-winding_t *ReverseWinding (winding_t *w)\r
-{\r
- int i;\r
- winding_t *c;\r
-\r
- c = AllocWinding (w->numpoints);\r
- for (i=0 ; i<w->numpoints ; i++)\r
- {\r
- VectorCopy (w->p[w->numpoints-1-i], c->p[i]);\r
- }\r
- c->numpoints = w->numpoints;\r
- return c;\r
-}\r
-\r
-\r
-/*\r
-=============\r
-ClipWindingEpsilon\r
-=============\r
-*/\r
-void ClipWindingEpsilon (winding_t *in, vec3_t normal, vec_t dist, \r
- vec_t epsilon, winding_t **front, winding_t **back)\r
-{\r
- vec_t dists[MAX_POINTS_ON_WINDING+4];\r
- int sides[MAX_POINTS_ON_WINDING+4];\r
- int counts[3];\r
- static vec_t dot; // VC 4.2 optimizer bug if not static\r
- int i, j;\r
- vec_t *p1, *p2;\r
- vec3_t mid;\r
- winding_t *f, *b;\r
- int maxpts;\r
- \r
- counts[0] = counts[1] = counts[2] = 0;\r
-\r
-// determine sides for each point\r
- for (i=0 ; i<in->numpoints ; i++)\r
- {\r
- dot = DotProduct (in->p[i], normal);\r
- dot -= dist;\r
- dists[i] = dot;\r
- if (dot > epsilon)\r
- sides[i] = SIDE_FRONT;\r
- else if (dot < -epsilon)\r
- sides[i] = SIDE_BACK;\r
- else\r
- {\r
- sides[i] = SIDE_ON;\r
- }\r
- counts[sides[i]]++;\r
- }\r
- sides[i] = sides[0];\r
- dists[i] = dists[0];\r
- \r
- *front = *back = NULL;\r
-\r
- if (!counts[0])\r
- {\r
- *back = CopyWinding (in);\r
- return;\r
- }\r
- if (!counts[1])\r
- {\r
- *front = CopyWinding (in);\r
- return;\r
- }\r
-\r
- maxpts = in->numpoints+4; // cant use counts[0]+2 because\r
- // of fp grouping errors\r
-\r
- *front = f = AllocWinding (maxpts);\r
- *back = b = AllocWinding (maxpts);\r
- \r
- for (i=0 ; i<in->numpoints ; i++)\r
- {\r
- p1 = in->p[i];\r
- \r
- if (sides[i] == SIDE_ON)\r
- {\r
- VectorCopy (p1, f->p[f->numpoints]);\r
- f->numpoints++;\r
- VectorCopy (p1, b->p[b->numpoints]);\r
- b->numpoints++;\r
- continue;\r
- }\r
- \r
- if (sides[i] == SIDE_FRONT)\r
- {\r
- VectorCopy (p1, f->p[f->numpoints]);\r
- f->numpoints++;\r
- }\r
- if (sides[i] == SIDE_BACK)\r
- {\r
- VectorCopy (p1, b->p[b->numpoints]);\r
- b->numpoints++;\r
- }\r
-\r
- if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])\r
- continue;\r
- \r
- // generate a split point\r
- p2 = in->p[(i+1)%in->numpoints];\r
- \r
- dot = dists[i] / (dists[i]-dists[i+1]);\r
- for (j=0 ; j<3 ; j++)\r
- { // avoid round off error when possible\r
- if (normal[j] == 1)\r
- mid[j] = dist;\r
- else if (normal[j] == -1)\r
- mid[j] = -dist;\r
- else\r
- mid[j] = p1[j] + dot*(p2[j]-p1[j]);\r
- }\r
- \r
- VectorCopy (mid, f->p[f->numpoints]);\r
- f->numpoints++;\r
- VectorCopy (mid, b->p[b->numpoints]);\r
- b->numpoints++;\r
- }\r
- \r
- if (f->numpoints > maxpts || b->numpoints > maxpts)\r
- Error ("ClipWinding: points exceeded estimate");\r
- if (f->numpoints > MAX_POINTS_ON_WINDING || b->numpoints > MAX_POINTS_ON_WINDING)\r
- Error ("ClipWinding: MAX_POINTS_ON_WINDING");\r
-}\r
-\r
-\r
-/*\r
-=============\r
-ChopWindingInPlace\r
-=============\r
-*/\r
-void ChopWindingInPlace (winding_t **inout, vec3_t normal, vec_t dist, vec_t epsilon)\r
-{\r
- winding_t *in;\r
- vec_t dists[MAX_POINTS_ON_WINDING+4];\r
- int sides[MAX_POINTS_ON_WINDING+4];\r
- int counts[3];\r
- static vec_t dot; // VC 4.2 optimizer bug if not static\r
- int i, j;\r
- vec_t *p1, *p2;\r
- vec3_t mid;\r
- winding_t *f;\r
- int maxpts;\r
-\r
- in = *inout;\r
- counts[0] = counts[1] = counts[2] = 0;\r
-\r
-// determine sides for each point\r
- for (i=0 ; i<in->numpoints ; i++)\r
- {\r
- dot = DotProduct (in->p[i], normal);\r
- dot -= dist;\r
- dists[i] = dot;\r
- if (dot > epsilon)\r
- sides[i] = SIDE_FRONT;\r
- else if (dot < -epsilon)\r
- sides[i] = SIDE_BACK;\r
- else\r
- {\r
- sides[i] = SIDE_ON;\r
- }\r
- counts[sides[i]]++;\r
- }\r
- sides[i] = sides[0];\r
- dists[i] = dists[0];\r
- \r
- if (!counts[0])\r
- {\r
- FreeWinding (in);\r
- *inout = NULL;\r
- return;\r
- }\r
- if (!counts[1])\r
- return; // inout stays the same\r
-\r
- maxpts = in->numpoints+4; // cant use counts[0]+2 because\r
- // of fp grouping errors\r
-\r
- f = AllocWinding (maxpts);\r
- \r
- for (i=0 ; i<in->numpoints ; i++)\r
- {\r
- p1 = in->p[i];\r
- \r
- if (sides[i] == SIDE_ON)\r
- {\r
- VectorCopy (p1, f->p[f->numpoints]);\r
- f->numpoints++;\r
- continue;\r
- }\r
- \r
- if (sides[i] == SIDE_FRONT)\r
- {\r
- VectorCopy (p1, f->p[f->numpoints]);\r
- f->numpoints++;\r
- }\r
-\r
- if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])\r
- continue;\r
- \r
- // generate a split point\r
- p2 = in->p[(i+1)%in->numpoints];\r
- \r
- dot = dists[i] / (dists[i]-dists[i+1]);\r
- for (j=0 ; j<3 ; j++)\r
- { // avoid round off error when possible\r
- if (normal[j] == 1)\r
- mid[j] = dist;\r
- else if (normal[j] == -1)\r
- mid[j] = -dist;\r
- else\r
- mid[j] = p1[j] + dot*(p2[j]-p1[j]);\r
- }\r
- \r
- VectorCopy (mid, f->p[f->numpoints]);\r
- f->numpoints++;\r
- }\r
- \r
- if (f->numpoints > maxpts)\r
- Error ("ClipWinding: points exceeded estimate");\r
- if (f->numpoints > MAX_POINTS_ON_WINDING)\r
- Error ("ClipWinding: MAX_POINTS_ON_WINDING");\r
-\r
- FreeWinding (in);\r
- *inout = f;\r
-}\r
-\r
-\r
-/*\r
-=================\r
-ChopWinding\r
-\r
-Returns the fragment of in that is on the front side\r
-of the cliping plane. The original is freed.\r
-=================\r
-*/\r
-winding_t *ChopWinding (winding_t *in, vec3_t normal, vec_t dist)\r
-{\r
- winding_t *f, *b;\r
-\r
- ClipWindingEpsilon (in, normal, dist, ON_EPSILON, &f, &b);\r
- FreeWinding (in);\r
- if (b)\r
- FreeWinding (b);\r
- return f;\r
-}\r
-\r
-\r
-/*\r
-=================\r
-CheckWinding\r
-\r
-=================\r
-*/\r
-void CheckWinding (winding_t *w)\r
-{\r
- int i, j;\r
- vec_t *p1, *p2;\r
- vec_t d, edgedist;\r
- vec3_t dir, edgenormal, facenormal;\r
- vec_t area;\r
- vec_t facedist;\r
-\r
- if (w->numpoints < 3)\r
- Error ("CheckWinding: %i points",w->numpoints);\r
- \r
- area = WindingArea(w);\r
- if (area < 1)\r
- Error ("CheckWinding: %f area", area);\r
-\r
- WindingPlane (w, facenormal, &facedist);\r
- \r
- for (i=0 ; i<w->numpoints ; i++)\r
- {\r
- p1 = w->p[i];\r
-\r
- for (j=0 ; j<3 ; j++)\r
- if (p1[j] > BOGUS_RANGE || p1[j] < -BOGUS_RANGE)\r
- Error ("CheckFace: BUGUS_RANGE: %f",p1[j]);\r
-\r
- j = i+1 == w->numpoints ? 0 : i+1;\r
- \r
- // check the point is on the face plane\r
- d = DotProduct (p1, facenormal) - facedist;\r
- if (d < -ON_EPSILON || d > ON_EPSILON)\r
- Error ("CheckWinding: point off plane");\r
- \r
- // check the edge isnt degenerate\r
- p2 = w->p[j];\r
- VectorSubtract (p2, p1, dir);\r
- \r
- if (VectorLength (dir) < ON_EPSILON)\r
- Error ("CheckWinding: degenerate edge");\r
- \r
- CrossProduct (facenormal, dir, edgenormal);\r
- VectorNormalize (edgenormal, edgenormal);\r
- edgedist = DotProduct (p1, edgenormal);\r
- edgedist += ON_EPSILON;\r
- \r
- // all other points must be on front side\r
- for (j=0 ; j<w->numpoints ; j++)\r
- {\r
- if (j == i)\r
- continue;\r
- d = DotProduct (w->p[j], edgenormal);\r
- if (d > edgedist)\r
- Error ("CheckWinding: non-convex");\r
- }\r
- }\r
-}\r
-\r
-\r
-/*\r
-============\r
-WindingOnPlaneSide\r
-============\r
-*/\r
-int WindingOnPlaneSide (winding_t *w, vec3_t normal, vec_t dist)\r
-{\r
- qboolean front, back;\r
- int i;\r
- vec_t d;\r
-\r
- front = false;\r
- back = false;\r
- for (i=0 ; i<w->numpoints ; i++)\r
- {\r
- d = DotProduct (w->p[i], normal) - dist;\r
- if (d < -ON_EPSILON)\r
- {\r
- if (front)\r
- return SIDE_CROSS;\r
- back = true;\r
- continue;\r
- }\r
- if (d > ON_EPSILON)\r
- {\r
- if (back)\r
- return SIDE_CROSS;\r
- front = true;\r
- continue;\r
- }\r
- }\r
-\r
- if (back)\r
- return SIDE_BACK;\r
- if (front)\r
- return SIDE_FRONT;\r
- return SIDE_ON;\r
-}\r
-\r
+/*
+Copyright (C) 1999-2007 id Software, Inc. and contributors.
+For a list of contributors, see the accompanying CONTRIBUTORS file.
+
+This file is part of GtkRadiant.
+
+GtkRadiant is free software; you can redistribute it and/or modify
+it under the terms of the GNU General Public License as published by
+the Free Software Foundation; either version 2 of the License, or
+(at your option) any later version.
+
+GtkRadiant is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+GNU General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with GtkRadiant; if not, write to the Free Software
+Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
+*/
+
+#include "cmdlib.h"
+#include "inout.h"
+#include "mathlib.h"
+#include "polylib.h"
+
+
+extern int numthreads;
+
+// counters are only bumped when running single threaded,
+// because they are an awefull coherence problem
+int c_active_windings;
+int c_peak_windings;
+int c_winding_allocs;
+int c_winding_points;
+
+#define BOGUS_RANGE 8192
+
+void pw(winding_t *w)
+{
+ int i;
+ for (i=0 ; i<w->numpoints ; i++)
+ printf ("(%5.1f, %5.1f, %5.1f)\n",w->p[i][0], w->p[i][1],w->p[i][2]);
+}
+
+
+/*
+=============
+AllocWinding
+=============
+*/
+winding_t *AllocWinding (int points)
+{
+ winding_t *w;
+ int s;
+
+ if (numthreads == 1)
+ {
+ c_winding_allocs++;
+ c_winding_points += points;
+ c_active_windings++;
+ if (c_active_windings > c_peak_windings)
+ c_peak_windings = c_active_windings;
+ }
+ s = sizeof(vec_t)*3*points + sizeof(int);
+ w = malloc (s);
+ memset (w, 0, s);
+ return w;
+}
+
+void FreeWinding (winding_t *w)
+{
+ if (*(unsigned *)w == 0xdeaddead)
+ Error ("FreeWinding: freed a freed winding");
+ *(unsigned *)w = 0xdeaddead;
+
+ if (numthreads == 1)
+ c_active_windings--;
+ free (w);
+}
+
+/*
+============
+RemoveColinearPoints
+============
+*/
+int c_removed;
+
+void RemoveColinearPoints (winding_t *w)
+{
+ int i, j, k;
+ vec3_t v1, v2;
+ int nump;
+ vec3_t p[MAX_POINTS_ON_WINDING];
+
+ nump = 0;
+ for (i=0 ; i<w->numpoints ; i++)
+ {
+ j = (i+1)%w->numpoints;
+ k = (i+w->numpoints-1)%w->numpoints;
+ VectorSubtract (w->p[j], w->p[i], v1);
+ VectorSubtract (w->p[i], w->p[k], v2);
+ VectorNormalize(v1,v1);
+ VectorNormalize(v2,v2);
+ if (DotProduct(v1, v2) < 0.999)
+ {
+ VectorCopy (w->p[i], p[nump]);
+ nump++;
+ }
+ }
+
+ if (nump == w->numpoints)
+ return;
+
+ if (numthreads == 1)
+ c_removed += w->numpoints - nump;
+ w->numpoints = nump;
+ memcpy (w->p, p, nump*sizeof(p[0]));
+}
+
+/*
+============
+WindingPlane
+============
+*/
+void WindingPlane (winding_t *w, vec3_t normal, vec_t *dist)
+{
+ vec3_t v1, v2;
+
+ VectorSubtract (w->p[1], w->p[0], v1);
+ VectorSubtract (w->p[2], w->p[0], v2);
+ CrossProduct (v2, v1, normal);
+ VectorNormalize (normal, normal);
+ *dist = DotProduct (w->p[0], normal);
+
+}
+
+/*
+=============
+WindingArea
+=============
+*/
+vec_t WindingArea (winding_t *w)
+{
+ int i;
+ vec3_t d1, d2, cross;
+ vec_t total;
+
+ total = 0;
+ for (i=2 ; i<w->numpoints ; i++)
+ {
+ VectorSubtract (w->p[i-1], w->p[0], d1);
+ VectorSubtract (w->p[i], w->p[0], d2);
+ CrossProduct (d1, d2, cross);
+ total += 0.5 * VectorLength ( cross );
+ }
+ return total;
+}
+
+void WindingBounds (winding_t *w, vec3_t mins, vec3_t maxs)
+{
+ vec_t v;
+ int i,j;
+
+ mins[0] = mins[1] = mins[2] = 99999;
+ maxs[0] = maxs[1] = maxs[2] = -99999;
+
+ for (i=0 ; i<w->numpoints ; i++)
+ {
+ for (j=0 ; j<3 ; j++)
+ {
+ v = w->p[i][j];
+ if (v < mins[j])
+ mins[j] = v;
+ if (v > maxs[j])
+ maxs[j] = v;
+ }
+ }
+}
+
+/*
+=============
+WindingCenter
+=============
+*/
+void WindingCenter (winding_t *w, vec3_t center)
+{
+ int i;
+ float scale;
+
+ VectorCopy (vec3_origin, center);
+ for (i=0 ; i<w->numpoints ; i++)
+ VectorAdd (w->p[i], center, center);
+
+ scale = 1.0/w->numpoints;
+ VectorScale (center, scale, center);
+}
+
+/*
+=================
+BaseWindingForPlane
+=================
+*/
+winding_t *BaseWindingForPlane (vec3_t normal, vec_t dist)
+{
+ int i, x;
+ vec_t max, v;
+ vec3_t org, vright, vup;
+ winding_t *w;
+
+// find the major axis
+
+ max = -BOGUS_RANGE;
+ x = -1;
+ for (i=0 ; i<3; i++)
+ {
+ v = fabs(normal[i]);
+ if (v > max)
+ {
+ x = i;
+ max = v;
+ }
+ }
+ if (x==-1)
+ Error ("BaseWindingForPlane: no axis found");
+
+ VectorCopy (vec3_origin, vup);
+ switch (x)
+ {
+ case 0:
+ case 1:
+ vup[2] = 1;
+ break;
+ case 2:
+ vup[0] = 1;
+ break;
+ }
+
+ v = DotProduct (vup, normal);
+ VectorMA (vup, -v, normal, vup);
+ VectorNormalize (vup, vup);
+
+ VectorScale (normal, dist, org);
+
+ CrossProduct (vup, normal, vright);
+
+ VectorScale (vup, 8192, vup);
+ VectorScale (vright, 8192, vright);
+
+// project a really big axis aligned box onto the plane
+ w = AllocWinding (4);
+
+ VectorSubtract (org, vright, w->p[0]);
+ VectorAdd (w->p[0], vup, w->p[0]);
+
+ VectorAdd (org, vright, w->p[1]);
+ VectorAdd (w->p[1], vup, w->p[1]);
+
+ VectorAdd (org, vright, w->p[2]);
+ VectorSubtract (w->p[2], vup, w->p[2]);
+
+ VectorSubtract (org, vright, w->p[3]);
+ VectorSubtract (w->p[3], vup, w->p[3]);
+
+ w->numpoints = 4;
+
+ return w;
+}
+
+/*
+==================
+CopyWinding
+==================
+*/
+winding_t *CopyWinding (winding_t *w)
+{
+ int size;
+ winding_t *c;
+
+ c = AllocWinding (w->numpoints);
+ size = (int)((winding_t *)0)->p[w->numpoints];
+ memcpy (c, w, size);
+ return c;
+}
+
+/*
+==================
+ReverseWinding
+==================
+*/
+winding_t *ReverseWinding (winding_t *w)
+{
+ int i;
+ winding_t *c;
+
+ c = AllocWinding (w->numpoints);
+ for (i=0 ; i<w->numpoints ; i++)
+ {
+ VectorCopy (w->p[w->numpoints-1-i], c->p[i]);
+ }
+ c->numpoints = w->numpoints;
+ return c;
+}
+
+
+/*
+=============
+ClipWindingEpsilon
+=============
+*/
+void ClipWindingEpsilon (winding_t *in, vec3_t normal, vec_t dist,
+ vec_t epsilon, winding_t **front, winding_t **back)
+{
+ vec_t dists[MAX_POINTS_ON_WINDING+4];
+ int sides[MAX_POINTS_ON_WINDING+4];
+ int counts[3];
+ static vec_t dot; // VC 4.2 optimizer bug if not static
+ int i, j;
+ vec_t *p1, *p2;
+ vec3_t mid;
+ winding_t *f, *b;
+ int maxpts;
+
+ counts[0] = counts[1] = counts[2] = 0;
+
+// determine sides for each point
+ for (i=0 ; i<in->numpoints ; i++)
+ {
+ dot = DotProduct (in->p[i], normal);
+ dot -= dist;
+ dists[i] = dot;
+ if (dot > epsilon)
+ sides[i] = SIDE_FRONT;
+ else if (dot < -epsilon)
+ sides[i] = SIDE_BACK;
+ else
+ {
+ sides[i] = SIDE_ON;
+ }
+ counts[sides[i]]++;
+ }
+ sides[i] = sides[0];
+ dists[i] = dists[0];
+
+ *front = *back = NULL;
+
+ if (!counts[0])
+ {
+ *back = CopyWinding (in);
+ return;
+ }
+ if (!counts[1])
+ {
+ *front = CopyWinding (in);
+ return;
+ }
+
+ maxpts = in->numpoints+4; // cant use counts[0]+2 because
+ // of fp grouping errors
+
+ *front = f = AllocWinding (maxpts);
+ *back = b = AllocWinding (maxpts);
+
+ for (i=0 ; i<in->numpoints ; i++)
+ {
+ p1 = in->p[i];
+
+ if (sides[i] == SIDE_ON)
+ {
+ VectorCopy (p1, f->p[f->numpoints]);
+ f->numpoints++;
+ VectorCopy (p1, b->p[b->numpoints]);
+ b->numpoints++;
+ continue;
+ }
+
+ if (sides[i] == SIDE_FRONT)
+ {
+ VectorCopy (p1, f->p[f->numpoints]);
+ f->numpoints++;
+ }
+ if (sides[i] == SIDE_BACK)
+ {
+ VectorCopy (p1, b->p[b->numpoints]);
+ b->numpoints++;
+ }
+
+ if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])
+ continue;
+
+ // generate a split point
+ p2 = in->p[(i+1)%in->numpoints];
+
+ dot = dists[i] / (dists[i]-dists[i+1]);
+ for (j=0 ; j<3 ; j++)
+ { // avoid round off error when possible
+ if (normal[j] == 1)
+ mid[j] = dist;
+ else if (normal[j] == -1)
+ mid[j] = -dist;
+ else
+ mid[j] = p1[j] + dot*(p2[j]-p1[j]);
+ }
+
+ VectorCopy (mid, f->p[f->numpoints]);
+ f->numpoints++;
+ VectorCopy (mid, b->p[b->numpoints]);
+ b->numpoints++;
+ }
+
+ if (f->numpoints > maxpts || b->numpoints > maxpts)
+ Error ("ClipWinding: points exceeded estimate");
+ if (f->numpoints > MAX_POINTS_ON_WINDING || b->numpoints > MAX_POINTS_ON_WINDING)
+ Error ("ClipWinding: MAX_POINTS_ON_WINDING");
+}
+
+
+/*
+=============
+ChopWindingInPlace
+=============
+*/
+void ChopWindingInPlace (winding_t **inout, vec3_t normal, vec_t dist, vec_t epsilon)
+{
+ winding_t *in;
+ vec_t dists[MAX_POINTS_ON_WINDING+4];
+ int sides[MAX_POINTS_ON_WINDING+4];
+ int counts[3];
+ static vec_t dot; // VC 4.2 optimizer bug if not static
+ int i, j;
+ vec_t *p1, *p2;
+ vec3_t mid;
+ winding_t *f;
+ int maxpts;
+
+ in = *inout;
+ counts[0] = counts[1] = counts[2] = 0;
+
+// determine sides for each point
+ for (i=0 ; i<in->numpoints ; i++)
+ {
+ dot = DotProduct (in->p[i], normal);
+ dot -= dist;
+ dists[i] = dot;
+ if (dot > epsilon)
+ sides[i] = SIDE_FRONT;
+ else if (dot < -epsilon)
+ sides[i] = SIDE_BACK;
+ else
+ {
+ sides[i] = SIDE_ON;
+ }
+ counts[sides[i]]++;
+ }
+ sides[i] = sides[0];
+ dists[i] = dists[0];
+
+ if (!counts[0])
+ {
+ FreeWinding (in);
+ *inout = NULL;
+ return;
+ }
+ if (!counts[1])
+ return; // inout stays the same
+
+ maxpts = in->numpoints+4; // cant use counts[0]+2 because
+ // of fp grouping errors
+
+ f = AllocWinding (maxpts);
+
+ for (i=0 ; i<in->numpoints ; i++)
+ {
+ p1 = in->p[i];
+
+ if (sides[i] == SIDE_ON)
+ {
+ VectorCopy (p1, f->p[f->numpoints]);
+ f->numpoints++;
+ continue;
+ }
+
+ if (sides[i] == SIDE_FRONT)
+ {
+ VectorCopy (p1, f->p[f->numpoints]);
+ f->numpoints++;
+ }
+
+ if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])
+ continue;
+
+ // generate a split point
+ p2 = in->p[(i+1)%in->numpoints];
+
+ dot = dists[i] / (dists[i]-dists[i+1]);
+ for (j=0 ; j<3 ; j++)
+ { // avoid round off error when possible
+ if (normal[j] == 1)
+ mid[j] = dist;
+ else if (normal[j] == -1)
+ mid[j] = -dist;
+ else
+ mid[j] = p1[j] + dot*(p2[j]-p1[j]);
+ }
+
+ VectorCopy (mid, f->p[f->numpoints]);
+ f->numpoints++;
+ }
+
+ if (f->numpoints > maxpts)
+ Error ("ClipWinding: points exceeded estimate");
+ if (f->numpoints > MAX_POINTS_ON_WINDING)
+ Error ("ClipWinding: MAX_POINTS_ON_WINDING");
+
+ FreeWinding (in);
+ *inout = f;
+}
+
+
+/*
+=================
+ChopWinding
+
+Returns the fragment of in that is on the front side
+of the cliping plane. The original is freed.
+=================
+*/
+winding_t *ChopWinding (winding_t *in, vec3_t normal, vec_t dist)
+{
+ winding_t *f, *b;
+
+ ClipWindingEpsilon (in, normal, dist, ON_EPSILON, &f, &b);
+ FreeWinding (in);
+ if (b)
+ FreeWinding (b);
+ return f;
+}
+
+
+/*
+=================
+CheckWinding
+
+=================
+*/
+void CheckWinding (winding_t *w)
+{
+ int i, j;
+ vec_t *p1, *p2;
+ vec_t d, edgedist;
+ vec3_t dir, edgenormal, facenormal;
+ vec_t area;
+ vec_t facedist;
+
+ if (w->numpoints < 3)
+ Error ("CheckWinding: %i points",w->numpoints);
+
+ area = WindingArea(w);
+ if (area < 1)
+ Error ("CheckWinding: %f area", area);
+
+ 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)
+ Error ("CheckFace: BUGUS_RANGE: %f",p1[j]);
+
+ 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)
+ Error ("CheckWinding: point off plane");
+
+ // check the edge isnt degenerate
+ p2 = w->p[j];
+ VectorSubtract (p2, p1, dir);
+
+ if (VectorLength (dir) < ON_EPSILON)
+ Error ("CheckWinding: degenerate edge");
+
+ CrossProduct (facenormal, dir, edgenormal);
+ VectorNormalize (edgenormal, 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)
+ Error ("CheckWinding: non-convex");
+ }
+ }
+}
+
+
+/*
+============
+WindingOnPlaneSide
+============
+*/
+int WindingOnPlaneSide (winding_t *w, vec3_t normal, vec_t dist)
+{
+ qboolean front, back;
+ int i;
+ vec_t d;
+
+ front = false;
+ back = false;
+ for (i=0 ; i<w->numpoints ; i++)
+ {
+ d = DotProduct (w->p[i], normal) - dist;
+ if (d < -ON_EPSILON)
+ {
+ if (front)
+ return SIDE_CROSS;
+ back = true;
+ continue;
+ }
+ if (d > ON_EPSILON)
+ {
+ if (back)
+ return SIDE_CROSS;
+ front = true;
+ continue;
+ }
+ }
+
+ if (back)
+ return SIDE_BACK;
+ if (front)
+ return SIDE_FRONT;
+ return SIDE_ON;
+}
+