2 Copyright (C) 1999-2007 id Software, Inc. and contributors.
\r
3 For a list of contributors, see the accompanying CONTRIBUTORS file.
\r
5 This file is part of GtkRadiant.
\r
7 GtkRadiant is free software; you can redistribute it and/or modify
\r
8 it under the terms of the GNU General Public License as published by
\r
9 the Free Software Foundation; either version 2 of the License, or
\r
10 (at your option) any later version.
\r
12 GtkRadiant is distributed in the hope that it will be useful,
\r
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
\r
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
\r
15 GNU General Public License for more details.
\r
17 You should have received a copy of the GNU General Public License
\r
18 along with GtkRadiant; if not, write to the Free Software
\r
19 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
\r
24 #include "mathlib.h"
\r
26 #include "polylib.h"
\r
30 extern int numthreads;
\r
32 // counters are only bumped when running single threaded,
\r
33 // because they are an awefull coherence problem
\r
34 int c_active_windings;
\r
35 int c_peak_windings;
\r
36 int c_winding_allocs;
\r
37 int c_winding_points;
\r
39 #define BOGUS_RANGE WORLD_SIZE
\r
41 void pw(winding_t *w)
\r
44 for (i=0 ; i<w->numpoints ; i++)
\r
45 Sys_Printf ("(%5.1f, %5.1f, %5.1f)\n",w->p[i][0], w->p[i][1],w->p[i][2]);
\r
54 winding_t *AllocWinding (int points)
\r
59 if (points >= MAX_POINTS_ON_WINDING)
\r
60 Error ("AllocWinding failed: MAX_POINTS_ON_WINDING exceeded");
\r
62 if (numthreads == 1)
\r
65 c_winding_points += points;
\r
66 c_active_windings++;
\r
67 if (c_active_windings > c_peak_windings)
\r
68 c_peak_windings = c_active_windings;
\r
70 s = sizeof(vec_t)*3*points + sizeof(int);
\r
71 w = safe_malloc (s);
\r
76 void FreeWinding (winding_t *w)
\r
78 if (*(unsigned *)w == 0xdeaddead)
\r
79 Error ("FreeWinding: freed a freed winding");
\r
80 *(unsigned *)w = 0xdeaddead;
\r
82 if (numthreads == 1)
\r
83 c_active_windings--;
\r
89 RemoveColinearPoints
\r
94 void RemoveColinearPoints (winding_t *w)
\r
99 vec3_t p[MAX_POINTS_ON_WINDING];
\r
102 for (i=0 ; i<w->numpoints ; i++)
\r
104 j = (i+1)%w->numpoints;
\r
105 k = (i+w->numpoints-1)%w->numpoints;
\r
106 VectorSubtract (w->p[j], w->p[i], v1);
\r
107 VectorSubtract (w->p[i], w->p[k], v2);
\r
108 VectorNormalize(v1,v1);
\r
109 VectorNormalize(v2,v2);
\r
110 if (DotProduct(v1, v2) < 0.999)
\r
112 VectorCopy (w->p[i], p[nump]);
\r
117 if (nump == w->numpoints)
\r
120 if (numthreads == 1)
\r
121 c_removed += w->numpoints - nump;
\r
122 w->numpoints = nump;
\r
123 memcpy (w->p, p, nump*sizeof(p[0]));
\r
131 void WindingPlane (winding_t *w, vec3_t normal, vec_t *dist)
\r
135 VectorSubtract (w->p[1], w->p[0], v1);
\r
136 VectorSubtract (w->p[2], w->p[0], v2);
\r
137 CrossProduct (v2, v1, normal);
\r
138 VectorNormalize (normal, normal);
\r
139 *dist = DotProduct (w->p[0], normal);
\r
148 vec_t WindingArea (winding_t *w)
\r
151 vec3_t d1, d2, cross;
\r
155 for (i=2 ; i<w->numpoints ; i++)
\r
157 VectorSubtract (w->p[i-1], w->p[0], d1);
\r
158 VectorSubtract (w->p[i], w->p[0], d2);
\r
159 CrossProduct (d1, d2, cross);
\r
160 total += 0.5 * VectorLength ( cross );
\r
165 void WindingBounds (winding_t *w, vec3_t mins, vec3_t maxs)
\r
170 mins[0] = mins[1] = mins[2] = 99999;
\r
171 maxs[0] = maxs[1] = maxs[2] = -99999;
\r
173 for (i=0 ; i<w->numpoints ; i++)
\r
175 for (j=0 ; j<3 ; j++)
\r
191 void WindingCenter (winding_t *w, vec3_t center)
\r
196 VectorCopy (vec3_origin, center);
\r
197 for (i=0 ; i<w->numpoints ; i++)
\r
198 VectorAdd (w->p[i], center, center);
\r
200 scale = 1.0/w->numpoints;
\r
201 VectorScale (center, scale, center);
\r
206 BaseWindingForPlane
\r
209 winding_t *BaseWindingForPlane (vec3_t normal, vec_t dist)
\r
213 vec3_t org, vright, vup;
\r
216 // find the major axis
\r
218 max = -BOGUS_RANGE;
\r
220 for (i=0 ; i<3; i++)
\r
222 v = fabs(normal[i]);
\r
230 Error ("BaseWindingForPlane: no axis found");
\r
232 VectorCopy (vec3_origin, vup);
\r
244 v = DotProduct (vup, normal);
\r
245 VectorMA (vup, -v, normal, vup);
\r
246 VectorNormalize (vup, vup);
\r
248 VectorScale (normal, dist, org);
\r
250 CrossProduct (vup, normal, vright);
\r
252 VectorScale (vup, MAX_WORLD_COORD, vup);
\r
253 VectorScale (vright, MAX_WORLD_COORD, vright);
\r
255 // project a really big axis aligned box onto the plane
\r
256 w = AllocWinding (4);
\r
258 VectorSubtract (org, vright, w->p[0]);
\r
259 VectorAdd (w->p[0], vup, w->p[0]);
\r
261 VectorAdd (org, vright, w->p[1]);
\r
262 VectorAdd (w->p[1], vup, w->p[1]);
\r
264 VectorAdd (org, vright, w->p[2]);
\r
265 VectorSubtract (w->p[2], vup, w->p[2]);
\r
267 VectorSubtract (org, vright, w->p[3]);
\r
268 VectorSubtract (w->p[3], vup, w->p[3]);
\r
280 winding_t *CopyWinding (winding_t *w)
\r
285 c = AllocWinding (w->numpoints);
\r
286 size = (int)((winding_t *)0)->p[w->numpoints];
\r
287 memcpy (c, w, size);
\r
296 winding_t *ReverseWinding (winding_t *w)
\r
301 c = AllocWinding (w->numpoints);
\r
302 for (i=0 ; i<w->numpoints ; i++)
\r
304 VectorCopy (w->p[w->numpoints-1-i], c->p[i]);
\r
306 c->numpoints = w->numpoints;
\r
316 void ClipWindingEpsilon (winding_t *in, vec3_t normal, vec_t dist,
\r
317 vec_t epsilon, winding_t **front, winding_t **back)
\r
319 vec_t dists[MAX_POINTS_ON_WINDING+4];
\r
320 int sides[MAX_POINTS_ON_WINDING+4];
\r
322 static vec_t dot; // VC 4.2 optimizer bug if not static
\r
329 counts[0] = counts[1] = counts[2] = 0;
\r
331 // determine sides for each point
\r
332 for (i=0 ; i<in->numpoints ; i++)
\r
335 dot = DotProduct (in->p[i], normal);
\r
339 sides[i] = SIDE_FRONT;
\r
340 else if (dot < -epsilon)
\r
341 sides[i] = SIDE_BACK;
\r
344 sides[i] = SIDE_ON;
\r
346 counts[sides[i]]++;
\r
348 sides[i] = sides[0];
\r
349 dists[i] = dists[0];
\r
351 *front = *back = NULL;
\r
355 *back = CopyWinding (in);
\r
360 *front = CopyWinding (in);
\r
364 maxpts = in->numpoints+4; // cant use counts[0]+2 because
\r
365 // of fp grouping errors
\r
367 *front = f = AllocWinding (maxpts);
\r
368 *back = b = AllocWinding (maxpts);
\r
370 for (i=0 ; i<in->numpoints ; i++)
\r
374 if (sides[i] == SIDE_ON)
\r
376 VectorCopy (p1, f->p[f->numpoints]);
\r
378 VectorCopy (p1, b->p[b->numpoints]);
\r
383 if (sides[i] == SIDE_FRONT)
\r
385 VectorCopy (p1, f->p[f->numpoints]);
\r
388 if (sides[i] == SIDE_BACK)
\r
390 VectorCopy (p1, b->p[b->numpoints]);
\r
394 if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])
\r
397 // generate a split point
\r
398 p2 = in->p[(i+1)%in->numpoints];
\r
400 dot = dists[i] / (dists[i]-dists[i+1]);
\r
401 for (j=0 ; j<3 ; j++)
\r
402 { // avoid round off error when possible
\r
403 if (normal[j] == 1)
\r
405 else if (normal[j] == -1)
\r
408 mid[j] = p1[j] + dot*(p2[j]-p1[j]);
\r
411 VectorCopy (mid, f->p[f->numpoints]);
\r
413 VectorCopy (mid, b->p[b->numpoints]);
\r
417 if (f->numpoints > maxpts || b->numpoints > maxpts)
\r
418 Error ("ClipWinding: points exceeded estimate");
\r
419 if (f->numpoints > MAX_POINTS_ON_WINDING || b->numpoints > MAX_POINTS_ON_WINDING)
\r
420 Error ("ClipWinding: MAX_POINTS_ON_WINDING");
\r
429 void ChopWindingInPlace (winding_t **inout, vec3_t normal, vec_t dist, vec_t epsilon)
\r
432 vec_t dists[MAX_POINTS_ON_WINDING+4];
\r
433 int sides[MAX_POINTS_ON_WINDING+4];
\r
435 static vec_t dot; // VC 4.2 optimizer bug if not static
\r
443 counts[0] = counts[1] = counts[2] = 0;
\r
445 // determine sides for each point
\r
446 for (i=0 ; i<in->numpoints ; i++)
\r
448 dot = DotProduct (in->p[i], normal);
\r
452 sides[i] = SIDE_FRONT;
\r
453 else if (dot < -epsilon)
\r
454 sides[i] = SIDE_BACK;
\r
457 sides[i] = SIDE_ON;
\r
459 counts[sides[i]]++;
\r
461 sides[i] = sides[0];
\r
462 dists[i] = dists[0];
\r
471 return; // inout stays the same
\r
473 maxpts = in->numpoints+4; // cant use counts[0]+2 because
\r
474 // of fp grouping errors
\r
476 f = AllocWinding (maxpts);
\r
478 for (i=0 ; i<in->numpoints ; i++)
\r
482 if (sides[i] == SIDE_ON)
\r
484 VectorCopy (p1, f->p[f->numpoints]);
\r
489 if (sides[i] == SIDE_FRONT)
\r
491 VectorCopy (p1, f->p[f->numpoints]);
\r
495 if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])
\r
498 // generate a split point
\r
499 p2 = in->p[(i+1)%in->numpoints];
\r
501 dot = dists[i] / (dists[i]-dists[i+1]);
\r
502 for (j=0 ; j<3 ; j++)
\r
503 { // avoid round off error when possible
\r
504 if (normal[j] == 1)
\r
506 else if (normal[j] == -1)
\r
509 mid[j] = p1[j] + dot*(p2[j]-p1[j]);
\r
512 VectorCopy (mid, f->p[f->numpoints]);
\r
516 if (f->numpoints > maxpts)
\r
517 Error ("ClipWinding: points exceeded estimate");
\r
518 if (f->numpoints > MAX_POINTS_ON_WINDING)
\r
519 Error ("ClipWinding: MAX_POINTS_ON_WINDING");
\r
530 Returns the fragment of in that is on the front side
\r
531 of the cliping plane. The original is freed.
\r
534 winding_t *ChopWinding (winding_t *in, vec3_t normal, vec_t dist)
\r
538 ClipWindingEpsilon (in, normal, dist, ON_EPSILON, &f, &b);
\r
552 void CheckWinding (winding_t *w)
\r
557 vec3_t dir, edgenormal, facenormal;
\r
561 if (w->numpoints < 3)
\r
562 Error ("CheckWinding: %i points",w->numpoints);
\r
564 area = WindingArea(w);
\r
566 Error ("CheckWinding: %f area", area);
\r
568 WindingPlane (w, facenormal, &facedist);
\r
570 for (i=0 ; i<w->numpoints ; i++)
\r
574 for (j=0 ; j<3 ; j++)
\r
575 if (p1[j] > MAX_WORLD_COORD || p1[j] < MIN_WORLD_COORD)
\r
576 Error ("CheckFace: MAX_WORLD_COORD exceeded: %f",p1[j]);
\r
578 j = i+1 == w->numpoints ? 0 : i+1;
\r
580 // check the point is on the face plane
\r
581 d = DotProduct (p1, facenormal) - facedist;
\r
582 if (d < -ON_EPSILON || d > ON_EPSILON)
\r
583 Error ("CheckWinding: point off plane");
\r
585 // check the edge isnt degenerate
\r
587 VectorSubtract (p2, p1, dir);
\r
589 if (VectorLength (dir) < ON_EPSILON)
\r
590 Error ("CheckWinding: degenerate edge");
\r
592 CrossProduct (facenormal, dir, edgenormal);
\r
593 VectorNormalize (edgenormal, edgenormal);
\r
594 edgedist = DotProduct (p1, edgenormal);
\r
595 edgedist += ON_EPSILON;
\r
597 // all other points must be on front side
\r
598 for (j=0 ; j<w->numpoints ; j++)
\r
602 d = DotProduct (w->p[j], edgenormal);
\r
604 Error ("CheckWinding: non-convex");
\r
615 int WindingOnPlaneSide (winding_t *w, vec3_t normal, vec_t dist)
\r
617 qboolean front, back;
\r
623 for (i=0 ; i<w->numpoints ; i++)
\r
625 d = DotProduct (w->p[i], normal) - dist;
\r
626 if (d < -ON_EPSILON)
\r
633 if (d > ON_EPSILON)
\r
652 AddWindingToConvexHull
\r
654 Both w and *hull are on the same plane
\r
657 #define MAX_HULL_POINTS 128
\r
658 void AddWindingToConvexHull( winding_t *w, winding_t **hull, vec3_t normal ) {
\r
663 int numHullPoints, numNew;
\r
664 vec3_t hullPoints[MAX_HULL_POINTS];
\r
665 vec3_t newHullPoints[MAX_HULL_POINTS];
\r
666 vec3_t hullDirs[MAX_HULL_POINTS];
\r
667 qboolean hullSide[MAX_HULL_POINTS];
\r
671 *hull = CopyWinding( w );
\r
675 numHullPoints = (*hull)->numpoints;
\r
676 memcpy( hullPoints, (*hull)->p, numHullPoints * sizeof(vec3_t) );
\r
678 for ( i = 0 ; i < w->numpoints ; i++ ) {
\r
681 // calculate hull side vectors
\r
682 for ( j = 0 ; j < numHullPoints ; j++ ) {
\r
683 k = ( j + 1 ) % numHullPoints;
\r
685 VectorSubtract( hullPoints[k], hullPoints[j], dir );
\r
686 VectorNormalize( dir, dir );
\r
687 CrossProduct( normal, dir, hullDirs[j] );
\r
691 for ( j = 0 ; j < numHullPoints ; j++ ) {
\r
692 VectorSubtract( p, hullPoints[j], dir );
\r
693 d = DotProduct( dir, hullDirs[j] );
\r
694 if ( d >= ON_EPSILON ) {
\r
697 if ( d >= -ON_EPSILON ) {
\r
698 hullSide[j] = qtrue;
\r
700 hullSide[j] = qfalse;
\r
704 // if the point is effectively inside, do nothing
\r
709 // find the back side to front side transition
\r
710 for ( j = 0 ; j < numHullPoints ; j++ ) {
\r
711 if ( !hullSide[ j % numHullPoints ] && hullSide[ (j + 1) % numHullPoints ] ) {
\r
715 if ( j == numHullPoints ) {
\r
719 // insert the point here
\r
720 VectorCopy( p, newHullPoints[0] );
\r
723 // copy over all points that aren't double fronts
\r
724 j = (j+1)%numHullPoints;
\r
725 for ( k = 0 ; k < numHullPoints ; k++ ) {
\r
726 if ( hullSide[ (j+k) % numHullPoints ] && hullSide[ (j+k+1) % numHullPoints ] ) {
\r
729 copy = hullPoints[ (j+k+1) % numHullPoints ];
\r
730 VectorCopy( copy, newHullPoints[numNew] );
\r
734 numHullPoints = numNew;
\r
735 memcpy( hullPoints, newHullPoints, numHullPoints * sizeof(vec3_t) );
\r
738 FreeWinding( *hull );
\r
739 w = AllocWinding( numHullPoints );
\r
740 w->numpoints = numHullPoints;
\r
742 memcpy( w->p, hullPoints, numHullPoints * sizeof(vec3_t) );
\r