home *** CD-ROM | disk | FTP | other *** search
/ GameStar 2006 March / Gamestar_82_2006-03_dvd.iso / DVDStar / Editace / quake4_sdkv10.exe / source / idlib / bv / Bounds.cpp next >
C/C++ Source or Header  |  2005-11-14  |  11KB  |  469 lines
  1.  
  2. #include "../precompiled.h"
  3. #pragma hdrstop
  4.  
  5. idBounds bounds_zero( vec3_zero, vec3_zero );
  6.  
  7. /*
  8. ============
  9. idBounds::GetRadius
  10. ============
  11. */
  12. float idBounds::GetRadius( void ) const {
  13.     int        i;
  14.     float    total, b0, b1;
  15.  
  16.     total = 0.0f;
  17.     for ( i = 0; i < 3; i++ ) {
  18.         b0 = (float)idMath::Fabs( b[0][i] );
  19.         b1 = (float)idMath::Fabs( b[1][i] );
  20.         if ( b0 > b1 ) {
  21.             total += b0 * b0;
  22.         } else {
  23.             total += b1 * b1;
  24.         }
  25.     }
  26.     return idMath::Sqrt( total );
  27. }
  28.  
  29. /*
  30. ============
  31. idBounds::GetRadius
  32. ============
  33. */
  34. float idBounds::GetRadius( const idVec3 ¢er ) const {
  35.     int        i;
  36.     float    total, b0, b1;
  37.  
  38.     total = 0.0f;
  39.     for ( i = 0; i < 3; i++ ) {
  40.         b0 = (float)idMath::Fabs( center[i] - b[0][i] );
  41.         b1 = (float)idMath::Fabs( b[1][i] - center[i] );
  42.         if ( b0 > b1 ) {
  43.             total += b0 * b0;
  44.         } else {
  45.             total += b1 * b1;
  46.         }
  47.     }
  48.     return idMath::Sqrt( total );
  49. }
  50.  
  51. /*
  52. ================
  53. idBounds::PlaneDistance
  54. ================
  55. */
  56. float idBounds::PlaneDistance( const idPlane &plane ) const {
  57.     idVec3 center;
  58.     float d1, d2;
  59.  
  60.     center = ( b[0] + b[1] ) * 0.5f;
  61.  
  62.     d1 = plane.Distance( center );
  63.     d2 = idMath::Fabs( ( b[1][0] - center[0] ) * plane.Normal()[0] ) +
  64.             idMath::Fabs( ( b[1][1] - center[1] ) * plane.Normal()[1] ) +
  65.                 idMath::Fabs( ( b[1][2] - center[2] ) * plane.Normal()[2] );
  66.  
  67.     if ( d1 - d2 > 0.0f ) {
  68.         return d1 - d2;
  69.     }
  70.     if ( d1 + d2 < 0.0f ) {
  71.         return d1 + d2;
  72.     }
  73.     return 0.0f;
  74. }
  75.  
  76. // RAVEN BEGIN
  77. // jscott: for BSE attenuation
  78. /*
  79. ================
  80. idBounds::ShortestDistance
  81. ================
  82. */
  83. float idBounds::ShortestDistance( const idVec3 &point ) const {
  84.  
  85.     int        i;
  86.     float    delta, distance;
  87.  
  88.     if( ContainsPoint( point ) ) {
  89.  
  90.         return( 0.0f );
  91.     }
  92.  
  93.     distance = 0.0f;
  94.     for( i = 0; i < 3; i++ ) {
  95.  
  96.         if( point[i] < b[0][i] ) {
  97.  
  98.             delta = b[0][i] - point[i];
  99.             distance += delta * delta;
  100.  
  101.         } else if ( point[i] > b[1][i] ) {
  102.  
  103.             delta = point[i] - b[1][i];
  104.             distance += delta * delta;
  105.         }
  106.     }
  107.  
  108.     return( idMath::Sqrt( distance ) );
  109. }
  110.  
  111. // abahr: 
  112. idVec3 idBounds::FindEdgePoint( const idVec3& dir ) const {
  113.     return FindEdgePoint( GetCenter(), dir );
  114. }
  115.  
  116. idVec3 idBounds::FindEdgePoint( const idVec3& start, const idVec3& dir ) const {
  117.     idVec3 center( GetCenter() );
  118.     float radius = GetRadius( center );
  119.     idVec3 point( start + dir * radius );
  120.     float scale = 0.0f;
  121.  
  122.     RayIntersection( point, -dir, scale );
  123.     
  124.     idVec3 p = point + -dir * scale;
  125.     return p;
  126. }
  127.  
  128. idVec3 idBounds::FindVectorToEdge( const idVec3& dir ) const {
  129.     return idVec3( FindVectorToEdge(GetCenter(), dir) );
  130. }
  131.  
  132. idVec3 idBounds::FindVectorToEdge( const idVec3& start, const idVec3& dir ) const {
  133.     return idVec3( FindEdgePoint(start, dir) - start );
  134. }
  135. // RAVEN END
  136.  
  137. /*
  138. ================
  139. idBounds::PlaneSide
  140. ================
  141. */
  142. int idBounds::PlaneSide( const idPlane &plane, const float epsilon ) const {
  143.     idVec3 center;
  144.     float d1, d2;
  145.  
  146.     center = ( b[0] + b[1] ) * 0.5f;
  147.  
  148.     d1 = plane.Distance( center );
  149.     d2 = idMath::Fabs( ( b[1][0] - center[0] ) * plane.Normal()[0] ) +
  150.             idMath::Fabs( ( b[1][1] - center[1] ) * plane.Normal()[1] ) +
  151.                 idMath::Fabs( ( b[1][2] - center[2] ) * plane.Normal()[2] );
  152.  
  153.     if ( d1 - d2 > epsilon ) {
  154.         return PLANESIDE_FRONT;
  155.     }
  156.     if ( d1 + d2 < -epsilon ) {
  157.         return PLANESIDE_BACK;
  158.     }
  159.     return PLANESIDE_CROSS;
  160. }
  161.  
  162. /*
  163. ============
  164. idBounds::LineIntersection
  165.  
  166.   Returns true if the line intersects the bounds between the start and end point.
  167. ============
  168. */
  169. bool idBounds::LineIntersection( const idVec3 &start, const idVec3 &end ) const {
  170.     float ld[3];
  171.     idVec3 center = ( b[0] + b[1] ) * 0.5f;
  172.     idVec3 extents = b[1] - center;
  173.     idVec3 lineDir = 0.5f * ( end - start );
  174.     idVec3 lineCenter = start + lineDir;
  175.     idVec3 dir = lineCenter - center;
  176.  
  177.     ld[0] = idMath::Fabs( lineDir[0] );
  178.     if ( idMath::Fabs( dir[0] ) > extents[0] + ld[0] ) {
  179.         return false;
  180.     }
  181.  
  182.     ld[1] = idMath::Fabs( lineDir[1] );
  183.     if ( idMath::Fabs( dir[1] ) > extents[1] + ld[1] ) {
  184.         return false;
  185.     }
  186.  
  187.     ld[2] = idMath::Fabs( lineDir[2] );
  188.     if ( idMath::Fabs( dir[2] ) > extents[2] + ld[2] ) {
  189.         return false;
  190.     }
  191.  
  192.     idVec3 cross = lineDir.Cross( dir );
  193.  
  194.     if ( idMath::Fabs( cross[0] ) > extents[1] * ld[2] + extents[2] * ld[1] ) {
  195.         return false;
  196.     }
  197.  
  198.     if ( idMath::Fabs( cross[1] ) > extents[0] * ld[2] + extents[2] * ld[0] ) {
  199.         return false;
  200.     }
  201.  
  202.     if ( idMath::Fabs( cross[2] ) > extents[0] * ld[1] + extents[1] * ld[0] ) {
  203.         return false;
  204.     }
  205.  
  206.     return true;
  207. }
  208.  
  209. /*
  210. ============
  211. idBounds::RayIntersection
  212.  
  213.   Returns true if the ray intersects the bounds.
  214.   The ray can intersect the bounds in both directions from the start point.
  215.   If start is inside the bounds it is considered an intersection with scale = 0
  216. ============
  217. */
  218. bool idBounds::RayIntersection( const idVec3 &start, const idVec3 &dir, float &scale ) const {
  219.     int i, ax0, ax1, ax2, side, inside;
  220.     float f;
  221.     idVec3 hit;
  222.  
  223.     ax0 = -1;
  224.     inside = 0;
  225.     for ( i = 0; i < 3; i++ ) {
  226.         if ( start[i] < b[0][i] ) {
  227.             side = 0;
  228.         }
  229.         else if ( start[i] > b[1][i] ) {
  230.             side = 1;
  231.         }
  232.         else {
  233.             inside++;
  234.             continue;
  235.         }
  236.         if ( dir[i] == 0.0f ) {
  237.             continue;
  238.         }
  239.         f = ( start[i] - b[side][i] );
  240.         if ( ax0 < 0 || idMath::Fabs( f ) > idMath::Fabs( scale * dir[i] ) ) {
  241.             scale = - ( f / dir[i] );
  242.             ax0 = i;
  243.         }
  244.     }
  245.  
  246.     if ( ax0 < 0 ) {
  247.         scale = 0.0f;
  248.         // return true if the start point is inside the bounds
  249.         return ( inside == 3 );
  250.     }
  251.  
  252.     ax1 = (ax0+1)%3;
  253.     ax2 = (ax0+2)%3;
  254.     hit[ax1] = start[ax1] + scale * dir[ax1];
  255.     hit[ax2] = start[ax2] + scale * dir[ax2];
  256.  
  257.     return ( hit[ax1] >= b[0][ax1] && hit[ax1] <= b[1][ax1] &&
  258.                 hit[ax2] >= b[0][ax2] && hit[ax2] <= b[1][ax2] );
  259. }
  260.  
  261. /*
  262. ============
  263. idBounds::FromTransformedBounds
  264. ============
  265. */
  266. void idBounds::FromTransformedBounds( const idBounds &bounds, const idVec3 &origin, const idMat3 &axis ) {
  267.     int i;
  268.     idVec3 center, extents, rotatedExtents;
  269.  
  270.     center = (bounds[0] + bounds[1]) * 0.5f;
  271.     extents = bounds[1] - center;
  272.  
  273.     for ( i = 0; i < 3; i++ ) {
  274.         rotatedExtents[i] = idMath::Fabs( extents[0] * axis[0][i] ) +
  275.                             idMath::Fabs( extents[1] * axis[1][i] ) +
  276.                             idMath::Fabs( extents[2] * axis[2][i] );
  277.     }
  278.  
  279.     center = origin + center * axis;
  280.     b[0] = center - rotatedExtents;
  281.     b[1] = center + rotatedExtents;
  282. }
  283.  
  284. /*
  285. ============
  286. idBounds::FromPoints
  287.  
  288.   Most tight bounds for a point set.
  289. ============
  290. */
  291. void idBounds::FromPoints( const idVec3 *points, const int numPoints ) {
  292.     SIMDProcessor->MinMax( b[0], b[1], points, numPoints );
  293. }
  294.  
  295. /*
  296. ============
  297. idBounds::FromPointTranslation
  298.  
  299.   Most tight bounds for the translational movement of the given point.
  300. ============
  301. */
  302. void idBounds::FromPointTranslation( const idVec3 &point, const idVec3 &translation ) {
  303.     int i;
  304.  
  305.     for ( i = 0; i < 3; i++ ) {
  306.         if ( translation[i] < 0.0f ) {
  307.             b[0][i] = point[i] + translation[i];
  308.             b[1][i] = point[i];
  309.         }
  310.         else {
  311.             b[0][i] = point[i];
  312.             b[1][i] = point[i] + translation[i];
  313.         }
  314.     }
  315. }
  316.  
  317. /*
  318. ============
  319. idBounds::FromBoundsTranslation
  320.  
  321.   Most tight bounds for the translational movement of the given bounds.
  322. ============
  323. */
  324. void idBounds::FromBoundsTranslation( const idBounds &bounds, const idVec3 &origin, const idMat3 &axis, const idVec3 &translation ) {
  325.     int i;
  326.  
  327.     if ( axis.IsRotated() ) {
  328.         FromTransformedBounds( bounds, origin, axis );
  329.     }
  330.     else {
  331.         b[0] = bounds[0] + origin;
  332.         b[1] = bounds[1] + origin;
  333.     }
  334.     for ( i = 0; i < 3; i++ ) {
  335.         if ( translation[i] < 0.0f ) {
  336.             b[0][i] += translation[i];
  337.         }
  338.         else {
  339.             b[1][i] += translation[i];
  340.         }
  341.     }
  342. }
  343.  
  344. /*
  345. ================
  346. BoundsForPointRotation
  347.  
  348.   only for rotations < 180 degrees
  349. ================
  350. */
  351. idBounds BoundsForPointRotation( const idVec3 &start, const idRotation &rotation ) {
  352.     int i;
  353.     float radiusSqr;
  354.     idVec3 v1, v2;
  355.     idVec3 origin, axis, end;
  356.     idBounds bounds;
  357.  
  358.     end = start * rotation;
  359.     axis = rotation.GetVec();
  360.     origin = rotation.GetOrigin() + axis * ( axis * ( start - rotation.GetOrigin() ) );
  361.     radiusSqr = ( start - origin ).LengthSqr();
  362.     v1 = ( start - origin ).Cross( axis );
  363.     v2 = ( end - origin ).Cross( axis );
  364.  
  365.     for ( i = 0; i < 3; i++ ) {
  366.         // if the derivative changes sign along this axis during the rotation from start to end
  367.         if ( ( v1[i] > 0.0f && v2[i] < 0.0f ) || ( v1[i] < 0.0f && v2[i] > 0.0f ) ) {
  368.             if ( ( 0.5f * (start[i] + end[i]) - origin[i] ) > 0.0f ) {
  369.                 bounds[0][i] = Min( start[i], end[i] );
  370. // RAVEN BEGIN
  371.                 bounds[1][i] = origin[i];
  372.                 if( axis[i] * axis[i] < 1.0f ) {
  373.                     bounds[1][i] += idMath::Sqrt( radiusSqr * ( 1.0f - axis[i] * axis[i] ) );
  374.                 }
  375. // RAVEN END
  376.             }
  377.             else {
  378. // RAVEN BEGIN
  379.                 bounds[0][i] = origin[i];
  380.                 if( axis[i] * axis[i] < 1.0f ) {
  381.                     bounds[0][i] -= idMath::Sqrt( radiusSqr * ( 1.0f - axis[i] * axis[i] ) );
  382.                 }
  383. // RAVEN END
  384.                 bounds[1][i] = Max( start[i], end[i] );
  385.             }
  386.         }
  387.         else if ( start[i] > end[i] ) {
  388.             bounds[0][i] = end[i];
  389.             bounds[1][i] = start[i];
  390.         }
  391.         else {
  392.             bounds[0][i] = start[i];
  393.             bounds[1][i] = end[i];
  394.         }
  395.     }
  396.  
  397.     return bounds;
  398. }
  399.  
  400. /*
  401. ============
  402. idBounds::FromPointRotation
  403.  
  404.   Most tight bounds for the rotational movement of the given point.
  405. ============
  406. */
  407. void idBounds::FromPointRotation( const idVec3 &point, const idRotation &rotation ) {
  408.     float radius;
  409.  
  410.     if ( idMath::Fabs( rotation.GetAngle() ) < 180.0f ) {
  411.         (*this) = BoundsForPointRotation( point, rotation );
  412.     }
  413.     else {
  414.  
  415.         radius = ( point - rotation.GetOrigin() ).Length();
  416.  
  417.         // FIXME: these bounds are usually way larger
  418.         b[0].Set( -radius, -radius, -radius );
  419.         b[1].Set( radius, radius, radius );
  420.     }
  421. }
  422.  
  423. /*
  424. ============
  425. idBounds::FromBoundsRotation
  426.  
  427.   Most tight bounds for the rotational movement of the given bounds.
  428. ============
  429. */
  430. void idBounds::FromBoundsRotation( const idBounds &bounds, const idVec3 &origin, const idMat3 &axis, const idRotation &rotation ) {
  431.     int i;
  432.     float radius;
  433.     idVec3 point;
  434.     idBounds rBounds;
  435.  
  436.     if ( idMath::Fabs( rotation.GetAngle() ) < 180.0f ) {
  437.  
  438.         (*this) = BoundsForPointRotation( bounds[0] * axis + origin, rotation );
  439.         for ( i = 1; i < 8; i++ ) {
  440.             point[0] = bounds[(i^(i>>1))&1][0];
  441.             point[1] = bounds[(i>>1)&1][1];
  442.             point[2] = bounds[(i>>2)&1][2];
  443.             (*this) += BoundsForPointRotation( point * axis + origin, rotation );
  444.         }
  445.     }
  446.     else {
  447.  
  448.         point = (bounds[1] - bounds[0]) * 0.5f;
  449.         radius = (bounds[1] - point).Length() + (point - rotation.GetOrigin()).Length();
  450.  
  451.         // FIXME: these bounds are usually way larger
  452.         b[0].Set( -radius, -radius, -radius );
  453.         b[1].Set( radius, radius, radius );
  454.     }
  455. }
  456.  
  457. /*
  458. ============
  459. idBounds::ToPoints
  460. ============
  461. */
  462. void idBounds::ToPoints( idVec3 points[8] ) const {
  463.     for ( int i = 0; i < 8; i++ ) {
  464.         points[i][0] = b[(i^(i>>1))&1][0];
  465.         points[i][1] = b[(i>>1)&1][1];
  466.         points[i][2] = b[(i>>2)&1][2];
  467.     }
  468. }
  469.