source: GTP/trunk/App/Demos/Vis/FriendlyCulling/src/AxisAlignedBox3.h @ 3318

Revision 3318, 14.6 KB checked in by mattausch, 16 years ago (diff)

played around with reprojection, cleaned up code

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