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 #include "cm_local.h"
24 #include "cm_patch.h"
25
26 /*
27
28 This file does not reference any globals, and has these entry points:
29
30 void CM_ClearLevelPatches( void );
31 struct patchCollide_s *CM_GeneratePatchCollide( int width, int height, const vec3_t *points );
32 void CM_TraceThroughPatchCollide( traceWork_t *tw, const struct patchCollide_s *pc );
33 qboolean CM_PositionTestInPatchCollide( traceWork_t *tw, const struct patchCollide_s *pc );
34 void CM_DrawDebugSurface( void (*drawPoly)(int color, int numPoints, flaot *points) );
35
36
37 WARNING: this may misbehave with meshes that have rows or columns that only
38 degenerate a few triangles. Completely degenerate rows and columns are handled
39 properly.
40 */
41
42 /*
43 #define MAX_FACETS 1024
44 #define MAX_PATCH_PLANES 2048
45
46 typedef struct {
47 float plane[4];
48 int signbits; // signx + (signy<<1) + (signz<<2), used as lookup during collision
49 } patchPlane_t;
50
51 typedef struct {
52 int surfacePlane;
53 int numBorders; // 3 or four + 6 axial bevels + 4 or 3 * 4 edge bevels
54 int borderPlanes[4+6+16];
55 int borderInward[4+6+16];
56 qboolean borderNoAdjust[4+6+16];
57 } facet_t;
58
59 typedef struct patchCollide_s {
60 vec3_t bounds[2];
61 int numPlanes; // surface planes plus edge planes
62 patchPlane_t *planes;
63 int numFacets;
64 facet_t *facets;
65 } patchCollide_t;
66
67
68 #define MAX_GRID_SIZE 129
69
70 typedef struct {
71 int width;
72 int height;
73 qboolean wrapWidth;
74 qboolean wrapHeight;
75 vec3_t points[MAX_GRID_SIZE][MAX_GRID_SIZE]; // [width][height]
76 } cGrid_t;
77
78 #define SUBDIVIDE_DISTANCE 16 //4 // never more than this units away from curve
79 #define PLANE_TRI_EPSILON 0.1
80 #define WRAP_POINT_EPSILON 0.1
81 */
82
83 int c_totalPatchBlocks;
84 int c_totalPatchSurfaces;
85 int c_totalPatchEdges;
86
87 static const patchCollide_t *debugPatchCollide;
88 static const facet_t *debugFacet;
89 static qboolean debugBlock;
90 static vec3_t debugBlockPoints[4];
91
92 /*
93 =================
94 CM_ClearLevelPatches
95 =================
96 */
CM_ClearLevelPatches(void)97 void CM_ClearLevelPatches( void ) {
98 debugPatchCollide = NULL;
99 debugFacet = NULL;
100 }
101
102 /*
103 =================
104 CM_SignbitsForNormal
105 =================
106 */
CM_SignbitsForNormal(vec3_t normal)107 static int CM_SignbitsForNormal( vec3_t normal ) {
108 int bits, j;
109
110 bits = 0;
111 for (j=0 ; j<3 ; j++) {
112 if ( normal[j] < 0 ) {
113 bits |= 1<<j;
114 }
115 }
116 return bits;
117 }
118
119 /*
120 =====================
121 CM_PlaneFromPoints
122
123 Returns false if the triangle is degenrate.
124 The normal will point out of the clock for clockwise ordered points
125 =====================
126 */
CM_PlaneFromPoints(vec4_t plane,vec3_t a,vec3_t b,vec3_t c)127 static qboolean CM_PlaneFromPoints( vec4_t plane, vec3_t a, vec3_t b, vec3_t c ) {
128 vec3_t d1, d2;
129
130 VectorSubtract( b, a, d1 );
131 VectorSubtract( c, a, d2 );
132 CrossProduct( d2, d1, plane );
133 if ( VectorNormalize( plane ) == 0 ) {
134 return qfalse;
135 }
136
137 plane[3] = DotProduct( a, plane );
138 return qtrue;
139 }
140
141
142 /*
143 ================================================================================
144
145 GRID SUBDIVISION
146
147 ================================================================================
148 */
149
150 /*
151 =================
152 CM_NeedsSubdivision
153
154 Returns true if the given quadratic curve is not flat enough for our
155 collision detection purposes
156 =================
157 */
CM_NeedsSubdivision(vec3_t a,vec3_t b,vec3_t c)158 static qboolean CM_NeedsSubdivision( vec3_t a, vec3_t b, vec3_t c ) {
159 vec3_t cmid;
160 vec3_t lmid;
161 vec3_t delta;
162 float dist;
163 int i;
164
165 // calculate the linear midpoint
166 for ( i = 0 ; i < 3 ; i++ ) {
167 lmid[i] = 0.5*(a[i] + c[i]);
168 }
169
170 // calculate the exact curve midpoint
171 for ( i = 0 ; i < 3 ; i++ ) {
172 cmid[i] = 0.5 * ( 0.5*(a[i] + b[i]) + 0.5*(b[i] + c[i]) );
173 }
174
175 // see if the curve is far enough away from the linear mid
176 VectorSubtract( cmid, lmid, delta );
177 dist = VectorLength( delta );
178
179 return dist >= SUBDIVIDE_DISTANCE;
180 }
181
182 /*
183 ===============
184 CM_Subdivide
185
186 a, b, and c are control points.
187 the subdivided sequence will be: a, out1, out2, out3, c
188 ===============
189 */
CM_Subdivide(vec3_t a,vec3_t b,vec3_t c,vec3_t out1,vec3_t out2,vec3_t out3)190 static void CM_Subdivide( vec3_t a, vec3_t b, vec3_t c, vec3_t out1, vec3_t out2, vec3_t out3 ) {
191 int i;
192
193 for ( i = 0 ; i < 3 ; i++ ) {
194 out1[i] = 0.5 * (a[i] + b[i]);
195 out3[i] = 0.5 * (b[i] + c[i]);
196 out2[i] = 0.5 * (out1[i] + out3[i]);
197 }
198 }
199
200 /*
201 =================
202 CM_TransposeGrid
203
204 Swaps the rows and columns in place
205 =================
206 */
CM_TransposeGrid(cGrid_t * grid)207 static void CM_TransposeGrid( cGrid_t *grid ) {
208 int i, j, l;
209 vec3_t temp;
210 qboolean tempWrap;
211
212 if ( grid->width > grid->height ) {
213 for ( i = 0 ; i < grid->height ; i++ ) {
214 for ( j = i + 1 ; j < grid->width ; j++ ) {
215 if ( j < grid->height ) {
216 // swap the value
217 VectorCopy( grid->points[i][j], temp );
218 VectorCopy( grid->points[j][i], grid->points[i][j] );
219 VectorCopy( temp, grid->points[j][i] );
220 } else {
221 // just copy
222 VectorCopy( grid->points[j][i], grid->points[i][j] );
223 }
224 }
225 }
226 } else {
227 for ( i = 0 ; i < grid->width ; i++ ) {
228 for ( j = i + 1 ; j < grid->height ; j++ ) {
229 if ( j < grid->width ) {
230 // swap the value
231 VectorCopy( grid->points[j][i], temp );
232 VectorCopy( grid->points[i][j], grid->points[j][i] );
233 VectorCopy( temp, grid->points[i][j] );
234 } else {
235 // just copy
236 VectorCopy( grid->points[i][j], grid->points[j][i] );
237 }
238 }
239 }
240 }
241
242 l = grid->width;
243 grid->width = grid->height;
244 grid->height = l;
245
246 tempWrap = grid->wrapWidth;
247 grid->wrapWidth = grid->wrapHeight;
248 grid->wrapHeight = tempWrap;
249 }
250
251 /*
252 ===================
253 CM_SetGridWrapWidth
254
255 If the left and right columns are exactly equal, set grid->wrapWidth qtrue
256 ===================
257 */
CM_SetGridWrapWidth(cGrid_t * grid)258 static void CM_SetGridWrapWidth( cGrid_t *grid ) {
259 int i, j;
260 float d;
261
262 for ( i = 0 ; i < grid->height ; i++ ) {
263 for ( j = 0 ; j < 3 ; j++ ) {
264 d = grid->points[0][i][j] - grid->points[grid->width-1][i][j];
265 if ( d < -WRAP_POINT_EPSILON || d > WRAP_POINT_EPSILON ) {
266 break;
267 }
268 }
269 if ( j != 3 ) {
270 break;
271 }
272 }
273 if ( i == grid->height ) {
274 grid->wrapWidth = qtrue;
275 } else {
276 grid->wrapWidth = qfalse;
277 }
278 }
279
280 /*
281 =================
282 CM_SubdivideGridColumns
283
284 Adds columns as necessary to the grid until
285 all the aproximating points are within SUBDIVIDE_DISTANCE
286 from the true curve
287 =================
288 */
CM_SubdivideGridColumns(cGrid_t * grid)289 static void CM_SubdivideGridColumns( cGrid_t *grid ) {
290 int i, j, k;
291
292 for ( i = 0 ; i < grid->width - 2 ; ) {
293 // grid->points[i][x] is an interpolating control point
294 // grid->points[i+1][x] is an aproximating control point
295 // grid->points[i+2][x] is an interpolating control point
296
297 //
298 // first see if we can collapse the aproximating collumn away
299 //
300 for ( j = 0 ; j < grid->height ; j++ ) {
301 if ( CM_NeedsSubdivision( grid->points[i][j], grid->points[i+1][j], grid->points[i+2][j] ) ) {
302 break;
303 }
304 }
305 if ( j == grid->height ) {
306 // all of the points were close enough to the linear midpoints
307 // that we can collapse the entire column away
308 for ( j = 0 ; j < grid->height ; j++ ) {
309 // remove the column
310 for ( k = i + 2 ; k < grid->width ; k++ ) {
311 VectorCopy( grid->points[k][j], grid->points[k-1][j] );
312 }
313 }
314
315 grid->width--;
316
317 // go to the next curve segment
318 i++;
319 continue;
320 }
321
322 //
323 // we need to subdivide the curve
324 //
325 for ( j = 0 ; j < grid->height ; j++ ) {
326 vec3_t prev, mid, next;
327
328 // save the control points now
329 VectorCopy( grid->points[i][j], prev );
330 VectorCopy( grid->points[i+1][j], mid );
331 VectorCopy( grid->points[i+2][j], next );
332
333 // make room for two additional columns in the grid
334 // columns i+1 will be replaced, column i+2 will become i+4
335 // i+1, i+2, and i+3 will be generated
336 for ( k = grid->width - 1 ; k > i + 1 ; k-- ) {
337 VectorCopy( grid->points[k][j], grid->points[k+2][j] );
338 }
339
340 // generate the subdivided points
341 CM_Subdivide( prev, mid, next, grid->points[i+1][j], grid->points[i+2][j], grid->points[i+3][j] );
342 }
343
344 grid->width += 2;
345
346 // the new aproximating point at i+1 may need to be removed
347 // or subdivided farther, so don't advance i
348 }
349 }
350
351 /*
352 ======================
353 CM_ComparePoints
354 ======================
355 */
356 #define POINT_EPSILON 0.1
CM_ComparePoints(float * a,float * b)357 static qboolean CM_ComparePoints( float *a, float *b ) {
358 float d;
359
360 d = a[0] - b[0];
361 if ( d < -POINT_EPSILON || d > POINT_EPSILON ) {
362 return qfalse;
363 }
364 d = a[1] - b[1];
365 if ( d < -POINT_EPSILON || d > POINT_EPSILON ) {
366 return qfalse;
367 }
368 d = a[2] - b[2];
369 if ( d < -POINT_EPSILON || d > POINT_EPSILON ) {
370 return qfalse;
371 }
372 return qtrue;
373 }
374
375 /*
376 =================
377 CM_RemoveDegenerateColumns
378
379 If there are any identical columns, remove them
380 =================
381 */
CM_RemoveDegenerateColumns(cGrid_t * grid)382 static void CM_RemoveDegenerateColumns( cGrid_t *grid ) {
383 int i, j, k;
384
385 for ( i = 0 ; i < grid->width - 1 ; i++ ) {
386 for ( j = 0 ; j < grid->height ; j++ ) {
387 if ( !CM_ComparePoints( grid->points[i][j], grid->points[i+1][j] ) ) {
388 break;
389 }
390 }
391
392 if ( j != grid->height ) {
393 continue; // not degenerate
394 }
395
396 for ( j = 0 ; j < grid->height ; j++ ) {
397 // remove the column
398 for ( k = i + 2 ; k < grid->width ; k++ ) {
399 VectorCopy( grid->points[k][j], grid->points[k-1][j] );
400 }
401 }
402 grid->width--;
403
404 // check against the next column
405 i--;
406 }
407 }
408
409 /*
410 ================================================================================
411
412 PATCH COLLIDE GENERATION
413
414 ================================================================================
415 */
416
417 static int numPlanes;
418 static patchPlane_t planes[MAX_PATCH_PLANES];
419
420 static int numFacets;
421 static facet_t facets[MAX_PATCH_PLANES]; //maybe MAX_FACETS ??
422
423 #define NORMAL_EPSILON 0.0001
424 #define DIST_EPSILON 0.02
425
426 /*
427 ==================
428 CM_PlaneEqual
429 ==================
430 */
CM_PlaneEqual(patchPlane_t * p,float plane[4],int * flipped)431 int CM_PlaneEqual(patchPlane_t *p, float plane[4], int *flipped) {
432 float invplane[4];
433
434 if (
435 fabs(p->plane[0] - plane[0]) < NORMAL_EPSILON
436 && fabs(p->plane[1] - plane[1]) < NORMAL_EPSILON
437 && fabs(p->plane[2] - plane[2]) < NORMAL_EPSILON
438 && fabs(p->plane[3] - plane[3]) < DIST_EPSILON )
439 {
440 *flipped = qfalse;
441 return qtrue;
442 }
443
444 VectorNegate(plane, invplane);
445 invplane[3] = -plane[3];
446
447 if (
448 fabs(p->plane[0] - invplane[0]) < NORMAL_EPSILON
449 && fabs(p->plane[1] - invplane[1]) < NORMAL_EPSILON
450 && fabs(p->plane[2] - invplane[2]) < NORMAL_EPSILON
451 && fabs(p->plane[3] - invplane[3]) < DIST_EPSILON )
452 {
453 *flipped = qtrue;
454 return qtrue;
455 }
456
457 return qfalse;
458 }
459
460 /*
461 ==================
462 CM_SnapVector
463 ==================
464 */
CM_SnapVector(vec3_t normal)465 void CM_SnapVector(vec3_t normal) {
466 int i;
467
468 for (i=0 ; i<3 ; i++)
469 {
470 if ( fabs(normal[i] - 1) < NORMAL_EPSILON )
471 {
472 VectorClear (normal);
473 normal[i] = 1;
474 break;
475 }
476 if ( fabs(normal[i] - -1) < NORMAL_EPSILON )
477 {
478 VectorClear (normal);
479 normal[i] = -1;
480 break;
481 }
482 }
483 }
484
485 /*
486 ==================
487 CM_FindPlane2
488 ==================
489 */
CM_FindPlane2(float plane[4],int * flipped)490 int CM_FindPlane2(float plane[4], int *flipped) {
491 int i;
492
493 // see if the points are close enough to an existing plane
494 for ( i = 0 ; i < numPlanes ; i++ ) {
495 if (CM_PlaneEqual(&planes[i], plane, flipped)) return i;
496 }
497
498 // add a new plane
499 if ( numPlanes == MAX_PATCH_PLANES ) {
500 Com_Error( ERR_DROP, "MAX_PATCH_PLANES" );
501 }
502
503 Vector4Copy( plane, planes[numPlanes].plane );
504 planes[numPlanes].signbits = CM_SignbitsForNormal( plane );
505
506 numPlanes++;
507
508 *flipped = qfalse;
509
510 return numPlanes-1;
511 }
512
513 /*
514 ==================
515 CM_FindPlane
516 ==================
517 */
CM_FindPlane(float * p1,float * p2,float * p3)518 static int CM_FindPlane( float *p1, float *p2, float *p3 ) {
519 float plane[4];
520 int i;
521 float d;
522
523 if ( !CM_PlaneFromPoints( plane, p1, p2, p3 ) ) {
524 return -1;
525 }
526
527 // see if the points are close enough to an existing plane
528 for ( i = 0 ; i < numPlanes ; i++ ) {
529 if ( DotProduct( plane, planes[i].plane ) < 0 ) {
530 continue; // allow backwards planes?
531 }
532
533 d = DotProduct( p1, planes[i].plane ) - planes[i].plane[3];
534 if ( d < -PLANE_TRI_EPSILON || d > PLANE_TRI_EPSILON ) {
535 continue;
536 }
537
538 d = DotProduct( p2, planes[i].plane ) - planes[i].plane[3];
539 if ( d < -PLANE_TRI_EPSILON || d > PLANE_TRI_EPSILON ) {
540 continue;
541 }
542
543 d = DotProduct( p3, planes[i].plane ) - planes[i].plane[3];
544 if ( d < -PLANE_TRI_EPSILON || d > PLANE_TRI_EPSILON ) {
545 continue;
546 }
547
548 // found it
549 return i;
550 }
551
552 // add a new plane
553 if ( numPlanes == MAX_PATCH_PLANES ) {
554 Com_Error( ERR_DROP, "MAX_PATCH_PLANES" );
555 }
556
557 Vector4Copy( plane, planes[numPlanes].plane );
558 planes[numPlanes].signbits = CM_SignbitsForNormal( plane );
559
560 numPlanes++;
561
562 return numPlanes-1;
563 }
564
565 /*
566 ==================
567 CM_PointOnPlaneSide
568 ==================
569 */
CM_PointOnPlaneSide(float * p,int planeNum)570 static int CM_PointOnPlaneSide( float *p, int planeNum ) {
571 float *plane;
572 float d;
573
574 if ( planeNum == -1 ) {
575 return SIDE_ON;
576 }
577 plane = planes[ planeNum ].plane;
578
579 d = DotProduct( p, plane ) - plane[3];
580
581 if ( d > PLANE_TRI_EPSILON ) {
582 return SIDE_FRONT;
583 }
584
585 if ( d < -PLANE_TRI_EPSILON ) {
586 return SIDE_BACK;
587 }
588
589 return SIDE_ON;
590 }
591
592 /*
593 ==================
594 CM_GridPlane
595 ==================
596 */
CM_GridPlane(int gridPlanes[MAX_GRID_SIZE][MAX_GRID_SIZE][2],int i,int j,int tri)597 static int CM_GridPlane( int gridPlanes[MAX_GRID_SIZE][MAX_GRID_SIZE][2], int i, int j, int tri ) {
598 int p;
599
600 p = gridPlanes[i][j][tri];
601 if ( p != -1 ) {
602 return p;
603 }
604 p = gridPlanes[i][j][!tri];
605 if ( p != -1 ) {
606 return p;
607 }
608
609 // should never happen
610 Com_Printf( "WARNING: CM_GridPlane unresolvable\n" );
611 return -1;
612 }
613
614 /*
615 ==================
616 CM_EdgePlaneNum
617 ==================
618 */
CM_EdgePlaneNum(cGrid_t * grid,int gridPlanes[MAX_GRID_SIZE][MAX_GRID_SIZE][2],int i,int j,int k)619 static int CM_EdgePlaneNum( cGrid_t *grid, int gridPlanes[MAX_GRID_SIZE][MAX_GRID_SIZE][2], int i, int j, int k ) {
620 float *p1, *p2;
621 vec3_t up;
622 int p;
623
624 switch ( k ) {
625 case 0: // top border
626 p1 = grid->points[i][j];
627 p2 = grid->points[i+1][j];
628 p = CM_GridPlane( gridPlanes, i, j, 0 );
629 VectorMA( p1, 4, planes[ p ].plane, up );
630 return CM_FindPlane( p1, p2, up );
631
632 case 2: // bottom border
633 p1 = grid->points[i][j+1];
634 p2 = grid->points[i+1][j+1];
635 p = CM_GridPlane( gridPlanes, i, j, 1 );
636 VectorMA( p1, 4, planes[ p ].plane, up );
637 return CM_FindPlane( p2, p1, up );
638
639 case 3: // left border
640 p1 = grid->points[i][j];
641 p2 = grid->points[i][j+1];
642 p = CM_GridPlane( gridPlanes, i, j, 1 );
643 VectorMA( p1, 4, planes[ p ].plane, up );
644 return CM_FindPlane( p2, p1, up );
645
646 case 1: // right border
647 p1 = grid->points[i+1][j];
648 p2 = grid->points[i+1][j+1];
649 p = CM_GridPlane( gridPlanes, i, j, 0 );
650 VectorMA( p1, 4, planes[ p ].plane, up );
651 return CM_FindPlane( p1, p2, up );
652
653 case 4: // diagonal out of triangle 0
654 p1 = grid->points[i+1][j+1];
655 p2 = grid->points[i][j];
656 p = CM_GridPlane( gridPlanes, i, j, 0 );
657 VectorMA( p1, 4, planes[ p ].plane, up );
658 return CM_FindPlane( p1, p2, up );
659
660 case 5: // diagonal out of triangle 1
661 p1 = grid->points[i][j];
662 p2 = grid->points[i+1][j+1];
663 p = CM_GridPlane( gridPlanes, i, j, 1 );
664 VectorMA( p1, 4, planes[ p ].plane, up );
665 return CM_FindPlane( p1, p2, up );
666
667 }
668
669 Com_Error( ERR_DROP, "CM_EdgePlaneNum: bad k" );
670 return -1;
671 }
672
673 /*
674 ===================
675 CM_SetBorderInward
676 ===================
677 */
CM_SetBorderInward(facet_t * facet,cGrid_t * grid,int gridPlanes[MAX_GRID_SIZE][MAX_GRID_SIZE][2],int i,int j,int which)678 static void CM_SetBorderInward( facet_t *facet, cGrid_t *grid, int gridPlanes[MAX_GRID_SIZE][MAX_GRID_SIZE][2],
679 int i, int j, int which ) {
680 int k, l;
681 float *points[4];
682 int numPoints;
683
684 switch ( which ) {
685 case -1:
686 points[0] = grid->points[i][j];
687 points[1] = grid->points[i+1][j];
688 points[2] = grid->points[i+1][j+1];
689 points[3] = grid->points[i][j+1];
690 numPoints = 4;
691 break;
692 case 0:
693 points[0] = grid->points[i][j];
694 points[1] = grid->points[i+1][j];
695 points[2] = grid->points[i+1][j+1];
696 numPoints = 3;
697 break;
698 case 1:
699 points[0] = grid->points[i+1][j+1];
700 points[1] = grid->points[i][j+1];
701 points[2] = grid->points[i][j];
702 numPoints = 3;
703 break;
704 default:
705 Com_Error( ERR_FATAL, "CM_SetBorderInward: bad parameter" );
706 numPoints = 0;
707 break;
708 }
709
710 for ( k = 0 ; k < facet->numBorders ; k++ ) {
711 int front, back;
712
713 front = 0;
714 back = 0;
715
716 for ( l = 0 ; l < numPoints ; l++ ) {
717 int side;
718
719 side = CM_PointOnPlaneSide( points[l], facet->borderPlanes[k] );
720 if ( side == SIDE_FRONT ) {
721 front++;
722 } if ( side == SIDE_BACK ) {
723 back++;
724 }
725 }
726
727 if ( front && !back ) {
728 facet->borderInward[k] = qtrue;
729 } else if ( back && !front ) {
730 facet->borderInward[k] = qfalse;
731 } else if ( !front && !back ) {
732 // flat side border
733 facet->borderPlanes[k] = -1;
734 } else {
735 // bisecting side border
736 Com_DPrintf( "WARNING: CM_SetBorderInward: mixed plane sides\n" );
737 facet->borderInward[k] = qfalse;
738 if ( !debugBlock ) {
739 debugBlock = qtrue;
740 VectorCopy( grid->points[i][j], debugBlockPoints[0] );
741 VectorCopy( grid->points[i+1][j], debugBlockPoints[1] );
742 VectorCopy( grid->points[i+1][j+1], debugBlockPoints[2] );
743 VectorCopy( grid->points[i][j+1], debugBlockPoints[3] );
744 }
745 }
746 }
747 }
748
749 /*
750 ==================
751 CM_ValidateFacet
752
753 If the facet isn't bounded by its borders, we screwed up.
754 ==================
755 */
CM_ValidateFacet(facet_t * facet)756 static qboolean CM_ValidateFacet( facet_t *facet ) {
757 float plane[4];
758 int j;
759 winding_t *w;
760 vec3_t bounds[2];
761
762 if ( facet->surfacePlane == -1 ) {
763 return qfalse;
764 }
765
766 Vector4Copy( planes[ facet->surfacePlane ].plane, plane );
767 w = BaseWindingForPlane( plane, plane[3] );
768 for ( j = 0 ; j < facet->numBorders && w ; j++ ) {
769 if ( facet->borderPlanes[j] == -1 ) {
770 FreeWinding( w );
771 return qfalse;
772 }
773 Vector4Copy( planes[ facet->borderPlanes[j] ].plane, plane );
774 if ( !facet->borderInward[j] ) {
775 VectorSubtract( vec3_origin, plane, plane );
776 plane[3] = -plane[3];
777 }
778 ChopWindingInPlace( &w, plane, plane[3], 0.1f );
779 }
780
781 if ( !w ) {
782 return qfalse; // winding was completely chopped away
783 }
784
785 // see if the facet is unreasonably large
786 WindingBounds( w, bounds[0], bounds[1] );
787 FreeWinding( w );
788
789 for ( j = 0 ; j < 3 ; j++ ) {
790 if ( bounds[1][j] - bounds[0][j] > MAX_MAP_BOUNDS ) {
791 return qfalse; // we must be missing a plane
792 }
793 if ( bounds[0][j] >= MAX_MAP_BOUNDS ) {
794 return qfalse;
795 }
796 if ( bounds[1][j] <= -MAX_MAP_BOUNDS ) {
797 return qfalse;
798 }
799 }
800 return qtrue; // winding is fine
801 }
802
803 /*
804 ==================
805 CM_AddFacetBevels
806 ==================
807 */
CM_AddFacetBevels(facet_t * facet)808 void CM_AddFacetBevels( facet_t *facet ) {
809
810 int i, j, k, l;
811 int axis, dir, order, flipped;
812 float plane[4], d, newplane[4];
813 winding_t *w, *w2;
814 vec3_t mins, maxs, vec, vec2;
815
816 Vector4Copy( planes[ facet->surfacePlane ].plane, plane );
817
818 w = BaseWindingForPlane( plane, plane[3] );
819 for ( j = 0 ; j < facet->numBorders && w ; j++ ) {
820 if (facet->borderPlanes[j] == facet->surfacePlane) continue;
821 Vector4Copy( planes[ facet->borderPlanes[j] ].plane, plane );
822
823 if ( !facet->borderInward[j] ) {
824 VectorSubtract( vec3_origin, plane, plane );
825 plane[3] = -plane[3];
826 }
827
828 ChopWindingInPlace( &w, plane, plane[3], 0.1f );
829 }
830 if ( !w ) {
831 return;
832 }
833
834 WindingBounds(w, mins, maxs);
835
836 // add the axial planes
837 order = 0;
838 for ( axis = 0 ; axis < 3 ; axis++ )
839 {
840 for ( dir = -1 ; dir <= 1 ; dir += 2, order++ )
841 {
842 VectorClear(plane);
843 plane[axis] = dir;
844 if (dir == 1) {
845 plane[3] = maxs[axis];
846 }
847 else {
848 plane[3] = -mins[axis];
849 }
850 //if it's the surface plane
851 if (CM_PlaneEqual(&planes[facet->surfacePlane], plane, &flipped)) {
852 continue;
853 }
854 // see if the plane is allready present
855 for ( i = 0 ; i < facet->numBorders ; i++ ) {
856 if (CM_PlaneEqual(&planes[facet->borderPlanes[i]], plane, &flipped))
857 break;
858 }
859
860 if ( i == facet->numBorders ) {
861 if (facet->numBorders > 4 + 6 + 16) Com_Printf("ERROR: too many bevels\n");
862 facet->borderPlanes[facet->numBorders] = CM_FindPlane2(plane, &flipped);
863 facet->borderNoAdjust[facet->numBorders] = 0;
864 facet->borderInward[facet->numBorders] = flipped;
865 facet->numBorders++;
866 }
867 }
868 }
869 //
870 // add the edge bevels
871 //
872 // test the non-axial plane edges
873 for ( j = 0 ; j < w->numpoints ; j++ )
874 {
875 k = (j+1)%w->numpoints;
876 VectorSubtract (w->p[j], w->p[k], vec);
877 //if it's a degenerate edge
878 if (VectorNormalize (vec) < 0.5)
879 continue;
880 CM_SnapVector(vec);
881 for ( k = 0; k < 3 ; k++ )
882 if ( vec[k] == -1 || vec[k] == 1 )
883 break; // axial
884 if ( k < 3 )
885 continue; // only test non-axial edges
886
887 // try the six possible slanted axials from this edge
888 for ( axis = 0 ; axis < 3 ; axis++ )
889 {
890 for ( dir = -1 ; dir <= 1 ; dir += 2 )
891 {
892 // construct a plane
893 VectorClear (vec2);
894 vec2[axis] = dir;
895 CrossProduct (vec, vec2, plane);
896 if (VectorNormalize (plane) < 0.5)
897 continue;
898 plane[3] = DotProduct (w->p[j], plane);
899
900 // if all the points of the facet winding are
901 // behind this plane, it is a proper edge bevel
902 for ( l = 0 ; l < w->numpoints ; l++ )
903 {
904 d = DotProduct (w->p[l], plane) - plane[3];
905 if (d > 0.1)
906 break; // point in front
907 }
908 if ( l < w->numpoints )
909 continue;
910
911 //if it's the surface plane
912 if (CM_PlaneEqual(&planes[facet->surfacePlane], plane, &flipped)) {
913 continue;
914 }
915 // see if the plane is allready present
916 for ( i = 0 ; i < facet->numBorders ; i++ ) {
917 if (CM_PlaneEqual(&planes[facet->borderPlanes[i]], plane, &flipped)) {
918 break;
919 }
920 }
921
922 if ( i == facet->numBorders ) {
923 if (facet->numBorders > 4 + 6 + 16) Com_Printf("ERROR: too many bevels\n");
924 facet->borderPlanes[facet->numBorders] = CM_FindPlane2(plane, &flipped);
925
926 for ( k = 0 ; k < facet->numBorders ; k++ ) {
927 if (facet->borderPlanes[facet->numBorders] ==
928 facet->borderPlanes[k]) Com_Printf("WARNING: bevel plane already used\n");
929 }
930
931 facet->borderNoAdjust[facet->numBorders] = 0;
932 facet->borderInward[facet->numBorders] = flipped;
933 //
934 w2 = CopyWinding(w);
935 Vector4Copy(planes[facet->borderPlanes[facet->numBorders]].plane, newplane);
936 if (!facet->borderInward[facet->numBorders])
937 {
938 VectorNegate(newplane, newplane);
939 newplane[3] = -newplane[3];
940 } //end if
941 ChopWindingInPlace( &w2, newplane, newplane[3], 0.1f );
942 if (!w2) {
943 Com_DPrintf("WARNING: CM_AddFacetBevels... invalid bevel\n");
944 continue;
945 }
946 else {
947 FreeWinding(w2);
948 }
949 //
950 facet->numBorders++;
951 //already got a bevel
952 // break;
953 }
954 }
955 }
956 }
957 FreeWinding( w );
958
959 #ifndef BSPC
960 //add opposite plane
961 facet->borderPlanes[facet->numBorders] = facet->surfacePlane;
962 facet->borderNoAdjust[facet->numBorders] = 0;
963 facet->borderInward[facet->numBorders] = qtrue;
964 facet->numBorders++;
965 #endif //BSPC
966
967 }
968
969 typedef enum {
970 EN_TOP,
971 EN_RIGHT,
972 EN_BOTTOM,
973 EN_LEFT
974 } edgeName_t;
975
976 /*
977 ==================
978 CM_PatchCollideFromGrid
979 ==================
980 */
CM_PatchCollideFromGrid(cGrid_t * grid,patchCollide_t * pf)981 static void CM_PatchCollideFromGrid( cGrid_t *grid, patchCollide_t *pf ) {
982 int i, j;
983 float *p1, *p2, *p3;
984 int gridPlanes[MAX_GRID_SIZE][MAX_GRID_SIZE][2];
985 facet_t *facet;
986 int borders[4];
987 int noAdjust[4];
988
989 numPlanes = 0;
990 numFacets = 0;
991
992 // find the planes for each triangle of the grid
993 for ( i = 0 ; i < grid->width - 1 ; i++ ) {
994 for ( j = 0 ; j < grid->height - 1 ; j++ ) {
995 p1 = grid->points[i][j];
996 p2 = grid->points[i+1][j];
997 p3 = grid->points[i+1][j+1];
998 gridPlanes[i][j][0] = CM_FindPlane( p1, p2, p3 );
999
1000 p1 = grid->points[i+1][j+1];
1001 p2 = grid->points[i][j+1];
1002 p3 = grid->points[i][j];
1003 gridPlanes[i][j][1] = CM_FindPlane( p1, p2, p3 );
1004 }
1005 }
1006
1007 // create the borders for each facet
1008 for ( i = 0 ; i < grid->width - 1 ; i++ ) {
1009 for ( j = 0 ; j < grid->height - 1 ; j++ ) {
1010
1011 borders[EN_TOP] = -1;
1012 if ( j > 0 ) {
1013 borders[EN_TOP] = gridPlanes[i][j-1][1];
1014 } else if ( grid->wrapHeight ) {
1015 borders[EN_TOP] = gridPlanes[i][grid->height-2][1];
1016 }
1017 noAdjust[EN_TOP] = ( borders[EN_TOP] == gridPlanes[i][j][0] );
1018 if ( borders[EN_TOP] == -1 || noAdjust[EN_TOP] ) {
1019 borders[EN_TOP] = CM_EdgePlaneNum( grid, gridPlanes, i, j, 0 );
1020 }
1021
1022 borders[EN_BOTTOM] = -1;
1023 if ( j < grid->height - 2 ) {
1024 borders[EN_BOTTOM] = gridPlanes[i][j+1][0];
1025 } else if ( grid->wrapHeight ) {
1026 borders[EN_BOTTOM] = gridPlanes[i][0][0];
1027 }
1028 noAdjust[EN_BOTTOM] = ( borders[EN_BOTTOM] == gridPlanes[i][j][1] );
1029 if ( borders[EN_BOTTOM] == -1 || noAdjust[EN_BOTTOM] ) {
1030 borders[EN_BOTTOM] = CM_EdgePlaneNum( grid, gridPlanes, i, j, 2 );
1031 }
1032
1033 borders[EN_LEFT] = -1;
1034 if ( i > 0 ) {
1035 borders[EN_LEFT] = gridPlanes[i-1][j][0];
1036 } else if ( grid->wrapWidth ) {
1037 borders[EN_LEFT] = gridPlanes[grid->width-2][j][0];
1038 }
1039 noAdjust[EN_LEFT] = ( borders[EN_LEFT] == gridPlanes[i][j][1] );
1040 if ( borders[EN_LEFT] == -1 || noAdjust[EN_LEFT] ) {
1041 borders[EN_LEFT] = CM_EdgePlaneNum( grid, gridPlanes, i, j, 3 );
1042 }
1043
1044 borders[EN_RIGHT] = -1;
1045 if ( i < grid->width - 2 ) {
1046 borders[EN_RIGHT] = gridPlanes[i+1][j][1];
1047 } else if ( grid->wrapWidth ) {
1048 borders[EN_RIGHT] = gridPlanes[0][j][1];
1049 }
1050 noAdjust[EN_RIGHT] = ( borders[EN_RIGHT] == gridPlanes[i][j][0] );
1051 if ( borders[EN_RIGHT] == -1 || noAdjust[EN_RIGHT] ) {
1052 borders[EN_RIGHT] = CM_EdgePlaneNum( grid, gridPlanes, i, j, 1 );
1053 }
1054
1055 if ( numFacets == MAX_FACETS ) {
1056 Com_Error( ERR_DROP, "MAX_FACETS" );
1057 }
1058 facet = &facets[numFacets];
1059 Com_Memset( facet, 0, sizeof( *facet ) );
1060
1061 if ( gridPlanes[i][j][0] == gridPlanes[i][j][1] ) {
1062 if ( gridPlanes[i][j][0] == -1 ) {
1063 continue; // degenrate
1064 }
1065 facet->surfacePlane = gridPlanes[i][j][0];
1066 facet->numBorders = 4;
1067 facet->borderPlanes[0] = borders[EN_TOP];
1068 facet->borderNoAdjust[0] = noAdjust[EN_TOP];
1069 facet->borderPlanes[1] = borders[EN_RIGHT];
1070 facet->borderNoAdjust[1] = noAdjust[EN_RIGHT];
1071 facet->borderPlanes[2] = borders[EN_BOTTOM];
1072 facet->borderNoAdjust[2] = noAdjust[EN_BOTTOM];
1073 facet->borderPlanes[3] = borders[EN_LEFT];
1074 facet->borderNoAdjust[3] = noAdjust[EN_LEFT];
1075 CM_SetBorderInward( facet, grid, gridPlanes, i, j, -1 );
1076 if ( CM_ValidateFacet( facet ) ) {
1077 CM_AddFacetBevels( facet );
1078 numFacets++;
1079 }
1080 } else {
1081 // two seperate triangles
1082 facet->surfacePlane = gridPlanes[i][j][0];
1083 facet->numBorders = 3;
1084 facet->borderPlanes[0] = borders[EN_TOP];
1085 facet->borderNoAdjust[0] = noAdjust[EN_TOP];
1086 facet->borderPlanes[1] = borders[EN_RIGHT];
1087 facet->borderNoAdjust[1] = noAdjust[EN_RIGHT];
1088 facet->borderPlanes[2] = gridPlanes[i][j][1];
1089 if ( facet->borderPlanes[2] == -1 ) {
1090 facet->borderPlanes[2] = borders[EN_BOTTOM];
1091 if ( facet->borderPlanes[2] == -1 ) {
1092 facet->borderPlanes[2] = CM_EdgePlaneNum( grid, gridPlanes, i, j, 4 );
1093 }
1094 }
1095 CM_SetBorderInward( facet, grid, gridPlanes, i, j, 0 );
1096 if ( CM_ValidateFacet( facet ) ) {
1097 CM_AddFacetBevels( facet );
1098 numFacets++;
1099 }
1100
1101 if ( numFacets == MAX_FACETS ) {
1102 Com_Error( ERR_DROP, "MAX_FACETS" );
1103 }
1104 facet = &facets[numFacets];
1105 Com_Memset( facet, 0, sizeof( *facet ) );
1106
1107 facet->surfacePlane = gridPlanes[i][j][1];
1108 facet->numBorders = 3;
1109 facet->borderPlanes[0] = borders[EN_BOTTOM];
1110 facet->borderNoAdjust[0] = noAdjust[EN_BOTTOM];
1111 facet->borderPlanes[1] = borders[EN_LEFT];
1112 facet->borderNoAdjust[1] = noAdjust[EN_LEFT];
1113 facet->borderPlanes[2] = gridPlanes[i][j][0];
1114 if ( facet->borderPlanes[2] == -1 ) {
1115 facet->borderPlanes[2] = borders[EN_TOP];
1116 if ( facet->borderPlanes[2] == -1 ) {
1117 facet->borderPlanes[2] = CM_EdgePlaneNum( grid, gridPlanes, i, j, 5 );
1118 }
1119 }
1120 CM_SetBorderInward( facet, grid, gridPlanes, i, j, 1 );
1121 if ( CM_ValidateFacet( facet ) ) {
1122 CM_AddFacetBevels( facet );
1123 numFacets++;
1124 }
1125 }
1126 }
1127 }
1128
1129 // copy the results out
1130 pf->numPlanes = numPlanes;
1131 pf->numFacets = numFacets;
1132 pf->facets = Hunk_Alloc( numFacets * sizeof( *pf->facets ), h_high );
1133 Com_Memcpy( pf->facets, facets, numFacets * sizeof( *pf->facets ) );
1134 pf->planes = Hunk_Alloc( numPlanes * sizeof( *pf->planes ), h_high );
1135 Com_Memcpy( pf->planes, planes, numPlanes * sizeof( *pf->planes ) );
1136 }
1137
1138
1139 /*
1140 ===================
1141 CM_GeneratePatchCollide
1142
1143 Creates an internal structure that will be used to perform
1144 collision detection with a patch mesh.
1145
1146 Points is packed as concatenated rows.
1147 ===================
1148 */
CM_GeneratePatchCollide(int width,int height,vec3_t * points)1149 struct patchCollide_s *CM_GeneratePatchCollide( int width, int height, vec3_t *points ) {
1150 patchCollide_t *pf;
1151 cGrid_t grid;
1152 int i, j;
1153
1154 if ( width <= 2 || height <= 2 || !points ) {
1155 Com_Error( ERR_DROP, "CM_GeneratePatchFacets: bad parameters: (%i, %i, %p)",
1156 width, height, (void *)points );
1157 }
1158
1159 if ( !(width & 1) || !(height & 1) ) {
1160 Com_Error( ERR_DROP, "CM_GeneratePatchFacets: even sizes are invalid for quadratic meshes" );
1161 }
1162
1163 if ( width > MAX_GRID_SIZE || height > MAX_GRID_SIZE ) {
1164 Com_Error( ERR_DROP, "CM_GeneratePatchFacets: source is > MAX_GRID_SIZE" );
1165 }
1166
1167 // build a grid
1168 grid.width = width;
1169 grid.height = height;
1170 grid.wrapWidth = qfalse;
1171 grid.wrapHeight = qfalse;
1172 for ( i = 0 ; i < width ; i++ ) {
1173 for ( j = 0 ; j < height ; j++ ) {
1174 VectorCopy( points[j*width + i], grid.points[i][j] );
1175 }
1176 }
1177
1178 // subdivide the grid
1179 CM_SetGridWrapWidth( &grid );
1180 CM_SubdivideGridColumns( &grid );
1181 CM_RemoveDegenerateColumns( &grid );
1182
1183 CM_TransposeGrid( &grid );
1184
1185 CM_SetGridWrapWidth( &grid );
1186 CM_SubdivideGridColumns( &grid );
1187 CM_RemoveDegenerateColumns( &grid );
1188
1189 // we now have a grid of points exactly on the curve
1190 // the aproximate surface defined by these points will be
1191 // collided against
1192 pf = Hunk_Alloc( sizeof( *pf ), h_high );
1193 ClearBounds( pf->bounds[0], pf->bounds[1] );
1194 for ( i = 0 ; i < grid.width ; i++ ) {
1195 for ( j = 0 ; j < grid.height ; j++ ) {
1196 AddPointToBounds( grid.points[i][j], pf->bounds[0], pf->bounds[1] );
1197 }
1198 }
1199
1200 c_totalPatchBlocks += ( grid.width - 1 ) * ( grid.height - 1 );
1201
1202 // generate a bsp tree for the surface
1203 CM_PatchCollideFromGrid( &grid, pf );
1204
1205 // expand by one unit for epsilon purposes
1206 pf->bounds[0][0] -= 1;
1207 pf->bounds[0][1] -= 1;
1208 pf->bounds[0][2] -= 1;
1209
1210 pf->bounds[1][0] += 1;
1211 pf->bounds[1][1] += 1;
1212 pf->bounds[1][2] += 1;
1213
1214 return pf;
1215 }
1216
1217 /*
1218 ================================================================================
1219
1220 TRACE TESTING
1221
1222 ================================================================================
1223 */
1224
1225 /*
1226 ====================
1227 CM_TracePointThroughPatchCollide
1228
1229 special case for point traces because the patch collide "brushes" have no volume
1230 ====================
1231 */
CM_TracePointThroughPatchCollide(traceWork_t * tw,const struct patchCollide_s * pc)1232 void CM_TracePointThroughPatchCollide( traceWork_t *tw, const struct patchCollide_s *pc ) {
1233 qboolean frontFacing[MAX_PATCH_PLANES];
1234 float intersection[MAX_PATCH_PLANES];
1235 float intersect;
1236 const patchPlane_t *planes;
1237 const facet_t *facet;
1238 int i, j, k;
1239 float offset;
1240 float d1, d2;
1241 #ifndef BSPC
1242 static cvar_t *cv;
1243 #endif //BSPC
1244
1245 #ifndef BSPC
1246 if ( !cm_playerCurveClip->integer || !tw->isPoint ) {
1247 return;
1248 }
1249 #endif
1250
1251 // determine the trace's relationship to all planes
1252 planes = pc->planes;
1253 for ( i = 0 ; i < pc->numPlanes ; i++, planes++ ) {
1254 offset = DotProduct( tw->offsets[ planes->signbits ], planes->plane );
1255 d1 = DotProduct( tw->start, planes->plane ) - planes->plane[3] + offset;
1256 d2 = DotProduct( tw->end, planes->plane ) - planes->plane[3] + offset;
1257 if ( d1 <= 0 ) {
1258 frontFacing[i] = qfalse;
1259 } else {
1260 frontFacing[i] = qtrue;
1261 }
1262 if ( d1 == d2 ) {
1263 intersection[i] = 99999;
1264 } else {
1265 intersection[i] = d1 / ( d1 - d2 );
1266 if ( intersection[i] <= 0 ) {
1267 intersection[i] = 99999;
1268 }
1269 }
1270 }
1271
1272
1273 // see if any of the surface planes are intersected
1274 facet = pc->facets;
1275 for ( i = 0 ; i < pc->numFacets ; i++, facet++ ) {
1276 if ( !frontFacing[facet->surfacePlane] ) {
1277 continue;
1278 }
1279 intersect = intersection[facet->surfacePlane];
1280 if ( intersect < 0 ) {
1281 continue; // surface is behind the starting point
1282 }
1283 if ( intersect > tw->trace.fraction ) {
1284 continue; // already hit something closer
1285 }
1286 for ( j = 0 ; j < facet->numBorders ; j++ ) {
1287 k = facet->borderPlanes[j];
1288 if ( frontFacing[k] ^ facet->borderInward[j] ) {
1289 if ( intersection[k] > intersect ) {
1290 break;
1291 }
1292 } else {
1293 if ( intersection[k] < intersect ) {
1294 break;
1295 }
1296 }
1297 }
1298 if ( j == facet->numBorders ) {
1299 // we hit this facet
1300 #ifndef BSPC
1301 if (!cv) {
1302 cv = Cvar_Get( "r_debugSurfaceUpdate", "1", 0 );
1303 }
1304 if (cv->integer) {
1305 debugPatchCollide = pc;
1306 debugFacet = facet;
1307 }
1308 #endif //BSPC
1309 planes = &pc->planes[facet->surfacePlane];
1310
1311 // calculate intersection with a slight pushoff
1312 offset = DotProduct( tw->offsets[ planes->signbits ], planes->plane );
1313 d1 = DotProduct( tw->start, planes->plane ) - planes->plane[3] + offset;
1314 d2 = DotProduct( tw->end, planes->plane ) - planes->plane[3] + offset;
1315 tw->trace.fraction = ( d1 - SURFACE_CLIP_EPSILON ) / ( d1 - d2 );
1316
1317 if ( tw->trace.fraction < 0 ) {
1318 tw->trace.fraction = 0;
1319 }
1320
1321 VectorCopy( planes->plane, tw->trace.plane.normal );
1322 tw->trace.plane.dist = planes->plane[3];
1323 }
1324 }
1325 }
1326
1327 /*
1328 ====================
1329 CM_CheckFacetPlane
1330 ====================
1331 */
CM_CheckFacetPlane(float * plane,vec3_t start,vec3_t end,float * enterFrac,float * leaveFrac,int * hit)1332 int CM_CheckFacetPlane(float *plane, vec3_t start, vec3_t end, float *enterFrac, float *leaveFrac, int *hit) {
1333 float d1, d2, f;
1334
1335 *hit = qfalse;
1336
1337 d1 = DotProduct( start, plane ) - plane[3];
1338 d2 = DotProduct( end, plane ) - plane[3];
1339
1340 // if completely in front of face, no intersection with the entire facet
1341 if (d1 > 0 && ( d2 >= SURFACE_CLIP_EPSILON || d2 >= d1 ) ) {
1342 return qfalse;
1343 }
1344
1345 // if it doesn't cross the plane, the plane isn't relevent
1346 if (d1 <= 0 && d2 <= 0 ) {
1347 return qtrue;
1348 }
1349
1350 // crosses face
1351 if (d1 > d2) { // enter
1352 f = (d1-SURFACE_CLIP_EPSILON) / (d1-d2);
1353 if ( f < 0 ) {
1354 f = 0;
1355 }
1356 //always favor previous plane hits and thus also the surface plane hit
1357 if (f > *enterFrac) {
1358 *enterFrac = f;
1359 *hit = qtrue;
1360 }
1361 } else { // leave
1362 f = (d1+SURFACE_CLIP_EPSILON) / (d1-d2);
1363 if ( f > 1 ) {
1364 f = 1;
1365 }
1366 if (f < *leaveFrac) {
1367 *leaveFrac = f;
1368 }
1369 }
1370 return qtrue;
1371 }
1372
1373 /*
1374 ====================
1375 CM_TraceThroughPatchCollide
1376 ====================
1377 */
CM_TraceThroughPatchCollide(traceWork_t * tw,const struct patchCollide_s * pc)1378 void CM_TraceThroughPatchCollide( traceWork_t *tw, const struct patchCollide_s *pc ) {
1379 int i, j, hit, hitnum;
1380 float offset, enterFrac, leaveFrac, t;
1381 patchPlane_t *planes;
1382 facet_t *facet;
1383 float plane[4] = {0, 0, 0, 0}, bestplane[4] = {0, 0, 0, 0};
1384 vec3_t startp, endp;
1385 #ifndef BSPC
1386 static cvar_t *cv;
1387 #endif //BSPC
1388
1389 if ( !CM_BoundsIntersect( tw->bounds[0], tw->bounds[1],
1390 pc->bounds[0], pc->bounds[1] ) ) {
1391 return;
1392 }
1393
1394 if (tw->isPoint) {
1395 CM_TracePointThroughPatchCollide( tw, pc );
1396 return;
1397 }
1398
1399 facet = pc->facets;
1400 for ( i = 0 ; i < pc->numFacets ; i++, facet++ ) {
1401 enterFrac = -1.0;
1402 leaveFrac = 1.0;
1403 hitnum = -1;
1404 //
1405 planes = &pc->planes[ facet->surfacePlane ];
1406 VectorCopy(planes->plane, plane);
1407 plane[3] = planes->plane[3];
1408 if ( tw->sphere.use ) {
1409 // adjust the plane distance apropriately for radius
1410 plane[3] += tw->sphere.radius;
1411
1412 // find the closest point on the capsule to the plane
1413 t = DotProduct( plane, tw->sphere.offset );
1414 if ( t > 0.0f ) {
1415 VectorSubtract( tw->start, tw->sphere.offset, startp );
1416 VectorSubtract( tw->end, tw->sphere.offset, endp );
1417 }
1418 else {
1419 VectorAdd( tw->start, tw->sphere.offset, startp );
1420 VectorAdd( tw->end, tw->sphere.offset, endp );
1421 }
1422 }
1423 else {
1424 offset = DotProduct( tw->offsets[ planes->signbits ], plane);
1425 plane[3] -= offset;
1426 VectorCopy( tw->start, startp );
1427 VectorCopy( tw->end, endp );
1428 }
1429
1430 if (!CM_CheckFacetPlane(plane, startp, endp, &enterFrac, &leaveFrac, &hit)) {
1431 continue;
1432 }
1433 if (hit) {
1434 Vector4Copy(plane, bestplane);
1435 }
1436
1437 for ( j = 0; j < facet->numBorders; j++ ) {
1438 planes = &pc->planes[ facet->borderPlanes[j] ];
1439 if (facet->borderInward[j]) {
1440 VectorNegate(planes->plane, plane);
1441 plane[3] = -planes->plane[3];
1442 }
1443 else {
1444 VectorCopy(planes->plane, plane);
1445 plane[3] = planes->plane[3];
1446 }
1447 if ( tw->sphere.use ) {
1448 // adjust the plane distance apropriately for radius
1449 plane[3] += tw->sphere.radius;
1450
1451 // find the closest point on the capsule to the plane
1452 t = DotProduct( plane, tw->sphere.offset );
1453 if ( t > 0.0f ) {
1454 VectorSubtract( tw->start, tw->sphere.offset, startp );
1455 VectorSubtract( tw->end, tw->sphere.offset, endp );
1456 }
1457 else {
1458 VectorAdd( tw->start, tw->sphere.offset, startp );
1459 VectorAdd( tw->end, tw->sphere.offset, endp );
1460 }
1461 }
1462 else {
1463 // NOTE: this works even though the plane might be flipped because the bbox is centered
1464 offset = DotProduct( tw->offsets[ planes->signbits ], plane);
1465 plane[3] += fabs(offset);
1466 VectorCopy( tw->start, startp );
1467 VectorCopy( tw->end, endp );
1468 }
1469
1470 if (!CM_CheckFacetPlane(plane, startp, endp, &enterFrac, &leaveFrac, &hit)) {
1471 break;
1472 }
1473 if (hit) {
1474 hitnum = j;
1475 Vector4Copy(plane, bestplane);
1476 }
1477 }
1478 if (j < facet->numBorders) continue;
1479 //never clip against the back side
1480 if (hitnum == facet->numBorders - 1) continue;
1481
1482 if (enterFrac < leaveFrac && enterFrac >= 0) {
1483 if (enterFrac < tw->trace.fraction) {
1484 if (enterFrac < 0) {
1485 enterFrac = 0;
1486 }
1487 #ifndef BSPC
1488 if (!cv) {
1489 cv = Cvar_Get( "r_debugSurfaceUpdate", "1", 0 );
1490 }
1491 if (cv && cv->integer) {
1492 debugPatchCollide = pc;
1493 debugFacet = facet;
1494 }
1495 #endif //BSPC
1496
1497 tw->trace.fraction = enterFrac;
1498 VectorCopy( bestplane, tw->trace.plane.normal );
1499 tw->trace.plane.dist = bestplane[3];
1500 }
1501 }
1502 }
1503 }
1504
1505
1506 /*
1507 =======================================================================
1508
1509 POSITION TEST
1510
1511 =======================================================================
1512 */
1513
1514 /*
1515 ====================
1516 CM_PositionTestInPatchCollide
1517 ====================
1518 */
CM_PositionTestInPatchCollide(traceWork_t * tw,const struct patchCollide_s * pc)1519 qboolean CM_PositionTestInPatchCollide( traceWork_t *tw, const struct patchCollide_s *pc ) {
1520 int i, j;
1521 float offset, t;
1522 patchPlane_t *planes;
1523 facet_t *facet;
1524 float plane[4];
1525 vec3_t startp;
1526
1527 if (tw->isPoint) {
1528 return qfalse;
1529 }
1530 //
1531 facet = pc->facets;
1532 for ( i = 0 ; i < pc->numFacets ; i++, facet++ ) {
1533 planes = &pc->planes[ facet->surfacePlane ];
1534 VectorCopy(planes->plane, plane);
1535 plane[3] = planes->plane[3];
1536 if ( tw->sphere.use ) {
1537 // adjust the plane distance apropriately for radius
1538 plane[3] += tw->sphere.radius;
1539
1540 // find the closest point on the capsule to the plane
1541 t = DotProduct( plane, tw->sphere.offset );
1542 if ( t > 0 ) {
1543 VectorSubtract( tw->start, tw->sphere.offset, startp );
1544 }
1545 else {
1546 VectorAdd( tw->start, tw->sphere.offset, startp );
1547 }
1548 }
1549 else {
1550 offset = DotProduct( tw->offsets[ planes->signbits ], plane);
1551 plane[3] -= offset;
1552 VectorCopy( tw->start, startp );
1553 }
1554
1555 if ( DotProduct( plane, startp ) - plane[3] > 0.0f ) {
1556 continue;
1557 }
1558
1559 for ( j = 0; j < facet->numBorders; j++ ) {
1560 planes = &pc->planes[ facet->borderPlanes[j] ];
1561 if (facet->borderInward[j]) {
1562 VectorNegate(planes->plane, plane);
1563 plane[3] = -planes->plane[3];
1564 }
1565 else {
1566 VectorCopy(planes->plane, plane);
1567 plane[3] = planes->plane[3];
1568 }
1569 if ( tw->sphere.use ) {
1570 // adjust the plane distance apropriately for radius
1571 plane[3] += tw->sphere.radius;
1572
1573 // find the closest point on the capsule to the plane
1574 t = DotProduct( plane, tw->sphere.offset );
1575 if ( t > 0.0f ) {
1576 VectorSubtract( tw->start, tw->sphere.offset, startp );
1577 }
1578 else {
1579 VectorAdd( tw->start, tw->sphere.offset, startp );
1580 }
1581 }
1582 else {
1583 // NOTE: this works even though the plane might be flipped because the bbox is centered
1584 offset = DotProduct( tw->offsets[ planes->signbits ], plane);
1585 plane[3] += fabs(offset);
1586 VectorCopy( tw->start, startp );
1587 }
1588
1589 if ( DotProduct( plane, startp ) - plane[3] > 0.0f ) {
1590 break;
1591 }
1592 }
1593 if (j < facet->numBorders) {
1594 continue;
1595 }
1596 // inside this patch facet
1597 return qtrue;
1598 }
1599 return qfalse;
1600 }
1601
1602 /*
1603 =======================================================================
1604
1605 DEBUGGING
1606
1607 =======================================================================
1608 */
1609
1610
1611 /*
1612 ==================
1613 CM_DrawDebugSurface
1614
1615 Called from the renderer
1616 ==================
1617 */
1618 #ifndef BSPC
1619 void BotDrawDebugPolygons(void (*drawPoly)(int color, int numPoints, float *points), int value);
1620 #endif
1621
CM_DrawDebugSurface(void (* drawPoly)(int color,int numPoints,float * points))1622 void CM_DrawDebugSurface( void (*drawPoly)(int color, int numPoints, float *points) ) {
1623 static cvar_t *cv;
1624 #ifndef BSPC
1625 static cvar_t *cv2;
1626 #endif
1627 const patchCollide_t *pc;
1628 facet_t *facet;
1629 winding_t *w;
1630 int i, j, k, n;
1631 int curplanenum, planenum, curinward, inward;
1632 float plane[4];
1633 vec3_t mins = {-15, -15, -28}, maxs = {15, 15, 28};
1634 //vec3_t mins = {0, 0, 0}, maxs = {0, 0, 0};
1635 vec3_t v1, v2;
1636
1637 #ifndef BSPC
1638 if ( !cv2 )
1639 {
1640 cv2 = Cvar_Get( "r_debugSurface", "0", 0 );
1641 }
1642
1643 if (cv2->integer != 1)
1644 {
1645 BotDrawDebugPolygons(drawPoly, cv2->integer);
1646 return;
1647 }
1648 #endif
1649
1650 if ( !debugPatchCollide ) {
1651 return;
1652 }
1653
1654 #ifndef BSPC
1655 if ( !cv ) {
1656 cv = Cvar_Get( "cm_debugSize", "2", 0 );
1657 }
1658 #endif
1659 pc = debugPatchCollide;
1660
1661 for ( i = 0, facet = pc->facets ; i < pc->numFacets ; i++, facet++ ) {
1662
1663 for ( k = 0 ; k < facet->numBorders + 1; k++ ) {
1664 //
1665 if (k < facet->numBorders) {
1666 planenum = facet->borderPlanes[k];
1667 inward = facet->borderInward[k];
1668 }
1669 else {
1670 planenum = facet->surfacePlane;
1671 inward = qfalse;
1672 //continue;
1673 }
1674
1675 Vector4Copy( pc->planes[ planenum ].plane, plane );
1676
1677 //planenum = facet->surfacePlane;
1678 if ( inward ) {
1679 VectorSubtract( vec3_origin, plane, plane );
1680 plane[3] = -plane[3];
1681 }
1682
1683 plane[3] += cv->value;
1684 //*
1685 for (n = 0; n < 3; n++)
1686 {
1687 if (plane[n] > 0) v1[n] = maxs[n];
1688 else v1[n] = mins[n];
1689 } //end for
1690 VectorNegate(plane, v2);
1691 plane[3] += fabs(DotProduct(v1, v2));
1692 //*/
1693
1694 w = BaseWindingForPlane( plane, plane[3] );
1695 for ( j = 0 ; j < facet->numBorders + 1 && w; j++ ) {
1696 //
1697 if (j < facet->numBorders) {
1698 curplanenum = facet->borderPlanes[j];
1699 curinward = facet->borderInward[j];
1700 }
1701 else {
1702 curplanenum = facet->surfacePlane;
1703 curinward = qfalse;
1704 //continue;
1705 }
1706 //
1707 if (curplanenum == planenum) continue;
1708
1709 Vector4Copy( pc->planes[ curplanenum ].plane, plane );
1710 if ( !curinward ) {
1711 VectorSubtract( vec3_origin, plane, plane );
1712 plane[3] = -plane[3];
1713 }
1714 // if ( !facet->borderNoAdjust[j] ) {
1715 plane[3] -= cv->value;
1716 // }
1717 for (n = 0; n < 3; n++)
1718 {
1719 if (plane[n] > 0) v1[n] = maxs[n];
1720 else v1[n] = mins[n];
1721 } //end for
1722 VectorNegate(plane, v2);
1723 plane[3] -= fabs(DotProduct(v1, v2));
1724
1725 ChopWindingInPlace( &w, plane, plane[3], 0.1f );
1726 }
1727 if ( w ) {
1728 if ( facet == debugFacet ) {
1729 drawPoly( 4, w->numpoints, w->p[0] );
1730 //Com_Printf("blue facet has %d border planes\n", facet->numBorders);
1731 } else {
1732 drawPoly( 1, w->numpoints, w->p[0] );
1733 }
1734 FreeWinding( w );
1735 }
1736 else
1737 Com_Printf("winding chopped away by border planes\n");
1738 }
1739 }
1740
1741 // draw the debug block
1742 {
1743 vec3_t v[3];
1744
1745 VectorCopy( debugBlockPoints[0], v[0] );
1746 VectorCopy( debugBlockPoints[1], v[1] );
1747 VectorCopy( debugBlockPoints[2], v[2] );
1748 drawPoly( 2, 3, v[0] );
1749
1750 VectorCopy( debugBlockPoints[2], v[0] );
1751 VectorCopy( debugBlockPoints[3], v[1] );
1752 VectorCopy( debugBlockPoints[0], v[2] );
1753 drawPoly( 2, 3, v[0] );
1754 }
1755
1756 #if 0
1757 vec3_t v[4];
1758
1759 v[0][0] = pc->bounds[1][0];
1760 v[0][1] = pc->bounds[1][1];
1761 v[0][2] = pc->bounds[1][2];
1762
1763 v[1][0] = pc->bounds[1][0];
1764 v[1][1] = pc->bounds[0][1];
1765 v[1][2] = pc->bounds[1][2];
1766
1767 v[2][0] = pc->bounds[0][0];
1768 v[2][1] = pc->bounds[0][1];
1769 v[2][2] = pc->bounds[1][2];
1770
1771 v[3][0] = pc->bounds[0][0];
1772 v[3][1] = pc->bounds[1][1];
1773 v[3][2] = pc->bounds[1][2];
1774
1775 drawPoly( 4, v[0] );
1776 #endif
1777 }
1778