1 /* Copyright Jukka Jyl�nki
2
3    Licensed under the Apache License, Version 2.0 (the "License");
4    you may not use this file except in compliance with the License.
5    You may obtain a copy of the License at
6
7        http://www.apache.org/licenses/LICENSE-2.0
8
9    Unless required by applicable law or agreed to in writing, software
10    distributed under the License is distributed on an "AS IS" BASIS,
11    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12    See the License for the specific language governing permissions and
13    limitations under the License. */
14
15 /** @file AABB.h
16         @author Jukka Jyl�nki
17         @brief The Axis-Aligned Bounding Box (AABB) geometry object. */
18 #pragma once
19
20 #include "../MathGeoLibFwd.h"
21 #include "../Math/float3.h"
22 #include "../Math/SSEMath.h"
23
24 #ifdef MATH_AUTOMATIC_SSE
25 #include "../Math/float4.h"
26 #endif
27
28 #ifdef MATH_OGRE_INTEROP
29 #include <OgreAxisAlignedBox.h>
30 #endif
31 #ifdef MATH_URHO3D_INTEROP
32 #include <Urho3D/Math/BoundingBox.h>
33 #endif
34
35 MATH_BEGIN_NAMESPACE
36
37 /// A 3D axis-aligned bounding box.
38 /** This data structure can be used to represent coarse bounds of objects, in situations where detailed triangle-level
39         computations can be avoided. In physics systems, bounding boxes are used as an efficient early-out test for geometry
40         intersection queries.
41         
42         The 'axis-aligned' part in the name means that the local axes of this bounding box are restricted to align with the
43         axes of the world space coordinate system. This makes computations involving AABB's very fast, since AABB's cannot
44         be arbitrarily oriented in the space with respect to each other.
45
46         If you need to represent a box in 3D space with arbitrary orientation, see the class OBB. */
47 class ALIGN16 AABB
48 {
49 public:
50
51         /// Specifies the minimum extent of this AABB in the world space x, y and z axes.
52         vec minPoint;
53         /// Specifies the maximum extent of this AABB in the world space x, y and z axes. [similarOverload: minPoint]
54         vec maxPoint;
55
56         /// The default constructor does not initialize any members of this class.
57         /** This means that the values of the members minPoint and maxPoint are undefined after creating a new AABB using this
58                 default constructor. Remember to assign to them before use.
59                 @see minPoint, maxPoint. */
60         AABB() {}
61
62         /// Constructs this AABB by specifying the minimum and maximum extending corners of the box.
63         /** @see minPoint, maxPoint. */
64         AABB(const vec &minPoint, const vec &maxPoint);
65
66         /// Constructs this AABB to enclose the given OBB.
67         /** This constructor computes the optimal minimum volume AABB that encloses the given OBB.
68                 @note Since an AABB cannot generally represent an OBB, this conversion is not exact, but the returned AABB
69                         specifies a larger volume.                      
70                 @see class OBB. */
71         explicit AABB(const OBB &obb);
72
73         /// Constructs this AABB to enclose the given Sphere.
74         /** @see class Sphere. */
75         explicit AABB(const Sphere &s);
76
77         FORCE_INLINE static int NumFaces() { return 6; }
78         FORCE_INLINE static int NumEdges() { return 12; }
79         FORCE_INLINE static int NumVertices() { return 8; }
80
81         /// Returns the minimum world-space coordinate along the given axis.
82         float MinX() const { return minPoint.x; }
83         float MinY() const { return minPoint.y; } ///< [similarOverload: MinX]
84         float MinZ() const { return minPoint.z; } ///< [similarOverload: MinX]
85         /// Returns the maximum world-space coordinate along the given axis.
86         float MaxX() const { return maxPoint.x; }
87         float MaxY() const { return maxPoint.y; } ///< [similarOverload: MaxX]
88         float MaxZ() const { return maxPoint.z; } ///< [similarOverload: MaxX]
89
90         /// Sets this structure to a degenerate AABB that does not have any volume.
91         /** This function is useful for initializing the AABB to "null" before a loop of calls to Enclose(),
92                 which incrementally expands the bounds of this AABB to enclose the given objects.
93                 @see Enclose(). */
94         void SetNegativeInfinity();
95
96         /// Sets this AABB by specifying its center and size.
97         /** @param center The center point of this AABB.
98                 @param size A vector that specifies the size of this AABB in x, y and z directions.
99                 @see SetFrom(), FromCenterAndSize(). */
100         void SetFromCenterAndSize(const vec &center, const vec &size);
101
102         /// Sets this AABB to enclose the given OBB.
103         /** This function computes the minimal axis-aligned bounding box for the given oriented bounding box. If the orientation
104                 of the OBB is not aligned with the world axes, this conversion is not exact and loosens the volume of the bounding box.
105                 @param obb The oriented bounding box to convert into this AABB.
106                 @todo Implement SetFrom(Polyhedron).
107                 @see SetCenter(), class OBB. */
108         void SetFrom(const OBB &obb);
109
110         // Computes the minimal enclosing AABB of the given polyhedron.         
111         /* This function computes the smallest AABB (in terms of volume) that contains the given polyhedron, and stores
112                 the result in this structure.
113                 @note An AABB cannot generally exactly represent a polyhedron. Converting a polyhedron to an AABB loses some
114                 features of the polyhedron.
115                 @return If the given polyhedron is closed, this function succeeds and returns true. If the polyhedron is uncapped
116                         (has infinite volume), this function does not modify this data structure, but returns false. */
117 //      bool SetFrom(const Polyhedron &polyhedron);
118
119         /// Sets this AABB to enclose the given sphere.
120         /** This function computes the smallest possible AABB (in terms of volume) that contains the given sphere, and stores the result in this structure. */
121         void SetFrom(const Sphere &s);
122
123         /// Sets this AABB to enclose the given set of points.
124         /** @param pointArray A pointer to an array of points to enclose inside an AABB.
125                 @param numPoints The number of elements in the pointArray list.
126                 @see MinimalEnclosingAABB(). */
127         void SetFrom(const vec *pointArray, int numPoints);
128
129         /// Converts this AABB to a polyhedron.
130         /** This function returns a polyhedron representation of this AABB. This conversion is exact, meaning that the returned
131                 polyhedron represents the same set of points that this AABB does.
132                 @see class Polyhedron, ToPBVolume(), ToOBB(). */
133         Polyhedron ToPolyhedron() const;
134
135         /// Converts this AABB to a PBVolume.
136         /** This function returns a plane-bounded volume representation of this AABB. The conversion is exact, meaning that the
137                 returned PBVolume<6> represents exactly the same set of points that this AABB does.
138                 @see ToPolyhedron(), ToOBB(). */
139         PBVolume<6> ToPBVolume() const;
140
141         /// Converts this AABB to an OBB.
142         /** This function returns an OBB representation of this AABB. This conversion is exact, meaning that the returned
143                 OBB represents the same set of points than this AABB.
144                 @see class OBB, ToPolyhedron(), ToPBVolume(). */
145         OBB ToOBB() const;
146
147         /// Returns the smallest sphere that contains this AABB.
148         /** This function computes the minimal volume sphere that contains all the points inside this AABB.
149                 @see MaximalContainedSphere(). */
150         Sphere MinimalEnclosingSphere() const;
151
152         /// Returns the largest sphere that can fit inside this AABB.
153         /** This function computes the largest sphere that can fit inside this AABB. This sphere is unique up to the center point
154                 of the sphere. The returned sphere will be positioned to the same center point as this AABB.
155                 @see MinimalEnclosingSphere(). */
156         Sphere MaximalContainedSphere() const;
157
158         /// Tests if this AABB is finite.
159         /** @return True if the member variables of this AABB are valid floats and do not contain NaNs or infs, and false otherwise.
160                 @see IsDegenerate(), minPoint, maxPoint. */
161         bool IsFinite() const;
162
163         /// Tests if this AABB is degenerate.
164         /** @return True if this AABB does not span a strictly positive volume.
165                 @see IsFinite(), Volume(), minPoint, maxPoint. */
166         bool IsDegenerate() const;
167
168         /// @return The center point of this AABB.
169         vec CenterPoint() const;
170         /// [similarOverload: CenterPoint]
171         vec Centroid() const { return CenterPoint(); }
172
173         /// Quickly returns an arbitrary point inside this AABB. Used in GJK intersection test.
174         vec AnyPointFast() const { return minPoint; }
175
176         /// Generates a point inside this AABB.
177         /** @param x A normalized value between [0,1]. This specifies the point position along the world x axis.
178                 @param y A normalized value between [0,1]. This specifies the point position along the world y axis.
179                 @param z A normalized value between [0,1]. This specifies the point position along the world z axis.
180                 @return A point inside this AABB at point specified by given parameters.
181                 @see Edge(), CornerPoint(), PointOnEdge(), FaceCenterPoint(), FacePoint(). */
182         vec PointInside(float x, float y, float z) const;
183
184         /// Returns an edge of this AABB.
185         /** @param edgeIndex The index of the edge line segment to get, in the range [0, 11].
186                 @todo Specify which index generates which edge.
187                 @see PointInside(), CornerPoint(), PointOnEdge(), FaceCenterPoint(), FacePoint(). */
188         LineSegment Edge(int edgeIndex) const;
189
190         /// Returns a corner point of this AABB.
191         /** This function generates one of the eight corner points of this AABB.
192                 @param cornerIndex The index of the corner point to generate, in the range [0, 7].
193                         The points are returned in the order 0: ---, 1: --+, 2: -+-, 3: -++, 4: +--, 5: +-+, 6: ++-, 7: +++. (corresponding the XYZ axis directions).
194                 @todo Draw which index generates which corner point.
195                 @see PointInside(), Edge(), PointOnEdge(), FaceCenterPoint(), FacePoint(), GetCornerPoints(). */
196         vec CornerPoint(int cornerIndex) const;
197
198         /// Computes an extreme point of this AABB in the given direction.
199         /** An extreme point is a farthest point of this AABB in the given direction. Given a direction,
200                 this point is not necessarily unique.
201                 @param direction The direction vector of the direction to find the extreme point. This vector may
202                         be unnormalized, but may not be null.
203                 @return An extreme point of this AABB in the given direction. The returned point is always a
204                         corner point of this AABB.
205                 @see CornerPoint(). */
206         vec ExtremePoint(const vec &direction) const;
207         vec ExtremePoint(const vec &direction, float &projectionDistance) const;
208
209         /// Returns a point on an edge of this AABB.
210         /** @param edgeIndex The index of the edge to generate a point to, in the range [0, 11]. @todo Document which index generates which one.
211                 @param u A normalized value between [0,1]. This specifies the relative distance of the point along the edge.
212                 @see PointInside(), CornerPoint(), CornerPoint(), FaceCenterPoint(), FacePoint(). */
213         vec PointOnEdge(int edgeIndex, float u) const;
214
215         /// Returns the point at the center of the given face of this AABB.
216         /** @param faceIndex The index of the AABB face to generate the point at. The valid range is [0, 5].
217                         This index corresponds to the planes in the order (-X, +X, -Y, +Y, -Z, +Z).
218                 @see PointInside(), CornerPoint(), PointOnEdge(), PointOnEdge(), FacePoint(). */
219         vec FaceCenterPoint(int faceIndex) const;
220
221         /// Generates a point at the surface of the given face of this AABB.
222         /** @param faceIndex The index of the AABB face to generate the point at. The valid range is [0, 5].
223                         This index corresponds to the planes in the order (-X, +X, -Y, +Y, -Z, +Z).
224                 @param u A normalized value between [0, 1].
225                 @param v A normalized value between [0, 1].
226                 @see PointInside(), CornerPoint(), PointOnEdge(), PointOnEdge(), FaceCenterPoint(). */
227         vec FacePoint(int faceIndex, float u, float v) const;
228
229         /// Returns the surface normal direction vector the given face points towards.
230         /** @param faceIndex The index of the AABB face to generate the point at. The valid range is [0, 5].
231                         This index corresponds to the planes in the order (-X, +X, -Y, +Y, -Z, +Z).
232                 @see FacePoint(), FacePlane(). */
233         vec FaceNormal(int faceIndex) const;
234
235         /// Computes the plane equation of the given face of this AABB.
236         /** @param faceIndex The index of the AABB face. The valid range is [0, 5].
237                         This index corresponds to the planes in the order (-X, +X, -Y, +Y, -Z, +Z).
238                 @return The plane equation the specified face lies on. The normal of this plane points outwards from this AABB.
239                 @see FacePoint(), FaceNormal(), GetFacePlanes(). */
240         Plane FacePlane(int faceIndex) const;
241
242         /// Fills an array with all the eight corner points of this AABB.
243         /** @param outPointArray [out] The array to write the points to. Must have space for 8 elements.
244                 @see CornerPoint(). */
245         void GetCornerPoints(vec *outPointArray) const;
246
247         /// Fills an array with all the six planes of this AABB.
248         /** @param outPlaneArray [out] The array to write the planes to. Must have space for 6 elements.
249                 @see FacePlane(). */
250         void GetFacePlanes(Plane *outPlaneArray) const;
251
252         /// Generates an AABB that encloses the given point set.
253         /** This function finds the smallest AABB that contains the given set of points.
254                 @param pointArray A pointer to an array of points to enclose inside an AABB.
255                 @param numPoints The number of elements in the pointArray list.
256                 @see SetFrom(). */
257         static AABB MinimalEnclosingAABB(const vec *pointArray, int numPoints);
258
259         /// Finds the most extremal points along the three world axes simultaneously.
260         /** @param pointArray A pointer to an array of points to process.
261                 @param numPoints The number of elements in the pointArray list.
262                 @param minx [out] Receives the point that has the smallest x coordinate.
263                 @param maxx [out] Receives the point that has the largest x coordinate.
264                 @param miny [out] Receives the point that has the smallest y coordinate.
265                 @param maxy [out] Receives the point that has the largest y coordinate.
266                 @param minz [out] Receives the point that has the smallest z coordinate.
267                 @param maxz [out] Receives the point that has the largest z coordinate. */
268         static void ExtremePointsAlongAABB(const vec *pointArray, int numPoints, int &minx, int &maxx, int &miny, int &maxy, int &minz, int &maxz);
269
270         /// Creates a new AABB given is center position and size along the X, Y and Z axes.
271         /** @see SetCenter(). */
272         static AABB FromCenterAndSize(const vec &aabbCenterPos, const vec &aabbSize);
273
274         /// Returns the side lengths of this AABB in x, y and z directions.
275         /** The returned vector is equal to the diagonal vector of this AABB, i.e. it spans from the
276                 minimum corner of the AABB to the maximum corner of the AABB.
277                 @see HalfSize(), Diagonal(). */
278         vec Size() const;
279
280         /// [similarOverload: Size]
281         /** Returns Size()/2.
282                 @see Size(), HalfDiagonal(). */
283         vec HalfSize() const;
284
285         /// Returns the diameter vector of this AABB.
286         /** @note For AABB, Diagonal() and Size() are the same concept. These functions are provided for symmetry
287                 with the OBB class.
288                 @see Size(), HalfDiagonal(). */
289         vec Diagonal() const { return Size(); }
290
291         /// [similarOverload: Diagonal]
292         /** Returns Diagonal()/2.
293                 @see Diagonal(), HalfSize(). */
294         vec HalfDiagonal() const { return HalfSize(); }
295
296         /// Computes the volume of this AABB.
297         /** @see SurfaceArea(), IsDegenerate(). */
298         float Volume() const;
299
300         /// Computes the surface area of the faces of this AABB.
301         /** @see Volume(). */
302         float SurfaceArea() const;
303
304         /// Generates a random point inside this AABB.
305         /** The points are distributed uniformly.
306                 @see RandomPointOnSurface(), RandomPointOnEdge(), RandomCornerPoint(). */
307         vec RandomPointInside(LCG &rng) const;
308
309         /// Generates a random point on a random face of this AABB.
310         /** The points are distributed uniformly.
311                 @see RandomPointInside(), RandomPointOnEdge(), RandomCornerPoint(). */
312         vec RandomPointOnSurface(LCG &rng) const;
313
314         /// Generates a random point on a random edge of this AABB.
315         /** The points are distributed uniformly.
316                 @see RandomPointInside(), RandomPointOnSurface(), RandomCornerPoint(). */
317         vec RandomPointOnEdge(LCG &rng) const;
318
319         /// Picks a random corner point of this AABB.
320         /** The points are distributed uniformly.
321                 @see RandomPointInside(), RandomPointOnSurface(), RandomPointOnEdge(). */
322         vec RandomCornerPoint(LCG &rng) const;
323
324         /// Translates this AABB in world space.
325         /** @param offset The amount of displacement to apply to this AABB, in world space coordinates.
326                 @see Scale(), Transform(). */
327         void Translate(const vec &offset);
328
329         /// Applies a uniform scale to this AABB.
330         /** This function scales this AABB structure in-place, using the given center point as the origin
331                 for the scaling operation.
332                 @param centerPoint Specifies the center of the scaling operation, in world space.
333                 @param scaleFactor The uniform scale factor to apply to each world space axis.
334                 @see Translate(), Transform(). */
335         void Scale(const vec &centerPoint, float scaleFactor);
336
337         /// Applies a non-uniform scale to this AABB.
338         /** This function scales this AABB structure in-place, using the given center point as the origin
339                 for the scaling operation.
340                 @param centerPoint Specifies the center of the scaling operation, in world space.
341                 @param scaleFactor The non-uniform scale factors to apply to each world space axis.
342                 @see Translate(), Transform(). */
343         void Scale(const vec &centerPoint, const vec &scaleFactor);
344
345         /// Applies a transformation to this AABB.
346         /** This function transforms this AABB with the given transformation, and then recomputes this AABB
347                 to enclose the resulting oriented bounding box. This transformation is not exact and in general, calling
348                 this function results in the loosening of the AABB bounds.
349                 @param transform The transformation to apply to this AABB. This function assumes that this
350                         transformation does not contain shear, nonuniform scaling or perspective properties, i.e. that the fourth
351                         row of the float4x4 is [0 0 0 1].
352                 @see Translate(), Scale(), Transform(), classes float3x3, float3x4, float4x4, Quat. */
353         void TransformAsAABB(const float3x3 &transform);
354         void TransformAsAABB(const float3x4 &transform);
355         void TransformAsAABB(const float4x4 &transform);
356         void TransformAsAABB(const Quat &transform);
357
358         /// Applies a transformation to this AABB and returns the resulting OBB.
359         /** Transforming an AABB produces an oriented bounding box. This set of functions does not apply the transformation
360                 to this object itself, but instead returns the OBB that results in the transformation.
361                 @param transform The transformation to apply to this AABB. This function assumes that this
362                         transformation does not contain shear, nonuniform scaling or perspective properties, i.e. that the fourth
363                         row of the float4x4 is [0 0 0 1].
364                 @see Translate(), Scale(), TransformAsAABB(), classes float3x3, float3x4, float4x4, Quat. */
365         OBB Transform(const float3x3 &transform) const;
366         OBB Transform(const float3x4 &transform) const;
367         OBB Transform(const float4x4 &transform) const;
368         OBB Transform(const Quat &transform) const;
369
370         /// Computes the closest point inside this AABB to the given point.
371         /** If the target point lies inside this AABB, then that point is returned.
372                 @see Distance(), Contains(), Intersects().
373                 @todo Add ClosestPoint(Line/Ray/LineSegment/Plane/Triangle/Polygon/Circle/Disc/AABB/OBB/Sphere/Capsule/Frustum/Polyhedron). */
374         vec ClosestPoint(const vec &targetPoint) const;
375
376         /// Computes the distance between this AABB and the given object.
377         /** This function finds the nearest pair of points on this and the given object, and computes their distance.
378                 If the two objects intersect, or one object is contained inside the other, the returned distance is zero.
379                 @todo Add AABB::Distance(Line/Ray/LineSegment/Plane/Triangle/Polygon/Circle/Disc/AABB/OBB/Capsule/Frustum/Polyhedron).
380                 @see Contains(), Intersects(), ClosestPoint(). */
381         float Distance(const vec &point) const;
382         float Distance(const Sphere &sphere) const;
383
384         /// Tests if the given object is fully contained inside this AABB.
385         /** This function returns true if the given object lies inside this AABB, and false otherwise.
386                 @note The comparison is performed using less-or-equal, so the faces of this AABB count as being inside, but
387                         due to float inaccuracies, this cannot generally be relied upon.
388                 @todo Add Contains(Circle/Disc/Sphere/Capsule).
389                 @see Distance(), Intersects(), ClosestPoint(). */
390         bool Contains(const vec &point) const;
391         bool Contains(const LineSegment &lineSegment) const;
392         bool Contains(const vec &aabbMinPoint, const vec &aabbMaxPoint) const;
393         bool Contains(const AABB &aabb) const { return Contains(aabb.minPoint, aabb.maxPoint); }
394         bool Contains(const OBB &obb) const;
395         bool Contains(const Sphere &sphere) const;
396         bool Contains(const Triangle &triangle) const;
397         bool Contains(const Polygon &polygon) const;
398         bool Contains(const Frustum &frustum) const;
399         bool Contains(const Polyhedron &polyhedron) const;
400         bool Contains(const Capsule &capsule) const;
401
402         /// Tests whether this AABB and the given object intersect.
403         /** Both objects are treated as "solid", meaning that if one of the objects is fully contained inside
404                 another, this function still returns true. (e.g. in case a line segment is contained inside this AABB,
405                 or this AABB is contained inside a Sphere, etc.)
406                 @param ray The first parameter of this function specifies the other object to test against.
407                 @param dNear [out] If specified, receives the parametric distance along the line denoting where the
408                         line entered this AABB.
409                 @param dFar [out] If specified, receives the parametric distance along the line denoting where the
410                         line exited this AABB.
411                 @see Contains(), Distance(), ClosestPoint().
412                 @note If you do not need the intersection intervals, you should call the functions without these
413                         parameters in the function signature for optimal performance.
414                 @todo Add Intersects(Circle/Disc). */
415         bool Intersects(const Ray &ray, float &dNear, float &dFar) const;
416         bool Intersects(const Ray &ray) const;
417         bool Intersects(const Line &line, float &dNear, float &dFar) const;
418         bool Intersects(const Line &line) const;
419         bool Intersects(const LineSegment &lineSegment, float &dNear, float &dFar) const;
420         bool Intersects(const LineSegment &lineSegment) const;
421         bool Intersects(const Plane &plane) const;
422         bool Intersects(const AABB &aabb) const;
423         bool Intersects(const OBB &obb) const;
424         /** For reference documentation on the Sphere-AABB intersection test, see Christer Ericson's Real-Time Collision Detection, p. 165. [groupSyntax]
425                 @param sphere The first parameter of this function specifies the other object to test against.
426                 @param closestPointOnAABB [out] Returns the closest point on this AABB to the given sphere. This pointer
427                         may be null. */
428         bool Intersects(const Sphere &sphere, vec *closestPointOnAABB = 0) const;
429         bool Intersects(const Capsule &capsule) const;
430         bool Intersects(const Triangle &triangle) const;
431         bool Intersects(const Polygon &polygon) const;
432         bool Intersects(const Frustum &frustum) const;
433         bool Intersects(const Polyhedron &polyhedron) const;
434
435         /// Projects this AABB onto the given axis.
436         /** @param axis The axis to project onto. This vector can be unnormalized.
437                 @param dMin [out] Returns the minimum extent of this AABB on the given axis.
438                 @param dMax [out] Returns the maximum extent of this AABB on the given axis. */
439         void ProjectToAxis(const vec &axis, float &dMin, float &dMax) const;
440
441         int UniqueFaceNormals(vec *out) const;
442         int UniqueEdgeDirections(vec *out) const;
443
444         /// Expands this AABB to enclose the given object.
445         /** This function computes an AABB that encloses both this AABB and the specified object, and stores the resulting
446                 AABB into this.
447                 @note The generated AABB is not necessarily the optimal enclosing AABB for this AABB and the given object. */
448         void Enclose(const vec &point);
449         void Enclose(const vec &aabbMinPoint, const vec &aabbMaxPoint);
450         void Enclose(const LineSegment &lineSegment);
451         void Enclose(const AABB &aabb) { Enclose(aabb.minPoint, aabb.maxPoint); }
452         void Enclose(const OBB &obb);
453         void Enclose(const Sphere &sphere);
454         void Enclose(const Triangle &triangle);
455         void Enclose(const Capsule &capsule);
456         void Enclose(const Frustum &frustum);
457         void Enclose(const Polygon &polygon);
458         void Enclose(const Polyhedron &polyhedron);
459         void Enclose(const vec *pointArray, int numPoints);
460
461         /// Generates an unindexed triangle mesh representation of this AABB.
462         /** @param numFacesX The number of faces to generate along the X axis. This value must be >= 1.
463                 @param numFacesY The number of faces to generate along the Y axis. This value must be >= 1.
464                 @param numFacesZ The number of faces to generate along the Z axis. This value must be >= 1.
465                 @param outPos [out] An array of size numVertices which will receive a triangle list
466                         of vertex positions. Cannot be null.
467                 @param outNormal [out] An array of size numVertices which will receive vertex normals.
468                         If this parameter is null, vertex normals are not returned.
469                 @param outUV [out] An array of size numVertices which will receive vertex UV coordinates.
470                         If this parameter is null, a UV mapping is not generated.
471                 @param ccwIsFrontFacing If true, then the front-facing direction of the faces will be the sides
472                         with counterclockwise winding order. Otherwise, the faces are generated in clockwise winding order.
473                 The number of vertices that outPos, outNormal and outUV must be able to contain is
474                 (x*y + x*z + y*z)*2*6. If x==y==z==1, then a total of 36 vertices are required. Call
475                 NumVerticesInTriangulation to obtain this value.
476                 @see ToPolyhedron(), ToEdgeList(), NumVerticesInTriangulation(). */
477         void Triangulate(int numFacesX, int numFacesY, int numFacesZ,
478                          vec *outPos, vec *outNormal, float2 *outUV,
479                          bool ccwIsFrontFacing) const;
480
481         /// Returns the number of vertices that the Triangulate() function will output with the given subdivision parameters.
482         /** @see Triangulate(). */
483         static int NumVerticesInTriangulation(int numFacesX, int numFacesY, int numFacesZ)
484         {
485                 return (numFacesX*numFacesY + numFacesX*numFacesZ + numFacesY*numFacesZ)*2*6;
486         }
487         
488         /// Generates an edge list representation of the edges of this AABB.
489         /** @param outPos [out] An array that contains space for at least 24 vertices (NumVerticesInEdgeList()).
490                 @see Triangulate(), Edge(), NumVerticesInEdgeList(). */
491         void ToEdgeList(vec *outPos) const;
492
493         /// Returns the number of vertices that the ToEdgeList() function will output.
494         /** @see ToEdgeList(). */
495         static int NumVerticesInEdgeList()
496         {
497                 return 4*3*2;
498         }
499
500 #ifdef MATH_ENABLE_STL_SUPPORT
501         /// Returns a human-readable representation of this AABB. Most useful for debugging purposes.
502         /** The returned string specifies the center point and the half-axes of this AABB. */
503         std::string ToString() const;
504         std::string SerializeToString() const;
505
506         /// Returns a string of C++ code that can be used to construct this object. Useful for generating test cases from badly behaving objects.
507         std::string SerializeToCodeString() const;
508 #endif
509
510         static AABB FromString(const char *str, const char **outEndStr = 0);
511 #ifdef MATH_ENABLE_STL_SUPPORT
512         static AABB FromString(const std::string &str) { return FromString(str.c_str()); }
513 #endif
514
515 #ifdef MATH_QT_INTEROP
516         operator QString() const { return toString(); }
517         QString toString() const { return QString::fromStdString(ToString()); }
518 #endif
519
520         /// Finds the set intersection of this and the given AABB.
521         /** @return This function returns the AABB that is contained in both this and the given AABB.
522                 @todo Add Intersection(OBB/Polyhedron). */
523         AABB Intersection(const AABB &aabb) const;
524
525         // Finds the set intersection of this AABB and the given OBB.
526         /* @return This function returns a Polyhedron that represents the set of points that are contained in this AABB
527                 and the given OBB. */
528 //      Polyhedron Intersection(const OBB &obb) const;
529
530         // Finds the set intersection of this AABB and the given Polyhedron.
531         /* @return This function returns a Polyhedron that represents the set of points that are contained in this AABB
532                 and the given Polyhedron. */
533 //      Polyhedron Intersection(const Polyhedron &polyhedron) const;
534
535         /// Computes the intersection of a line, ray or line segment and an AABB.
536         /** Based on "T. Kay, J. Kajiya. Ray Tracing Complex Scenes. SIGGRAPH 1986 vol 20, number 4. pp. 269-"
537                 http://www.siggraph.org/education/materials/HyperGraph/raytrace/rtinter3.htm
538                 @param linePos The starting position of the line.
539                 @param lineDir The direction of the line. This direction vector must be normalized!
540                 @param tNear [in, out] For the test, the input line is treated as a line segment. Pass in the signed distance
541                         from the line origin to the start of the line. For a Line-AABB test, -FLOAT_INF is typically passed here.
542                         For a Ray-AABB test, 0.0f should be inputted. If intersection occurs, the signed distance from line origin
543                         to the line entry point in the AABB is returned here.
544                 @param tFar [in, out] Pass in the signed distance from the line origin to the end of the line. For Line-AABB and
545                         Ray-AABB tests, pass in FLOAT_INF. For a LineSegment-AABB test, pass in the length of the line segment here.
546                         If intersection occurs, the signed distance from line origin to the line exit point in the AABB
547                         is returned here.
548                 @return True if an intersection occurs, false otherwise.
549                 @note This is a low level utility function. It may be more convenient to use one of the AABB::Intersects()
550                         functions instead.
551                 @see Intersects(). */
552         bool IntersectLineAABB(const vec &linePos, const vec &lineDir, float &tNear, float &tFar) const;
553
554         bool IntersectLineAABB_CPP(const vec &linePos, const vec &lineDir, float &tNear, float &tFar) const;
555 #ifdef MATH_SSE
556         bool IntersectLineAABB_SSE(const float4 &linePos, const float4 &lineDir, float tNear, float tFar) const;
557 #endif
558
559 #ifdef MATH_OGRE_INTEROP
560         AABB(const Ogre::AxisAlignedBox &other):minPoint(other.getMinimum()), maxPoint(other.getMaximum()) {}
561         operator Ogre::AxisAlignedBox() const { return Ogre::AxisAlignedBox(minPoint, maxPoint); }
562 #endif
563 #ifdef MATH_GRAPHICSENGINE_INTEROP
564         void Triangulate(VertexBuffer &vb, int numFacesX, int numFacesY, int numFacesZ, bool ccwIsFrontFacing) const;
565         void ToLineList(VertexBuffer &vb) const;
566 #endif
567 #ifdef MATH_URHO3D_INTEROP
568         AABB(const Urho3D::BoundingBox&other) : minPoint(other.min_), maxPoint(other.max_) {}
569         operator Urho3D::BoundingBox() const { return Urho3D::BoundingBox(minPoint, maxPoint); }
570 #endif
571
572         bool Equals(const AABB &rhs, float epsilon = 1e-3f) const { return minPoint.Equals(rhs.minPoint, epsilon) && maxPoint.Equals(rhs.maxPoint, epsilon); }
573
574         /// Compares whether this AABB and the given AABB are identical bit-by-bit in the underlying representation.
575         /** @note Prefer using this over e.g. memcmp, since there can be SSE-related padding in the structures. */
576         bool BitEquals(const AABB &other) const { return minPoint.BitEquals(other.minPoint) && maxPoint.BitEquals(other.maxPoint); }
577 };
578
579 OBB operator *(const float3x3 &transform, const AABB &aabb);
580 OBB operator *(const float3x4 &transform, const AABB &aabb);
581 OBB operator *(const float4x4 &transform, const AABB &aabb);
582 OBB operator *(const Quat &transform, const AABB &aabb);
583
584 #ifdef MATH_QT_INTEROP
585 Q_DECLARE_METATYPE(AABB)
586 Q_DECLARE_METATYPE(AABB*)
587 #endif
588
589 #ifdef MATH_ENABLE_STL_SUPPORT
590 std::ostream &operator <<(std::ostream &o, const AABB &aabb);
591 #endif
592
593 #ifdef MATH_SIMD
594 void AABBTransformAsAABB_SIMD(AABB &aabb, const float4x4 &m);
595 #endif
596
597 MATH_END_NAMESPACE