Libs/Math3D/BoundingBox.cpp

   1 /*
   2 Cafu Engine, http://www.cafu.de/
   3 Copyright (c) Carsten Fuchs and other contributors.
   4 This project is licensed under the terms of the MIT license.
   5 */
   6
   7 /********************/
   8 /*** Bounding Box ***/
   9 /********************/
  10
  11 #include "BoundingBox.hpp"
  12
  13
  14 // This ctor is required for example in order to be able to put BoundingBox3Ts into ArrayTs etc.
  15 template<class T> BoundingBox3T<T>::BoundingBox3T()
  16 {
  17     const T MaxVal=std::numeric_limits<T>::max();
  18
  19     Min=Vector3T<T>( MaxVal,  MaxVal,  MaxVal);
  20     Max=Vector3T<T>(-MaxVal, -MaxVal, -MaxVal);
  21
  22     assert(!IsInited());
  23 }
  24
  25
  26 template<class T> BoundingBox3T<T>::BoundingBox3T(const Vector3T<T>& A)
  27     : Min(A),
  28       Max(A)
  29 {
  30     assert(IsInited());
  31 }
  32
  33
  34 template<class T> BoundingBox3T<T>::BoundingBox3T(const Vector3T<T>& A, const Vector3T<T>& B)
  35     : Min(A),
  36       Max(A)
  37 {
  38     Insert(B);
  39
  40     assert(IsInited());
  41 }
  42
  43
  44 template<class T> BoundingBox3T<T>::BoundingBox3T(const ArrayT< Vector3T<T> >& A)
  45 {
  46     const T MaxVal=std::numeric_limits<T>::max();
  47
  48     Min=Vector3T<T>( MaxVal,  MaxVal,  MaxVal);
  49     Max=Vector3T<T>(-MaxVal, -MaxVal, -MaxVal);
  50
  51     assert(!IsInited());
  52
  53     for (unsigned long VertexNr=0; VertexNr<A.Size(); VertexNr++)
  54         Insert(A[VertexNr]);
  55 }
  56
  57
  58 template<class T> bool BoundingBox3T<T>::IsValid() const
  59 {
  60     const T MaxVal=std::numeric_limits<T>::max();
  61
  62     // Uninitialized bounding-boxes are valid.
  63     if (Min==Vector3T<T>( MaxVal,  MaxVal,  MaxVal) &&
  64         Max==Vector3T<T>(-MaxVal, -MaxVal, -MaxVal)) return true;
  65
  66     // Properly initialized bounding-boxes must have a non-negative volume.
  67     return Min.x<=Max.x && Min.y<=Max.y && Min.z<=Max.z;
  68 }
  69
  70
  71 template<class T> bool BoundingBox3T<T>::IsInited() const
  72 {
  73     assert(IsValid());
  74
  75     return Min.x<=Max.x;
  76 }
  77
  78
  79 template<class T> void BoundingBox3T<T>::Insert(const Vector3T<T>& A)
  80 {
  81     if (A.x<Min.x) Min.x=A.x;
  82     if (A.y<Min.y) Min.y=A.y;
  83     if (A.z<Min.z) Min.z=A.z;
  84
  85     if (A.x>Max.x) Max.x=A.x;
  86     if (A.y>Max.y) Max.y=A.y;
  87     if (A.z>Max.z) Max.z=A.z;
  88
  89     assert(IsInited());
  90 }
  91
  92
  93 template<class T> void BoundingBox3T<T>::Insert(const ArrayT< Vector3T<T> >& A)
  94 {
  95     for (unsigned long VertexNr=0; VertexNr<A.Size(); VertexNr++)
  96         Insert(A[VertexNr]);
  97 }
  98
  99
 100 template<class T> void BoundingBox3T<T>::Insert(const BoundingBox3T<T>& BB)
 101 {
 102     assert(BB.IsInited());
 103
 104     Insert(BB.Min);
 105     Insert(BB.Max);
 106
 107     assert(IsInited());
 108 }
 109
 110
 111 template<class T> void BoundingBox3T<T>::InsertValid(const BoundingBox3T<T>& BB)
 112 {
 113     if (!BB.IsInited()) return;
 114
 115     Insert(BB.Min);
 116     Insert(BB.Max);
 117
 118     assert(IsInited());
 119 }
 120
 121
 122 template<class T> BoundingBox3T<T> BoundingBox3T<T>::GetOverallTranslationBox(const Vector3T<T>& Start, const Vector3T<T>& End) const
 123 {
 124     assert(IsInited());
 125
 126     BoundingBox3T<T> ResultBB(*this);
 127
 128     // Move the ResultBB to the Start point.
 129     ResultBB.Min+=Start;
 130     ResultBB.Max+=Start;
 131
 132     // Insert the corresponding points near End.
 133     ResultBB.Insert(Min+End);
 134     ResultBB.Insert(Max+End);
 135
 136     return ResultBB;
 137 }
 138
 139
 140 template<class T> bool BoundingBox3T<T>::Contains(const Vector3T<T>& A) const
 141 {
 142     assert(IsInited());
 143
 144     return A.x>Min.x && A.x<Max.x &&
 145            A.y>Min.y && A.y<Max.y &&
 146            A.z>Min.z && A.z<Max.z;
 147 }
 148
 149
 150 template<class T> bool BoundingBox3T<T>::Intersects(const BoundingBox3T<T>& BB) const
 151 {
 152     assert(IsInited());
 153     assert(BB.IsInited());
 154
 155     // This expression can easily be considered and verified in 2D on a sheet of paper!
 156     return Min.x<BB.Max.x && Max.x>BB.Min.x &&
 157            Min.y<BB.Max.y && Max.y>BB.Min.y &&
 158            Min.z<BB.Max.z && Max.z>BB.Min.z;
 159 }
 160
 161
 162 template<class T> bool BoundingBox3T<T>::IntersectsOrTouches(const BoundingBox3T<T>& BB) const
 163 {
 164     assert(IsInited());
 165     assert(BB.IsInited());
 166
 167     // This expression can easily be considered and verified in 2D on a sheet of paper!
 168     return Min.x<=BB.Max.x && Max.x>=BB.Min.x &&
 169            Min.y<=BB.Max.y && Max.y>=BB.Min.y &&
 170            Min.z<=BB.Max.z && Max.z>=BB.Min.z;
 171 }
 172
 173
 174 template<class T> typename BoundingBox3T<T>::SideT BoundingBox3T<T>::WhatSide(const Plane3T<T>& P, const T Epsilon) const
 175 {
 176     assert(IsInited());
 177
 178     Vector3T<T> VertNear;
 179     Vector3T<T> VertFar;
 180
 181     // We can determine the vertex that is nearest and the vertex that is farthest
 182     // from P by evaluating the sign of the components of the normal vector of P.
 183     if (P.Normal.x>0)
 184     {
 185         VertNear.x=Min.x;
 186         VertFar.x =Max.x;
 187     }
 188     else
 189     {
 190         VertNear.x=Max.x;
 191         VertFar.x =Min.x;
 192     }
 193
 194     if (P.Normal.y>0)
 195     {
 196         VertNear.y=Min.y;
 197         VertFar.y =Max.y;
 198     }
 199     else
 200     {
 201         VertNear.y=Max.y;
 202         VertFar.y =Min.y;
 203     }
 204
 205     if (P.Normal.z>0)
 206     {
 207         VertNear.z=Min.z;
 208         VertFar.z =Max.z;
 209     }
 210     else
 211     {
 212         VertNear.z=Max.z;
 213         VertFar.z =Min.z;
 214     }
 215
 216     if (P.GetDistance(VertNear)>= Epsilon) return Front;
 217     if (P.GetDistance(VertFar )<=-Epsilon) return Back;
 218
 219     return Both;
 220 }
 221
 222
 223 template<class T> typename BoundingBox3T<T>::SideT BoundingBox3T<T>::WhatSide_OLD(const Plane3T<T>& P, const T Epsilon) const
 224 {
 225     assert(IsInited());
 226
 227 #if 1
 228     const Vector3T<T> Center=(Min+Max)*0.5f;
 229     const T           DistC =P.GetDistance(Center);
 230     const T           Dist2 =fabs((Max.x-Center.x)*P.Normal.x) +
 231                              fabs((Max.y-Center.y)*P.Normal.y) +
 232                              fabs((Max.z-Center.z)*P.Normal.z);
 233
 234     // Dist2 bedeutet:
 235     // "Wie weit muß ich eine Ebene, die den Normalenvektor P.Normal hat und Center enthält, parallel verschieben
 236     //  (entlang ihres Normalvektors), um zu der in dieser Richtung liegenden äußersten Ecke der BB zu gelangen?"
 237     if (DistC-Dist2>= Epsilon) return Front;
 238     if (DistC+Dist2<=-Epsilon) return Back;
 239
 240     return Both;
 241 #else
 242     Vector3T<T> VertBB[8]={ Min,                              Vector3T<T>(Min.x, Min.y, Max.z),
 243                             Vector3T<T>(Min.x, Max.y, Min.z), Vector3T<T>(Min.x, Max.y, Max.z),
 244                             Vector3T<T>(Max.x, Min.y, Min.z), Vector3T<T>(Max.x, Min.y, Max.z),
 245                             Vector3T<T>(Max.x, Max.y, Min.z), Max };
 246
 247     int VertFront=0;
 248     int VertBack =0;
 249
 250     for (unsigned long Nr=0; Nr<8; Nr++)
 251     {
 252         if (P.GetDistance(VertBB[Nr])>0.0) VertFront= 1;
 253                                       else VertBack =-1;
 254     }
 255
 256     return SideT(VertFront+VertBack);
 257 #endif
 258 }
 259
 260
 261 template<class T> T BoundingBox3T<T>::GetDistance(const Plane3T<T>& P) const
 262 {
 263     assert(IsInited());
 264
 265 #if 1
 266     Vector3T<T> VertNear;
 267     Vector3T<T> VertFar;
 268
 269     // We can determine the vertex that is nearest and the vertex that is farthest
 270     // from P by evaluating the sign of the components of the normal vector of P.
 271     if (P.Normal.x>0)
 272     {
 273         VertNear.x=Min.x;
 274         VertFar.x =Max.x;
 275     }
 276     else
 277     {
 278         VertNear.x=Max.x;
 279         VertFar.x =Min.x;
 280     }
 281
 282     if (P.Normal.y>0)
 283     {
 284         VertNear.y=Min.y;
 285         VertFar.y =Max.y;
 286     }
 287     else
 288     {
 289         VertNear.y=Max.y;
 290         VertFar.y =Min.y;
 291     }
 292
 293     if (P.Normal.z>0)
 294     {
 295         VertNear.z=Min.z;
 296         VertFar.z =Max.z;
 297     }
 298     else
 299     {
 300         VertNear.z=Max.z;
 301         VertFar.z =Min.z;
 302     }
 303
 304     T Dist;
 305     Dist=P.GetDistance(VertNear); if (Dist>0) return Dist;
 306     Dist=P.GetDistance(VertFar ); if (Dist<0) return Dist;
 307
 308     return 0;
 309 #else
 310     const Vector3T<T> Center=(Min+Max)*0.5f;
 311     const T           DistC =P.GetDistance(Center);
 312     const T           Dist2 =fabs((Max.x-Center.x)*P.Normal.x) +
 313                              fabs((Max.y-Center.y)*P.Normal.y) +
 314                              fabs((Max.z-Center.z)*P.Normal.z);
 315
 316     // Dist2 bedeutet:
 317     // "Wie weit muß ich eine Ebene, die den Normalenvektor P.Normal hat und Center enthält, parallel verschieben
 318     //  (entlang ihres Normalvektors), um zu der in dieser Richtung liegenden äußersten Ecke der BB zu gelangen?"
 319     if (DistC-Dist2>0) return DistC-Dist2;
 320     if (DistC+Dist2<0) return DistC+Dist2;
 321
 322     return 0;
 323 #endif
 324 }
 325
 326
 327 #if defined(_MSC_VER)
 328     #pragma warning(push)
 329     #pragma warning(disable: 4723)    // potential divide by 0
 330 #endif
 331
 332 // Algorithm derived from Amy Williams et al., "An Efficient and Robust Ray-Box Intersection Algorithm", http://www.cs.utah.edu/~awilliam/box/.
 333 template<class T> bool BoundingBox3T<T>::TraceRay(const Vector3T<T>& RayOrigin, const Vector3T<T>& RayDir, T& Fraction) const
 334 {
 335     assert(IsInited());
 336
 337     // The RayDir components can be 0, potentially causing a division by 0.
 338     // This is perfectly intentional here as described in the above paper.
 339     const Vector3T<T> OneDivRayDir(1/RayDir.x, 1/RayDir.y, 1/RayDir.z);
 340     const bool        RayDirSigns[3]={ RayDir.x<0, RayDir.y<0, RayDir.z<0 };
 341
 342           T tmin =((RayDirSigns[0] ? Max : Min).x - RayOrigin.x) * OneDivRayDir.x;
 343           T tmax =((RayDirSigns[0] ? Min : Max).x - RayOrigin.x) * OneDivRayDir.x;
 344     const T tymin=((RayDirSigns[1] ? Max : Min).y - RayOrigin.y) * OneDivRayDir.y;
 345     const T tymax=((RayDirSigns[1] ? Min : Max).y - RayOrigin.y) * OneDivRayDir.y;
 346
 347     if ((tmin>tymax) || (tymin>tmax)) return false;
 348     if (tymin>tmin) tmin=tymin;
 349     if (tymax<tmax) tmax=tymax;
 350
 351     const T tzmin=((RayDirSigns[2] ? Max : Min).z - RayOrigin.z) * OneDivRayDir.z;
 352     const T tzmax=((RayDirSigns[2] ? Min : Max).z - RayOrigin.z) * OneDivRayDir.z;
 353
 354     if ((tmin>tzmax) || (tzmin>tmax)) return false;
 355     if (tzmin>tmin) tmin=tzmin;
 356     if (tzmax<tmax) tmax=tzmax;
 357
 358     if (tmin<0) return false;   // Ray starts in or already "out of" bounding box.
 359     Fraction=tmin;
 360     return true;
 361 }
 362
 363 #if defined(_MSC_VER)
 364     #pragma warning(pop)
 365 #endif
 366
 367
 368 template<class T> void BoundingBox3T<T>::GetCornerVertices(Vector3T<T>* Vertices) const
 369 {
 370     assert(IsInited());
 371
 372     Vertices[0]=Min;
 373     Vertices[1]=Vector3T<T>(Min.x, Min.y, Max.z);
 374     Vertices[2]=Vector3T<T>(Min.x, Max.y, Min.z);
 375     Vertices[3]=Vector3T<T>(Min.x, Max.y, Max.z);
 376     Vertices[4]=Vector3T<T>(Max.x, Min.y, Min.z);
 377     Vertices[5]=Vector3T<T>(Max.x, Min.y, Max.z);
 378     Vertices[6]=Vector3T<T>(Max.x, Max.y, Min.z);
 379     Vertices[7]=Max;
 380 }
 381
 382
 383 template<class T> ArrayT< BoundingBox3T<T> > BoundingBox3T<T>::GetSplits(const Plane3T<T>& SplitPlane, const T PlaneThickness) const
 384 {
 385     assert(IsInited());
 386
 387     Vector3T<T> VertBB[8]={ Min,                              Vector3T<T>(Min.x, Min.y, Max.z),
 388                             Vector3T<T>(Min.x, Max.y, Min.z), Vector3T<T>(Min.x, Max.y, Max.z),
 389                             Vector3T<T>(Max.x, Min.y, Min.z), Vector3T<T>(Max.x, Min.y, Max.z),
 390                             Vector3T<T>(Max.x, Max.y, Min.z), Max };
 391
 392     signed char           Side[8];
 393     ArrayT< Vector3T<T> > VertFront;
 394     ArrayT< Vector3T<T> > VertBack;
 395     ArrayT< Vector3T<T> > VertOn;
 396
 397     const char Edge[12][2]={ {0,1}, {0,2}, {0,4}, {7,3}, {7,5}, {7,6}, {1,3}, {1,5}, {6,2}, {6,4}, {4,5}, {2,3} };
 398
 399     for (unsigned long Nr=0; Nr<8; Nr++)
 400     {
 401         const double Dist=SplitPlane.GetDistance(VertBB[Nr]);
 402
 403              if (Dist> PlaneThickness) { VertFront.PushBack(VertBB[Nr]); Side[Nr]= 1; }
 404         else if (Dist<-PlaneThickness) { VertBack .PushBack(VertBB[Nr]); Side[Nr]=-1; }
 405         else                           { VertOn   .PushBack(VertBB[Nr]); Side[Nr]= 0; }
 406     }
 407
 408     for (unsigned long Nr=0; Nr<12; Nr++)
 409     {
 410         char v1=Edge[Nr][0];
 411         char v2=Edge[Nr][1];
 412
 413         if (Side[v1] && Side[v1]==-Side[v2]) VertOn.PushBack(SplitPlane.GetIntersection(VertBB[v1], VertBB[v2], 0));
 414     }
 415
 416
 417     ArrayT< BoundingBox3T<T> > Result;
 418
 419     Result.PushBackEmpty(2);
 420
 421     if (VertFront.Size())
 422     {
 423         Result[0]=BoundingBox3T<T>(VertFront);
 424         Result[0].Insert(VertOn);
 425     }
 426
 427     if (VertBack.Size())
 428     {
 429         Result[1]=BoundingBox3T<T>(VertBack);
 430         Result[1].Insert(VertOn);
 431     }
 432
 433     return Result;
 434 }
 435
 436
 437 template class BoundingBox3T<float>;
 438 template class BoundingBox3T<double>;