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