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