Panda3D
boundingBox.cxx
1 // Filename: boundingBox.cxx
2 // Created by: drose (31May07)
3 //
4 ////////////////////////////////////////////////////////////////////
5 //
6 // PANDA 3D SOFTWARE
7 // Copyright (c) Carnegie Mellon University. All rights reserved.
8 //
9 // All use of this software is subject to the terms of the revised BSD
10 // license. You should have received a copy of this license along
11 // with this source code in a file named "LICENSE."
12 //
13 ////////////////////////////////////////////////////////////////////
14 
15 #include "boundingBox.h"
16 #include "boundingSphere.h"
17 #include "boundingHexahedron.h"
18 #include "boundingLine.h"
19 #include "boundingPlane.h"
20 #include "config_mathutil.h"
21 #include "dcast.h"
22 
23 #include <math.h>
24 #include <algorithm>
25 
26 const int BoundingBox::plane_def[6][3] = {
27  { 0, 4, 5 },
28  { 4, 6, 7 },
29  { 6, 2, 3 },
30  { 2, 0, 1 },
31  { 1, 5, 7 },
32  { 2, 6, 4 },
33 };
34 
35 TypeHandle BoundingBox::_type_handle;
36 
37 ////////////////////////////////////////////////////////////////////
38 // Function: BoundingBox::make_copy
39 // Access: Public, Virtual
40 // Description:
41 ////////////////////////////////////////////////////////////////////
42 BoundingVolume *BoundingBox::
43 make_copy() const {
44  return new BoundingBox(*this);
45 }
46 
47 ////////////////////////////////////////////////////////////////////
48 // Function: BoundingBox::get_min
49 // Access: Public, Virtual
50 // Description:
51 ////////////////////////////////////////////////////////////////////
52 LPoint3 BoundingBox::
53 get_min() const {
54  nassertr(!is_empty(), _min);
55  nassertr(!is_infinite(), _min);
56  return _min;
57 }
58 
59 ////////////////////////////////////////////////////////////////////
60 // Function: BoundingBox::get_max
61 // Access: Public, Virtual
62 // Description:
63 ////////////////////////////////////////////////////////////////////
64 LPoint3 BoundingBox::
65 get_max() const {
66  nassertr(!is_empty(), _max);
67  nassertr(!is_infinite(), _max);
68  return _max;
69 }
70 
71 ////////////////////////////////////////////////////////////////////
72 // Function: BoundingBox::get_volume
73 // Access: Public, Virtual
74 // Description:
75 ////////////////////////////////////////////////////////////////////
76 PN_stdfloat BoundingBox::
77 get_volume() const {
78  nassertr(!is_infinite(), 0.0f);
79  if (is_empty()) {
80  return 0.0f;
81  }
82 
83  // Volume of a box: width x depth x height
84  return (_max[0] - _min[0]) * (_max[1] - _min[1]) * (_max[2] - _min[2]);
85 }
86 
87 ////////////////////////////////////////////////////////////////////
88 // Function: BoundingBox::get_approx_center
89 // Access: Public, Virtual
90 // Description:
91 ////////////////////////////////////////////////////////////////////
92 LPoint3 BoundingBox::
93 get_approx_center() const {
94  nassertr(!is_empty(), LPoint3::zero());
95  nassertr(!is_infinite(), LPoint3::zero());
96  return (_min + _max) * 0.5f;
97 }
98 
99 ////////////////////////////////////////////////////////////////////
100 // Function: BoundingBox::xform
101 // Access: Public, Virtual
102 // Description:
103 ////////////////////////////////////////////////////////////////////
104 void BoundingBox::
105 xform(const LMatrix4 &mat) {
106  nassertv(!mat.is_nan());
107 
108  if (!is_empty() && !is_infinite()) {
109  // We need to transform the eight corners of the cube, and then
110  // determine the new box.
111  LPoint3 x = get_point(0) * mat;
112  LPoint3 n = x;
113  for (int i = 1; i < 8; ++i) {
114  LPoint3 p = get_point(i) * mat;
115  n.set(min(n[0], p[0]), min(n[1], p[1]), min(n[2], p[2]));
116  x.set(max(x[0], p[0]), max(x[1], p[1]), max(x[2], p[2]));
117  }
118  _max = x;
119  _min = n;
120  }
121 }
122 
123 ////////////////////////////////////////////////////////////////////
124 // Function: BoundingBox::output
125 // Access: Public, Virtual
126 // Description:
127 ////////////////////////////////////////////////////////////////////
128 void BoundingBox::
129 output(ostream &out) const {
130  if (is_empty()) {
131  out << "bbox, empty";
132  } else if (is_infinite()) {
133  out << "bbox, infinite";
134  } else {
135  out << "bbox, (" << _min << ") to (" << _max << ")";
136  }
137 }
138 
139 ////////////////////////////////////////////////////////////////////
140 // Function: BoundingBox::as_bounding_box
141 // Access: Public, Virtual
142 // Description: Virtual downcast method. Returns this object as a
143 // pointer of the indicated type, if it is in fact that
144 // type. Returns NULL if it is not that type.
145 ////////////////////////////////////////////////////////////////////
148  return this;
149 }
150 
151 ////////////////////////////////////////////////////////////////////
152 // Function: BoundingBox::extend_other
153 // Access: Protected, Virtual
154 // Description:
155 ////////////////////////////////////////////////////////////////////
156 bool BoundingBox::
157 extend_other(BoundingVolume *other) const {
158  return other->extend_by_box(this);
159 }
160 
161 ////////////////////////////////////////////////////////////////////
162 // Function: BoundingBox::around_other
163 // Access: Protected, Virtual
164 // Description:
165 ////////////////////////////////////////////////////////////////////
166 bool BoundingBox::
167 around_other(BoundingVolume *other,
168  const BoundingVolume **first,
169  const BoundingVolume **last) const {
170  return other->around_boxes(first, last);
171 }
172 
173 ////////////////////////////////////////////////////////////////////
174 // Function: BoundingBox::contains_other
175 // Access: Protected, Virtual
176 // Description:
177 ////////////////////////////////////////////////////////////////////
178 int BoundingBox::
179 contains_other(const BoundingVolume *other) const {
180  return other->contains_box(this);
181 }
182 
183 
184 ////////////////////////////////////////////////////////////////////
185 // Function: BoundingBox::extend_by_point
186 // Access: Protected, Virtual
187 // Description:
188 ////////////////////////////////////////////////////////////////////
189 bool BoundingBox::
190 extend_by_point(const LPoint3 &point) {
191  nassertr(!point.is_nan(), false);
192 
193  if (is_empty()) {
194  _min = point;
195  _max = point;
196  _flags = 0;
197 
198  } else if (!is_infinite()) {
199  _min.set(min(_min[0], point[0]), min(_min[1], point[1]), min(_min[2], point[2]));
200  _max.set(max(_max[0], point[0]), max(_max[1], point[1]), max(_max[2], point[2]));
201  }
202 
203  return true;
204 }
205 
206 ////////////////////////////////////////////////////////////////////
207 // Function: BoundingBox::extend_by_box
208 // Access: Protected, Virtual
209 // Description:
210 ////////////////////////////////////////////////////////////////////
211 bool BoundingBox::
212 extend_by_box(const BoundingBox *box) {
213  nassertr(!box->is_empty() && !box->is_infinite(), false);
214  nassertr(!is_infinite(), false);
215 
216  if (is_empty()) {
217  _min = box->_min;
218  _max = box->_max;
219  _flags = 0;
220 
221  } else {
222  _min.set(min(_min[0], box->_min[0]),
223  min(_min[1], box->_min[1]),
224  min(_min[2], box->_min[2]));
225  _max.set(max(_max[0], box->_max[0]),
226  max(_max[1], box->_max[1]),
227  max(_max[2], box->_max[2]));
228  }
229  return true;
230 }
231 
232 ////////////////////////////////////////////////////////////////////
233 // Function: BoundingBox::extend_by_finite
234 // Access: Protected, Virtual
235 // Description:
236 ////////////////////////////////////////////////////////////////////
237 bool BoundingBox::
238 extend_by_finite(const FiniteBoundingVolume *volume) {
239  nassertr(!volume->is_empty() && !volume->is_infinite(), false);
240 
241  LVector3 min1 = volume->get_min();
242  LVector3 max1 = volume->get_max();
243 
244  if (is_empty()) {
245  _min = min1;
246  _max = max1;
247  _flags = 0;
248 
249  } else {
250  _min.set(min(_min[0], min1[0]),
251  min(_min[1], min1[1]),
252  min(_min[2], min1[2]));
253  _max.set(max(_max[0], max1[0]),
254  max(_max[1], max1[1]),
255  max(_max[2], max1[2]));
256  }
257 
258  return true;
259 }
260 
261 ////////////////////////////////////////////////////////////////////
262 // Function: BoundingBox::around_points
263 // Access: Protected, Virtual
264 // Description:
265 ////////////////////////////////////////////////////////////////////
266 bool BoundingBox::
267 around_points(const LPoint3 *first, const LPoint3 *last) {
268  nassertr(first != last, false);
269 
270  // Get the minmax of all the points to construct a bounding box.
271  const LPoint3 *p = first;
272 
273 #ifndef NDEBUG
274  // Skip any NaN points.
275  int skipped_nan = 0;
276  while (p != last && (*p).is_nan()) {
277  ++p;
278  ++skipped_nan;
279  }
280  if (p == last) {
281  mathutil_cat.warning()
282  << "BoundingBox around NaN\n";
283  return false;
284  }
285 #endif
286 
287  _min = *p;
288  _max = *p;
289  ++p;
290 
291 #ifndef NDEBUG
292  // Skip more NaN points.
293  while (p != last && (*p).is_nan()) {
294  ++p;
295  ++skipped_nan;
296  }
297 #endif
298 
299  while (p != last) {
300 #ifndef NDEBUG
301  // Skip more NaN points.
302  if ((*p).is_nan()) {
303  ++skipped_nan;
304  } else
305 #endif
306  {
307  _min.set(min(_min[0], (*p)[0]),
308  min(_min[1], (*p)[1]),
309  min(_min[2], (*p)[2]));
310  _max.set(max(_max[0], (*p)[0]),
311  max(_max[1], (*p)[1]),
312  max(_max[2], (*p)[2]));
313  }
314  ++p;
315  }
316 
317 #ifndef NDEBUG
318  if (skipped_nan != 0) {
319  mathutil_cat.warning()
320  << "BoundingBox ignored " << skipped_nan << " NaN points of "
321  << (last - first) << " total.\n";
322  }
323 #endif
324 
325  _flags = 0;
326 
327  return true;
328 }
329 
330 ////////////////////////////////////////////////////////////////////
331 // Function: BoundingBox::around_finite
332 // Access: Protected, Virtual
333 // Description:
334 ////////////////////////////////////////////////////////////////////
335 bool BoundingBox::
336 around_finite(const BoundingVolume **first,
337  const BoundingVolume **last) {
338  nassertr(first != last, false);
339 
340  // We're given a set of bounding volumes, at least the first one of
341  // which is guaranteed to be finite and nonempty. Some others may
342  // not be.
343 
344  // First, get the box of all the points to construct a bounding
345  // box.
346  const BoundingVolume **p = first;
347  nassertr(!(*p)->is_empty() && !(*p)->is_infinite(), false);
348  const FiniteBoundingVolume *vol = DCAST(FiniteBoundingVolume, *p);
349  _min = vol->get_min();
350  _max = vol->get_max();
351 
352  for (++p; p != last; ++p) {
353  nassertr(!(*p)->is_infinite(), false);
354  if (!(*p)->is_empty()) {
355  const FiniteBoundingVolume *vol = DCAST(FiniteBoundingVolume, *p);
356  LPoint3 min1 = vol->get_min();
357  LPoint3 max1 = vol->get_max();
358  _min.set(min(_min[0], min1[0]),
359  min(_min[1], min1[1]),
360  min(_min[2], min1[2]));
361  _max.set(max(_max[0], max1[0]),
362  max(_max[1], max1[1]),
363  max(_max[2], max1[2]));
364  }
365  }
366 
367  _flags = 0;
368  return true;
369 }
370 
371 ////////////////////////////////////////////////////////////////////
372 // Function: BoundingBox::contains_point
373 // Access: Protected, Virtual
374 // Description:
375 ////////////////////////////////////////////////////////////////////
376 int BoundingBox::
377 contains_point(const LPoint3 &point) const {
378  nassertr(!point.is_nan(), IF_no_intersection);
379 
380  if (is_empty()) {
381  return IF_no_intersection;
382 
383  } else if (is_infinite()) {
384  return IF_possible | IF_some | IF_all;
385 
386  } else {
387  if (point[0] >= _min[0] && point[0] <= _max[0] &&
388  point[1] >= _min[1] && point[1] <= _max[1] &&
389  point[2] >= _min[2] && point[2] <= _max[2]) {
390  return IF_possible | IF_some | IF_all;
391  } else {
392  return IF_no_intersection;
393  }
394  }
395 }
396 
397 ////////////////////////////////////////////////////////////////////
398 // Function: BoundingBox::contains_lineseg
399 // Access: Protected, Virtual
400 // Description:
401 ////////////////////////////////////////////////////////////////////
402 int BoundingBox::
403 contains_lineseg(const LPoint3 &a, const LPoint3 &b) const {
404  nassertr(!a.is_nan() && !b.is_nan(), IF_no_intersection);
405 
406  if (a == b) {
407  return contains_point(a);
408  }
409  if (is_empty()) {
410  return IF_no_intersection;
411 
412  } else if (is_infinite()) {
413  return IF_possible | IF_some | IF_all;
414 
415  } else {
416  // Set a bit for each plane a and b are on the wrong side of.
417  unsigned int a_bits = 0;
418 
419  if (a[0] < _min[0]) {
420  a_bits |= 0x01;
421  } else if (a[0] > _max[0]) {
422  a_bits |= 0x02;
423  }
424 
425  if (a[1] < _min[1]) {
426  a_bits |= 0x04;
427  } else if (a[1] > _max[1]) {
428  a_bits |= 0x08;
429  }
430 
431  if (a[2] < _min[2]) {
432  a_bits |= 0x10;
433  } else if (a[2] > _max[2]) {
434  a_bits |= 0x20;
435  }
436 
437  unsigned int b_bits = 0;
438 
439  if (b[0] < _min[0]) {
440  b_bits |= 0x01;
441  } else if (b[0] > _max[0]) {
442  b_bits |= 0x02;
443  }
444 
445  if (b[1] < _min[1]) {
446  b_bits |= 0x04;
447  } else if (b[1] > _max[1]) {
448  b_bits |= 0x08;
449  }
450 
451  if (b[2] < _min[2]) {
452  b_bits |= 0x10;
453  } else if (b[2] > _max[2]) {
454  b_bits |= 0x20;
455  }
456 
457  if ((a_bits & b_bits) != 0) {
458  // If there are any bits in common, the segment is wholly
459  // outside the box (both points are on the wrong side of the
460  // same plane).
461  return IF_no_intersection;
462 
463  } else if ((a_bits | b_bits) == 0) {
464  // If there are no bits at all, the segment is wholly within the
465  // box.
466  return IF_possible | IF_some | IF_all;
467 
468  } else if (a_bits == 0 || b_bits == 0) {
469  // If either point is within the box, the segment is partially
470  // within the box.
471  return IF_possible | IF_some;
472 
473  } else {
474  unsigned int differ = (a_bits ^ b_bits);
475  if (differ == 0x03 || differ == 0x0c || differ == 0x30) {
476  // If the line segment stretches straight across the box, the
477  // segment is partially within.
478  return IF_possible | IF_some;
479 
480  } else {
481  // Otherwise, it's hard to tell whether it does or doesn't.
482  return IF_possible;
483  }
484  }
485  }
486 }
487 
488 ////////////////////////////////////////////////////////////////////
489 // Function: BoundingBox::contains_box
490 // Access: Protected, Virtual
491 // Description: Double-dispatch support: called by contains_other()
492 // when the type we're testing for intersection is known
493 // to be a box.
494 ////////////////////////////////////////////////////////////////////
495 int BoundingBox::
496 contains_box(const BoundingBox *box) const {
497  nassertr(!is_empty() && !is_infinite(), 0);
498  nassertr(!box->is_empty() && !box->is_infinite(), 0);
499 
500  const LPoint3 &min1 = box->get_minq();
501  const LPoint3 &max1 = box->get_maxq();
502 
503  if (min1[0] >= _min[0] && max1[0] <= _max[0] &&
504  min1[1] >= _min[1] && max1[1] <= _max[1] &&
505  min1[2] >= _min[2] && max1[2] <= _max[2]) {
506  // The other volume is completely within this volume.
507  return IF_possible | IF_some | IF_all;
508 
509  } else if (max1[0] >= _min[0] && min1[0] <= _max[0] &&
510  max1[1] >= _min[1] && min1[1] <= _max[1] &&
511  max1[2] >= _min[2] && min1[2] <= _max[2]) {
512  // The other volume is partially within this volume.
513  return IF_possible;
514 
515  } else {
516  // The other volume is not within this volume.
517  return IF_no_intersection;
518  }
519 }
520 
521 ////////////////////////////////////////////////////////////////////
522 // Function: BoundingBox::contains_hexahedron
523 // Access: Protected, Virtual
524 // Description: Double-dispatch support: called by contains_other()
525 // when the type we're testing for intersection is known
526 // to be a hexahedron.
527 ////////////////////////////////////////////////////////////////////
528 int BoundingBox::
529 contains_hexahedron(const BoundingHexahedron *hexahedron) const {
530  // First, try the quick bounding-box test. If that's decisive,
531  // we'll accept it.
532  int result = contains_finite(hexahedron);
533  if (result == IF_no_intersection || ((result & IF_all) != 0)) {
534  return result;
535  }
536 
537  // If that was inconclusive, we'll look more closely with the
538  // somewhat more expensive reverse answer.
539  return hexahedron->contains_box(this) & ~IF_all;
540 }
541 
542 ////////////////////////////////////////////////////////////////////
543 // Function: BoundingBox::contains_line
544 // Access: Protected, Virtual
545 // Description: Double-dispatch support: called by contains_other()
546 // when the type we're testing for intersection is known
547 // to be a line.
548 ////////////////////////////////////////////////////////////////////
549 int BoundingBox::
550 contains_line(const BoundingLine *line) const {
551  return line->contains_box(this) & ~IF_all;
552 }
553 
554 ////////////////////////////////////////////////////////////////////
555 // Function: BoundingBox::contains_plane
556 // Access: Protected, Virtual
557 // Description: Double-dispatch support: called by contains_other()
558 // when the type we're testing for intersection is known
559 // to be a plane.
560 ////////////////////////////////////////////////////////////////////
561 int BoundingBox::
562 contains_plane(const BoundingPlane *plane) const {
563  return plane->contains_box(this) & ~IF_all;
564 }
565 
566 ////////////////////////////////////////////////////////////////////
567 // Function: BoundingBox::contains_finite
568 // Access: Protected, Virtual
569 // Description:
570 ////////////////////////////////////////////////////////////////////
571 int BoundingBox::
572 contains_finite(const FiniteBoundingVolume *volume) const {
573  nassertr(!is_empty() && !is_infinite(), 0);
574  nassertr(!volume->is_empty() && !volume->is_infinite(), 0);
575 
576  LPoint3 min1 = volume->get_min();
577  LPoint3 max1 = volume->get_max();
578 
579  if (min1[0] >= _min[0] && max1[0] <= _max[0] &&
580  min1[1] >= _min[1] && max1[1] <= _max[1] &&
581  min1[2] >= _min[2] && max1[2] <= _max[2]) {
582  // The other volume is completely within this volume.
583  return IF_possible | IF_some | IF_all;
584 
585  } else if (max1[0] >= _min[0] && min1[0] <= _max[0] &&
586  max1[1] >= _min[1] && min1[1] <= _max[1] &&
587  max1[2] >= _min[2] && min1[2] <= _max[2]) {
588  // The other volume is partially within this volume.
589  return IF_possible;
590 
591  } else {
592  // The other volume is not within this volume.
593  return IF_no_intersection;
594  }
595 }
An axis-aligned bounding box; that is, a minimum and maximum coordinate triple.
Definition: boundingBox.h:31
bool is_empty() const
Any kind of volume might be empty.
virtual const BoundingBox * as_bounding_box() const
Virtual downcast method.
bool is_infinite() const
The other side of the empty coin is an infinite volume.
static const LPoint3f & zero()
Returns a zero-length point.
Definition: lpoint3.h:259
This is a three-component vector distance (as opposed to a three-component point, which represents a ...
Definition: lvector3.h:100
This is a three-component point in space (as opposed to a three-component vector, which represents a ...
Definition: lpoint3.h:99
bool is_nan() const
Returns true if any component of the vector is not-a-number, false otherwise.
Definition: lvecBase3.h:464
bool is_nan() const
Returns true if any component of the matrix is not-a-number, false otherwise.
Definition: lmatrix.h:1417
This funny bounding volume is an infinite plane that divides space into two regions: the part behind ...
Definition: boundingPlane.h:31
This is an abstract class for any volume in any sense which can be said to define the locality of ref...
This is a 4-by-4 transform matrix.
Definition: lmatrix.h:451
const LPoint3 & get_maxq() const
An inline accessor for the maximum value.
Definition: boundingBox.I:64
LPoint3 get_point(int n) const
Returns the nth vertex of the rectangular solid.
Definition: boundingBox.I:86
A special kind of GeometricBoundingVolume that is known to be finite.
BoundingBox()
Constructs an empty box object.
Definition: boundingBox.I:22
TypeHandle is the identifier used to differentiate C++ class types.
Definition: typeHandle.h:85
This defines a bounding convex hexahedron.
This funny bounding volume is an infinite line with no thickness and extending to infinity in both di...
Definition: boundingLine.h:33
const LPoint3 & get_minq() const
An inline accessor for the minimum value.
Definition: boundingBox.I:50