home *** CD-ROM | disk | FTP | other *** search
/ GameStar 2006 March / Gamestar_82_2006-03_dvd.iso / DVDStar / Editace / quake4_sdkv10.exe / source / idlib / bv / Box.cpp < prev    next >
C/C++ Source or Header  |  2005-11-14  |  21KB  |  821 lines
  1.  
  2. #include "../precompiled.h"
  3. #pragma hdrstop
  4.  
  5. idBox box_zero( vec3_zero, vec3_zero, mat3_identity );
  6.  
  7. /*
  8.             4---{4}---5
  9.  +         /|        /|
  10.  Z      {7} {8}   {5} |
  11.  -     /    |    /    {9}
  12.       7--{6}----6     |
  13.       |     |   |     |
  14.     {11}    0---|-{0}-1
  15.       |    /    |    /       -
  16.       | {3}  {10} {1}       Y
  17.       |/        |/         +
  18.       3---{2}---2
  19.  
  20.         - X +
  21.  
  22.   plane bits:
  23.   0 = min x
  24.   1 = max x
  25.   2 = min y
  26.   3 = max y
  27.   4 = min z
  28.   5 = max z
  29.  
  30. */
  31.  
  32. static int boxVertPlanes[8] = {
  33.     ( (1<<0) | (1<<2) | (1<<4) ),
  34.     ( (1<<1) | (1<<2) | (1<<4) ),
  35.     ( (1<<1) | (1<<3) | (1<<4) ),
  36.     ( (1<<0) | (1<<3) | (1<<4) ),
  37.     ( (1<<0) | (1<<2) | (1<<5) ),
  38.     ( (1<<1) | (1<<2) | (1<<5) ),
  39.     ( (1<<1) | (1<<3) | (1<<5) ),
  40.     ( (1<<0) | (1<<3) | (1<<5) )
  41. };
  42.  
  43. static int boxVertEdges[8][3] = {
  44.     // bottom
  45.     { 3, 0, 8 },
  46.     { 0, 1, 9 },
  47.     { 1, 2, 10 },
  48.     { 2, 3, 11 },
  49.     // top
  50.     { 7, 4, 8 },
  51.     { 4, 5, 9 },
  52.     { 5, 6, 10 },
  53.     { 6, 7, 11 }
  54. };
  55.  
  56. static int boxEdgePlanes[12][2] = {
  57.     // bottom
  58.     { 4, 2 },
  59.     { 4, 1 },
  60.     { 4, 3 },
  61.     { 4, 0 },
  62.     // top
  63.     { 5, 2 },
  64.     { 5, 1 },
  65.     { 5, 3 },
  66.     { 5, 0 },
  67.     // sides
  68.     { 0, 2 },
  69.     { 2, 1 },
  70.     { 1, 3 },
  71.     { 3, 0 }
  72. };
  73.  
  74. static int boxEdgeVerts[12][2] = {
  75.     // bottom
  76.     { 0, 1 },
  77.     { 1, 2 },
  78.     { 2, 3 },
  79.     { 3, 0 },
  80.     // top
  81.     { 4, 5 },
  82.     { 5, 6 },
  83.     { 6, 7 },
  84.     { 7, 4 },
  85.     // sides
  86.     { 0, 4 },
  87.     { 1, 5 },
  88.     { 2, 6 },
  89.     { 3, 7 }
  90. };
  91.  
  92. static int boxPlaneBitsSilVerts[64][7] = {
  93.     { 0, 0, 0, 0, 0, 0, 0 }, // 000000 = 0
  94.     { 4, 7, 4, 0, 3, 0, 0 }, // 000001 = 1
  95.     { 4, 5, 6, 2, 1, 0, 0 }, // 000010 = 2
  96.     { 0, 0, 0, 0, 0, 0, 0 }, // 000011 = 3
  97.     { 4, 4, 5, 1, 0, 0, 0 }, // 000100 = 4
  98.     { 6, 3, 7, 4, 5, 1, 0 }, // 000101 = 5
  99.     { 6, 4, 5, 6, 2, 1, 0 }, // 000110 = 6
  100.     { 0, 0, 0, 0, 0, 0, 0 }, // 000111 = 7
  101.     { 4, 6, 7, 3, 2, 0, 0 }, // 001000 = 8
  102.     { 6, 6, 7, 4, 0, 3, 2 }, // 001001 = 9
  103.     { 6, 5, 6, 7, 3, 2, 1 }, // 001010 = 10
  104.     { 0, 0, 0, 0, 0, 0, 0 }, // 001011 = 11
  105.     { 0, 0, 0, 0, 0, 0, 0 }, // 001100 = 12
  106.     { 0, 0, 0, 0, 0, 0, 0 }, // 001101 = 13
  107.     { 0, 0, 0, 0, 0, 0, 0 }, // 001110 = 14
  108.     { 0, 0, 0, 0, 0, 0, 0 }, // 001111 = 15
  109.     { 4, 0, 1, 2, 3, 0, 0 }, // 010000 = 16
  110.     { 6, 0, 1, 2, 3, 7, 4 }, // 010001 = 17
  111.     { 6, 3, 2, 6, 5, 1, 0 }, // 010010 = 18
  112.     { 0, 0, 0, 0, 0, 0, 0 }, // 010011 = 19
  113.     { 6, 1, 2, 3, 0, 4, 5 }, // 010100 = 20
  114.     { 6, 1, 2, 3, 7, 4, 5 }, // 010101 = 21
  115.     { 6, 2, 3, 0, 4, 5, 6 }, // 010110 = 22
  116.     { 0, 0, 0, 0, 0, 0, 0 }, // 010111 = 23
  117.     { 6, 0, 1, 2, 6, 7, 3 }, // 011000 = 24
  118.     { 6, 0, 1, 2, 6, 7, 4 }, // 011001 = 25
  119.     { 6, 0, 1, 5, 6, 7, 3 }, // 011010 = 26
  120.     { 0, 0, 0, 0, 0, 0, 0 }, // 011011 = 27
  121.     { 0, 0, 0, 0, 0, 0, 0 }, // 011100 = 28
  122.     { 0, 0, 0, 0, 0, 0, 0 }, // 011101 = 29
  123.     { 0, 0, 0, 0, 0, 0, 0 }, // 011110 = 30
  124.     { 0, 0, 0, 0, 0, 0, 0 }, // 011111 = 31
  125.     { 4, 7, 6, 5, 4, 0, 0 }, // 100000 = 32
  126.     { 6, 7, 6, 5, 4, 0, 3 }, // 100001 = 33
  127.     { 6, 5, 4, 7, 6, 2, 1 }, // 100010 = 34
  128.     { 0, 0, 0, 0, 0, 0, 0 }, // 100011 = 35
  129.     { 6, 4, 7, 6, 5, 1, 0 }, // 100100 = 36
  130.     { 6, 3, 7, 6, 5, 1, 0 }, // 100101 = 37
  131.     { 6, 4, 7, 6, 2, 1, 0 }, // 100110 = 38
  132.     { 0, 0, 0, 0, 0, 0, 0 }, // 100111 = 39
  133.     { 6, 6, 5, 4, 7, 3, 2 }, // 101000 = 40
  134.     { 6, 6, 5, 4, 0, 3, 2 }, // 101001 = 41
  135.     { 6, 5, 4, 7, 3, 2, 1 }, // 101010 = 42
  136.     { 0, 0, 0, 0, 0, 0, 0 }, // 101011 = 43
  137.     { 0, 0, 0, 0, 0, 0, 0 }, // 101100 = 44
  138.     { 0, 0, 0, 0, 0, 0, 0 }, // 101101 = 45
  139.     { 0, 0, 0, 0, 0, 0, 0 }, // 101110 = 46
  140.     { 0, 0, 0, 0, 0, 0, 0 }, // 101111 = 47
  141.     { 0, 0, 0, 0, 0, 0, 0 }, // 110000 = 48
  142.     { 0, 0, 0, 0, 0, 0, 0 }, // 110001 = 49
  143.     { 0, 0, 0, 0, 0, 0, 0 }, // 110010 = 50
  144.     { 0, 0, 0, 0, 0, 0, 0 }, // 110011 = 51
  145.     { 0, 0, 0, 0, 0, 0, 0 }, // 110100 = 52
  146.     { 0, 0, 0, 0, 0, 0, 0 }, // 110101 = 53
  147.     { 0, 0, 0, 0, 0, 0, 0 }, // 110110 = 54
  148.     { 0, 0, 0, 0, 0, 0, 0 }, // 110111 = 55
  149.     { 0, 0, 0, 0, 0, 0, 0 }, // 111000 = 56
  150.     { 0, 0, 0, 0, 0, 0, 0 }, // 111001 = 57
  151.     { 0, 0, 0, 0, 0, 0, 0 }, // 111010 = 58
  152.     { 0, 0, 0, 0, 0, 0, 0 }, // 111011 = 59
  153.     { 0, 0, 0, 0, 0, 0, 0 }, // 111100 = 60
  154.     { 0, 0, 0, 0, 0, 0, 0 }, // 111101 = 61
  155.     { 0, 0, 0, 0, 0, 0, 0 }, // 111110 = 62
  156.     { 0, 0, 0, 0, 0, 0, 0 }, // 111111 = 63
  157. };
  158.  
  159.  
  160. /*
  161. ============
  162. idBox::AddPoint
  163. ============
  164. */
  165. bool idBox::AddPoint( const idVec3 &v ) {
  166.     idMat3 axis2;
  167.     idBounds bounds1, bounds2;
  168.  
  169.     if ( extents[0] < 0.0f ) {
  170.         extents.Zero();
  171.         center = v;
  172.         axis.Identity();
  173.         return true;
  174.     }
  175.  
  176.     bounds1[0][0] = bounds1[1][0] = center * axis[0];
  177.     bounds1[0][1] = bounds1[1][1] = center * axis[1];
  178.     bounds1[0][2] = bounds1[1][2] = center * axis[2];
  179.     bounds1[0] -= extents;
  180.     bounds1[1] += extents;
  181.     if ( !bounds1.AddPoint( idVec3( v * axis[0], v * axis[1], v * axis[2] ) ) ) {
  182.         // point is contained in the box
  183.         return false;
  184.     }
  185.  
  186.     axis2[0] = v - center;
  187.     axis2[0].Normalize();
  188.     axis2[1] = axis[ Min3Index( axis2[0] * axis[0], axis2[0] * axis[1], axis2[0] * axis[2] ) ];
  189.     axis2[1] = axis2[1] - ( axis2[1] * axis2[0] ) * axis2[0];
  190.     axis2[1].Normalize();
  191.     axis2[2].Cross( axis2[0], axis2[1] );
  192.  
  193.     AxisProjection( axis2, bounds2 );
  194.     bounds2.AddPoint( idVec3( v * axis2[0], v * axis2[1], v * axis2[2] ) );
  195.  
  196.     // create new box based on the smallest bounds
  197.     if ( bounds1.GetVolume() < bounds2.GetVolume() ) {
  198.         center = ( bounds1[0] + bounds1[1] ) * 0.5f;
  199.         extents = bounds1[1] - center;
  200.         center *= axis;
  201.     }
  202.     else {
  203.         center = ( bounds2[0] + bounds2[1] ) * 0.5f;
  204.         extents = bounds2[1] - center;
  205.         center *= axis2;
  206.         axis = axis2;
  207.     }
  208.     return true;
  209. }
  210.  
  211. /*
  212. ============
  213. idBox::AddBox
  214. ============
  215. */
  216. bool idBox::AddBox( const idBox &a ) {
  217.     int i, besti;
  218.     float v, bestv;
  219.     idVec3 dir;
  220.     idMat3 ax[4];
  221.     idBounds bounds[4], b;
  222.  
  223.     if ( a.extents[0] < 0.0f ) {
  224.         return false;
  225.     }
  226.  
  227.     if ( extents[0] < 0.0f ) {
  228.         center = a.center;
  229.         extents = a.extents;
  230.         axis = a.axis;
  231.         return true;
  232.     }
  233.  
  234.     // test axis of this box
  235.     ax[0] = axis;
  236.     bounds[0][0][0] = bounds[0][1][0] = center * ax[0][0];
  237.     bounds[0][0][1] = bounds[0][1][1] = center * ax[0][1];
  238.     bounds[0][0][2] = bounds[0][1][2] = center * ax[0][2];
  239.     bounds[0][0] -= extents;
  240.     bounds[0][1] += extents;
  241.     a.AxisProjection( ax[0], b );
  242.     if ( !bounds[0].AddBounds( b ) ) {
  243.         // the other box is contained in this box
  244.         return false;
  245.     }
  246.  
  247.     // test axis of other box
  248.     ax[1] = a.axis;
  249.     bounds[1][0][0] = bounds[1][1][0] = a.center * ax[1][0];
  250.     bounds[1][0][1] = bounds[1][1][1] = a.center * ax[1][1];
  251.     bounds[1][0][2] = bounds[1][1][2] = a.center * ax[1][2];
  252.     bounds[1][0] -= a.extents;
  253.     bounds[1][1] += a.extents;
  254.     AxisProjection( ax[1], b );
  255.     if ( !bounds[1].AddBounds( b ) ) {
  256.         // this box is contained in the other box
  257.         center = a.center;
  258.         extents = a.extents;
  259.         axis = a.axis;
  260.         return true;
  261.     }
  262.  
  263.     // test axes aligned with the vector between the box centers and one of the box axis
  264.     dir = a.center - center;
  265.     dir.Normalize();
  266.     for ( i = 2; i < 4; i++ ) {
  267.         ax[i][0] = dir;
  268.         ax[i][1] = ax[i-2][ Min3Index( dir * ax[i-2][0], dir * ax[i-2][1], dir * ax[i-2][2] ) ];
  269.         ax[i][1] = ax[i][1] - ( ax[i][1] * dir ) * dir;
  270.         ax[i][1].Normalize();
  271.         ax[i][2].Cross( dir, ax[i][1] );
  272.  
  273.         AxisProjection( ax[i], bounds[i] );
  274.         a.AxisProjection( ax[i], b );
  275.         bounds[i].AddBounds( b );
  276.     }
  277.  
  278.     // get the bounds with the smallest volume
  279.     bestv = idMath::INFINITY;
  280.     besti = 0;
  281.     for ( i = 0; i < 4; i++ ) {
  282.         v = bounds[i].GetVolume();
  283.         if ( v < bestv ) {
  284.             bestv = v;
  285.             besti = i;
  286.         }
  287.     }
  288.  
  289.     // create a box from the smallest bounds axis pair
  290.     center = ( bounds[besti][0] + bounds[besti][1] ) * 0.5f;
  291.     extents = bounds[besti][1] - center;
  292.     center *= ax[besti];
  293.     axis = ax[besti];
  294.  
  295.     return false;
  296. }
  297.  
  298. /*
  299. ================
  300. idBox::PlaneDistance
  301. ================
  302. */
  303. float idBox::PlaneDistance( const idPlane &plane ) const {
  304.     float d1, d2;
  305.  
  306.     d1 = plane.Distance( center );
  307.     d2 = idMath::Fabs( extents[0] * ( plane.Normal() * axis[0] ) ) +
  308.             idMath::Fabs( extents[1] * ( plane.Normal() * axis[1] ) ) +
  309.                 idMath::Fabs( extents[2] * ( plane.Normal() * axis[2] ) );
  310.  
  311.     if ( d1 - d2 > 0.0f ) {
  312.         return d1 - d2;
  313.     }
  314.     if ( d1 + d2 < 0.0f ) {
  315.         return d1 + d2;
  316.     }
  317.     return 0.0f;
  318. }
  319.  
  320. /*
  321. ================
  322. idBox::PlaneSide
  323. ================
  324. */
  325. int idBox::PlaneSide( const idPlane &plane, const float epsilon ) const {
  326.     float d1, d2;
  327.  
  328.     d1 = plane.Distance( center );
  329.     d2 = idMath::Fabs( extents[0] * ( plane.Normal() * axis[0] ) ) +
  330.             idMath::Fabs( extents[1] * ( plane.Normal() * axis[1] ) ) +
  331.                 idMath::Fabs( extents[2] * ( plane.Normal() * axis[2] ) );
  332.  
  333.     if ( d1 - d2 > epsilon ) {
  334.         return PLANESIDE_FRONT;
  335.     }
  336.     if ( d1 + d2 < -epsilon ) {
  337.         return PLANESIDE_BACK;
  338.     }
  339.     return PLANESIDE_CROSS;
  340. }
  341.  
  342. /*
  343. ============
  344. idBox::IntersectsBox
  345. ============
  346. */
  347. bool idBox::IntersectsBox( const idBox &a ) const {
  348.     idVec3 dir;            // vector between centers
  349.     float c[3][3];        // matrix c = axis.Transpose() * a.axis
  350.     float ac[3][3];        // absolute values of c
  351.     float axisdir[3];    // axis[i] * dir
  352.     float d, e0, e1;    // distance between centers and projected extents
  353.  
  354.     dir = a.center - center;
  355.     
  356.     // axis C0 + t * A0
  357.     c[0][0] = axis[0] * a.axis[0];
  358.     c[0][1] = axis[0] * a.axis[1];
  359.     c[0][2] = axis[0] * a.axis[2];
  360.     axisdir[0] = axis[0] * dir;
  361.     ac[0][0] = idMath::Fabs( c[0][0] );
  362.     ac[0][1] = idMath::Fabs( c[0][1] );
  363.     ac[0][2] = idMath::Fabs( c[0][2] );
  364.  
  365.     d = idMath::Fabs( axisdir[0] );
  366.     e0 = extents[0];
  367.     e1 = a.extents[0] * ac[0][0] + a.extents[1] * ac[0][1] + a.extents[2] * ac[0][2];
  368.     if ( d > e0 + e1 ) {
  369.         return false;
  370.     }
  371.  
  372.     // axis C0 + t * A1
  373.     c[1][0] = axis[1] * a.axis[0];
  374.     c[1][1] = axis[1] * a.axis[1];
  375.     c[1][2] = axis[1] * a.axis[2];
  376.     axisdir[1] = axis[1] * dir;
  377.     ac[1][0] = idMath::Fabs( c[1][0] );
  378.     ac[1][1] = idMath::Fabs( c[1][1] );
  379.     ac[1][2] = idMath::Fabs( c[1][2] );
  380.  
  381.     d = idMath::Fabs( axisdir[1] );
  382.     e0 = extents[1];
  383.     e1 = a.extents[0] * ac[1][0] + a.extents[1] * ac[1][1] + a.extents[2] * ac[1][2];
  384.     if ( d > e0 + e1 ) {
  385.         return false;
  386.     }
  387.  
  388.     // axis C0 + t * A2
  389.     c[2][0] = axis[2] * a.axis[0];
  390.     c[2][1] = axis[2] * a.axis[1];
  391.     c[2][2] = axis[2] * a.axis[2];
  392.     axisdir[2] = axis[2] * dir;
  393.     ac[2][0] = idMath::Fabs( c[2][0] );
  394.     ac[2][1] = idMath::Fabs( c[2][1] );
  395.     ac[2][2] = idMath::Fabs( c[2][2] );
  396.  
  397.     d = idMath::Fabs( axisdir[2] );
  398.     e0 = extents[2];
  399.     e1 = a.extents[0] * ac[2][0] + a.extents[1] * ac[2][1] + a.extents[2] * ac[2][2];
  400.     if ( d > e0 + e1 ) {
  401.         return false;
  402.     }
  403.  
  404.     // axis C0 + t * B0
  405.     d = idMath::Fabs( a.axis[0] * dir );
  406.     e0 = extents[0] * ac[0][0] + extents[1] * ac[1][0] + extents[2] * ac[2][0];
  407.     e1 = a.extents[0];
  408.     if ( d > e0 + e1 ) {
  409.         return false;
  410.     }
  411.  
  412.     // axis C0 + t * B1
  413.     d = idMath::Fabs( a.axis[1] * dir );
  414.     e0 = extents[0] * ac[0][1] + extents[1] * ac[1][1] + extents[2] * ac[2][1];
  415.     e1 = a.extents[1];
  416.     if ( d > e0 + e1 ) {
  417.         return false;
  418.     }
  419.  
  420.     // axis C0 + t * B2
  421.     d = idMath::Fabs( a.axis[2] * dir );
  422.     e0 = extents[0] * ac[0][2] + extents[1] * ac[1][2] + extents[2] * ac[2][2];
  423.     e1 = a.extents[2];
  424.     if ( d > e0 + e1 ) {
  425.         return false;
  426.     }
  427.  
  428.     // axis C0 + t * A0xB0
  429.     d = idMath::Fabs( axisdir[2] * c[1][0] - axisdir[1] * c[2][0] );
  430.     e0 = extents[1] * ac[2][0] + extents[2] * ac[1][0];
  431.     e1 = a.extents[1] * ac[0][2] + a.extents[2] * ac[0][1];
  432.     if ( d > e0 + e1 ) {
  433.         return false;
  434.     }
  435.  
  436.     // axis C0 + t * A0xB1
  437.     d = idMath::Fabs( axisdir[2] * c[1][1] - axisdir[1] * c[2][1] );
  438.     e0 = extents[1] * ac[2][1] + extents[2] * ac[1][1];
  439.     e1 = a.extents[0] * ac[0][2] + a.extents[2] * ac[0][0];
  440.     if ( d > e0 + e1 ) {
  441.         return false;
  442.     }
  443.  
  444.     // axis C0 + t * A0xB2
  445.     d = idMath::Fabs( axisdir[2] * c[1][2] - axisdir[1] * c[2][2] );
  446.     e0 = extents[1] * ac[2][2] + extents[2] * ac[1][2];
  447.     e1 = a.extents[0] * ac[0][1] + a.extents[1] * ac[0][0];
  448.     if ( d > e0 + e1 ) {
  449.         return false;
  450.     }
  451.  
  452.     // axis C0 + t * A1xB0
  453.     d = idMath::Fabs( axisdir[0] * c[2][0] - axisdir[2] * c[0][0] );
  454.     e0 = extents[0] * ac[2][0] + extents[2] * ac[0][0];
  455.     e1 = a.extents[1] * ac[1][2] + a.extents[2] * ac[1][1];
  456.     if ( d > e0 + e1 ) {
  457.         return false;
  458.     }
  459.  
  460.     // axis C0 + t * A1xB1
  461.     d = idMath::Fabs( axisdir[0] * c[2][1] - axisdir[2] * c[0][1] );
  462.     e0 = extents[0] * ac[2][1] + extents[2] * ac[0][1];
  463.     e1 = a.extents[0] * ac[1][2] + a.extents[2] * ac[1][0];
  464.     if ( d > e0 + e1 ) {
  465.         return false;
  466.     }
  467.  
  468.     // axis C0 + t * A1xB2
  469.     d = idMath::Fabs( axisdir[0] * c[2][2] - axisdir[2] * c[0][2] );
  470.     e0 = extents[0] * ac[2][2] + extents[2] * ac[0][2];
  471.     e1 = a.extents[0] * ac[1][1] + a.extents[1] * ac[1][0];
  472.     if ( d > e0 + e1 ) {
  473.         return false;
  474.     }
  475.  
  476.     // axis C0 + t * A2xB0
  477.     d = idMath::Fabs( axisdir[1] * c[0][0] - axisdir[0] * c[1][0] );
  478.     e0 = extents[0] * ac[1][0] + extents[1] * ac[0][0];
  479.     e1 = a.extents[1] * ac[2][2] + a.extents[2] * ac[2][1];
  480.     if ( d > e0 + e1 ) {
  481.         return false;
  482.     }
  483.  
  484.     // axis C0 + t * A2xB1
  485.     d = idMath::Fabs( axisdir[1] * c[0][1] - axisdir[0] * c[1][1] );
  486.     e0 = extents[0] * ac[1][1] + extents[1] * ac[0][1];
  487.     e1 = a.extents[0] * ac[2][2] + a.extents[2] * ac[2][0];
  488.     if ( d > e0 + e1 ) {
  489.         return false;
  490.     }
  491.  
  492.     // axis C0 + t * A2xB2
  493.     d = idMath::Fabs( axisdir[1] * c[0][2] - axisdir[0] * c[1][2] );
  494.     e0 = extents[0] * ac[1][2] + extents[1] * ac[0][2];
  495.     e1 = a.extents[0] * ac[2][1] + a.extents[1] * ac[2][0];
  496.     if ( d > e0 + e1 ) {
  497.         return false;
  498.     }
  499.     return true;
  500. }
  501.  
  502. /*
  503. ============
  504. idBox::LineIntersection
  505.  
  506.   Returns true if the line intersects the box between the start and end point.
  507. ============
  508. */
  509. bool idBox::LineIntersection( const idVec3 &start, const idVec3 &end ) const {
  510.     float ld[3];
  511.     idVec3 lineDir = 0.5f * ( end - start );
  512.     idVec3 lineCenter = start + lineDir;
  513.     idVec3 dir = lineCenter - center;
  514.  
  515.     ld[0] = idMath::Fabs( lineDir * axis[0] );
  516.     if ( idMath::Fabs( dir * axis[0] ) > extents[0] + ld[0] ) {
  517.         return false;
  518.     }
  519.  
  520.     ld[1] = idMath::Fabs( lineDir * axis[1] );
  521.     if ( idMath::Fabs( dir * axis[1] ) > extents[1] + ld[1] ) {
  522.         return false;
  523.     }
  524.  
  525.     ld[2] = idMath::Fabs( lineDir * axis[2] );
  526.     if ( idMath::Fabs( dir * axis[2] ) > extents[2] + ld[2] ) {
  527.         return false;
  528.     }
  529.  
  530.     idVec3 cross = lineDir.Cross( dir );
  531.  
  532.     if ( idMath::Fabs( cross * axis[0] ) > extents[1] * ld[2] + extents[2] * ld[1] ) {
  533.         return false;
  534.     }
  535.  
  536.     if ( idMath::Fabs( cross * axis[1] ) > extents[0] * ld[2] + extents[2] * ld[0] ) {
  537.         return false;
  538.     }
  539.  
  540.     if ( idMath::Fabs( cross * axis[2] ) > extents[0] * ld[1] + extents[1] * ld[0] ) {
  541.         return false;
  542.     }
  543.  
  544.     return true;
  545. }
  546.  
  547. /*
  548. ============
  549. BoxPlaneClip
  550. ============
  551. */
  552. static bool BoxPlaneClip( const float denom, const float numer, float &scale0, float &scale1 ) {
  553.     if ( denom > 0.0f ) {
  554.         if ( numer > denom * scale1 ) {
  555.             return false;
  556.         }
  557.         if ( numer > denom * scale0 ) {
  558.             scale0 = numer / denom;
  559.         }
  560.         return true;
  561.     }
  562.     else if ( denom < 0.0f ) {
  563.         if ( numer > denom * scale0 ) {
  564.             return false;
  565.         }
  566.         if ( numer > denom * scale1 ) {
  567.             scale1 = numer / denom;
  568.         }
  569.         return true;
  570.     }
  571.     else {
  572.         return ( numer <= 0.0f );
  573.     }
  574. }
  575.  
  576. /*
  577. ============
  578. idBox::RayIntersection
  579.  
  580.   Returns true if the ray intersects the box.
  581.   The ray can intersect the box in both directions from the start point.
  582.   If start is inside the box then scale1 < 0 and scale2 > 0.
  583. ============
  584. */
  585. bool idBox::RayIntersection( const idVec3 &start, const idVec3 &dir, float &scale1, float &scale2 ) const {
  586.     idVec3 localStart, localDir;
  587.  
  588.     localStart = ( start - center ) * axis.Transpose();
  589.     localDir = dir * axis.Transpose();
  590.  
  591.     scale1 = -idMath::INFINITY;
  592.     scale2 = idMath::INFINITY;
  593.     return    BoxPlaneClip(  localDir.x, -localStart.x - extents[0], scale1, scale2 ) &&
  594.             BoxPlaneClip( -localDir.x,  localStart.x - extents[0], scale1, scale2 ) &&
  595.             BoxPlaneClip(  localDir.y, -localStart.y - extents[1], scale1, scale2 ) &&
  596.             BoxPlaneClip( -localDir.y,  localStart.y - extents[1], scale1, scale2 ) &&
  597.             BoxPlaneClip(  localDir.z, -localStart.z - extents[2], scale1, scale2 ) &&
  598.             BoxPlaneClip( -localDir.z,  localStart.z - extents[2], scale1, scale2 );
  599. }
  600.  
  601. /*
  602. ============
  603. idBox::FromPoints
  604.  
  605.   Tight box for a collection of points.
  606. ============
  607. */
  608. void idBox::FromPoints( const idVec3 *points, const int numPoints ) {
  609.     int i;
  610.     float invNumPoints, sumXX, sumXY, sumXZ, sumYY, sumYZ, sumZZ;
  611.     idVec3 dir;
  612.     idBounds bounds;
  613.     idMatX eigenVectors;
  614.     idVecX eigenValues;
  615.  
  616.     // compute mean of points
  617.     center = points[0];
  618.     for ( i = 1; i < numPoints; i++ ) {
  619.         center += points[i];
  620.     }
  621.     invNumPoints = 1.0f / numPoints;
  622.     center *= invNumPoints;
  623.  
  624.     // compute covariances of points
  625.     sumXX = 0.0f; sumXY = 0.0f; sumXZ = 0.0f;
  626.     sumYY = 0.0f; sumYZ = 0.0f; sumZZ = 0.0f;
  627.     for ( i = 0; i < numPoints; i++ ) {
  628.         dir = points[i] - center;
  629.         sumXX += dir.x * dir.x;
  630.         sumXY += dir.x * dir.y;
  631.         sumXZ += dir.x * dir.z;
  632.         sumYY += dir.y * dir.y;
  633.         sumYZ += dir.y * dir.z;
  634.         sumZZ += dir.z * dir.z;
  635.     }
  636.     sumXX *= invNumPoints;
  637.     sumXY *= invNumPoints;
  638.     sumXZ *= invNumPoints;
  639.     sumYY *= invNumPoints;
  640.     sumYZ *= invNumPoints;
  641.     sumZZ *= invNumPoints;
  642.  
  643.     // compute eigenvectors for covariance matrix
  644.     eigenValues.SetData( 3, VECX_ALLOCA( 3 ) );
  645.     eigenVectors.SetData( 3, 3, MATX_ALLOCA( 3 * 3 ) );
  646.  
  647.     eigenVectors[0][0] = sumXX;
  648.     eigenVectors[0][1] = sumXY;
  649.     eigenVectors[0][2] = sumXZ;
  650.     eigenVectors[1][0] = sumXY;
  651.     eigenVectors[1][1] = sumYY;
  652.     eigenVectors[1][2] = sumYZ;
  653.     eigenVectors[2][0] = sumXZ;
  654.     eigenVectors[2][1] = sumYZ;
  655.     eigenVectors[2][2] = sumZZ;
  656.     eigenVectors.Eigen_SolveSymmetric( eigenValues );
  657.     eigenVectors.Eigen_SortIncreasing( eigenValues );
  658.  
  659.     axis[0][0] = eigenVectors[0][0];
  660.     axis[0][1] = eigenVectors[0][1];
  661.     axis[0][2] = eigenVectors[0][2];
  662.     axis[1][0] = eigenVectors[1][0];
  663.     axis[1][1] = eigenVectors[1][1];
  664.     axis[1][2] = eigenVectors[1][2];
  665.     axis[2][0] = eigenVectors[2][0];
  666.     axis[2][1] = eigenVectors[2][1];
  667.     axis[2][2] = eigenVectors[2][2];
  668.  
  669.     extents[0] = eigenValues[0];
  670.     extents[1] = eigenValues[0];
  671.     extents[2] = eigenValues[0];
  672.  
  673.     // refine by calculating the bounds of the points projected onto the axis and adjusting the center and extents
  674.     bounds.Clear();
  675.     for ( i = 0; i < numPoints; i++ ) {
  676.         bounds.AddPoint( idVec3( points[i] * axis[0], points[i] * axis[1], points[i] * axis[2] ) );
  677.     }
  678.     center = ( bounds[0] + bounds[1] ) * 0.5f;
  679.     extents = bounds[1] - center;
  680.     center *= axis;
  681. }
  682.  
  683. /*
  684. ============
  685. idBox::FromPointTranslation
  686.  
  687.   Most tight box for the translational movement of the given point.
  688. ============
  689. */
  690. void idBox::FromPointTranslation( const idVec3 &point, const idVec3 &translation ) {
  691.     // FIXME: implement
  692. }
  693.  
  694. /*
  695. ============
  696. idBox::FromBoxTranslation
  697.  
  698.   Most tight box for the translational movement of the given box.
  699. ============
  700. */
  701. void idBox::FromBoxTranslation( const idBox &box, const idVec3 &translation ) {
  702.     // FIXME: implement
  703. }
  704.  
  705. /*
  706. ============
  707. idBox::FromPointRotation
  708.  
  709.   Most tight bounds for the rotational movement of the given point.
  710. ============
  711. */
  712. void idBox::FromPointRotation( const idVec3 &point, const idRotation &rotation ) {
  713.     // FIXME: implement
  714. }
  715.  
  716. /*
  717. ============
  718. idBox::FromBoxRotation
  719.  
  720.   Most tight box for the rotational movement of the given box.
  721. ============
  722. */
  723. void idBox::FromBoxRotation( const idBox &box, const idRotation &rotation ) {
  724.     // FIXME: implement
  725. }
  726.  
  727. /*
  728. ============
  729. idBox::ToPoints
  730. ============
  731. */
  732. void idBox::ToPoints( idVec3 points[8] ) const {
  733.     idMat3 ax;
  734.     idVec3 temp[4];
  735.  
  736.     ax[0] = extents[0] * axis[0];
  737.     ax[1] = extents[1] * axis[1];
  738.     ax[2] = extents[2] * axis[2];
  739.     temp[0] = center - ax[0];
  740.     temp[1] = center + ax[0];
  741.     temp[2] = ax[1] - ax[2];
  742.     temp[3] = ax[1] + ax[2];
  743.     points[0] = temp[0] - temp[3];
  744.     points[1] = temp[1] - temp[3];
  745.     points[2] = temp[1] + temp[2];
  746.     points[3] = temp[0] + temp[2];
  747.     points[4] = temp[0] - temp[2];
  748.     points[5] = temp[1] - temp[2];
  749.     points[6] = temp[1] + temp[3];
  750.     points[7] = temp[0] + temp[3];
  751. }
  752.  
  753. /*
  754. ============
  755. idBox::GetProjectionSilhouetteVerts
  756. ============
  757. */
  758. int idBox::GetProjectionSilhouetteVerts( const idVec3 &projectionOrigin, idVec3 silVerts[6] ) const {
  759.     float f;
  760.     int i, planeBits, *index;
  761.     idVec3 points[8], dir1, dir2;
  762.  
  763.     ToPoints( points );
  764.  
  765.     dir1 = points[0] - projectionOrigin;
  766.     dir2 = points[6] - projectionOrigin;
  767.     f = dir1 * axis[0];
  768.     planeBits = FLOATSIGNBITNOTSET( f );
  769.     f = dir2 * axis[0];
  770.     planeBits |= FLOATSIGNBITSET( f ) << 1;
  771.     f = dir1 * axis[1];
  772.     planeBits |= FLOATSIGNBITNOTSET( f ) << 2;
  773.     f = dir2 * axis[1];
  774.     planeBits |= FLOATSIGNBITSET( f ) << 3;
  775.     f = dir1 * axis[2];
  776.     planeBits |= FLOATSIGNBITNOTSET( f ) << 4;
  777.     f = dir2 * axis[2];
  778.     planeBits |= FLOATSIGNBITSET( f ) << 5;
  779.  
  780.     index = boxPlaneBitsSilVerts[planeBits];
  781.     for ( i = 0; i < index[0]; i++ ) {
  782.         silVerts[i] = points[index[i+1]];
  783.     }
  784.  
  785.     return index[0];
  786. }
  787.  
  788. /*
  789. ============
  790. idBox::GetParallelProjectionSilhouetteVerts
  791. ============
  792. */
  793. int idBox::GetParallelProjectionSilhouetteVerts( const idVec3 &projectionDir, idVec3 silVerts[6] ) const {
  794.     float f;
  795.     int i, planeBits, *index;
  796.     idVec3 points[8];
  797.  
  798.     ToPoints( points );
  799.  
  800.     planeBits = 0;
  801.     f = projectionDir * axis[0];
  802.     if ( FLOATNOTZERO( f ) ) {
  803.         planeBits = 1 << FLOATSIGNBITSET( f );
  804.     }
  805.     f = projectionDir * axis[1];
  806.     if ( FLOATNOTZERO( f ) ) {
  807.         planeBits |= 4 << FLOATSIGNBITSET( f );
  808.     }
  809.     f = projectionDir * axis[2];
  810.     if ( FLOATNOTZERO( f ) ) {
  811.         planeBits |= 16 << FLOATSIGNBITSET( f );
  812.     }
  813.  
  814.     index = boxPlaneBitsSilVerts[planeBits];
  815.     for ( i = 0; i < index[0]; i++ ) {
  816.         silVerts[i] = points[index[i+1]];
  817.     }
  818.  
  819.     return index[0];
  820. }
  821.