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