From 6bf20c78f5b69d40bcc4931df93d29198435ab67 Mon Sep 17 00:00:00 2001 From: zakk Date: Fri, 26 Aug 2005 17:39:27 +0000 Subject: newlines fixed git-svn-id: svn://svn.icculus.org/quake3/trunk@6 edf5b092-35ff-0310-97b2-ce42778d08ea --- common/polylib.c | 1438 +++++++++++++++++++++++++++--------------------------- 1 file changed, 719 insertions(+), 719 deletions(-) (limited to 'common/polylib.c') diff --git a/common/polylib.c b/common/polylib.c index c0e89a7..2acf0f5 100755 --- a/common/polylib.c +++ b/common/polylib.c @@ -19,722 +19,722 @@ along with Foobar; if not, write to the Free Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA =========================================================================== */ - -#include "cmdlib.h" -#include "mathlib.h" -#include "polylib.h" -#include "qfiles.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 WORLD_SIZE - -void pw(winding_t *w) -{ - int i; - for (i=0 ; inumpoints ; 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 ; inumpoints ; 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 ; inumpoints ; 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 ; inumpoints ; 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 ; inumpoints ; 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, MAX_WORLD_COORD, vup); - VectorScale (vright, MAX_WORLD_COORD, 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 ; inumpoints ; 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 ; inumpoints ; 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 ; inumpoints ; 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 ; inumpoints ; 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 ; inumpoints ; 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 ; inumpoints ; i++) - { - p1 = w->p[i]; - - for (j=0 ; j<3 ; j++) - if (p1[j] > MAX_WORLD_COORD || p1[j] < MIN_WORLD_COORD) - 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 ; jnumpoints ; 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 = qfalse; - back = qfalse; - for (i=0 ; inumpoints ; i++) - { - d = DotProduct (w->p[i], normal) - dist; - if (d < -ON_EPSILON) - { - if (front) - return SIDE_CROSS; - back = qtrue; - continue; - } - if (d > ON_EPSILON) - { - if (back) - return SIDE_CROSS; - front = qtrue; - continue; - } - } - - if (back) - return SIDE_BACK; - if (front) - return SIDE_FRONT; - return SIDE_ON; -} - - -/* -================= -AddWindingToConvexHull - -Both w and *hull are on the same plane -================= -*/ -#define MAX_HULL_POINTS 128 -void AddWindingToConvexHull( winding_t *w, winding_t **hull, vec3_t normal ) { - int i, j, k; - float *p, *copy; - vec3_t dir; - float d; - int numHullPoints, numNew; - vec3_t hullPoints[MAX_HULL_POINTS]; - vec3_t newHullPoints[MAX_HULL_POINTS]; - vec3_t hullDirs[MAX_HULL_POINTS]; - qboolean hullSide[MAX_HULL_POINTS]; - qboolean outside; - - if ( !*hull ) { - *hull = CopyWinding( w ); - return; - } - - numHullPoints = (*hull)->numpoints; - memcpy( hullPoints, (*hull)->p, numHullPoints * sizeof(vec3_t) ); - - for ( i = 0 ; i < w->numpoints ; i++ ) { - p = w->p[i]; - - // calculate hull side vectors - for ( j = 0 ; j < numHullPoints ; j++ ) { - k = ( j + 1 ) % numHullPoints; - - VectorSubtract( hullPoints[k], hullPoints[j], dir ); - VectorNormalize( dir, dir ); - CrossProduct( normal, dir, hullDirs[j] ); - } - - outside = qfalse; - for ( j = 0 ; j < numHullPoints ; j++ ) { - VectorSubtract( p, hullPoints[j], dir ); - d = DotProduct( dir, hullDirs[j] ); - if ( d >= ON_EPSILON ) { - outside = qtrue; - } - if ( d >= -ON_EPSILON ) { - hullSide[j] = qtrue; - } else { - hullSide[j] = qfalse; - } - } - - // if the point is effectively inside, do nothing - if ( !outside ) { - continue; - } - - // find the back side to front side transition - for ( j = 0 ; j < numHullPoints ; j++ ) { - if ( !hullSide[ j % numHullPoints ] && hullSide[ (j + 1) % numHullPoints ] ) { - break; - } - } - if ( j == numHullPoints ) { - continue; - } - - // insert the point here - VectorCopy( p, newHullPoints[0] ); - numNew = 1; - - // copy over all points that aren't double fronts - j = (j+1)%numHullPoints; - for ( k = 0 ; k < numHullPoints ; k++ ) { - if ( hullSide[ (j+k) % numHullPoints ] && hullSide[ (j+k+1) % numHullPoints ] ) { - continue; - } - copy = hullPoints[ (j+k+1) % numHullPoints ]; - VectorCopy( copy, newHullPoints[numNew] ); - numNew++; - } - - numHullPoints = numNew; - memcpy( hullPoints, newHullPoints, numHullPoints * sizeof(vec3_t) ); - } - - FreeWinding( *hull ); - w = AllocWinding( numHullPoints ); - w->numpoints = numHullPoints; - *hull = w; - memcpy( w->p, hullPoints, numHullPoints * sizeof(vec3_t) ); -} - - + +#include "cmdlib.h" +#include "mathlib.h" +#include "polylib.h" +#include "qfiles.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 WORLD_SIZE + +void pw(winding_t *w) +{ + int i; + for (i=0 ; inumpoints ; 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 ; inumpoints ; 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 ; inumpoints ; 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 ; inumpoints ; 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 ; inumpoints ; 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, MAX_WORLD_COORD, vup); + VectorScale (vright, MAX_WORLD_COORD, 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 ; inumpoints ; 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 ; inumpoints ; 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 ; inumpoints ; 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 ; inumpoints ; 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 ; inumpoints ; 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 ; inumpoints ; i++) + { + p1 = w->p[i]; + + for (j=0 ; j<3 ; j++) + if (p1[j] > MAX_WORLD_COORD || p1[j] < MIN_WORLD_COORD) + 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 ; jnumpoints ; 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 = qfalse; + back = qfalse; + for (i=0 ; inumpoints ; i++) + { + d = DotProduct (w->p[i], normal) - dist; + if (d < -ON_EPSILON) + { + if (front) + return SIDE_CROSS; + back = qtrue; + continue; + } + if (d > ON_EPSILON) + { + if (back) + return SIDE_CROSS; + front = qtrue; + continue; + } + } + + if (back) + return SIDE_BACK; + if (front) + return SIDE_FRONT; + return SIDE_ON; +} + + +/* +================= +AddWindingToConvexHull + +Both w and *hull are on the same plane +================= +*/ +#define MAX_HULL_POINTS 128 +void AddWindingToConvexHull( winding_t *w, winding_t **hull, vec3_t normal ) { + int i, j, k; + float *p, *copy; + vec3_t dir; + float d; + int numHullPoints, numNew; + vec3_t hullPoints[MAX_HULL_POINTS]; + vec3_t newHullPoints[MAX_HULL_POINTS]; + vec3_t hullDirs[MAX_HULL_POINTS]; + qboolean hullSide[MAX_HULL_POINTS]; + qboolean outside; + + if ( !*hull ) { + *hull = CopyWinding( w ); + return; + } + + numHullPoints = (*hull)->numpoints; + memcpy( hullPoints, (*hull)->p, numHullPoints * sizeof(vec3_t) ); + + for ( i = 0 ; i < w->numpoints ; i++ ) { + p = w->p[i]; + + // calculate hull side vectors + for ( j = 0 ; j < numHullPoints ; j++ ) { + k = ( j + 1 ) % numHullPoints; + + VectorSubtract( hullPoints[k], hullPoints[j], dir ); + VectorNormalize( dir, dir ); + CrossProduct( normal, dir, hullDirs[j] ); + } + + outside = qfalse; + for ( j = 0 ; j < numHullPoints ; j++ ) { + VectorSubtract( p, hullPoints[j], dir ); + d = DotProduct( dir, hullDirs[j] ); + if ( d >= ON_EPSILON ) { + outside = qtrue; + } + if ( d >= -ON_EPSILON ) { + hullSide[j] = qtrue; + } else { + hullSide[j] = qfalse; + } + } + + // if the point is effectively inside, do nothing + if ( !outside ) { + continue; + } + + // find the back side to front side transition + for ( j = 0 ; j < numHullPoints ; j++ ) { + if ( !hullSide[ j % numHullPoints ] && hullSide[ (j + 1) % numHullPoints ] ) { + break; + } + } + if ( j == numHullPoints ) { + continue; + } + + // insert the point here + VectorCopy( p, newHullPoints[0] ); + numNew = 1; + + // copy over all points that aren't double fronts + j = (j+1)%numHullPoints; + for ( k = 0 ; k < numHullPoints ; k++ ) { + if ( hullSide[ (j+k) % numHullPoints ] && hullSide[ (j+k+1) % numHullPoints ] ) { + continue; + } + copy = hullPoints[ (j+k+1) % numHullPoints ]; + VectorCopy( copy, newHullPoints[numNew] ); + numNew++; + } + + numHullPoints = numNew; + memcpy( hullPoints, newHullPoints, numHullPoints * sizeof(vec3_t) ); + } + + FreeWinding( *hull ); + w = AllocWinding( numHullPoints ); + w->numpoints = numHullPoints; + *hull = w; + memcpy( w->p, hullPoints, numHullPoints * sizeof(vec3_t) ); +} + + -- cgit v1.2.3