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

Revision 1486, 17.6 KB checked in by mattausch, 18 years ago (diff)

worked on guided visibility sampling

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