Panda3D

boundingBox.cxx

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 }
 All Classes Functions Variables Enumerations