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