source: GTP/trunk/Lib/Vis/Preprocessing/src/AxisAlignedBox3.h @ 870

Revision 870, 18.2 KB checked in by mattausch, 19 years ago (diff)

added pvs

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