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

Revision 2176, 18.3 KB checked in by mattausch, 18 years ago (diff)

removed using namespace std from .h

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