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