include/aabbox3d.h

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