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

Revision 1414, 18.5 KB checked in by mattausch, 18 years ago (diff)

fixed kd tree loading / exporting

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