1 // Copyright (C) 2002-2012 Nikolaus Gebhardt 2 // This file is part of the "Irrlicht Engine". 3 // For conditions of distribution and use, see copyright notice in irrlicht.h 4 5 #ifndef __IRR_AABBOX_3D_H_INCLUDED__ 6 #define __IRR_AABBOX_3D_H_INCLUDED__ 7 8 #include "irrMath.h" 9 #include "plane3d.h" 10 #include "line3d.h" 11 12 namespace irr 13 { 14 namespace core 15 { 16 17 //! Axis aligned bounding box in 3d dimensional space. 18 /** Has some useful methods used with occlusion culling or clipping. 19 */ 20 template <class T> 21 class aabbox3d 22 { 23 public: 24 25 //! Default Constructor. aabbox3d()26 aabbox3d(): MinEdge(-1,-1,-1), MaxEdge(1,1,1) {} 27 //! Constructor with min edge and max edge. aabbox3d(const vector3d<T> & min,const vector3d<T> & max)28 aabbox3d(const vector3d<T>& min, const vector3d<T>& max): MinEdge(min), MaxEdge(max) {} 29 //! Constructor with only one point. aabbox3d(const vector3d<T> & init)30 aabbox3d(const vector3d<T>& init): MinEdge(init), MaxEdge(init) {} 31 //! Constructor with min edge and max edge as single values, not vectors. aabbox3d(T minx,T miny,T minz,T maxx,T maxy,T maxz)32 aabbox3d(T minx, T miny, T minz, T maxx, T maxy, T maxz): MinEdge(minx, miny, minz), MaxEdge(maxx, maxy, maxz) {} 33 34 // operators 35 //! Equality operator 36 /** \param other box to compare with. 37 \return True if both boxes are equal, else false. */ 38 inline bool operator==(const aabbox3d<T>& other) const { return (MinEdge == other.MinEdge && other.MaxEdge == MaxEdge);} 39 //! Inequality operator 40 /** \param other box to compare with. 41 \return True if both boxes are different, else false. */ 42 inline bool operator!=(const aabbox3d<T>& other) const { return !(MinEdge == other.MinEdge && other.MaxEdge == MaxEdge);} 43 44 // functions 45 46 //! Resets the bounding box to a one-point box. 47 /** \param x X coord of the point. 48 \param y Y coord of the point. 49 \param z Z coord of the point. */ reset(T x,T y,T z)50 void reset(T x, T y, T z) 51 { 52 MaxEdge.set(x,y,z); 53 MinEdge = MaxEdge; 54 } 55 56 //! Resets the bounding box. 57 /** \param initValue New box to set this one to. */ reset(const aabbox3d<T> & initValue)58 void reset(const aabbox3d<T>& initValue) 59 { 60 *this = initValue; 61 } 62 63 //! Resets the bounding box to a one-point box. 64 /** \param initValue New point. */ reset(const vector3d<T> & initValue)65 void reset(const vector3d<T>& initValue) 66 { 67 MaxEdge = initValue; 68 MinEdge = initValue; 69 } 70 71 //! Adds a point to the bounding box 72 /** The box grows bigger, if point was outside of the box. 73 \param p: Point to add into the box. */ addInternalPoint(const vector3d<T> & p)74 void addInternalPoint(const vector3d<T>& p) 75 { 76 addInternalPoint(p.X, p.Y, p.Z); 77 } 78 79 //! Adds another bounding box 80 /** The box grows bigger, if the new box was outside of the box. 81 \param b: Other bounding box to add into this box. */ addInternalBox(const aabbox3d<T> & b)82 void addInternalBox(const aabbox3d<T>& b) 83 { 84 addInternalPoint(b.MaxEdge); 85 addInternalPoint(b.MinEdge); 86 } 87 88 //! Adds a point to the bounding box 89 /** The box grows bigger, if point is outside of the box. 90 \param x X coordinate of the point to add to this box. 91 \param y Y coordinate of the point to add to this box. 92 \param z Z coordinate of the point to add to this box. */ addInternalPoint(T x,T y,T z)93 void addInternalPoint(T x, T y, T z) 94 { 95 if (x>MaxEdge.X) MaxEdge.X = x; 96 if (y>MaxEdge.Y) MaxEdge.Y = y; 97 if (z>MaxEdge.Z) MaxEdge.Z = z; 98 99 if (x<MinEdge.X) MinEdge.X = x; 100 if (y<MinEdge.Y) MinEdge.Y = y; 101 if (z<MinEdge.Z) MinEdge.Z = z; 102 } 103 104 //! Get center of the bounding box 105 /** \return Center of the bounding box. */ getCenter()106 vector3d<T> getCenter() const 107 { 108 return (MinEdge + MaxEdge) / 2; 109 } 110 111 //! Get extent of the box (maximal distance of two points in the box) 112 /** \return Extent of the bounding box. */ getExtent()113 vector3d<T> getExtent() const 114 { 115 return MaxEdge - MinEdge; 116 } 117 118 //! Check if the box is empty. 119 /** This means that there is no space between the min and max edge. 120 \return True if box is empty, else false. */ isEmpty()121 bool isEmpty() const 122 { 123 return MinEdge.equals ( MaxEdge ); 124 } 125 126 //! Get the volume enclosed by the box in cubed units getVolume()127 T getVolume() const 128 { 129 const vector3d<T> e = getExtent(); 130 return e.X * e.Y * e.Z; 131 } 132 133 //! Get the surface area of the box in squared units getArea()134 T getArea() const 135 { 136 const vector3d<T> e = getExtent(); 137 return 2*(e.X*e.Y + e.X*e.Z + e.Y*e.Z); 138 } 139 140 //! Stores all 8 edges of the box into an array 141 /** \param edges: Pointer to array of 8 edges. */ getEdges(vector3d<T> * edges)142 void getEdges(vector3d<T> *edges) const 143 { 144 const core::vector3d<T> middle = getCenter(); 145 const core::vector3d<T> diag = middle - MaxEdge; 146 147 /* 148 Edges are stored in this way: 149 Hey, am I an ascii artist, or what? :) niko. 150 /3--------/7 151 / | / | 152 / | / | 153 1---------5 | 154 | /2- - -|- -6 155 | / | / 156 |/ | / 157 0---------4/ 158 */ 159 160 edges[0].set(middle.X + diag.X, middle.Y + diag.Y, middle.Z + diag.Z); 161 edges[1].set(middle.X + diag.X, middle.Y - diag.Y, middle.Z + diag.Z); 162 edges[2].set(middle.X + diag.X, middle.Y + diag.Y, middle.Z - diag.Z); 163 edges[3].set(middle.X + diag.X, middle.Y - diag.Y, middle.Z - diag.Z); 164 edges[4].set(middle.X - diag.X, middle.Y + diag.Y, middle.Z + diag.Z); 165 edges[5].set(middle.X - diag.X, middle.Y - diag.Y, middle.Z + diag.Z); 166 edges[6].set(middle.X - diag.X, middle.Y + diag.Y, middle.Z - diag.Z); 167 edges[7].set(middle.X - diag.X, middle.Y - diag.Y, middle.Z - diag.Z); 168 } 169 170 //! Repairs the box. 171 /** Necessary if for example MinEdge and MaxEdge are swapped. */ repair()172 void repair() 173 { 174 T t; 175 176 if (MinEdge.X > MaxEdge.X) 177 { t=MinEdge.X; MinEdge.X = MaxEdge.X; MaxEdge.X=t; } 178 if (MinEdge.Y > MaxEdge.Y) 179 { t=MinEdge.Y; MinEdge.Y = MaxEdge.Y; MaxEdge.Y=t; } 180 if (MinEdge.Z > MaxEdge.Z) 181 { t=MinEdge.Z; MinEdge.Z = MaxEdge.Z; MaxEdge.Z=t; } 182 } 183 184 //! Calculates a new interpolated bounding box. 185 /** d=0 returns other, d=1 returns this, all other values blend between 186 the two boxes. 187 \param other Other box to interpolate between 188 \param d Value between 0.0f and 1.0f. 189 \return Interpolated box. */ getInterpolated(const aabbox3d<T> & other,f32 d)190 aabbox3d<T> getInterpolated(const aabbox3d<T>& other, f32 d) const 191 { 192 f32 inv = 1.0f - d; 193 return aabbox3d<T>((other.MinEdge*inv) + (MinEdge*d), 194 (other.MaxEdge*inv) + (MaxEdge*d)); 195 } 196 197 //! Determines if a point is within this box. 198 /** Border is included (IS part of the box)! 199 \param p: Point to check. 200 \return True if the point is within the box and false if not */ isPointInside(const vector3d<T> & p)201 bool isPointInside(const vector3d<T>& p) const 202 { 203 return (p.X >= MinEdge.X && p.X <= MaxEdge.X && 204 p.Y >= MinEdge.Y && p.Y <= MaxEdge.Y && 205 p.Z >= MinEdge.Z && p.Z <= MaxEdge.Z); 206 } 207 208 //! Determines if a point is within this box and not its borders. 209 /** Border is excluded (NOT part of the box)! 210 \param p: Point to check. 211 \return True if the point is within the box and false if not. */ isPointTotalInside(const vector3d<T> & p)212 bool isPointTotalInside(const vector3d<T>& p) const 213 { 214 return (p.X > MinEdge.X && p.X < MaxEdge.X && 215 p.Y > MinEdge.Y && p.Y < MaxEdge.Y && 216 p.Z > MinEdge.Z && p.Z < MaxEdge.Z); 217 } 218 219 //! Check if this box is completely inside the 'other' box. 220 /** \param other: Other box to check against. 221 \return True if this box is completly inside the other box, 222 otherwise false. */ isFullInside(const aabbox3d<T> & other)223 bool isFullInside(const aabbox3d<T>& other) const 224 { 225 return (MinEdge.X >= other.MinEdge.X && MinEdge.Y >= other.MinEdge.Y && MinEdge.Z >= other.MinEdge.Z && 226 MaxEdge.X <= other.MaxEdge.X && MaxEdge.Y <= other.MaxEdge.Y && MaxEdge.Z <= other.MaxEdge.Z); 227 } 228 229 //! Determines if the axis-aligned box intersects with another axis-aligned box. 230 /** \param other: Other box to check a intersection with. 231 \return True if there is an intersection with the other box, 232 otherwise false. */ intersectsWithBox(const aabbox3d<T> & other)233 bool intersectsWithBox(const aabbox3d<T>& other) const 234 { 235 return (MinEdge.X <= other.MaxEdge.X && MinEdge.Y <= other.MaxEdge.Y && MinEdge.Z <= other.MaxEdge.Z && 236 MaxEdge.X >= other.MinEdge.X && MaxEdge.Y >= other.MinEdge.Y && MaxEdge.Z >= other.MinEdge.Z); 237 } 238 239 //! Tests if the box intersects with a line 240 /** \param line: Line to test intersection with. 241 \return True if there is an intersection , else false. */ intersectsWithLine(const line3d<T> & line)242 bool intersectsWithLine(const line3d<T>& line) const 243 { 244 return intersectsWithLine(line.getMiddle(), line.getVector().normalize(), 245 (T)(line.getLength() * 0.5)); 246 } 247 248 //! Tests if the box intersects with a line 249 /** \param linemiddle Center of the line. 250 \param linevect Vector of the line. 251 \param halflength Half length of the line. 252 \return True if there is an intersection, else false. */ intersectsWithLine(const vector3d<T> & linemiddle,const vector3d<T> & linevect,T halflength)253 bool intersectsWithLine(const vector3d<T>& linemiddle, 254 const vector3d<T>& linevect, T halflength) const 255 { 256 const vector3d<T> e = getExtent() * (T)0.5; 257 const vector3d<T> t = getCenter() - linemiddle; 258 259 if ((fabs(t.X) > e.X + halflength * fabs(linevect.X)) || 260 (fabs(t.Y) > e.Y + halflength * fabs(linevect.Y)) || 261 (fabs(t.Z) > e.Z + halflength * fabs(linevect.Z)) ) 262 return false; 263 264 T r = e.Y * (T)fabs(linevect.Z) + e.Z * (T)fabs(linevect.Y); 265 if (fabs(t.Y*linevect.Z - t.Z*linevect.Y) > r ) 266 return false; 267 268 r = e.X * (T)fabs(linevect.Z) + e.Z * (T)fabs(linevect.X); 269 if (fabs(t.Z*linevect.X - t.X*linevect.Z) > r ) 270 return false; 271 272 r = e.X * (T)fabs(linevect.Y) + e.Y * (T)fabs(linevect.X); 273 if (fabs(t.X*linevect.Y - t.Y*linevect.X) > r) 274 return false; 275 276 return true; 277 } 278 279 //! Classifies a relation with a plane. 280 /** \param plane Plane to classify relation to. 281 \return Returns ISREL3D_FRONT if the box is in front of the plane, 282 ISREL3D_BACK if the box is behind the plane, and 283 ISREL3D_CLIPPED if it is on both sides of the plane. */ classifyPlaneRelation(const plane3d<T> & plane)284 EIntersectionRelation3D classifyPlaneRelation(const plane3d<T>& plane) const 285 { 286 vector3d<T> nearPoint(MaxEdge); 287 vector3d<T> farPoint(MinEdge); 288 289 if (plane.Normal.X > (T)0) 290 { 291 nearPoint.X = MinEdge.X; 292 farPoint.X = MaxEdge.X; 293 } 294 295 if (plane.Normal.Y > (T)0) 296 { 297 nearPoint.Y = MinEdge.Y; 298 farPoint.Y = MaxEdge.Y; 299 } 300 301 if (plane.Normal.Z > (T)0) 302 { 303 nearPoint.Z = MinEdge.Z; 304 farPoint.Z = MaxEdge.Z; 305 } 306 307 if (plane.Normal.dotProduct(nearPoint) + plane.D > (T)0) 308 return ISREL3D_FRONT; 309 310 if (plane.Normal.dotProduct(farPoint) + plane.D > (T)0) 311 return ISREL3D_CLIPPED; 312 313 return ISREL3D_BACK; 314 } 315 316 //! The near edge 317 vector3d<T> MinEdge; 318 319 //! The far edge 320 vector3d<T> MaxEdge; 321 }; 322 323 //! Typedef for a f32 3d bounding box. 324 typedef aabbox3d<f32> aabbox3df; 325 //! Typedef for an integer 3d bounding box. 326 typedef aabbox3d<s32> aabbox3di; 327 328 } // end namespace core 329 } // end namespace irr 330 331 #endif 332 333