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

Revision 302, 15.4 KB checked in by mattausch, 19 years ago (diff)

added surface area heuristic for bsp

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