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 LPoint3 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 LPoint3 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 PN_stdfloat 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 LPoint3 BoundingBox:: 00093 get_approx_center() const { 00094 nassertr(!is_empty(), LPoint3::zero()); 00095 nassertr(!is_infinite(), LPoint3::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 LMatrix4 &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 LPoint3 x = get_point(0) * mat; 00112 LPoint3 n = x; 00113 for (int i = 1; i < 8; ++i) { 00114 LPoint3 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 LPoint3 &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_box 00208 // Access: Protected, Virtual 00209 // Description: 00210 //////////////////////////////////////////////////////////////////// 00211 bool BoundingBox:: 00212 extend_by_box(const BoundingBox *box) { 00213 nassertr(!box->is_empty() && !box->is_infinite(), false); 00214 nassertr(!is_infinite(), false); 00215 00216 if (is_empty()) { 00217 _min = box->_min; 00218 _max = box->_max; 00219 _flags = 0; 00220 00221 } else { 00222 _min.set(min(_min[0], box->_min[0]), 00223 min(_min[1], box->_min[1]), 00224 min(_min[2], box->_min[2])); 00225 _max.set(max(_max[0], box->_max[0]), 00226 max(_max[1], box->_max[1]), 00227 max(_max[2], box->_max[2])); 00228 } 00229 return true; 00230 } 00231 00232 //////////////////////////////////////////////////////////////////// 00233 // Function: BoundingBox::extend_by_finite 00234 // Access: Protected, Virtual 00235 // Description: 00236 //////////////////////////////////////////////////////////////////// 00237 bool BoundingBox:: 00238 extend_by_finite(const FiniteBoundingVolume *volume) { 00239 nassertr(!volume->is_empty() && !volume->is_infinite(), false); 00240 00241 LVector3 min1 = volume->get_min(); 00242 LVector3 max1 = volume->get_max(); 00243 00244 if (is_empty()) { 00245 _min = min1; 00246 _max = max1; 00247 _flags = 0; 00248 00249 } else { 00250 _min.set(min(_min[0], min1[0]), 00251 min(_min[1], min1[1]), 00252 min(_min[2], min1[2])); 00253 _max.set(max(_max[0], max1[0]), 00254 max(_max[1], max1[1]), 00255 max(_max[2], max1[2])); 00256 } 00257 00258 return true; 00259 } 00260 00261 //////////////////////////////////////////////////////////////////// 00262 // Function: BoundingBox::around_points 00263 // Access: Protected, Virtual 00264 // Description: 00265 //////////////////////////////////////////////////////////////////// 00266 bool BoundingBox:: 00267 around_points(const LPoint3 *first, const LPoint3 *last) { 00268 nassertr(first != last, false); 00269 00270 // Get the minmax of all the points to construct a bounding box. 00271 const LPoint3 *p = first; 00272 00273 #ifndef NDEBUG 00274 // Skip any NaN points. 00275 int skipped_nan = 0; 00276 while (p != last && (*p).is_nan()) { 00277 ++p; 00278 ++skipped_nan; 00279 } 00280 if (p == last) { 00281 mathutil_cat.warning() 00282 << "BoundingBox around NaN\n"; 00283 return false; 00284 } 00285 #endif 00286 00287 _min = *p; 00288 _max = *p; 00289 ++p; 00290 00291 #ifndef NDEBUG 00292 // Skip more NaN points. 00293 while (p != last && (*p).is_nan()) { 00294 ++p; 00295 ++skipped_nan; 00296 } 00297 #endif 00298 00299 while (p != last) { 00300 #ifndef NDEBUG 00301 // Skip more NaN points. 00302 if ((*p).is_nan()) { 00303 ++skipped_nan; 00304 } else 00305 #endif 00306 { 00307 _min.set(min(_min[0], (*p)[0]), 00308 min(_min[1], (*p)[1]), 00309 min(_min[2], (*p)[2])); 00310 _max.set(max(_max[0], (*p)[0]), 00311 max(_max[1], (*p)[1]), 00312 max(_max[2], (*p)[2])); 00313 } 00314 ++p; 00315 } 00316 00317 #ifndef NDEBUG 00318 if (skipped_nan != 0) { 00319 mathutil_cat.warning() 00320 << "BoundingBox ignored " << skipped_nan << " NaN points of " 00321 << (last - first) << " total.\n"; 00322 } 00323 #endif 00324 00325 _flags = 0; 00326 00327 return true; 00328 } 00329 00330 //////////////////////////////////////////////////////////////////// 00331 // Function: BoundingBox::around_finite 00332 // Access: Protected, Virtual 00333 // Description: 00334 //////////////////////////////////////////////////////////////////// 00335 bool BoundingBox:: 00336 around_finite(const BoundingVolume **first, 00337 const BoundingVolume **last) { 00338 nassertr(first != last, false); 00339 00340 // We're given a set of bounding volumes, at least the first one of 00341 // which is guaranteed to be finite and nonempty. Some others may 00342 // not be. 00343 00344 // First, get the box of all the points to construct a bounding 00345 // box. 00346 const BoundingVolume **p = first; 00347 nassertr(!(*p)->is_empty() && !(*p)->is_infinite(), false); 00348 const FiniteBoundingVolume *vol = DCAST(FiniteBoundingVolume, *p); 00349 _min = vol->get_min(); 00350 _max = vol->get_max(); 00351 00352 for (++p; p != last; ++p) { 00353 nassertr(!(*p)->is_infinite(), false); 00354 if (!(*p)->is_empty()) { 00355 const FiniteBoundingVolume *vol = DCAST(FiniteBoundingVolume, *p); 00356 LPoint3 min1 = vol->get_min(); 00357 LPoint3 max1 = vol->get_max(); 00358 _min.set(min(_min[0], min1[0]), 00359 min(_min[1], min1[1]), 00360 min(_min[2], min1[2])); 00361 _max.set(max(_max[0], max1[0]), 00362 max(_max[1], max1[1]), 00363 max(_max[2], max1[2])); 00364 } 00365 } 00366 00367 _flags = 0; 00368 return true; 00369 } 00370 00371 //////////////////////////////////////////////////////////////////// 00372 // Function: BoundingBox::contains_point 00373 // Access: Protected, Virtual 00374 // Description: 00375 //////////////////////////////////////////////////////////////////// 00376 int BoundingBox:: 00377 contains_point(const LPoint3 &point) const { 00378 nassertr(!point.is_nan(), IF_no_intersection); 00379 00380 if (is_empty()) { 00381 return IF_no_intersection; 00382 00383 } else if (is_infinite()) { 00384 return IF_possible | IF_some | IF_all; 00385 00386 } else { 00387 if (point[0] >= _min[0] && point[0] <= _max[0] && 00388 point[1] >= _min[1] && point[1] <= _max[1] && 00389 point[2] >= _min[2] && point[2] <= _max[2]) { 00390 return IF_possible | IF_some | IF_all; 00391 } else { 00392 return IF_no_intersection; 00393 } 00394 } 00395 } 00396 00397 //////////////////////////////////////////////////////////////////// 00398 // Function: BoundingBox::contains_lineseg 00399 // Access: Protected, Virtual 00400 // Description: 00401 //////////////////////////////////////////////////////////////////// 00402 int BoundingBox:: 00403 contains_lineseg(const LPoint3 &a, const LPoint3 &b) const { 00404 nassertr(!a.is_nan() && !b.is_nan(), IF_no_intersection); 00405 00406 if (a == b) { 00407 return contains_point(a); 00408 } 00409 if (is_empty()) { 00410 return IF_no_intersection; 00411 00412 } else if (is_infinite()) { 00413 return IF_possible | IF_some | IF_all; 00414 00415 } else { 00416 // Set a bit for each plane a and b are on the wrong side of. 00417 unsigned int a_bits = 0; 00418 00419 if (a[0] < _min[0]) { 00420 a_bits |= 0x01; 00421 } else if (a[0] > _max[0]) { 00422 a_bits |= 0x02; 00423 } 00424 00425 if (a[1] < _min[1]) { 00426 a_bits |= 0x04; 00427 } else if (a[1] > _max[1]) { 00428 a_bits |= 0x08; 00429 } 00430 00431 if (a[2] < _min[2]) { 00432 a_bits |= 0x10; 00433 } else if (a[2] > _max[2]) { 00434 a_bits |= 0x20; 00435 } 00436 00437 unsigned int b_bits = 0; 00438 00439 if (b[0] < _min[0]) { 00440 b_bits |= 0x01; 00441 } else if (b[0] > _max[0]) { 00442 b_bits |= 0x02; 00443 } 00444 00445 if (b[1] < _min[1]) { 00446 b_bits |= 0x04; 00447 } else if (b[1] > _max[1]) { 00448 b_bits |= 0x08; 00449 } 00450 00451 if (b[2] < _min[2]) { 00452 b_bits |= 0x10; 00453 } else if (b[2] > _max[2]) { 00454 b_bits |= 0x20; 00455 } 00456 00457 if ((a_bits & b_bits) != 0) { 00458 // If there are any bits in common, the segment is wholly 00459 // outside the box (both points are on the wrong side of the 00460 // same plane). 00461 return IF_no_intersection; 00462 00463 } else if ((a_bits | b_bits) == 0) { 00464 // If there are no bits at all, the segment is wholly within the 00465 // box. 00466 return IF_possible | IF_some | IF_all; 00467 00468 } else if (a_bits == 0 || b_bits == 0) { 00469 // If either point is within the box, the segment is partially 00470 // within the box. 00471 return IF_possible | IF_some; 00472 00473 } else { 00474 unsigned int differ = (a_bits ^ b_bits); 00475 if (differ == 0x03 || differ == 0x0c || differ == 0x30) { 00476 // If the line segment stretches straight across the box, the 00477 // segment is partially within. 00478 return IF_possible | IF_some; 00479 00480 } else { 00481 // Otherwise, it's hard to tell whether it does or doesn't. 00482 return IF_possible; 00483 } 00484 } 00485 } 00486 } 00487 00488 //////////////////////////////////////////////////////////////////// 00489 // Function: BoundingBox::contains_box 00490 // Access: Protected, Virtual 00491 // Description: Double-dispatch support: called by contains_other() 00492 // when the type we're testing for intersection is known 00493 // to be a box. 00494 //////////////////////////////////////////////////////////////////// 00495 int BoundingBox:: 00496 contains_box(const BoundingBox *box) const { 00497 nassertr(!is_empty() && !is_infinite(), 0); 00498 nassertr(!box->is_empty() && !box->is_infinite(), 0); 00499 00500 const LPoint3 &min1 = box->get_minq(); 00501 const LPoint3 &max1 = box->get_maxq(); 00502 00503 if (min1[0] >= _min[0] && max1[0] <= _max[0] && 00504 min1[1] >= _min[1] && max1[1] <= _max[1] && 00505 min1[2] >= _min[2] && max1[2] <= _max[2]) { 00506 // The other volume is completely within this volume. 00507 return IF_possible | IF_some | IF_all; 00508 00509 } else if (max1[0] >= _min[0] && min1[0] <= _max[0] && 00510 max1[1] >= _min[1] && min1[1] <= _max[1] && 00511 max1[2] >= _min[2] && min1[2] <= _max[2]) { 00512 // The other volume is partially within this volume. 00513 return IF_possible; 00514 00515 } else { 00516 // The other volume is not within this volume. 00517 return IF_no_intersection; 00518 } 00519 } 00520 00521 //////////////////////////////////////////////////////////////////// 00522 // Function: BoundingBox::contains_hexahedron 00523 // Access: Protected, Virtual 00524 // Description: Double-dispatch support: called by contains_other() 00525 // when the type we're testing for intersection is known 00526 // to be a hexahedron. 00527 //////////////////////////////////////////////////////////////////// 00528 int BoundingBox:: 00529 contains_hexahedron(const BoundingHexahedron *hexahedron) const { 00530 // First, try the quick bounding-box test. If that's decisive, 00531 // we'll accept it. 00532 int result = contains_finite(hexahedron); 00533 if (result == IF_no_intersection || ((result & IF_all) != 0)) { 00534 return result; 00535 } 00536 00537 // If that was inconclusive, we'll look more closely with the 00538 // somewhat more expensive reverse answer. 00539 return hexahedron->contains_box(this) & ~IF_all; 00540 } 00541 00542 //////////////////////////////////////////////////////////////////// 00543 // Function: BoundingBox::contains_line 00544 // Access: Protected, Virtual 00545 // Description: Double-dispatch support: called by contains_other() 00546 // when the type we're testing for intersection is known 00547 // to be a line. 00548 //////////////////////////////////////////////////////////////////// 00549 int BoundingBox:: 00550 contains_line(const BoundingLine *line) const { 00551 return line->contains_box(this) & ~IF_all; 00552 } 00553 00554 //////////////////////////////////////////////////////////////////// 00555 // Function: BoundingBox::contains_plane 00556 // Access: Protected, Virtual 00557 // Description: Double-dispatch support: called by contains_other() 00558 // when the type we're testing for intersection is known 00559 // to be a plane. 00560 //////////////////////////////////////////////////////////////////// 00561 int BoundingBox:: 00562 contains_plane(const BoundingPlane *plane) const { 00563 return plane->contains_box(this) & ~IF_all; 00564 } 00565 00566 //////////////////////////////////////////////////////////////////// 00567 // Function: BoundingBox::contains_finite 00568 // Access: Protected, Virtual 00569 // Description: 00570 //////////////////////////////////////////////////////////////////// 00571 int BoundingBox:: 00572 contains_finite(const FiniteBoundingVolume *volume) const { 00573 nassertr(!is_empty() && !is_infinite(), 0); 00574 nassertr(!volume->is_empty() && !volume->is_infinite(), 0); 00575 00576 LPoint3 min1 = volume->get_min(); 00577 LPoint3 max1 = volume->get_max(); 00578 00579 if (min1[0] >= _min[0] && max1[0] <= _max[0] && 00580 min1[1] >= _min[1] && max1[1] <= _max[1] && 00581 min1[2] >= _min[2] && max1[2] <= _max[2]) { 00582 // The other volume is completely within this volume. 00583 return IF_possible | IF_some | IF_all; 00584 00585 } else if (max1[0] >= _min[0] && min1[0] <= _max[0] && 00586 max1[1] >= _min[1] && min1[1] <= _max[1] && 00587 max1[2] >= _min[2] && min1[2] <= _max[2]) { 00588 // The other volume is partially within this volume. 00589 return IF_possible; 00590 00591 } else { 00592 // The other volume is not within this volume. 00593 return IF_no_intersection; 00594 } 00595 }