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