Point Cloud Library (PCL)  1.9.1-dev
opennurbs_bounding_box.h
1 /* $NoKeywords: $ */
2 /*
3 //
4 // Copyright (c) 1993-2012 Robert McNeel & Associates. All rights reserved.
5 // OpenNURBS, Rhinoceros, and Rhino3D are registered trademarks of Robert
6 // McNeel & Associates.
7 //
8 // THIS SOFTWARE IS PROVIDED "AS IS" WITHOUT EXPRESS OR IMPLIED WARRANTY.
9 // ALL IMPLIED WARRANTIES OF FITNESS FOR ANY PARTICULAR PURPOSE AND OF
10 // MERCHANTABILITY ARE HEREBY DISCLAIMED.
11 //
12 // For complete openNURBS copyright information see <http://www.opennurbs.org>.
13 //
14 ////////////////////////////////////////////////////////////////
15 */
16 
17 #if !defined(ON_BOUNDING_BOX_INC_)
18 #define ON_BOUNDING_BOX_INC_
19 
20 ////////////////////////////////////////////////////////////////
21 //
22 // ON_BoundingBox - axis aligned bounding box
23 //
24 
25 class ON_CLASS ON_BoundingBox
26 {
27 public:
28  static const ON_BoundingBox EmptyBoundingBox; // ((1.0,0,0,0,0),(-1.0,0.0,0.0))
29 
30  ON_BoundingBox(); // creates EmptyBox
31 
33  const ON_3dPoint&, // min corner of axis aligned bounding box
34  const ON_3dPoint& // max corner of axis aligned bounding box
35  );
36  ~ON_BoundingBox();
37 
38 
39  // temporary - use ON_ClippingRegion - this function will be removed soon.
40  int IsVisible(
41  const ON_Xform& bbox2c
42  ) const;
43 
44  void Destroy(); // invalidates bounding box
45 
46  // operator[] returns min if index <= 0 and max if indes >= 1
47  ON_3dPoint& operator[](int);
48  const ON_3dPoint& operator[](int) const;
49 
50  ON_3dPoint Min() const;
51  ON_3dPoint Max() const;
52  ON_3dVector Diagonal() const; // max corner - min corner
53  ON_3dPoint Center() const;
54  ON_3dPoint Corner( // 8 corners of box
55  int, // x_index 0 = Min().x, 1 = Max().x
56  int, // y_index 0 = Min().y, 1 = Max().y
57  int // z_index 0 = Min().z, 1 = Max().z
58  ) const;
59  bool GetCorners(
60  ON_3dPointArray& box_corners // returns list of 8 corner points
61  ) const;
62  bool GetCorners(
63  ON_3dPoint box_corners[8] // returns list of 8 corner points
64  ) const;
65 
66  bool IsValid() const; // empty boxes are not valid
67 
68  void Dump(class ON_TextLog&) const;
69 
70  /*
71  Description:
72  Test a bounding box to see if it is degenerate (flat)
73  in one or more directions.
74  Parameters:
75  tolerance - [in] Distances <= tolerance will be considered
76  to be zero. If tolerance is negative (default), then
77  a scale invarient tolerance is used.
78  Returns:
79  @untitled table
80  0 box is not degenerate
81  1 box is a rectangle (degenerate in one direction)
82  2 box is a line (degenerate in two directions)
83  3 box is a point (degenerate in three directions)
84  4 box is not valid
85  */
86  int IsDegenerate(
87  double tolerance = ON_UNSET_VALUE
88  ) const;
89 
90 
91  //////////
92  // ON_BoundingBox::Transform() updates the bounding box
93  // to be the smallest axis aligned bounding box that contains
94  // the transform of the eight corner points of the input
95  // bounding box.
96  bool Transform( const ON_Xform& );
97 
98  double Tolerance() const; // rough guess at a tolerance to use for comparing
99  // objects in this bounding box
100 
101 
102  // All of these Set() functions set or expand a box to enclose the points in the arguments
103  // If bGrowBox is true, the existing box is expanded, otherwise it is only set to the current point list
104  bool Set(
105  int dim,
106  int is_rat,
107  int count,
108  int stride,
109  const double* point_array,
110  int bGrowBox = false
111  );
112 
113  bool Set(
114  const ON_3dPoint& point,
115  int bGrowBox = false
116  );
117 
118  bool Set(
119  const ON_SimpleArray<ON_4dPoint>& point_array,
120  int bGrowBox = false
121  );
122 
123  bool Set(
124  const ON_SimpleArray<ON_3dPoint>& point_array,
125  int bGrowBox = false
126  );
127 
128  bool Set(
129  const ON_SimpleArray<ON_2dPoint>& point_array,
130  int bGrowBox = false
131  );
132 
133  bool IsPointIn(
134  const ON_3dPoint& test_point, // point to test
135  int bStrictlyIn = false
136  // true to test for strict ( min < point < max )
137  // false to test for (min <= point <= max)
138  //
139  ) const;
140 
141  //////////
142  // Point on or in the box that is closest to test_point.
143  // If test_point is in or on the box, the test_point is returned.
144  ON_3dPoint ClosestPoint(
145  const ON_3dPoint& test_point
146  ) const;
147 
148 
149  /*
150  Description:
151  Quickly find a lower bound on the distance
152  between the point and this bounding box.
153  Parameters:
154  P - [in]
155  Returns:
156  A distance that is less than or equal to the shortest
157  distance from the line to this bounding box.
158  Put another way, if Q is any point in this bounding box,
159  then P.DistanceTo(Q) >= MinimumDistanceTo(bbox).
160  */
161  double MinimumDistanceTo( const ON_3dPoint& P ) const;
162 
163  /*
164  Description:
165  Quickly find an upper bound on the distance
166  between the point and this bounding box.
167  Parameters:
168  P - [in]
169  Returns:
170  A distance that is greater than or equal to the
171  longest distance from the point P to this bounding box.
172  Put another way, if Q is any point in this bounding box,
173  then P.DistanceTo(Q) <= MaximumDistanceTo(bbox).
174  */
175  double MaximumDistanceTo( const ON_3dPoint& P ) const;
176 
177 
178  /*
179  Description:
180  Quickly find a lower bound on the distance
181  between this and the other bounding box.
182  Parameters:
183  other - [in]
184  Returns:
185  A distance that is less than or equal to the shortest
186  distance between the bounding boxes.
187  Put another way, if Q is any point in this bounding box
188  and P is any point in the other bounding box,
189  then P.DistanceTo(Q) >= MinimumDistanceTo(bbox).
190  */
191  double MinimumDistanceTo( const ON_BoundingBox& other ) const;
192 
193  /*
194  Description:
195  Quickly find an upper bound on the distance
196  between this and the other bounding box.
197  Parameters:
198  other - [in]
199  Returns:
200  A distance that is greater than or equal to the longest
201  distance between the bounding boxes.
202  Put another way, if Q is any point in this bounding box
203  and P is any point in the other bounding box,
204  then P.DistanceTo(Q) <= MaximumDistanceTo(bbox).
205  */
206  double MaximumDistanceTo( const ON_BoundingBox& other ) const;
207 
208  /*
209  Description:
210  Quickly find a lower bound on the distance
211  between the line segment and this bounding box.
212  Parameters:
213  line - [in]
214  Returns:
215  A distance that is less than or equal to the shortest
216  distance from the line to this bounding box.
217  Put another way, if Q is any point on line
218  and P is any point in this bounding box, then
219  P.DistanceTo(Q) >= MinimumDistanceTo(bbox).
220  */
221  double MinimumDistanceTo( const ON_Line& line ) const;
222 
223  /*
224  Description:
225  Quickly find a tight lower bound on the distance
226  between the plane and this bounding box.
227  Parameters:
228  plane - [in]
229  Returns:
230  The minimum distance between a point on the plane
231  and a point on the bounding box.
232  See Also:
233  ON_PlaneEquation::MimimumValueAt
234  ON_PlaneEquation::MaximumValueAt
235  */
236  double MinimumDistanceTo( const ON_Plane& plane ) const;
237  double MinimumDistanceTo( const ON_PlaneEquation& plane_equation ) const;
238 
239  /*
240  Description:
241  Quickly find an upper bound on the distance
242  between the line segment and this bounding box.
243  Parameters:
244  line - [in]
245  Returns:
246  A distance that is greater than or equal to the
247  longest distance from the line to this bounding box.
248  Put another way, if Q is any point on the line
249  and P is any point in this bounding box, then
250  P.DistanceTo(Q) <= MaximumDistanceTo(bbox).
251  */
252  double MaximumDistanceTo( const ON_Line& line ) const;
253 
254  /*
255  Description:
256  Quickly find a tight upper bound on the distance
257  between the plane and this bounding box.
258  Parameters:
259  plane - [in]
260  Returns:
261  A distance that is equal to the longest distance from
262  the plane to this bounding box. Put another way,
263  if Q is any point on the plane and P is any point
264  in this bounding box, then
265  P.DistanceTo(Q) <= MaximumDistanceTo(bbox) and there
266  is at least one point on the bounding box where the
267  distance is equal to the returned value.
268  See Also:
269  ON_PlaneEquation::MaximumValueAt
270  */
271  double MaximumDistanceTo( const ON_Plane& plane ) const;
272  double MaximumDistanceTo( const ON_PlaneEquation& plane_equation ) const;
273 
274 
275  /*
276  Description:
277  Quickly determine if the shortest distance from
278  the point P to the bounding box is greater than d.
279  Parameters:
280  d - [in] distance (> 0.0)
281  P - [in]
282  Returns:
283  True if if the shortest distance from the point P
284  to the bounding box is greater than d.
285  */
286  bool IsFartherThan( double d, const ON_3dPoint& P ) const;
287 
288  /*
289  Description:
290  Quickly determine if the shortest distance from the line
291  to the bounding box is greater than d.
292  Parameters:
293  d - [in] distance (> 0.0)
294  line - [in]
295  Returns:
296  True if the shortest distance from the line
297  to the bounding box is greater than d. It is not the
298  case that false means that the shortest distance
299  is less than or equal to d.
300  */
301  bool IsFartherThan( double d, const ON_Line& line ) const;
302 
303  /*
304  Description:
305  Quickly determine if the shortest distance from the plane
306  to the bounding box is greater than d.
307  Parameters:
308  d - [in] distance (> 0.0)
309  plane - [in]
310  Returns:
311  True if the shortest distance from the plane
312  to the bounding box is greater than d, and false
313  if the shortest distance is less than or equal to d.
314  */
315  bool IsFartherThan( double d, const ON_Plane& plane ) const;
316 
317  /*
318  Description:
319  Quickly determine if the shortest distance from the plane
320  to the bounding box is greater than d.
321  Parameters:
322  d - [in] distance (> 0.0)
323  plane_equation - [in] (the first three coefficients
324  are assumed to be a unit vector.
325  If not, adjust your d accordingly.)
326  Returns:
327  True if the shortest distance from the plane
328  to the bounding box is greater than d, and false
329  if the shortest distance is less than or equal to d.
330  */
331  bool IsFartherThan( double d, const ON_PlaneEquation& plane_equation ) const;
332 
333  /*
334  Description:
335  Quickly determine if the shortest distance this bounding
336  box to another bounding box is greater than d.
337  Parameters:
338  d - [in] distance (> 0.0)
339  other - [in] other bounding box
340  Returns:
341  True if if the shortest distance from this bounding
342  box to the other bounding box is greater than d.
343  */
344  bool IsFartherThan( double d, const ON_BoundingBox& other ) const;
345 
346 
347  // Description:
348  // Get point in a bounding box that is closest to a line
349  // segment.
350  // Parameters:
351  // line - [in] line segment
352  // box_point - [out] point in box that is closest to line
353  // segment point at t0.
354  // t0 - [out] parameter of point on line that is closest to
355  // the box.
356  // t1 - [out] parameter of point on line that is closest to
357  // the box.
358  // Returns:
359  // 3 success - line segments intersects box in a segment
360  // from line(t0) to line(t1) (t0 < t1)
361  // 2 success - line segments intersects box in a single point
362  // at line(t0) (t0==t1)
363  // 1 success - line segment does not intersect box. Closest
364  // point on the line is at line(t0) (t0==t1)
365  // 0 failure - box is invalid.
366  // Remarks:
367  // The box is treated as a solid box. If the intersection
368  // of the line segment, then 3 is returned.
369  int GetClosestPoint(
370  const ON_Line&, // line
371  ON_3dPoint&, // box_point
372  double*, // t0
373  double* // t1
374  ) const;
375 
376  //////////
377  // Get points on bounding boxes that are closest to each other.
378  // If the boxes intersect, then the point at the centroid of the
379  // intersection is returned for both points.
380  bool GetClosestPoint(
381  const ON_BoundingBox&, // "other" bounding box
382  ON_3dPoint&, // point on "this" box that is closest to "other" box
383  ON_3dPoint& // point on "other" box that is closest to "this" box
384  ) const;
385 
386  //////////
387  // Point on the box that is farthest from the test_point.
388  ON_3dPoint FarPoint(
389  const ON_3dPoint& // test_point
390  ) const;
391 
392  //////////
393  // Get points on bounding boxes that are farthest from each other.
394  bool GetFarPoint(
395  const ON_BoundingBox&, // "other" bounding box
396  ON_3dPoint&, // point on "this" box that is farthest from "other" box
397  ON_3dPoint& // point on "other" box that is farthest from "this" box
398  ) const;
399 
400  /*
401  Description:
402  Intersect this with other_bbox and save intersection in this.
403  Parameters:
404  other_bbox - [in]
405  Returns:
406  True if this-intesect-other_bbox is a non-empty valid bounding box
407  and this is set. False if the intersection is empty, in which case
408  "this" is set to an invalid bounding box.
409  Remarks:
410  If "this" or other_bbox is invalid, they are treated as
411  the empty set, and false is returned.
412  */
413  bool Intersection(
414  const ON_BoundingBox& other_bbox
415  );
416 
417  /*
418  Description:
419  Set "this" to the intersection of bbox_A and bbox_B.
420  Parameters:
421  bbox_A - [in]
422  bbox_B - [in]
423  Returns:
424  True if the "this" is a non-empty valid bounding box.
425  False if the intersection is empty, in which case
426  "this" is set to an invalid bounding box.
427  Remarks:
428  If bbox_A or bbox_B is invalid, they are treated as
429  the empty set, and false is returned.
430  */
431  bool Intersection( // this = intersection of two args
432  const ON_BoundingBox& bbox_A,
433  const ON_BoundingBox& bbox_B
434  );
435 
436  bool Intersection( //Returns true when intersect is non-empty.
437  const ON_Line&, //Infinite Line segment to intersect with
438  double* =NULL , // t0 parameter of first intersection point
439  double* =NULL // t1 parameter of last intersection point (t0<=t1)
440  ) const;
441 
442  /*
443  Description:
444  Test a box to see if it is contained in this box.
445  Parameters:
446  other - [in] box to test
447  bProperSubSet - [in] if true, then the test is for a proper inclusion.
448  Returns:
449  If bProperSubSet is false, then the result is true when
450  this->m_min[i] <= other.m_min[i] and other.m_max[i] <= this->m_max[i].
451  for i=0,1 and 2.
452  If bProperSubSet is true, then the result is true when
453  the above condition is true and at least one of the inequalities is strict.
454  */
455  bool Includes(
456  const ON_BoundingBox& other,
457  bool bProperSubSet = false
458  ) const;
459 
460  double Volume() const;
461 
462  double Area() const;
463 
464  // Union() returns true if union is not empty.
465  // Invalid boxes are treated as the empty set.
466  bool Union( // this = this union arg
467  const ON_BoundingBox&
468  );
469 
470  bool Union( // this = union of two args
471  const ON_BoundingBox&,
472  const ON_BoundingBox&
473  );
474 
475  /*
476  Description:
477  Test to see if "this" and other_bbox are disjoint (do not intersect).
478  Parameters:
479  other_bbox - [in]
480  Returns:
481  True if "this" and other_bbox are disjoint.
482  Remarks:
483  If "this" or other_bbox is invalid, then true is returned.
484  */
485  bool IsDisjoint(
486  const ON_BoundingBox& other_bbox
487  ) const;
488 
489  bool SwapCoordinates( int, int );
490 
493 };
494 
495 #if defined(ON_DLL_TEMPLATE)
496 
497 // This stuff is here because of a limitation in the way Microsoft
498 // handles templates and DLLs. See Microsoft's knowledge base
499 // article ID Q168958 for details.
500 #pragma warning( push )
501 #pragma warning( disable : 4231 )
502 ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<ON_BoundingBox>;
503 #pragma warning( pop )
504 
505 #endif
506 
507 /*
508 Description:
509  Get a tight bounding box that contains the points.
510 Parameters:
511  dim - [in] (>=1)
512  is_rat - [in] true if points are rational
513  count - [in] number of points
514  stride - [in] stride between points
515  point_list - [in]
516  bbox - [in/out]
517  bGrowBox - [in] (default = false)
518  If the input bbox is valid and bGrowBox is true,
519  then the output bbox is the union of the input
520  bbox and the bounding box of the point list.
521  xform - [in] (default = NULL)
522  If not null, the bounding box of the transformed
523  points is calculated. The points are not modified.
524 Returns:
525  True if the output bbox is valid.
526 */
527 ON_DECL
528 bool ON_GetPointListBoundingBox(
529  int dim,
530  int is_rat,
531  int count,
532  int stride,
533  const double* point_list,
534  ON_BoundingBox& bbox,
535  int bGrowBox = false,
536  const ON_Xform* xform = 0
537  );
538 
539 ON_DECL
540 bool ON_GetPointListBoundingBox(
541  int dim,
542  int is_rat,
543  int count,
544  int stride,
545  const float* point_list,
546  ON_BoundingBox& bbox,
547  int bGrowBox = false,
548  const ON_Xform* xform = 0
549  );
550 
551 ON_DECL
552 bool ON_GetPointListBoundingBox(
553  int dim,
554  int is_rat,
555  int count,
556  int stride,
557  const double* point_list,
558  double* boxmin, // min[dim]
559  double* boxmax, // max[dim]
560  int bGrowBox
561  );
562 
563 ON_DECL
564 ON_BoundingBox ON_PointListBoundingBox(
565  int dim,
566  int is_rat,
567  int count,
568  int stride,
569  const double* point_list
570  );
571 
572 ON_DECL
573 bool ON_GetPointListBoundingBox(
574  int dim,
575  int is_rat,
576  int count,
577  int stride,
578  const float* point_list,
579  float* boxmin, // min[dim]
580  float* boxmax, // max[dim]
581  int bGrowBox
582  );
583 
584 ON_DECL
585 ON_BoundingBox ON_PointListBoundingBox( // low level workhorse function
586  int dim,
587  int is_rat,
588  int count,
589  int stride,
590  const float* point_list
591  );
592 
593 ON_DECL
594 bool ON_GetPointGridBoundingBox(
595  int dim,
596  int is_rat,
597  int point_count0, int point_count1,
598  int point_stride0, int point_stride1,
599  const double* point_grid,
600  double* boxmin, // min[dim]
601  double* boxmax, // max[dim]
602  int bGrowBox
603  );
604 
605 ON_DECL
606 ON_BoundingBox ON_PointGridBoundingBox(
607  int dim,
608  int is_rat,
609  int point_count0, int point_count1,
610  int point_stride0, int point_stride1,
611  const double* point_grid
612  );
613 
614 ON_DECL
615 double ON_BoundingBoxTolerance(
616  int dim,
617  const double* bboxmin,
618  const double* bboxmax
619  );
620 
621 /*
622 Description:
623  Determine if an object is too large or too far
624  from the origin for single precision coordinates
625  to be useful.
626 Parameters:
627  bbox - [in]
628  Bounding box of an object with single precision
629  coordinates. An ON_Mesh is an example of an
630  object with single precision coordinates.
631  xform - [out]
632  If this function returns false and xform is not
633  null, then the identity transform is returned.
634  If this function returns true and xform is not
635  null, then the transform moves the region
636  contained in bbox to a location where single
637  precision coordinates will have enough
638  information for the object to be useful.
639 Returns:
640  true:
641  The region contained in bbox is too large
642  or too far from the origin for single
643  precision coordinates to be useful.
644  false:
645  A single precision object contained in bbox
646  will be satisfactory for common calculations.
647 */
648 ON_DECL
649 bool ON_BeyondSinglePrecision( const ON_BoundingBox& bbox, ON_Xform* xform );
650 
651 ON_DECL
652 bool ON_WorldBBoxIsInTightBBox(
653  const ON_BoundingBox& tight_bbox,
654  const ON_BoundingBox& world_bbox,
655  const ON_Xform* xform
656  );
657 
658 #endif
static const ON_BoundingBox EmptyBoundingBox