neo/idlib/bv/Frustum.cpp

   1 /*
   2 ===========================================================================
   3
   4 Doom 3 GPL Source Code
   5 Copyright (C) 1999-2011 id Software LLC, a ZeniMax Media company.
   6
   7 This file is part of the Doom 3 GPL Source Code (?Doom 3 Source Code?).
   8
   9 Doom 3 Source Code is free software: you can redistribute it and/or modify
  10 it under the terms of the GNU General Public License as published by
  11 the Free Software Foundation, either version 3 of the License, or
  12 (at your option) any later version.
  13
  14 Doom 3 Source Code is distributed in the hope that it will be useful,
  15 but WITHOUT ANY WARRANTY; without even the implied warranty of
  16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  17 GNU General Public License for more details.
  18
  19 You should have received a copy of the GNU General Public License
  20 along with Doom 3 Source Code.  If not, see <http://www.gnu.org/licenses/>.
  21
  22 In addition, the Doom 3 Source Code is also subject to certain additional terms. You should have received a copy of these additional terms immediately following the terms and conditions of the GNU General Public License which accompanied the Doom 3 Source Code.  If not, please request a copy in writing from id Software at the address below.
  23
  24 If you have questions concerning this license or the applicable additional terms, you may contact in writing id Software LLC, c/o ZeniMax Media Inc., Suite 120, Rockville, Maryland 20850 USA.
  25
  26 ===========================================================================
  27 */
  28
  29 #include "../precompiled.h"
  30 #pragma hdrstop
  31
  32 //#define FRUSTUM_DEBUG
  33
  34 /*
  35   bit 0 = min x
  36   bit 1 = max x
  37   bit 2 = min y
  38   bit 3 = max y
  39   bit 4 = min z
  40   bit 5 = max z
  41 */
  42 static int boxVertPlanes[8] = {
  43         ( (1<<0) | (1<<2) | (1<<4) ),
  44         ( (1<<1) | (1<<2) | (1<<4) ),
  45         ( (1<<1) | (1<<3) | (1<<4) ),
  46         ( (1<<0) | (1<<3) | (1<<4) ),
  47         ( (1<<0) | (1<<2) | (1<<5) ),
  48         ( (1<<1) | (1<<2) | (1<<5) ),
  49         ( (1<<1) | (1<<3) | (1<<5) ),
  50         ( (1<<0) | (1<<3) | (1<<5) ),
  51 };
  52
  53 /*
  54 ============
  55 BoxToPoints
  56 ============
  57 */
  58 void BoxToPoints( const idVec3 &center, const idVec3 &extents, const idMat3 &axis, idVec3 points[8] ) {
  59         idMat3 ax;
  60         idVec3 temp[4];
  61
  62         ax[0] = extents[0] * axis[0];
  63         ax[1] = extents[1] * axis[1];
  64         ax[2] = extents[2] * axis[2];
  65         temp[0] = center - ax[0];
  66         temp[1] = center + ax[0];
  67         temp[2] = ax[1] - ax[2];
  68         temp[3] = ax[1] + ax[2];
  69         points[0] = temp[0] - temp[3];
  70         points[1] = temp[1] - temp[3];
  71         points[2] = temp[1] + temp[2];
  72         points[3] = temp[0] + temp[2];
  73         points[4] = temp[0] - temp[2];
  74         points[5] = temp[1] - temp[2];
  75         points[6] = temp[1] + temp[3];
  76         points[7] = temp[0] + temp[3];
  77 }
  78
  79 /*
  80 ================
  81 idFrustum::PlaneDistance
  82 ================
  83 */
  84 float idFrustum::PlaneDistance( const idPlane &plane ) const {
  85         float min, max;
  86
  87         AxisProjection( plane.Normal(), min, max );
  88         if ( min + plane[3] > 0.0f ) {
  89                 return min + plane[3];
  90         }
  91         if ( max + plane[3] < 0.0f ) {
  92                 return max + plane[3];
  93         }
  94         return 0.0f;
  95 }
  96
  97 /*
  98 ================
  99 idFrustum::PlaneSide
 100 ================
 101 */
 102 int idFrustum::PlaneSide( const idPlane &plane, const float epsilon ) const {
 103         float min, max;
 104
 105         AxisProjection( plane.Normal(), min, max );
 106         if ( min + plane[3] > epsilon ) {
 107                 return PLANESIDE_FRONT;
 108         }
 109         if ( max + plane[3] < epsilon ) {
 110                 return PLANESIDE_BACK;
 111         }
 112         return PLANESIDE_CROSS;
 113 }
 114
 115 /*
 116 ============
 117 idFrustum::CullPoint
 118 ============
 119 */
 120 bool idFrustum::CullPoint( const idVec3 &point ) const {
 121         idVec3 p;
 122         float scale;
 123
 124         // transform point to frustum space
 125         p = ( point - origin ) * axis.Transpose();
 126         // test whether or not the point is within the frustum
 127         if ( p.x < dNear || p.x > dFar ) {
 128                 return true;
 129         }
 130         scale = p.x * invFar;
 131         if ( idMath::Fabs( p.y ) > dLeft * scale ) {
 132                 return true;
 133         }
 134         if ( idMath::Fabs( p.z ) > dUp * scale ) {
 135                 return true;
 136         }
 137         return false;
 138 }
 139
 140 /*
 141 ============
 142 idFrustum::CullLocalBox
 143
 144   Tests if any of the planes of the frustum can be used as a separating plane.
 145
 146    3 muls best case
 147   25 muls worst case
 148 ============
 149 */
 150 bool idFrustum::CullLocalBox( const idVec3 &localOrigin, const idVec3 &extents, const idMat3 &localAxis ) const {
 151         float d1, d2;
 152         idVec3 testOrigin;
 153         idMat3 testAxis;
 154
 155         // near plane
 156         d1 = dNear - localOrigin.x;
 157         d2 = idMath::Fabs( extents[0] * localAxis[0][0] ) +
 158                                 idMath::Fabs( extents[1] * localAxis[1][0] ) +
 159                                                 idMath::Fabs( extents[2] * localAxis[2][0] );
 160         if ( d1 - d2 > 0.0f ) {
 161                 return true;
 162         }
 163
 164         // far plane
 165         d1 = localOrigin.x - dFar;
 166         if ( d1 - d2 > 0.0f ) {
 167                 return true;
 168         }
 169
 170         testOrigin = localOrigin;
 171         testAxis = localAxis;
 172
 173         if ( testOrigin.y < 0.0f ) {
 174                 testOrigin.y = -testOrigin.y;
 175                 testAxis[0][1] = -testAxis[0][1];
 176                 testAxis[1][1] = -testAxis[1][1];
 177                 testAxis[2][1] = -testAxis[2][1];
 178         }
 179
 180         // test left/right planes
 181         d1 = dFar * testOrigin.y - dLeft * testOrigin.x;
 182         d2 = idMath::Fabs( extents[0] * ( dFar * testAxis[0][1] - dLeft * testAxis[0][0] ) ) +
 183                                 idMath::Fabs( extents[1] * ( dFar * testAxis[1][1] - dLeft * testAxis[1][0] ) ) +
 184                                         idMath::Fabs( extents[2] * ( dFar * testAxis[2][1] - dLeft * testAxis[2][0] ) );
 185         if ( d1 - d2 > 0.0f ) {
 186                 return true;
 187         }
 188
 189         if ( testOrigin.z < 0.0f ) {
 190                 testOrigin.z = -testOrigin.z;
 191                 testAxis[0][2] = -testAxis[0][2];
 192                 testAxis[1][2] = -testAxis[1][2];
 193                 testAxis[2][2] = -testAxis[2][2];
 194         }
 195
 196         // test up/down planes
 197         d1 = dFar * testOrigin.z - dUp * testOrigin.x;
 198         d2 = idMath::Fabs( extents[0] * ( dFar * testAxis[0][2] - dUp * testAxis[0][0] ) ) +
 199                                 idMath::Fabs( extents[1] * ( dFar * testAxis[1][2] - dUp * testAxis[1][0] ) ) +
 200                                         idMath::Fabs( extents[2] * ( dFar * testAxis[2][2] - dUp * testAxis[2][0] ) );
 201         if ( d1 - d2 > 0.0f ) {
 202                 return true;
 203         }
 204
 205         return false;
 206 }
 207
 208 /*
 209 ============
 210 idFrustum::CullBounds
 211
 212   Tests if any of the planes of the frustum can be used as a separating plane.
 213
 214   24 muls best case
 215   37 muls worst case
 216 ============
 217 */
 218 bool idFrustum::CullBounds( const idBounds &bounds ) const {
 219         idVec3 localOrigin, center, extents;
 220         idMat3 localAxis;
 221
 222         center = ( bounds[0] + bounds[1] ) * 0.5f;
 223         extents = bounds[1] - center;
 224
 225         // transform the bounds into the space of this frustum
 226         localOrigin = ( center - origin ) * axis.Transpose();
 227         localAxis = axis.Transpose();
 228
 229         return CullLocalBox( localOrigin, extents, localAxis );
 230 }
 231
 232 /*
 233 ============
 234 idFrustum::CullBounds
 235
 236   Tests if any of the planes of the frustum can be used as a separating plane.
 237
 238   39 muls best case
 239   61 muls worst case
 240 ============
 241 */
 242 bool idFrustum::CullBox( const idBox &box ) const {
 243         idVec3 localOrigin;
 244         idMat3 localAxis;
 245
 246         // transform the box into the space of this frustum
 247         localOrigin = ( box.GetCenter() - origin ) * axis.Transpose();
 248         localAxis = box.GetAxis() * axis.Transpose();
 249
 250         return CullLocalBox( localOrigin, box.GetExtents(), localAxis );
 251 }
 252
 253 /*
 254 ============
 255 idFrustum::CullSphere
 256
 257   Tests if any of the planes of the frustum can be used as a separating plane.
 258
 259    9 muls best case
 260   21 muls worst case
 261 ============
 262 */
 263 bool idFrustum::CullSphere( const idSphere &sphere ) const {
 264         float d, r, rs, sFar;
 265         idVec3 center;
 266
 267         center = ( sphere.GetOrigin() - origin ) * axis.Transpose();
 268         r = sphere.GetRadius();
 269
 270         // test near plane
 271         if ( dNear - center.x > r ) {
 272                 return true;
 273         }
 274
 275         // test far plane
 276         if ( center.x - dFar > r ) {
 277                 return true;
 278         }
 279
 280         rs = r * r;
 281         sFar = dFar * dFar;
 282
 283         // test left/right planes
 284         d = dFar * idMath::Fabs( center.y ) - dLeft * center.x;
 285         if ( ( d * d ) > rs * ( sFar + dLeft * dLeft ) ) {
 286                 return true;
 287         }
 288
 289         // test up/down planes
 290         d = dFar * idMath::Fabs( center.z ) - dUp * center.x;
 291         if ( ( d * d ) > rs * ( sFar + dUp * dUp ) ) {
 292                 return true;
 293         }
 294
 295         return false;
 296 }
 297
 298 /*
 299 ============
 300 idFrustum::CullLocalFrustum
 301
 302   Tests if any of the planes of this frustum can be used as a separating plane.
 303
 304    0 muls best case
 305   30 muls worst case
 306 ============
 307 */
 308 bool idFrustum::CullLocalFrustum( const idFrustum &localFrustum, const idVec3 indexPoints[8], const idVec3 cornerVecs[4] ) const {
 309         int index;
 310         float dx, dy, dz, leftScale, upScale;
 311
 312         // test near plane
 313         dy = -localFrustum.axis[1].x;
 314         dz = -localFrustum.axis[2].x;
 315         index = ( FLOATSIGNBITSET( dy ) << 1 ) | FLOATSIGNBITSET( dz );
 316         dx = -cornerVecs[index].x;
 317         index |= ( FLOATSIGNBITSET( dx ) << 2 );
 318
 319         if ( indexPoints[index].x < dNear ) {
 320                 return true;
 321         }
 322
 323         // test far plane
 324         dy = localFrustum.axis[1].x;
 325         dz = localFrustum.axis[2].x;
 326         index = ( FLOATSIGNBITSET( dy ) << 1 ) | FLOATSIGNBITSET( dz );
 327         dx = cornerVecs[index].x;
 328         index |= ( FLOATSIGNBITSET( dx ) << 2 );
 329
 330         if ( indexPoints[index].x > dFar ) {
 331                 return true;
 332         }
 333
 334         leftScale = dLeft * invFar;
 335
 336         // test left plane
 337         dy = dFar * localFrustum.axis[1].y - dLeft * localFrustum.axis[1].x;
 338         dz = dFar * localFrustum.axis[2].y - dLeft * localFrustum.axis[2].x;
 339         index = ( FLOATSIGNBITSET( dy ) << 1 ) | FLOATSIGNBITSET( dz );
 340         dx = dFar * cornerVecs[index].y - dLeft * cornerVecs[index].x;
 341         index |= ( FLOATSIGNBITSET( dx ) << 2 );
 342
 343         if ( indexPoints[index].y > indexPoints[index].x * leftScale ) {
 344                 return true;
 345         }
 346
 347         // test right plane
 348         dy = -dFar * localFrustum.axis[1].y - dLeft * localFrustum.axis[1].x;
 349         dz = -dFar * localFrustum.axis[2].y - dLeft * localFrustum.axis[2].x;
 350         index = ( FLOATSIGNBITSET( dy ) << 1 ) | FLOATSIGNBITSET( dz );
 351         dx = -dFar * cornerVecs[index].y - dLeft * cornerVecs[index].x;
 352         index |= ( FLOATSIGNBITSET( dx ) << 2 );
 353
 354         if ( indexPoints[index].y < -indexPoints[index].x * leftScale ) {
 355                 return true;
 356         }
 357
 358         upScale = dUp * invFar;
 359
 360         // test up plane
 361         dy = dFar * localFrustum.axis[1].z - dUp * localFrustum.axis[1].x;
 362         dz = dFar * localFrustum.axis[2].z - dUp * localFrustum.axis[2].x;
 363         index = ( FLOATSIGNBITSET( dy ) << 1 ) | FLOATSIGNBITSET( dz );
 364         dx = dFar * cornerVecs[index].z - dUp * cornerVecs[index].x;
 365         index |= ( FLOATSIGNBITSET( dx ) << 2 );
 366
 367         if ( indexPoints[index].z > indexPoints[index].x * upScale ) {
 368                 return true;
 369         }
 370
 371         // test down plane
 372         dy = -dFar * localFrustum.axis[1].z - dUp * localFrustum.axis[1].x;
 373         dz = -dFar * localFrustum.axis[2].z - dUp * localFrustum.axis[2].x;
 374         index = ( FLOATSIGNBITSET( dy ) << 1 ) | FLOATSIGNBITSET( dz );
 375         dx = -dFar * cornerVecs[index].z - dUp * cornerVecs[index].x;
 376         index |= ( FLOATSIGNBITSET( dx ) << 2 );
 377
 378         if ( indexPoints[index].z < -indexPoints[index].x * upScale ) {
 379                 return true;
 380         }
 381
 382         return false;
 383 }
 384
 385 /*
 386 ============
 387 idFrustum::CullFrustum
 388
 389   Tests if any of the planes of this frustum can be used as a separating plane.
 390
 391   58 muls best case
 392   88 muls worst case
 393 ============
 394 */
 395 bool idFrustum::CullFrustum( const idFrustum &frustum ) const {
 396         idFrustum localFrustum;
 397         idVec3 indexPoints[8], cornerVecs[4];
 398
 399         // transform the given frustum into the space of this frustum
 400         localFrustum = frustum;
 401         localFrustum.origin = ( frustum.origin - origin ) * axis.Transpose();
 402         localFrustum.axis = frustum.axis * axis.Transpose();
 403
 404         localFrustum.ToIndexPointsAndCornerVecs( indexPoints, cornerVecs );
 405
 406         return CullLocalFrustum( localFrustum, indexPoints, cornerVecs );
 407 }
 408
 409 /*
 410 ============
 411 idFrustum::CullLocalWinding
 412 ============
 413 */
 414 bool idFrustum::CullLocalWinding( const idVec3 *points, const int numPoints, int *pointCull ) const {
 415         int i, pCull, culled;
 416         float leftScale, upScale;
 417
 418         leftScale = dLeft * invFar;
 419         upScale = dUp * invFar;
 420
 421         culled = -1;
 422         for ( i = 0; i < numPoints; i++ ) {
 423                 const idVec3 &p = points[i];
 424                 pCull = 0;
 425                 if ( p.x < dNear ) {
 426                         pCull = 1;
 427                 }
 428                 else if ( p.x > dFar ) {
 429                         pCull = 2;
 430                 }
 431                 if ( idMath::Fabs( p.y ) > p.x * leftScale ) {
 432                         pCull |= 4 << FLOATSIGNBITSET( p.y );
 433                 }
 434                 if ( idMath::Fabs( p.z ) > p.x * upScale ) {
 435                         pCull |= 16 << FLOATSIGNBITSET( p.z );
 436                 }
 437                 culled &= pCull;
 438                 pointCull[i] = pCull;
 439         }
 440
 441         return ( culled != 0 );
 442 }
 443
 444 /*
 445 ============
 446 idFrustum::CullWinding
 447 ============
 448 */
 449 bool idFrustum::CullWinding( const idWinding &winding ) const {
 450         int i, *pointCull;
 451         idVec3 *localPoints;
 452         idMat3 transpose;
 453
 454         localPoints = (idVec3 *) _alloca16( winding.GetNumPoints() * sizeof( idVec3 ) );
 455         pointCull = (int *) _alloca16( winding.GetNumPoints() * sizeof( int ) );
 456
 457         transpose = axis.Transpose();
 458         for ( i = 0; i < winding.GetNumPoints(); i++ ) {
 459                 localPoints[i] = ( winding[i].ToVec3() - origin ) * transpose;
 460         }
 461
 462         return CullLocalWinding( localPoints, winding.GetNumPoints(), pointCull );
 463 }
 464
 465 /*
 466 ============
 467 idFrustum::BoundsCullLocalFrustum
 468
 469   Tests if any of the bounding box planes can be used as a separating plane.
 470 ============
 471 */
 472 bool idFrustum::BoundsCullLocalFrustum( const idBounds &bounds, const idFrustum &localFrustum, const idVec3 indexPoints[8], const idVec3 cornerVecs[4] ) const {
 473         int index;
 474         float dx, dy, dz;
 475
 476         dy = -localFrustum.axis[1].x;
 477         dz = -localFrustum.axis[2].x;
 478         index = ( FLOATSIGNBITSET( dy ) << 1 ) | FLOATSIGNBITSET( dz );
 479         dx = -cornerVecs[index].x;
 480         index |= ( FLOATSIGNBITSET( dx ) << 2 );
 481
 482         if ( indexPoints[index].x < bounds[0].x ) {
 483                 return true;
 484         }
 485
 486         dy = localFrustum.axis[1].x;
 487         dz = localFrustum.axis[2].x;
 488         index = ( FLOATSIGNBITSET( dy ) << 1 ) | FLOATSIGNBITSET( dz );
 489         dx = cornerVecs[index].x;
 490         index |= ( FLOATSIGNBITSET( dx ) << 2 );
 491
 492         if ( indexPoints[index].x > bounds[1].x ) {
 493                 return true;
 494         }
 495
 496         dy = -localFrustum.axis[1].y;
 497         dz = -localFrustum.axis[2].y;
 498         index = ( FLOATSIGNBITSET( dy ) << 1 ) | FLOATSIGNBITSET( dz );
 499         dx = -cornerVecs[index].y;
 500         index |= ( FLOATSIGNBITSET( dx ) << 2 );
 501
 502         if ( indexPoints[index].y < bounds[0].y ) {
 503                 return true;
 504         }
 505
 506         dy = localFrustum.axis[1].y;
 507         dz = localFrustum.axis[2].y;
 508         index = ( FLOATSIGNBITSET( dy ) << 1 ) | FLOATSIGNBITSET( dz );
 509         dx = cornerVecs[index].y;
 510         index |= ( FLOATSIGNBITSET( dx ) << 2 );
 511
 512         if ( indexPoints[index].y > bounds[1].y ) {
 513                 return true;
 514         }
 515
 516         dy = -localFrustum.axis[1].z;
 517         dz = -localFrustum.axis[2].z;
 518         index = ( FLOATSIGNBITSET( dy ) << 1 ) | FLOATSIGNBITSET( dz );
 519         dx = -cornerVecs[index].z;
 520         index |= ( FLOATSIGNBITSET( dx ) << 2 );
 521
 522         if ( indexPoints[index].z < bounds[0].z ) {
 523                 return true;
 524         }
 525
 526         dy = localFrustum.axis[1].z;
 527         dz = localFrustum.axis[2].z;
 528         index = ( FLOATSIGNBITSET( dy ) << 1 ) | FLOATSIGNBITSET( dz );
 529         dx = cornerVecs[index].z;
 530         index |= ( FLOATSIGNBITSET( dx ) << 2 );
 531
 532         if ( indexPoints[index].z > bounds[1].z ) {
 533                 return true;
 534         }
 535
 536         return false;
 537 }
 538
 539 /*
 540 ============
 541 idFrustum::LocalLineIntersection
 542
 543    7 divs
 544   30 muls
 545 ============
 546 */
 547 bool idFrustum::LocalLineIntersection( const idVec3 &start, const idVec3 &end ) const {
 548         idVec3 dir;
 549         float d1, d2, fstart, fend, lstart, lend, f, x;
 550         float leftScale, upScale;
 551         int startInside = 1;
 552
 553         leftScale = dLeft * invFar;
 554         upScale = dUp * invFar;
 555         dir = end - start;
 556
 557         // test near plane
 558         if ( dNear > 0.0f ) {
 559                 d1 = dNear - start.x;
 560                 startInside &= FLOATSIGNBITSET( d1 );
 561                 if ( FLOATNOTZERO( d1 ) ) {
 562                         d2 = dNear - end.x;
 563                         if ( FLOATSIGNBITSET( d1 ) ^ FLOATSIGNBITSET( d2 ) ) {
 564                                 f = d1 / ( d1 - d2 );
 565                                 if ( idMath::Fabs( start.y + f * dir.y ) <= dNear * leftScale ) {
 566                                         if ( idMath::Fabs( start.z + f * dir.z ) <= dNear * upScale ) {
 567                                                 return true;
 568                                         }
 569                                 }
 570                         }
 571                 }
 572         }
 573
 574         // test far plane
 575         d1 = start.x - dFar;
 576         startInside &= FLOATSIGNBITSET( d1 );
 577         if ( FLOATNOTZERO( d1 ) ) {
 578                 d2 = end.x - dFar;
 579                 if ( FLOATSIGNBITSET( d1 ) ^ FLOATSIGNBITSET( d2 ) ) {
 580                         f = d1 / ( d1 - d2 );
 581                         if ( idMath::Fabs( start.y + f * dir.y ) <= dFar * leftScale ) {
 582                                 if ( idMath::Fabs( start.z + f * dir.z ) <= dFar * upScale ) {
 583                                         return true;
 584                                 }
 585                         }
 586                 }
 587         }
 588
 589         fstart = dFar * start.y;
 590         fend = dFar * end.y;
 591         lstart = dLeft * start.x;
 592         lend = dLeft * end.x;
 593
 594         // test left plane
 595         d1 = fstart - lstart;
 596         startInside &= FLOATSIGNBITSET( d1 );
 597         if ( FLOATNOTZERO( d1 ) ) {
 598                 d2 = fend - lend;
 599                 if ( FLOATSIGNBITSET( d1 ) ^ FLOATSIGNBITSET( d2 ) ) {
 600                         f = d1 / ( d1 - d2 );
 601                         x = start.x + f * dir.x;
 602                         if ( x >= dNear && x <= dFar ) {
 603                                 if ( idMath::Fabs( start.z + f * dir.z ) <= x * upScale ) {
 604                                         return true;
 605                                 }
 606                         }
 607                 }
 608         }
 609
 610         // test right plane
 611         d1 = -fstart - lstart;
 612         startInside &= FLOATSIGNBITSET( d1 );
 613         if ( FLOATNOTZERO( d1 ) ) {
 614                 d2 = -fend - lend;
 615                 if ( FLOATSIGNBITSET( d1 ) ^ FLOATSIGNBITSET( d2 ) ) {
 616                         f = d1 / ( d1 - d2 );
 617                         x = start.x + f * dir.x;
 618                         if ( x >= dNear && x <= dFar ) {
 619                                 if ( idMath::Fabs( start.z + f * dir.z ) <= x * upScale ) {
 620                                         return true;
 621                                 }
 622                         }
 623                 }
 624         }
 625
 626         fstart = dFar * start.z;
 627         fend = dFar * end.z;
 628         lstart = dUp * start.x;
 629         lend = dUp * end.x;
 630
 631         // test up plane
 632         d1 = fstart - lstart;
 633         startInside &= FLOATSIGNBITSET( d1 );
 634         if ( FLOATNOTZERO( d1 ) ) {
 635                 d2 = fend - lend;
 636                 if ( FLOATSIGNBITSET( d1 ) ^ FLOATSIGNBITSET( d2 ) ) {
 637                         f = d1 / ( d1 - d2 );
 638                         x = start.x + f * dir.x;
 639                         if ( x >= dNear && x <= dFar ) {
 640                                 if ( idMath::Fabs( start.y + f * dir.y ) <= x * leftScale ) {
 641                                         return true;
 642                                 }
 643                         }
 644                 }
 645         }
 646
 647         // test down plane
 648         d1 = -fstart - lstart;
 649         startInside &= FLOATSIGNBITSET( d1 );
 650         if ( FLOATNOTZERO( d1 ) ) {
 651                 d2 = -fend - lend;
 652                 if ( FLOATSIGNBITSET( d1 ) ^ FLOATSIGNBITSET( d2 ) ) {
 653                         f = d1 / ( d1 - d2 );
 654                         x = start.x + f * dir.x;
 655                         if ( x >= dNear && x <= dFar ) {
 656                                 if ( idMath::Fabs( start.y + f * dir.y ) <= x * leftScale ) {
 657                                         return true;
 658                                 }
 659                         }
 660                 }
 661         }
 662
 663         return ( startInside != 0 );
 664 }
 665
 666 /*
 667 ============
 668 idFrustum::LocalRayIntersection
 669
 670   Returns true if the ray starts inside the frustum.
 671   If there was an intersection scale1 <= scale2
 672 ============
 673 */
 674 bool idFrustum::LocalRayIntersection( const idVec3 &start, const idVec3 &dir, float &scale1, float &scale2 ) const {
 675         idVec3 end;
 676         float d1, d2, fstart, fend, lstart, lend, f, x;
 677         float leftScale, upScale;
 678         int startInside = 1;
 679
 680         leftScale = dLeft * invFar;
 681         upScale = dUp * invFar;
 682         end = start + dir;
 683
 684         scale1 = idMath::INFINITY;
 685         scale2 = -idMath::INFINITY;
 686
 687         // test near plane
 688         if ( dNear > 0.0f ) {
 689                 d1 = dNear - start.x;
 690                 startInside &= FLOATSIGNBITSET( d1 );
 691                 d2 = dNear - end.x;
 692                 if ( d1 != d2 ) {
 693                         f = d1 / ( d1 - d2 );
 694                         if ( idMath::Fabs( start.y + f * dir.y ) <= dNear * leftScale ) {
 695                                 if ( idMath::Fabs( start.z + f * dir.z ) <= dNear * upScale ) {
 696                                         if ( f < scale1 ) scale1 = f;
 697                                         if ( f > scale2 ) scale2 = f;
 698                                 }
 699                         }
 700                 }
 701         }
 702
 703         // test far plane
 704         d1 = start.x - dFar;
 705         startInside &= FLOATSIGNBITSET( d1 );
 706         d2 = end.x - dFar;
 707         if ( d1 != d2 ) {
 708                 f = d1 / ( d1 - d2 );
 709                 if ( idMath::Fabs( start.y + f * dir.y ) <= dFar * leftScale ) {
 710                         if ( idMath::Fabs( start.z + f * dir.z ) <= dFar * upScale ) {
 711                                 if ( f < scale1 ) scale1 = f;
 712                                 if ( f > scale2 ) scale2 = f;
 713                         }
 714                 }
 715         }
 716
 717         fstart = dFar * start.y;
 718         fend = dFar * end.y;
 719         lstart = dLeft * start.x;
 720         lend = dLeft * end.x;
 721
 722         // test left plane
 723         d1 = fstart - lstart;
 724         startInside &= FLOATSIGNBITSET( d1 );
 725         d2 = fend - lend;
 726         if ( d1 != d2 ) {
 727                 f = d1 / ( d1 - d2 );
 728                 x = start.x + f * dir.x;
 729                 if ( x >= dNear && x <= dFar ) {
 730                         if ( idMath::Fabs( start.z + f * dir.z ) <= x * upScale ) {
 731                                 if ( f < scale1 ) scale1 = f;
 732                                 if ( f > scale2 ) scale2 = f;
 733                         }
 734                 }
 735         }
 736
 737         // test right plane
 738         d1 = -fstart - lstart;
 739         startInside &= FLOATSIGNBITSET( d1 );
 740         d2 = -fend - lend;
 741         if ( d1 != d2 ) {
 742                 f = d1 / ( d1 - d2 );
 743                 x = start.x + f * dir.x;
 744                 if ( x >= dNear && x <= dFar ) {
 745                         if ( idMath::Fabs( start.z + f * dir.z ) <= x * upScale ) {
 746                                 if ( f < scale1 ) scale1 = f;
 747                                 if ( f > scale2 ) scale2 = f;
 748                         }
 749                 }
 750         }
 751
 752         fstart = dFar * start.z;
 753         fend = dFar * end.z;
 754         lstart = dUp * start.x;
 755         lend = dUp * end.x;
 756
 757         // test up plane
 758         d1 = fstart - lstart;
 759         startInside &= FLOATSIGNBITSET( d1 );
 760         d2 = fend - lend;
 761         if ( d1 != d2 ) {
 762                 f = d1 / ( d1 - d2 );
 763                 x = start.x + f * dir.x;
 764                 if ( x >= dNear && x <= dFar ) {
 765                         if ( idMath::Fabs( start.y + f * dir.y ) <= x * leftScale ) {
 766                                 if ( f < scale1 ) scale1 = f;
 767                                 if ( f > scale2 ) scale2 = f;
 768                         }
 769                 }
 770         }
 771
 772         // test down plane
 773         d1 = -fstart - lstart;
 774         startInside &= FLOATSIGNBITSET( d1 );
 775         d2 = -fend - lend;
 776         if ( d1 != d2 ) {
 777                 f = d1 / ( d1 - d2 );
 778                 x = start.x + f * dir.x;
 779                 if ( x >= dNear && x <= dFar ) {
 780                         if ( idMath::Fabs( start.y + f * dir.y ) <= x * leftScale ) {
 781                                 if ( f < scale1 ) scale1 = f;
 782                                 if ( f > scale2 ) scale2 = f;
 783                         }
 784                 }
 785         }
 786
 787         return ( startInside != 0 );
 788 }
 789
 790 /*
 791 ============
 792 idFrustum::ContainsPoint
 793 ============
 794 */
 795 bool idFrustum::ContainsPoint( const idVec3 &point ) const {
 796         return !CullPoint( point );
 797 }
 798
 799 /*
 800 ============
 801 idFrustum::LocalFrustumIntersectsFrustum
 802 ============
 803 */
 804 bool idFrustum::LocalFrustumIntersectsFrustum( const idVec3 points[8], const bool testFirstSide ) const {
 805         int i;
 806
 807         // test if any edges of the other frustum intersect this frustum
 808         for ( i = 0; i < 4; i++ ) {
 809                 if ( LocalLineIntersection( points[i], points[4+i] ) ) {
 810                         return true;
 811                 }
 812         }
 813         if ( testFirstSide ) {
 814                 for ( i = 0; i < 4; i++ ) {
 815                         if ( LocalLineIntersection( points[i], points[(i+1)&3] ) ) {
 816                                 return true;
 817                         }
 818                 }
 819         }
 820         for ( i = 0; i < 4; i++ ) {
 821                 if ( LocalLineIntersection( points[4+i], points[4+((i+1)&3)] ) ) {
 822                         return true;
 823                 }
 824         }
 825
 826         return false;
 827 }
 828
 829 /*
 830 ============
 831 idFrustum::LocalFrustumIntersectsBounds
 832 ============
 833 */
 834 bool idFrustum::LocalFrustumIntersectsBounds( const idVec3 points[8], const idBounds &bounds ) const {
 835         int i;
 836
 837         // test if any edges of the other frustum intersect this frustum
 838         for ( i = 0; i < 4; i++ ) {
 839                 if ( bounds.LineIntersection( points[i], points[4+i] ) ) {
 840                         return true;
 841                 }
 842         }
 843         if ( dNear > 0.0f ) {
 844                 for ( i = 0; i < 4; i++ ) {
 845                         if ( bounds.LineIntersection( points[i], points[(i+1)&3] ) ) {
 846                                 return true;
 847                         }
 848                 }
 849         }
 850         for ( i = 0; i < 4; i++ ) {
 851                 if ( bounds.LineIntersection( points[4+i], points[4+((i+1)&3)] ) ) {
 852                         return true;
 853                 }
 854         }
 855
 856         return false;
 857 }
 858
 859 /*
 860 ============
 861 idFrustum::IntersectsBounds
 862 ============
 863 */
 864 bool idFrustum::IntersectsBounds( const idBounds &bounds ) const {
 865         idVec3 localOrigin, center, extents;
 866         idMat3 localAxis;
 867
 868         center = ( bounds[0] + bounds[1] ) * 0.5f;
 869         extents = bounds[1] - center;
 870
 871         localOrigin = ( center - origin ) * axis.Transpose();
 872         localAxis = axis.Transpose();
 873
 874         if ( CullLocalBox( localOrigin, extents, localAxis ) ) {
 875                 return false;
 876         }
 877
 878         idVec3 indexPoints[8], cornerVecs[4];
 879
 880         ToIndexPointsAndCornerVecs( indexPoints, cornerVecs );
 881
 882         if ( BoundsCullLocalFrustum( bounds, *this, indexPoints, cornerVecs ) ) {
 883                 return false;
 884         }
 885
 886         idSwap( indexPoints[2], indexPoints[3] );
 887         idSwap( indexPoints[6], indexPoints[7] );
 888
 889         if ( LocalFrustumIntersectsBounds( indexPoints, bounds ) ) {
 890                 return true;
 891         }
 892
 893         BoxToPoints( localOrigin, extents, localAxis, indexPoints );
 894
 895         if ( LocalFrustumIntersectsFrustum( indexPoints, true ) ) {
 896                 return true;
 897         }
 898
 899         return false;
 900 }
 901
 902 /*
 903 ============
 904 idFrustum::IntersectsBox
 905 ============
 906 */
 907 bool idFrustum::IntersectsBox( const idBox &box ) const {
 908         idVec3 localOrigin;
 909         idMat3 localAxis;
 910
 911         localOrigin = ( box.GetCenter() - origin ) * axis.Transpose();
 912         localAxis = box.GetAxis() * axis.Transpose();
 913
 914         if ( CullLocalBox( localOrigin, box.GetExtents(), localAxis ) ) {
 915                 return false;
 916         }
 917
 918         idVec3 indexPoints[8], cornerVecs[4];
 919         idFrustum localFrustum;
 920
 921         localFrustum = *this;
 922         localFrustum.origin = ( origin - box.GetCenter() ) * box.GetAxis().Transpose();
 923         localFrustum.axis = axis * box.GetAxis().Transpose();
 924         localFrustum.ToIndexPointsAndCornerVecs( indexPoints, cornerVecs );
 925
 926         if ( BoundsCullLocalFrustum( idBounds( -box.GetExtents(), box.GetExtents() ), localFrustum, indexPoints, cornerVecs ) ) {
 927                 return false;
 928         }
 929
 930         idSwap( indexPoints[2], indexPoints[3] );
 931         idSwap( indexPoints[6], indexPoints[7] );
 932
 933         if ( LocalFrustumIntersectsBounds( indexPoints, idBounds( -box.GetExtents(), box.GetExtents() ) ) ) {
 934                 return true;
 935         }
 936
 937         BoxToPoints( localOrigin, box.GetExtents(), localAxis, indexPoints );
 938
 939         if ( LocalFrustumIntersectsFrustum( indexPoints, true ) ) {
 940                 return true;
 941         }
 942
 943         return false;
 944 }
 945
 946 /*
 947 ============
 948 idFrustum::IntersectsSphere
 949
 950   FIXME: test this
 951 ============
 952 */
 953 #define VORONOI_INDEX( x, y, z )        ( x + y * 3 + z * 9 )
 954
 955 bool idFrustum::IntersectsSphere( const idSphere &sphere ) const {
 956         int index, x, y, z;
 957         float scale, r, d;
 958         idVec3 p, dir, points[8];
 959
 960         if ( CullSphere( sphere ) ) {
 961                 return false;
 962         }
 963
 964         x = y = z = 0;
 965         dir.Zero();
 966
 967         p = ( sphere.GetOrigin() - origin ) * axis.Transpose();
 968
 969         if ( p.x <= dNear ) {
 970                 scale = dNear * invFar;
 971                 dir.y = idMath::Fabs( p.y ) - dLeft * scale;
 972                 dir.z = idMath::Fabs( p.z ) - dUp * scale;
 973         }
 974         else if ( p.x >= dFar ) {
 975                 dir.y = idMath::Fabs( p.y ) - dLeft;
 976                 dir.z = idMath::Fabs( p.z ) - dUp;
 977         }
 978         else {
 979                 scale = p.x * invFar;
 980                 dir.y = idMath::Fabs( p.y ) - dLeft * scale;
 981                 dir.z = idMath::Fabs( p.z ) - dUp * scale;
 982         }
 983         if ( dir.y > 0.0f ) {
 984                 y = ( 1 + FLOATSIGNBITNOTSET( p.y ) );
 985         }
 986         if ( dir.z > 0.0f ) {
 987                 z = ( 1 + FLOATSIGNBITNOTSET( p.z ) );
 988         }
 989         if ( p.x < dNear ) {
 990                 scale = dLeft * dNear * invFar;
 991                 if ( p.x < dNear + ( scale - p.y ) * scale * invFar ) {
 992                         scale = dUp * dNear * invFar;
 993                         if ( p.x < dNear + ( scale - p.z ) * scale * invFar ) {
 994                                 x = 1;
 995                         }
 996                 }
 997         }
 998         else {
 999                 if ( p.x > dFar ) {
1000                         x = 2;
1001                 }
1002                 else if ( p.x > dFar + ( dLeft - p.y ) * dLeft * invFar ) {
1003                         x = 2;
1004                 }
1005                 else if ( p.x > dFar + ( dUp - p.z ) * dUp * invFar ) {
1006                         x = 2;
1007                 }
1008         }
1009
1010         r = sphere.GetRadius();
1011         index = VORONOI_INDEX( x, y, z );
1012         switch( index ) {
1013                 case VORONOI_INDEX( 0, 0, 0 ): return true;
1014                 case VORONOI_INDEX( 1, 0, 0 ): return ( dNear - p.x < r );
1015                 case VORONOI_INDEX( 2, 0, 0 ): return ( p.x - dFar < r );
1016                 case VORONOI_INDEX( 0, 1, 0 ): d = dFar * p.y - dLeft * p.x; return ( d * d < r * r * ( dFar * dFar + dLeft * dLeft ) );
1017                 case VORONOI_INDEX( 0, 2, 0 ): d = -dFar * p.z - dLeft * p.x; return ( d * d < r * r * ( dFar * dFar + dLeft * dLeft ) );
1018                 case VORONOI_INDEX( 0, 0, 1 ): d = dFar * p.z - dUp * p.x; return ( d * d < r * r * ( dFar * dFar + dUp * dUp ) );
1019                 case VORONOI_INDEX( 0, 0, 2 ): d = -dFar * p.z - dUp * p.x; return ( d * d < r * r * ( dFar * dFar + dUp * dUp ) );
1020                 default: {
1021                         ToIndexPoints( points );
1022                         switch( index ) {
1023                                 case VORONOI_INDEX( 1, 1, 1 ): return sphere.ContainsPoint( points[0] );
1024                                 case VORONOI_INDEX( 2, 1, 1 ): return sphere.ContainsPoint( points[4] );
1025                                 case VORONOI_INDEX( 1, 2, 1 ): return sphere.ContainsPoint( points[1] );
1026                                 case VORONOI_INDEX( 2, 2, 1 ): return sphere.ContainsPoint( points[5] );
1027                                 case VORONOI_INDEX( 1, 1, 2 ): return sphere.ContainsPoint( points[2] );
1028                                 case VORONOI_INDEX( 2, 1, 2 ): return sphere.ContainsPoint( points[6] );
1029                                 case VORONOI_INDEX( 1, 2, 2 ): return sphere.ContainsPoint( points[3] );
1030                                 case VORONOI_INDEX( 2, 2, 2 ): return sphere.ContainsPoint( points[7] );
1031                                 case VORONOI_INDEX( 1, 1, 0 ): return sphere.LineIntersection( points[0], points[2] );
1032                                 case VORONOI_INDEX( 2, 1, 0 ): return sphere.LineIntersection( points[4], points[6] );
1033                                 case VORONOI_INDEX( 1, 2, 0 ): return sphere.LineIntersection( points[1], points[3] );
1034                                 case VORONOI_INDEX( 2, 2, 0 ): return sphere.LineIntersection( points[5], points[7] );
1035                                 case VORONOI_INDEX( 1, 0, 1 ): return sphere.LineIntersection( points[0], points[1] );
1036                                 case VORONOI_INDEX( 2, 0, 1 ): return sphere.LineIntersection( points[4], points[5] );
1037                                 case VORONOI_INDEX( 0, 1, 1 ): return sphere.LineIntersection( points[0], points[4] );
1038                                 case VORONOI_INDEX( 0, 2, 1 ): return sphere.LineIntersection( points[1], points[5] );
1039                                 case VORONOI_INDEX( 1, 0, 2 ): return sphere.LineIntersection( points[2], points[3] );
1040                                 case VORONOI_INDEX( 2, 0, 2 ): return sphere.LineIntersection( points[6], points[7] );
1041                                 case VORONOI_INDEX( 0, 1, 2 ): return sphere.LineIntersection( points[2], points[6] );
1042                                 case VORONOI_INDEX( 0, 2, 2 ): return sphere.LineIntersection( points[3], points[7] );
1043                         }
1044                         break;
1045                 }
1046         }
1047         return false;
1048 }
1049
1050 /*
1051 ============
1052 idFrustum::IntersectsFrustum
1053 ============
1054 */
1055 bool idFrustum::IntersectsFrustum( const idFrustum &frustum ) const {
1056         idVec3 indexPoints2[8], cornerVecs2[4];
1057         idFrustum localFrustum2;
1058
1059         localFrustum2 = frustum;
1060         localFrustum2.origin = ( frustum.origin - origin ) * axis.Transpose();
1061         localFrustum2.axis = frustum.axis * axis.Transpose();
1062         localFrustum2.ToIndexPointsAndCornerVecs( indexPoints2, cornerVecs2 );
1063
1064         if ( CullLocalFrustum( localFrustum2, indexPoints2, cornerVecs2 ) ) {
1065                 return false;
1066         }
1067
1068         idVec3 indexPoints1[8], cornerVecs1[4];
1069         idFrustum localFrustum1;
1070
1071         localFrustum1 = *this;
1072         localFrustum1.origin = ( origin - frustum.origin ) * frustum.axis.Transpose();
1073         localFrustum1.axis = axis * frustum.axis.Transpose();
1074         localFrustum1.ToIndexPointsAndCornerVecs( indexPoints1, cornerVecs1 );
1075
1076         if ( frustum.CullLocalFrustum( localFrustum1, indexPoints1, cornerVecs1 ) ) {
1077                 return false;
1078         }
1079
1080         idSwap( indexPoints2[2], indexPoints2[3] );
1081         idSwap( indexPoints2[6], indexPoints2[7] );
1082
1083         if ( LocalFrustumIntersectsFrustum( indexPoints2, ( localFrustum2.dNear > 0.0f ) ) ) {
1084                 return true;
1085         }
1086
1087         idSwap( indexPoints1[2], indexPoints1[3] );
1088         idSwap( indexPoints1[6], indexPoints1[7] );
1089
1090         if ( frustum.LocalFrustumIntersectsFrustum( indexPoints1, ( localFrustum1.dNear > 0.0f ) ) ) {
1091                 return true;
1092         }
1093
1094         return false;
1095 }
1096
1097 /*
1098 ============
1099 idFrustum::IntersectsWinding
1100 ============
1101 */
1102 bool idFrustum::IntersectsWinding( const idWinding &winding ) const {
1103         int i, j, *pointCull;
1104         float min, max;
1105         idVec3 *localPoints, indexPoints[8], cornerVecs[4];
1106         idMat3 transpose;
1107         idPlane plane;
1108
1109         localPoints = (idVec3 *) _alloca16( winding.GetNumPoints() * sizeof( idVec3 ) );
1110         pointCull = (int *) _alloca16( winding.GetNumPoints() * sizeof( int ) );
1111
1112         transpose = axis.Transpose();
1113         for ( i = 0; i < winding.GetNumPoints(); i++ ) {
1114                 localPoints[i] = ( winding[i].ToVec3() - origin ) * transpose;
1115         }
1116
1117         // if the winding is culled
1118         if ( CullLocalWinding( localPoints, winding.GetNumPoints(), pointCull ) ) {
1119                 return false;
1120         }
1121
1122         winding.GetPlane( plane );
1123
1124         ToIndexPointsAndCornerVecs( indexPoints, cornerVecs );
1125         AxisProjection( indexPoints, cornerVecs, plane.Normal(), min, max );
1126
1127         // if the frustum does not cross the winding plane
1128         if ( min + plane[3] > 0.0f || max + plane[3] < 0.0f ) {
1129                 return false;
1130         }
1131
1132         // test if any of the winding edges goes through the frustum
1133         for ( i = 0; i < winding.GetNumPoints(); i++ ) {
1134                 j = (i+1)%winding.GetNumPoints();
1135                 if ( !( pointCull[i] & pointCull[j] ) ) {
1136                         if ( LocalLineIntersection( localPoints[i], localPoints[j] ) ) {
1137                                 return true;
1138                         }
1139                 }
1140         }
1141
1142         idSwap( indexPoints[2], indexPoints[3] );
1143         idSwap( indexPoints[6], indexPoints[7] );
1144
1145         // test if any edges of the frustum intersect the winding
1146         for ( i = 0; i < 4; i++ ) {
1147                 if ( winding.LineIntersection( plane, indexPoints[i], indexPoints[4+i] ) ) {
1148                         return true;
1149                 }
1150         }
1151         if ( dNear > 0.0f ) {
1152                 for ( i = 0; i < 4; i++ ) {
1153                         if ( winding.LineIntersection( plane, indexPoints[i], indexPoints[(i+1)&3] ) ) {
1154                                 return true;
1155                         }
1156                 }
1157         }
1158         for ( i = 0; i < 4; i++ ) {
1159                 if ( winding.LineIntersection( plane, indexPoints[4+i], indexPoints[4+((i+1)&3)] ) ) {
1160                         return true;
1161                 }
1162         }
1163
1164         return false;
1165 }
1166
1167 /*
1168 ============
1169 idFrustum::LineIntersection
1170
1171   Returns true if the line intersects the box between the start and end point.
1172 ============
1173 */
1174 bool idFrustum::LineIntersection( const idVec3 &start, const idVec3 &end ) const {
1175         return LocalLineIntersection( ( start - origin ) * axis.Transpose(), ( end - origin ) * axis.Transpose() );
1176 }
1177
1178 /*
1179 ============
1180 idFrustum::RayIntersection
1181
1182   Returns true if the ray intersects the bounds.
1183   The ray can intersect the bounds in both directions from the start point.
1184   If start is inside the frustum then scale1 < 0 and scale2 > 0.
1185 ============
1186 */
1187 bool idFrustum::RayIntersection( const idVec3 &start, const idVec3 &dir, float &scale1, float &scale2 ) const {
1188         if ( LocalRayIntersection( ( start - origin ) * axis.Transpose(), dir * axis.Transpose(), scale1, scale2 ) ) {
1189                 return true;
1190         }
1191         if ( scale1 <= scale2 ) {
1192                 return true;
1193         }
1194         return false;
1195 }
1196
1197 /*
1198 ============
1199 idFrustum::FromProjection
1200
1201   Creates a frustum which contains the projection of the bounds.
1202 ============
1203 */
1204 bool idFrustum::FromProjection( const idBounds &bounds, const idVec3 &projectionOrigin, const float dFar ) {
1205         return FromProjection( idBox( bounds, vec3_origin, mat3_identity ), projectionOrigin, dFar );
1206 }
1207
1208 /*
1209 ============
1210 idFrustum::FromProjection
1211
1212   Creates a frustum which contains the projection of the box.
1213 ============
1214 */
1215 bool idFrustum::FromProjection( const idBox &box, const idVec3 &projectionOrigin, const float dFar ) {
1216         int i, bestAxis;
1217         float value, bestValue;
1218         idVec3 dir;
1219
1220         assert( dFar > 0.0f );
1221
1222         this->dNear = this->dFar = this->invFar = 0.0f;
1223
1224         dir = box.GetCenter() - projectionOrigin;
1225         if ( dir.Normalize() == 0.0f ) {
1226                 return false;
1227         }
1228
1229         bestAxis = 0;
1230         bestValue = idMath::Fabs( box.GetAxis()[0] * dir );
1231         for ( i = 1; i < 3; i++ ) {
1232                 value = idMath::Fabs( box.GetAxis()[i] * dir );
1233                 if ( value * box.GetExtents()[bestAxis] * box.GetExtents()[bestAxis] < bestValue * box.GetExtents()[i] * box.GetExtents()[i] ) {
1234                         bestValue = value;
1235                         bestAxis = i;
1236                 }
1237         }
1238
1239 #if 1
1240
1241         int j, minX, minY, maxY, minZ, maxZ;
1242         idVec3 points[8];
1243
1244         minX = minY = maxY = minZ = maxZ = 0;
1245
1246         for ( j = 0; j < 2; j++ ) {
1247
1248                 axis[0] = dir;
1249                 axis[1] = box.GetAxis()[bestAxis] - ( box.GetAxis()[bestAxis] * axis[0] ) * axis[0];
1250                 axis[1].Normalize();
1251                 axis[2].Cross( axis[0], axis[1] );
1252
1253                 BoxToPoints( ( box.GetCenter() - projectionOrigin ) * axis.Transpose(), box.GetExtents(), box.GetAxis() * axis.Transpose(), points );
1254
1255                 if ( points[0].x <= 1.0f ) {
1256                         return false;
1257                 }
1258
1259                 minX = minY = maxY = minZ = maxZ = 0;
1260                 for ( i = 1; i < 8; i++ ) {
1261                         if ( points[i].x <= 1.0f ) {
1262                                 return false;
1263                         }
1264                         if ( points[i].x < points[minX].x ) {
1265                                 minX = i;
1266                         }
1267                         if ( points[minY].x * points[i].y < points[i].x * points[minY].y ) {
1268                                 minY = i;
1269                         } else if ( points[maxY].x * points[i].y > points[i].x * points[maxY].y ) {
1270                                 maxY = i;
1271                         }
1272                         if ( points[minZ].x * points[i].z < points[i].x * points[minZ].z ) {
1273                                 minZ = i;
1274                         } else if ( points[maxZ].x * points[i].z > points[i].x * points[maxZ].z ) {
1275                                 maxZ = i;
1276                         }
1277                 }
1278
1279                 if ( j == 0 ) {
1280                         dir += idMath::Tan16( 0.5f * ( idMath::ATan16( points[minY].y, points[minY].x ) + idMath::ATan16( points[maxY].y, points[maxY].x ) ) ) * axis[1];
1281                         dir += idMath::Tan16( 0.5f * ( idMath::ATan16( points[minZ].z, points[minZ].x ) + idMath::ATan16( points[maxZ].z, points[maxZ].x ) ) ) * axis[2];
1282                         dir.Normalize();
1283                 }
1284         }
1285
1286         this->origin = projectionOrigin;
1287         this->dNear = points[minX].x;
1288         this->dFar = dFar;
1289         this->dLeft = Max( idMath::Fabs( points[minY].y / points[minY].x ), idMath::Fabs( points[maxY].y / points[maxY].x ) ) * dFar;
1290         this->dUp = Max( idMath::Fabs( points[minZ].z / points[minZ].x ), idMath::Fabs( points[maxZ].z / points[maxZ].x ) ) * dFar;
1291         this->invFar = 1.0f / dFar;
1292
1293 #elif 1
1294
1295         int j;
1296         float f, x;
1297         idBounds b;
1298         idVec3 points[8];
1299
1300         for ( j = 0; j < 2; j++ ) {
1301
1302                 axis[0] = dir;
1303                 axis[1] = box.GetAxis()[bestAxis] - ( box.GetAxis()[bestAxis] * axis[0] ) * axis[0];
1304                 axis[1].Normalize();
1305                 axis[2].Cross( axis[0], axis[1] );
1306
1307                 BoxToPoints( ( box.GetCenter() - projectionOrigin ) * axis.Transpose(), box.GetExtents(), box.GetAxis() * axis.Transpose(), points );
1308
1309                 b.Clear();
1310                 for ( i = 0; i < 8; i++ ) {
1311                         x = points[i].x;
1312                         if ( x <= 1.0f ) {
1313                                 return false;
1314                         }
1315                         f = 1.0f / x;
1316                         points[i].y *= f;
1317                         points[i].z *= f;
1318                         b.AddPoint( points[i] );
1319                 }
1320
1321                 if ( j == 0 ) {
1322                         dir += idMath::Tan16( 0.5f * ( idMath::ATan16( b[1][1] ) + idMath::ATan16( b[0][1] ) ) ) * axis[1];
1323                         dir += idMath::Tan16( 0.5f * ( idMath::ATan16( b[1][2] ) + idMath::ATan16( b[0][2] ) ) ) * axis[2];
1324                         dir.Normalize();
1325                 }
1326         }
1327
1328         this->origin = projectionOrigin;
1329         this->dNear = b[0][0];
1330         this->dFar = dFar;
1331         this->dLeft = Max( idMath::Fabs( b[0][1] ), idMath::Fabs( b[1][1] ) ) * dFar;
1332         this->dUp = Max( idMath::Fabs( b[0][2] ), idMath::Fabs( b[1][2] ) ) * dFar;
1333         this->invFar = 1.0f / dFar;
1334
1335 #else
1336
1337         float dist;
1338         idVec3 org;
1339
1340         axis[0] = dir;
1341         axis[1] = box.GetAxis()[bestAxis] - ( box.GetAxis()[bestAxis] * axis[0] ) * axis[0];
1342         axis[1].Normalize();
1343         axis[2].Cross( axis[0], axis[1] );
1344
1345         for ( i = 0; i < 3; i++ ) {
1346                 dist[i] = idMath::Fabs( box.GetExtents()[0] * ( axis[i] * box.GetAxis()[0] ) ) +
1347                                         idMath::Fabs( box.GetExtents()[1] * ( axis[i] * box.GetAxis()[1] ) ) +
1348                                                 idMath::Fabs( box.GetExtents()[2] * ( axis[i] * box.GetAxis()[2] ) );
1349         }
1350
1351         dist[0] = axis[0] * ( box.GetCenter() - projectionOrigin ) - dist[0];
1352         if ( dist[0] <= 1.0f ) {
1353                 return false;
1354         }
1355         float invDist = 1.0f / dist[0];
1356
1357         this->origin = projectionOrigin;
1358         this->dNear = dist[0];
1359         this->dFar = dFar;
1360         this->dLeft = dist[1] * invDist * dFar;
1361         this->dUp = dist[2] * invDist * dFar;
1362         this->invFar = 1.0f / dFar;
1363
1364 #endif
1365
1366         return true;
1367 }
1368
1369 /*
1370 ============
1371 idFrustum::FromProjection
1372
1373   Creates a frustum which contains the projection of the sphere.
1374 ============
1375 */
1376 bool idFrustum::FromProjection( const idSphere &sphere, const idVec3 &projectionOrigin, const float dFar ) {
1377         idVec3 dir;
1378         float d, r, s, x, y;
1379
1380         assert( dFar > 0.0f );
1381
1382         dir = sphere.GetOrigin() - projectionOrigin;
1383         d = dir.Normalize();
1384         r = sphere.GetRadius();
1385
1386         if ( d <= r + 1.0f ) {
1387                 this->dNear = this->dFar = this->invFar = 0.0f;
1388                 return false;
1389         }
1390
1391         origin = projectionOrigin;
1392         axis = dir.ToMat3();
1393
1394         s = idMath::Sqrt( d * d - r * r );
1395         x = r / d * s;
1396         y = idMath::Sqrt( s * s - x * x );
1397
1398         this->dNear = d - r;
1399         this->dFar = dFar;
1400         this->dLeft = x / y * dFar;
1401         this->dUp = dLeft;
1402         this->invFar = 1.0f / dFar;
1403
1404         return true;
1405 }
1406
1407 /*
1408 ============
1409 idFrustum::ConstrainToBounds
1410
1411   Returns false if no part of the bounds extends beyond the near plane.
1412 ============
1413 */
1414 bool idFrustum::ConstrainToBounds( const idBounds &bounds ) {
1415         float min, max, newdFar;
1416
1417         bounds.AxisProjection( axis[0], min, max );
1418         newdFar = max - axis[0] * origin;
1419         if ( newdFar <= dNear ) {
1420                 MoveFarDistance( dNear + 1.0f );
1421                 return false;
1422         }
1423         MoveFarDistance( newdFar );
1424         return true;
1425 }
1426
1427 /*
1428 ============
1429 idFrustum::ConstrainToBox
1430
1431   Returns false if no part of the box extends beyond the near plane.
1432 ============
1433 */
1434 bool idFrustum::ConstrainToBox( const idBox &box ) {
1435         float min, max, newdFar;
1436
1437         box.AxisProjection( axis[0], min, max );
1438         newdFar = max - axis[0] * origin;
1439         if ( newdFar <= dNear ) {
1440                 MoveFarDistance( dNear + 1.0f );
1441                 return false;
1442         }
1443         MoveFarDistance( newdFar );
1444         return true;
1445 }
1446
1447 /*
1448 ============
1449 idFrustum::ConstrainToSphere
1450
1451   Returns false if no part of the sphere extends beyond the near plane.
1452 ============
1453 */
1454 bool idFrustum::ConstrainToSphere( const idSphere &sphere ) {
1455         float min, max, newdFar;
1456
1457         sphere.AxisProjection( axis[0], min, max );
1458         newdFar = max - axis[0] * origin;
1459         if ( newdFar <= dNear ) {
1460                 MoveFarDistance( dNear + 1.0f );
1461                 return false;
1462         }
1463         MoveFarDistance( newdFar );
1464         return true;
1465 }
1466
1467 /*
1468 ============
1469 idFrustum::ConstrainToFrustum
1470
1471   Returns false if no part of the frustum extends beyond the near plane.
1472 ============
1473 */
1474 bool idFrustum::ConstrainToFrustum( const idFrustum &frustum ) {
1475         float min, max, newdFar;
1476
1477         frustum.AxisProjection( axis[0], min, max );
1478         newdFar = max - axis[0] * origin;
1479         if ( newdFar <= dNear ) {
1480                 MoveFarDistance( dNear + 1.0f );
1481                 return false;
1482         }
1483         MoveFarDistance( newdFar );
1484         return true;
1485 }
1486
1487 /*
1488 ============
1489 idFrustum::ToPlanes
1490
1491   planes point outwards
1492 ============
1493 */
1494 void idFrustum::ToPlanes( idPlane planes[6] ) const {
1495         int i;
1496         idVec3 scaled[2];
1497         idVec3 points[4];
1498
1499         planes[0].Normal() = -axis[0];
1500         planes[0].SetDist( -dNear );
1501         planes[1].Normal() = axis[0];
1502         planes[1].SetDist( dFar );
1503
1504         scaled[0] = axis[1] * dLeft;
1505         scaled[1] = axis[2] * dUp;
1506         points[0] = scaled[0] + scaled[1];
1507         points[1] = -scaled[0] + scaled[1];
1508         points[2] = -scaled[0] - scaled[1];
1509         points[3] = scaled[0] - scaled[1];
1510
1511         for ( i = 0; i < 4; i++ ) {
1512                 planes[i+2].Normal() = points[i].Cross( points[(i+1)&3] - points[i] );
1513                 planes[i+2].Normalize();
1514                 planes[i+2].FitThroughPoint( points[i] );
1515         }
1516 }
1517
1518 /*
1519 ============
1520 idFrustum::ToPoints
1521 ============
1522 */
1523 void idFrustum::ToPoints( idVec3 points[8] ) const {
1524         idMat3 scaled;
1525
1526         scaled[0] = origin + axis[0] * dNear;
1527         scaled[1] = axis[1] * ( dLeft * dNear * invFar );
1528         scaled[2] = axis[2] * ( dUp * dNear * invFar );
1529
1530         points[0] = scaled[0] + scaled[1];
1531         points[1] = scaled[0] - scaled[1];
1532         points[2] = points[1] - scaled[2];
1533         points[3] = points[0] - scaled[2];
1534         points[0] += scaled[2];
1535         points[1] += scaled[2];
1536
1537         scaled[0] = origin + axis[0] * dFar;
1538         scaled[1] = axis[1] * dLeft;
1539         scaled[2] = axis[2] * dUp;
1540
1541         points[4] = scaled[0] + scaled[1];
1542         points[5] = scaled[0] - scaled[1];
1543         points[6] = points[5] - scaled[2];
1544         points[7] = points[4] - scaled[2];
1545         points[4] += scaled[2];
1546         points[5] += scaled[2];
1547 }
1548
1549 /*
1550 ============
1551 idFrustum::ToClippedPoints
1552 ============
1553 */
1554 void idFrustum::ToClippedPoints( const float fractions[4], idVec3 points[8] ) const {
1555         idMat3 scaled;
1556
1557         scaled[0] = origin + axis[0] * dNear;
1558         scaled[1] = axis[1] * ( dLeft * dNear * invFar );
1559         scaled[2] = axis[2] * ( dUp * dNear * invFar );
1560
1561         points[0] = scaled[0] + scaled[1];
1562         points[1] = scaled[0] - scaled[1];
1563         points[2] = points[1] - scaled[2];
1564         points[3] = points[0] - scaled[2];
1565         points[0] += scaled[2];
1566         points[1] += scaled[2];
1567
1568         scaled[0] = axis[0] * dFar;
1569         scaled[1] = axis[1] * dLeft;
1570         scaled[2] = axis[2] * dUp;
1571
1572         points[4] = scaled[0] + scaled[1];
1573         points[5] = scaled[0] - scaled[1];
1574         points[6] = points[5] - scaled[2];
1575         points[7] = points[4] - scaled[2];
1576         points[4] += scaled[2];
1577         points[5] += scaled[2];
1578
1579         points[4] = origin + fractions[0] * points[4];
1580         points[5] = origin + fractions[1] * points[5];
1581         points[6] = origin + fractions[2] * points[6];
1582         points[7] = origin + fractions[3] * points[7];
1583 }
1584
1585 /*
1586 ============
1587 idFrustum::ToIndexPoints
1588 ============
1589 */
1590 void idFrustum::ToIndexPoints( idVec3 indexPoints[8] ) const {
1591         idMat3 scaled;
1592
1593         scaled[0] = origin + axis[0] * dNear;
1594         scaled[1] = axis[1] * ( dLeft * dNear * invFar );
1595         scaled[2] = axis[2] * ( dUp * dNear * invFar );
1596
1597         indexPoints[0] = scaled[0] - scaled[1];
1598         indexPoints[2] = scaled[0] + scaled[1];
1599         indexPoints[1] = indexPoints[0] + scaled[2];
1600         indexPoints[3] = indexPoints[2] + scaled[2];
1601         indexPoints[0] -= scaled[2];
1602         indexPoints[2] -= scaled[2];
1603
1604         scaled[0] = origin + axis[0] * dFar;
1605         scaled[1] = axis[1] * dLeft;
1606         scaled[2] = axis[2] * dUp;
1607
1608         indexPoints[4] = scaled[0] - scaled[1];
1609         indexPoints[6] = scaled[0] + scaled[1];
1610         indexPoints[5] = indexPoints[4] + scaled[2];
1611         indexPoints[7] = indexPoints[6] + scaled[2];
1612         indexPoints[4] -= scaled[2];
1613         indexPoints[6] -= scaled[2];
1614 }
1615
1616 /*
1617 ============
1618 idFrustum::ToIndexPointsAndCornerVecs
1619
1620   22 muls
1621 ============
1622 */
1623 void idFrustum::ToIndexPointsAndCornerVecs( idVec3 indexPoints[8], idVec3 cornerVecs[4] ) const {
1624         idMat3 scaled;
1625
1626         scaled[0] = origin + axis[0] * dNear;
1627         scaled[1] = axis[1] * ( dLeft * dNear * invFar );
1628         scaled[2] = axis[2] * ( dUp * dNear * invFar );
1629
1630         indexPoints[0] = scaled[0] - scaled[1];
1631         indexPoints[2] = scaled[0] + scaled[1];
1632         indexPoints[1] = indexPoints[0] + scaled[2];
1633         indexPoints[3] = indexPoints[2] + scaled[2];
1634         indexPoints[0] -= scaled[2];
1635         indexPoints[2] -= scaled[2];
1636
1637         scaled[0] = axis[0] * dFar;
1638         scaled[1] = axis[1] * dLeft;
1639         scaled[2] = axis[2] * dUp;
1640
1641         cornerVecs[0] = scaled[0] - scaled[1];
1642         cornerVecs[2] = scaled[0] + scaled[1];
1643         cornerVecs[1] = cornerVecs[0] + scaled[2];
1644         cornerVecs[3] = cornerVecs[2] + scaled[2];
1645         cornerVecs[0] -= scaled[2];
1646         cornerVecs[2] -= scaled[2];
1647
1648         indexPoints[4] = cornerVecs[0] + origin;
1649         indexPoints[5] = cornerVecs[1] + origin;
1650         indexPoints[6] = cornerVecs[2] + origin;
1651         indexPoints[7] = cornerVecs[3] + origin;
1652 }
1653
1654 /*
1655 ============
1656 idFrustum::AxisProjection
1657
1658   18 muls
1659 ============
1660 */
1661 void idFrustum::AxisProjection( const idVec3 indexPoints[8], const idVec3 cornerVecs[4], const idVec3 &dir, float &min, float &max ) const {
1662         float dx, dy, dz;
1663         int index;
1664
1665         dy = dir.x * axis[1].x + dir.y * axis[1].y + dir.z * axis[1].z;
1666         dz = dir.x * axis[2].x + dir.y * axis[2].y + dir.z * axis[2].z;
1667         index = ( FLOATSIGNBITSET( dy ) << 1 ) | FLOATSIGNBITSET( dz );
1668         dx = dir.x * cornerVecs[index].x + dir.y * cornerVecs[index].y + dir.z * cornerVecs[index].z;
1669         index |= ( FLOATSIGNBITSET( dx ) << 2 );
1670         min = indexPoints[index] * dir;
1671         index = ~index & 3;
1672         dx = -dir.x * cornerVecs[index].x - dir.y * cornerVecs[index].y - dir.z * cornerVecs[index].z;
1673         index |= ( FLOATSIGNBITSET( dx ) << 2 );
1674         max = indexPoints[index] * dir;
1675 }
1676
1677 /*
1678 ============
1679 idFrustum::AxisProjection
1680
1681   40 muls
1682 ============
1683 */
1684 void idFrustum::AxisProjection( const idVec3 &dir, float &min, float &max ) const {
1685         idVec3 indexPoints[8], cornerVecs[4];
1686
1687         ToIndexPointsAndCornerVecs( indexPoints, cornerVecs );
1688         AxisProjection( indexPoints, cornerVecs, dir, min, max );
1689 }
1690
1691 /*
1692 ============
1693 idFrustum::AxisProjection
1694
1695   76 muls
1696 ============
1697 */
1698 void idFrustum::AxisProjection( const idMat3 &ax, idBounds &bounds ) const {
1699         idVec3 indexPoints[8], cornerVecs[4];
1700
1701         ToIndexPointsAndCornerVecs( indexPoints, cornerVecs );
1702         AxisProjection( indexPoints, cornerVecs, ax[0], bounds[0][0], bounds[1][0] );
1703         AxisProjection( indexPoints, cornerVecs, ax[1], bounds[0][1], bounds[1][1] );
1704         AxisProjection( indexPoints, cornerVecs, ax[2], bounds[0][2], bounds[1][2] );
1705 }
1706
1707 /*
1708 ============
1709 idFrustum::AddLocalLineToProjectionBoundsSetCull
1710 ============
1711 */
1712 void idFrustum::AddLocalLineToProjectionBoundsSetCull( const idVec3 &start, const idVec3 &end, int &startCull, int &endCull, idBounds &bounds ) const {
1713         idVec3 dir, p;
1714         float d1, d2, fstart, fend, lstart, lend, f;
1715         float leftScale, upScale;
1716         int cull1, cull2;
1717
1718 #ifdef FRUSTUM_DEBUG
1719         static idCVar r_showInteractionScissors( "r_showInteractionScissors", "0", CVAR_RENDERER | CVAR_INTEGER, "", 0, 2, idCmdSystem::ArgCompletion_Integer<0,2> );
1720         if ( r_showInteractionScissors.GetInteger() > 1 ) {
1721                 session->rw->DebugLine( colorGreen, origin + start * axis, origin + end * axis );
1722         }
1723 #endif
1724
1725         leftScale = dLeft * invFar;
1726         upScale = dUp * invFar;
1727         dir = end - start;
1728
1729         fstart = dFar * start.y;
1730         fend = dFar * end.y;
1731         lstart = dLeft * start.x;
1732         lend = dLeft * end.x;
1733
1734         // test left plane
1735         d1 = -fstart + lstart;
1736         d2 = -fend + lend;
1737         cull1 = FLOATSIGNBITSET( d1 );
1738         cull2 = FLOATSIGNBITSET( d2 );
1739         if ( FLOATNOTZERO( d1 ) ) {
1740                 if ( FLOATSIGNBITSET( d1 ) ^ FLOATSIGNBITSET( d2 ) ) {
1741                         f = d1 / ( d1 - d2 );
1742                         p.x = start.x + f * dir.x;
1743                         if ( p.x > 0.0f ) {
1744                                 p.z = start.z + f * dir.z;
1745                                 if ( idMath::Fabs( p.z ) <= p.x * upScale ) {
1746                                         p.y = 1.0f;
1747                                         p.z = p.z * dFar / ( p.x * dUp );
1748                                         bounds.AddPoint( p );
1749                                 }
1750                         }
1751                 }
1752         }
1753
1754         // test right plane
1755         d1 = fstart + lstart;
1756         d2 = fend + lend;
1757         cull1 |= FLOATSIGNBITSET( d1 ) << 1;
1758         cull2 |= FLOATSIGNBITSET( d2 ) << 1;
1759         if ( FLOATNOTZERO( d1 ) ) {
1760                 if ( FLOATSIGNBITSET( d1 ) ^ FLOATSIGNBITSET( d2 ) ) {
1761                         f = d1 / ( d1 - d2 );
1762                         p.x = start.x + f * dir.x;
1763                         if ( p.x > 0.0f ) {
1764                                 p.z = start.z + f * dir.z;
1765                                 if ( idMath::Fabs( p.z  ) <= p.x * upScale ) {
1766                                         p.y = -1.0f;
1767                                         p.z = p.z * dFar / ( p.x * dUp );
1768                                         bounds.AddPoint( p );
1769                                 }
1770                         }
1771                 }
1772         }
1773
1774         fstart = dFar * start.z;
1775         fend = dFar * end.z;
1776         lstart = dUp * start.x;
1777         lend = dUp * end.x;
1778
1779         // test up plane
1780         d1 = -fstart + lstart;
1781         d2 = -fend + lend;
1782         cull1 |= FLOATSIGNBITSET( d1 ) << 2;
1783         cull2 |= FLOATSIGNBITSET( d2 ) << 2;
1784         if ( FLOATNOTZERO( d1 ) ) {
1785                 if ( FLOATSIGNBITSET( d1 ) ^ FLOATSIGNBITSET( d2 ) ) {
1786                         f = d1 / ( d1 - d2 );
1787                         p.x = start.x + f * dir.x;
1788                         if ( p.x > 0.0f ) {
1789                                 p.y = start.y + f * dir.y;
1790                                 if ( idMath::Fabs( p.y ) <= p.x * leftScale ) {
1791                                         p.y = p.y * dFar / ( p.x * dLeft );
1792                                         p.z = 1.0f;
1793                                         bounds.AddPoint( p );
1794                                 }
1795                         }
1796                 }
1797         }
1798
1799         // test down plane
1800         d1 = fstart + lstart;
1801         d2 = fend + lend;
1802         cull1 |= FLOATSIGNBITSET( d1 ) << 3;
1803         cull2 |= FLOATSIGNBITSET( d2 ) << 3;
1804         if ( FLOATNOTZERO( d1 ) ) {
1805                 if ( FLOATSIGNBITSET( d1 ) ^ FLOATSIGNBITSET( d2 ) ) {
1806                         f = d1 / ( d1 - d2 );
1807                         p.x = start.x + f * dir.x;
1808                         if ( p.x > 0.0f ) {
1809                                 p.y = start.y + f * dir.y;
1810                                 if ( idMath::Fabs( p.y ) <= p.x * leftScale ) {
1811                                         p.y = p.y * dFar / ( p.x * dLeft );
1812                                         p.z = -1.0f;
1813                                         bounds.AddPoint( p );
1814                                 }
1815                         }
1816                 }
1817         }
1818
1819         if ( cull1 == 0 && start.x > 0.0f ) {
1820                 // add start point to projection bounds
1821                 p.x = start.x;
1822                 p.y = start.y * dFar / ( start.x * dLeft );
1823                 p.z = start.z * dFar / ( start.x * dUp );
1824                 bounds.AddPoint( p );
1825         }
1826
1827         if ( cull2 == 0 && end.x > 0.0f ) {
1828                 // add end point to projection bounds
1829                 p.x = end.x;
1830                 p.y = end.y * dFar / ( end.x * dLeft );
1831                 p.z = end.z * dFar / ( end.x * dUp );
1832                 bounds.AddPoint( p );
1833         }
1834
1835         if ( start.x < bounds[0].x ) {
1836                 bounds[0].x = start.x < 0.0f ? 0.0f : start.x;
1837         }
1838         if ( end.x < bounds[0].x ) {
1839                 bounds[0].x = end.x < 0.0f ? 0.0f : end.x;
1840         }
1841
1842         startCull = cull1;
1843         endCull = cull2;
1844 }
1845
1846 /*
1847 ============
1848 idFrustum::AddLocalLineToProjectionBoundsUseCull
1849 ============
1850 */
1851 void idFrustum::AddLocalLineToProjectionBoundsUseCull( const idVec3 &start, const idVec3 &end, int startCull, int endCull, idBounds &bounds ) const {
1852         idVec3 dir, p;
1853         float d1, d2, fstart, fend, lstart, lend, f;
1854         float leftScale, upScale;
1855         int clip;
1856
1857         clip = startCull ^ endCull;
1858         if ( !clip ) {
1859                 return;
1860         }
1861
1862 #ifdef FRUSTUM_DEBUG
1863         static idCVar r_showInteractionScissors( "r_showInteractionScissors", "0", CVAR_RENDERER | CVAR_INTEGER, "", 0, 2, idCmdSystem::ArgCompletion_Integer<0,2> );
1864         if ( r_showInteractionScissors.GetInteger() > 1 ) {
1865                 session->rw->DebugLine( colorGreen, origin + start * axis, origin + end * axis );
1866         }
1867 #endif
1868
1869         leftScale = dLeft * invFar;
1870         upScale = dUp * invFar;
1871         dir = end - start;
1872
1873         if ( clip & (1|2) ) {
1874
1875                 fstart = dFar * start.y;
1876                 fend = dFar * end.y;
1877                 lstart = dLeft * start.x;
1878                 lend = dLeft * end.x;
1879
1880                 if ( clip & 1 ) {
1881                         // test left plane
1882                         d1 = -fstart + lstart;
1883                         d2 = -fend + lend;
1884                         if ( FLOATNOTZERO( d1 ) ) {
1885                                 if ( FLOATSIGNBITSET( d1 ) ^ FLOATSIGNBITSET( d2 ) ) {
1886                                         f = d1 / ( d1 - d2 );
1887                                         p.x = start.x + f * dir.x;
1888                                         if ( p.x > 0.0f ) {
1889                                                 p.z = start.z + f * dir.z;
1890                                                 if ( idMath::Fabs( p.z ) <= p.x * upScale ) {
1891                                                         p.y = 1.0f;
1892                                                         p.z = p.z * dFar / ( p.x * dUp );
1893                                                         bounds.AddPoint( p );
1894                                                 }
1895                                         }
1896                                 }
1897                         }
1898                 }
1899
1900                 if ( clip & 2 ) {
1901                         // test right plane
1902                         d1 = fstart + lstart;
1903                         d2 = fend + lend;
1904                         if ( FLOATNOTZERO( d1 ) ) {
1905                                 if ( FLOATSIGNBITSET( d1 ) ^ FLOATSIGNBITSET( d2 ) ) {
1906                                         f = d1 / ( d1 - d2 );
1907                                         p.x = start.x + f * dir.x;
1908                                         if ( p.x > 0.0f ) {
1909                                                 p.z = start.z + f * dir.z;
1910                                                 if ( idMath::Fabs( p.z  ) <= p.x * upScale ) {
1911                                                         p.y = -1.0f;
1912                                                         p.z = p.z * dFar / ( p.x * dUp );
1913                                                         bounds.AddPoint( p );
1914                                                 }
1915                                         }
1916                                 }
1917                         }
1918                 }
1919         }
1920
1921         if ( clip & (4|8) ) {
1922
1923                 fstart = dFar * start.z;
1924                 fend = dFar * end.z;
1925                 lstart = dUp * start.x;
1926                 lend = dUp * end.x;
1927
1928                 if ( clip & 4 ) {
1929                         // test up plane
1930                         d1 = -fstart + lstart;
1931                         d2 = -fend + lend;
1932                         if ( FLOATNOTZERO( d1 ) ) {
1933                                 if ( FLOATSIGNBITSET( d1 ) ^ FLOATSIGNBITSET( d2 ) ) {
1934                                         f = d1 / ( d1 - d2 );
1935                                         p.x = start.x + f * dir.x;
1936                                         if ( p.x > 0.0f ) {
1937                                                 p.y = start.y + f * dir.y;
1938                                                 if ( idMath::Fabs( p.y ) <= p.x * leftScale ) {
1939                                                         p.y = p.y * dFar / ( p.x * dLeft );
1940                                                         p.z = 1.0f;
1941                                                         bounds.AddPoint( p );
1942                                                 }
1943                                         }
1944                                 }
1945                         }
1946                 }
1947
1948                 if ( clip & 8 ) {
1949                         // test down plane
1950                         d1 = fstart + lstart;
1951                         d2 = fend + lend;
1952                         if ( FLOATNOTZERO( d1 ) ) {
1953                                 if ( FLOATSIGNBITSET( d1 ) ^ FLOATSIGNBITSET( d2 ) ) {
1954                                         f = d1 / ( d1 - d2 );
1955                                         p.x = start.x + f * dir.x;
1956                                         if ( p.x > 0.0f ) {
1957                                                 p.y = start.y + f * dir.y;
1958                                                 if ( idMath::Fabs( p.y ) <= p.x * leftScale ) {
1959                                                         p.y = p.y * dFar / ( p.x * dLeft );
1960                                                         p.z = -1.0f;
1961                                                         bounds.AddPoint( p );
1962                                                 }
1963                                         }
1964                                 }
1965                         }
1966                 }
1967         }
1968 }
1969
1970 /*
1971 ============
1972 idFrustum::BoundsRayIntersection
1973
1974   Returns true if the ray starts inside the bounds.
1975   If there was an intersection scale1 <= scale2
1976 ============
1977 */
1978 bool idFrustum::BoundsRayIntersection( const idBounds &bounds, const idVec3 &start, const idVec3 &dir, float &scale1, float &scale2 ) const {
1979         idVec3 end, p;
1980         float d1, d2, f;
1981         int i, startInside = 1;
1982
1983         scale1 = idMath::INFINITY;
1984         scale2 = -idMath::INFINITY;
1985
1986         end = start + dir;
1987
1988         for ( i = 0; i < 2; i++ ) {
1989                 d1 = start.x - bounds[i].x;
1990                 startInside &= FLOATSIGNBITSET( d1 ) ^ i;
1991                 d2 = end.x - bounds[i].x;
1992                 if ( d1 != d2 ) {
1993                         f = d1 / ( d1 - d2 );
1994                         p.y = start.y + f * dir.y;
1995                         if ( bounds[0].y <= p.y && p.y <= bounds[1].y ) {
1996                                 p.z = start.z + f * dir.z;
1997                                 if ( bounds[0].z <= p.z && p.z <= bounds[1].z ) {
1998                                         if ( f < scale1 ) scale1 = f;
1999                                         if ( f > scale2 ) scale2 = f;
2000                                 }
2001                         }
2002                 }
2003
2004                 d1 = start.y - bounds[i].y;
2005                 startInside &= FLOATSIGNBITSET( d1 ) ^ i;
2006                 d2 = end.y - bounds[i].y;
2007                 if ( d1 != d2 ) {
2008                         f = d1 / ( d1 - d2 );
2009                         p.x = start.x + f * dir.x;
2010                         if ( bounds[0].x <= p.x && p.x <= bounds[1].x ) {
2011                                 p.z = start.z + f * dir.z;
2012                                 if ( bounds[0].z <= p.z && p.z <= bounds[1].z ) {
2013                                         if ( f < scale1 ) scale1 = f;
2014                                         if ( f > scale2 ) scale2 = f;
2015                                 }
2016                         }
2017                 }
2018
2019                 d1 = start.z - bounds[i].z;
2020                 startInside &= FLOATSIGNBITSET( d1 ) ^ i;
2021                 d2 = end.z - bounds[i].z;
2022                 if ( d1 != d2 ) {
2023                         f = d1 / ( d1 - d2 );
2024                         p.x = start.x + f * dir.x;
2025                         if ( bounds[0].x <= p.x && p.x <= bounds[1].x ) {
2026                                 p.y = start.y + f * dir.y;
2027                                 if ( bounds[0].y <= p.y && p.y <= bounds[1].y ) {
2028                                         if ( f < scale1 ) scale1 = f;
2029                                         if ( f > scale2 ) scale2 = f;
2030                                 }
2031                         }
2032                 }
2033         }
2034
2035         return ( startInside != 0 );
2036 }
2037
2038 /*
2039 ============
2040 idFrustum::ProjectionBounds
2041 ============
2042 */
2043 bool idFrustum::ProjectionBounds( const idBounds &bounds, idBounds &projectionBounds ) const {
2044         return ProjectionBounds( idBox( bounds, vec3_origin, mat3_identity ), projectionBounds );
2045 }
2046
2047 #ifndef __linux__
2048
2049 /*
2050 ============
2051 idFrustum::ProjectionBounds
2052 ============
2053 */
2054 bool idFrustum::ProjectionBounds( const idBox &box, idBounds &projectionBounds ) const {
2055         int i, p1, p2, pointCull[8], culled, outside;
2056         float scale1, scale2;
2057         idFrustum localFrustum;
2058         idVec3 points[8], localOrigin;
2059         idMat3 localAxis, localScaled;
2060         idBounds bounds( -box.GetExtents(), box.GetExtents() );
2061
2062         // if the frustum origin is inside the bounds
2063         if ( bounds.ContainsPoint( ( origin - box.GetCenter() ) * box.GetAxis().Transpose() ) ) {
2064                 // bounds that cover the whole frustum
2065                 float boxMin, boxMax, base;
2066
2067                 base = origin * axis[0];
2068                 box.AxisProjection( axis[0], boxMin, boxMax );
2069
2070                 projectionBounds[0].x = boxMin - base;
2071                 projectionBounds[1].x = boxMax - base;
2072                 projectionBounds[0].y = projectionBounds[0].z = -1.0f;
2073                 projectionBounds[1].y = projectionBounds[1].z = 1.0f;
2074
2075                 return true;
2076         }
2077
2078         projectionBounds.Clear();
2079
2080         // transform the bounds into the space of this frustum
2081         localOrigin = ( box.GetCenter() - origin ) * axis.Transpose();
2082         localAxis = box.GetAxis() * axis.Transpose();
2083         BoxToPoints( localOrigin, box.GetExtents(), localAxis, points );
2084
2085         // test outer four edges of the bounds
2086         culled = -1;
2087         outside = 0;
2088         for ( i = 0; i < 4; i++ ) {
2089                 p1 = i;
2090                 p2 = 4 + i;
2091                 AddLocalLineToProjectionBoundsSetCull( points[p1], points[p2], pointCull[p1], pointCull[p2], projectionBounds );
2092                 culled &= pointCull[p1] & pointCull[p2];
2093                 outside |= pointCull[p1] | pointCull[p2];
2094         }
2095
2096         // if the bounds are completely outside this frustum
2097         if ( culled ) {
2098                 return false;
2099         }
2100
2101         // if the bounds are completely inside this frustum
2102         if ( !outside ) {
2103                 return true;
2104         }
2105
2106         // test the remaining edges of the bounds
2107         for ( i = 0; i < 4; i++ ) {
2108                 p1 = i;
2109                 p2 = (i+1)&3;
2110                 AddLocalLineToProjectionBoundsUseCull( points[p1], points[p2], pointCull[p1], pointCull[p2], projectionBounds );
2111         }
2112
2113         for ( i = 0; i < 4; i++ ) {
2114                 p1 = 4 + i;
2115                 p2 = 4 + ((i+1)&3);
2116                 AddLocalLineToProjectionBoundsUseCull( points[p1], points[p2], pointCull[p1], pointCull[p2], projectionBounds );
2117         }
2118
2119         // if the bounds extend beyond two or more boundaries of this frustum
2120         if ( outside != 1 && outside != 2 && outside != 4 && outside != 8 ) {
2121
2122                 localOrigin = ( origin - box.GetCenter() ) * box.GetAxis().Transpose();
2123                 localScaled = axis * box.GetAxis().Transpose();
2124                 localScaled[0] *= dFar;
2125                 localScaled[1] *= dLeft;
2126                 localScaled[2] *= dUp;
2127
2128                 // test the outer edges of this frustum for intersection with the bounds
2129                 if ( (outside & 2) && (outside & 8) ) {
2130                         BoundsRayIntersection( bounds, localOrigin, localScaled[0] - localScaled[1] - localScaled[2], scale1, scale2 );
2131                         if ( scale1 <= scale2 && scale1 >= 0.0f ) {
2132                                 projectionBounds.AddPoint( idVec3( scale1 * dFar, -1.0f, -1.0f ) );
2133                                 projectionBounds.AddPoint( idVec3( scale2 * dFar, -1.0f, -1.0f ) );
2134                         }
2135                 }
2136                 if ( (outside & 2) && (outside & 4) ) {
2137                         BoundsRayIntersection( bounds, localOrigin, localScaled[0] - localScaled[1] + localScaled[2], scale1, scale2 );
2138                         if ( scale1 <= scale2 && scale1 >= 0.0f  ) {
2139                                 projectionBounds.AddPoint( idVec3( scale1 * dFar, -1.0f, 1.0f ) );
2140                                 projectionBounds.AddPoint( idVec3( scale2 * dFar, -1.0f, 1.0f ) );
2141                         }
2142                 }
2143                 if ( (outside & 1) && (outside & 8) ) {
2144                         BoundsRayIntersection( bounds, localOrigin, localScaled[0] + localScaled[1] - localScaled[2], scale1, scale2 );
2145                         if ( scale1 <= scale2 && scale1 >= 0.0f  ) {
2146                                 projectionBounds.AddPoint( idVec3( scale1 * dFar, 1.0f, -1.0f ) );
2147                                 projectionBounds.AddPoint( idVec3( scale2 * dFar, 1.0f, -1.0f ) );
2148                         }
2149                 }
2150                 if ( (outside & 1) && (outside & 2) ) {
2151                         BoundsRayIntersection( bounds, localOrigin, localScaled[0] + localScaled[1] + localScaled[2], scale1, scale2 );
2152                         if ( scale1 <= scale2 && scale1 >= 0.0f  ) {
2153                                 projectionBounds.AddPoint( idVec3( scale1 * dFar, 1.0f, 1.0f ) );
2154                                 projectionBounds.AddPoint( idVec3( scale2 * dFar, 1.0f, 1.0f ) );
2155                         }
2156                 }
2157         }
2158
2159         return true;
2160 }
2161
2162 #endif
2163
2164 /*
2165 ============
2166 idFrustum::ProjectionBounds
2167 ============
2168 */
2169 bool idFrustum::ProjectionBounds( const idSphere &sphere, idBounds &projectionBounds ) const {
2170         float d, r, rs, sFar;
2171         idVec3 center;
2172
2173         projectionBounds.Clear();
2174
2175         center = ( sphere.GetOrigin() - origin ) * axis.Transpose();
2176         r = sphere.GetRadius();
2177         rs = r * r;
2178         sFar = dFar * dFar;
2179
2180         // test left/right planes
2181         d = dFar * idMath::Fabs( center.y ) - dLeft * center.x;
2182         if ( ( d * d ) > rs * ( sFar + dLeft * dLeft ) ) {
2183                 return false;
2184         }
2185
2186         // test up/down planes
2187         d = dFar * idMath::Fabs( center.z ) - dUp * center.x;
2188         if ( ( d * d ) > rs * ( sFar + dUp * dUp ) ) {
2189                 return false;
2190         }
2191
2192         // bounds that cover the whole frustum
2193         projectionBounds[0].x = 0.0f;
2194         projectionBounds[1].x = dFar;
2195         projectionBounds[0].y = projectionBounds[0].z = -1.0f;
2196         projectionBounds[1].y = projectionBounds[1].z = 1.0f;
2197         return true;
2198 }
2199
2200 /*
2201 ============
2202 idFrustum::ProjectionBounds
2203 ============
2204 */
2205 bool idFrustum::ProjectionBounds( const idFrustum &frustum, idBounds &projectionBounds ) const {
2206         int i, p1, p2, pointCull[8], culled, outside;
2207         float scale1, scale2;
2208         idFrustum localFrustum;
2209         idVec3 points[8], localOrigin;
2210         idMat3 localScaled;
2211
2212         // if the frustum origin is inside the other frustum
2213         if ( frustum.ContainsPoint( origin ) ) {
2214                 // bounds that cover the whole frustum
2215                 float frustumMin, frustumMax, base;
2216
2217                 base = origin * axis[0];
2218                 frustum.AxisProjection( axis[0], frustumMin, frustumMax );
2219
2220                 projectionBounds[0].x = frustumMin - base;
2221                 projectionBounds[1].x = frustumMax - base;
2222                 projectionBounds[0].y = projectionBounds[0].z = -1.0f;
2223                 projectionBounds[1].y = projectionBounds[1].z = 1.0f;
2224                 return true;
2225         }
2226
2227         projectionBounds.Clear();
2228
2229         // transform the given frustum into the space of this frustum
2230         localFrustum = frustum;
2231         localFrustum.origin = ( frustum.origin - origin ) * axis.Transpose();
2232         localFrustum.axis = frustum.axis * axis.Transpose();
2233         localFrustum.ToPoints( points );
2234
2235         // test outer four edges of the other frustum
2236         culled = -1;
2237         outside = 0;
2238         for ( i = 0; i < 4; i++ ) {
2239                 p1 = i;
2240                 p2 = 4 + i;
2241                 AddLocalLineToProjectionBoundsSetCull( points[p1], points[p2], pointCull[p1], pointCull[p2], projectionBounds );
2242                 culled &= pointCull[p1] & pointCull[p2];
2243                 outside |= pointCull[p1] | pointCull[p2];
2244         }
2245
2246         // if the other frustum is completely outside this frustum
2247         if ( culled ) {
2248                 return false;
2249         }
2250
2251         // if the other frustum is completely inside this frustum
2252         if ( !outside ) {
2253                 return true;
2254         }
2255
2256         // test the remaining edges of the other frustum
2257         if ( localFrustum.dNear > 0.0f ) {
2258                 for ( i = 0; i < 4; i++ ) {
2259                         p1 = i;
2260                         p2 = (i+1)&3;
2261                         AddLocalLineToProjectionBoundsUseCull( points[p1], points[p2], pointCull[p1], pointCull[p2], projectionBounds );
2262                 }
2263         }
2264
2265         for ( i = 0; i < 4; i++ ) {
2266                 p1 = 4 + i;
2267                 p2 = 4 + ((i+1)&3);
2268                 AddLocalLineToProjectionBoundsUseCull( points[p1], points[p2], pointCull[p1], pointCull[p2], projectionBounds );
2269         }
2270
2271         // if the other frustum extends beyond two or more boundaries of this frustum
2272         if ( outside != 1 && outside != 2 && outside != 4 && outside != 8 ) {
2273
2274                 localOrigin = ( origin - frustum.origin ) * frustum.axis.Transpose();
2275                 localScaled = axis * frustum.axis.Transpose();
2276                 localScaled[0] *= dFar;
2277                 localScaled[1] *= dLeft;
2278                 localScaled[2] *= dUp;
2279
2280                 // test the outer edges of this frustum for intersection with the other frustum
2281                 if ( (outside & 2) && (outside & 8) ) {
2282                         frustum.LocalRayIntersection( localOrigin, localScaled[0] - localScaled[1] - localScaled[2], scale1, scale2 );
2283                         if ( scale1 <= scale2 && scale1 >= 0.0f ) {
2284                                 projectionBounds.AddPoint( idVec3( scale1 * dFar, -1.0f, -1.0f ) );
2285                                 projectionBounds.AddPoint( idVec3( scale2 * dFar, -1.0f, -1.0f ) );
2286                         }
2287                 }
2288                 if ( (outside & 2) && (outside & 4) ) {
2289                         frustum.LocalRayIntersection( localOrigin, localScaled[0] - localScaled[1] + localScaled[2], scale1, scale2 );
2290                         if ( scale1 <= scale2 && scale1 >= 0.0f  ) {
2291                                 projectionBounds.AddPoint( idVec3( scale1 * dFar, -1.0f, 1.0f ) );
2292                                 projectionBounds.AddPoint( idVec3( scale2 * dFar, -1.0f, 1.0f ) );
2293                         }
2294                 }
2295                 if ( (outside & 1) && (outside & 8) ) {
2296                         frustum.LocalRayIntersection( localOrigin, localScaled[0] + localScaled[1] - localScaled[2], scale1, scale2 );
2297                         if ( scale1 <= scale2 && scale1 >= 0.0f  ) {
2298                                 projectionBounds.AddPoint( idVec3( scale1 * dFar, 1.0f, -1.0f ) );
2299                                 projectionBounds.AddPoint( idVec3( scale2 * dFar, 1.0f, -1.0f ) );
2300                         }
2301                 }
2302                 if ( (outside & 1) && (outside & 2) ) {
2303                         frustum.LocalRayIntersection( localOrigin, localScaled[0] + localScaled[1] + localScaled[2], scale1, scale2 );
2304                         if ( scale1 <= scale2 && scale1 >= 0.0f  ) {
2305                                 projectionBounds.AddPoint( idVec3( scale1 * dFar, 1.0f, 1.0f ) );
2306                                 projectionBounds.AddPoint( idVec3( scale2 * dFar, 1.0f, 1.0f ) );
2307                         }
2308                 }
2309         }
2310
2311         return true;
2312 }
2313
2314 /*
2315 ============
2316 idFrustum::ProjectionBounds
2317 ============
2318 */
2319 bool idFrustum::ProjectionBounds( const idWinding &winding, idBounds &projectionBounds ) const {
2320         int i, p1, p2, *pointCull, culled, outside;
2321         float scale;
2322         idVec3 *localPoints;
2323         idMat3 transpose, scaled;
2324         idPlane plane;
2325
2326         projectionBounds.Clear();
2327
2328         // transform the winding points into the space of this frustum
2329         localPoints = (idVec3 *) _alloca16( winding.GetNumPoints() * sizeof( idVec3 ) );
2330         transpose = axis.Transpose();
2331         for ( i = 0; i < winding.GetNumPoints(); i++ ) {
2332                 localPoints[i] = ( winding[i].ToVec3() - origin ) * transpose;
2333         }
2334
2335         // test the winding edges
2336         culled = -1;
2337         outside = 0;
2338         pointCull = (int *) _alloca16( winding.GetNumPoints() * sizeof( int ) );
2339         for ( i = 0; i < winding.GetNumPoints(); i += 2 ) {
2340                 p1 = i;
2341                 p2 = (i+1)%winding.GetNumPoints();
2342                 AddLocalLineToProjectionBoundsSetCull( localPoints[p1], localPoints[p2], pointCull[p1], pointCull[p2], projectionBounds );
2343                 culled &= pointCull[p1] & pointCull[p2];
2344                 outside |= pointCull[p1] | pointCull[p2];
2345         }
2346
2347         // if completely culled
2348         if ( culled ) {
2349                 return false;
2350         }
2351
2352         // if completely inside
2353         if ( !outside ) {
2354                 return true;
2355         }
2356
2357         // test remaining winding edges
2358         for ( i = 1; i < winding.GetNumPoints(); i += 2 ) {
2359                 p1 = i;
2360                 p2 = (i+1)%winding.GetNumPoints();
2361                 AddLocalLineToProjectionBoundsUseCull( localPoints[p1], localPoints[p2], pointCull[p1], pointCull[p2], projectionBounds );
2362         }
2363
2364         // if the winding extends beyond two or more boundaries of this frustum
2365         if ( outside != 1 && outside != 2 && outside != 4 && outside != 8 ) {
2366
2367                 winding.GetPlane( plane );
2368                 scaled[0] = axis[0] * dFar;
2369                 scaled[1] = axis[1] * dLeft;
2370                 scaled[2] = axis[2] * dUp;
2371
2372                 // test the outer edges of this frustum for intersection with the winding
2373                 if ( (outside & 2) && (outside & 8) ) {
2374                         if ( winding.RayIntersection( plane, origin, scaled[0] - scaled[1] - scaled[2], scale ) ) {
2375                                 projectionBounds.AddPoint( idVec3( scale * dFar, -1.0f, -1.0f ) );
2376                         }
2377                 }
2378                 if ( (outside & 2) && (outside & 4) ) {
2379                         if ( winding.RayIntersection( plane, origin, scaled[0] - scaled[1] + scaled[2], scale ) ) {
2380                                 projectionBounds.AddPoint( idVec3( scale * dFar, -1.0f, 1.0f ) );
2381                         }
2382                 }
2383                 if ( (outside & 1) && (outside & 8) ) {
2384                         if ( winding.RayIntersection( plane, origin, scaled[0] + scaled[1] - scaled[2], scale ) ) {
2385                                 projectionBounds.AddPoint( idVec3( scale * dFar, 1.0f, -1.0f ) );
2386                         }
2387                 }
2388                 if ( (outside & 1) && (outside & 2) ) {
2389                         if ( winding.RayIntersection( plane, origin, scaled[0] + scaled[1] + scaled[2], scale ) ) {
2390                                 projectionBounds.AddPoint( idVec3( scale * dFar, 1.0f, 1.0f ) );
2391                         }
2392                 }
2393         }
2394
2395         return true;
2396 }
2397
2398 /*
2399 ============
2400 idFrustum::ClipFrustumToBox
2401
2402   Clips the frustum far extents to the box.
2403 ============
2404 */
2405 void idFrustum::ClipFrustumToBox( const idBox &box, float clipFractions[4], int clipPlanes[4] ) const {
2406         int i, index;
2407         float f, minf;
2408         idMat3 scaled, localAxis, transpose;
2409         idVec3 localOrigin, cornerVecs[4];
2410         idBounds bounds;
2411
2412         transpose = box.GetAxis();
2413         transpose.TransposeSelf();
2414         localOrigin = ( origin - box.GetCenter() ) * transpose;
2415         localAxis = axis * transpose;
2416
2417         scaled[0] = localAxis[0] * dFar;
2418         scaled[1] = localAxis[1] * dLeft;
2419         scaled[2] = localAxis[2] * dUp;
2420         cornerVecs[0] = scaled[0] + scaled[1];
2421         cornerVecs[1] = scaled[0] - scaled[1];
2422         cornerVecs[2] = cornerVecs[1] - scaled[2];
2423         cornerVecs[3] = cornerVecs[0] - scaled[2];
2424         cornerVecs[0] += scaled[2];
2425         cornerVecs[1] += scaled[2];
2426
2427         bounds[0] = -box.GetExtents();
2428         bounds[1] = box.GetExtents();
2429
2430         minf = ( dNear + 1.0f ) * invFar;
2431
2432         for ( i = 0; i < 4; i++ ) {
2433
2434                 index = FLOATSIGNBITNOTSET( cornerVecs[i].x );
2435                 f = ( bounds[index].x - localOrigin.x ) / cornerVecs[i].x;
2436                 clipFractions[i] = f;
2437                 clipPlanes[i] = 1 << index;
2438
2439                 index = FLOATSIGNBITNOTSET( cornerVecs[i].y );
2440                 f = ( bounds[index].y - localOrigin.y ) / cornerVecs[i].y;
2441                 if ( f < clipFractions[i] ) {
2442                         clipFractions[i] = f;
2443                         clipPlanes[i] = 4 << index;
2444                 }
2445
2446                 index = FLOATSIGNBITNOTSET( cornerVecs[i].z );
2447                 f = ( bounds[index].z - localOrigin.z ) / cornerVecs[i].z;
2448                 if ( f < clipFractions[i] ) {
2449                         clipFractions[i] = f;
2450                         clipPlanes[i] = 16 << index;
2451                 }
2452
2453                 // make sure the frustum is not clipped between the frustum origin and the near plane
2454                 if ( clipFractions[i] < minf ) {
2455                         clipFractions[i] = minf;
2456                 }
2457         }
2458 }
2459
2460 /*
2461 ============
2462 idFrustum::ClipLine
2463
2464   Returns true if part of the line is inside the frustum.
2465   Does not clip to the near and far plane.
2466 ============
2467 */
2468 bool idFrustum::ClipLine( const idVec3 localPoints[8], const idVec3 points[8], int startIndex, int endIndex, idVec3 &start, idVec3 &end, int &startClip, int &endClip ) const {
2469         float d1, d2, fstart, fend, lstart, lend, f, x;
2470         float leftScale, upScale;
2471         float scale1, scale2;
2472         int startCull, endCull;
2473         idVec3 localStart, localEnd, localDir;
2474
2475         leftScale = dLeft * invFar;
2476         upScale = dUp * invFar;
2477
2478         localStart = localPoints[startIndex];
2479         localEnd = localPoints[endIndex];
2480         localDir = localEnd - localStart;
2481
2482         startClip = endClip = -1;
2483         scale1 = idMath::INFINITY;
2484         scale2 = -idMath::INFINITY;
2485
2486         fstart = dFar * localStart.y;
2487         fend = dFar * localEnd.y;
2488         lstart = dLeft * localStart.x;
2489         lend = dLeft * localEnd.x;
2490
2491         // test left plane
2492         d1 = -fstart + lstart;
2493         d2 = -fend + lend;
2494         startCull = FLOATSIGNBITSET( d1 );
2495         endCull = FLOATSIGNBITSET( d2 );
2496         if ( FLOATNOTZERO( d1 ) ) {
2497                 if ( FLOATSIGNBITSET( d1 ) ^ FLOATSIGNBITSET( d2 ) ) {
2498                         f = d1 / ( d1 - d2 );
2499                         x = localStart.x + f * localDir.x;
2500                         if ( x >= 0.0f ) {
2501                                 if ( idMath::Fabs( localStart.z + f * localDir.z ) <= x * upScale ) {
2502                                         if ( f < scale1 ) { scale1 = f; startClip = 0; }
2503                                         if ( f > scale2 ) { scale2 = f; endClip = 0; }
2504                                 }
2505                         }
2506                 }
2507         }
2508
2509         // test right plane
2510         d1 = fstart + lstart;
2511         d2 = fend + lend;
2512         startCull |= FLOATSIGNBITSET( d1 ) << 1;
2513         endCull |= FLOATSIGNBITSET( d2 ) << 1;
2514         if ( FLOATNOTZERO( d1 ) ) {
2515                 if ( FLOATSIGNBITSET( d1 ) ^ FLOATSIGNBITSET( d2 ) ) {
2516                         f = d1 / ( d1 - d2 );
2517                         x = localStart.x + f * localDir.x;
2518                         if ( x >= 0.0f ) {
2519                                 if ( idMath::Fabs( localStart.z + f * localDir.z ) <= x * upScale ) {
2520                                         if ( f < scale1 ) { scale1 = f; startClip = 1; }
2521                                         if ( f > scale2 ) { scale2 = f; endClip = 1; }
2522                                 }
2523                         }
2524                 }
2525         }
2526
2527         fstart = dFar * localStart.z;
2528         fend = dFar * localEnd.z;
2529         lstart = dUp * localStart.x;
2530         lend = dUp * localEnd.x;
2531
2532         // test up plane
2533         d1 = -fstart + lstart;
2534         d2 = -fend + lend;
2535         startCull |= FLOATSIGNBITSET( d1 ) << 2;
2536         endCull |= FLOATSIGNBITSET( d2 ) << 2;
2537         if ( FLOATNOTZERO( d1 ) ) {
2538                 if ( FLOATSIGNBITSET( d1 ) ^ FLOATSIGNBITSET( d2 ) ) {
2539                         f = d1 / ( d1 - d2 );
2540                         x = localStart.x + f * localDir.x;
2541                         if ( x >= 0.0f ) {
2542                                 if ( idMath::Fabs( localStart.y + f * localDir.y ) <= x * leftScale ) {
2543                                         if ( f < scale1 ) { scale1 = f; startClip = 2; }
2544                                         if ( f > scale2 ) { scale2 = f; endClip = 2; }
2545                                 }
2546                         }
2547                 }
2548         }
2549
2550         // test down plane
2551         d1 = fstart + lstart;
2552         d2 = fend + lend;
2553         startCull |= FLOATSIGNBITSET( d1 ) << 3;
2554         endCull |= FLOATSIGNBITSET( d2 ) << 3;
2555         if ( FLOATNOTZERO( d1 ) ) {
2556                 if ( FLOATSIGNBITSET( d1 ) ^ FLOATSIGNBITSET( d2 ) ) {
2557                         f = d1 / ( d1 - d2 );
2558                         x = localStart.x + f * localDir.x;
2559                         if ( x >= 0.0f ) {
2560                                 if ( idMath::Fabs( localStart.y + f * localDir.y ) <= x * leftScale ) {
2561                                         if ( f < scale1 ) { scale1 = f; startClip = 3; }
2562                                         if ( f > scale2 ) { scale2 = f; endClip = 3; }
2563                                 }
2564                         }
2565                 }
2566         }
2567
2568         // if completely inside
2569         if ( !( startCull | endCull ) ) {
2570                 start = points[startIndex];
2571                 end = points[endIndex];
2572                 return true;
2573         }
2574         else if ( scale1 <= scale2 ) {
2575                 if ( !startCull ) {
2576                         start = points[startIndex];
2577                         startClip = -1;
2578                 }
2579                 else {
2580                         start = points[startIndex] + scale1 * ( points[endIndex] - points[startIndex] );
2581                 }
2582                 if ( !endCull ) {
2583                         end = points[endIndex];
2584                         endClip = -1;
2585                 }
2586                 else {
2587                         end = points[startIndex] + scale2 * ( points[endIndex] - points[startIndex] );
2588                 }
2589                 return true;
2590         }
2591         return false;
2592 }
2593
2594 /*
2595 ============
2596 idFrustum::AddLocalCapsToProjectionBounds
2597 ============
2598 */
2599 static int capPointIndex[4][2] = {
2600         { 0, 3 },
2601         { 1, 2 },
2602         { 0, 1 },
2603         { 2, 3 }
2604 };
2605
2606 ID_INLINE bool idFrustum::AddLocalCapsToProjectionBounds( const idVec3 endPoints[4], const int endPointCull[4], const idVec3 &point, int pointCull, int pointClip, idBounds &projectionBounds ) const {
2607         int *p;
2608
2609         if ( pointClip < 0 ) {
2610                 return false;
2611         }
2612         p = capPointIndex[pointClip];
2613         AddLocalLineToProjectionBoundsUseCull( endPoints[p[0]], point, endPointCull[p[0]], pointCull, projectionBounds );
2614         AddLocalLineToProjectionBoundsUseCull( endPoints[p[1]], point, endPointCull[p[1]], pointCull, projectionBounds );
2615         return true;
2616 }
2617
2618 /*
2619 ============
2620 idFrustum::ClippedProjectionBounds
2621 ============
2622 */
2623 bool idFrustum::ClippedProjectionBounds( const idFrustum &frustum, const idBox &clipBox, idBounds &projectionBounds ) const {
2624         int i, p1, p2, clipPointCull[8], clipPlanes[4], usedClipPlanes, nearCull, farCull, outside;
2625         int pointCull[2], startClip, endClip, boxPointCull[8];
2626         float clipFractions[4], s1, s2, t1, t2, leftScale, upScale;
2627         idFrustum localFrustum;
2628         idVec3 clipPoints[8], localPoints1[8], localPoints2[8], localOrigin1, localOrigin2, start, end;
2629         idMat3 localAxis1, localAxis2, transpose;
2630         idBounds clipBounds;
2631
2632         // if the frustum origin is inside the other frustum
2633         if ( frustum.ContainsPoint( origin ) ) {
2634                 // bounds that cover the whole frustum
2635                 float clipBoxMin, clipBoxMax, frustumMin, frustumMax, base;
2636
2637                 base = origin * axis[0];
2638                 clipBox.AxisProjection( axis[0], clipBoxMin, clipBoxMax );
2639                 frustum.AxisProjection( axis[0], frustumMin, frustumMax );
2640
2641                 projectionBounds[0].x = Max( clipBoxMin, frustumMin ) - base;
2642                 projectionBounds[1].x = Min( clipBoxMax, frustumMax ) - base;
2643                 projectionBounds[0].y = projectionBounds[0].z = -1.0f;
2644                 projectionBounds[1].y = projectionBounds[1].z = 1.0f;
2645                 return true;
2646         }
2647
2648         projectionBounds.Clear();
2649
2650         // clip the outer edges of the given frustum to the clip bounds
2651         frustum.ClipFrustumToBox( clipBox, clipFractions, clipPlanes );
2652         usedClipPlanes = clipPlanes[0] | clipPlanes[1] | clipPlanes[2] | clipPlanes[3];
2653
2654         // transform the clipped frustum to the space of this frustum
2655         transpose = axis;
2656         transpose.TransposeSelf();
2657         localFrustum = frustum;
2658         localFrustum.origin = ( frustum.origin - origin ) * transpose;
2659         localFrustum.axis = frustum.axis * transpose;
2660         localFrustum.ToClippedPoints( clipFractions, clipPoints );
2661
2662         // test outer four edges of the clipped frustum
2663         for ( i = 0; i < 4; i++ ) {
2664                 p1 = i;
2665                 p2 = 4 + i;
2666                 AddLocalLineToProjectionBoundsSetCull( clipPoints[p1], clipPoints[p2], clipPointCull[p1], clipPointCull[p2], projectionBounds );
2667         }
2668
2669         // get cull bits for the clipped frustum
2670         outside = clipPointCull[0] | clipPointCull[1] | clipPointCull[2] | clipPointCull[3] |
2671                                         clipPointCull[4] | clipPointCull[5] | clipPointCull[6] | clipPointCull[7];
2672         nearCull = clipPointCull[0] & clipPointCull[1] & clipPointCull[2] & clipPointCull[3];
2673         farCull = clipPointCull[4] & clipPointCull[5] & clipPointCull[6] & clipPointCull[7];
2674
2675         // if the clipped frustum is not completely inside this frustum
2676         if ( outside ) {
2677
2678                 // test the remaining edges of the clipped frustum
2679                 if ( !nearCull && localFrustum.dNear > 0.0f ) {
2680                         for ( i = 0; i < 4; i++ ) {
2681                                 p1 = i;
2682                                 p2 = (i+1)&3;
2683                                 AddLocalLineToProjectionBoundsUseCull( clipPoints[p1], clipPoints[p2], clipPointCull[p1], clipPointCull[p2], projectionBounds );
2684                         }
2685                 }
2686
2687                 if ( !farCull ) {
2688                         for ( i = 0; i < 4; i++ ) {
2689                                 p1 = 4 + i;
2690                                 p2 = 4 + ((i+1)&3);
2691                                 AddLocalLineToProjectionBoundsUseCull( clipPoints[p1], clipPoints[p2], clipPointCull[p1], clipPointCull[p2], projectionBounds );
2692                         }
2693                 }
2694         }
2695
2696         // if the clipped frustum far end points are inside this frustum
2697         if ( !( farCull && !( nearCull & farCull ) ) &&
2698                         // if the clipped frustum is not clipped to a single plane of the clip bounds
2699                         ( clipPlanes[0] != clipPlanes[1] || clipPlanes[1] != clipPlanes[2] || clipPlanes[2] != clipPlanes[3] ) ) {
2700
2701                 // transform the clip box into the space of the other frustum
2702                 transpose = frustum.axis;
2703                 transpose.TransposeSelf();
2704                 localOrigin1 = ( clipBox.GetCenter() - frustum.origin ) * transpose;
2705                 localAxis1 = clipBox.GetAxis() * transpose;
2706                 BoxToPoints( localOrigin1, clipBox.GetExtents(), localAxis1, localPoints1 );
2707
2708                 // cull the box corners with the other frustum
2709                 leftScale = frustum.dLeft * frustum.invFar;
2710                 upScale = frustum.dUp * frustum.invFar;
2711                 for ( i = 0; i < 8; i++ ) {
2712                         idVec3 &p = localPoints1[i];
2713                         if ( !( boxVertPlanes[i] & usedClipPlanes ) || p.x <= 0.0f ) {
2714                                 boxPointCull[i] = 1|2|4|8;
2715                         }
2716                         else {
2717                                 boxPointCull[i] = 0;
2718                                 if ( idMath::Fabs( p.y ) > p.x * leftScale ) {
2719                                         boxPointCull[i] |= 1 << FLOATSIGNBITSET( p.y );
2720                                 }
2721                                 if ( idMath::Fabs( p.z ) > p.x * upScale ) {
2722                                         boxPointCull[i] |= 4 << FLOATSIGNBITSET( p.z );
2723                                 }
2724                         }
2725                 }
2726
2727                 // transform the clip box into the space of this frustum
2728                 transpose = axis;
2729                 transpose.TransposeSelf();
2730                 localOrigin2 = ( clipBox.GetCenter() - origin ) * transpose;
2731                 localAxis2 = clipBox.GetAxis() * transpose;
2732                 BoxToPoints( localOrigin2, clipBox.GetExtents(), localAxis2, localPoints2 );
2733
2734                 // clip the edges of the clip bounds to the other frustum and add the clipped edges to the projection bounds
2735                 for ( i = 0; i < 4; i++ ) {
2736                         p1 = i;
2737                         p2 = 4 + i;
2738                         if ( !( boxPointCull[p1] & boxPointCull[p2] ) ) {
2739                                 if ( frustum.ClipLine( localPoints1, localPoints2, p1, p2, start, end, startClip, endClip ) ) {
2740                                         AddLocalLineToProjectionBoundsSetCull( start, end, pointCull[0], pointCull[1], projectionBounds );
2741                                         AddLocalCapsToProjectionBounds( clipPoints+4, clipPointCull+4, start, pointCull[0], startClip, projectionBounds );
2742                                         AddLocalCapsToProjectionBounds( clipPoints+4, clipPointCull+4, end, pointCull[1], endClip, projectionBounds );
2743                                         outside |= pointCull[0] | pointCull[1];
2744                                 }
2745                         }
2746                 }
2747
2748                 for ( i = 0; i < 4; i++ ) {
2749                         p1 = i;
2750                         p2 = (i+1)&3;
2751                         if ( !( boxPointCull[p1] & boxPointCull[p2] ) ) {
2752                                 if ( frustum.ClipLine( localPoints1, localPoints2, p1, p2, start, end, startClip, endClip ) ) {
2753                                         AddLocalLineToProjectionBoundsSetCull( start, end, pointCull[0], pointCull[1], projectionBounds );
2754                                         AddLocalCapsToProjectionBounds( clipPoints+4, clipPointCull+4, start, pointCull[0], startClip, projectionBounds );
2755                                         AddLocalCapsToProjectionBounds( clipPoints+4, clipPointCull+4, end, pointCull[1], endClip, projectionBounds );
2756                                         outside |= pointCull[0] | pointCull[1];
2757                                 }
2758                         }
2759                 }
2760
2761                 for ( i = 0; i < 4; i++ ) {
2762                         p1 = 4 + i;
2763                         p2 = 4 + ((i+1)&3);
2764                         if ( !( boxPointCull[p1] & boxPointCull[p2] ) ) {
2765                                 if ( frustum.ClipLine( localPoints1, localPoints2, p1, p2, start, end, startClip, endClip ) ) {
2766                                         AddLocalLineToProjectionBoundsSetCull( start, end, pointCull[0], pointCull[1], projectionBounds );
2767                                         AddLocalCapsToProjectionBounds( clipPoints+4, clipPointCull+4, start, pointCull[0], startClip, projectionBounds );
2768                                         AddLocalCapsToProjectionBounds( clipPoints+4, clipPointCull+4, end, pointCull[1], endClip, projectionBounds );
2769                                         outside |= pointCull[0] | pointCull[1];
2770                                 }
2771                         }
2772                 }
2773         }
2774
2775         // if the clipped frustum extends beyond two or more boundaries of this frustum
2776         if ( outside != 1 && outside != 2 && outside != 4 && outside != 8 ) {
2777
2778                 // transform this frustum into the space of the other frustum
2779                 transpose = frustum.axis;
2780                 transpose.TransposeSelf();
2781                 localOrigin1 = ( origin - frustum.origin ) * transpose;
2782                 localAxis1 = axis * transpose;
2783                 localAxis1[0] *= dFar;
2784                 localAxis1[1] *= dLeft;
2785                 localAxis1[2] *= dUp;
2786
2787                 // transform this frustum into the space of the clip bounds
2788                 transpose = clipBox.GetAxis();
2789                 transpose.TransposeSelf();
2790                 localOrigin2 = ( origin - clipBox.GetCenter() ) * transpose;
2791                 localAxis2 = axis * transpose;
2792                 localAxis2[0] *= dFar;
2793                 localAxis2[1] *= dLeft;
2794                 localAxis2[2] *= dUp;
2795
2796                 clipBounds[0] = -clipBox.GetExtents();
2797                 clipBounds[1] = clipBox.GetExtents();
2798
2799                 // test the outer edges of this frustum for intersection with both the other frustum and the clip bounds
2800                 if ( (outside & 2) && (outside & 8) ) {
2801                         frustum.LocalRayIntersection( localOrigin1, localAxis1[0] - localAxis1[1] - localAxis1[2], s1, s2 );
2802                         if ( s1 <= s2 && s1 >= 0.0f ) {
2803                                 BoundsRayIntersection( clipBounds, localOrigin2, localAxis2[0] - localAxis2[1] - localAxis2[2], t1, t2 );
2804                                 if ( t1 <= t2 && t2 > s1 && t1 < s2 ) {
2805                                         projectionBounds.AddPoint( idVec3( s1 * dFar, -1.0f, -1.0f ) );
2806                                         projectionBounds.AddPoint( idVec3( s2 * dFar, -1.0f, -1.0f ) );
2807                                 }
2808                         }
2809                 }
2810                 if ( (outside & 2) && (outside & 4) ) {
2811                         frustum.LocalRayIntersection( localOrigin1, localAxis1[0] - localAxis1[1] + localAxis1[2], s1, s2 );
2812                         if ( s1 <= s2 && s1 >= 0.0f ) {
2813                                 BoundsRayIntersection( clipBounds, localOrigin2, localAxis2[0] - localAxis2[1] + localAxis2[2], t1, t2 );
2814                                 if ( t1 <= t2 && t2 > s1 && t1 < s2 ) {
2815                                         projectionBounds.AddPoint( idVec3( s1 * dFar, -1.0f, 1.0f ) );
2816                                         projectionBounds.AddPoint( idVec3( s2 * dFar, -1.0f, 1.0f ) );
2817                                 }
2818                         }
2819                 }
2820                 if ( (outside & 1) && (outside & 8) ) {
2821                         frustum.LocalRayIntersection( localOrigin1, localAxis1[0] + localAxis1[1] - localAxis1[2], s1, s2 );
2822                         if ( s1 <= s2 && s1 >= 0.0f ) {
2823                                 BoundsRayIntersection( clipBounds, localOrigin2, localAxis2[0] + localAxis2[1] - localAxis2[2], t1, t2 );
2824                                 if ( t1 <= t2 && t2 > s1 && t1 < s2 ) {
2825                                         projectionBounds.AddPoint( idVec3( s1 * dFar, 1.0f, -1.0f ) );
2826                                         projectionBounds.AddPoint( idVec3( s2 * dFar, 1.0f, -1.0f ) );
2827                                 }
2828                         }
2829                 }
2830                 if ( (outside & 1) && (outside & 2) ) {
2831                         frustum.LocalRayIntersection( localOrigin1, localAxis1[0] + localAxis1[1] + localAxis1[2], s1, s2 );
2832                         if ( s1 <= s2 && s1 >= 0.0f ) {
2833                                 BoundsRayIntersection( clipBounds, localOrigin2, localAxis2[0] + localAxis2[1] + localAxis2[2], t1, t2 );
2834                                 if ( t1 <= t2 && t2 > s1 && t1 < s2 ) {
2835                                         projectionBounds.AddPoint( idVec3( s1 * dFar, 1.0f, 1.0f ) );
2836                                         projectionBounds.AddPoint( idVec3( s2 * dFar, 1.0f, 1.0f ) );
2837                                 }
2838                         }
2839                 }
2840         }
2841
2842         return true;
2843 }