[2747] | 1 | #ifndef _AxisAlignedBox3_H__
|
---|
| 2 | #define _AxisAlignedBox3_H__
|
---|
| 3 |
|
---|
| 4 |
|
---|
| 5 | #include "Matrix4x4.h"
|
---|
| 6 | #include "Vector3.h"
|
---|
[2911] | 7 | #include "common.h"
|
---|
[2747] | 8 |
|
---|
| 9 |
|
---|
[2776] | 10 | namespace CHCDemoEngine
|
---|
[2751] | 11 | {
|
---|
[2747] | 12 |
|
---|
| 13 | struct Triangle3;
|
---|
[2755] | 14 | class Plane3;
|
---|
[2911] | 15 | class Polygon3;
|
---|
| 16 | class Polyhedron;
|
---|
[2747] | 17 |
|
---|
[2911] | 18 |
|
---|
[2913] | 19 | struct SimpleRay
|
---|
| 20 | {
|
---|
| 21 | SimpleRay() {}
|
---|
| 22 |
|
---|
| 23 | SimpleRay(const Vector3 &o, const Vector3 &d): mOrigin(o), mDirection(d) {}
|
---|
| 24 |
|
---|
| 25 | Vector3 mOrigin;
|
---|
| 26 | Vector3 mDirection;
|
---|
| 27 |
|
---|
| 28 | Vector3 Extrap(const float t) const
|
---|
| 29 | {
|
---|
| 30 | return mOrigin + mDirection * t;
|
---|
| 31 | }
|
---|
| 32 | };
|
---|
| 33 |
|
---|
| 34 |
|
---|
[2747] | 35 | /** Axis alignedd box class.
|
---|
[2751] | 36 | This is a box in 3-space, defined by min and max
|
---|
| 37 | corner vectors. Many useful operations are defined.
|
---|
[2747] | 38 | */
|
---|
| 39 | class AxisAlignedBox3
|
---|
| 40 | {
|
---|
| 41 |
|
---|
| 42 | public:
|
---|
| 43 |
|
---|
[2751] | 44 | ///////////
|
---|
| 45 | //-- Constructors.
|
---|
[2747] | 46 |
|
---|
[2751] | 47 | AxisAlignedBox3();
|
---|
[2747] | 48 |
|
---|
[2751] | 49 | AxisAlignedBox3(const Vector3 &nMin, const Vector3 &nMax);
|
---|
[2747] | 50 | /** initialization to the non existing bounding box
|
---|
| 51 | */
|
---|
| 52 | void Initialize();
|
---|
| 53 | /** The center of the box
|
---|
| 54 | */
|
---|
| 55 | Vector3 Center() const;
|
---|
| 56 | /** The diagonal of the box
|
---|
| 57 | */
|
---|
| 58 | Vector3 Diagonal() const;
|
---|
| 59 |
|
---|
| 60 | float Center(const int axis) const;
|
---|
| 61 |
|
---|
| 62 | float Min(const int axis) const;
|
---|
| 63 |
|
---|
| 64 | float Max(const int axis) const;
|
---|
| 65 |
|
---|
| 66 | float Size(const int axis) const;
|
---|
| 67 |
|
---|
| 68 | // Read-only const access tomMin and max vectors using references
|
---|
| 69 | const Vector3& Min() const;
|
---|
| 70 | const Vector3& Max() const;
|
---|
| 71 |
|
---|
[2755] | 72 | void Enlarge(const Vector3 &v);
|
---|
[2747] | 73 |
|
---|
| 74 | void EnlargeToMinSize();
|
---|
| 75 |
|
---|
| 76 | void SetMin(const Vector3 &v);
|
---|
| 77 |
|
---|
| 78 | void SetMax(const Vector3 &v);
|
---|
| 79 |
|
---|
| 80 | void SetMin(int axis, const float value);
|
---|
| 81 |
|
---|
| 82 | void SetMax(int axis, const float value);
|
---|
[2755] | 83 | /** Decrease box by given splitting plane
|
---|
| 84 | */
|
---|
[2747] | 85 | void Reduce(int axis, int right, float value);
|
---|
| 86 |
|
---|
| 87 | bool Intersects(const Vector3 &lStart, const Vector3 &lEnd) const;
|
---|
| 88 |
|
---|
| 89 | // the size of the box along all the axes
|
---|
| 90 | Vector3 Size() const;
|
---|
[2755] | 91 | float Radius() const { return 0.5f * Magnitude(Size()); }
|
---|
| 92 | float SqrRadius() const { return 0.5f * SqrMagnitude(Size()); }
|
---|
[2747] | 93 |
|
---|
| 94 | // Return whether the box is unbounded. Unbounded boxes appear
|
---|
| 95 | // when unbounded objects such as quadric surfaces are included.
|
---|
| 96 | bool Unbounded() const;
|
---|
| 97 |
|
---|
| 98 | // Expand the axis-aligned box to include the given object.
|
---|
| 99 | void Include(const Vector3 &newpt);
|
---|
| 100 | void Include(const AxisAlignedBox3 &bbox);
|
---|
[2911] | 101 | void Include(const Polygon3 &newpoly);
|
---|
| 102 | void Include(const PolygonContainer &polys);
|
---|
| 103 |
|
---|
[2747] | 104 | /** Expand the axis-aligned box to include given values in particular axis.
|
---|
| 105 | */
|
---|
| 106 | void Include(const int &axis, const float &newBound);
|
---|
| 107 | /** Includes returns true if a includes b (completely)
|
---|
| 108 | */
|
---|
| 109 | bool Includes(const AxisAlignedBox3 &b) const;
|
---|
[2911] | 110 |
|
---|
[2747] | 111 | /** Returns true if this point is inside box.
|
---|
| 112 | */
|
---|
| 113 | virtual int IsInside(const Vector3 &v) const;
|
---|
| 114 | /** Test if the box makes sense.
|
---|
| 115 | */
|
---|
| 116 | virtual bool IsCorrect();
|
---|
| 117 | /** To answer true requires the box of real volume of non-zero value.
|
---|
| 118 | */
|
---|
| 119 | bool IsSingularOrIncorrect() const;
|
---|
| 120 | /** When the box is not of non-zero or negative surface area.
|
---|
| 121 | */
|
---|
| 122 | bool IsCorrectAndNotPoint() const;
|
---|
| 123 | /** Returns true when the box degenerates to a point.
|
---|
| 124 | */
|
---|
| 125 | bool IsPoint() const;
|
---|
| 126 | /** Scales the box with the factor.
|
---|
| 127 | */
|
---|
[2755] | 128 | void Scale(float scale);
|
---|
[2747] | 129 |
|
---|
| 130 | void Scale(const Vector3 &scale);
|
---|
| 131 | /** Translates the box with the factor.
|
---|
| 132 | */
|
---|
| 133 | void Translate(const Vector3 &shift);
|
---|
| 134 | /** Returns the square of the minimal and maximal distance to
|
---|
[2751] | 135 | a point on the box.
|
---|
[2747] | 136 | */
|
---|
[2751] | 137 | void GetSqrDistances(const Vector3 &point,
|
---|
| 138 | float &minDistance,
|
---|
| 139 | float &maxDistance) const;
|
---|
| 140 | /** return random point in box.
|
---|
| 141 | */
|
---|
[2747] | 142 | Vector3 GetRandomPoint() const;
|
---|
[2751] | 143 | /** Returns surface area of the box.
|
---|
| 144 | */
|
---|
| 145 | float SurfaceArea() const;
|
---|
| 146 | /** Returns volume of the box.
|
---|
| 147 | */
|
---|
| 148 | float GetVolume() const;
|
---|
[2747] | 149 |
|
---|
| 150 | // Six faces are distuinguished by their name.
|
---|
| 151 | enum EFaces {ID_Back = 0,
|
---|
| 152 | ID_Left = 1,
|
---|
| 153 | ID_Bottom = 2,
|
---|
| 154 | ID_Front = 3,
|
---|
| 155 | ID_Right = 4,
|
---|
| 156 | ID_Top = 5};
|
---|
| 157 |
|
---|
| 158 | // Writes a brief description of the object, indenting by the given
|
---|
| 159 | // number of spaces first.
|
---|
| 160 | virtual void Describe(std::ostream& app, int ind) const;
|
---|
| 161 |
|
---|
| 162 | // For edge .. number <0..11> returns two incident vertices
|
---|
[2751] | 163 | void GetEdge(int edge, Vector3 *a, Vector3 *b) const;
|
---|
[2747] | 164 |
|
---|
| 165 | // Compute the coordinates of one vertex of the box for 0/1 in each axis
|
---|
| 166 | // 0 .. smaller coordinates, 1 .. large coordinates
|
---|
| 167 | Vector3 GetVertex(int xAxis, int yAxis, int zAxis) const;
|
---|
| 168 |
|
---|
| 169 | // Compute the vertex for number N=<0..7>, N = 4*x + 2*y + z, where
|
---|
| 170 | // x,y,z are either 0 or 1; (0 .. lower coordinate, 1 .. large coordinate)
|
---|
| 171 | // (xmin,ymin, zmin) .. N = 0, (xmax, ymax, zmax) .. N= 7
|
---|
[2751] | 172 | void GetVertex(int N, Vector3 &vertex) const;
|
---|
[2747] | 173 |
|
---|
[2751] | 174 | Vector3 GetVertex(int N) const;
|
---|
| 175 | /** get the extent of face.
|
---|
| 176 | */
|
---|
| 177 | float GetExtent(int face) const;
|
---|
| 178 | /** Returns 1, if the box includes on arbitrary face a given box
|
---|
| 179 | */
|
---|
[2747] | 180 | int IsPiercedByBox(const AxisAlignedBox3 &box, int &axis) const;
|
---|
| 181 |
|
---|
| 182 | int GetFaceVisibilityMask(const Vector3 &position) const;
|
---|
| 183 | /** Returns vertex indices of edge.
|
---|
| 184 | */
|
---|
[2755] | 185 | void GetEdge(int edge, int &aIdx, int &bIdx) const;
|
---|
| 186 | /** Get distance of plane to vertex with specified index.
|
---|
| 187 | */
|
---|
| 188 | float GetDistance(int index, const Plane3 &plane) const;
|
---|
| 189 | /** Returns the distance between the plane given by 'vecNearplaneNormal' and the vertex that
|
---|
| 190 | is closest to it (this vertex is unequivocally identified by the direction of the vector)
|
---|
| 191 | */
|
---|
| 192 | float GetMinVisibleDistance(const Plane3 &near) const;
|
---|
[2911] | 193 | /** Returns cross section of the plane as a polygon.
|
---|
| 194 | */
|
---|
[2913] | 195 | Polygon3 *CrossSection(const Plane3 &plane) const;
|
---|
[2911] | 196 | /** Returns the supporting plane of this face.
|
---|
| 197 | */
|
---|
[2913] | 198 | Plane3 GetPlane(const int face) const;
|
---|
[2911] | 199 | /** Returns
|
---|
| 200 | 0 if box intersects plane
|
---|
| 201 | 1 if box in front of plane
|
---|
| 202 | -1 if box behind plane
|
---|
| 203 | */
|
---|
| 204 | int Side(const Plane3 &plane) const;
|
---|
| 205 | /** Calculates the intersection of the polyhedron with the box.
|
---|
| 206 | */
|
---|
[2913] | 207 | Polyhedron *CalcIntersection(const Polyhedron &polyhedron) const;
|
---|
[2929] | 208 | /** Tests for intersection of the ray with the box.
|
---|
| 209 | */
|
---|
| 210 | bool Intersects(const SimpleRay &ray, float &tnear, float &tfar) const;
|
---|
| 211 | /** Extracts the box sides as polygons.
|
---|
| 212 | */
|
---|
| 213 | void ExtractPolygons(PolygonContainer &polys) const;
|
---|
[2747] | 214 |
|
---|
| 215 |
|
---|
[2751] | 216 | ////////////
|
---|
| 217 | //-- friend functions
|
---|
| 218 |
|
---|
[2755] | 219 | /// Overlap returns 1 if the two axis-aligned boxes overlap .. even weakly
|
---|
| 220 | friend inline bool Overlap(const AxisAlignedBox3 &, const AxisAlignedBox3 &);
|
---|
| 221 |
|
---|
| 222 | /// Overlap returns 1 if the two axis-aligned boxes overlap .. only strongly
|
---|
| 223 | friend inline bool OverlapS(const AxisAlignedBox3 &,const AxisAlignedBox3 &);
|
---|
| 224 |
|
---|
[2911] | 225 | /** Overlap returns 1 if the two axis-aligned boxes overlap for a given epsilon.
|
---|
| 226 | If eps > 0.0, then the boxes has to have the real intersection
|
---|
[2755] | 227 | box, if eps < 0.0, then the boxes need not intersect really, they
|
---|
| 228 | can be at eps distance in the projection.
|
---|
| 229 | */
|
---|
| 230 | friend inline bool Overlap(const AxisAlignedBox3 &, const AxisAlignedBox3 &, float eps);
|
---|
| 231 |
|
---|
| 232 |
|
---|
[2751] | 233 | // Returns the smallest axis-aligned box that includes all points
|
---|
| 234 | // inside the two given boxes.
|
---|
| 235 | friend inline AxisAlignedBox3 Union(const AxisAlignedBox3 &x,
|
---|
| 236 | const AxisAlignedBox3 &y);
|
---|
| 237 |
|
---|
| 238 | // Returns the intersection of two axis-aligned boxes.
|
---|
| 239 | friend inline AxisAlignedBox3 Intersect(const AxisAlignedBox3 &x,
|
---|
| 240 | const AxisAlignedBox3 &y);
|
---|
| 241 |
|
---|
| 242 | // Given 4x4 matrix, transform the current box to new one.
|
---|
| 243 | friend inline AxisAlignedBox3 Transform(const AxisAlignedBox3 &box,
|
---|
| 244 | const Matrix4x4 &tform);
|
---|
| 245 |
|
---|
| 246 |
|
---|
| 247 | // returns true when two boxes are completely equal
|
---|
| 248 | friend inline int operator== (const AxisAlignedBox3 &A,
|
---|
| 249 | const AxisAlignedBox3 &B);
|
---|
| 250 |
|
---|
| 251 | // input and output operator with stream
|
---|
| 252 | friend std::ostream& operator<<(std::ostream &s, const AxisAlignedBox3 &A);
|
---|
| 253 | friend std::istream& operator>>(std::istream &s, AxisAlignedBox3 &A);
|
---|
| 254 |
|
---|
| 255 |
|
---|
| 256 |
|
---|
[2747] | 257 | // The vertices that form boundaries of the projected bounding box
|
---|
| 258 | // for all the regions possible, number of regions is 3^3 = 27,
|
---|
| 259 | // since two parallel sides of bbox forms three disjoint spaces
|
---|
| 260 | // the vertices are given in anti-clockwise order .. stopped by -1 elem.
|
---|
| 261 | static const int bvertices[27][9];
|
---|
| 262 |
|
---|
| 263 | // The list of all faces visible from a given region (except region 13)
|
---|
| 264 | // the faces are identified by triple: (axis, min-vertex, max-vertex),
|
---|
| 265 | // that is maximaly three triples are defined. axis = 0 (x-axis),
|
---|
| 266 | // axis = 1 (y-axis), axis = 2 (z-axis), -1 .. terminator. Is is always
|
---|
| 267 | // true that: min-vertex < max-vertex for all coordinates excluding axis
|
---|
| 268 | static const int bfaces[27][10];
|
---|
| 269 |
|
---|
| 270 | // The correct corners indexed starting from entry face to exit face
|
---|
| 271 | // first index determines entry face, second index exit face, and
|
---|
| 272 | // the two numbers (indx, inc) determines: ind = the index on the exit
|
---|
| 273 | // face, when starting from the vertex 0 on entry face, 'inc' is
|
---|
| 274 | // the increment when we go on entry face in order 0,1,2,3 to create
|
---|
| 275 | // convex shaft with the rectangle on exit face. That is, inc = -1 or 1.
|
---|
| 276 | static const int pairFaceRects[6][6][2];
|
---|
| 277 |
|
---|
| 278 | // The vertices that form CLOSEST points with respect to the region
|
---|
| 279 | // for all the regions possible, number of regions is 3^3 = 27,
|
---|
| 280 | // since two parallel sides of bbox forms three disjoint spaces.
|
---|
| 281 | // The vertices are given in anti-clockwise order, stopped by -1 elem,
|
---|
| 282 | // at most 8 points, at least 1 point.
|
---|
| 283 | static const int cvertices[27][9];
|
---|
| 284 | static const int csvertices[27][6];
|
---|
| 285 |
|
---|
| 286 | // The vertices that form FARTHEST points with respect to the region
|
---|
| 287 | // for all the regions possible, number of regions is 3^3 = 27,
|
---|
| 288 | // since two parallel sides of bbox forms three disjoint spaces.
|
---|
| 289 | // The vertices are given in anti-clockwise order, stopped by -1 elem,
|
---|
| 290 | // at most 8 points, at least 1 point.
|
---|
| 291 | static const int fvertices[27][9];
|
---|
| 292 | static const int fsvertices[27][9];
|
---|
| 293 |
|
---|
[2755] | 294 | /** Returns the vertex index nearest from the plane specified by the normal.
|
---|
| 295 | */
|
---|
| 296 | static int GetIndexNearestVertex(const Vector3 &vecPlaneNormal);
|
---|
| 297 | /** Returns the vertwx index farthest from the plane specified by the normal.
|
---|
| 298 | */
|
---|
| 299 | static int GetIndexFarthestVertex(const Vector3 &vecPlaneNormal);
|
---|
| 300 |
|
---|
| 301 |
|
---|
| 302 |
|
---|
[2751] | 303 | protected:
|
---|
| 304 |
|
---|
| 305 | Vector3 mMin, mMax;
|
---|
[2747] | 306 | };
|
---|
| 307 |
|
---|
| 308 |
|
---|
| 309 | // --------------------------------------------------------------------------
|
---|
| 310 | // Implementation of inline (member) functions
|
---|
| 311 |
|
---|
| 312 | inline bool
|
---|
| 313 | Overlap(const AxisAlignedBox3 &x, const AxisAlignedBox3 &y)
|
---|
| 314 | {
|
---|
| 315 | if (x.mMax.x < y.mMin.x ||
|
---|
| 316 | x.mMin.x > y.mMax.x ||
|
---|
| 317 | x.mMax.y < y.mMin.y ||
|
---|
| 318 | x.mMin.y > y.mMax.y ||
|
---|
| 319 | x.mMax.z < y.mMin.z ||
|
---|
| 320 | x.mMin.z > y.mMax.z) {
|
---|
| 321 | return false;
|
---|
| 322 | }
|
---|
| 323 | return true;
|
---|
| 324 | }
|
---|
| 325 |
|
---|
| 326 | inline bool
|
---|
| 327 | OverlapS(const AxisAlignedBox3 &x, const AxisAlignedBox3 &y)
|
---|
| 328 | {
|
---|
| 329 | if (x.mMax.x <= y.mMin.x ||
|
---|
| 330 | x.mMin.x >= y.mMax.x ||
|
---|
| 331 | x.mMax.y <= y.mMin.y ||
|
---|
| 332 | x.mMin.y >= y.mMax.y ||
|
---|
| 333 | x.mMax.z <= y.mMin.z ||
|
---|
| 334 | x.mMin.z >= y.mMax.z) {
|
---|
| 335 | return false;
|
---|
| 336 | }
|
---|
| 337 | return true;
|
---|
| 338 | }
|
---|
| 339 |
|
---|
| 340 | inline bool
|
---|
| 341 | Overlap(const AxisAlignedBox3 &x, const AxisAlignedBox3 &y, float eps)
|
---|
| 342 | {
|
---|
| 343 | if ( (x.mMax.x - eps) < y.mMin.x ||
|
---|
| 344 | (x.mMin.x + eps) > y.mMax.x ||
|
---|
| 345 | (x.mMax.y - eps) < y.mMin.y ||
|
---|
| 346 | (x.mMin.y + eps) > y.mMax.y ||
|
---|
| 347 | (x.mMax.z - eps) < y.mMin.z ||
|
---|
| 348 | (x.mMin.z + eps) > y.mMax.z ) {
|
---|
| 349 | return false;
|
---|
| 350 | }
|
---|
| 351 | return true;
|
---|
| 352 | }
|
---|
| 353 |
|
---|
| 354 | inline AxisAlignedBox3
|
---|
| 355 | Intersect(const AxisAlignedBox3 &x, const AxisAlignedBox3 &y)
|
---|
| 356 | {
|
---|
| 357 | if (x.Unbounded())
|
---|
| 358 | return y;
|
---|
| 359 | else
|
---|
| 360 | if (y.Unbounded())
|
---|
| 361 | return x;
|
---|
| 362 | AxisAlignedBox3 ret = x;
|
---|
| 363 | if (Overlap(ret, y)) {
|
---|
| 364 | Maximize(ret.mMin, y.mMin);
|
---|
| 365 | Minimize(ret.mMax, y.mMax);
|
---|
| 366 | return ret;
|
---|
| 367 | }
|
---|
| 368 | else // Null intersection.
|
---|
| 369 | return AxisAlignedBox3(Vector3(0), Vector3(0));
|
---|
| 370 | // return AxisAlignedBox3(Vector3(0), Vector3(-1));
|
---|
| 371 | }
|
---|
| 372 |
|
---|
| 373 | inline AxisAlignedBox3
|
---|
| 374 | Union(const AxisAlignedBox3 &x, const AxisAlignedBox3 &y)
|
---|
| 375 | {
|
---|
| 376 | Vector3 min = x.mMin;
|
---|
| 377 | Vector3 max = x.mMax;
|
---|
| 378 | Minimize(min, y.mMin);
|
---|
| 379 | Maximize(max, y.mMax);
|
---|
| 380 | return AxisAlignedBox3(min, max);
|
---|
| 381 | }
|
---|
| 382 |
|
---|
| 383 | inline AxisAlignedBox3
|
---|
| 384 | Transform(const AxisAlignedBox3 &box, const Matrix4x4 &tform)
|
---|
| 385 | {
|
---|
| 386 | Vector3 mmin(MAXFLOAT);
|
---|
| 387 | Vector3 mmax(-MAXFLOAT);
|
---|
[2802] | 388 |
|
---|
[2747] | 389 | AxisAlignedBox3 ret(mmin, mmax);
|
---|
[2802] | 390 |
|
---|
[2747] | 391 | ret.Include(tform * Vector3(box.mMin.x, box.mMin.y, box.mMin.z));
|
---|
| 392 | ret.Include(tform * Vector3(box.mMin.x, box.mMin.y, box.mMax.z));
|
---|
| 393 | ret.Include(tform * Vector3(box.mMin.x, box.mMax.y, box.mMin.z));
|
---|
| 394 | ret.Include(tform * Vector3(box.mMin.x, box.mMax.y, box.mMax.z));
|
---|
| 395 | ret.Include(tform * Vector3(box.mMax.x, box.mMin.y, box.mMin.z));
|
---|
| 396 | ret.Include(tform * Vector3(box.mMax.x, box.mMin.y, box.mMax.z));
|
---|
| 397 | ret.Include(tform * Vector3(box.mMax.x, box.mMax.y, box.mMin.z));
|
---|
| 398 | ret.Include(tform * Vector3(box.mMax.x, box.mMax.y, box.mMax.z));
|
---|
[2802] | 399 |
|
---|
[2747] | 400 | return ret;
|
---|
| 401 | }
|
---|
| 402 |
|
---|
| 403 | inline float RatioOfOverlap(const AxisAlignedBox3 &box1, const AxisAlignedBox3 &box2)
|
---|
| 404 | {
|
---|
| 405 | // return ratio of intersection to union
|
---|
| 406 | const AxisAlignedBox3 bisect = Intersect(box1, box2);
|
---|
| 407 | const AxisAlignedBox3 bunion = Union(box1, box2);
|
---|
| 408 |
|
---|
| 409 | return bisect.GetVolume() / bunion.GetVolume();
|
---|
| 410 | }
|
---|
| 411 |
|
---|
| 412 | inline int operator==(const AxisAlignedBox3 &A, const AxisAlignedBox3 &B)
|
---|
| 413 | {
|
---|
| 414 | return (A.mMin == B.mMin) && (A.mMax == B.mMax);
|
---|
| 415 | }
|
---|
| 416 |
|
---|
| 417 |
|
---|
[2751] | 418 | }
|
---|
[2747] | 419 |
|
---|
| 420 |
|
---|
| 421 | #endif
|
---|