Point Cloud Library (PCL) 1.13.0
Loading...
Searching...
No Matches
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
25class ON_CLASS ON_BoundingBox
26{
27public:
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 );
37
38
39 // temporary - use ON_ClippingRegion - this function will be removed soon.
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
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
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;
60 ON_3dPointArray& box_corners // returns list of 8 corner points
61 ) const;
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 */
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
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.
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.
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.
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.
389 const ON_3dPoint& // test_point
390 ) const;
391
392 //////////
393 // Get points on bounding boxes that are farthest from each other.
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 */
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 */
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 )
502ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<ON_BoundingBox>;
503#pragma warning( pop )
504
505#endif
506
507/*
508Description:
509 Get a tight bounding box that contains the points.
510Parameters:
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.
524Returns:
525 True if the output bbox is valid.
526*/
527ON_DECL
528bool 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
539ON_DECL
540bool 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
551ON_DECL
552bool 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
563ON_DECL
564ON_BoundingBox ON_PointListBoundingBox(
565 int dim,
566 int is_rat,
567 int count,
568 int stride,
569 const double* point_list
570 );
571
572ON_DECL
573bool 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
584ON_DECL
585ON_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
593ON_DECL
594bool 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
605ON_DECL
606ON_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
614ON_DECL
615double ON_BoundingBoxTolerance(
616 int dim,
617 const double* bboxmin,
618 const double* bboxmax
619 );
620
621/*
622Description:
623 Determine if an object is too large or too far
624 from the origin for single precision coordinates
625 to be useful.
626Parameters:
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.
639Returns:
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*/
648ON_DECL
649bool ON_BeyondSinglePrecision( const ON_BoundingBox& bbox, ON_Xform* xform );
650
651ON_DECL
652bool ON_WorldBBoxIsInTightBBox(
653 const ON_BoundingBox& tight_bbox,
654 const ON_BoundingBox& world_bbox,
655 const ON_Xform* xform
656 );
657
658#endif
ON_BoundingBox(const ON_3dPoint &, const ON_3dPoint &)
double MaximumDistanceTo(const ON_Line &line) const
int IsVisible(const ON_Xform &bbox2c) const
void Dump(class ON_TextLog &) const
double MaximumDistanceTo(const ON_BoundingBox &other) const
bool Intersection(const ON_BoundingBox &other_bbox)
double MaximumDistanceTo(const ON_PlaneEquation &plane_equation) const
bool GetCorners(ON_3dPoint box_corners[8]) const
bool Includes(const ON_BoundingBox &other, bool bProperSubSet=false) const
double MinimumDistanceTo(const ON_PlaneEquation &plane_equation) const
bool Set(const ON_SimpleArray< ON_4dPoint > &point_array, int bGrowBox=false)
ON_3dPoint Max() const
bool IsDisjoint(const ON_BoundingBox &other_bbox) const
double MinimumDistanceTo(const ON_Plane &plane) const
bool Set(const ON_3dPoint &point, int bGrowBox=false)
double Volume() const
bool IsPointIn(const ON_3dPoint &test_point, int bStrictlyIn=false) const
bool Set(const ON_SimpleArray< ON_3dPoint > &point_array, int bGrowBox=false)
ON_3dPoint & operator[](int)
bool IsFartherThan(double d, const ON_3dPoint &P) const
double MinimumDistanceTo(const ON_BoundingBox &other) const
bool IsFartherThan(double d, const ON_Plane &plane) const
bool SwapCoordinates(int, int)
bool GetFarPoint(const ON_BoundingBox &, ON_3dPoint &, ON_3dPoint &) const
ON_3dPoint FarPoint(const ON_3dPoint &) const
bool IsValid() const
bool Transform(const ON_Xform &)
bool Set(const ON_SimpleArray< ON_2dPoint > &point_array, int bGrowBox=false)
bool GetCorners(ON_3dPointArray &box_corners) const
double MinimumDistanceTo(const ON_Line &line) const
bool Set(int dim, int is_rat, int count, int stride, const double *point_array, int bGrowBox=false)
int GetClosestPoint(const ON_Line &, ON_3dPoint &, double *, double *) const
const ON_3dPoint & operator[](int) const
bool Union(const ON_BoundingBox &)
bool IsFartherThan(double d, const ON_BoundingBox &other) const
bool IsFartherThan(double d, const ON_Line &line) const
int IsDegenerate(double tolerance=ON_UNSET_VALUE) const
ON_3dPoint Center() const
ON_3dVector Diagonal() const
double Area() const
double Tolerance() const
bool Union(const ON_BoundingBox &, const ON_BoundingBox &)
bool IsFartherThan(double d, const ON_PlaneEquation &plane_equation) const
double MaximumDistanceTo(const ON_3dPoint &P) const
double MinimumDistanceTo(const ON_3dPoint &P) const
bool Intersection(const ON_BoundingBox &bbox_A, const ON_BoundingBox &bbox_B)
static const ON_BoundingBox EmptyBoundingBox
bool Intersection(const ON_Line &, double *=NULL, double *=NULL) const
double MaximumDistanceTo(const ON_Plane &plane) const
ON_3dPoint Corner(int, int, int) const
bool GetClosestPoint(const ON_BoundingBox &, ON_3dPoint &, ON_3dPoint &) const
ON_3dPoint Min() const
ON_3dPoint ClosestPoint(const ON_3dPoint &test_point) const