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

Revision 697, 17.5 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  /** Extracts plane of bounding box.
281  */
282  Plane3 GetPlane(const int face) const;
283 
284  // For a given point returns the region, where the point is located
285  // there are 27 regions (0..26) .. determined by the planes embedding in the
286  // sides of the bounding box (0 .. lower the position of the box,
287  // 1 .. inside the box, 2 .. greater than box). The region number is given as
288  // R = 9*x + 3*y + z  ; e.g. region .. inside the box is 13.
289  int GetRegionID(const Vector3 &point) const;
290 
291  // Set the corner point of rectangle on the face of bounding box
292  // given by the index number and the rectangle lying on this face
293  //  void GetFaceRectCorner(const CRectLeaf2D *rect, EFaces faceIndx,
294  //                     const int &cornerIndx, Vector3 &cornerPoint);
295
296  // Project the box to a plane given a normal vector of this plane. Computes
297  // the surface area of projected silhouettes for parallel projection.
298  float ProjectToPlaneSA(const Vector3 &normal) const;
299
300  // Computes projected surface area of the box to a given viewing plane
301  // given a viewpoint. This corresponds the probability, the box will
302  // be hit by the ray .. moreover returns .. the region number (0-26).
303  // the function supposes all the points lie of the box lies in the viewing
304  // frustrum !!! The positive halfspace of viewplane has to contain
305  // viewpoint. "projectionType" == 0 .. perspective projection,
306  // == 1 .. parallel projection.
307  float ProjectToPlaneSA(const Plane3 &viewplane,
308                         const Vector3 &viewpoint,
309                         int *tcase,
310                         const float &maxSA,
311                         int projectionType) const;
312
313  // Computes projected surface area of the box to a given viewing plane
314  // and viewpoint. It clipps the area by all the planes given .. they should
315  // define the viewing frustrum. Variable tclip defines, which planes are
316  // used for clipping, parameter 31 is the most general, clip all the plane.
317  // 1 .. clip left, 2 .. clip top, 4 .. clip right, 8 .. clip bottom,
318  // 16 .. clip supporting plane(its normal towards the viewing frustrum).
319  // "typeProjection" == 0 .. perspective projection,
320  // == 1 .. parallel projection
321  float ProjectToPlaneSA(const Plane3 &viewplane,
322                         const Vector3 &viewpoint,
323                         int *tcase, int &tclip,
324                         const Plane3 &leftPlane,
325                         const Plane3 &topPlane,
326                         const Plane3 &rightPlane,
327                         const Plane3 &bottomPlane,
328                         const Plane3 &suppPlane,
329                         const float &maxSA,
330                         int typeProjection) const;
331
332  // Projects the box to a unit sphere enclosing a given viewpoint and
333  // returns the solid angle of the box projected to a unit sphere
334  float ProjectToSphereSA(const Vector3 &viewpoint, int *tcase) const;
335
336  /** Returns vertex indices of edge.
337  */
338  void GetEdge(const int edge, int  &aIdx, int &bIdx) const;
339
340  /** Computes cross section of plane with box (i.e., bounds box).
341          @returns the cross section
342  */
343  Polygon3 *CrossSection(const Plane3 &plane) const;
344
345  /** Computes minimal and maximal t of ray, including the object intersections.
346          @returns true if ray hits the bounding box.
347  */
348  bool GetRaySegment(const Ray &ray,
349                                float &minT,
350                                float &maxT) const;
351
352  /** If the boxes are intersecting on a common face, this function
353          returns the face intersection, false otherwise.
354   
355          @param neighbour the neighbouring box intersecting with this box.
356  */
357  bool GetIntersectionFace(Rectangle3 &face,
358                                                   const AxisAlignedBox3 &neighbour) const;
359
360  /** Adds the box faces to the mesh.
361  */
362  void AddBoxToMesh(Mesh *mesh) const;
363
364  /** Box faces are turned into polygons.
365  */
366  void ExtractPolys(PolygonContainer &polys) const;
367
368#define __EXTENT_HACK
369  // get the extent of face
370  float GetExtent(const int &face) const {
371#if defined(__EXTENT_HACK) && defined(__VECTOR_HACK)
372    return mMin[face];
373#else
374    if (face < 3)
375      return mMin[face];
376    else
377      return mMax[face-3];
378#endif
379  }
380
381  // The vertices that form boundaries of the projected bounding box
382  // for all the regions possible, number of regions is 3^3 = 27,
383  // since two parallel sides of bbox forms three disjoint spaces
384  // the vertices are given in anti-clockwise order .. stopped by -1 elem.
385  static const int bvertices[27][9];
386
387  // The list of all faces visible from a given region (except region 13)
388  // the faces are identified by triple: (axis, min-vertex, max-vertex),
389  // that is maximaly three triples are defined. axis = 0 (x-axis),
390  // axis = 1 (y-axis), axis = 2 (z-axis), -1 .. terminator. Is is always
391  // true that: min-vertex < max-vertex for all coordinates excluding axis
392  static const int bfaces[27][10];
393 
394  // The correct corners indexed starting from entry face to exit face
395  // first index determines entry face, second index exit face, and
396  // the two numbers (indx, inc) determines: ind = the index on the exit
397  // face, when starting from the vertex 0 on entry face, 'inc' is
398  // the increment when we go on entry face in order 0,1,2,3 to create
399  // convex shaft with the rectangle on exit face. That is, inc = -1 or 1.
400  static const int pairFaceRects[6][6][2];
401
402  // The vertices that form CLOSEST points with respect to the region
403  // for all the regions possible, number of regions is 3^3 = 27,
404  // since two parallel sides of bbox forms three disjoint spaces.
405  // The vertices are given in anti-clockwise order, stopped by -1 elem,
406  // at most 8 points, at least 1 point.
407  static const int cvertices[27][9];
408  static const int csvertices[27][6];
409
410  // The vertices that form FARTHEST points with respect to the region
411  // for all the regions possible, number of regions is 3^3 = 27,
412  // since two parallel sides of bbox forms three disjoint spaces.
413  // The vertices are given in anti-clockwise order, stopped by -1 elem,
414  // at most 8 points, at least 1 point.
415  static const int fvertices[27][9]; 
416  static const int fsvertices[27][9];
417
418  // input and output operator with stream
419  friend ostream& operator<<(ostream &s, const AxisAlignedBox3 &A);
420  friend istream& operator>>(istream &s, AxisAlignedBox3 &A);
421
422protected:
423  // definition of friend functions
424  friend class Ray;
425};
426
427// --------------------------------------------------------------------------
428// Implementation of inline (member) functions
429 
430inline bool
431Overlap(const AxisAlignedBox3 &x, const AxisAlignedBox3 &y)
432{
433  if (x.mMax.x < y.mMin.x ||
434      x.mMin.x > y.mMax.x ||
435      x.mMax.y < y.mMin.y ||
436      x.mMin.y > y.mMax.y ||
437      x.mMax.z < y.mMin.z ||
438      x.mMin.z > y.mMax.z) {
439    return false;
440  }
441  return true;
442}
443
444inline bool
445OverlapS(const AxisAlignedBox3 &x, const AxisAlignedBox3 &y)
446{
447  if (x.mMax.x <= y.mMin.x ||
448      x.mMin.x >= y.mMax.x ||
449      x.mMax.y <= y.mMin.y ||
450      x.mMin.y >= y.mMax.y ||
451      x.mMax.z <= y.mMin.z ||
452      x.mMin.z >= y.mMax.z) {
453    return false;
454  }
455  return true;
456}
457
458inline bool
459Overlap(const AxisAlignedBox3 &x, const AxisAlignedBox3 &y, float eps)
460{
461  if ( (x.mMax.x - eps) < y.mMin.x ||
462       (x.mMin.x + eps) > y.mMax.x ||
463       (x.mMax.y - eps) < y.mMin.y ||
464       (x.mMin.y + eps) > y.mMax.y ||
465       (x.mMax.z - eps) < y.mMin.z ||
466       (x.mMin.z + eps) > y.mMax.z ) {
467    return false;
468  }
469  return true;
470}
471
472inline AxisAlignedBox3
473Intersect(const AxisAlignedBox3 &x, const AxisAlignedBox3 &y)
474{
475  if (x.Unbounded())
476    return y;
477  else
478    if (y.Unbounded())
479      return x;
480  AxisAlignedBox3 ret = x;
481  if (Overlap(ret, y)) {
482    Maximize(ret.mMin, y.mMin);
483    Minimize(ret.mMax, y.mMax);
484    return ret;
485  }
486  else      // Null intersection.
487    return AxisAlignedBox3(Vector3(0), Vector3(0));
488  // return AxisAlignedBox3(Vector3(0), Vector3(-1));
489}
490
491inline AxisAlignedBox3
492Union(const AxisAlignedBox3 &x, const AxisAlignedBox3 &y)
493{
494  Vector3 min = x.mMin;
495  Vector3 max = x.mMax;
496  Minimize(min, y.mMin);
497  Maximize(max, y.mMax);
498  return AxisAlignedBox3(min, max);
499}
500
501inline AxisAlignedBox3
502Transform(const AxisAlignedBox3 &box, const Matrix4x4 &tform)
503{
504  Vector3 mmin(MAXFLOAT);
505  Vector3 mmax(-MAXFLOAT);
506
507  AxisAlignedBox3 ret(mmin, mmax);
508  ret.Include(tform * Vector3(box.mMin.x, box.mMin.y, box.mMin.z));
509  ret.Include(tform * Vector3(box.mMin.x, box.mMin.y, box.mMax.z));
510  ret.Include(tform * Vector3(box.mMin.x, box.mMax.y, box.mMin.z));
511  ret.Include(tform * Vector3(box.mMin.x, box.mMax.y, box.mMax.z));
512  ret.Include(tform * Vector3(box.mMax.x, box.mMin.y, box.mMin.z));
513  ret.Include(tform * Vector3(box.mMax.x, box.mMin.y, box.mMax.z));
514  ret.Include(tform * Vector3(box.mMax.x, box.mMax.y, box.mMin.z));
515  ret.Include(tform * Vector3(box.mMax.x, box.mMax.y, box.mMax.z));
516  return ret;
517}
518
519
520inline int operator==(const AxisAlignedBox3 &A, const AxisAlignedBox3 &B)
521{
522  return (A.mMin == B.mMin) && (A.mMax == B.mMax);
523}
524
525 
526
527
528
529#endif
Note: See TracBrowser for help on using the repository browser.