Panda3D
|
00001 // Filename: boundingBox.cxx 00002 // Created by: drose (31May07) 00003 // 00004 //////////////////////////////////////////////////////////////////// 00005 // 00006 // PANDA 3D SOFTWARE 00007 // Copyright (c) Carnegie Mellon University. All rights reserved. 00008 // 00009 // All use of this software is subject to the terms of the revised BSD 00010 // license. You should have received a copy of this license along 00011 // with this source code in a file named "LICENSE." 00012 // 00013 //////////////////////////////////////////////////////////////////// 00014 00015 #include "boundingBox.h" 00016 #include "boundingSphere.h" 00017 #include "boundingHexahedron.h" 00018 #include "boundingLine.h" 00019 #include "boundingPlane.h" 00020 #include "config_mathutil.h" 00021 #include "dcast.h" 00022 00023 #include <math.h> 00024 #include <algorithm> 00025 00026 const int BoundingBox::plane_def[6][3] = { 00027 { 0, 4, 5 }, 00028 { 4, 6, 7 }, 00029 { 6, 2, 3 }, 00030 { 2, 0, 1 }, 00031 { 1, 5, 7 }, 00032 { 2, 6, 4 }, 00033 }; 00034 00035 TypeHandle BoundingBox::_type_handle; 00036 00037 //////////////////////////////////////////////////////////////////// 00038 // Function: BoundingBox::make_copy 00039 // Access: Public, Virtual 00040 // Description: 00041 //////////////////////////////////////////////////////////////////// 00042 BoundingVolume *BoundingBox:: 00043 make_copy() const { 00044 return new BoundingBox(*this); 00045 } 00046 00047 //////////////////////////////////////////////////////////////////// 00048 // Function: BoundingBox::get_min 00049 // Access: Public, Virtual 00050 // Description: 00051 //////////////////////////////////////////////////////////////////// 00052 LPoint3f BoundingBox:: 00053 get_min() const { 00054 nassertr(!is_empty(), _min); 00055 nassertr(!is_infinite(), _min); 00056 return _min; 00057 } 00058 00059 //////////////////////////////////////////////////////////////////// 00060 // Function: BoundingBox::get_max 00061 // Access: Public, Virtual 00062 // Description: 00063 //////////////////////////////////////////////////////////////////// 00064 LPoint3f BoundingBox:: 00065 get_max() const { 00066 nassertr(!is_empty(), _max); 00067 nassertr(!is_infinite(), _max); 00068 return _max; 00069 } 00070 00071 //////////////////////////////////////////////////////////////////// 00072 // Function: BoundingBox::get_volume 00073 // Access: Public, Virtual 00074 // Description: 00075 //////////////////////////////////////////////////////////////////// 00076 float BoundingBox:: 00077 get_volume() const { 00078 nassertr(!is_infinite(), 0.0f); 00079 if (is_empty()) { 00080 return 0.0f; 00081 } 00082 00083 // Volume of a box: width x depth x height 00084 return (_max[0] - _min[0]) * (_max[1] - _min[1]) * (_max[2] - _min[2]); 00085 } 00086 00087 //////////////////////////////////////////////////////////////////// 00088 // Function: BoundingBox::get_approx_center 00089 // Access: Public, Virtual 00090 // Description: 00091 //////////////////////////////////////////////////////////////////// 00092 LPoint3f BoundingBox:: 00093 get_approx_center() const { 00094 nassertr(!is_empty(), LPoint3f::zero()); 00095 nassertr(!is_infinite(), LPoint3f::zero()); 00096 return (_min + _max) * 0.5f; 00097 } 00098 00099 //////////////////////////////////////////////////////////////////// 00100 // Function: BoundingBox::xform 00101 // Access: Public, Virtual 00102 // Description: 00103 //////////////////////////////////////////////////////////////////// 00104 void BoundingBox:: 00105 xform(const LMatrix4f &mat) { 00106 nassertv(!mat.is_nan()); 00107 00108 if (!is_empty() && !is_infinite()) { 00109 // We need to transform the eight corners of the cube, and then 00110 // determine the new box. 00111 LPoint3f x = get_point(0) * mat; 00112 LPoint3f n = x; 00113 for (int i = 1; i < 8; ++i) { 00114 LPoint3f p = get_point(i) * mat; 00115 n.set(min(n[0], p[0]), min(n[1], p[1]), min(n[2], p[2])); 00116 x.set(max(x[0], p[0]), max(x[1], p[1]), max(x[2], p[2])); 00117 } 00118 _max = x; 00119 _min = n; 00120 } 00121 } 00122 00123 //////////////////////////////////////////////////////////////////// 00124 // Function: BoundingBox::output 00125 // Access: Public, Virtual 00126 // Description: 00127 //////////////////////////////////////////////////////////////////// 00128 void BoundingBox:: 00129 output(ostream &out) const { 00130 if (is_empty()) { 00131 out << "bbox, empty"; 00132 } else if (is_infinite()) { 00133 out << "bbox, infinite"; 00134 } else { 00135 out << "bbox, (" << _min << ") to (" << _max << ")"; 00136 } 00137 } 00138 00139 //////////////////////////////////////////////////////////////////// 00140 // Function: BoundingBox::as_bounding_box 00141 // Access: Public, Virtual 00142 // Description: Virtual downcast method. Returns this object as a 00143 // pointer of the indicated type, if it is in fact that 00144 // type. Returns NULL if it is not that type. 00145 //////////////////////////////////////////////////////////////////// 00146 const BoundingBox *BoundingBox:: 00147 as_bounding_box() const { 00148 return this; 00149 } 00150 00151 //////////////////////////////////////////////////////////////////// 00152 // Function: BoundingBox::extend_other 00153 // Access: Protected, Virtual 00154 // Description: 00155 //////////////////////////////////////////////////////////////////// 00156 bool BoundingBox:: 00157 extend_other(BoundingVolume *other) const { 00158 return other->extend_by_box(this); 00159 } 00160 00161 //////////////////////////////////////////////////////////////////// 00162 // Function: BoundingBox::around_other 00163 // Access: Protected, Virtual 00164 // Description: 00165 //////////////////////////////////////////////////////////////////// 00166 bool BoundingBox:: 00167 around_other(BoundingVolume *other, 00168 const BoundingVolume **first, 00169 const BoundingVolume **last) const { 00170 return other->around_boxes(first, last); 00171 } 00172 00173 //////////////////////////////////////////////////////////////////// 00174 // Function: BoundingBox::contains_other 00175 // Access: Protected, Virtual 00176 // Description: 00177 //////////////////////////////////////////////////////////////////// 00178 int BoundingBox:: 00179 contains_other(const BoundingVolume *other) const { 00180 return other->contains_box(this); 00181 } 00182 00183 00184 //////////////////////////////////////////////////////////////////// 00185 // Function: BoundingBox::extend_by_point 00186 // Access: Protected, Virtual 00187 // Description: 00188 //////////////////////////////////////////////////////////////////// 00189 bool BoundingBox:: 00190 extend_by_point(const LPoint3f &point) { 00191 nassertr(!point.is_nan(), false); 00192 00193 if (is_empty()) { 00194 _min = point; 00195 _max = point; 00196 _flags = 0; 00197 00198 } else if (!is_infinite()) { 00199 _min.set(min(_min[0], point[0]), min(_min[1], point[1]), min(_min[2], point[2])); 00200 _max.set(max(_max[0], point[0]), max(_max[1], point[1]), max(_max[2], point[2])); 00201 } 00202 00203 return true; 00204 } 00205 00206 //////////////////////////////////////////////////////////////////// 00207 // Function: BoundingBox::extend_by_sphere 00208 // Access: Protected, Virtual 00209 // Description: 00210 //////////////////////////////////////////////////////////////////// 00211 bool BoundingBox:: 00212 extend_by_sphere(const BoundingSphere *sphere) { 00213 return extend_by_finite(sphere); 00214 } 00215 00216 //////////////////////////////////////////////////////////////////// 00217 // Function: BoundingBox::extend_by_box 00218 // Access: Protected, Virtual 00219 // Description: 00220 //////////////////////////////////////////////////////////////////// 00221 bool BoundingBox:: 00222 extend_by_box(const BoundingBox *box) { 00223 nassertr(!box->is_empty() && !box->is_infinite(), false); 00224 nassertr(!is_infinite(), false); 00225 00226 if (is_empty()) { 00227 _min = box->_min; 00228 _max = box->_max; 00229 _flags = 0; 00230 00231 } else { 00232 _min.set(min(_min[0], box->_min[0]), 00233 min(_min[1], box->_min[1]), 00234 min(_min[2], box->_min[2])); 00235 _max.set(max(_max[0], box->_max[0]), 00236 max(_max[1], box->_max[1]), 00237 max(_max[2], box->_max[2])); 00238 } 00239 return true; 00240 } 00241 00242 //////////////////////////////////////////////////////////////////// 00243 // Function: BoundingBox::extend_by_hexahedron 00244 // Access: Protected, Virtual 00245 // Description: 00246 //////////////////////////////////////////////////////////////////// 00247 bool BoundingBox:: 00248 extend_by_hexahedron(const BoundingHexahedron *hexahedron) { 00249 return extend_by_finite(hexahedron); 00250 } 00251 00252 //////////////////////////////////////////////////////////////////// 00253 // Function: BoundingBox::extend_by_finite 00254 // Access: Protected 00255 // Description: 00256 //////////////////////////////////////////////////////////////////// 00257 bool BoundingBox:: 00258 extend_by_finite(const FiniteBoundingVolume *volume) { 00259 nassertr(!volume->is_empty(), false); 00260 00261 LVector3f min1 = volume->get_min(); 00262 LVector3f max1 = volume->get_max(); 00263 00264 if (is_empty()) { 00265 _min = min1; 00266 _max = max1; 00267 _flags = 0; 00268 00269 } else { 00270 _min.set(min(_min[0], min1[0]), 00271 min(_min[1], min1[1]), 00272 min(_min[2], min1[2])); 00273 _max.set(max(_max[0], max1[0]), 00274 max(_max[1], max1[1]), 00275 max(_max[2], max1[2])); 00276 } 00277 00278 return true; 00279 } 00280 00281 //////////////////////////////////////////////////////////////////// 00282 // Function: BoundingBox::around_points 00283 // Access: Protected, Virtual 00284 // Description: 00285 //////////////////////////////////////////////////////////////////// 00286 bool BoundingBox:: 00287 around_points(const LPoint3f *first, const LPoint3f *last) { 00288 nassertr(first != last, false); 00289 00290 // Get the minmax of all the points to construct a bounding box. 00291 const LPoint3f *p = first; 00292 00293 #ifndef NDEBUG 00294 // Skip any NaN points. 00295 int skipped_nan = 0; 00296 while (p != last && (*p).is_nan()) { 00297 ++p; 00298 ++skipped_nan; 00299 } 00300 if (p == last) { 00301 mathutil_cat.warning() 00302 << "BoundingBox around NaN\n"; 00303 return false; 00304 } 00305 #endif 00306 00307 _min = *p; 00308 _max = *p; 00309 ++p; 00310 00311 #ifndef NDEBUG 00312 // Skip more NaN points. 00313 while (p != last && (*p).is_nan()) { 00314 ++p; 00315 ++skipped_nan; 00316 } 00317 #endif 00318 00319 while (p != last) { 00320 #ifndef NDEBUG 00321 // Skip more NaN points. 00322 if ((*p).is_nan()) { 00323 ++skipped_nan; 00324 } else 00325 #endif 00326 { 00327 _min.set(min(_min[0], (*p)[0]), 00328 min(_min[1], (*p)[1]), 00329 min(_min[2], (*p)[2])); 00330 _max.set(max(_max[0], (*p)[0]), 00331 max(_max[1], (*p)[1]), 00332 max(_max[2], (*p)[2])); 00333 } 00334 ++p; 00335 } 00336 00337 #ifndef NDEBUG 00338 if (skipped_nan != 0) { 00339 mathutil_cat.warning() 00340 << "BoundingBox ignored " << skipped_nan << " NaN points of " 00341 << (last - first) << " total.\n"; 00342 } 00343 #endif 00344 00345 _flags = 0; 00346 00347 return true; 00348 } 00349 00350 //////////////////////////////////////////////////////////////////// 00351 // Function: BoundingBox::around_spheres 00352 // Access: Protected, Virtual 00353 // Description: 00354 //////////////////////////////////////////////////////////////////// 00355 bool BoundingBox:: 00356 around_spheres(const BoundingVolume **first, 00357 const BoundingVolume **last) { 00358 return around_finite(first, last); 00359 } 00360 00361 //////////////////////////////////////////////////////////////////// 00362 // Function: BoundingBox::around_boxes 00363 // Access: Protected, Virtual 00364 // Description: 00365 //////////////////////////////////////////////////////////////////// 00366 bool BoundingBox:: 00367 around_boxes(const BoundingVolume **first, 00368 const BoundingVolume **last) { 00369 return around_finite(first, last); 00370 } 00371 00372 //////////////////////////////////////////////////////////////////// 00373 // Function: BoundingBox::around_hexahedrons 00374 // Access: Protected, Virtual 00375 // Description: 00376 //////////////////////////////////////////////////////////////////// 00377 bool BoundingBox:: 00378 around_hexahedrons(const BoundingVolume **first, 00379 const BoundingVolume **last) { 00380 return around_finite(first, last); 00381 } 00382 00383 //////////////////////////////////////////////////////////////////// 00384 // Function: BoundingBox::around_finite 00385 // Access: Protected 00386 // Description: 00387 //////////////////////////////////////////////////////////////////// 00388 bool BoundingBox:: 00389 around_finite(const BoundingVolume **first, 00390 const BoundingVolume **last) { 00391 nassertr(first != last, false); 00392 00393 // We're given a set of bounding volumes, at least the first one of 00394 // which is guaranteed to be finite and nonempty. Some others may 00395 // not be. 00396 00397 // First, get the box of all the points to construct a bounding 00398 // box. 00399 const BoundingVolume **p = first; 00400 nassertr(!(*p)->is_empty() && !(*p)->is_infinite(), false); 00401 const FiniteBoundingVolume *vol = DCAST(FiniteBoundingVolume, *p); 00402 _min = vol->get_min(); 00403 _max = vol->get_max(); 00404 00405 for (++p; p != last; ++p) { 00406 nassertr(!(*p)->is_infinite(), false); 00407 if (!(*p)->is_empty()) { 00408 const FiniteBoundingVolume *vol = DCAST(FiniteBoundingVolume, *p); 00409 LPoint3f min1 = vol->get_min(); 00410 LPoint3f max1 = vol->get_max(); 00411 _min.set(min(_min[0], min1[0]), 00412 min(_min[1], min1[1]), 00413 min(_min[2], min1[2])); 00414 _max.set(max(_max[0], max1[0]), 00415 max(_max[1], max1[1]), 00416 max(_max[2], max1[2])); 00417 } 00418 } 00419 00420 _flags = 0; 00421 return true; 00422 } 00423 00424 //////////////////////////////////////////////////////////////////// 00425 // Function: BoundingBox::contains_point 00426 // Access: Protected, Virtual 00427 // Description: 00428 //////////////////////////////////////////////////////////////////// 00429 int BoundingBox:: 00430 contains_point(const LPoint3f &point) const { 00431 nassertr(!point.is_nan(), IF_no_intersection); 00432 00433 if (is_empty()) { 00434 return IF_no_intersection; 00435 00436 } else if (is_infinite()) { 00437 return IF_possible | IF_some | IF_all; 00438 00439 } else { 00440 if (point[0] >= _min[0] && point[0] <= _max[0] && 00441 point[1] >= _min[1] && point[1] <= _max[1] && 00442 point[2] >= _min[2] && point[2] <= _max[2]) { 00443 return IF_possible | IF_some | IF_all; 00444 } else { 00445 return IF_no_intersection; 00446 } 00447 } 00448 } 00449 00450 //////////////////////////////////////////////////////////////////// 00451 // Function: BoundingBox::contains_lineseg 00452 // Access: Protected, Virtual 00453 // Description: 00454 //////////////////////////////////////////////////////////////////// 00455 int BoundingBox:: 00456 contains_lineseg(const LPoint3f &a, const LPoint3f &b) const { 00457 nassertr(!a.is_nan() && !b.is_nan(), IF_no_intersection); 00458 00459 if (a == b) { 00460 return contains_point(a); 00461 } 00462 if (is_empty()) { 00463 return IF_no_intersection; 00464 00465 } else if (is_infinite()) { 00466 return IF_possible | IF_some | IF_all; 00467 00468 } else { 00469 // Set a bit for each plane a and b are on the wrong side of. 00470 unsigned int a_bits = 0; 00471 00472 if (a[0] < _min[0]) { 00473 a_bits |= 0x01; 00474 } else if (a[0] > _max[0]) { 00475 a_bits |= 0x02; 00476 } 00477 00478 if (a[1] < _min[1]) { 00479 a_bits |= 0x04; 00480 } else if (a[1] > _max[1]) { 00481 a_bits |= 0x08; 00482 } 00483 00484 if (a[2] < _min[2]) { 00485 a_bits |= 0x10; 00486 } else if (a[2] > _max[2]) { 00487 a_bits |= 0x20; 00488 } 00489 00490 unsigned int b_bits = 0; 00491 00492 if (b[0] < _min[0]) { 00493 b_bits |= 0x01; 00494 } else if (b[0] > _max[0]) { 00495 b_bits |= 0x02; 00496 } 00497 00498 if (b[1] < _min[1]) { 00499 b_bits |= 0x04; 00500 } else if (b[1] > _max[1]) { 00501 b_bits |= 0x08; 00502 } 00503 00504 if (b[2] < _min[2]) { 00505 b_bits |= 0x10; 00506 } else if (b[2] > _max[2]) { 00507 b_bits |= 0x20; 00508 } 00509 00510 if ((a_bits & b_bits) != 0) { 00511 // If there are any bits in common, the segment is wholly 00512 // outside the box (both points are on the wrong side of the 00513 // same plane). 00514 return IF_no_intersection; 00515 00516 } else if ((a_bits | b_bits) == 0) { 00517 // If there are no bits at all, the segment is wholly within the 00518 // box. 00519 return IF_possible | IF_some | IF_all; 00520 00521 } else if (a_bits == 0 || b_bits == 0) { 00522 // If either point is within the box, the segment is partially 00523 // within the box. 00524 return IF_possible | IF_some; 00525 00526 } else { 00527 unsigned int differ = (a_bits ^ b_bits); 00528 if (differ == 0x03 || differ == 0x0c || differ == 0x30) { 00529 // If the line segment stretches straight across the box, the 00530 // segment is partially within. 00531 return IF_possible | IF_some; 00532 00533 } else { 00534 // Otherwise, it's hard to tell whether it does or doesn't. 00535 return IF_possible; 00536 } 00537 } 00538 } 00539 } 00540 00541 //////////////////////////////////////////////////////////////////// 00542 // Function: BoundingBox::contains_sphere 00543 // Access: Protected, Virtual 00544 // Description: Double-dispatch support: called by contains_other() 00545 // when the type we're testing for intersection is known 00546 // to be a sphere. 00547 //////////////////////////////////////////////////////////////////// 00548 int BoundingBox:: 00549 contains_sphere(const BoundingSphere *sphere) const { 00550 return contains_finite(sphere); 00551 } 00552 00553 //////////////////////////////////////////////////////////////////// 00554 // Function: BoundingBox::contains_box 00555 // Access: Protected, Virtual 00556 // Description: Double-dispatch support: called by contains_other() 00557 // when the type we're testing for intersection is known 00558 // to be a box. 00559 //////////////////////////////////////////////////////////////////// 00560 int BoundingBox:: 00561 contains_box(const BoundingBox *box) const { 00562 nassertr(!is_empty() && !is_infinite(), 0); 00563 nassertr(!box->is_empty() && !box->is_infinite(), 0); 00564 00565 const LPoint3f &min1 = box->get_minq(); 00566 const LPoint3f &max1 = box->get_maxq(); 00567 00568 if (min1[0] >= _min[0] && max1[0] <= _max[0] && 00569 min1[1] >= _min[1] && max1[1] <= _max[1] && 00570 min1[2] >= _min[2] && max1[2] <= _max[2]) { 00571 // The other volume is completely within this volume. 00572 return IF_possible | IF_some | IF_all; 00573 00574 } else if (max1[0] >= _min[0] && min1[0] <= _max[0] && 00575 max1[1] >= _min[1] && min1[1] <= _max[1] && 00576 max1[2] >= _min[2] && min1[2] <= _max[2]) { 00577 // The other volume is partially within this volume. 00578 return IF_possible; 00579 00580 } else { 00581 // The other volume is not within this volume. 00582 return IF_no_intersection; 00583 } 00584 } 00585 00586 //////////////////////////////////////////////////////////////////// 00587 // Function: BoundingBox::contains_hexahedron 00588 // Access: Protected, Virtual 00589 // Description: Double-dispatch support: called by contains_other() 00590 // when the type we're testing for intersection is known 00591 // to be a hexahedron. 00592 //////////////////////////////////////////////////////////////////// 00593 int BoundingBox:: 00594 contains_hexahedron(const BoundingHexahedron *hexahedron) const { 00595 // First, try the quick bounding-box test. If that's decisive, 00596 // we'll accept it. 00597 int result = contains_finite(hexahedron); 00598 if (result == IF_no_intersection || ((result & IF_all) != 0)) { 00599 return result; 00600 } 00601 00602 // If that was inconclusive, we'll look more closely with the 00603 // somewhat more expensive reverse answer. 00604 return hexahedron->contains_box(this) & ~IF_all; 00605 } 00606 00607 //////////////////////////////////////////////////////////////////// 00608 // Function: BoundingBox::contains_line 00609 // Access: Protected, Virtual 00610 // Description: Double-dispatch support: called by contains_other() 00611 // when the type we're testing for intersection is known 00612 // to be a line. 00613 //////////////////////////////////////////////////////////////////// 00614 int BoundingBox:: 00615 contains_line(const BoundingLine *line) const { 00616 return line->contains_box(this) & ~IF_all; 00617 } 00618 00619 //////////////////////////////////////////////////////////////////// 00620 // Function: BoundingBox::contains_plane 00621 // Access: Protected, Virtual 00622 // Description: Double-dispatch support: called by contains_other() 00623 // when the type we're testing for intersection is known 00624 // to be a plane. 00625 //////////////////////////////////////////////////////////////////// 00626 int BoundingBox:: 00627 contains_plane(const BoundingPlane *plane) const { 00628 return plane->contains_box(this) & ~IF_all; 00629 } 00630 00631 //////////////////////////////////////////////////////////////////// 00632 // Function: BoundingBox::contains_finite 00633 // Access: Protected 00634 // Description: 00635 //////////////////////////////////////////////////////////////////// 00636 int BoundingBox:: 00637 contains_finite(const FiniteBoundingVolume *volume) const { 00638 nassertr(!is_empty() && !is_infinite(), 0); 00639 nassertr(!volume->is_empty() && !volume->is_infinite(), 0); 00640 00641 LPoint3f min1 = volume->get_min(); 00642 LPoint3f max1 = volume->get_max(); 00643 00644 if (min1[0] >= _min[0] && max1[0] <= _max[0] && 00645 min1[1] >= _min[1] && max1[1] <= _max[1] && 00646 min1[2] >= _min[2] && max1[2] <= _max[2]) { 00647 // The other volume is completely within this volume. 00648 return IF_possible | IF_some | IF_all; 00649 00650 } else if (max1[0] >= _min[0] && min1[0] <= _max[0] && 00651 max1[1] >= _min[1] && min1[1] <= _max[1] && 00652 max1[2] >= _min[2] && min1[2] <= _max[2]) { 00653 // The other volume is partially within this volume. 00654 return IF_possible; 00655 00656 } else { 00657 // The other volume is not within this volume. 00658 return IF_no_intersection; 00659 } 00660 }