source: trunk/VUT/GtpVisibilityPreprocessor/src/AxisAlignedBox3.h @ 542

Revision 542, 17.3 KB checked in by mattausch, 19 years ago (diff)
Line 
1#ifndef _AxisAlignedBox3_H__
2#define _AxisAlignedBox3_H__
3
4#include "Rectangle3.h"
5#include "Matrix4x4.h"
6#include "Vector3.h"
7#include "Plane3.h"
8#include "Containers.h"
9
10class Ray;
11class Polygon3;
12class Mesh;
13
14// --------------------------------------------------------
15// CAABox class.
16//  This is a box in 3-space, defined by min and max
17//  corner vectors.  Many useful operations are defined
18//  on this
19// --------------------------------------------------------
20class AxisAlignedBox3
21{
22protected:
23  Vector3 mMin, mMax;
24public:
25  // Constructors.
26  AxisAlignedBox3() { }
27  AxisAlignedBox3(const Vector3 &nMin, const Vector3 &nMax)
28  {
29    mMin = nMin; mMax = nMax;
30  }
31
32  //  AxisAlignedBox3(const Vector3 &center, const float radius):min(center - Vector3(radius)),
33  //                                                  max(center + Vector3(radius)) {}
34
35  // initialization to the non existing bounding box
36  void Initialize() {
37    mMin = Vector3(MAXFLOAT);
38    mMax = Vector3(-MAXFLOAT);
39  }
40
41  // The center of the box
42  Vector3 Center() const { return 0.5 * (mMin + mMax); }
43 
44  // The diagonal of the box
45  Vector3 Diagonal() const { return (mMax -mMin); }
46
47  float Center(const int axis) const {
48    return  0.5f * (mMin[axis] + mMax[axis]);
49  }
50
51  float Min(const int axis) const {
52    return mMin[axis];
53  }
54
55  float Max(const int axis) const {
56    return  mMax[axis];
57  }
58
59  float Size(const int axis) const {
60    return  Max(axis) - Min(axis);
61  }
62
63  // Read-only const access tomMin and max vectors using references
64  const Vector3& Min() const { return mMin;}
65  const Vector3& Max() const { return mMax;}
66
67  void Enlarge (const Vector3 &v) {
68    mMax += v;
69    mMin -= v;
70  }
71
72
73  void SetMin(const Vector3 &v) {
74    mMin = v;
75  }
76
77  void SetMax(const Vector3 &v) {
78    mMax = v;
79  }
80
81  void SetMin(int axis, const float value) {
82   mMin[axis] = value;
83  }
84
85  void SetMax(int axis, const float value) {
86    mMax[axis] = value;
87  }
88
89  // Decrease box by given splitting plane
90  void Reduce(int axis, int right, float value) {
91    if ( (value >=mMin[axis]) && (value <= mMax[axis]) )
92      if (right)
93                                mMin[axis] = value;
94      else
95        mMax[axis] = value;
96  }
97       
98  // the size of the box along all the axes
99  Vector3 Size() const { return mMax - mMin; }
100
101  // Return whether the box is unbounded.  Unbounded boxes appear
102  // when unbounded objects such as quadric surfaces are included.
103  bool Unbounded() const;
104
105  // Expand the axis-aligned box to include the given object.
106  void Include(const Vector3 &newpt);
107  void Include(const Polygon3 &newpoly);
108  void Include(const AxisAlignedBox3 &bbox);
109  void Include(Mesh *mesh);
110  // Expand the axis-aligned box to include given values in particular axis
111  void Include(const int &axis, const float &newBound);
112
113 
114  int
115  Side(const Plane3 &plane) const;
116
117  // Overlap returns 1 if the two axis-aligned boxes overlap .. even weakly
118  friend inline bool Overlap(const AxisAlignedBox3 &, const AxisAlignedBox3 &);
119
120  // Overlap returns 1 if the two axis-aligned boxes overlap .. only strongly
121  friend inline bool OverlapS(const AxisAlignedBox3 &,const AxisAlignedBox3 &);
122
123  // Overlap returns 1 if the two axis-aligned boxes overlap for a given
124  // epsilon. If eps > 0.0, then the boxes has to have the real intersection
125  // box, if eps < 0.0, then the boxes need not intersect really, they
126  // can be at eps distance in the projection
127  friend inline bool Overlap(const AxisAlignedBox3 &,
128                             const AxisAlignedBox3 &,
129                             float eps);
130
131  // Includes returns true if a includes b (completely
132  bool Includes(const AxisAlignedBox3 &b) const;
133
134  virtual int IsInside(const Vector3 &v) const;
135 
136  // Test if the box is really sensefull
137  virtual bool IsCorrect();
138
139  // To answer true requires the box of real volume of non-zero value
140  bool IsSingularOrIncorrect() const;
141
142  // When the box is not of non-zero or negative surface area
143  bool IsCorrectAndNotPoint() const;
144
145  // Returns true when the box degenerates to a point
146  bool IsPoint() const;
147
148  void Scale(const float scale) {
149        Vector3 newSize = Size()*(scale*0.5f);
150        Vector3 center = Center();
151        mMin = center - newSize;
152        mMax = center + newSize;
153  }
154 
155  void
156  GetSqrDistances(const Vector3 &point,
157                  float &minDistance,
158                  float &maxDistance
159                  ) const;
160
161  // returns true, when the sphere specified by the origin and radius
162  // fully contains the box
163  bool IsFullyContainedInSphere(const Vector3 &center, float radius) const;
164
165  // returns true, when the volume of the sphere and volume of the
166  // axis aligned box has no intersection
167  bool HasNoIntersectionWithSphere(const Vector3 &center,
168                                   float radius) const;
169
170
171  // Given a sphere described by the center and radius,
172  // the fullowing function returns:
173  //   -1 ... the sphere and the box are completely separate
174  //    0 ... the sphere and the box only partially overlap
175  //    1 ... the sphere contains fully the box
176  //  Note: the case when box fully contains the sphere is not reported
177  //        since it was not required.
178  int MutualPositionWithSphere(const Vector3 &center, float radius) const;
179
180  // Given a cube described by the center and half-size (radius),
181  // the following function returns:
182  //   -1 ... the cube and the box are completely separate
183  //    0 ... the cube and the box only partially overlap
184  //    1 ... the cube contains fully the box
185  int MutualPositionWithCube(const Vector3 &center, float halfSize) const;
186
187
188  Vector3 GetRandomPoint() const {
189    Vector3 size = Size();
190    return mMin + Vector3(RandomValue(0.0f, size.x),
191                                                  RandomValue(0.0f, size.y),
192                                                  RandomValue(0.0f, size.z));
193  }
194
195
196  Vector3 GetPoint(const Vector3 &p) const {
197    return mMin + p*Size();
198  }
199
200  // Returns the smallest axis-aligned box that includes all points
201  // inside the two given boxes.
202  friend inline AxisAlignedBox3 Union(const AxisAlignedBox3 &x,
203                             const AxisAlignedBox3 &y);
204
205  // Returns the intersection of two axis-aligned boxes.
206  friend inline AxisAlignedBox3 Intersect(const AxisAlignedBox3 &x,
207                                 const AxisAlignedBox3 &y);
208
209  // Given 4x4 matrix, transform the current box to new one.
210  friend inline AxisAlignedBox3 Transform(const AxisAlignedBox3 &box,
211                                          const Matrix4x4 &tform);
212
213 
214  // returns true when two boxes are completely equal
215  friend inline int operator== (const AxisAlignedBox3 &A, const AxisAlignedBox3 &B);
216 
217  virtual float SurfaceArea() const;
218  virtual float GetVolume() const {
219    return (mMax.x - mMin.x) * (mMax.y - mMin.y) * (mMax.z - mMin.z);
220  }
221
222  // Six faces are distuinguished by their name.
223  enum EFaces { ID_Back = 0, ID_Left = 1, ID_Bottom = 2, ID_Front = 3,
224                ID_Right = 4, ID_Top = 5};
225 
226  int
227  ComputeMinMaxT(const Vector3 &origin,
228                                 const Vector3 &direction,
229                                 float *tmin,
230                                 float *tmax) const;
231       
232  // Compute tmin and tmax for a ray, whenever required .. need not pierce box
233  int ComputeMinMaxT(const Ray &ray, float *tmin, float *tmax) const;
234
235  // Compute tmin and tmax for a ray, whenever required .. need not pierce box
236  int ComputeMinMaxT(const Ray &ray,
237                                         float *tmin,
238                                         float *tmax,
239                                         EFaces &entryFace,
240                                         EFaces &exitFace) const;
241 
242  // If a ray pierces the box .. returns 1, otherwise 0.
243  // Computes the signed distances for case: tmin < tmax and tmax > 0
244  int GetMinMaxT(const Ray &ray, float *tmin, float *tmax) const;
245  // computes the signed distances for case: tmin < tmax and tmax > 0
246  int GetMinMaxT(const Ray &ray, float *tmin, float *tmax,
247                 EFaces &entryFace, EFaces &exitFace) const;
248 
249  // Writes a brief description of the object, indenting by the given
250  // number of spaces first.
251  virtual void Describe(ostream& app, int ind) const;
252
253  // For edge .. number <0..11> returns two incident vertices
254  void GetEdge(const int edge, Vector3 *a, Vector3 *b) const;
255
256  // Compute the coordinates of one vertex of the box for 0/1 in each axis
257  // 0 .. smaller coordinates, 1 .. large coordinates
258  Vector3 GetVertex(int xAxis, int yAxis, int zAxis) const;
259
260  // Compute the vertex for number N=<0..7>, N = 4*x + 2*y + z, where
261  // x,y,z are either 0 or 1; (0 .. lower coordinate, 1 .. large coordinate)
262  // (xmin,ymin, zmin) .. N = 0, (xmax, ymax, zmax) .. N= 7
263  void GetVertex(const int N, Vector3 &vertex) const;
264
265  Vector3 GetVertex(const int N) const {
266    Vector3 v;
267    GetVertex(N, v);
268    return v;
269  }
270
271  // Returns 1, if the box includes on arbitrary face a given box
272  int IsPiercedByBox(const AxisAlignedBox3 &box, int &axis) const;
273
274
275  int GetFaceVisibilityMask(const Vector3 &position) const;
276  int GetFaceVisibilityMask(const Rectangle3 &rectangle) const;
277
278  Rectangle3 GetFace(const int face) const;
279 
280  // For a given point returns the region, where the point is located
281  // there are 27 regions (0..26) .. determined by the planes embedding in the
282  // sides of the bounding box (0 .. lower the position of the box,
283  // 1 .. inside the box, 2 .. greater than box). The region number is given as
284  // R = 9*x + 3*y + z  ; e.g. region .. inside the box is 13.
285  int GetRegionID(const Vector3 &point) const;
286 
287  // Set the corner point of rectangle on the face of bounding box
288  // given by the index number and the rectangle lying on this face
289  //  void GetFaceRectCorner(const CRectLeaf2D *rect, EFaces faceIndx,
290  //                     const int &cornerIndx, Vector3 &cornerPoint);
291
292  // Project the box to a plane given a normal vector of this plane. Computes
293  // the surface area of projected silhouettes for parallel projection.
294  float ProjectToPlaneSA(const Vector3 &normal) const;
295
296  // Computes projected surface area of the box to a given viewing plane
297  // given a viewpoint. This corresponds the probability, the box will
298  // be hit by the ray .. moreover returns .. the region number (0-26).
299  // the function supposes all the points lie of the box lies in the viewing
300  // frustrum !!! The positive halfspace of viewplane has to contain
301  // viewpoint. "projectionType" == 0 .. perspective projection,
302  // == 1 .. parallel projection.
303  float ProjectToPlaneSA(const Plane3 &viewplane,
304                         const Vector3 &viewpoint,
305                         int *tcase,
306                         const float &maxSA,
307                         int projectionType) const;
308
309  // Computes projected surface area of the box to a given viewing plane
310  // and viewpoint. It clipps the area by all the planes given .. they should
311  // define the viewing frustrum. Variable tclip defines, which planes are
312  // used for clipping, parameter 31 is the most general, clip all the plane.
313  // 1 .. clip left, 2 .. clip top, 4 .. clip right, 8 .. clip bottom,
314  // 16 .. clip supporting plane(its normal towards the viewing frustrum).
315  // "typeProjection" == 0 .. perspective projection,
316  // == 1 .. parallel projection
317  float ProjectToPlaneSA(const Plane3 &viewplane,
318                         const Vector3 &viewpoint,
319                         int *tcase, int &tclip,
320                         const Plane3 &leftPlane,
321                         const Plane3 &topPlane,
322                         const Plane3 &rightPlane,
323                         const Plane3 &bottomPlane,
324                         const Plane3 &suppPlane,
325                         const float &maxSA,
326                         int typeProjection) const;
327
328  // Projects the box to a unit sphere enclosing a given viewpoint and
329  // returns the solid angle of the box projected to a unit sphere
330  float ProjectToSphereSA(const Vector3 &viewpoint, int *tcase) const;
331
332  /** Returns vertex indices of edge.
333  */
334  void GetEdge(const int edge, int  &aIdx, int &bIdx) const;
335
336  /** Computes cross section of plane with box (i.e., bounds box).
337          @returns the cross section
338  */
339  Polygon3 *CrossSection(const Plane3 &plane) const;
340
341  /** Computes minimal and maximal t of ray, including the object intersections.
342          @returns true if ray hits the bounding box.
343  */
344  bool GetRaySegment(const Ray &ray,
345                                float &minT,
346                                float &maxT) const;
347
348  /** If the boxes are intersecting on a common face, this function
349          returns the face intersection, false otherwise.
350   
351          @param neighbour the neighbouring box intersecting with this box.
352  */
353  bool GetIntersectionFace(Rectangle3 &face,
354                                                   const AxisAlignedBox3 &neighbour) const;
355
356  /** Adds the box faces to the mesh.
357  */
358  void AddBoxToMesh(Mesh *mesh) const;
359
360  void ExtractPolys(PolygonContainer &polys) const;
361
362#define __EXTENT_HACK
363  // get the extent of face
364  float GetExtent(const int &face) const {
365#if defined(__EXTENT_HACK) && defined(__VECTOR_HACK)
366    return mMin[face];
367#else
368    if (face < 3)
369      return mMin[face];
370    else
371      return mMax[face-3];
372#endif
373  }
374
375  // The vertices that form boundaries of the projected bounding box
376  // for all the regions possible, number of regions is 3^3 = 27,
377  // since two parallel sides of bbox forms three disjoint spaces
378  // the vertices are given in anti-clockwise order .. stopped by -1 elem.
379  static const int bvertices[27][9];
380
381  // The list of all faces visible from a given region (except region 13)
382  // the faces are identified by triple: (axis, min-vertex, max-vertex),
383  // that is maximaly three triples are defined. axis = 0 (x-axis),
384  // axis = 1 (y-axis), axis = 2 (z-axis), -1 .. terminator. Is is always
385  // true that: min-vertex < max-vertex for all coordinates excluding axis
386  static const int bfaces[27][10];
387 
388  // The correct corners indexed starting from entry face to exit face
389  // first index determines entry face, second index exit face, and
390  // the two numbers (indx, inc) determines: ind = the index on the exit
391  // face, when starting from the vertex 0 on entry face, 'inc' is
392  // the increment when we go on entry face in order 0,1,2,3 to create
393  // convex shaft with the rectangle on exit face. That is, inc = -1 or 1.
394  static const int pairFaceRects[6][6][2];
395
396  // The vertices that form CLOSEST points with respect to the region
397  // for all the regions possible, number of regions is 3^3 = 27,
398  // since two parallel sides of bbox forms three disjoint spaces.
399  // The vertices are given in anti-clockwise order, stopped by -1 elem,
400  // at most 8 points, at least 1 point.
401  static const int cvertices[27][9];
402  static const int csvertices[27][6];
403
404  // The vertices that form FARTHEST points with respect to the region
405  // for all the regions possible, number of regions is 3^3 = 27,
406  // since two parallel sides of bbox forms three disjoint spaces.
407  // The vertices are given in anti-clockwise order, stopped by -1 elem,
408  // at most 8 points, at least 1 point.
409  static const int fvertices[27][9]; 
410  static const int fsvertices[27][9];
411
412  // input and output operator with stream
413  friend ostream& operator<<(ostream &s, const AxisAlignedBox3 &A);
414  friend istream& operator>>(istream &s, AxisAlignedBox3 &A);
415
416protected:
417  // definition of friend functions
418  friend class Ray;
419};
420
421// --------------------------------------------------------------------------
422// Implementation of inline (member) functions
423 
424inline bool
425Overlap(const AxisAlignedBox3 &x, const AxisAlignedBox3 &y)
426{
427  if (x.mMax.x < y.mMin.x ||
428      x.mMin.x > y.mMax.x ||
429      x.mMax.y < y.mMin.y ||
430      x.mMin.y > y.mMax.y ||
431      x.mMax.z < y.mMin.z ||
432      x.mMin.z > y.mMax.z) {
433    return false;
434  }
435  return true;
436}
437
438inline bool
439OverlapS(const AxisAlignedBox3 &x, const AxisAlignedBox3 &y)
440{
441  if (x.mMax.x <= y.mMin.x ||
442      x.mMin.x >= y.mMax.x ||
443      x.mMax.y <= y.mMin.y ||
444      x.mMin.y >= y.mMax.y ||
445      x.mMax.z <= y.mMin.z ||
446      x.mMin.z >= y.mMax.z) {
447    return false;
448  }
449  return true;
450}
451
452inline bool
453Overlap(const AxisAlignedBox3 &x, const AxisAlignedBox3 &y, float eps)
454{
455  if ( (x.mMax.x - eps) < y.mMin.x ||
456       (x.mMin.x + eps) > y.mMax.x ||
457       (x.mMax.y - eps) < y.mMin.y ||
458       (x.mMin.y + eps) > y.mMax.y ||
459       (x.mMax.z - eps) < y.mMin.z ||
460       (x.mMin.z + eps) > y.mMax.z ) {
461    return false;
462  }
463  return true;
464}
465
466inline AxisAlignedBox3
467Intersect(const AxisAlignedBox3 &x, const AxisAlignedBox3 &y)
468{
469  if (x.Unbounded())
470    return y;
471  else
472    if (y.Unbounded())
473      return x;
474  AxisAlignedBox3 ret = x;
475  if (Overlap(ret, y)) {
476    Maximize(ret.mMin, y.mMin);
477    Minimize(ret.mMax, y.mMax);
478    return ret;
479  }
480  else      // Null intersection.
481    return AxisAlignedBox3(Vector3(0), Vector3(0));
482  // return AxisAlignedBox3(Vector3(0), Vector3(-1));
483}
484
485inline AxisAlignedBox3
486Union(const AxisAlignedBox3 &x, const AxisAlignedBox3 &y)
487{
488  Vector3 min = x.mMin;
489  Vector3 max = x.mMax;
490  Minimize(min, y.mMin);
491  Maximize(max, y.mMax);
492  return AxisAlignedBox3(min, max);
493}
494
495inline AxisAlignedBox3
496Transform(const AxisAlignedBox3 &box, const Matrix4x4 &tform)
497{
498  Vector3 mmin(MAXFLOAT);
499  Vector3 mmax(-MAXFLOAT);
500
501  AxisAlignedBox3 ret(mmin, mmax);
502  ret.Include(tform * Vector3(box.mMin.x, box.mMin.y, box.mMin.z));
503  ret.Include(tform * Vector3(box.mMin.x, box.mMin.y, box.mMax.z));
504  ret.Include(tform * Vector3(box.mMin.x, box.mMax.y, box.mMin.z));
505  ret.Include(tform * Vector3(box.mMin.x, box.mMax.y, box.mMax.z));
506  ret.Include(tform * Vector3(box.mMax.x, box.mMin.y, box.mMin.z));
507  ret.Include(tform * Vector3(box.mMax.x, box.mMin.y, box.mMax.z));
508  ret.Include(tform * Vector3(box.mMax.x, box.mMax.y, box.mMin.z));
509  ret.Include(tform * Vector3(box.mMax.x, box.mMax.y, box.mMax.z));
510  return ret;
511}
512
513
514inline int operator==(const AxisAlignedBox3 &A, const AxisAlignedBox3 &B)
515{
516  return (A.mMin == B.mMin) && (A.mMax == B.mMax);
517}
518
519 
520
521
522
523#endif
Note: See TracBrowser for help on using the repository browser.