 BoundingBox.hpp
1 /*
2 Cafu Engine, http://www.cafu.de/
3 Copyright (c) Carsten Fuchs and other contributors.
5 */
6
7 /********************/
8 /*** Bounding Box ***/
9 /********************/
10
11 #ifndef CAFU_MATH_BOUNDING_BOX_HPP_INCLUDED
12 #define CAFU_MATH_BOUNDING_BOX_HPP_INCLUDED
13
14 #include "Vector3.hpp"
15 #include "Plane3.hpp"
16 #include "Templates/Array.hpp"
17
18 #include <cassert>
19
20
21 /// This class represents an axis-aligned bounding-box ("AABB") in 3-dimensional space.
22 template<class T>
24 {
25  public:
26
27  /// Information about on which side of a plane the bounding box is.
28  enum SideT
29  {
30  Back =-1, ///< The bounding box is on the back-side of the plane.
31  Both = 0, ///< The bounding box is on both sides of the plane (i.e. it is intersected by the plane).
32  Front= 1, ///< The bounding box is on the front-side of the plane.
33  };
34
35
36  /// The default constructor creates a bounding-box that is "uninitialized", i.e. whose dimensions are not specified.
37  /// Inserting the first vertex into the bounding-box will automatically turn it into a regular, initialized instance.
38  BoundingBox3T();
39
40  /// Constructs a zero-volume bounding box at A.
41  /// @param A The spatial location to initialize the bounding-box at.
42  explicit BoundingBox3T(const Vector3T<T>& A);
43
44  /// Constructs a bounding box as defined by A and B.
45  /// @param A The first corner point that defines the dimensions of the bounding-box.
46  /// @param B The second corner point that defines the dimensions of the bounding-box.
47  BoundingBox3T(const Vector3T<T>& A, const Vector3T<T>& B);
48
49  /// Constructs a bounding box from the vertices of the array A.
50  /// The bounding-box will be "uninitialized" if A is empty.
51  /// @param A An array of vertices whose elements define the dimensions of the bounding-box.
52  explicit BoundingBox3T(const ArrayT< Vector3T<T> >& A);
53
54
55  /// Casts this BoundingBox3T<T> to a BoundingBox3T<float>, so that the cast is explicitly and easy to see and find in user code.
57  {
59
60  if (IsInited())
61  {
62  BB.Min = Min.AsVectorOfFloat();
63  BB.Max = Max.AsVectorOfFloat();
64  }
65
66  return BB;
67  }
68
69  /// Casts this BoundingBox3T<T> to a BoundingBox3T<double>, so that the cast is explicitly and easy to see and find in user code.
71  {
73
74  if (IsInited())
75  {
76  BB.Min = Min.AsVectorOfDouble();
77  BB.Max = Max.AsVectorOfDouble();
78  }
79
80  return BB;
81  }
82
83
84  /// Determines whether a bounding-box is valid.
85  /// A bounding-box is valid if it is in "uninitialized" or properly initialized state.
86  /// (A bounding-box is invalid if it has negative volume.)
87  /// This method is needed mostly for debugging, as a bounding-box should *always* be valid.
88  bool IsValid() const;
89
90  /// Returns whether this bounding-box has been initialized with at least one point in space.
91  /// A bounding-box that has not yet been initialized can be initalized by inserting the first vertex.
92  bool IsInited() const;
93
94
95  /// Inserts A into this boundig-box, growing it appropriately.
96  /// @param A The point to be inserted into the bounding-box.
97  void Insert(const Vector3T<T>& A);
98
99  /// An equivalent to Insert(A), but more readable.
100  void operator += (const Vector3T<T>& A) { Insert(A); }
101
102  /// Inserts all vertices of A into this boundig-box, growing it appropriately.
103  /// @param A The list of points to be inserted into the bounding-box.
104  void Insert(const ArrayT< Vector3T<T> >& A);
105
106  /// An equivalent to Insert(A), but more readable.
107  void operator += (const ArrayT< Vector3T<T> >& A) { Insert(A); }
108
109  /// Inserts the given bounding-box into this one, growing it appropriately.
110  /// This is also called "merging" or "combining" BB with this bounding box.
111  /// @param BB The bounding-box to be combined/merged with this bounding-box. BB.IsInited() must be true.
112  void Insert(const BoundingBox3T<T>& BB);
113
114  /// An equivalent to Insert(BB), but more readable.
115  void operator += (const BoundingBox3T<T>& BB) { Insert(BB); }
116
117  /// Like Insert(BB), but with this version it suffices when BB is only valid, i.e. it can be initialized or uninitialized.
118  /// If BB is uninitialized, this bounding-box is not changed. Otherwise, BB is inserted normally: this->Insert(BB).
119  /// @param BB The bounding-box to be combined/merged with this bounding-box. BB.IsValid() must be true.
120  void InsertValid(const BoundingBox3T<T>& BB);
121
122
123  /// This method returns a copy of this bounding box that is slightly enlarged by Epsilon (or shrunk if Epsilon is negative).
124  /// The returned box is very useful with the containment / intersection / test methods when rounding errors are an issue!
125  /// Note that it is easy to control the desired effect by passing either a positive number to make the box slightly larger,
126  /// or by passing a negative number to make the box slightly smaller.
127  /// For example, if BB is a bounding box, BB.GetEpsilonBox(0.1).Contains(A) returns true even if A is actually a bit outside of BB,
128  /// or BB.GetEpsilonBox(-0.3).Intersects(OtherBB) yields false even if BB and OtherBB are neighboured and share a plane.
129  /// @param Epsilon The amount by which the bounding-box is expanded.
130  BoundingBox3T<T> GetEpsilonBox(const T Epsilon) const
131  {
132  assert(IsInited());
133
134  const Vector3T<T> Eps=Vector3T<T>(Epsilon, Epsilon, Epsilon);
135  BoundingBox3T<T> BB(*this);
136
137  // Don't use the (Min-Eps, Max+Eps) constructor here, as it involved an additional call to Insert().
138  BB.Min-=Eps;
139  BB.Max+=Eps;
140
141  // Maybe the box got smaller, now make sure it didn't get negative.
142  if (BB.Min.x>BB.Max.x) BB.Min.x=BB.Max.x=(BB.Min.x+BB.Max.x)*0.5f;
143  if (BB.Min.y>BB.Max.y) BB.Min.y=BB.Max.y=(BB.Min.y+BB.Max.y)*0.5f;
144  if (BB.Min.z>BB.Max.z) BB.Min.z=BB.Max.z=(BB.Min.z+BB.Max.z)*0.5f;
145
146  return BB;
147  }
148
149  /// Returns the overall bounding box that is defined by translating (moving) this bounding box in a linear fashion from point Start to End.
150  /// @param Start The start point for the thought linear movement of this bounding box.
151  /// @param End The end point for the thought linear movement of this bounding box.
152  /// @returns the overall bounding box that contains the entire movement.
153  BoundingBox3T<T> GetOverallTranslationBox(const Vector3T<T>& Start, const Vector3T<T>& End) const;
154
155  /// Determines whether this bounding box contains A.
156  /// @param A The point for which containment should be determined.
157  bool Contains(const Vector3T<T>& A) const;
158
159  /// Determines whether this bounding box and BB intersect.
160  /// @param BB The other bounding box to test with.
161  bool Intersects(const BoundingBox3T<T>& BB) const;
162
163  /// Determines whether this bounding box and BB intersect or touch each other.
164  /// This method is only used in the ClipSys, and the Intersects() method should always be preferred.
165  /// @param BB The other bounding box to test with.
166  bool IntersectsOrTouches(const BoundingBox3T<T>& BB) const;
167
168  /// Determines on what side of plane P the this BB is.
169  /// @param P The plane to test with.
170  /// @param Epsilon Maximum error value.
171  /// @returns SideT::Front if this box is completely on the front of P,
172  /// SideT::Back if this box is completely on the back of P,
173  /// SideT::Both if this box is on both sides of P.
174  SideT WhatSide(const Plane3T<T>& P, const T Epsilon=0) const;
175  SideT WhatSide_OLD(const Plane3T<T>& P, const T Epsilon=0) const;
176
177  /// Returns the center point of the BB.
178  Vector3T<T> GetCenter() const { assert(IsInited()); return (Min+Max)/2; }
179
180  /// Determines the distance from the plane P to the nearest point of the BB.
181  /// @param P The plane to test with.
182  /// @returns the distance from the plane P to the nearest point of the BB, 0 whenever the BB intersects P.
183  T GetDistance(const Plane3T<T>& P) const;
184
185  /// Traces a ray against this bounding-box, and returns whether it was hit.
186  /// The ray for the trace is defined by RayOrigin + RayDir*Fraction, where Fraction is a scalar >= 0.
187  /// If a hit was detected, the Fraction is returned. The method only accounts for "incoming" hits,
188  /// that is, where the ray comes from "outside" of the boundig-box and enters its inside.
189  /// Hits where the ray leaves the inner of the bounding-box to the outside are not reported.
190  ///
191  /// @param RayOrigin The point where the ray starts.
192  /// @param RayDir A vector of non-zero length that describes the direction the ray extends to (not required to be a unit vector).
193  /// @param Fraction On hit, the scalar along RayDir at which the hit occurred is returned here.
194  ///
195  /// @returns true if the ray hit this bounding-box, false otherwise. On hit, the Fraction is returned via reference paramaters.
196  bool TraceRay(const Vector3T<T>& RayOrigin, const Vector3T<T>& RayDir, T& Fraction) const;
197
198  /// Explicitly returns the eight corner vertices of this bounding box.
199  /// @param Vertices An array of eight vertices in which the eight corner vertices are returned.
200  void GetCornerVertices(Vector3T<T>* Vertices) const;
201
202  /// Splits the quad that is defined by this bounding box and constructs new bounding boxes from the results.
203  /// @param SplitPlane The plane along which this bounding box is split.
204  /// @param PlaneThickness The "thickness" that is attributed to the SplitPlane to account for rounding-error.
205  /// @returns an array of two bounding-boxes that correspond to the front and back split results.
206  ArrayT< BoundingBox3T<T> > GetSplits(const Plane3T<T>& SplitPlane, const T PlaneThickness) const;
207
208
209  Vector3T<T> Min; ///< The minimum-coordinate corner of the bounding-box.
210  Vector3T<T> Max; ///< The maximum-coordinate corner of the bounding-box.
211 };
212
213
214 /// Typedef for a BoundingBox3T of floats.
216
217 /// Typedef for a BoundingBox3T of doubles.
219
220 #endif
The bounding box is on both sides of the plane (i.e. it is intersected by the plane).
Definition: BoundingBox.hpp:31
The bounding box is on the back-side of the plane.
Definition: BoundingBox.hpp:30
This class represents a plane in three-dimensional space.
Definition: Plane3.hpp:26
bool IsInited() const
Returns whether this bounding-box has been initialized with at least one point in space...
Definition: BoundingBox.cpp:71
BoundingBox3T< T > GetOverallTranslationBox(const Vector3T< T > &Start, const Vector3T< T > &End) const
Returns the overall bounding box that is defined by translating (moving) this bounding box in a linea...
Definition: BoundingBox.cpp:122
BoundingBox3T()
The default constructor creates a bounding-box that is "uninitialized", i.e.
Definition: BoundingBox.cpp:15
BoundingBox3T< double > AsBoxOfDouble() const
Casts this BoundingBox3T<T> to a BoundingBox3T<double>, so that the cast is explicitly and easy to se...
Definition: BoundingBox.hpp:70
The bounding box is on the front-side of the plane.
Definition: BoundingBox.hpp:32
SideT
Information about on which side of a plane the bounding box is.
Definition: BoundingBox.hpp:28
Vector3T< T > Max
The maximum-coordinate corner of the bounding-box.
Definition: BoundingBox.hpp:210
bool Intersects(const BoundingBox3T< T > &BB) const
Determines whether this bounding box and BB intersect.
Definition: BoundingBox.cpp:150
T y
The y-component of this vector.
Definition: Vector3.hpp:41
Vector3T< T > Min
The minimum-coordinate corner of the bounding-box.
Definition: BoundingBox.hpp:209
void operator+=(const Vector3T< T > &A)
An equivalent to Insert(A), but more readable.
Definition: BoundingBox.hpp:100
This class represents a polymorphic 3-dimensional vector.
Definition: Misc.hpp:11
ArrayT< BoundingBox3T< T > > GetSplits(const Plane3T< T > &SplitPlane, const T PlaneThickness) const
Splits the quad that is defined by this bounding box and constructs new bounding boxes from the resul...
Definition: BoundingBox.cpp:383
T GetDistance(const Plane3T< T > &P) const
Determines the distance from the plane P to the nearest point of the BB.
Definition: BoundingBox.cpp:261
BoundingBox3T< float > AsBoxOfFloat() const
Casts this BoundingBox3T<T> to a BoundingBox3T<float>, so that the cast is explicitly and easy to see...
Definition: BoundingBox.hpp:56
bool Contains(const Vector3T< T > &A) const
Determines whether this bounding box contains A.
Definition: BoundingBox.cpp:140
SideT WhatSide(const Plane3T< T > &P, const T Epsilon=0) const
Determines on what side of plane P the this BB is.
Definition: BoundingBox.cpp:174
bool TraceRay(const Vector3T< T > &RayOrigin, const Vector3T< T > &RayDir, T &Fraction) const
Traces a ray against this bounding-box, and returns whether it was hit.
Definition: BoundingBox.cpp:333
void GetCornerVertices(Vector3T< T > *Vertices) const
Explicitly returns the eight corner vertices of this bounding box.
Definition: BoundingBox.cpp:368
void Insert(const Vector3T< T > &A)
Inserts A into this boundig-box, growing it appropriately.
Definition: BoundingBox.cpp:79
bool IntersectsOrTouches(const BoundingBox3T< T > &BB) const
Determines whether this bounding box and BB intersect or touch each other.
Definition: BoundingBox.cpp:162
T z
The z-component of this vector.
Definition: Vector3.hpp:42
void InsertValid(const BoundingBox3T< T > &BB)
Like Insert(BB), but with this version it suffices when BB is only valid, i.e.
Definition: BoundingBox.cpp:111
bool IsValid() const
Determines whether a bounding-box is valid.
Definition: BoundingBox.cpp:58
T x
The x-component of this vector.
Definition: Vector3.hpp:40
Vector3T< T > GetCenter() const
Returns the center point of the BB.
Definition: BoundingBox.hpp:178
Definition: Renderer.hpp:16
This class represents an axis-aligned bounding-box ("AABB") in 3-dimensional space.
Definition: BoundingBox.hpp:23
BoundingBox3T< T > GetEpsilonBox(const T Epsilon) const
This method returns a copy of this bounding box that is slightly enlarged by Epsilon (or shrunk if Ep...
Definition: BoundingBox.hpp:130