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 #include "cm_local.h"
23
24 // always use bbox vs. bbox collision and never capsule vs. bbox or vice versa
25 //#define ALWAYS_BBOX_VS_BBOX
26 // always use capsule vs. capsule collision and never capsule vs. bbox or vice versa
27 //#define ALWAYS_CAPSULE_VS_CAPSULE
28
29 //#define CAPSULE_DEBUG
30
31 /*
32 ===============================================================================
33
34 BASIC MATH
35
36 ===============================================================================
37 */
38
39 /*
40 ================
41 RotatePoint
42 ================
43 */
RotatePoint(vec3_t point,vec3_t matrix[3])44 void RotatePoint(vec3_t point, /*const*/ vec3_t matrix[3]) { // FIXME
45 vec3_t tvec;
46
47 VectorCopy(point, tvec);
48 point[0] = DotProduct(matrix[0], tvec);
49 point[1] = DotProduct(matrix[1], tvec);
50 point[2] = DotProduct(matrix[2], tvec);
51 }
52
53 /*
54 ================
55 TransposeMatrix
56 ================
57 */
TransposeMatrix(vec3_t matrix[3],vec3_t transpose[3])58 void TransposeMatrix(/*const*/ vec3_t matrix[3], vec3_t transpose[3]) { // FIXME
59 int i, j;
60 for (i = 0; i < 3; i++) {
61 for (j = 0; j < 3; j++) {
62 transpose[i][j] = matrix[j][i];
63 }
64 }
65 }
66
67 /*
68 ================
69 CreateRotationMatrix
70 ================
71 */
CreateRotationMatrix(const vec3_t angles,vec3_t matrix[3])72 void CreateRotationMatrix(const vec3_t angles, vec3_t matrix[3]) {
73 AngleVectors(angles, matrix[0], matrix[1], matrix[2]);
74 VectorInverse(matrix[1]);
75 }
76
77 /*
78 ================
79 CM_ProjectPointOntoVector
80 ================
81 */
CM_ProjectPointOntoVector(vec3_t point,vec3_t vStart,vec3_t vDir,vec3_t vProj)82 void CM_ProjectPointOntoVector( vec3_t point, vec3_t vStart, vec3_t vDir, vec3_t vProj )
83 {
84 vec3_t pVec;
85
86 VectorSubtract( point, vStart, pVec );
87 // project onto the directional vector for this segment
88 VectorMA( vStart, DotProduct( pVec, vDir ), vDir, vProj );
89 }
90
91 /*
92 ================
93 CM_DistanceFromLineSquared
94 ================
95 */
CM_DistanceFromLineSquared(vec3_t p,vec3_t lp1,vec3_t lp2,vec3_t dir)96 float CM_DistanceFromLineSquared(vec3_t p, vec3_t lp1, vec3_t lp2, vec3_t dir) {
97 vec3_t proj, t;
98 int j;
99
100 CM_ProjectPointOntoVector(p, lp1, dir, proj);
101 for (j = 0; j < 3; j++)
102 if ((proj[j] > lp1[j] && proj[j] > lp2[j]) ||
103 (proj[j] < lp1[j] && proj[j] < lp2[j]))
104 break;
105 if (j < 3) {
106 if (fabs(proj[j] - lp1[j]) < fabs(proj[j] - lp2[j]))
107 VectorSubtract(p, lp1, t);
108 else
109 VectorSubtract(p, lp2, t);
110 return VectorLengthSquared(t);
111 }
112 VectorSubtract(p, proj, t);
113 return VectorLengthSquared(t);
114 }
115
116 /*
117 ================
118 CM_VectorDistanceSquared
119 ================
120 */
CM_VectorDistanceSquared(vec3_t p1,vec3_t p2)121 float CM_VectorDistanceSquared(vec3_t p1, vec3_t p2) {
122 vec3_t dir;
123
124 VectorSubtract(p2, p1, dir);
125 return VectorLengthSquared(dir);
126 }
127
128 /*
129 ================
130 SquareRootFloat
131 ================
132 */
SquareRootFloat(float number)133 float SquareRootFloat(float number) {
134 union {
135 float f;
136 int i;
137 } t;
138 float x, y;
139 const float f = 1.5F;
140
141 x = number * 0.5F;
142 t.f = number;
143 t.i = 0x5f3759df - ( t.i >> 1 );
144 y = t.f;
145 y = y * ( f - ( x * y * y ) );
146 y = y * ( f - ( x * y * y ) );
147 return number * y;
148 }
149
150
151 /*
152 ===============================================================================
153
154 POSITION TESTING
155
156 ===============================================================================
157 */
158
159 /*
160 ================
161 CM_TestBoxInBrush
162 ================
163 */
CM_TestBoxInBrush(traceWork_t * tw,cbrush_t * brush)164 void CM_TestBoxInBrush( traceWork_t *tw, cbrush_t *brush ) {
165 int i;
166 cplane_t *plane;
167 float dist;
168 float d1;
169 cbrushside_t *side;
170 float t;
171 vec3_t startp;
172
173 if (!brush->numsides) {
174 return;
175 }
176
177 // special test for axial
178 if ( tw->bounds[0][0] > brush->bounds[1][0]
179 || tw->bounds[0][1] > brush->bounds[1][1]
180 || tw->bounds[0][2] > brush->bounds[1][2]
181 || tw->bounds[1][0] < brush->bounds[0][0]
182 || tw->bounds[1][1] < brush->bounds[0][1]
183 || tw->bounds[1][2] < brush->bounds[0][2]
184 ) {
185 return;
186 }
187
188 if ( tw->sphere.use ) {
189 // the first six planes are the axial planes, so we only
190 // need to test the remainder
191 for ( i = 6 ; i < brush->numsides ; i++ ) {
192 side = brush->sides + i;
193 plane = side->plane;
194
195 // adjust the plane distance apropriately for radius
196 dist = plane->dist + tw->sphere.radius;
197 // find the closest point on the capsule to the plane
198 t = DotProduct( plane->normal, tw->sphere.offset );
199 if ( t > 0 )
200 {
201 VectorSubtract( tw->start, tw->sphere.offset, startp );
202 }
203 else
204 {
205 VectorAdd( tw->start, tw->sphere.offset, startp );
206 }
207 d1 = DotProduct( startp, plane->normal ) - dist;
208 // if completely in front of face, no intersection
209 if ( d1 > 0 ) {
210 return;
211 }
212 }
213 } else {
214 // the first six planes are the axial planes, so we only
215 // need to test the remainder
216 for ( i = 6 ; i < brush->numsides ; i++ ) {
217 side = brush->sides + i;
218 plane = side->plane;
219
220 // adjust the plane distance apropriately for mins/maxs
221 dist = plane->dist - DotProduct( tw->offsets[ plane->signbits ], plane->normal );
222
223 d1 = DotProduct( tw->start, plane->normal ) - dist;
224
225 // if completely in front of face, no intersection
226 if ( d1 > 0 ) {
227 return;
228 }
229 }
230 }
231
232 // inside this brush
233 tw->trace.startsolid = tw->trace.allsolid = qtrue;
234 tw->trace.fraction = 0;
235 tw->trace.contents = brush->contents;
236 }
237
238
239
240 /*
241 ================
242 CM_TestInLeaf
243 ================
244 */
CM_TestInLeaf(traceWork_t * tw,cLeaf_t * leaf)245 void CM_TestInLeaf( traceWork_t *tw, cLeaf_t *leaf ) {
246 int k;
247 int brushnum;
248 cbrush_t *b;
249 cPatch_t *patch;
250
251 // test box position against all brushes in the leaf
252 for (k=0 ; k<leaf->numLeafBrushes ; k++) {
253 brushnum = cm.leafbrushes[leaf->firstLeafBrush+k];
254 b = &cm.brushes[brushnum];
255 if (b->checkcount == cm.checkcount) {
256 continue; // already checked this brush in another leaf
257 }
258 b->checkcount = cm.checkcount;
259
260 if ( !(b->contents & tw->contents)) {
261 continue;
262 }
263
264 CM_TestBoxInBrush( tw, b );
265 if ( tw->trace.allsolid ) {
266 return;
267 }
268 }
269
270 // test against all patches
271 #ifdef BSPC
272 if (1) {
273 #else
274 if ( !cm_noCurves->integer ) {
275 #endif //BSPC
276 for ( k = 0 ; k < leaf->numLeafSurfaces ; k++ ) {
277 patch = cm.surfaces[ cm.leafsurfaces[ leaf->firstLeafSurface + k ] ];
278 if ( !patch ) {
279 continue;
280 }
281 if ( patch->checkcount == cm.checkcount ) {
282 continue; // already checked this brush in another leaf
283 }
284 patch->checkcount = cm.checkcount;
285
286 if ( !(patch->contents & tw->contents)) {
287 continue;
288 }
289
290 if ( CM_PositionTestInPatchCollide( tw, patch->pc ) ) {
291 tw->trace.startsolid = tw->trace.allsolid = qtrue;
292 tw->trace.fraction = 0;
293 tw->trace.contents = patch->contents;
294 return;
295 }
296 }
297 }
298 }
299
300 /*
301 ==================
302 CM_TestCapsuleInCapsule
303
304 capsule inside capsule check
305 ==================
306 */
307 void CM_TestCapsuleInCapsule( traceWork_t *tw, clipHandle_t model ) {
308 int i;
309 vec3_t mins, maxs;
310 vec3_t top, bottom;
311 vec3_t p1, p2, tmp;
312 vec3_t offset, symetricSize[2];
313 float radius, halfwidth, halfheight, offs, r;
314
315 CM_ModelBounds(model, mins, maxs);
316
317 VectorAdd(tw->start, tw->sphere.offset, top);
318 VectorSubtract(tw->start, tw->sphere.offset, bottom);
319 for ( i = 0 ; i < 3 ; i++ ) {
320 offset[i] = ( mins[i] + maxs[i] ) * 0.5;
321 symetricSize[0][i] = mins[i] - offset[i];
322 symetricSize[1][i] = maxs[i] - offset[i];
323 }
324 halfwidth = symetricSize[ 1 ][ 0 ];
325 halfheight = symetricSize[ 1 ][ 2 ];
326 radius = ( halfwidth > halfheight ) ? halfheight : halfwidth;
327 offs = halfheight - radius;
328
329 r = Square(tw->sphere.radius + radius);
330 // check if any of the spheres overlap
331 VectorCopy(offset, p1);
332 p1[2] += offs;
333 VectorSubtract(p1, top, tmp);
334 if ( VectorLengthSquared(tmp) < r ) {
335 tw->trace.startsolid = tw->trace.allsolid = qtrue;
336 tw->trace.fraction = 0;
337 }
338 VectorSubtract(p1, bottom, tmp);
339 if ( VectorLengthSquared(tmp) < r ) {
340 tw->trace.startsolid = tw->trace.allsolid = qtrue;
341 tw->trace.fraction = 0;
342 }
343 VectorCopy(offset, p2);
344 p2[2] -= offs;
345 VectorSubtract(p2, top, tmp);
346 if ( VectorLengthSquared(tmp) < r ) {
347 tw->trace.startsolid = tw->trace.allsolid = qtrue;
348 tw->trace.fraction = 0;
349 }
350 VectorSubtract(p2, bottom, tmp);
351 if ( VectorLengthSquared(tmp) < r ) {
352 tw->trace.startsolid = tw->trace.allsolid = qtrue;
353 tw->trace.fraction = 0;
354 }
355 // if between cylinder up and lower bounds
356 if ( (top[2] >= p1[2] && top[2] <= p2[2]) ||
357 (bottom[2] >= p1[2] && bottom[2] <= p2[2]) ) {
358 // 2d coordinates
359 top[2] = p1[2] = 0;
360 // if the cylinders overlap
361 VectorSubtract(top, p1, tmp);
362 if ( VectorLengthSquared(tmp) < r ) {
363 tw->trace.startsolid = tw->trace.allsolid = qtrue;
364 tw->trace.fraction = 0;
365 }
366 }
367 }
368
369 /*
370 ==================
371 CM_TestBoundingBoxInCapsule
372
373 bounding box inside capsule check
374 ==================
375 */
376 void CM_TestBoundingBoxInCapsule( traceWork_t *tw, clipHandle_t model ) {
377 vec3_t mins, maxs, offset, size[2];
378 clipHandle_t h;
379 cmodel_t *cmod;
380 int i;
381
382 // mins maxs of the capsule
383 CM_ModelBounds(model, mins, maxs);
384
385 // offset for capsule center
386 for ( i = 0 ; i < 3 ; i++ ) {
387 offset[i] = ( mins[i] + maxs[i] ) * 0.5;
388 size[0][i] = mins[i] - offset[i];
389 size[1][i] = maxs[i] - offset[i];
390 tw->start[i] -= offset[i];
391 tw->end[i] -= offset[i];
392 }
393
394 // replace the bounding box with the capsule
395 tw->sphere.use = qtrue;
396 tw->sphere.radius = ( size[1][0] > size[1][2] ) ? size[1][2]: size[1][0];
397 tw->sphere.halfheight = size[1][2];
398 VectorSet( tw->sphere.offset, 0, 0, size[1][2] - tw->sphere.radius );
399
400 // replace the capsule with the bounding box
401 h = CM_TempBoxModel(tw->size[0], tw->size[1], qfalse);
402 // calculate collision
403 cmod = CM_ClipHandleToModel( h );
404 CM_TestInLeaf( tw, &cmod->leaf );
405 }
406
407 /*
408 ==================
409 CM_PositionTest
410 ==================
411 */
412 #define MAX_POSITION_LEAFS 1024
413 void CM_PositionTest( traceWork_t *tw ) {
414 int leafs[MAX_POSITION_LEAFS];
415 int i;
416 leafList_t ll;
417
418 // identify the leafs we are touching
419 VectorAdd( tw->start, tw->size[0], ll.bounds[0] );
420 VectorAdd( tw->start, tw->size[1], ll.bounds[1] );
421
422 for (i=0 ; i<3 ; i++) {
423 ll.bounds[0][i] -= 1;
424 ll.bounds[1][i] += 1;
425 }
426
427 ll.count = 0;
428 ll.maxcount = MAX_POSITION_LEAFS;
429 ll.list = leafs;
430 ll.storeLeafs = CM_StoreLeafs;
431 ll.lastLeaf = 0;
432 ll.overflowed = qfalse;
433
434 cm.checkcount++;
435
436 CM_BoxLeafnums_r( &ll, 0 );
437
438
439 cm.checkcount++;
440
441 // test the contents of the leafs
442 for (i=0 ; i < ll.count ; i++) {
443 CM_TestInLeaf( tw, &cm.leafs[leafs[i]] );
444 if ( tw->trace.allsolid ) {
445 break;
446 }
447 }
448 }
449
450 /*
451 ===============================================================================
452
453 TRACING
454
455 ===============================================================================
456 */
457
458
459 /*
460 ================
461 CM_TraceThroughPatch
462 ================
463 */
464
465 void CM_TraceThroughPatch( traceWork_t *tw, cPatch_t *patch ) {
466 float oldFrac;
467
468 c_patch_traces++;
469
470 oldFrac = tw->trace.fraction;
471
472 CM_TraceThroughPatchCollide( tw, patch->pc );
473
474 if ( tw->trace.fraction < oldFrac ) {
475 tw->trace.surfaceFlags = patch->surfaceFlags;
476 tw->trace.contents = patch->contents;
477 }
478 }
479
480 /*
481 ================
482 CM_TraceThroughBrush
483 ================
484 */
485 void CM_TraceThroughBrush( traceWork_t *tw, cbrush_t *brush ) {
486 int i;
487 cplane_t *plane, *clipplane;
488 float dist;
489 float enterFrac, leaveFrac;
490 float d1, d2;
491 qboolean getout, startout;
492 float f;
493 cbrushside_t *side, *leadside;
494 float t;
495 vec3_t startp;
496 vec3_t endp;
497
498 enterFrac = -1.0;
499 leaveFrac = 1.0;
500 clipplane = NULL;
501
502 if ( !brush->numsides ) {
503 return;
504 }
505
506 c_brush_traces++;
507
508 getout = qfalse;
509 startout = qfalse;
510
511 leadside = NULL;
512
513 if ( tw->sphere.use ) {
514 //
515 // compare the trace against all planes of the brush
516 // find the latest time the trace crosses a plane towards the interior
517 // and the earliest time the trace crosses a plane towards the exterior
518 //
519 for (i = 0; i < brush->numsides; i++) {
520 side = brush->sides + i;
521 plane = side->plane;
522
523 // adjust the plane distance apropriately for radius
524 dist = plane->dist + tw->sphere.radius;
525
526 // find the closest point on the capsule to the plane
527 t = DotProduct( plane->normal, tw->sphere.offset );
528 if ( t > 0 )
529 {
530 VectorSubtract( tw->start, tw->sphere.offset, startp );
531 VectorSubtract( tw->end, tw->sphere.offset, endp );
532 }
533 else
534 {
535 VectorAdd( tw->start, tw->sphere.offset, startp );
536 VectorAdd( tw->end, tw->sphere.offset, endp );
537 }
538
539 d1 = DotProduct( startp, plane->normal ) - dist;
540 d2 = DotProduct( endp, plane->normal ) - dist;
541
542 if (d2 > 0) {
543 getout = qtrue; // endpoint is not in solid
544 }
545 if (d1 > 0) {
546 startout = qtrue;
547 }
548
549 // if completely in front of face, no intersection with the entire brush
550 if (d1 > 0 && ( d2 >= SURFACE_CLIP_EPSILON || d2 >= d1 ) ) {
551 return;
552 }
553
554 // if it doesn't cross the plane, the plane isn't relevent
555 if (d1 <= 0 && d2 <= 0 ) {
556 continue;
557 }
558
559 // crosses face
560 if (d1 > d2) { // enter
561 f = (d1-SURFACE_CLIP_EPSILON) / (d1-d2);
562 if ( f < 0 ) {
563 f = 0;
564 }
565 if (f > enterFrac) {
566 enterFrac = f;
567 clipplane = plane;
568 leadside = side;
569 }
570 } else { // leave
571 f = (d1+SURFACE_CLIP_EPSILON) / (d1-d2);
572 if ( f > 1 ) {
573 f = 1;
574 }
575 if (f < leaveFrac) {
576 leaveFrac = f;
577 }
578 }
579 }
580 } else {
581 //
582 // compare the trace against all planes of the brush
583 // find the latest time the trace crosses a plane towards the interior
584 // and the earliest time the trace crosses a plane towards the exterior
585 //
586 for (i = 0; i < brush->numsides; i++) {
587 side = brush->sides + i;
588 plane = side->plane;
589
590 // adjust the plane distance apropriately for mins/maxs
591 dist = plane->dist - DotProduct( tw->offsets[ plane->signbits ], plane->normal );
592
593 d1 = DotProduct( tw->start, plane->normal ) - dist;
594 d2 = DotProduct( tw->end, plane->normal ) - dist;
595
596 if (d2 > 0) {
597 getout = qtrue; // endpoint is not in solid
598 }
599 if (d1 > 0) {
600 startout = qtrue;
601 }
602
603 // if completely in front of face, no intersection with the entire brush
604 if (d1 > 0 && ( d2 >= SURFACE_CLIP_EPSILON || d2 >= d1 ) ) {
605 return;
606 }
607
608 // if it doesn't cross the plane, the plane isn't relevent
609 if (d1 <= 0 && d2 <= 0 ) {
610 continue;
611 }
612
613 // crosses face
614 if (d1 > d2) { // enter
615 f = (d1-SURFACE_CLIP_EPSILON) / (d1-d2);
616 if ( f < 0 ) {
617 f = 0;
618 }
619 if (f > enterFrac) {
620 enterFrac = f;
621 clipplane = plane;
622 leadside = side;
623 }
624 } else { // leave
625 f = (d1+SURFACE_CLIP_EPSILON) / (d1-d2);
626 if ( f > 1 ) {
627 f = 1;
628 }
629 if (f < leaveFrac) {
630 leaveFrac = f;
631 }
632 }
633 }
634 }
635
636 //
637 // all planes have been checked, and the trace was not
638 // completely outside the brush
639 //
640 if (!startout) { // original point was inside brush
641 tw->trace.startsolid = qtrue;
642 if (!getout) {
643 tw->trace.allsolid = qtrue;
644 tw->trace.fraction = 0;
645 tw->trace.contents = brush->contents;
646 }
647 return;
648 }
649
650 if (enterFrac < leaveFrac) {
651 if (enterFrac > -1 && enterFrac < tw->trace.fraction) {
652 if (enterFrac < 0) {
653 enterFrac = 0;
654 }
655 tw->trace.fraction = enterFrac;
656 tw->trace.plane = *clipplane;
657 tw->trace.surfaceFlags = leadside->surfaceFlags;
658 tw->trace.contents = brush->contents;
659 }
660 }
661 }
662
663 /*
664 ================
665 CM_TraceThroughLeaf
666 ================
667 */
668 void CM_TraceThroughLeaf( traceWork_t *tw, cLeaf_t *leaf ) {
669 int k;
670 int brushnum;
671 cbrush_t *b;
672 cPatch_t *patch;
673
674 // trace line against all brushes in the leaf
675 for ( k = 0 ; k < leaf->numLeafBrushes ; k++ ) {
676 brushnum = cm.leafbrushes[leaf->firstLeafBrush+k];
677
678 b = &cm.brushes[brushnum];
679 if ( b->checkcount == cm.checkcount ) {
680 continue; // already checked this brush in another leaf
681 }
682 b->checkcount = cm.checkcount;
683
684 if ( !(b->contents & tw->contents) ) {
685 continue;
686 }
687
688 if ( !CM_BoundsIntersect( tw->bounds[0], tw->bounds[1],
689 b->bounds[0], b->bounds[1] ) ) {
690 continue;
691 }
692
693 CM_TraceThroughBrush( tw, b );
694 if ( !tw->trace.fraction ) {
695 return;
696 }
697 }
698
699 // trace line against all patches in the leaf
700 #ifdef BSPC
701 if (1) {
702 #else
703 if ( !cm_noCurves->integer ) {
704 #endif
705 for ( k = 0 ; k < leaf->numLeafSurfaces ; k++ ) {
706 patch = cm.surfaces[ cm.leafsurfaces[ leaf->firstLeafSurface + k ] ];
707 if ( !patch ) {
708 continue;
709 }
710 if ( patch->checkcount == cm.checkcount ) {
711 continue; // already checked this patch in another leaf
712 }
713 patch->checkcount = cm.checkcount;
714
715 if ( !(patch->contents & tw->contents) ) {
716 continue;
717 }
718
719 CM_TraceThroughPatch( tw, patch );
720 if ( !tw->trace.fraction ) {
721 return;
722 }
723 }
724 }
725 }
726
727 #define RADIUS_EPSILON 1.0f
728
729 /*
730 ================
731 CM_TraceThroughSphere
732
733 get the first intersection of the ray with the sphere
734 ================
735 */
736 void CM_TraceThroughSphere( traceWork_t *tw, vec3_t origin, float radius, vec3_t start, vec3_t end ) {
737 float l1, l2, length, scale, fraction;
738 float a, b, c, d, sqrtd;
739 vec3_t v1, dir, intersection;
740
741 // if inside the sphere
742 VectorSubtract(start, origin, dir);
743 l1 = VectorLengthSquared(dir);
744 if (l1 < Square(radius)) {
745 tw->trace.fraction = 0;
746 tw->trace.startsolid = qtrue;
747 // test for allsolid
748 VectorSubtract(end, origin, dir);
749 l1 = VectorLengthSquared(dir);
750 if (l1 < Square(radius)) {
751 tw->trace.allsolid = qtrue;
752 }
753 return;
754 }
755 //
756 VectorSubtract(end, start, dir);
757 length = VectorNormalize(dir);
758 //
759 l1 = CM_DistanceFromLineSquared(origin, start, end, dir);
760 VectorSubtract(end, origin, v1);
761 l2 = VectorLengthSquared(v1);
762 // if no intersection with the sphere and the end point is at least an epsilon away
763 if (l1 >= Square(radius) && l2 > Square(radius+SURFACE_CLIP_EPSILON)) {
764 return;
765 }
766 //
767 // | origin - (start + t * dir) | = radius
768 // a = dir[0]^2 + dir[1]^2 + dir[2]^2;
769 // b = 2 * (dir[0] * (start[0] - origin[0]) + dir[1] * (start[1] - origin[1]) + dir[2] * (start[2] - origin[2]));
770 // c = (start[0] - origin[0])^2 + (start[1] - origin[1])^2 + (start[2] - origin[2])^2 - radius^2;
771 //
772 VectorSubtract(start, origin, v1);
773 // dir is normalized so a = 1
774 a = 1.0f;//dir[0] * dir[0] + dir[1] * dir[1] + dir[2] * dir[2];
775 b = 2.0f * (dir[0] * v1[0] + dir[1] * v1[1] + dir[2] * v1[2]);
776 c = v1[0] * v1[0] + v1[1] * v1[1] + v1[2] * v1[2] - (radius+RADIUS_EPSILON) * (radius+RADIUS_EPSILON);
777
778 d = b * b - 4.0f * c;// * a;
779 if (d > 0) {
780 sqrtd = SquareRootFloat(d);
781 // = (- b + sqrtd) * 0.5f; // / (2.0f * a);
782 fraction = (- b - sqrtd) * 0.5f; // / (2.0f * a);
783 //
784 if (fraction < 0) {
785 fraction = 0;
786 }
787 else {
788 fraction /= length;
789 }
790 if ( fraction < tw->trace.fraction ) {
791 tw->trace.fraction = fraction;
792 VectorSubtract(end, start, dir);
793 VectorMA(start, fraction, dir, intersection);
794 VectorSubtract(intersection, origin, dir);
795 #ifdef CAPSULE_DEBUG
796 l2 = VectorLength(dir);
797 if (l2 < radius) {
798 int bah = 1;
799 }
800 #endif
801 scale = 1 / (radius+RADIUS_EPSILON);
802 VectorScale(dir, scale, dir);
803 VectorCopy(dir, tw->trace.plane.normal);
804 VectorAdd( tw->modelOrigin, intersection, intersection);
805 tw->trace.plane.dist = DotProduct(tw->trace.plane.normal, intersection);
806 tw->trace.contents = CONTENTS_BODY;
807 }
808 }
809 else if (d == 0) {
810 //t1 = (- b ) / 2;
811 // slide along the sphere
812 }
813 // no intersection at all
814 }
815
816 /*
817 ================
818 CM_TraceThroughVerticalCylinder
819
820 get the first intersection of the ray with the cylinder
821 the cylinder extends halfheight above and below the origin
822 ================
823 */
824 void CM_TraceThroughVerticalCylinder( traceWork_t *tw, vec3_t origin, float radius, float halfheight, vec3_t start, vec3_t end) {
825 float length, scale, fraction, l1, l2;
826 float a, b, c, d, sqrtd;
827 vec3_t v1, dir, start2d, end2d, org2d, intersection;
828
829 // 2d coordinates
830 VectorSet(start2d, start[0], start[1], 0);
831 VectorSet(end2d, end[0], end[1], 0);
832 VectorSet(org2d, origin[0], origin[1], 0);
833 // if between lower and upper cylinder bounds
834 if (start[2] <= origin[2] + halfheight &&
835 start[2] >= origin[2] - halfheight) {
836 // if inside the cylinder
837 VectorSubtract(start2d, org2d, dir);
838 l1 = VectorLengthSquared(dir);
839 if (l1 < Square(radius)) {
840 tw->trace.fraction = 0;
841 tw->trace.startsolid = qtrue;
842 VectorSubtract(end2d, org2d, dir);
843 l1 = VectorLengthSquared(dir);
844 if (l1 < Square(radius)) {
845 tw->trace.allsolid = qtrue;
846 }
847 return;
848 }
849 }
850 //
851 VectorSubtract(end2d, start2d, dir);
852 length = VectorNormalize(dir);
853 //
854 l1 = CM_DistanceFromLineSquared(org2d, start2d, end2d, dir);
855 VectorSubtract(end2d, org2d, v1);
856 l2 = VectorLengthSquared(v1);
857 // if no intersection with the cylinder and the end point is at least an epsilon away
858 if (l1 >= Square(radius) && l2 > Square(radius+SURFACE_CLIP_EPSILON)) {
859 return;
860 }
861 //
862 //
863 // (start[0] - origin[0] - t * dir[0]) ^ 2 + (start[1] - origin[1] - t * dir[1]) ^ 2 = radius ^ 2
864 // (v1[0] + t * dir[0]) ^ 2 + (v1[1] + t * dir[1]) ^ 2 = radius ^ 2;
865 // v1[0] ^ 2 + 2 * v1[0] * t * dir[0] + (t * dir[0]) ^ 2 +
866 // v1[1] ^ 2 + 2 * v1[1] * t * dir[1] + (t * dir[1]) ^ 2 = radius ^ 2
867 // t ^ 2 * (dir[0] ^ 2 + dir[1] ^ 2) + t * (2 * v1[0] * dir[0] + 2 * v1[1] * dir[1]) +
868 // v1[0] ^ 2 + v1[1] ^ 2 - radius ^ 2 = 0
869 //
870 VectorSubtract(start, origin, v1);
871 // dir is normalized so we can use a = 1
872 a = 1.0f;// * (dir[0] * dir[0] + dir[1] * dir[1]);
873 b = 2.0f * (v1[0] * dir[0] + v1[1] * dir[1]);
874 c = v1[0] * v1[0] + v1[1] * v1[1] - (radius+RADIUS_EPSILON) * (radius+RADIUS_EPSILON);
875
876 d = b * b - 4.0f * c;// * a;
877 if (d > 0) {
878 sqrtd = SquareRootFloat(d);
879 // = (- b + sqrtd) * 0.5f;// / (2.0f * a);
880 fraction = (- b - sqrtd) * 0.5f;// / (2.0f * a);
881 //
882 if (fraction < 0) {
883 fraction = 0;
884 }
885 else {
886 fraction /= length;
887 }
888 if ( fraction < tw->trace.fraction ) {
889 VectorSubtract(end, start, dir);
890 VectorMA(start, fraction, dir, intersection);
891 // if the intersection is between the cylinder lower and upper bound
892 if (intersection[2] <= origin[2] + halfheight &&
893 intersection[2] >= origin[2] - halfheight) {
894 //
895 tw->trace.fraction = fraction;
896 VectorSubtract(intersection, origin, dir);
897 dir[2] = 0;
898 #ifdef CAPSULE_DEBUG
899 l2 = VectorLength(dir);
900 if (l2 <= radius) {
901 int bah = 1;
902 }
903 #endif
904 scale = 1 / (radius+RADIUS_EPSILON);
905 VectorScale(dir, scale, dir);
906 VectorCopy(dir, tw->trace.plane.normal);
907 VectorAdd( tw->modelOrigin, intersection, intersection);
908 tw->trace.plane.dist = DotProduct(tw->trace.plane.normal, intersection);
909 tw->trace.contents = CONTENTS_BODY;
910 }
911 }
912 }
913 else if (d == 0) {
914 //t[0] = (- b ) / 2 * a;
915 // slide along the cylinder
916 }
917 // no intersection at all
918 }
919
920 /*
921 ================
922 CM_TraceCapsuleThroughCapsule
923
924 capsule vs. capsule collision (not rotated)
925 ================
926 */
927 void CM_TraceCapsuleThroughCapsule( traceWork_t *tw, clipHandle_t model ) {
928 int i;
929 vec3_t mins, maxs;
930 vec3_t top, bottom, starttop, startbottom, endtop, endbottom;
931 vec3_t offset, symetricSize[2];
932 float radius, halfwidth, halfheight, offs, h;
933
934 CM_ModelBounds(model, mins, maxs);
935 // test trace bounds vs. capsule bounds
936 if ( tw->bounds[0][0] > maxs[0] + RADIUS_EPSILON
937 || tw->bounds[0][1] > maxs[1] + RADIUS_EPSILON
938 || tw->bounds[0][2] > maxs[2] + RADIUS_EPSILON
939 || tw->bounds[1][0] < mins[0] - RADIUS_EPSILON
940 || tw->bounds[1][1] < mins[1] - RADIUS_EPSILON
941 || tw->bounds[1][2] < mins[2] - RADIUS_EPSILON
942 ) {
943 return;
944 }
945 // top origin and bottom origin of each sphere at start and end of trace
946 VectorAdd(tw->start, tw->sphere.offset, starttop);
947 VectorSubtract(tw->start, tw->sphere.offset, startbottom);
948 VectorAdd(tw->end, tw->sphere.offset, endtop);
949 VectorSubtract(tw->end, tw->sphere.offset, endbottom);
950
951 // calculate top and bottom of the capsule spheres to collide with
952 for ( i = 0 ; i < 3 ; i++ ) {
953 offset[i] = ( mins[i] + maxs[i] ) * 0.5;
954 symetricSize[0][i] = mins[i] - offset[i];
955 symetricSize[1][i] = maxs[i] - offset[i];
956 }
957 halfwidth = symetricSize[ 1 ][ 0 ];
958 halfheight = symetricSize[ 1 ][ 2 ];
959 radius = ( halfwidth > halfheight ) ? halfheight : halfwidth;
960 offs = halfheight - radius;
961 VectorCopy(offset, top);
962 top[2] += offs;
963 VectorCopy(offset, bottom);
964 bottom[2] -= offs;
965 // expand radius of spheres
966 radius += tw->sphere.radius;
967 // if there is horizontal movement
968 if ( tw->start[0] != tw->end[0] || tw->start[1] != tw->end[1] ) {
969 // height of the expanded cylinder is the height of both cylinders minus the radius of both spheres
970 h = halfheight + tw->sphere.halfheight - radius;
971 // if the cylinder has a height
972 if ( h > 0 ) {
973 // test for collisions between the cylinders
974 CM_TraceThroughVerticalCylinder(tw, offset, radius, h, tw->start, tw->end);
975 }
976 }
977 // test for collision between the spheres
978 CM_TraceThroughSphere(tw, top, radius, startbottom, endbottom);
979 CM_TraceThroughSphere(tw, bottom, radius, starttop, endtop);
980 }
981
982 /*
983 ================
984 CM_TraceBoundingBoxThroughCapsule
985
986 bounding box vs. capsule collision
987 ================
988 */
989 void CM_TraceBoundingBoxThroughCapsule( traceWork_t *tw, clipHandle_t model ) {
990 vec3_t mins, maxs, offset, size[2];
991 clipHandle_t h;
992 cmodel_t *cmod;
993 int i;
994
995 // mins maxs of the capsule
996 CM_ModelBounds(model, mins, maxs);
997
998 // offset for capsule center
999 for ( i = 0 ; i < 3 ; i++ ) {
1000 offset[i] = ( mins[i] + maxs[i] ) * 0.5;
1001 size[0][i] = mins[i] - offset[i];
1002 size[1][i] = maxs[i] - offset[i];
1003 tw->start[i] -= offset[i];
1004 tw->end[i] -= offset[i];
1005 }
1006
1007 // replace the bounding box with the capsule
1008 tw->sphere.use = qtrue;
1009 tw->sphere.radius = ( size[1][0] > size[1][2] ) ? size[1][2]: size[1][0];
1010 tw->sphere.halfheight = size[1][2];
1011 VectorSet( tw->sphere.offset, 0, 0, size[1][2] - tw->sphere.radius );
1012
1013 // replace the capsule with the bounding box
1014 h = CM_TempBoxModel(tw->size[0], tw->size[1], qfalse);
1015 // calculate collision
1016 cmod = CM_ClipHandleToModel( h );
1017 CM_TraceThroughLeaf( tw, &cmod->leaf );
1018 }
1019
1020 //=========================================================================================
1021
1022 /*
1023 ==================
1024 CM_TraceThroughTree
1025
1026 Traverse all the contacted leafs from the start to the end position.
1027 If the trace is a point, they will be exactly in order, but for larger
1028 trace volumes it is possible to hit something in a later leaf with
1029 a smaller intercept fraction.
1030 ==================
1031 */
1032 void CM_TraceThroughTree( traceWork_t *tw, int num, float p1f, float p2f, vec3_t p1, vec3_t p2) {
1033 cNode_t *node;
1034 cplane_t *plane;
1035 float t1, t2, offset;
1036 float frac, frac2;
1037 float idist;
1038 vec3_t mid;
1039 int side;
1040 float midf;
1041
1042 if (tw->trace.fraction <= p1f) {
1043 return; // already hit something nearer
1044 }
1045
1046 // if < 0, we are in a leaf node
1047 if (num < 0) {
1048 CM_TraceThroughLeaf( tw, &cm.leafs[-1-num] );
1049 return;
1050 }
1051
1052 //
1053 // find the point distances to the seperating plane
1054 // and the offset for the size of the box
1055 //
1056 node = cm.nodes + num;
1057 plane = node->plane;
1058
1059 // adjust the plane distance apropriately for mins/maxs
1060 if ( plane->type < 3 ) {
1061 t1 = p1[plane->type] - plane->dist;
1062 t2 = p2[plane->type] - plane->dist;
1063 offset = tw->extents[plane->type];
1064 } else {
1065 t1 = DotProduct (plane->normal, p1) - plane->dist;
1066 t2 = DotProduct (plane->normal, p2) - plane->dist;
1067 if ( tw->isPoint ) {
1068 offset = 0;
1069 } else {
1070 // this is silly
1071 offset = 2048;
1072 }
1073 }
1074
1075 // see which sides we need to consider
1076 if ( t1 >= offset + 1 && t2 >= offset + 1 ) {
1077 CM_TraceThroughTree( tw, node->children[0], p1f, p2f, p1, p2 );
1078 return;
1079 }
1080 if ( t1 < -offset - 1 && t2 < -offset - 1 ) {
1081 CM_TraceThroughTree( tw, node->children[1], p1f, p2f, p1, p2 );
1082 return;
1083 }
1084
1085 // put the crosspoint SURFACE_CLIP_EPSILON pixels on the near side
1086 if ( t1 < t2 ) {
1087 idist = 1.0/(t1-t2);
1088 side = 1;
1089 frac2 = (t1 + offset + SURFACE_CLIP_EPSILON)*idist;
1090 frac = (t1 - offset + SURFACE_CLIP_EPSILON)*idist;
1091 } else if (t1 > t2) {
1092 idist = 1.0/(t1-t2);
1093 side = 0;
1094 frac2 = (t1 - offset - SURFACE_CLIP_EPSILON)*idist;
1095 frac = (t1 + offset + SURFACE_CLIP_EPSILON)*idist;
1096 } else {
1097 side = 0;
1098 frac = 1;
1099 frac2 = 0;
1100 }
1101
1102 // move up to the node
1103 if ( frac < 0 ) {
1104 frac = 0;
1105 }
1106 if ( frac > 1 ) {
1107 frac = 1;
1108 }
1109
1110 midf = p1f + (p2f - p1f)*frac;
1111
1112 mid[0] = p1[0] + frac*(p2[0] - p1[0]);
1113 mid[1] = p1[1] + frac*(p2[1] - p1[1]);
1114 mid[2] = p1[2] + frac*(p2[2] - p1[2]);
1115
1116 CM_TraceThroughTree( tw, node->children[side], p1f, midf, p1, mid );
1117
1118
1119 // go past the node
1120 if ( frac2 < 0 ) {
1121 frac2 = 0;
1122 }
1123 if ( frac2 > 1 ) {
1124 frac2 = 1;
1125 }
1126
1127 midf = p1f + (p2f - p1f)*frac2;
1128
1129 mid[0] = p1[0] + frac2*(p2[0] - p1[0]);
1130 mid[1] = p1[1] + frac2*(p2[1] - p1[1]);
1131 mid[2] = p1[2] + frac2*(p2[2] - p1[2]);
1132
1133 CM_TraceThroughTree( tw, node->children[side^1], midf, p2f, mid, p2 );
1134 }
1135
1136
1137 //======================================================================
1138
1139
1140 /*
1141 ==================
1142 CM_Trace
1143 ==================
1144 */
1145 void CM_Trace( trace_t *results, const vec3_t start, const vec3_t end, vec3_t mins, vec3_t maxs,
1146 clipHandle_t model, const vec3_t origin, int brushmask, int capsule, sphere_t *sphere ) {
1147 int i;
1148 traceWork_t tw;
1149 vec3_t offset;
1150 cmodel_t *cmod;
1151
1152 cmod = CM_ClipHandleToModel( model );
1153
1154 cm.checkcount++; // for multi-check avoidance
1155
1156 c_traces++; // for statistics, may be zeroed
1157
1158 // fill in a default trace
1159 Com_Memset( &tw, 0, sizeof(tw) );
1160 tw.trace.fraction = 1; // assume it goes the entire distance until shown otherwise
1161 VectorCopy(origin, tw.modelOrigin);
1162
1163 if (!cm.numNodes) {
1164 *results = tw.trace;
1165
1166 return; // map not loaded, shouldn't happen
1167 }
1168
1169 // allow NULL to be passed in for 0,0,0
1170 if ( !mins ) {
1171 mins = vec3_origin;
1172 }
1173 if ( !maxs ) {
1174 maxs = vec3_origin;
1175 }
1176
1177 // set basic parms
1178 tw.contents = brushmask;
1179
1180 // adjust so that mins and maxs are always symetric, which
1181 // avoids some complications with plane expanding of rotated
1182 // bmodels
1183 for ( i = 0 ; i < 3 ; i++ ) {
1184 offset[i] = ( mins[i] + maxs[i] ) * 0.5;
1185 tw.size[0][i] = mins[i] - offset[i];
1186 tw.size[1][i] = maxs[i] - offset[i];
1187 tw.start[i] = start[i] + offset[i];
1188 tw.end[i] = end[i] + offset[i];
1189 }
1190
1191 // if a sphere is already specified
1192 if ( sphere ) {
1193 tw.sphere = *sphere;
1194 }
1195 else {
1196 tw.sphere.use = capsule;
1197 tw.sphere.radius = ( tw.size[1][0] > tw.size[1][2] ) ? tw.size[1][2]: tw.size[1][0];
1198 tw.sphere.halfheight = tw.size[1][2];
1199 VectorSet( tw.sphere.offset, 0, 0, tw.size[1][2] - tw.sphere.radius );
1200 }
1201
1202 tw.maxOffset = tw.size[1][0] + tw.size[1][1] + tw.size[1][2];
1203
1204 // tw.offsets[signbits] = vector to apropriate corner from origin
1205 tw.offsets[0][0] = tw.size[0][0];
1206 tw.offsets[0][1] = tw.size[0][1];
1207 tw.offsets[0][2] = tw.size[0][2];
1208
1209 tw.offsets[1][0] = tw.size[1][0];
1210 tw.offsets[1][1] = tw.size[0][1];
1211 tw.offsets[1][2] = tw.size[0][2];
1212
1213 tw.offsets[2][0] = tw.size[0][0];
1214 tw.offsets[2][1] = tw.size[1][1];
1215 tw.offsets[2][2] = tw.size[0][2];
1216
1217 tw.offsets[3][0] = tw.size[1][0];
1218 tw.offsets[3][1] = tw.size[1][1];
1219 tw.offsets[3][2] = tw.size[0][2];
1220
1221 tw.offsets[4][0] = tw.size[0][0];
1222 tw.offsets[4][1] = tw.size[0][1];
1223 tw.offsets[4][2] = tw.size[1][2];
1224
1225 tw.offsets[5][0] = tw.size[1][0];
1226 tw.offsets[5][1] = tw.size[0][1];
1227 tw.offsets[5][2] = tw.size[1][2];
1228
1229 tw.offsets[6][0] = tw.size[0][0];
1230 tw.offsets[6][1] = tw.size[1][1];
1231 tw.offsets[6][2] = tw.size[1][2];
1232
1233 tw.offsets[7][0] = tw.size[1][0];
1234 tw.offsets[7][1] = tw.size[1][1];
1235 tw.offsets[7][2] = tw.size[1][2];
1236
1237 //
1238 // calculate bounds
1239 //
1240 if ( tw.sphere.use ) {
1241 for ( i = 0 ; i < 3 ; i++ ) {
1242 if ( tw.start[i] < tw.end[i] ) {
1243 tw.bounds[0][i] = tw.start[i] - fabs(tw.sphere.offset[i]) - tw.sphere.radius;
1244 tw.bounds[1][i] = tw.end[i] + fabs(tw.sphere.offset[i]) + tw.sphere.radius;
1245 } else {
1246 tw.bounds[0][i] = tw.end[i] - fabs(tw.sphere.offset[i]) - tw.sphere.radius;
1247 tw.bounds[1][i] = tw.start[i] + fabs(tw.sphere.offset[i]) + tw.sphere.radius;
1248 }
1249 }
1250 }
1251 else {
1252 for ( i = 0 ; i < 3 ; i++ ) {
1253 if ( tw.start[i] < tw.end[i] ) {
1254 tw.bounds[0][i] = tw.start[i] + tw.size[0][i];
1255 tw.bounds[1][i] = tw.end[i] + tw.size[1][i];
1256 } else {
1257 tw.bounds[0][i] = tw.end[i] + tw.size[0][i];
1258 tw.bounds[1][i] = tw.start[i] + tw.size[1][i];
1259 }
1260 }
1261 }
1262
1263 //
1264 // check for position test special case
1265 //
1266 if (start[0] == end[0] && start[1] == end[1] && start[2] == end[2]) {
1267 if ( model ) {
1268 #ifdef ALWAYS_BBOX_VS_BBOX // FIXME - compile time flag?
1269 if ( model == BOX_MODEL_HANDLE || model == CAPSULE_MODEL_HANDLE) {
1270 tw.sphere.use = qfalse;
1271 CM_TestInLeaf( &tw, &cmod->leaf );
1272 }
1273 else
1274 #elif defined(ALWAYS_CAPSULE_VS_CAPSULE)
1275 if ( model == BOX_MODEL_HANDLE || model == CAPSULE_MODEL_HANDLE) {
1276 CM_TestCapsuleInCapsule( &tw, model );
1277 }
1278 else
1279 #endif
1280 if ( model == CAPSULE_MODEL_HANDLE ) {
1281 if ( tw.sphere.use ) {
1282 CM_TestCapsuleInCapsule( &tw, model );
1283 }
1284 else {
1285 CM_TestBoundingBoxInCapsule( &tw, model );
1286 }
1287 }
1288 else {
1289 CM_TestInLeaf( &tw, &cmod->leaf );
1290 }
1291 } else {
1292 CM_PositionTest( &tw );
1293 }
1294 } else {
1295 //
1296 // check for point special case
1297 //
1298 if ( tw.size[0][0] == 0 && tw.size[0][1] == 0 && tw.size[0][2] == 0 ) {
1299 tw.isPoint = qtrue;
1300 VectorClear( tw.extents );
1301 } else {
1302 tw.isPoint = qfalse;
1303 tw.extents[0] = tw.size[1][0];
1304 tw.extents[1] = tw.size[1][1];
1305 tw.extents[2] = tw.size[1][2];
1306 }
1307
1308 //
1309 // general sweeping through world
1310 //
1311 if ( model ) {
1312 #ifdef ALWAYS_BBOX_VS_BBOX
1313 if ( model == BOX_MODEL_HANDLE || model == CAPSULE_MODEL_HANDLE) {
1314 tw.sphere.use = qfalse;
1315 CM_TraceThroughLeaf( &tw, &cmod->leaf );
1316 }
1317 else
1318 #elif defined(ALWAYS_CAPSULE_VS_CAPSULE)
1319 if ( model == BOX_MODEL_HANDLE || model == CAPSULE_MODEL_HANDLE) {
1320 CM_TraceCapsuleThroughCapsule( &tw, model );
1321 }
1322 else
1323 #endif
1324 if ( model == CAPSULE_MODEL_HANDLE ) {
1325 if ( tw.sphere.use ) {
1326 CM_TraceCapsuleThroughCapsule( &tw, model );
1327 }
1328 else {
1329 CM_TraceBoundingBoxThroughCapsule( &tw, model );
1330 }
1331 }
1332 else {
1333 CM_TraceThroughLeaf( &tw, &cmod->leaf );
1334 }
1335 } else {
1336 CM_TraceThroughTree( &tw, 0, 0, 1, tw.start, tw.end );
1337 }
1338 }
1339
1340 // generate endpos from the original, unmodified start/end
1341 if ( tw.trace.fraction == 1 ) {
1342 VectorCopy (end, tw.trace.endpos);
1343 } else {
1344 for ( i=0 ; i<3 ; i++ ) {
1345 tw.trace.endpos[i] = start[i] + tw.trace.fraction * (end[i] - start[i]);
1346 }
1347 }
1348
1349 // If allsolid is set (was entirely inside something solid), the plane is not valid.
1350 // If fraction == 1.0, we never hit anything, and thus the plane is not valid.
1351 // Otherwise, the normal on the plane should have unit length
1352 assert(tw.trace.allsolid ||
1353 tw.trace.fraction == 1.0 ||
1354 VectorLengthSquared(tw.trace.plane.normal) > 0.9999);
1355 *results = tw.trace;
1356 }
1357
1358 /*
1359 ==================
1360 CM_BoxTrace
1361 ==================
1362 */
1363 void CM_BoxTrace( trace_t *results, const vec3_t start, const vec3_t end,
1364 vec3_t mins, vec3_t maxs,
1365 clipHandle_t model, int brushmask, int capsule ) {
1366 CM_Trace( results, start, end, mins, maxs, model, vec3_origin, brushmask, capsule, NULL );
1367 }
1368
1369 /*
1370 ==================
1371 CM_TransformedBoxTrace
1372
1373 Handles offseting and rotation of the end points for moving and
1374 rotating entities
1375 ==================
1376 */
1377 void CM_TransformedBoxTrace( trace_t *results, const vec3_t start, const vec3_t end,
1378 vec3_t mins, vec3_t maxs,
1379 clipHandle_t model, int brushmask,
1380 const vec3_t origin, const vec3_t angles, int capsule ) {
1381 trace_t trace;
1382 vec3_t start_l, end_l;
1383 qboolean rotated;
1384 vec3_t offset;
1385 vec3_t symetricSize[2];
1386 vec3_t matrix[3], transpose[3];
1387 int i;
1388 float halfwidth;
1389 float halfheight;
1390 float t;
1391 sphere_t sphere;
1392
1393 if ( !mins ) {
1394 mins = vec3_origin;
1395 }
1396 if ( !maxs ) {
1397 maxs = vec3_origin;
1398 }
1399
1400 // adjust so that mins and maxs are always symetric, which
1401 // avoids some complications with plane expanding of rotated
1402 // bmodels
1403 for ( i = 0 ; i < 3 ; i++ ) {
1404 offset[i] = ( mins[i] + maxs[i] ) * 0.5;
1405 symetricSize[0][i] = mins[i] - offset[i];
1406 symetricSize[1][i] = maxs[i] - offset[i];
1407 start_l[i] = start[i] + offset[i];
1408 end_l[i] = end[i] + offset[i];
1409 }
1410
1411 // subtract origin offset
1412 VectorSubtract( start_l, origin, start_l );
1413 VectorSubtract( end_l, origin, end_l );
1414
1415 // rotate start and end into the models frame of reference
1416 if ( model != BOX_MODEL_HANDLE &&
1417 (angles[0] || angles[1] || angles[2]) ) {
1418 rotated = qtrue;
1419 } else {
1420 rotated = qfalse;
1421 }
1422
1423 halfwidth = symetricSize[ 1 ][ 0 ];
1424 halfheight = symetricSize[ 1 ][ 2 ];
1425
1426 sphere.use = capsule;
1427 sphere.radius = ( halfwidth > halfheight ) ? halfheight : halfwidth;
1428 sphere.halfheight = halfheight;
1429 t = halfheight - sphere.radius;
1430
1431 if (rotated) {
1432 // rotation on trace line (start-end) instead of rotating the bmodel
1433 // NOTE: This is still incorrect for bounding boxes because the actual bounding
1434 // box that is swept through the model is not rotated. We cannot rotate
1435 // the bounding box or the bmodel because that would make all the brush
1436 // bevels invalid.
1437 // However this is correct for capsules since a capsule itself is rotated too.
1438 CreateRotationMatrix(angles, matrix);
1439 RotatePoint(start_l, matrix);
1440 RotatePoint(end_l, matrix);
1441 // rotated sphere offset for capsule
1442 sphere.offset[0] = matrix[0][ 2 ] * t;
1443 sphere.offset[1] = -matrix[1][ 2 ] * t;
1444 sphere.offset[2] = matrix[2][ 2 ] * t;
1445 }
1446 else {
1447 VectorSet( sphere.offset, 0, 0, t );
1448 }
1449
1450 // sweep the box through the model
1451 CM_Trace( &trace, start_l, end_l, symetricSize[0], symetricSize[1], model, origin, brushmask, capsule, &sphere );
1452
1453 // if the bmodel was rotated and there was a collision
1454 if ( rotated && trace.fraction != 1.0 ) {
1455 // rotation of bmodel collision plane
1456 TransposeMatrix(matrix, transpose);
1457 RotatePoint(trace.plane.normal, transpose);
1458 }
1459
1460 // re-calculate the end position of the trace because the trace.endpos
1461 // calculated by CM_Trace could be rotated and have an offset
1462 trace.endpos[0] = start[0] + trace.fraction * (end[0] - start[0]);
1463 trace.endpos[1] = start[1] + trace.fraction * (end[1] - start[1]);
1464 trace.endpos[2] = start[2] + trace.fraction * (end[2] - start[2]);
1465
1466 *results = trace;
1467 }
1468