From 39ed87570bdb2f86969d4be821c94b722dc71179 Mon Sep 17 00:00:00 2001 From: Joe Ludwig Date: Wed, 26 Jun 2013 15:22:04 -0700 Subject: First version of the SOurce SDK 2013 --- mp/src/utils/common/polylib.cpp | 915 ++++++++++++++++++++++++++++++++++++++++ 1 file changed, 915 insertions(+) create mode 100644 mp/src/utils/common/polylib.cpp (limited to 'mp/src/utils/common/polylib.cpp') diff --git a/mp/src/utils/common/polylib.cpp b/mp/src/utils/common/polylib.cpp new file mode 100644 index 00000000..36690a27 --- /dev/null +++ b/mp/src/utils/common/polylib.cpp @@ -0,0 +1,915 @@ +//========= Copyright Valve Corporation, All rights reserved. ============// +// +// Purpose: +// +// $Workfile: $ +// $Date: $ +// $NoKeywords: $ +//=============================================================================// + +#include "cmdlib.h" +#include "mathlib/mathlib.h" +#include "polylib.h" +#include "worldsize.h" +#include "threads.h" +#include "tier0/dbg.h" + +// doesn't seem to need to be here? -- in threads.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; + +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]); +} + +winding_t *winding_pool[MAX_POINTS_ON_WINDING+4]; + +/* +============= +AllocWinding +============= +*/ +winding_t *AllocWinding (int points) +{ + winding_t *w; + + 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; + } + ThreadLock(); + if (winding_pool[points]) + { + w = winding_pool[points]; + winding_pool[points] = w->next; + } + else + { + w = (winding_t *)malloc(sizeof(*w)); + w->p = (Vector *)calloc( points, sizeof(Vector) ); + } + ThreadUnlock(); + w->numpoints = 0; // None are occupied yet even though allocated. + w->maxpoints = points; + w->next = NULL; + return w; +} + +void FreeWinding (winding_t *w) +{ + if (w->numpoints == 0xdeaddead) + Error ("FreeWinding: freed a freed winding"); + + ThreadLock(); + w->numpoints = 0xdeaddead; // flag as freed + w->next = winding_pool[w->maxpoints]; + winding_pool[w->maxpoints] = w; + ThreadUnlock(); +} + +/* +============ +RemoveColinearPoints +============ +*/ +int c_removed; + +void RemoveColinearPoints (winding_t *w) +{ + int i, j, k; + Vector v1, v2; + int nump; + Vector 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); + VectorNormalize(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, Vector &normal, vec_t *dist) +{ + Vector v1, v2; + + VectorSubtract (w->p[1], w->p[0], v1); + + // HACKHACK: Avoid potentially collinear verts + if ( w->numpoints > 3 ) + { + VectorSubtract (w->p[3], w->p[0], v2); + } + else + { + VectorSubtract (w->p[2], w->p[0], v2); + } + CrossProduct (v2, v1, normal); + VectorNormalize (normal); + *dist = DotProduct (w->p[0], normal); + +} + + +/* +============= +WindingArea +============= +*/ +vec_t WindingArea(winding_t *w) +{ + int i; + Vector 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 += VectorLength ( cross ); + } + return total * 0.5; +} + +void WindingBounds (winding_t *w, Vector &mins, Vector &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, Vector ¢er) +{ + 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 +============= +*/ +vec_t WindingAreaAndBalancePoint( winding_t *w, Vector ¢er ) +{ + int i; + Vector d1, d2, cross; + vec_t total; + + VectorCopy (vec3_origin, center); + if ( !w ) + return 0.0f; + + 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); + float area = VectorLength ( cross ); + total += area; + + // center of triangle, weighed by area + VectorMA( center, area / 3.0, w->p[i-1], center ); + VectorMA( center, area / 3.0, w->p[i], center ); + VectorMA( center, area / 3.0, w->p[0], center ); + } + if (total) + { + VectorScale( center, 1.0 / total, center ); + } + return total * 0.5; +} + +/* +================= +BaseWindingForPlane +================= +*/ +winding_t *BaseWindingForPlane (const Vector &normal, vec_t dist) +{ + int i, x; + vec_t max, v; + Vector org, vright, vup; + winding_t *w; + +// find the major axis + + max = -1; + 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); + + VectorScale (normal, dist, org); + + CrossProduct (vup, normal, vright); + + VectorScale (vup, (MAX_COORD_INTEGER*4), vup); + VectorScale (vright, (MAX_COORD_INTEGER*4), 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); + c->numpoints = w->numpoints; + size = w->numpoints*sizeof(w->p[0]); + memcpy (c->p, w->p, 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; +} + + +// BUGBUG: Hunt this down - it's causing CSG errors +#pragma optimize("g", off) +/* +============= +ClipWindingEpsilon +============= +*/ + +void ClipWindingEpsilon (winding_t *in, const Vector &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]; + vec_t dot; + int i, j; + Vector mid = vec3_origin; + 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++) + { + Vector& 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 + Vector& 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"); +} +#pragma optimize("", on) + + +// NOTE: This is identical to ClipWindingEpsilon, but it does a pre/post translation to improve precision +void ClipWindingEpsilon_Offset( winding_t *in, const Vector &normal, vec_t dist, vec_t epsilon, winding_t **front, winding_t **back, const Vector &offset ) +{ + TranslateWinding( in, offset ); + ClipWindingEpsilon( in, normal, dist+DotProduct(offset,normal), epsilon, front, back ); + TranslateWinding( in, -offset ); + if ( front && *front ) + { + TranslateWinding( *front, -offset ); + } + if ( back && *back ) + { + TranslateWinding( *back, -offset ); + } +} + +void ClassifyWindingEpsilon_Offset( winding_t *in, const Vector &normal, vec_t dist, vec_t epsilon, winding_t **front, winding_t **back, winding_t **on, const Vector &offset) +{ + TranslateWinding( in, offset ); + ClassifyWindingEpsilon( in, normal, dist+DotProduct(offset,normal), epsilon, front, back, on ); + TranslateWinding( in, -offset ); + if ( front && *front ) + { + TranslateWinding( *front, -offset ); + } + if ( back && *back ) + { + TranslateWinding( *back, -offset ); + } + if ( on && *on ) + { + TranslateWinding( *on, -offset ); + } +} + +/* +============= +ClassifyWindingEpsilon +============= +*/ +// This version returns the winding as "on" if all verts lie in the plane +void ClassifyWindingEpsilon( winding_t *in, const Vector &normal, vec_t dist, + vec_t epsilon, winding_t **front, winding_t **back, winding_t **on) +{ + vec_t dists[MAX_POINTS_ON_WINDING+4]; + int sides[MAX_POINTS_ON_WINDING+4]; + int counts[3]; + vec_t dot; + int i, j; + Vector mid = vec3_origin; + 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 = *on = NULL; + + if ( !counts[0] && !counts[1] ) + { + *on = CopyWinding(in); + return; + } + + 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++) + { + Vector& 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 + Vector& 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, const Vector &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]; + vec_t dot; + int i, j; + Vector mid = vec3_origin; + 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++) + { + Vector& 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 + Vector& 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, const Vector &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 d, edgedist; + Vector 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++) + { + Vector& p1 = w->p[i]; + + for (j=0 ; j<3 ; j++) + { + if (p1[j] > MAX_COORD_INTEGER || p1[j] < MIN_COORD_INTEGER) + Error ("CheckFace: out of 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 + Vector& p2 = w->p[j]; + VectorSubtract (p2, p1, dir); + + if (VectorLength (dir) < ON_EPSILON) + Error ("CheckWinding: degenerate edge"); + + CrossProduct (facenormal, dir, edgenormal); + VectorNormalize (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, const Vector &normal, vec_t dist) +{ + qboolean front, back; + int i; + vec_t d; + + front = false; + back = false; + for (i=0 ; inumpoints ; 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; +} + + +//----------------------------------------------------------------------------- +// Purpose: 2d point inside of winding test (assumes the point resides in the +// winding plane) +//----------------------------------------------------------------------------- +bool PointInWinding( const Vector &pt, winding_t *pWinding ) +{ + if( !pWinding ) + return false; + +#if 0 + // + // NOTE: this will be a quicker way to calculate this, however I don't + // know the trick off hand (post dot product tests??) + // TODO: look in graphics gems!!!! (cab) + // + + Vector edge1, edge2; + for( int ndxPt = 0; ndxPt < pWinding->numpoints; ndxPt++ ) + { + edge1 = pWinding->p[ndxPt] - pt; + edge2 = pWinding->p[(ndxPt+1)%pWinding->numpoints] - pt; + + VectorNormalize( edge1 ); + VectorNormalize( edge2 ); + + if( edge2.Dot( edge1 ) < 0.0f ) + return false; + } + + return true; + +#else + Vector edge, toPt, cross, testCross; + + // + // get the first normal to test + // + toPt = pt - pWinding->p[0]; + edge = pWinding->p[1] - pWinding->p[0]; + testCross = edge.Cross( toPt ); + VectorNormalize( testCross ); + + for( int ndxPt = 1; ndxPt < pWinding->numpoints; ndxPt++ ) + { + toPt = pt - pWinding->p[ndxPt]; + edge = pWinding->p[(ndxPt+1)%pWinding->numpoints] - pWinding->p[ndxPt]; + cross = edge.Cross( toPt ); + VectorNormalize( cross ); + + if( cross.Dot( testCross ) < 0.0f ) + return false; + } + + return true; +#endif +} + +void TranslateWinding( winding_t *pWinding, const Vector &offset ) +{ + for ( int i = 0; i < pWinding->numpoints; i++ ) + { + pWinding->p[i] += offset; + } +} -- cgit v1.2.3