neo/idlib/bv/Bounds.cpp

   1 /*
   2 ===========================================================================
   3
   4 Doom 3 GPL Source Code
   5 Copyright (C) 1999-2011 id Software LLC, a ZeniMax Media company.
   6
   7 This file is part of the Doom 3 GPL Source Code (?Doom 3 Source Code?).
   8
   9 Doom 3 Source Code is free software: you can redistribute it and/or modify
  10 it under the terms of the GNU General Public License as published by
  11 the Free Software Foundation, either version 3 of the License, or
  12 (at your option) any later version.
  13
  14 Doom 3 Source Code is distributed in the hope that it will be useful,
  15 but WITHOUT ANY WARRANTY; without even the implied warranty of
  16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  17 GNU General Public License for more details.
  18
  19 You should have received a copy of the GNU General Public License
  20 along with Doom 3 Source Code.  If not, see <http://www.gnu.org/licenses/>.
  21
  22 In addition, the Doom 3 Source Code is also subject to certain additional terms. You should have received a copy of these additional terms immediately following the terms and conditions of the GNU General Public License which accompanied the Doom 3 Source Code.  If not, please request a copy in writing from id Software at the address below.
  23
  24 If you have questions concerning this license or the applicable additional terms, you may contact in writing id Software LLC, c/o ZeniMax Media Inc., Suite 120, Rockville, Maryland 20850 USA.
  25
  26 ===========================================================================
  27 */
  28
  29 #include "../precompiled.h"
  30 #pragma hdrstop
  31
  32 idBounds bounds_zero( vec3_zero, vec3_zero );
  33
  34 /*
  35 ============
  36 idBounds::GetRadius
  37 ============
  38 */
  39 float idBounds::GetRadius( void ) const {
  40         int             i;
  41         float   total, b0, b1;
  42
  43         total = 0.0f;
  44         for ( i = 0; i < 3; i++ ) {
  45                 b0 = (float)idMath::Fabs( b[0][i] );
  46                 b1 = (float)idMath::Fabs( b[1][i] );
  47                 if ( b0 > b1 ) {
  48                         total += b0 * b0;
  49                 } else {
  50                         total += b1 * b1;
  51                 }
  52         }
  53         return idMath::Sqrt( total );
  54 }
  55
  56 /*
  57 ============
  58 idBounds::GetRadius
  59 ============
  60 */
  61 float idBounds::GetRadius( const idVec3 &center ) const {
  62         int             i;
  63         float   total, b0, b1;
  64
  65         total = 0.0f;
  66         for ( i = 0; i < 3; i++ ) {
  67                 b0 = (float)idMath::Fabs( center[i] - b[0][i] );
  68                 b1 = (float)idMath::Fabs( b[1][i] - center[i] );
  69                 if ( b0 > b1 ) {
  70                         total += b0 * b0;
  71                 } else {
  72                         total += b1 * b1;
  73                 }
  74         }
  75         return idMath::Sqrt( total );
  76 }
  77
  78 /*
  79 ================
  80 idBounds::PlaneDistance
  81 ================
  82 */
  83 float idBounds::PlaneDistance( const idPlane &plane ) const {
  84         idVec3 center;
  85         float d1, d2;
  86
  87         center = ( b[0] + b[1] ) * 0.5f;
  88
  89         d1 = plane.Distance( center );
  90         d2 = idMath::Fabs( ( b[1][0] - center[0] ) * plane.Normal()[0] ) +
  91                         idMath::Fabs( ( b[1][1] - center[1] ) * plane.Normal()[1] ) +
  92                                 idMath::Fabs( ( b[1][2] - center[2] ) * plane.Normal()[2] );
  93
  94         if ( d1 - d2 > 0.0f ) {
  95                 return d1 - d2;
  96         }
  97         if ( d1 + d2 < 0.0f ) {
  98                 return d1 + d2;
  99         }
 100         return 0.0f;
 101 }
 102
 103 /*
 104 ================
 105 idBounds::PlaneSide
 106 ================
 107 */
 108 int idBounds::PlaneSide( const idPlane &plane, const float epsilon ) const {
 109         idVec3 center;
 110         float d1, d2;
 111
 112         center = ( b[0] + b[1] ) * 0.5f;
 113
 114         d1 = plane.Distance( center );
 115         d2 = idMath::Fabs( ( b[1][0] - center[0] ) * plane.Normal()[0] ) +
 116                         idMath::Fabs( ( b[1][1] - center[1] ) * plane.Normal()[1] ) +
 117                                 idMath::Fabs( ( b[1][2] - center[2] ) * plane.Normal()[2] );
 118
 119         if ( d1 - d2 > epsilon ) {
 120                 return PLANESIDE_FRONT;
 121         }
 122         if ( d1 + d2 < -epsilon ) {
 123                 return PLANESIDE_BACK;
 124         }
 125         return PLANESIDE_CROSS;
 126 }
 127
 128 /*
 129 ============
 130 idBounds::LineIntersection
 131
 132   Returns true if the line intersects the bounds between the start and end point.
 133 ============
 134 */
 135 bool idBounds::LineIntersection( const idVec3 &start, const idVec3 &end ) const {
 136     float ld[3];
 137         idVec3 center = ( b[0] + b[1] ) * 0.5f;
 138         idVec3 extents = b[1] - center;
 139     idVec3 lineDir = 0.5f * ( end - start );
 140     idVec3 lineCenter = start + lineDir;
 141     idVec3 dir = lineCenter - center;
 142
 143     ld[0] = idMath::Fabs( lineDir[0] );
 144         if ( idMath::Fabs( dir[0] ) > extents[0] + ld[0] ) {
 145         return false;
 146         }
 147
 148     ld[1] = idMath::Fabs( lineDir[1] );
 149         if ( idMath::Fabs( dir[1] ) > extents[1] + ld[1] ) {
 150         return false;
 151         }
 152
 153     ld[2] = idMath::Fabs( lineDir[2] );
 154         if ( idMath::Fabs( dir[2] ) > extents[2] + ld[2] ) {
 155         return false;
 156         }
 157
 158     idVec3 cross = lineDir.Cross( dir );
 159
 160         if ( idMath::Fabs( cross[0] ) > extents[1] * ld[2] + extents[2] * ld[1] ) {
 161         return false;
 162         }
 163
 164         if ( idMath::Fabs( cross[1] ) > extents[0] * ld[2] + extents[2] * ld[0] ) {
 165         return false;
 166         }
 167
 168         if ( idMath::Fabs( cross[2] ) > extents[0] * ld[1] + extents[1] * ld[0] ) {
 169         return false;
 170         }
 171
 172     return true;
 173 }
 174
 175 /*
 176 ============
 177 idBounds::RayIntersection
 178
 179   Returns true if the ray intersects the bounds.
 180   The ray can intersect the bounds in both directions from the start point.
 181   If start is inside the bounds it is considered an intersection with scale = 0
 182 ============
 183 */
 184 bool idBounds::RayIntersection( const idVec3 &start, const idVec3 &dir, float &scale ) const {
 185         int i, ax0, ax1, ax2, side, inside;
 186         float f;
 187         idVec3 hit;
 188
 189         ax0 = -1;
 190         inside = 0;
 191         for ( i = 0; i < 3; i++ ) {
 192                 if ( start[i] < b[0][i] ) {
 193                         side = 0;
 194                 }
 195                 else if ( start[i] > b[1][i] ) {
 196                         side = 1;
 197                 }
 198                 else {
 199                         inside++;
 200                         continue;
 201                 }
 202                 if ( dir[i] == 0.0f ) {
 203                         continue;
 204                 }
 205                 f = ( start[i] - b[side][i] );
 206                 if ( ax0 < 0 || idMath::Fabs( f ) > idMath::Fabs( scale * dir[i] ) ) {
 207                         scale = - ( f / dir[i] );
 208                         ax0 = i;
 209                 }
 210         }
 211
 212         if ( ax0 < 0 ) {
 213                 scale = 0.0f;
 214                 // return true if the start point is inside the bounds
 215                 return ( inside == 3 );
 216         }
 217
 218         ax1 = (ax0+1)%3;
 219         ax2 = (ax0+2)%3;
 220         hit[ax1] = start[ax1] + scale * dir[ax1];
 221         hit[ax2] = start[ax2] + scale * dir[ax2];
 222
 223         return ( hit[ax1] >= b[0][ax1] && hit[ax1] <= b[1][ax1] &&
 224                                 hit[ax2] >= b[0][ax2] && hit[ax2] <= b[1][ax2] );
 225 }
 226
 227 /*
 228 ============
 229 idBounds::FromTransformedBounds
 230 ============
 231 */
 232 void idBounds::FromTransformedBounds( const idBounds &bounds, const idVec3 &origin, const idMat3 &axis ) {
 233         int i;
 234         idVec3 center, extents, rotatedExtents;
 235
 236         center = (bounds[0] + bounds[1]) * 0.5f;
 237         extents = bounds[1] - center;
 238
 239         for ( i = 0; i < 3; i++ ) {
 240                 rotatedExtents[i] = idMath::Fabs( extents[0] * axis[0][i] ) +
 241                                                         idMath::Fabs( extents[1] * axis[1][i] ) +
 242                                                         idMath::Fabs( extents[2] * axis[2][i] );
 243         }
 244
 245         center = origin + center * axis;
 246         b[0] = center - rotatedExtents;
 247         b[1] = center + rotatedExtents;
 248 }
 249
 250 /*
 251 ============
 252 idBounds::FromPoints
 253
 254   Most tight bounds for a point set.
 255 ============
 256 */
 257 void idBounds::FromPoints( const idVec3 *points, const int numPoints ) {
 258         SIMDProcessor->MinMax( b[0], b[1], points, numPoints );
 259 }
 260
 261 /*
 262 ============
 263 idBounds::FromPointTranslation
 264
 265   Most tight bounds for the translational movement of the given point.
 266 ============
 267 */
 268 void idBounds::FromPointTranslation( const idVec3 &point, const idVec3 &translation ) {
 269         int i;
 270
 271         for ( i = 0; i < 3; i++ ) {
 272                 if ( translation[i] < 0.0f ) {
 273                         b[0][i] = point[i] + translation[i];
 274                         b[1][i] = point[i];
 275                 }
 276                 else {
 277                         b[0][i] = point[i];
 278                         b[1][i] = point[i] + translation[i];
 279                 }
 280         }
 281 }
 282
 283 /*
 284 ============
 285 idBounds::FromBoundsTranslation
 286
 287   Most tight bounds for the translational movement of the given bounds.
 288 ============
 289 */
 290 void idBounds::FromBoundsTranslation( const idBounds &bounds, const idVec3 &origin, const idMat3 &axis, const idVec3 &translation ) {
 291         int i;
 292
 293         if ( axis.IsRotated() ) {
 294                 FromTransformedBounds( bounds, origin, axis );
 295         }
 296         else {
 297                 b[0] = bounds[0] + origin;
 298                 b[1] = bounds[1] + origin;
 299         }
 300         for ( i = 0; i < 3; i++ ) {
 301                 if ( translation[i] < 0.0f ) {
 302                         b[0][i] += translation[i];
 303                 }
 304                 else {
 305                         b[1][i] += translation[i];
 306                 }
 307         }
 308 }
 309
 310 /*
 311 ================
 312 BoundsForPointRotation
 313
 314   only for rotations < 180 degrees
 315 ================
 316 */
 317 idBounds BoundsForPointRotation( const idVec3 &start, const idRotation &rotation ) {
 318         int i;
 319         float radiusSqr;
 320         idVec3 v1, v2;
 321         idVec3 origin, axis, end;
 322         idBounds bounds;
 323
 324         end = start * rotation;
 325         axis = rotation.GetVec();
 326         origin = rotation.GetOrigin() + axis * ( axis * ( start - rotation.GetOrigin() ) );
 327         radiusSqr = ( start - origin ).LengthSqr();
 328         v1 = ( start - origin ).Cross( axis );
 329         v2 = ( end - origin ).Cross( axis );
 330
 331         for ( i = 0; i < 3; i++ ) {
 332                 // if the derivative changes sign along this axis during the rotation from start to end
 333                 if ( ( v1[i] > 0.0f && v2[i] < 0.0f ) || ( v1[i] < 0.0f && v2[i] > 0.0f ) ) {
 334                         if ( ( 0.5f * (start[i] + end[i]) - origin[i] ) > 0.0f ) {
 335                                 bounds[0][i] = Min( start[i], end[i] );
 336                                 bounds[1][i] = origin[i] + idMath::Sqrt( radiusSqr * ( 1.0f - axis[i] * axis[i] ) );
 337                         }
 338                         else {
 339                                 bounds[0][i] = origin[i] - idMath::Sqrt( radiusSqr * ( 1.0f - axis[i] * axis[i] ) );
 340                                 bounds[1][i] = Max( start[i], end[i] );
 341                         }
 342                 }
 343                 else if ( start[i] > end[i] ) {
 344                         bounds[0][i] = end[i];
 345                         bounds[1][i] = start[i];
 346                 }
 347                 else {
 348                         bounds[0][i] = start[i];
 349                         bounds[1][i] = end[i];
 350                 }
 351         }
 352
 353         return bounds;
 354 }
 355
 356 /*
 357 ============
 358 idBounds::FromPointRotation
 359
 360   Most tight bounds for the rotational movement of the given point.
 361 ============
 362 */
 363 void idBounds::FromPointRotation( const idVec3 &point, const idRotation &rotation ) {
 364         float radius;
 365
 366         if ( idMath::Fabs( rotation.GetAngle() ) < 180.0f ) {
 367                 (*this) = BoundsForPointRotation( point, rotation );
 368         }
 369         else {
 370
 371                 radius = ( point - rotation.GetOrigin() ).Length();
 372
 373                 // FIXME: these bounds are usually way larger
 374                 b[0].Set( -radius, -radius, -radius );
 375                 b[1].Set( radius, radius, radius );
 376         }
 377 }
 378
 379 /*
 380 ============
 381 idBounds::FromBoundsRotation
 382
 383   Most tight bounds for the rotational movement of the given bounds.
 384 ============
 385 */
 386 void idBounds::FromBoundsRotation( const idBounds &bounds, const idVec3 &origin, const idMat3 &axis, const idRotation &rotation ) {
 387         int i;
 388         float radius;
 389         idVec3 point;
 390         idBounds rBounds;
 391
 392         if ( idMath::Fabs( rotation.GetAngle() ) < 180.0f ) {
 393
 394                 (*this) = BoundsForPointRotation( bounds[0] * axis + origin, rotation );
 395                 for ( i = 1; i < 8; i++ ) {
 396                         point[0] = bounds[(i^(i>>1))&1][0];
 397                         point[1] = bounds[(i>>1)&1][1];
 398                         point[2] = bounds[(i>>2)&1][2];
 399                         (*this) += BoundsForPointRotation( point * axis + origin, rotation );
 400                 }
 401         }
 402         else {
 403
 404                 point = (bounds[1] - bounds[0]) * 0.5f;
 405                 radius = (bounds[1] - point).Length() + (point - rotation.GetOrigin()).Length();
 406
 407                 // FIXME: these bounds are usually way larger
 408                 b[0].Set( -radius, -radius, -radius );
 409                 b[1].Set( radius, radius, radius );
 410         }
 411 }
 412
 413 /*
 414 ============
 415 idBounds::ToPoints
 416 ============
 417 */
 418 void idBounds::ToPoints( idVec3 points[8] ) const {
 419         for ( int i = 0; i < 8; i++ ) {
 420                 points[i][0] = b[(i^(i>>1))&1][0];
 421                 points[i][1] = b[(i>>1)&1][1];
 422                 points[i][2] = b[(i>>2)&1][2];
 423         }
 424 }