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

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