1 /*
2 ===========================================================================
3 Copyright (C) 1999-2005 Id Software, Inc.
4
5 This file is part of Quake III Arena source code.
6
7 Quake III Arena source code is free software; you can redistribute it
8 and/or modify it under the terms of the GNU General Public License as
9 published by the Free Software Foundation; either version 2 of the License,
10 or (at your option) any later version.
11
12 Quake III Arena source code is distributed in the hope that it will be
13 useful, 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.
16
17 You should have received a copy of the GNU General Public License
18 along with Quake III Arena source code; if not, write to the Free Software
19 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
20 ===========================================================================
21 */
22
23 // this is only used for visualization tools in cm_ debug functions
24
25
26 #include "cm_local.h"
27
28
29 // counters are only bumped when running single threaded,
30 // because they are an awful coherence problem
31 int c_active_windings;
32 int c_peak_windings;
33 int c_winding_allocs;
34 int c_winding_points;
35
pw(winding_t * w)36 void pw(winding_t *w)
37 {
38 int i;
39 for (i=0 ; i<w->numpoints ; i++)
40 printf ("(%5.1f, %5.1f, %5.1f)\n",w->p[i][0], w->p[i][1],w->p[i][2]);
41 }
42
43
44 /*
45 =============
46 AllocWinding
47 =============
48 */
AllocWinding(int points)49 winding_t *AllocWinding (int points)
50 {
51 winding_t *w;
52 int s;
53
54 c_winding_allocs++;
55 c_winding_points += points;
56 c_active_windings++;
57 if (c_active_windings > c_peak_windings)
58 c_peak_windings = c_active_windings;
59
60 s = sizeof(vec_t)*3*points + sizeof(int);
61 w = Z_Malloc (s);
62 Com_Memset (w, 0, s);
63 return w;
64 }
65
FreeWinding(winding_t * w)66 void FreeWinding (winding_t *w)
67 {
68 if (*(unsigned *)w == 0xdeaddead)
69 Com_Error (ERR_FATAL, "FreeWinding: freed a freed winding");
70 *(unsigned *)w = 0xdeaddead;
71
72 c_active_windings--;
73 Z_Free (w);
74 }
75
76 /*
77 ============
78 RemoveColinearPoints
79 ============
80 */
81 int c_removed;
82
RemoveColinearPoints(winding_t * w)83 void RemoveColinearPoints (winding_t *w)
84 {
85 int i, j, k;
86 vec3_t v1, v2;
87 int nump;
88 vec3_t p[MAX_POINTS_ON_WINDING];
89
90 nump = 0;
91 for (i=0 ; i<w->numpoints ; i++)
92 {
93 j = (i+1)%w->numpoints;
94 k = (i+w->numpoints-1)%w->numpoints;
95 VectorSubtract (w->p[j], w->p[i], v1);
96 VectorSubtract (w->p[i], w->p[k], v2);
97 VectorNormalize2(v1,v1);
98 VectorNormalize2(v2,v2);
99 if (DotProduct(v1, v2) < 0.999)
100 {
101 VectorCopy (w->p[i], p[nump]);
102 nump++;
103 }
104 }
105
106 if (nump == w->numpoints)
107 return;
108
109 c_removed += w->numpoints - nump;
110 w->numpoints = nump;
111 Com_Memcpy (w->p, p, nump*sizeof(p[0]));
112 }
113
114 /*
115 ============
116 WindingPlane
117 ============
118 */
WindingPlane(winding_t * w,vec3_t normal,vec_t * dist)119 void WindingPlane (winding_t *w, vec3_t normal, vec_t *dist)
120 {
121 vec3_t v1, v2;
122
123 VectorSubtract (w->p[1], w->p[0], v1);
124 VectorSubtract (w->p[2], w->p[0], v2);
125 CrossProduct (v2, v1, normal);
126 VectorNormalize2(normal, normal);
127 *dist = DotProduct (w->p[0], normal);
128
129 }
130
131 /*
132 =============
133 WindingArea
134 =============
135 */
WindingArea(winding_t * w)136 vec_t WindingArea (winding_t *w)
137 {
138 int i;
139 vec3_t d1, d2, cross;
140 vec_t total;
141
142 total = 0;
143 for (i=2 ; i<w->numpoints ; i++)
144 {
145 VectorSubtract (w->p[i-1], w->p[0], d1);
146 VectorSubtract (w->p[i], w->p[0], d2);
147 CrossProduct (d1, d2, cross);
148 total += 0.5 * VectorLength ( cross );
149 }
150 return total;
151 }
152
153 /*
154 =============
155 WindingBounds
156 =============
157 */
WindingBounds(winding_t * w,vec3_t mins,vec3_t maxs)158 void WindingBounds (winding_t *w, vec3_t mins, vec3_t maxs)
159 {
160 vec_t v;
161 int i,j;
162
163 mins[0] = mins[1] = mins[2] = MAX_MAP_BOUNDS;
164 maxs[0] = maxs[1] = maxs[2] = -MAX_MAP_BOUNDS;
165
166 for (i=0 ; i<w->numpoints ; i++)
167 {
168 for (j=0 ; j<3 ; j++)
169 {
170 v = w->p[i][j];
171 if (v < mins[j])
172 mins[j] = v;
173 if (v > maxs[j])
174 maxs[j] = v;
175 }
176 }
177 }
178
179 /*
180 =============
181 WindingCenter
182 =============
183 */
WindingCenter(winding_t * w,vec3_t center)184 void WindingCenter (winding_t *w, vec3_t center)
185 {
186 int i;
187 float scale;
188
189 VectorCopy (vec3_origin, center);
190 for (i=0 ; i<w->numpoints ; i++)
191 VectorAdd (w->p[i], center, center);
192
193 scale = 1.0/w->numpoints;
194 VectorScale (center, scale, center);
195 }
196
197 /*
198 =================
199 BaseWindingForPlane
200 =================
201 */
BaseWindingForPlane(vec3_t normal,vec_t dist)202 winding_t *BaseWindingForPlane (vec3_t normal, vec_t dist)
203 {
204 int i, x;
205 vec_t max, v;
206 vec3_t org, vright, vup;
207 winding_t *w;
208
209 // find the major axis
210
211 max = -MAX_MAP_BOUNDS;
212 x = -1;
213 for (i=0 ; i<3; i++)
214 {
215 v = fabs(normal[i]);
216 if (v > max)
217 {
218 x = i;
219 max = v;
220 }
221 }
222 if (x==-1)
223 Com_Error (ERR_DROP, "BaseWindingForPlane: no axis found");
224
225 VectorCopy (vec3_origin, vup);
226 switch (x)
227 {
228 case 0:
229 case 1:
230 vup[2] = 1;
231 break;
232 case 2:
233 vup[0] = 1;
234 break;
235 }
236
237 v = DotProduct (vup, normal);
238 VectorMA (vup, -v, normal, vup);
239 VectorNormalize2(vup, vup);
240
241 VectorScale (normal, dist, org);
242
243 CrossProduct (vup, normal, vright);
244
245 VectorScale (vup, MAX_MAP_BOUNDS, vup);
246 VectorScale (vright, MAX_MAP_BOUNDS, vright);
247
248 // project a really big axis aligned box onto the plane
249 w = AllocWinding (4);
250
251 VectorSubtract (org, vright, w->p[0]);
252 VectorAdd (w->p[0], vup, w->p[0]);
253
254 VectorAdd (org, vright, w->p[1]);
255 VectorAdd (w->p[1], vup, w->p[1]);
256
257 VectorAdd (org, vright, w->p[2]);
258 VectorSubtract (w->p[2], vup, w->p[2]);
259
260 VectorSubtract (org, vright, w->p[3]);
261 VectorSubtract (w->p[3], vup, w->p[3]);
262
263 w->numpoints = 4;
264
265 return w;
266 }
267
268 /*
269 ==================
270 CopyWinding
271 ==================
272 */
CopyWinding(winding_t * w)273 winding_t *CopyWinding (winding_t *w)
274 {
275 unsigned long size;
276 winding_t *c;
277
278 c = AllocWinding (w->numpoints);
279 size = (long)((winding_t *)0)->p[w->numpoints];
280 Com_Memcpy (c, w, size);
281 return c;
282 }
283
284 /*
285 ==================
286 ReverseWinding
287 ==================
288 */
ReverseWinding(winding_t * w)289 winding_t *ReverseWinding (winding_t *w)
290 {
291 int i;
292 winding_t *c;
293
294 c = AllocWinding (w->numpoints);
295 for (i=0 ; i<w->numpoints ; i++)
296 {
297 VectorCopy (w->p[w->numpoints-1-i], c->p[i]);
298 }
299 c->numpoints = w->numpoints;
300 return c;
301 }
302
303
304 /*
305 =============
306 ClipWindingEpsilon
307 =============
308 */
ClipWindingEpsilon(winding_t * in,vec3_t normal,vec_t dist,vec_t epsilon,winding_t ** front,winding_t ** back)309 void ClipWindingEpsilon (winding_t *in, vec3_t normal, vec_t dist,
310 vec_t epsilon, winding_t **front, winding_t **back)
311 {
312 vec_t dists[MAX_POINTS_ON_WINDING+4];
313 int sides[MAX_POINTS_ON_WINDING+4];
314 int counts[3];
315 static vec_t dot; // VC 4.2 optimizer bug if not static
316 int i, j;
317 vec_t *p1, *p2;
318 vec3_t mid;
319 winding_t *f, *b;
320 int maxpts;
321
322 counts[0] = counts[1] = counts[2] = 0;
323
324 // determine sides for each point
325 for (i=0 ; i<in->numpoints ; i++)
326 {
327 dot = DotProduct (in->p[i], normal);
328 dot -= dist;
329 dists[i] = dot;
330 if (dot > epsilon)
331 sides[i] = SIDE_FRONT;
332 else if (dot < -epsilon)
333 sides[i] = SIDE_BACK;
334 else
335 {
336 sides[i] = SIDE_ON;
337 }
338 counts[sides[i]]++;
339 }
340 sides[i] = sides[0];
341 dists[i] = dists[0];
342
343 *front = *back = NULL;
344
345 if (!counts[0])
346 {
347 *back = CopyWinding (in);
348 return;
349 }
350 if (!counts[1])
351 {
352 *front = CopyWinding (in);
353 return;
354 }
355
356 maxpts = in->numpoints+4; // cant use counts[0]+2 because
357 // of fp grouping errors
358
359 *front = f = AllocWinding (maxpts);
360 *back = b = AllocWinding (maxpts);
361
362 for (i=0 ; i<in->numpoints ; i++)
363 {
364 p1 = in->p[i];
365
366 if (sides[i] == SIDE_ON)
367 {
368 VectorCopy (p1, f->p[f->numpoints]);
369 f->numpoints++;
370 VectorCopy (p1, b->p[b->numpoints]);
371 b->numpoints++;
372 continue;
373 }
374
375 if (sides[i] == SIDE_FRONT)
376 {
377 VectorCopy (p1, f->p[f->numpoints]);
378 f->numpoints++;
379 }
380 if (sides[i] == SIDE_BACK)
381 {
382 VectorCopy (p1, b->p[b->numpoints]);
383 b->numpoints++;
384 }
385
386 if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])
387 continue;
388
389 // generate a split point
390 p2 = in->p[(i+1)%in->numpoints];
391
392 dot = dists[i] / (dists[i]-dists[i+1]);
393 for (j=0 ; j<3 ; j++)
394 { // avoid round off error when possible
395 if (normal[j] == 1)
396 mid[j] = dist;
397 else if (normal[j] == -1)
398 mid[j] = -dist;
399 else
400 mid[j] = p1[j] + dot*(p2[j]-p1[j]);
401 }
402
403 VectorCopy (mid, f->p[f->numpoints]);
404 f->numpoints++;
405 VectorCopy (mid, b->p[b->numpoints]);
406 b->numpoints++;
407 }
408
409 if (f->numpoints > maxpts || b->numpoints > maxpts)
410 Com_Error (ERR_DROP, "ClipWinding: points exceeded estimate");
411 if (f->numpoints > MAX_POINTS_ON_WINDING || b->numpoints > MAX_POINTS_ON_WINDING)
412 Com_Error (ERR_DROP, "ClipWinding: MAX_POINTS_ON_WINDING");
413 }
414
415
416 /*
417 =============
418 ChopWindingInPlace
419 =============
420 */
ChopWindingInPlace(winding_t ** inout,vec3_t normal,vec_t dist,vec_t epsilon)421 void ChopWindingInPlace (winding_t **inout, vec3_t normal, vec_t dist, vec_t epsilon)
422 {
423 winding_t *in;
424 vec_t dists[MAX_POINTS_ON_WINDING+4];
425 int sides[MAX_POINTS_ON_WINDING+4];
426 int counts[3];
427 static vec_t dot; // VC 4.2 optimizer bug if not static
428 int i, j;
429 vec_t *p1, *p2;
430 vec3_t mid;
431 winding_t *f;
432 int maxpts;
433
434 in = *inout;
435 counts[0] = counts[1] = counts[2] = 0;
436
437 // determine sides for each point
438 for (i=0 ; i<in->numpoints ; i++)
439 {
440 dot = DotProduct (in->p[i], normal);
441 dot -= dist;
442 dists[i] = dot;
443 if (dot > epsilon)
444 sides[i] = SIDE_FRONT;
445 else if (dot < -epsilon)
446 sides[i] = SIDE_BACK;
447 else
448 {
449 sides[i] = SIDE_ON;
450 }
451 counts[sides[i]]++;
452 }
453 sides[i] = sides[0];
454 dists[i] = dists[0];
455
456 if (!counts[0])
457 {
458 FreeWinding (in);
459 *inout = NULL;
460 return;
461 }
462 if (!counts[1])
463 return; // inout stays the same
464
465 maxpts = in->numpoints+4; // cant use counts[0]+2 because
466 // of fp grouping errors
467
468 f = AllocWinding (maxpts);
469
470 for (i=0 ; i<in->numpoints ; i++)
471 {
472 p1 = in->p[i];
473
474 if (sides[i] == SIDE_ON)
475 {
476 VectorCopy (p1, f->p[f->numpoints]);
477 f->numpoints++;
478 continue;
479 }
480
481 if (sides[i] == SIDE_FRONT)
482 {
483 VectorCopy (p1, f->p[f->numpoints]);
484 f->numpoints++;
485 }
486
487 if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])
488 continue;
489
490 // generate a split point
491 p2 = in->p[(i+1)%in->numpoints];
492
493 dot = dists[i] / (dists[i]-dists[i+1]);
494 for (j=0 ; j<3 ; j++)
495 { // avoid round off error when possible
496 if (normal[j] == 1)
497 mid[j] = dist;
498 else if (normal[j] == -1)
499 mid[j] = -dist;
500 else
501 mid[j] = p1[j] + dot*(p2[j]-p1[j]);
502 }
503
504 VectorCopy (mid, f->p[f->numpoints]);
505 f->numpoints++;
506 }
507
508 if (f->numpoints > maxpts)
509 Com_Error (ERR_DROP, "ClipWinding: points exceeded estimate");
510 if (f->numpoints > MAX_POINTS_ON_WINDING)
511 Com_Error (ERR_DROP, "ClipWinding: MAX_POINTS_ON_WINDING");
512
513 FreeWinding (in);
514 *inout = f;
515 }
516
517
518 /*
519 =================
520 ChopWinding
521
522 Returns the fragment of in that is on the front side
523 of the cliping plane. The original is freed.
524 =================
525 */
ChopWinding(winding_t * in,vec3_t normal,vec_t dist)526 winding_t *ChopWinding (winding_t *in, vec3_t normal, vec_t dist)
527 {
528 winding_t *f, *b;
529
530 ClipWindingEpsilon (in, normal, dist, ON_EPSILON, &f, &b);
531 FreeWinding (in);
532 if (b)
533 FreeWinding (b);
534 return f;
535 }
536
537
538 /*
539 =================
540 CheckWinding
541
542 =================
543 */
CheckWinding(winding_t * w)544 void CheckWinding (winding_t *w)
545 {
546 int i, j;
547 vec_t *p1, *p2;
548 vec_t d, edgedist;
549 vec3_t dir, edgenormal, facenormal;
550 vec_t area;
551 vec_t facedist;
552
553 if (w->numpoints < 3)
554 Com_Error (ERR_DROP, "CheckWinding: %i points",w->numpoints);
555
556 area = WindingArea(w);
557 if (area < 1)
558 Com_Error (ERR_DROP, "CheckWinding: %f area", area);
559
560 WindingPlane (w, facenormal, &facedist);
561
562 for (i=0 ; i<w->numpoints ; i++)
563 {
564 p1 = w->p[i];
565
566 for (j=0 ; j<3 ; j++)
567 if (p1[j] > MAX_MAP_BOUNDS || p1[j] < -MAX_MAP_BOUNDS)
568 Com_Error (ERR_DROP, "CheckFace: BUGUS_RANGE: %f",p1[j]);
569
570 j = i+1 == w->numpoints ? 0 : i+1;
571
572 // check the point is on the face plane
573 d = DotProduct (p1, facenormal) - facedist;
574 if (d < -ON_EPSILON || d > ON_EPSILON)
575 Com_Error (ERR_DROP, "CheckWinding: point off plane");
576
577 // check the edge isnt degenerate
578 p2 = w->p[j];
579 VectorSubtract (p2, p1, dir);
580
581 if (VectorLength (dir) < ON_EPSILON)
582 Com_Error (ERR_DROP, "CheckWinding: degenerate edge");
583
584 CrossProduct (facenormal, dir, edgenormal);
585 VectorNormalize2 (edgenormal, edgenormal);
586 edgedist = DotProduct (p1, edgenormal);
587 edgedist += ON_EPSILON;
588
589 // all other points must be on front side
590 for (j=0 ; j<w->numpoints ; j++)
591 {
592 if (j == i)
593 continue;
594 d = DotProduct (w->p[j], edgenormal);
595 if (d > edgedist)
596 Com_Error (ERR_DROP, "CheckWinding: non-convex");
597 }
598 }
599 }
600
601
602 /*
603 ============
604 WindingOnPlaneSide
605 ============
606 */
WindingOnPlaneSide(winding_t * w,vec3_t normal,vec_t dist)607 int WindingOnPlaneSide (winding_t *w, vec3_t normal, vec_t dist)
608 {
609 qboolean front, back;
610 int i;
611 vec_t d;
612
613 front = qfalse;
614 back = qfalse;
615 for (i=0 ; i<w->numpoints ; i++)
616 {
617 d = DotProduct (w->p[i], normal) - dist;
618 if (d < -ON_EPSILON)
619 {
620 if (front)
621 return SIDE_CROSS;
622 back = qtrue;
623 continue;
624 }
625 if (d > ON_EPSILON)
626 {
627 if (back)
628 return SIDE_CROSS;
629 front = qtrue;
630 continue;
631 }
632 }
633
634 if (back)
635 return SIDE_BACK;
636 if (front)
637 return SIDE_FRONT;
638 return SIDE_ON;
639 }
640
641
642 /*
643 =================
644 AddWindingToConvexHull
645
646 Both w and *hull are on the same plane
647 =================
648 */
649 #define MAX_HULL_POINTS 128
AddWindingToConvexHull(winding_t * w,winding_t ** hull,vec3_t normal)650 void AddWindingToConvexHull( winding_t *w, winding_t **hull, vec3_t normal ) {
651 int i, j, k;
652 float *p, *copy;
653 vec3_t dir;
654 float d;
655 int numHullPoints, numNew;
656 vec3_t hullPoints[MAX_HULL_POINTS];
657 vec3_t newHullPoints[MAX_HULL_POINTS];
658 vec3_t hullDirs[MAX_HULL_POINTS];
659 qboolean hullSide[MAX_HULL_POINTS];
660 qboolean outside;
661
662 if ( !*hull ) {
663 *hull = CopyWinding( w );
664 return;
665 }
666
667 numHullPoints = (*hull)->numpoints;
668 Com_Memcpy( hullPoints, (*hull)->p, numHullPoints * sizeof(vec3_t) );
669
670 for ( i = 0 ; i < w->numpoints ; i++ ) {
671 p = w->p[i];
672
673 // calculate hull side vectors
674 for ( j = 0 ; j < numHullPoints ; j++ ) {
675 k = ( j + 1 ) % numHullPoints;
676
677 VectorSubtract( hullPoints[k], hullPoints[j], dir );
678 VectorNormalize2( dir, dir );
679 CrossProduct( normal, dir, hullDirs[j] );
680 }
681
682 outside = qfalse;
683 for ( j = 0 ; j < numHullPoints ; j++ ) {
684 VectorSubtract( p, hullPoints[j], dir );
685 d = DotProduct( dir, hullDirs[j] );
686 if ( d >= ON_EPSILON ) {
687 outside = qtrue;
688 }
689 if ( d >= -ON_EPSILON ) {
690 hullSide[j] = qtrue;
691 } else {
692 hullSide[j] = qfalse;
693 }
694 }
695
696 // if the point is effectively inside, do nothing
697 if ( !outside ) {
698 continue;
699 }
700
701 // find the back side to front side transition
702 for ( j = 0 ; j < numHullPoints ; j++ ) {
703 if ( !hullSide[ j % numHullPoints ] && hullSide[ (j + 1) % numHullPoints ] ) {
704 break;
705 }
706 }
707 if ( j == numHullPoints ) {
708 continue;
709 }
710
711 // insert the point here
712 VectorCopy( p, newHullPoints[0] );
713 numNew = 1;
714
715 // copy over all points that aren't double fronts
716 j = (j+1)%numHullPoints;
717 for ( k = 0 ; k < numHullPoints ; k++ ) {
718 if ( hullSide[ (j+k) % numHullPoints ] && hullSide[ (j+k+1) % numHullPoints ] ) {
719 continue;
720 }
721 copy = hullPoints[ (j+k+1) % numHullPoints ];
722 VectorCopy( copy, newHullPoints[numNew] );
723 numNew++;
724 }
725
726 numHullPoints = numNew;
727 Com_Memcpy( hullPoints, newHullPoints, numHullPoints * sizeof(vec3_t) );
728 }
729
730 FreeWinding( *hull );
731 w = AllocWinding( numHullPoints );
732 w->numpoints = numHullPoints;
733 *hull = w;
734 Com_Memcpy( w->p, hullPoints, numHullPoints * sizeof(vec3_t) );
735 }
736
737
738