X-Git-Url: https://de.git.xonotic.org/?p=xonotic%2Fnetradiant.git;a=blobdiff_plain;f=tools%2Fquake3%2Fcommon%2Fpolylib.c;h=c7b85dd3aa818192b38d75de6ac0824cc7d3b270;hp=34dd173ecbd0473715dd3a688ce22ac785f6756d;hb=7fc621fc78d0e040dc2c12f38dc53dd9048215dc;hpb=94cb905da9c38e65cff6dcd9a56874c33c367df2 diff --git a/tools/quake3/common/polylib.c b/tools/quake3/common/polylib.c index 34dd173e..c7b85dd3 100644 --- a/tools/quake3/common/polylib.c +++ b/tools/quake3/common/polylib.c @@ -1,23 +1,23 @@ /* -Copyright (C) 1999-2006 Id Software, Inc. and contributors. -For a list of contributors, see the accompanying CONTRIBUTORS file. + Copyright (C) 1999-2006 Id Software, Inc. and contributors. + For a list of contributors, see the accompanying CONTRIBUTORS file. -This file is part of GtkRadiant. + 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 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. + 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 -*/ + 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" @@ -31,236 +31,238 @@ 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++) - Sys_Printf ("(%5.1f, %5.1f, %5.1f)\n",w->p[i][0], w->p[i][1],w->p[i][2]); +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 ; i < w->numpoints ; i++ ) + Sys_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 (points >= MAX_POINTS_ON_WINDING) - Error ("AllocWinding failed: MAX_POINTS_ON_WINDING exceeded"); - - if (numthreads == 1) - { + ============= + AllocWinding + ============= + */ +winding_t *AllocWinding( int points ){ + winding_t *w; + int s; + + if ( points >= MAX_POINTS_ON_WINDING ) { + Error( "AllocWinding failed: MAX_POINTS_ON_WINDING exceeded" ); + } + + if ( numthreads == 1 ) { c_winding_allocs++; c_winding_points += points; c_active_windings++; - if (c_active_windings > c_peak_windings) + if ( c_active_windings > c_peak_windings ) { c_peak_windings = c_active_windings; + } } - s = sizeof(vec_t)*3*points + sizeof(int); - w = safe_malloc (s); - memset (w, 0, s); + s = sizeof( *w ) + ( points ? sizeof( w->p[0] ) * ( points - 1 ) : 0 ); + w = safe_malloc( s ); + memset( w, 0, s ); return w; } /* -============= -AllocWindingAccu -============= -*/ -winding_accu_t *AllocWindingAccu(int points) -{ - winding_accu_t *w; - int s; - - if (points >= MAX_POINTS_ON_WINDING) - Error("AllocWindingAccu failed: MAX_POINTS_ON_WINDING exceeded"); - - if (numthreads == 1) - { + ============= + AllocWindingAccu + ============= + */ +winding_accu_t *AllocWindingAccu( int points ){ + winding_accu_t *w; + int s; + + if ( points >= MAX_POINTS_ON_WINDING ) { + Error( "AllocWindingAccu failed: MAX_POINTS_ON_WINDING exceeded" ); + } + + if ( numthreads == 1 ) { // At the time of this writing, these statistics were not used in any way. c_winding_allocs++; c_winding_points += points; c_active_windings++; - if (c_active_windings > c_peak_windings) + if ( c_active_windings > c_peak_windings ) { c_peak_windings = c_active_windings; + } } - s = sizeof(vec_accu_t) * 3 * points + sizeof(int); - w = safe_malloc(s); - memset(w, 0, s); + s = sizeof( *w ) + ( points ? sizeof( w->p[0] ) * ( points - 1 ) : 0 ); + w = safe_malloc( s ); + memset( w, 0, s ); return w; } /* -============= -FreeWinding -============= -*/ -void FreeWinding (winding_t *w) -{ - if (!w) Error("FreeWinding: winding is NULL"); - - if (*(unsigned *)w == 0xdeaddead) - Error ("FreeWinding: freed a freed winding"); + ============= + FreeWinding + ============= + */ +void FreeWinding( winding_t *w ){ + if ( !w ) { + Error( "FreeWinding: winding is NULL" ); + } + + if ( *(unsigned *)w == 0xdeaddead ) { + Error( "FreeWinding: freed a freed winding" ); + } *(unsigned *)w = 0xdeaddead; - if (numthreads == 1) + if ( numthreads == 1 ) { c_active_windings--; - free (w); + } + free( w ); } /* -============= -FreeWindingAccu -============= -*/ -void FreeWindingAccu(winding_accu_t *w) -{ - if (!w) Error("FreeWindingAccu: winding is NULL"); - - if (*((unsigned *) w) == 0xdeaddead) - Error("FreeWindingAccu: freed a freed winding"); - *((unsigned *) w) = 0xdeaddead; - - if (numthreads == 1) + ============= + FreeWindingAccu + ============= + */ +void FreeWindingAccu( winding_accu_t *w ){ + if ( !w ) { + Error( "FreeWindingAccu: winding is NULL" ); + } + + if ( *( (unsigned *) w ) == 0xdeaddead ) { + Error( "FreeWindingAccu: freed a freed winding" ); + } + *( (unsigned *) w ) = 0xdeaddead; + + if ( numthreads == 1 ) { c_active_windings--; - free(w); + } + 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]; + ============ + 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++) + 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]); + 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) + if ( nump == w->numpoints ) { return; + } - if (numthreads == 1) + if ( numthreads == 1 ) { c_removed += w->numpoints - nump; + } w->numpoints = nump; - memcpy (w->p, p, nump*sizeof(p[0])); + 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); + ============ + 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; + ============= + WindingArea + ============= + */ +vec_t WindingArea( winding_t *w ){ + int i; + vec3_t d1, d2, cross; + vec_t total; total = 0; - for (i=2 ; inumpoints ; i++) + 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 ); + 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; +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 ( i = 0 ; i < w->numpoints ; i++ ) { - for (j=0 ; j<3 ; j++) + for ( j = 0 ; j < 3 ; j++ ) { v = w->p[i][j]; - if (v < mins[j]) + if ( v < mins[j] ) { mins[j] = v; - if (v > maxs[j]) + } + 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); + ============= + 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 ); } /* -================= -BaseWindingForPlaneAccu -================= -*/ -winding_accu_t *BaseWindingForPlaneAccu(vec3_t normal, vec_t dist) -{ + ================= + BaseWindingForPlaneAccu + ================= + */ +winding_accu_t *BaseWindingForPlaneAccu( vec3_t normal, vec_t dist ){ // The goal in this function is to replicate the behavior of the original BaseWindingForPlane() // function (see below) but at the same time increasing accuracy substantially. @@ -274,10 +276,10 @@ winding_accu_t *BaseWindingForPlaneAccu(vec3_t normal, vec_t dist) // variable in this function (depending on the angle of normal), and is larger (by about a factor // of 2) than the winding polygon in the original function. - int x, i; - vec_t max, v; - vec3_accu_t vright, vup, org, normalAccu; - winding_accu_t *w; + int x, i; + vec_t max, v; + vec3_accu_t vright, vup, org, normalAccu; + winding_accu_t *w; // One of the components of normal must have a magnitiude greater than this value, // otherwise normal is not a unit vector. This is a little bit of inexpensive @@ -285,27 +287,29 @@ winding_accu_t *BaseWindingForPlaneAccu(vec3_t normal, vec_t dist) max = 0.56; // 1 / sqrt(1^2 + 1^2 + 1^2) = 0.577350269 x = -1; - for (i = 0; i < 3; i++) { - v = (vec_t) fabs(normal[i]); - if (v > max) { + for ( i = 0; i < 3; i++ ) { + v = (vec_t) fabs( normal[i] ); + if ( v > max ) { x = i; max = v; } } - if (x == -1) Error("BaseWindingForPlaneAccu: no dominant axis found because normal is too short"); - - switch (x) { - case 0: // Fall through to next case. - case 1: - vright[0] = (vec_accu_t) -normal[1]; - vright[1] = (vec_accu_t) normal[0]; - vright[2] = 0; - break; - case 2: - vright[0] = 0; - vright[1] = (vec_accu_t) -normal[2]; - vright[2] = (vec_accu_t) normal[1]; - break; + if ( x == -1 ) { + Error( "BaseWindingForPlaneAccu: no dominant axis found because normal is too short" ); + } + + switch ( x ) { + case 0: // Fall through to next case. + case 1: + vright[0] = (vec_accu_t) -normal[1]; + vright[1] = (vec_accu_t) normal[0]; + vright[2] = 0; + break; + case 2: + vright[0] = 0; + vright[1] = (vec_accu_t) -normal[2]; + vright[2] = (vec_accu_t) normal[1]; + break; } // vright and normal are now perpendicular; you can prove this by taking their @@ -321,19 +325,19 @@ winding_accu_t *BaseWindingForPlaneAccu(vec3_t normal, vec_t dist) // We're relying on the fact that MAX_WORLD_COORD is a power of 2 to keep // our calculation precise and relatively free of floating point error. // [However, the code will still work fine if that's not the case.] - VectorScaleAccu(vright, ((vec_accu_t) MAX_WORLD_COORD) * 4.0, vright); + VectorScaleAccu( vright, ( (vec_accu_t) MAX_WORLD_COORD ) * 4.0, vright ); // At time time of this writing, MAX_WORLD_COORD was 65536 (2^16). Therefore // the length of vright at this point is at least 185364. In comparison, a // corner of the world at location (65536, 65536, 65536) is distance 113512 // away from the origin. - VectorCopyRegularToAccu(normal, normalAccu); - CrossProductAccu(normalAccu, vright, vup); + VectorCopyRegularToAccu( normal, normalAccu ); + CrossProductAccu( normalAccu, vright, vup ); // vup now has length equal to that of vright. - VectorScaleAccu(normalAccu, (vec_accu_t) dist, org); + VectorScaleAccu( normalAccu, (vec_accu_t) dist, org ); // org is now a point on the plane defined by normal and dist. Furthermore, // org, vright, and vup are pairwise perpendicular. Now, the 4 vectors @@ -347,19 +351,19 @@ winding_accu_t *BaseWindingForPlaneAccu(vec3_t normal, vec_t dist) // outside the world. sqrt(262144^2 + 262144^2)/2 = 185363, which is greater than // 113512. - w = AllocWindingAccu(4); + w = AllocWindingAccu( 4 ); - VectorSubtractAccu(org, vright, w->p[0]); - VectorAddAccu(w->p[0], vup, w->p[0]); + VectorSubtractAccu( org, vright, w->p[0] ); + VectorAddAccu( w->p[0], vup, w->p[0] ); - VectorAddAccu(org, vright, w->p[1]); - VectorAddAccu(w->p[1], vup, w->p[1]); + VectorAddAccu( org, vright, w->p[1] ); + VectorAddAccu( w->p[1], vup, w->p[1] ); - VectorAddAccu(org, vright, w->p[2]); - VectorSubtractAccu(w->p[2], vup, w->p[2]); + VectorAddAccu( org, vright, w->p[2] ); + VectorSubtractAccu( w->p[2], vup, w->p[2] ); - VectorSubtractAccu(org, vright, w->p[3]); - VectorSubtractAccu(w->p[3], vup, w->p[3]); + VectorSubtractAccu( org, vright, w->p[3] ); + VectorSubtractAccu( w->p[3], vup, w->p[3] ); w->numpoints = 4; @@ -367,164 +371,165 @@ winding_accu_t *BaseWindingForPlaneAccu(vec3_t normal, vec_t dist) } /* -================= -BaseWindingForPlane - -Original BaseWindingForPlane() function that has serious accuracy problems. Here is why. -The base winding is computed as a rectangle with very large coordinates. These coordinates -are in the range 2^17 or 2^18. "Epsilon" (meaning the distance between two adjacent numbers) -at these magnitudes in 32 bit floating point world is about 0.02. So for example, if things -go badly (by bad luck), then the whole plane could be shifted by 0.02 units (its distance could -be off by that much). Then if we were to compute the winding of this plane and another of -the brush's planes met this winding at a very acute angle, that error could multiply to around -0.1 or more when computing the final vertex coordinates of the winding. 0.1 is a very large -error, and can lead to all sorts of disappearing triangle problems. -================= -*/ -winding_t *BaseWindingForPlane (vec3_t normal, vec_t dist) -{ - int i, x; - vec_t max, v; - vec3_t org, vright, vup; - winding_t *w; - + ================= + BaseWindingForPlane + + Original BaseWindingForPlane() function that has serious accuracy problems. Here is why. + The base winding is computed as a rectangle with very large coordinates. These coordinates + are in the range 2^17 or 2^18. "Epsilon" (meaning the distance between two adjacent numbers) + at these magnitudes in 32 bit floating point world is about 0.02. So for example, if things + go badly (by bad luck), then the whole plane could be shifted by 0.02 units (its distance could + be off by that much). Then if we were to compute the winding of this plane and another of + the brush's planes met this winding at a very acute angle, that error could multiply to around + 0.1 or more when computing the final vertex coordinates of the winding. 0.1 is a very large + error, and can lead to all sorts of disappearing triangle problems. + ================= + */ +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++) + for ( i = 0 ; i < 3; i++ ) { - v = fabs(normal[i]); - if (v > max) - { + 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) + if ( x == -1 ) { + Error( "BaseWindingForPlane: no axis found" ); + } + + VectorCopy( vec3_origin, vup ); + switch ( x ) { case 0: case 1: vup[2] = 1; - break; + break; case 2: vup[0] = 1; - break; + break; } - v = DotProduct (vup, normal); - VectorMA (vup, -v, normal, vup); - VectorNormalize (vup, vup); - - VectorScale (normal, dist, org); - - CrossProduct (vup, normal, vright); - + v = DotProduct( vup, normal ); + VectorMA( vup, -v, normal, vup ); + VectorNormalize( vup, vup ); + + VectorScale( normal, dist, org ); + + CrossProduct( vup, normal, vright ); + // LordHavoc: this has to use *2 because otherwise some created points may // be inside the world (think of a diagonal case), and any brush with such // points should be removed, failure to detect such cases is disasterous - VectorScale (vup, MAX_WORLD_COORD*2, vup); - VectorScale (vright, MAX_WORLD_COORD*2, 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]); - + VectorScale( vup, MAX_WORLD_COORD * 2, vup ); + VectorScale( vright, MAX_WORLD_COORD * 2, 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; + + return w; } /* -================== -CopyWinding -================== -*/ -winding_t *CopyWinding (winding_t *w) -{ - size_t size; - winding_t *c; - - if (!w) Error("CopyWinding: winding is NULL"); - - c = AllocWinding (w->numpoints); - size = (size_t)((winding_t *)NULL)->p[w->numpoints]; - memcpy (c, w, size); + ================== + CopyWinding + ================== + */ +winding_t *CopyWinding( winding_t *w ){ + size_t size; + winding_t *c; + + if ( !w ) { + Error( "CopyWinding: winding is NULL" ); + } + + c = AllocWinding( w->numpoints ); + size = (size_t)( (winding_t *)NULL )->p[w->numpoints]; + memcpy( c, w, size ); return c; } /* -================== -CopyWindingAccuIncreaseSizeAndFreeOld -================== -*/ -winding_accu_t *CopyWindingAccuIncreaseSizeAndFreeOld(winding_accu_t *w) -{ - int i; - winding_accu_t *c; - - if (!w) Error("CopyWindingAccuIncreaseSizeAndFreeOld: winding is NULL"); - - c = AllocWindingAccu(w->numpoints + 1); + ================== + CopyWindingAccuIncreaseSizeAndFreeOld + ================== + */ +winding_accu_t *CopyWindingAccuIncreaseSizeAndFreeOld( winding_accu_t *w ){ + int i; + winding_accu_t *c; + + if ( !w ) { + Error( "CopyWindingAccuIncreaseSizeAndFreeOld: winding is NULL" ); + } + + c = AllocWindingAccu( w->numpoints + 1 ); c->numpoints = w->numpoints; - for (i = 0; i < c->numpoints; i++) + for ( i = 0; i < c->numpoints; i++ ) { - VectorCopyAccu(w->p[i], c->p[i]); + VectorCopyAccu( w->p[i], c->p[i] ); } - FreeWindingAccu(w); + FreeWindingAccu( w ); return c; } /* -================== -CopyWindingAccuToRegular -================== -*/ -winding_t *CopyWindingAccuToRegular(winding_accu_t *w) -{ - int i; - winding_t *c; - - if (!w) Error("CopyWindingAccuToRegular: winding is NULL"); - - c = AllocWinding(w->numpoints); + ================== + CopyWindingAccuToRegular + ================== + */ +winding_t *CopyWindingAccuToRegular( winding_accu_t *w ){ + int i; + winding_t *c; + + if ( !w ) { + Error( "CopyWindingAccuToRegular: winding is NULL" ); + } + + c = AllocWinding( w->numpoints ); c->numpoints = w->numpoints; - for (i = 0; i < c->numpoints; i++) + for ( i = 0; i < c->numpoints; i++ ) { - VectorCopyAccuToRegular(w->p[i], c->p[i]); + VectorCopyAccuToRegular( w->p[i], c->p[i] ); } return c; } /* -================== -ReverseWinding -================== -*/ -winding_t *ReverseWinding (winding_t *w) -{ - int i; - winding_t *c; - - c = AllocWinding (w->numpoints); - for (i=0 ; inumpoints ; i++) + ================== + 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]); + VectorCopy( w->p[w->numpoints - 1 - i], c->p[i] ); } c->numpoints = w->numpoints; return c; @@ -532,36 +537,37 @@ winding_t *ReverseWinding (winding_t *w) /* -============= -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; - + ============= + ClipWindingEpsilon + ============= + */ +void ClipWindingEpsilonStrict( 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++) - { + for ( i = 0 ; i < in->numpoints ; i++ ) + { - dot = DotProduct (in->p[i], normal); + dot = DotProduct( in->p[i], normal ); dot -= dist; dists[i] = dot; - if (dot > epsilon) + if ( dot > epsilon ) { sides[i] = SIDE_FRONT; - else if (dot < -epsilon) + } + else if ( dot < -epsilon ) { sides[i] = SIDE_BACK; + } else { sides[i] = SIDE_ON; @@ -570,98 +576,110 @@ void ClipWindingEpsilon (winding_t *in, vec3_t normal, vec_t dist, } sides[i] = sides[0]; dists[i] = dists[0]; - + *front = *back = NULL; - if (!counts[0]) - { - *back = CopyWinding (in); + if ( !counts[0] && !counts[1] ) { return; } - if (!counts[1]) - { - *front = CopyWinding (in); + 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 - maxpts = in->numpoints+4; // cant use counts[0]+2 because - // of fp grouping errors + *front = f = AllocWinding( maxpts ); + *back = b = AllocWinding( maxpts ); - *front = f = AllocWinding (maxpts); - *back = b = AllocWinding (maxpts); - - for (i=0 ; inumpoints ; i++) + for ( i = 0 ; i < in->numpoints ; i++ ) { p1 = in->p[i]; - - if (sides[i] == SIDE_ON) - { - VectorCopy (p1, f->p[f->numpoints]); + + if ( sides[i] == SIDE_ON ) { + VectorCopy( p1, f->p[f->numpoints] ); f->numpoints++; - VectorCopy (p1, b->p[b->numpoints]); + VectorCopy( p1, b->p[b->numpoints] ); b->numpoints++; continue; } - - if (sides[i] == SIDE_FRONT) - { - VectorCopy (p1, f->p[f->numpoints]); + + if ( sides[i] == SIDE_FRONT ) { + VectorCopy( p1, f->p[f->numpoints] ); f->numpoints++; } - if (sides[i] == SIDE_BACK) - { - VectorCopy (p1, b->p[b->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]) + 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) + } + + // 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) + } + else if ( normal[j] == -1 ) { mid[j] = -dist; - else - mid[j] = p1[j] + dot*(p2[j]-p1[j]); + } + else{ + mid[j] = p1[j] + dot * ( p2[j] - p1[j] ); + } } - - VectorCopy (mid, f->p[f->numpoints]); + + VectorCopy( mid, f->p[f->numpoints] ); f->numpoints++; - VectorCopy (mid, b->p[b->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"); + + 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" ); + } +} + +void ClipWindingEpsilon( winding_t *in, vec3_t normal, vec_t dist, + vec_t epsilon, winding_t **front, winding_t **back ){ + ClipWindingEpsilonStrict( in, normal, dist, epsilon, front, back ); + /* apparently most code expects that in the winding-on-plane case, the back winding is the original winding */ + if ( !*front && !*back ) { + *back = CopyWinding( in ); + } } /* -============= -ChopWindingInPlaceAccu -============= -*/ -void ChopWindingInPlaceAccu(winding_accu_t **inout, vec3_t normal, vec_t dist, vec_t crudeEpsilon) -{ - vec_accu_t fineEpsilon; - winding_accu_t *in; - int counts[3]; - int i, j; - vec_accu_t dists[MAX_POINTS_ON_WINDING + 1]; - int sides[MAX_POINTS_ON_WINDING + 1]; - int maxpts; - winding_accu_t *f; - vec_accu_t *p1, *p2; - vec_accu_t w; - vec3_accu_t mid, normalAccu; + ============= + ChopWindingInPlaceAccu + ============= + */ +void ChopWindingInPlaceAccu( winding_accu_t **inout, vec3_t normal, vec_t dist, vec_t crudeEpsilon ){ + vec_accu_t fineEpsilon; + winding_accu_t *in; + int counts[3]; + int i, j; + vec_accu_t dists[MAX_POINTS_ON_WINDING + 1]; + int sides[MAX_POINTS_ON_WINDING + 1]; + int maxpts; + winding_accu_t *f; + vec_accu_t *p1, *p2; + vec_accu_t w; + vec3_accu_t mid, normalAccu; // We require at least a very small epsilon. It's a good idea for several reasons. // First, we will be dividing by a potentially very small distance below. We don't @@ -695,34 +713,40 @@ void ChopWindingInPlaceAccu(winding_accu_t **inout, vec3_t normal, vec_t dist, v // VEC_SMALLEST_EPSILON_AROUND_ONE, you would be guaranteed at least 2000 "ticks" in // 64-bit land inside of the epsilon for all numbers we're dealing with. - static const vec_accu_t smallestEpsilonAllowed = ((vec_accu_t) VEC_SMALLEST_EPSILON_AROUND_ONE) * 0.5; - if (crudeEpsilon < smallestEpsilonAllowed) fineEpsilon = smallestEpsilonAllowed; - else fineEpsilon = (vec_accu_t) crudeEpsilon; + static const vec_accu_t smallestEpsilonAllowed = ( (vec_accu_t) VEC_SMALLEST_EPSILON_AROUND_ONE ) * 0.5; + if ( crudeEpsilon < smallestEpsilonAllowed ) { + fineEpsilon = smallestEpsilonAllowed; + } + else{fineEpsilon = (vec_accu_t) crudeEpsilon; } in = *inout; counts[0] = counts[1] = counts[2] = 0; - VectorCopyRegularToAccu(normal, normalAccu); + VectorCopyRegularToAccu( normal, normalAccu ); - for (i = 0; i < in->numpoints; i++) + for ( i = 0; i < in->numpoints; i++ ) { - dists[i] = DotProductAccu(in->p[i], normalAccu) - dist; - if (dists[i] > fineEpsilon) sides[i] = SIDE_FRONT; - else if (dists[i] < -fineEpsilon) sides[i] = SIDE_BACK; - else sides[i] = SIDE_ON; + dists[i] = DotProductAccu( in->p[i], normalAccu ) - dist; + if ( dists[i] > fineEpsilon ) { + sides[i] = SIDE_FRONT; + } + else if ( dists[i] < -fineEpsilon ) { + sides[i] = SIDE_BACK; + } + else{sides[i] = SIDE_ON; } counts[sides[i]]++; } sides[i] = sides[0]; dists[i] = dists[0]; - + // I'm wondering if whatever code that handles duplicate planes is robust enough // that we never get a case where two nearly equal planes result in 2 NULL windings // due to the 'if' statement below. TODO: Investigate this. - if (!counts[SIDE_FRONT]) { - FreeWindingAccu(in); + if ( !counts[SIDE_FRONT] ) { + FreeWindingAccu( in ); *inout = NULL; return; } - if (!counts[SIDE_BACK]) { + if ( !counts[SIDE_BACK] ) { return; // Winding is unmodified. } @@ -730,92 +754,97 @@ void ChopWindingInPlaceAccu(winding_accu_t **inout, vec3_t normal, vec_t dist, v // In that case, one point is SIDE_FRONT and the other is SIDE_BACK. maxpts = counts[SIDE_FRONT] + 2; // We dynamically expand if this is too small. - f = AllocWindingAccu(maxpts); + f = AllocWindingAccu( maxpts ); - for (i = 0; i < in->numpoints; i++) + for ( i = 0; i < in->numpoints; i++ ) { p1 = in->p[i]; - if (sides[i] == SIDE_ON || sides[i] == SIDE_FRONT) - { - if (f->numpoints >= MAX_POINTS_ON_WINDING) - Error("ChopWindingInPlaceAccu: MAX_POINTS_ON_WINDING"); - if (f->numpoints >= maxpts) // This will probably never happen. - { - Sys_FPrintf(SYS_VRB, "WARNING: estimate on chopped winding size incorrect (no problem)\n"); - f = CopyWindingAccuIncreaseSizeAndFreeOld(f); + if ( sides[i] == SIDE_ON || sides[i] == SIDE_FRONT ) { + if ( f->numpoints >= MAX_POINTS_ON_WINDING ) { + Error( "ChopWindingInPlaceAccu: MAX_POINTS_ON_WINDING" ); + } + if ( f->numpoints >= maxpts ) { // This will probably never happen. + Sys_FPrintf( SYS_VRB, "WARNING: estimate on chopped winding size incorrect (no problem)\n" ); + f = CopyWindingAccuIncreaseSizeAndFreeOld( f ); maxpts++; } - VectorCopyAccu(p1, f->p[f->numpoints]); + VectorCopyAccu( p1, f->p[f->numpoints] ); f->numpoints++; - if (sides[i] == SIDE_ON) continue; + if ( sides[i] == SIDE_ON ) { + continue; + } } - if (sides[i + 1] == SIDE_ON || sides[i + 1] == sides[i]) - { + if ( sides[i + 1] == SIDE_ON || sides[i + 1] == sides[i] ) { continue; } - + // Generate a split point. - p2 = in->p[((i + 1) == in->numpoints) ? 0 : (i + 1)]; + p2 = in->p[( ( i + 1 ) == in->numpoints ) ? 0 : ( i + 1 )]; // The divisor's absolute value is greater than the dividend's absolute value. // w is in the range (0,1). - w = dists[i] / (dists[i] - dists[i + 1]); + w = dists[i] / ( dists[i] - dists[i + 1] ); - for (j = 0; j < 3; j++) + for ( j = 0; j < 3; j++ ) { // Avoid round-off error when possible. Check axis-aligned normal. - if (normal[j] == 1) mid[j] = dist; - else if (normal[j] == -1) mid[j] = -dist; - else mid[j] = p1[j] + (w * (p2[j] - p1[j])); + if ( normal[j] == 1 ) { + mid[j] = dist; + } + else if ( normal[j] == -1 ) { + mid[j] = -dist; + } + else{mid[j] = p1[j] + ( w * ( p2[j] - p1[j] ) ); } } - if (f->numpoints >= MAX_POINTS_ON_WINDING) - Error("ChopWindingInPlaceAccu: MAX_POINTS_ON_WINDING"); - if (f->numpoints >= maxpts) // This will probably never happen. - { - Sys_FPrintf(SYS_VRB, "WARNING: estimate on chopped winding size incorrect (no problem)\n"); - f = CopyWindingAccuIncreaseSizeAndFreeOld(f); + if ( f->numpoints >= MAX_POINTS_ON_WINDING ) { + Error( "ChopWindingInPlaceAccu: MAX_POINTS_ON_WINDING" ); + } + if ( f->numpoints >= maxpts ) { // This will probably never happen. + Sys_FPrintf( SYS_VRB, "WARNING: estimate on chopped winding size incorrect (no problem)\n" ); + f = CopyWindingAccuIncreaseSizeAndFreeOld( f ); maxpts++; } - VectorCopyAccu(mid, f->p[f->numpoints]); + VectorCopyAccu( mid, f->p[f->numpoints] ); f->numpoints++; } - FreeWindingAccu(in); + FreeWindingAccu( in ); *inout = f; } /* -============= -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; + ============= + 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++) + for ( i = 0 ; i < in->numpoints ; i++ ) { - dot = DotProduct (in->p[i], normal); + dot = DotProduct( in->p[i], normal ); dot -= dist; dists[i] = dot; - if (dot > epsilon) + if ( dot > epsilon ) { sides[i] = SIDE_FRONT; - else if (dot < -epsilon) + } + else if ( dot < -epsilon ) { sides[i] = SIDE_BACK; + } else { sides[i] = SIDE_ON; @@ -824,220 +853,231 @@ void ChopWindingInPlace (winding_t **inout, vec3_t normal, vec_t dist, vec_t eps } sides[i] = sides[0]; dists[i] = dists[0]; - - if (!counts[0]) - { - FreeWinding (in); + + if ( !counts[0] ) { + FreeWinding( in ); *inout = NULL; return; } - if (!counts[1]) - return; // inout stays the same + if ( !counts[1] ) { + return; // inout stays the same + + } + maxpts = in->numpoints + 4; // cant use counts[0]+2 because + // of fp grouping errors - maxpts = in->numpoints+4; // cant use counts[0]+2 because - // of fp grouping errors + f = AllocWinding( maxpts ); - f = AllocWinding (maxpts); - - for (i=0 ; inumpoints ; i++) + for ( i = 0 ; i < in->numpoints ; i++ ) { p1 = in->p[i]; - - if (sides[i] == SIDE_ON) - { - VectorCopy (p1, f->p[f->numpoints]); + + 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]); + + if ( sides[i] == SIDE_FRONT ) { + VectorCopy( p1, f->p[f->numpoints] ); f->numpoints++; } - if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i]) + 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) + } + + // 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) + } + else if ( normal[j] == -1 ) { mid[j] = -dist; - else - mid[j] = p1[j] + dot*(p2[j]-p1[j]); + } + else{ + mid[j] = p1[j] + dot * ( p2[j] - p1[j] ); + } } - - VectorCopy (mid, f->p[f->numpoints]); + + 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); + 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); + ================= + 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++) + ================= + 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] > MAX_WORLD_COORD || p1[j] < MIN_WORLD_COORD) - Error ("CheckFace: MAX_WORLD_COORD exceeded: %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 + for ( j = 0 ; j < 3 ; j++ ) + if ( p1[j] > MAX_WORLD_COORD || p1[j] < MIN_WORLD_COORD ) { + Error( "CheckFace: MAX_WORLD_COORD exceeded: %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); + 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++) + + // all other points must be on front side + for ( j = 0 ; j < w->numpoints ; j++ ) { - if (j == i) + if ( j == i ) { continue; - d = DotProduct (w->p[j], edgenormal); - if (d > edgedist) - Error ("CheckWinding: non-convex"); + } + 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; + ============ + 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++) + for ( i = 0 ; i < w->numpoints ; i++ ) { - d = DotProduct (w->p[i], normal) - dist; - if (d < -ON_EPSILON) - { - if (front) + 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) + if ( d > ON_EPSILON ) { + if ( back ) { return SIDE_CROSS; + } front = qtrue; continue; } } - if (back) + if ( back ) { return SIDE_BACK; - if (front) + } + 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; + ================= + 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) ); + numHullPoints = ( *hull )->numpoints; + memcpy( hullPoints, ( *hull )->p, numHullPoints * sizeof( vec3_t ) ); for ( i = 0 ; i < w->numpoints ; i++ ) { p = w->p[i]; @@ -1060,7 +1100,8 @@ void AddWindingToConvexHull( winding_t *w, winding_t **hull, vec3_t normal ) { } if ( d >= -ON_EPSILON ) { hullSide[j] = qtrue; - } else { + } + else { hullSide[j] = qfalse; } } @@ -1072,7 +1113,7 @@ void AddWindingToConvexHull( winding_t *w, winding_t **hull, vec3_t normal ) { // find the back side to front side transition for ( j = 0 ; j < numHullPoints ; j++ ) { - if ( !hullSide[ j % numHullPoints ] && hullSide[ (j + 1) % numHullPoints ] ) { + if ( !hullSide[ j % numHullPoints ] && hullSide[ ( j + 1 ) % numHullPoints ] ) { break; } } @@ -1085,25 +1126,23 @@ void AddWindingToConvexHull( winding_t *w, winding_t **hull, vec3_t normal ) { numNew = 1; // copy over all points that aren't double fronts - j = (j+1)%numHullPoints; + j = ( j + 1 ) % numHullPoints; for ( k = 0 ; k < numHullPoints ; k++ ) { - if ( hullSide[ (j+k) % numHullPoints ] && hullSide[ (j+k+1) % numHullPoints ] ) { + if ( hullSide[ ( j + k ) % numHullPoints ] && hullSide[ ( j + k + 1 ) % numHullPoints ] ) { continue; } - copy = hullPoints[ (j+k+1) % numHullPoints ]; + copy = hullPoints[ ( j + k + 1 ) % numHullPoints ]; VectorCopy( copy, newHullPoints[numNew] ); numNew++; } numHullPoints = numNew; - memcpy( hullPoints, newHullPoints, numHullPoints * sizeof(vec3_t) ); + 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) ); + memcpy( w->p, hullPoints, numHullPoints * sizeof( vec3_t ) ); } - -