aabbox3d.h 11 KB

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