Panda3D

unionBoundingVolume.cxx

00001 // Filename: unionBoundingVolume.cxx
00002 // Created by:  drose (08Feb12)
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 "unionBoundingVolume.h"
00016 #include "config_mathutil.h"
00017 #include "dcast.h"
00018 #include "indent.h"
00019 
00020 TypeHandle UnionBoundingVolume::_type_handle;
00021 
00022 ////////////////////////////////////////////////////////////////////
00023 //     Function: UnionBoundingVolume::Copy Constructor
00024 //       Access: Public
00025 //  Description: 
00026 ////////////////////////////////////////////////////////////////////
00027 UnionBoundingVolume::
00028 UnionBoundingVolume(const UnionBoundingVolume &copy) :
00029   GeometricBoundingVolume(copy),
00030   _components(copy._components)
00031 {
00032 }
00033 
00034 ////////////////////////////////////////////////////////////////////
00035 //     Function: UnionBoundingVolume::make_copy
00036 //       Access: Public, Virtual
00037 //  Description: 
00038 ////////////////////////////////////////////////////////////////////
00039 BoundingVolume *UnionBoundingVolume::
00040 make_copy() const {
00041   return new UnionBoundingVolume(*this);
00042 }
00043 
00044 ////////////////////////////////////////////////////////////////////
00045 //     Function: UnionBoundingVolume::get_approx_center
00046 //       Access: Public, Virtual
00047 //  Description: 
00048 ////////////////////////////////////////////////////////////////////
00049 LPoint3 UnionBoundingVolume::
00050 get_approx_center() const {
00051   nassertr(!is_empty(), LPoint3::zero());
00052   nassertr(!is_infinite(), LPoint3::zero());
00053 
00054   LPoint3 center = LPoint3::zero();
00055   for (Components::const_iterator ci = _components.begin();
00056        ci != _components.end();
00057        ++ci) {
00058     center += (*ci)->get_approx_center();
00059   }
00060 
00061   return center / (PN_stdfloat)_components.size();
00062 }
00063 
00064 ////////////////////////////////////////////////////////////////////
00065 //     Function: UnionBoundingVolume::xform
00066 //       Access: Public, Virtual
00067 //  Description: 
00068 ////////////////////////////////////////////////////////////////////
00069 void UnionBoundingVolume::
00070 xform(const LMatrix4 &mat) {
00071   nassertv(!mat.is_nan());
00072 
00073   for (Components::iterator ci = _components.begin();
00074        ci != _components.end();
00075        ++ci) {
00076     PT(GeometricBoundingVolume) copy = DCAST(GeometricBoundingVolume, (*ci)->make_copy());
00077     copy->xform(mat);
00078     (*ci) = copy;
00079   }
00080 }
00081 
00082 ////////////////////////////////////////////////////////////////////
00083 //     Function: UnionBoundingVolume::output
00084 //       Access: Public, Virtual
00085 //  Description: 
00086 ////////////////////////////////////////////////////////////////////
00087 void UnionBoundingVolume::
00088 output(ostream &out) const {
00089   if (is_empty()) {
00090     out << "union, empty";
00091   } else if (is_infinite()) {
00092     out << "union, infinite";
00093   } else {
00094     out << "union [";
00095     for (Components::const_iterator ci = _components.begin();
00096          ci != _components.end();
00097          ++ci) {
00098       out << " " << *(*ci);
00099     }
00100     out << " ]";
00101   }
00102 }
00103 
00104 ////////////////////////////////////////////////////////////////////
00105 //     Function: UnionBoundingVolume::write
00106 //       Access: Public, Virtual
00107 //  Description: 
00108 ////////////////////////////////////////////////////////////////////
00109 void UnionBoundingVolume::
00110 write(ostream &out, int indent_level) const {
00111   if (is_empty()) {
00112     indent(out, indent_level) << "union, empty\n";
00113   } else if (is_infinite()) {
00114     indent(out, indent_level) << "union, infinite\n";
00115   } else {
00116     indent(out, indent_level) << "union {\n";
00117     for (Components::const_iterator ci = _components.begin();
00118          ci != _components.end();
00119          ++ci) {
00120       (*ci)->write(out, indent_level + 2);
00121     }
00122     indent(out, indent_level) << "}\n";
00123   }
00124 }
00125 
00126 ////////////////////////////////////////////////////////////////////
00127 //     Function: UnionBoundingVolume::clear_components
00128 //       Access: Published
00129 //  Description: Removes all components from the volume.
00130 ////////////////////////////////////////////////////////////////////
00131 void UnionBoundingVolume::
00132 clear_components() {
00133   _components.clear();
00134   _flags = F_empty;
00135 }
00136 
00137 ////////////////////////////////////////////////////////////////////
00138 //     Function: UnionBoundingVolume::add_component
00139 //       Access: Published
00140 //  Description: Adds a new component to the volume.  This does not
00141 //               necessarily increase the total number of components
00142 //               by one, and you may or may not be able to find this
00143 //               component in the volume by a subsequent call to
00144 //               get_component(); certain optimizations may prevent
00145 //               the component from being added, or have other
00146 //               unexpected effects on the total set of components.
00147 ////////////////////////////////////////////////////////////////////
00148 void UnionBoundingVolume::
00149 add_component(const GeometricBoundingVolume *component) {
00150   if (component->is_infinite()) {
00151     _flags = F_infinite;
00152     _components.clear();
00153 
00154   } else if (component->is_empty() || is_infinite()) {
00155     // No-op.
00156 
00157   } else {
00158     size_t i = 0;
00159     while (i < _components.size()) {
00160       const GeometricBoundingVolume *existing = _components[i];
00161       ++i;
00162 
00163       int result = existing->contains(component);
00164       if ((result & IF_all) != 0) {
00165         // This new component is entirely within an existing
00166         // component; no need to do anything with it.
00167         return;
00168       }
00169 
00170       result = component->contains(existing);
00171       if ((result & IF_all) != 0) {
00172         // The existing component is entirely within this one; no need
00173         // to keep the existing one.
00174         --i;
00175         _components.erase(_components.begin() + i);
00176       }
00177     }
00178 
00179     _flags &= ~F_empty;
00180     _components.push_back(component);
00181   }
00182 }
00183 
00184 ////////////////////////////////////////////////////////////////////
00185 //     Function: UnionBoundingVolume::filter_intersection
00186 //       Access: Published
00187 //  Description: Removes from the union any components that have no
00188 //               intersection with the indicated volume.
00189 ////////////////////////////////////////////////////////////////////
00190 void UnionBoundingVolume::
00191 filter_intersection(const BoundingVolume *volume) {
00192   size_t i = 0;
00193   while (i < _components.size()) {
00194     const GeometricBoundingVolume *existing = _components[i];
00195     ++i;
00196 
00197     int result = volume->contains(existing);
00198     if ((result & IF_possible) == 0) {
00199       // There is no intersection.  Remove this component.
00200       --i;
00201       _components.erase(_components.begin() + i);
00202     }
00203   }
00204 
00205   if (_components.empty()) {
00206     _flags |= F_empty;
00207   }
00208 }
00209 
00210 ////////////////////////////////////////////////////////////////////
00211 //     Function: UnionBoundingVolume::extend_other
00212 //       Access: Protected, Virtual
00213 //  Description: 
00214 ////////////////////////////////////////////////////////////////////
00215 bool UnionBoundingVolume::
00216 extend_other(BoundingVolume *other) const {
00217   return other->extend_by_union(this);
00218 }
00219 
00220 ////////////////////////////////////////////////////////////////////
00221 //     Function: UnionBoundingVolume::around_other
00222 //       Access: Protected, Virtual
00223 //  Description: 
00224 ////////////////////////////////////////////////////////////////////
00225 bool UnionBoundingVolume::
00226 around_other(BoundingVolume *other,
00227              const BoundingVolume **first,
00228              const BoundingVolume **last) const {
00229   return other->around_unions(first, last);
00230 }
00231 
00232 ////////////////////////////////////////////////////////////////////
00233 //     Function: UnionBoundingVolume::contains_other
00234 //       Access: Protected, Virtual
00235 //  Description: 
00236 ////////////////////////////////////////////////////////////////////
00237 int UnionBoundingVolume::
00238 contains_other(const BoundingVolume *other) const {
00239   return other->contains_union(this);
00240 }
00241 
00242 ////////////////////////////////////////////////////////////////////
00243 //     Function: UnionBoundingVolume::extend_by_geometric
00244 //       Access: Protected
00245 //  Description: 
00246 ////////////////////////////////////////////////////////////////////
00247 bool UnionBoundingVolume::
00248 extend_by_geometric(const GeometricBoundingVolume *volume) {
00249   add_component(volume);
00250   return true;
00251 }
00252 
00253 ////////////////////////////////////////////////////////////////////
00254 //     Function: UnionBoundingVolume::around_geometric
00255 //       Access: Protected
00256 //  Description: 
00257 ////////////////////////////////////////////////////////////////////
00258 bool UnionBoundingVolume::
00259 around_geometric(const BoundingVolume **first,
00260                  const BoundingVolume **last) {
00261   nassertr(first != last, false);
00262 
00263   clear_components();
00264 
00265   const BoundingVolume **p = first;
00266   while (p != last) {
00267     nassertr(!(*p)->is_infinite(), false);
00268     if (!(*p)->is_empty()) {
00269       const GeometricBoundingVolume *volume = (*p)->as_geometric_bounding_volume();
00270       if (volume != (GeometricBoundingVolume *)NULL) {
00271         add_component(volume);
00272       } else {
00273         set_infinite();
00274         _components.clear();
00275         return false;
00276       }
00277     }
00278   }
00279 
00280   return true;
00281 }
00282 
00283 ////////////////////////////////////////////////////////////////////
00284 //     Function: UnionBoundingVolume::contains_point
00285 //       Access: Protected, Virtual
00286 //  Description: 
00287 ////////////////////////////////////////////////////////////////////
00288 int UnionBoundingVolume::
00289 contains_point(const LPoint3 &point) const {
00290   nassertr(!point.is_nan(), IF_no_intersection);
00291 
00292   int result = 0;
00293   for (Components::const_iterator ci = _components.begin();
00294        ci != _components.end();
00295        ++ci) {
00296     result |= (*ci)->contains(point);
00297     if ((result & (IF_all | IF_dont_understand)) != 0) {
00298       // No point in looking further.
00299       break;
00300     }
00301   }
00302 
00303   return result;
00304 }
00305 
00306 ////////////////////////////////////////////////////////////////////
00307 //     Function: UnionBoundingVolume::contains_lineseg
00308 //       Access: Protected, Virtual
00309 //  Description: 
00310 ////////////////////////////////////////////////////////////////////
00311 int UnionBoundingVolume::
00312 contains_lineseg(const LPoint3 &a, const LPoint3 &b) const {
00313   nassertr(!a.is_nan() && !b.is_nan(), IF_no_intersection);
00314 
00315   int result = 0;
00316   for (Components::const_iterator ci = _components.begin();
00317        ci != _components.end();
00318        ++ci) {
00319     result |= (*ci)->contains(a, b);
00320     if ((result & (IF_all | IF_dont_understand)) != 0) {
00321       // No point in looking further.
00322       break;
00323     }
00324   }
00325 
00326   return result;
00327 }
00328 
00329 ////////////////////////////////////////////////////////////////////
00330 //     Function: UnionBoundingVolume::contains_sphere
00331 //       Access: Protected, Virtual
00332 //  Description: Double-dispatch support: called by contains_other()
00333 //               when the type we're testing for intersection is known
00334 //               to be a sphere.
00335 ////////////////////////////////////////////////////////////////////
00336 int UnionBoundingVolume::
00337 contains_sphere(const BoundingSphere *sphere) const {
00338   int result = 0;
00339   for (Components::const_iterator ci = _components.begin();
00340        ci != _components.end();
00341        ++ci) {
00342     result |= (*ci)->contains_sphere(sphere);
00343     if ((result & (IF_all | IF_dont_understand)) != 0) {
00344       // No point in looking further.
00345       break;
00346     }
00347   }
00348 
00349   return result;
00350 }
00351 
00352 ////////////////////////////////////////////////////////////////////
00353 //     Function: UnionBoundingVolume::contains_box
00354 //       Access: Protected, Virtual
00355 //  Description: Double-dispatch support: called by contains_other()
00356 //               when the type we're testing for intersection is known
00357 //               to be a box.
00358 ////////////////////////////////////////////////////////////////////
00359 int UnionBoundingVolume::
00360 contains_box(const BoundingBox *box) const {
00361   int result = 0;
00362   for (Components::const_iterator ci = _components.begin();
00363        ci != _components.end();
00364        ++ci) {
00365     result |= (*ci)->contains_box(box);
00366     if ((result & (IF_all | IF_dont_understand)) != 0) {
00367       // No point in looking further.
00368       break;
00369     }
00370   }
00371 
00372   return result;
00373 }
00374 
00375 ////////////////////////////////////////////////////////////////////
00376 //     Function: UnionBoundingVolume::contains_hexahedron
00377 //       Access: Protected, Virtual
00378 //  Description: Double-dispatch support: called by contains_other()
00379 //               when the type we're testing for intersection is known
00380 //               to be a hexahedron.
00381 ////////////////////////////////////////////////////////////////////
00382 int UnionBoundingVolume::
00383 contains_hexahedron(const BoundingHexahedron *hexahedron) const {
00384   int result = 0;
00385   for (Components::const_iterator ci = _components.begin();
00386        ci != _components.end();
00387        ++ci) {
00388     result |= (*ci)->contains_hexahedron(hexahedron);
00389     if ((result & (IF_all | IF_dont_understand)) != 0) {
00390       // No point in looking further.
00391       break;
00392     }
00393   }
00394 
00395   return result;
00396 }
00397 
00398 ////////////////////////////////////////////////////////////////////
00399 //     Function: UnionBoundingVolume::contains_line
00400 //       Access: Protected, Virtual
00401 //  Description: Double-dispatch support: called by contains_other()
00402 //               when the type we're testing for intersection is known
00403 //               to be a line.
00404 ////////////////////////////////////////////////////////////////////
00405 int UnionBoundingVolume::
00406 contains_line(const BoundingLine *line) const {
00407   int result = 0;
00408   for (Components::const_iterator ci = _components.begin();
00409        ci != _components.end();
00410        ++ci) {
00411     result |= (*ci)->contains_line(line);
00412     if ((result & (IF_all | IF_dont_understand)) != 0) {
00413       // No point in looking further.
00414       break;
00415     }
00416   }
00417 
00418   return result;
00419 }
00420 
00421 ////////////////////////////////////////////////////////////////////
00422 //     Function: UnionBoundingVolume::contains_plane
00423 //       Access: Protected, Virtual
00424 //  Description: Double-dispatch support: called by contains_other()
00425 //               when the type we're testing for intersection is known
00426 //               to be a plane.
00427 ////////////////////////////////////////////////////////////////////
00428 int UnionBoundingVolume::
00429 contains_plane(const BoundingPlane *plane) const {
00430   int result = 0;
00431   for (Components::const_iterator ci = _components.begin();
00432        ci != _components.end();
00433        ++ci) {
00434     result |= (*ci)->contains_plane(plane);
00435     if ((result & (IF_all | IF_dont_understand)) != 0) {
00436       // No point in looking further.
00437       break;
00438     }
00439   }
00440 
00441   return result;
00442 }
00443 
00444 ////////////////////////////////////////////////////////////////////
00445 //     Function: UnionBoundingVolume::contains_union
00446 //       Access: Protected, Virtual
00447 //  Description: Double-dispatch support: called by contains_other()
00448 //               when the type we're testing for intersection is known
00449 //               to be a union object.
00450 ////////////////////////////////////////////////////////////////////
00451 int UnionBoundingVolume::
00452 contains_union(const UnionBoundingVolume *unionv) const {
00453   int result = 0;
00454   for (Components::const_iterator ci = _components.begin();
00455        ci != _components.end();
00456        ++ci) {
00457     result |= (*ci)->contains_union(unionv);
00458     if ((result & (IF_all | IF_dont_understand)) != 0) {
00459       // No point in looking further.
00460       break;
00461     }
00462   }
00463 
00464   return result;
00465 }
00466 
00467 ////////////////////////////////////////////////////////////////////
00468 //     Function: UnionBoundingVolume::contains_intersection
00469 //       Access: Protected, Virtual
00470 //  Description: Double-dispatch support: called by contains_other()
00471 //               when the type we're testing for intersection is known
00472 //               to be an intersection object.
00473 ////////////////////////////////////////////////////////////////////
00474 int UnionBoundingVolume::
00475 contains_intersection(const IntersectionBoundingVolume *intersection) const {
00476   int result = 0;
00477   for (Components::const_iterator ci = _components.begin();
00478        ci != _components.end();
00479        ++ci) {
00480     result |= (*ci)->contains_intersection(intersection);
00481     if ((result & (IF_all | IF_dont_understand)) != 0) {
00482       // No point in looking further.
00483       break;
00484     }
00485   }
00486 
00487   return result;
00488 }
00489 
00490 ////////////////////////////////////////////////////////////////////
00491 //     Function: UnionBoundingVolume::contains_finite
00492 //       Access: Protected, Virtual
00493 //  Description: Generic handler for a FiniteBoundingVolume.
00494 ////////////////////////////////////////////////////////////////////
00495 int UnionBoundingVolume::
00496 contains_finite(const FiniteBoundingVolume *volume) const {
00497   int result = 0;
00498   for (Components::const_iterator ci = _components.begin();
00499        ci != _components.end();
00500        ++ci) {
00501     result |= (*ci)->contains_finite(volume);
00502     if ((result & (IF_all | IF_dont_understand)) != 0) {
00503       // No point in looking further.
00504       break;
00505     }
00506   }
00507 
00508   return result;
00509 }
00510 
00511 ////////////////////////////////////////////////////////////////////
00512 //     Function: UnionBoundingVolume::contains_geometric
00513 //       Access: Protected, Virtual
00514 //  Description: Generic handler for a GeometricBoundingVolume.
00515 ////////////////////////////////////////////////////////////////////
00516 int UnionBoundingVolume::
00517 contains_geometric(const GeometricBoundingVolume *volume) const {
00518   int result = 0;
00519   for (Components::const_iterator ci = _components.begin();
00520        ci != _components.end();
00521        ++ci) {
00522     result |= (*ci)->contains_geometric(volume);
00523     if ((result & (IF_all | IF_dont_understand)) != 0) {
00524       // No point in looking further.
00525       break;
00526     }
00527   }
00528 
00529   return result;
00530 }
00531 
00532 ////////////////////////////////////////////////////////////////////
00533 //     Function: UnionBoundingVolume::other_contains_union
00534 //       Access: Protected, Virtual
00535 //  Description: Generic reverse-direction comparison.  Called by
00536 //               BoundingVolumes that do not implement
00537 //               contains_union() explicitly.  This returns the test
00538 //               of whether the other volume contains this volume.
00539 ////////////////////////////////////////////////////////////////////
00540 int UnionBoundingVolume::
00541 other_contains_union(const BoundingVolume *volume) const {
00542   int all_result = IF_possible | IF_some | IF_all;
00543   int some_result = 0;
00544   for (Components::const_iterator ci = _components.begin();
00545        ci != _components.end();
00546        ++ci) {
00547     int this_result = volume->contains(*ci);
00548     if ((this_result & IF_dont_understand) != 0) {
00549       some_result |= IF_dont_understand;
00550       break;
00551     }
00552     all_result &= this_result;
00553     some_result |= this_result;
00554   }
00555 
00556   some_result &= ~IF_all;
00557   return some_result | all_result;
00558 }
00559 
 All Classes Functions Variables Enumerations