neo/idlib/bv/Bounds.h

   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 #ifndef __BV_BOUNDS_H__
  30 #define __BV_BOUNDS_H__
  31
  32 /*
  33 ===============================================================================
  34
  35         Axis Aligned Bounding Box
  36
  37 ===============================================================================
  38 */
  39
  40 class idBounds {
  41 public:
  42                                         idBounds( void );
  43                                         explicit idBounds( const idVec3 &mins, const idVec3 &maxs );
  44                                         explicit idBounds( const idVec3 &point );
  45
  46         const idVec3 &  operator[]( const int index ) const;
  47         idVec3 &                operator[]( const int index );
  48         idBounds                operator+( const idVec3 &t ) const;                             // returns translated bounds
  49         idBounds &              operator+=( const idVec3 &t );                                  // translate the bounds
  50         idBounds                operator*( const idMat3 &r ) const;                             // returns rotated bounds
  51         idBounds &              operator*=( const idMat3 &r );                                  // rotate the bounds
  52         idBounds                operator+( const idBounds &a ) const;
  53         idBounds &              operator+=( const idBounds &a );
  54         idBounds                operator-( const idBounds &a ) const;
  55         idBounds &              operator-=( const idBounds &a );
  56
  57         bool                    Compare( const idBounds &a ) const;                                                     // exact compare, no epsilon
  58         bool                    Compare( const idBounds &a, const float epsilon ) const;        // compare with epsilon
  59         bool                    operator==(     const idBounds &a ) const;                                              // exact compare, no epsilon
  60         bool                    operator!=(     const idBounds &a ) const;                                              // exact compare, no epsilon
  61
  62         void                    Clear( void );                                                                  // inside out bounds
  63         void                    Zero( void );                                                                   // single point at origin
  64
  65         idVec3                  GetCenter( void ) const;                                                // returns center of bounds
  66         float                   GetRadius( void ) const;                                                // returns the radius relative to the bounds origin
  67         float                   GetRadius( const idVec3 &center ) const;                // returns the radius relative to the given center
  68         float                   GetVolume( void ) const;                                                // returns the volume of the bounds
  69         bool                    IsCleared( void ) const;                                                // returns true if bounds are inside out
  70
  71         bool                    AddPoint( const idVec3 &v );                                    // add the point, returns true if the bounds expanded
  72         bool                    AddBounds( const idBounds &a );                                 // add the bounds, returns true if the bounds expanded
  73         idBounds                Intersect( const idBounds &a ) const;                   // return intersection of this bounds with the given bounds
  74         idBounds &              IntersectSelf( const idBounds &a );                             // intersect this bounds with the given bounds
  75         idBounds                Expand( const float d ) const;                                  // return bounds expanded in all directions with the given value
  76         idBounds &              ExpandSelf( const float d );                                    // expand bounds in all directions with the given value
  77         idBounds                Translate( const idVec3 &translation ) const;   // return translated bounds
  78         idBounds &              TranslateSelf( const idVec3 &translation );             // translate this bounds
  79         idBounds                Rotate( const idMat3 &rotation ) const;                 // return rotated bounds
  80         idBounds &              RotateSelf( const idMat3 &rotation );                   // rotate this bounds
  81
  82         float                   PlaneDistance( const idPlane &plane ) const;
  83         int                             PlaneSide( const idPlane &plane, const float epsilon = ON_EPSILON ) const;
  84
  85         bool                    ContainsPoint( const idVec3 &p ) const;                 // includes touching
  86         bool                    IntersectsBounds( const idBounds &a ) const;    // includes touching
  87         bool                    LineIntersection( const idVec3 &start, const idVec3 &end ) const;
  88                                         // intersection point is start + dir * scale
  89         bool                    RayIntersection( const idVec3 &start, const idVec3 &dir, float &scale ) const;
  90
  91                                         // most tight bounds for the given transformed bounds
  92         void                    FromTransformedBounds( const idBounds &bounds, const idVec3 &origin, const idMat3 &axis );
  93                                         // most tight bounds for a point set
  94         void                    FromPoints( const idVec3 *points, const int numPoints );
  95                                         // most tight bounds for a translation
  96         void                    FromPointTranslation( const idVec3 &point, const idVec3 &translation );
  97         void                    FromBoundsTranslation( const idBounds &bounds, const idVec3 &origin, const idMat3 &axis, const idVec3 &translation );
  98                                         // most tight bounds for a rotation
  99         void                    FromPointRotation( const idVec3 &point, const idRotation &rotation );
 100         void                    FromBoundsRotation( const idBounds &bounds, const idVec3 &origin, const idMat3 &axis, const idRotation &rotation );
 101
 102         void                    ToPoints( idVec3 points[8] ) const;
 103         idSphere                ToSphere( void ) const;
 104
 105         void                    AxisProjection( const idVec3 &dir, float &min, float &max ) const;
 106         void                    AxisProjection( const idVec3 &origin, const idMat3 &axis, const idVec3 &dir, float &min, float &max ) const;
 107
 108 private:
 109         idVec3                  b[2];
 110 };
 111
 112 extern idBounds bounds_zero;
 113
 114 ID_INLINE idBounds::idBounds( void ) {
 115 }
 116
 117 ID_INLINE idBounds::idBounds( const idVec3 &mins, const idVec3 &maxs ) {
 118         b[0] = mins;
 119         b[1] = maxs;
 120 }
 121
 122 ID_INLINE idBounds::idBounds( const idVec3 &point ) {
 123         b[0] = point;
 124         b[1] = point;
 125 }
 126
 127 ID_INLINE const idVec3 &idBounds::operator[]( const int index ) const {
 128         return b[index];
 129 }
 130
 131 ID_INLINE idVec3 &idBounds::operator[]( const int index ) {
 132         return b[index];
 133 }
 134
 135 ID_INLINE idBounds idBounds::operator+( const idVec3 &t ) const {
 136         return idBounds( b[0] + t, b[1] + t );
 137 }
 138
 139 ID_INLINE idBounds &idBounds::operator+=( const idVec3 &t ) {
 140         b[0] += t;
 141         b[1] += t;
 142         return *this;
 143 }
 144
 145 ID_INLINE idBounds idBounds::operator*( const idMat3 &r ) const {
 146         idBounds bounds;
 147         bounds.FromTransformedBounds( *this, vec3_origin, r );
 148         return bounds;
 149 }
 150
 151 ID_INLINE idBounds &idBounds::operator*=( const idMat3 &r ) {
 152         this->FromTransformedBounds( *this, vec3_origin, r );
 153         return *this;
 154 }
 155
 156 ID_INLINE idBounds idBounds::operator+( const idBounds &a ) const {
 157         idBounds newBounds;
 158         newBounds = *this;
 159         newBounds.AddBounds( a );
 160         return newBounds;
 161 }
 162
 163 ID_INLINE idBounds &idBounds::operator+=( const idBounds &a ) {
 164         idBounds::AddBounds( a );
 165         return *this;
 166 }
 167
 168 ID_INLINE idBounds idBounds::operator-( const idBounds &a ) const {
 169         assert( b[1][0] - b[0][0] > a.b[1][0] - a.b[0][0] &&
 170                                 b[1][1] - b[0][1] > a.b[1][1] - a.b[0][1] &&
 171                                         b[1][2] - b[0][2] > a.b[1][2] - a.b[0][2] );
 172         return idBounds( idVec3( b[0][0] + a.b[1][0], b[0][1] + a.b[1][1], b[0][2] + a.b[1][2] ),
 173                                         idVec3( b[1][0] + a.b[0][0], b[1][1] + a.b[0][1], b[1][2] + a.b[0][2] ) );
 174 }
 175
 176 ID_INLINE idBounds &idBounds::operator-=( const idBounds &a ) {
 177         assert( b[1][0] - b[0][0] > a.b[1][0] - a.b[0][0] &&
 178                                 b[1][1] - b[0][1] > a.b[1][1] - a.b[0][1] &&
 179                                         b[1][2] - b[0][2] > a.b[1][2] - a.b[0][2] );
 180         b[0] += a.b[1];
 181         b[1] += a.b[0];
 182         return *this;
 183 }
 184
 185 ID_INLINE bool idBounds::Compare( const idBounds &a ) const {
 186         return ( b[0].Compare( a.b[0] ) && b[1].Compare( a.b[1] ) );
 187 }
 188
 189 ID_INLINE bool idBounds::Compare( const idBounds &a, const float epsilon ) const {
 190         return ( b[0].Compare( a.b[0], epsilon ) && b[1].Compare( a.b[1], epsilon ) );
 191 }
 192
 193 ID_INLINE bool idBounds::operator==( const idBounds &a ) const {
 194         return Compare( a );
 195 }
 196
 197 ID_INLINE bool idBounds::operator!=( const idBounds &a ) const {
 198         return !Compare( a );
 199 }
 200
 201 ID_INLINE void idBounds::Clear( void ) {
 202         b[0][0] = b[0][1] = b[0][2] = idMath::INFINITY;
 203         b[1][0] = b[1][1] = b[1][2] = -idMath::INFINITY;
 204 }
 205
 206 ID_INLINE void idBounds::Zero( void ) {
 207         b[0][0] = b[0][1] = b[0][2] =
 208         b[1][0] = b[1][1] = b[1][2] = 0;
 209 }
 210
 211 ID_INLINE idVec3 idBounds::GetCenter( void ) const {
 212         return idVec3( ( b[1][0] + b[0][0] ) * 0.5f, ( b[1][1] + b[0][1] ) * 0.5f, ( b[1][2] + b[0][2] ) * 0.5f );
 213 }
 214
 215 ID_INLINE float idBounds::GetVolume( void ) const {
 216         if ( b[0][0] >= b[1][0] || b[0][1] >= b[1][1] || b[0][2] >= b[1][2] ) {
 217                 return 0.0f;
 218         }
 219         return ( ( b[1][0] - b[0][0] ) * ( b[1][1] - b[0][1] ) * ( b[1][2] - b[0][2] ) );
 220 }
 221
 222 ID_INLINE bool idBounds::IsCleared( void ) const {
 223         return b[0][0] > b[1][0];
 224 }
 225
 226 ID_INLINE bool idBounds::AddPoint( const idVec3 &v ) {
 227         bool expanded = false;
 228         if ( v[0] < b[0][0]) {
 229                 b[0][0] = v[0];
 230                 expanded = true;
 231         }
 232         if ( v[0] > b[1][0]) {
 233                 b[1][0] = v[0];
 234                 expanded = true;
 235         }
 236         if ( v[1] < b[0][1] ) {
 237                 b[0][1] = v[1];
 238                 expanded = true;
 239         }
 240         if ( v[1] > b[1][1]) {
 241                 b[1][1] = v[1];
 242                 expanded = true;
 243         }
 244         if ( v[2] < b[0][2] ) {
 245                 b[0][2] = v[2];
 246                 expanded = true;
 247         }
 248         if ( v[2] > b[1][2]) {
 249                 b[1][2] = v[2];
 250                 expanded = true;
 251         }
 252         return expanded;
 253 }
 254
 255 ID_INLINE bool idBounds::AddBounds( const idBounds &a ) {
 256         bool expanded = false;
 257         if ( a.b[0][0] < b[0][0] ) {
 258                 b[0][0] = a.b[0][0];
 259                 expanded = true;
 260         }
 261         if ( a.b[0][1] < b[0][1] ) {
 262                 b[0][1] = a.b[0][1];
 263                 expanded = true;
 264         }
 265         if ( a.b[0][2] < b[0][2] ) {
 266                 b[0][2] = a.b[0][2];
 267                 expanded = true;
 268         }
 269         if ( a.b[1][0] > b[1][0] ) {
 270                 b[1][0] = a.b[1][0];
 271                 expanded = true;
 272         }
 273         if ( a.b[1][1] > b[1][1] ) {
 274                 b[1][1] = a.b[1][1];
 275                 expanded = true;
 276         }
 277         if ( a.b[1][2] > b[1][2] ) {
 278                 b[1][2] = a.b[1][2];
 279                 expanded = true;
 280         }
 281         return expanded;
 282 }
 283
 284 ID_INLINE idBounds idBounds::Intersect( const idBounds &a ) const {
 285         idBounds n;
 286         n.b[0][0] = ( a.b[0][0] > b[0][0] ) ? a.b[0][0] : b[0][0];
 287         n.b[0][1] = ( a.b[0][1] > b[0][1] ) ? a.b[0][1] : b[0][1];
 288         n.b[0][2] = ( a.b[0][2] > b[0][2] ) ? a.b[0][2] : b[0][2];
 289         n.b[1][0] = ( a.b[1][0] < b[1][0] ) ? a.b[1][0] : b[1][0];
 290         n.b[1][1] = ( a.b[1][1] < b[1][1] ) ? a.b[1][1] : b[1][1];
 291         n.b[1][2] = ( a.b[1][2] < b[1][2] ) ? a.b[1][2] : b[1][2];
 292         return n;
 293 }
 294
 295 ID_INLINE idBounds &idBounds::IntersectSelf( const idBounds &a ) {
 296         if ( a.b[0][0] > b[0][0] ) {
 297                 b[0][0] = a.b[0][0];
 298         }
 299         if ( a.b[0][1] > b[0][1] ) {
 300                 b[0][1] = a.b[0][1];
 301         }
 302         if ( a.b[0][2] > b[0][2] ) {
 303                 b[0][2] = a.b[0][2];
 304         }
 305         if ( a.b[1][0] < b[1][0] ) {
 306                 b[1][0] = a.b[1][0];
 307         }
 308         if ( a.b[1][1] < b[1][1] ) {
 309                 b[1][1] = a.b[1][1];
 310         }
 311         if ( a.b[1][2] < b[1][2] ) {
 312                 b[1][2] = a.b[1][2];
 313         }
 314         return *this;
 315 }
 316
 317 ID_INLINE idBounds idBounds::Expand( const float d ) const {
 318         return idBounds( idVec3( b[0][0] - d, b[0][1] - d, b[0][2] - d ),
 319                                                 idVec3( b[1][0] + d, b[1][1] + d, b[1][2] + d ) );
 320 }
 321
 322 ID_INLINE idBounds &idBounds::ExpandSelf( const float d ) {
 323         b[0][0] -= d;
 324         b[0][1] -= d;
 325         b[0][2] -= d;
 326         b[1][0] += d;
 327         b[1][1] += d;
 328         b[1][2] += d;
 329         return *this;
 330 }
 331
 332 ID_INLINE idBounds idBounds::Translate( const idVec3 &translation ) const {
 333         return idBounds( b[0] + translation, b[1] + translation );
 334 }
 335
 336 ID_INLINE idBounds &idBounds::TranslateSelf( const idVec3 &translation ) {
 337         b[0] += translation;
 338         b[1] += translation;
 339         return *this;
 340 }
 341
 342 ID_INLINE idBounds idBounds::Rotate( const idMat3 &rotation ) const {
 343         idBounds bounds;
 344         bounds.FromTransformedBounds( *this, vec3_origin, rotation );
 345         return bounds;
 346 }
 347
 348 ID_INLINE idBounds &idBounds::RotateSelf( const idMat3 &rotation ) {
 349         FromTransformedBounds( *this, vec3_origin, rotation );
 350         return *this;
 351 }
 352
 353 ID_INLINE bool idBounds::ContainsPoint( const idVec3 &p ) const {
 354         if ( p[0] < b[0][0] || p[1] < b[0][1] || p[2] < b[0][2]
 355                 || p[0] > b[1][0] || p[1] > b[1][1] || p[2] > b[1][2] ) {
 356                 return false;
 357         }
 358         return true;
 359 }
 360
 361 ID_INLINE bool idBounds::IntersectsBounds( const idBounds &a ) const {
 362         if ( a.b[1][0] < b[0][0] || a.b[1][1] < b[0][1] || a.b[1][2] < b[0][2]
 363                 || a.b[0][0] > b[1][0] || a.b[0][1] > b[1][1] || a.b[0][2] > b[1][2] ) {
 364                 return false;
 365         }
 366         return true;
 367 }
 368
 369 ID_INLINE idSphere idBounds::ToSphere( void ) const {
 370         idSphere sphere;
 371         sphere.SetOrigin( ( b[0] + b[1] ) * 0.5f );
 372         sphere.SetRadius( ( b[1] - sphere.GetOrigin() ).Length() );
 373         return sphere;
 374 }
 375
 376 ID_INLINE void idBounds::AxisProjection( const idVec3 &dir, float &min, float &max ) const {
 377         float d1, d2;
 378         idVec3 center, extents;
 379
 380         center = ( b[0] + b[1] ) * 0.5f;
 381         extents = b[1] - center;
 382
 383         d1 = dir * center;
 384         d2 = idMath::Fabs( extents[0] * dir[0] ) +
 385                         idMath::Fabs( extents[1] * dir[1] ) +
 386                                 idMath::Fabs( extents[2] * dir[2] );
 387
 388         min = d1 - d2;
 389         max = d1 + d2;
 390 }
 391
 392 ID_INLINE void idBounds::AxisProjection( const idVec3 &origin, const idMat3 &axis, const idVec3 &dir, float &min, float &max ) const {
 393         float d1, d2;
 394         idVec3 center, extents;
 395
 396         center = ( b[0] + b[1] ) * 0.5f;
 397         extents = b[1] - center;
 398         center = origin + center * axis;
 399
 400         d1 = dir * center;
 401         d2 = idMath::Fabs( extents[0] * ( dir * axis[0] ) ) +
 402                         idMath::Fabs( extents[1] * ( dir * axis[1] ) ) +
 403                                 idMath::Fabs( extents[2] * ( dir * axis[2] ) );
 404
 405         min = d1 - d2;
 406         max = d1 + d2;
 407 }
 408
 409 #endif /* !__BV_BOUNDS_H__ */