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

Revision 1112, 18.6 KB checked in by bittner, 18 years ago (diff)

Merge with Olivers code

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