2 Copyright (C) 1999-2007 id Software, Inc. and contributors.
3 For a list of contributors, see the accompanying CONTRIBUTORS file.
5 This file is part of GtkRadiant.
7 GtkRadiant is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2 of the License, or
10 (at your option) any later version.
12 GtkRadiant is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GtkRadiant; if not, write to the Free Software
19 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
28 extern int numthreads;
30 // counters are only bumped when running single threaded,
31 // because they are an awefull coherence problem
32 int c_active_windings;
37 #define BOGUS_RANGE 8192
42 for (i=0 ; i<w->numpoints ; i++)
43 printf ("(%5.1f, %5.1f, %5.1f)\n",w->p[i][0], w->p[i][1],w->p[i][2]);
52 winding_t *AllocWinding (int points)
60 c_winding_points += points;
62 if (c_active_windings > c_peak_windings)
63 c_peak_windings = c_active_windings;
65 s = sizeof(vec_t)*3*points + sizeof(int);
71 void FreeWinding (winding_t *w)
73 if (*(unsigned *)w == 0xdeaddead)
74 Error ("FreeWinding: freed a freed winding");
75 *(unsigned *)w = 0xdeaddead;
89 void RemoveColinearPoints (winding_t *w)
94 vec3_t p[MAX_POINTS_ON_WINDING];
97 for (i=0 ; i<w->numpoints ; i++)
99 j = (i+1)%w->numpoints;
100 k = (i+w->numpoints-1)%w->numpoints;
101 VectorSubtract (w->p[j], w->p[i], v1);
102 VectorSubtract (w->p[i], w->p[k], v2);
103 VectorNormalize(v1,v1);
104 VectorNormalize(v2,v2);
105 if (DotProduct(v1, v2) < 0.999)
107 VectorCopy (w->p[i], p[nump]);
112 if (nump == w->numpoints)
116 c_removed += w->numpoints - nump;
118 memcpy (w->p, p, nump*sizeof(p[0]));
126 void WindingPlane (winding_t *w, vec3_t normal, vec_t *dist)
130 VectorSubtract (w->p[1], w->p[0], v1);
131 VectorSubtract (w->p[2], w->p[0], v2);
132 CrossProduct (v2, v1, normal);
133 VectorNormalize (normal, normal);
134 *dist = DotProduct (w->p[0], normal);
143 vec_t WindingArea (winding_t *w)
146 vec3_t d1, d2, cross;
150 for (i=2 ; i<w->numpoints ; i++)
152 VectorSubtract (w->p[i-1], w->p[0], d1);
153 VectorSubtract (w->p[i], w->p[0], d2);
154 CrossProduct (d1, d2, cross);
155 total += 0.5 * VectorLength ( cross );
160 void WindingBounds (winding_t *w, vec3_t mins, vec3_t maxs)
165 mins[0] = mins[1] = mins[2] = 99999;
166 maxs[0] = maxs[1] = maxs[2] = -99999;
168 for (i=0 ; i<w->numpoints ; i++)
170 for (j=0 ; j<3 ; j++)
186 void WindingCenter (winding_t *w, vec3_t center)
191 VectorCopy (vec3_origin, center);
192 for (i=0 ; i<w->numpoints ; i++)
193 VectorAdd (w->p[i], center, center);
195 scale = 1.0/w->numpoints;
196 VectorScale (center, scale, center);
204 winding_t *BaseWindingForPlane (vec3_t normal, vec_t dist)
208 vec3_t org, vright, vup;
211 // find the major axis
225 Error ("BaseWindingForPlane: no axis found");
227 VectorCopy (vec3_origin, vup);
239 v = DotProduct (vup, normal);
240 VectorMA (vup, -v, normal, vup);
241 VectorNormalize (vup, vup);
243 VectorScale (normal, dist, org);
245 CrossProduct (vup, normal, vright);
247 VectorScale (vup, 8192, vup);
248 VectorScale (vright, 8192, vright);
250 // project a really big axis aligned box onto the plane
251 w = AllocWinding (4);
253 VectorSubtract (org, vright, w->p[0]);
254 VectorAdd (w->p[0], vup, w->p[0]);
256 VectorAdd (org, vright, w->p[1]);
257 VectorAdd (w->p[1], vup, w->p[1]);
259 VectorAdd (org, vright, w->p[2]);
260 VectorSubtract (w->p[2], vup, w->p[2]);
262 VectorSubtract (org, vright, w->p[3]);
263 VectorSubtract (w->p[3], vup, w->p[3]);
275 winding_t *CopyWinding (winding_t *w)
280 c = AllocWinding (w->numpoints);
281 size = (int)((winding_t *)0)->p[w->numpoints];
291 winding_t *ReverseWinding (winding_t *w)
296 c = AllocWinding (w->numpoints);
297 for (i=0 ; i<w->numpoints ; i++)
299 VectorCopy (w->p[w->numpoints-1-i], c->p[i]);
301 c->numpoints = w->numpoints;
311 void ClipWindingEpsilon (winding_t *in, vec3_t normal, vec_t dist,
312 vec_t epsilon, winding_t **front, winding_t **back)
314 vec_t dists[MAX_POINTS_ON_WINDING+4];
315 int sides[MAX_POINTS_ON_WINDING+4];
317 static vec_t dot; // VC 4.2 optimizer bug if not static
324 counts[0] = counts[1] = counts[2] = 0;
326 // determine sides for each point
327 for (i=0 ; i<in->numpoints ; i++)
329 dot = DotProduct (in->p[i], normal);
333 sides[i] = SIDE_FRONT;
334 else if (dot < -epsilon)
335 sides[i] = SIDE_BACK;
345 *front = *back = NULL;
349 *back = CopyWinding (in);
354 *front = CopyWinding (in);
358 maxpts = in->numpoints+4; // cant use counts[0]+2 because
359 // of fp grouping errors
361 *front = f = AllocWinding (maxpts);
362 *back = b = AllocWinding (maxpts);
364 for (i=0 ; i<in->numpoints ; i++)
368 if (sides[i] == SIDE_ON)
370 VectorCopy (p1, f->p[f->numpoints]);
372 VectorCopy (p1, b->p[b->numpoints]);
377 if (sides[i] == SIDE_FRONT)
379 VectorCopy (p1, f->p[f->numpoints]);
382 if (sides[i] == SIDE_BACK)
384 VectorCopy (p1, b->p[b->numpoints]);
388 if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])
391 // generate a split point
392 p2 = in->p[(i+1)%in->numpoints];
394 dot = dists[i] / (dists[i]-dists[i+1]);
395 for (j=0 ; j<3 ; j++)
396 { // avoid round off error when possible
399 else if (normal[j] == -1)
402 mid[j] = p1[j] + dot*(p2[j]-p1[j]);
405 VectorCopy (mid, f->p[f->numpoints]);
407 VectorCopy (mid, b->p[b->numpoints]);
411 if (f->numpoints > maxpts || b->numpoints > maxpts)
412 Error ("ClipWinding: points exceeded estimate");
413 if (f->numpoints > MAX_POINTS_ON_WINDING || b->numpoints > MAX_POINTS_ON_WINDING)
414 Error ("ClipWinding: MAX_POINTS_ON_WINDING");
423 void ChopWindingInPlace (winding_t **inout, vec3_t normal, vec_t dist, vec_t epsilon)
426 vec_t dists[MAX_POINTS_ON_WINDING+4];
427 int sides[MAX_POINTS_ON_WINDING+4];
429 static vec_t dot; // VC 4.2 optimizer bug if not static
437 counts[0] = counts[1] = counts[2] = 0;
439 // determine sides for each point
440 for (i=0 ; i<in->numpoints ; i++)
442 dot = DotProduct (in->p[i], normal);
446 sides[i] = SIDE_FRONT;
447 else if (dot < -epsilon)
448 sides[i] = SIDE_BACK;
465 return; // inout stays the same
467 maxpts = in->numpoints+4; // cant use counts[0]+2 because
468 // of fp grouping errors
470 f = AllocWinding (maxpts);
472 for (i=0 ; i<in->numpoints ; i++)
476 if (sides[i] == SIDE_ON)
478 VectorCopy (p1, f->p[f->numpoints]);
483 if (sides[i] == SIDE_FRONT)
485 VectorCopy (p1, f->p[f->numpoints]);
489 if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])
492 // generate a split point
493 p2 = in->p[(i+1)%in->numpoints];
495 dot = dists[i] / (dists[i]-dists[i+1]);
496 for (j=0 ; j<3 ; j++)
497 { // avoid round off error when possible
500 else if (normal[j] == -1)
503 mid[j] = p1[j] + dot*(p2[j]-p1[j]);
506 VectorCopy (mid, f->p[f->numpoints]);
510 if (f->numpoints > maxpts)
511 Error ("ClipWinding: points exceeded estimate");
512 if (f->numpoints > MAX_POINTS_ON_WINDING)
513 Error ("ClipWinding: MAX_POINTS_ON_WINDING");
524 Returns the fragment of in that is on the front side
525 of the cliping plane. The original is freed.
528 winding_t *ChopWinding (winding_t *in, vec3_t normal, vec_t dist)
532 ClipWindingEpsilon (in, normal, dist, ON_EPSILON, &f, &b);
546 void CheckWinding (winding_t *w)
551 vec3_t dir, edgenormal, facenormal;
555 if (w->numpoints < 3)
556 Error ("CheckWinding: %i points",w->numpoints);
558 area = WindingArea(w);
560 Error ("CheckWinding: %f area", area);
562 WindingPlane (w, facenormal, &facedist);
564 for (i=0 ; i<w->numpoints ; i++)
568 for (j=0 ; j<3 ; j++)
569 if (p1[j] > BOGUS_RANGE || p1[j] < -BOGUS_RANGE)
570 Error ("CheckFace: BUGUS_RANGE: %f",p1[j]);
572 j = i+1 == w->numpoints ? 0 : i+1;
574 // check the point is on the face plane
575 d = DotProduct (p1, facenormal) - facedist;
576 if (d < -ON_EPSILON || d > ON_EPSILON)
577 Error ("CheckWinding: point off plane");
579 // check the edge isnt degenerate
581 VectorSubtract (p2, p1, dir);
583 if (VectorLength (dir) < ON_EPSILON)
584 Error ("CheckWinding: degenerate edge");
586 CrossProduct (facenormal, dir, edgenormal);
587 VectorNormalize (edgenormal, edgenormal);
588 edgedist = DotProduct (p1, edgenormal);
589 edgedist += ON_EPSILON;
591 // all other points must be on front side
592 for (j=0 ; j<w->numpoints ; j++)
596 d = DotProduct (w->p[j], edgenormal);
598 Error ("CheckWinding: non-convex");
609 int WindingOnPlaneSide (winding_t *w, vec3_t normal, vec_t dist)
611 qboolean front, back;
617 for (i=0 ; i<w->numpoints ; i++)
619 d = DotProduct (w->p[i], normal) - dist;