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