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