Panda3D
Loading...
Searching...
No Matches
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
25using std::max;
26using std::min;
27
28const 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
37TypeHandle BoundingBox::_type_handle;
38
39/**
40 *
41 */
42BoundingVolume *BoundingBox::
43make_copy() const {
44 return new BoundingBox(*this);
45}
46
47/**
48 *
49 */
50LPoint3 BoundingBox::
51get_min() const {
52 nassertr(!is_empty(), _min);
53 nassertr(!is_infinite(), _min);
54 return _min;
55}
56
57/**
58 *
59 */
60LPoint3 BoundingBox::
61get_max() const {
62 nassertr(!is_empty(), _max);
63 nassertr(!is_infinite(), _max);
64 return _max;
65}
66
67/**
68 *
69 */
70PN_stdfloat BoundingBox::
71get_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 */
84LPoint3 BoundingBox::
85get_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 */
94void BoundingBox::
95xform(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 */
116void BoundingBox::
117output(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 */
132as_bounding_box() const {
133 return this;
134}
135
136/**
137 *
138 */
139bool BoundingBox::
140extend_other(BoundingVolume *other) const {
141 return other->extend_by_box(this);
142}
143
144/**
145 *
146 */
147bool BoundingBox::
148around_other(BoundingVolume *other,
149 const BoundingVolume **first,
150 const BoundingVolume **last) const {
151 return other->around_boxes(first, last);
152}
153
154/**
155 *
156 */
157int BoundingBox::
158contains_other(const BoundingVolume *other) const {
159 return other->contains_box(this);
160}
161
162
163/**
164 *
165 */
166bool BoundingBox::
167extend_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 */
186bool BoundingBox::
187extend_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 */
210bool BoundingBox::
211extend_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 */
237bool BoundingBox::
238around_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 */
304bool BoundingBox::
305around_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 */
341int BoundingBox::
342contains_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 */
365int BoundingBox::
366contains_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 */
453int BoundingBox::
454contains_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 */
483int BoundingBox::
484contains_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 */
501int BoundingBox::
502contains_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 */
510int BoundingBox::
511contains_plane(const BoundingPlane *plane) const {
512 return plane->contains_box(this) & ~IF_all;
513}
514
515/**
516 *
517 */
518int BoundingBox::
519contains_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}
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
An axis-aligned bounding box; that is, a minimum and maximum coordinate triple.
Definition boundingBox.h:29
const LPoint3 & get_minq() const
An inline accessor for the minimum value.
Definition boundingBox.I:41
BoundingBox()
Constructs an empty box object.
Definition boundingBox.I:18
virtual const BoundingBox * as_bounding_box() const
Virtual downcast method.
get_point
Returns the nth vertex of the rectangular solid.
Definition boundingBox.h:51
const LPoint3 & get_maxq() const
An inline accessor for the maximum value.
Definition boundingBox.I:52
This defines a bounding convex hexahedron.
This funny bounding volume is an infinite line with no thickness and extending to infinity in both di...
This funny bounding volume is an infinite plane that divides space into two regions: the part behind ...
This is an abstract class for any volume in any sense which can be said to define the locality of ref...
bool is_empty() const
Any kind of volume might be empty.
bool is_infinite() const
The other side of the empty coin is an infinite volume.
A special kind of GeometricBoundingVolume that is known to be finite.
TypeHandle is the identifier used to differentiate C++ class types.
Definition typeHandle.h:81
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.