Panda3D

intersectionBoundingVolume.cxx

00001 // Filename: intersectionBoundingVolume.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 "intersectionBoundingVolume.h"
00016 #include "unionBoundingVolume.h"
00017 #include "config_mathutil.h"
00018 #include "dcast.h"
00019 
00020 TypeHandle IntersectionBoundingVolume::_type_handle;
00021 
00022 ////////////////////////////////////////////////////////////////////
00023 //     Function: IntersectionBoundingVolume::Copy Constructor
00024 //       Access: Public
00025 //  Description: 
00026 ////////////////////////////////////////////////////////////////////
00027 IntersectionBoundingVolume::
00028 IntersectionBoundingVolume(const IntersectionBoundingVolume &copy) :
00029   GeometricBoundingVolume(copy),
00030   _components(copy._components)
00031 {
00032 }
00033 
00034 ////////////////////////////////////////////////////////////////////
00035 //     Function: IntersectionBoundingVolume::make_copy
00036 //       Access: Public, Virtual
00037 //  Description: 
00038 ////////////////////////////////////////////////////////////////////
00039 BoundingVolume *IntersectionBoundingVolume::
00040 make_copy() const {
00041   return new IntersectionBoundingVolume(*this);
00042 }
00043 
00044 ////////////////////////////////////////////////////////////////////
00045 //     Function: IntersectionBoundingVolume::get_approx_center
00046 //       Access: Public, Virtual
00047 //  Description: 
00048 ////////////////////////////////////////////////////////////////////
00049 LPoint3 IntersectionBoundingVolume::
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: IntersectionBoundingVolume::xform
00066 //       Access: Public, Virtual
00067 //  Description: 
00068 ////////////////////////////////////////////////////////////////////
00069 void IntersectionBoundingVolume::
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: IntersectionBoundingVolume::output
00084 //       Access: Public, Virtual
00085 //  Description: 
00086 ////////////////////////////////////////////////////////////////////
00087 void IntersectionBoundingVolume::
00088 output(ostream &out) const {
00089   if (is_empty()) {
00090     out << "intersection, empty";
00091   } else if (is_infinite()) {
00092     out << "intersection, infinite";
00093   } else {
00094     out << "intersection [";
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: IntersectionBoundingVolume::write
00106 //       Access: Public, Virtual
00107 //  Description: 
00108 ////////////////////////////////////////////////////////////////////
00109 void IntersectionBoundingVolume::
00110 write(ostream &out, int indent_level) const {
00111   if (is_empty()) {
00112     indent(out, indent_level) << "intersection, empty\n";
00113   } else if (is_infinite()) {
00114     indent(out, indent_level) << "intersection, infinite\n";
00115   } else {
00116     indent(out, indent_level) << "intersection {\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: IntersectionBoundingVolume::clear_components
00128 //       Access: Published
00129 //  Description: Removes all components from the volume.
00130 ////////////////////////////////////////////////////////////////////
00131 void IntersectionBoundingVolume::
00132 clear_components() {
00133   _components.clear();
00134   _flags = F_infinite;
00135 }
00136 
00137 ////////////////////////////////////////////////////////////////////
00138 //     Function: IntersectionBoundingVolume::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 IntersectionBoundingVolume::
00149 add_component(const GeometricBoundingVolume *component) {
00150   CPT(GeometricBoundingVolume) gbv;
00151 
00152   if (component->is_exact_type(UnionBoundingVolume::get_class_type())) {
00153     // Here's a special case.  We'll construct a new union that
00154     // includes only those components that have some intersection with
00155     // our existing components.  (No need to include the components
00156     // that have no intersection.)
00157     PT(UnionBoundingVolume) unionv = DCAST(UnionBoundingVolume, component->make_copy());
00158     unionv->filter_intersection(this);
00159 
00160     // Save the modified union in a PT() so it won't be destructed.
00161     gbv = unionv.p();
00162 
00163     if (unionv->get_num_components() == 1) {
00164       // If there's only one component left, use just that one.
00165       gbv = unionv->get_component(0);
00166     }
00167 
00168     component = gbv;
00169   }
00170 
00171   if (component->is_empty()) {
00172     _flags = F_empty;
00173     _components.clear();
00174 
00175   } else if (component->is_infinite() || is_empty()) {
00176     // No-op.
00177 
00178   } else if (component->is_exact_type(IntersectionBoundingVolume::get_class_type())) {
00179     // Another special case.  Just more components.
00180     const IntersectionBoundingVolume *other = DCAST(IntersectionBoundingVolume, component);
00181     for (Components::const_iterator ci = other->_components.begin();
00182          ci != other->_components.end();
00183          ++ci) {
00184       add_component(*ci);
00185     }
00186     
00187   } else {
00188     // The general case.
00189     size_t i = 0;
00190     while (i < _components.size()) {
00191       const GeometricBoundingVolume *existing = _components[i];
00192       ++i;
00193 
00194       int result = component->contains(existing);
00195       if ((result & IF_all) != 0) {
00196         // The existing component is entirely within this one; no need
00197         // to do anything with it.
00198         return;
00199 
00200       } else if (result == 0) {
00201         // No intersection between these components; we're now empty.
00202         _flags = F_empty;
00203         _components.clear();
00204         return;
00205       }
00206 
00207       result = existing->contains(component);
00208       if ((result & IF_all) != 0) {
00209         // This new component is entirely within an existing
00210         // component; no need to keep the existing one.
00211         --i;
00212         _components.erase(_components.begin() + i);
00213 
00214       } else if (result == 0) {
00215         // No intersection between these components; we're now empty.
00216         _flags = F_empty;
00217         _components.clear();
00218         return;
00219       }
00220     }
00221 
00222     _flags &= ~F_infinite;
00223     _components.push_back(component);
00224   }
00225 }
00226 
00227 ////////////////////////////////////////////////////////////////////
00228 //     Function: IntersectionBoundingVolume::extend_other
00229 //       Access: Protected, Virtual
00230 //  Description: 
00231 ////////////////////////////////////////////////////////////////////
00232 bool IntersectionBoundingVolume::
00233 extend_other(BoundingVolume *other) const {
00234   return other->extend_by_intersection(this);
00235 }
00236 
00237 ////////////////////////////////////////////////////////////////////
00238 //     Function: IntersectionBoundingVolume::around_other
00239 //       Access: Protected, Virtual
00240 //  Description: 
00241 ////////////////////////////////////////////////////////////////////
00242 bool IntersectionBoundingVolume::
00243 around_other(BoundingVolume *other,
00244              const BoundingVolume **first,
00245              const BoundingVolume **last) const {
00246   return other->around_intersections(first, last);
00247 }
00248 
00249 ////////////////////////////////////////////////////////////////////
00250 //     Function: IntersectionBoundingVolume::contains_other
00251 //       Access: Protected, Virtual
00252 //  Description: 
00253 ////////////////////////////////////////////////////////////////////
00254 int IntersectionBoundingVolume::
00255 contains_other(const BoundingVolume *other) const {
00256   return other->contains_intersection(this);
00257 }
00258 
00259 ////////////////////////////////////////////////////////////////////
00260 //     Function: IntersectionBoundingVolume::contains_point
00261 //       Access: Protected, Virtual
00262 //  Description: 
00263 ////////////////////////////////////////////////////////////////////
00264 int IntersectionBoundingVolume::
00265 contains_point(const LPoint3 &point) const {
00266   nassertr(!point.is_nan(), IF_no_intersection);
00267 
00268   int result = IF_possible | IF_some | IF_all;
00269   for (Components::const_iterator ci = _components.begin();
00270        ci != _components.end();
00271        ++ci) {
00272     int this_result = (*ci)->contains(point);
00273     if ((this_result & IF_dont_understand) != 0) {
00274       result |= IF_dont_understand;
00275       break;
00276     }
00277     result &= this_result;
00278     if ((result & IF_possible) == 0) {
00279       // No point in looking further.
00280       break;
00281     }
00282   }
00283 
00284   return result;
00285 }
00286 
00287 ////////////////////////////////////////////////////////////////////
00288 //     Function: IntersectionBoundingVolume::contains_lineseg
00289 //       Access: Protected, Virtual
00290 //  Description: 
00291 ////////////////////////////////////////////////////////////////////
00292 int IntersectionBoundingVolume::
00293 contains_lineseg(const LPoint3 &a, const LPoint3 &b) const {
00294   nassertr(!a.is_nan() && !b.is_nan(), IF_no_intersection);
00295 
00296   int result = IF_possible | IF_some | IF_all;
00297   for (Components::const_iterator ci = _components.begin();
00298        ci != _components.end();
00299        ++ci) {
00300     int this_result = (*ci)->contains(a, b);
00301     if ((this_result & IF_dont_understand) != 0) {
00302       result |= IF_dont_understand;
00303       break;
00304     }
00305     result &= this_result;
00306     if ((result & IF_possible) == 0) {
00307       // No point in looking further.
00308       break;
00309     }
00310   }
00311 
00312   return result;
00313 }
00314 
00315 ////////////////////////////////////////////////////////////////////
00316 //     Function: IntersectionBoundingVolume::contains_sphere
00317 //       Access: Protected, Virtual
00318 //  Description: Double-dispatch support: called by contains_other()
00319 //               when the type we're testing for intersection is known
00320 //               to be a sphere.
00321 ////////////////////////////////////////////////////////////////////
00322 int IntersectionBoundingVolume::
00323 contains_sphere(const BoundingSphere *sphere) const {
00324   int result = IF_possible | IF_some | IF_all;
00325   for (Components::const_iterator ci = _components.begin();
00326        ci != _components.end();
00327        ++ci) {
00328     int this_result = (*ci)->contains_sphere(sphere);
00329     if ((this_result & IF_dont_understand) != 0) {
00330       result |= IF_dont_understand;
00331       break;
00332     }
00333     result &= this_result;
00334     if ((result & IF_possible) == 0) {
00335       // No point in looking further.
00336       break;
00337     }
00338   }
00339 
00340   return result;
00341 }
00342 
00343 ////////////////////////////////////////////////////////////////////
00344 //     Function: IntersectionBoundingVolume::contains_box
00345 //       Access: Protected, Virtual
00346 //  Description: Double-dispatch support: called by contains_other()
00347 //               when the type we're testing for intersection is known
00348 //               to be a box.
00349 ////////////////////////////////////////////////////////////////////
00350 int IntersectionBoundingVolume::
00351 contains_box(const BoundingBox *box) const {
00352   int result = IF_possible | IF_some | IF_all;
00353   for (Components::const_iterator ci = _components.begin();
00354        ci != _components.end();
00355        ++ci) {
00356     int this_result = (*ci)->contains_box(box);
00357     if ((this_result & IF_dont_understand) != 0) {
00358       result |= IF_dont_understand;
00359       break;
00360     }
00361     result &= this_result;
00362     if ((result & IF_possible) == 0) {
00363       // No point in looking further.
00364       break;
00365     }
00366   }
00367 
00368   return result;
00369 }
00370 
00371 ////////////////////////////////////////////////////////////////////
00372 //     Function: IntersectionBoundingVolume::contains_hexahedron
00373 //       Access: Protected, Virtual
00374 //  Description: Double-dispatch support: called by contains_other()
00375 //               when the type we're testing for intersection is known
00376 //               to be a hexahedron.
00377 ////////////////////////////////////////////////////////////////////
00378 int IntersectionBoundingVolume::
00379 contains_hexahedron(const BoundingHexahedron *hexahedron) const {
00380   int result = IF_possible | IF_some | IF_all;
00381   for (Components::const_iterator ci = _components.begin();
00382        ci != _components.end();
00383        ++ci) {
00384     int this_result = (*ci)->contains_hexahedron(hexahedron);
00385     if ((this_result & IF_dont_understand) != 0) {
00386       result |= IF_dont_understand;
00387       break;
00388     }
00389     result &= this_result;
00390     if ((result & IF_possible) == 0) {
00391       // No point in looking further.
00392       break;
00393     }
00394   }
00395 
00396   return result;
00397 }
00398 
00399 ////////////////////////////////////////////////////////////////////
00400 //     Function: IntersectionBoundingVolume::contains_line
00401 //       Access: Protected, Virtual
00402 //  Description: Double-dispatch support: called by contains_other()
00403 //               when the type we're testing for intersection is known
00404 //               to be a line.
00405 ////////////////////////////////////////////////////////////////////
00406 int IntersectionBoundingVolume::
00407 contains_line(const BoundingLine *line) const {
00408   int result = IF_possible | IF_some | IF_all;
00409   for (Components::const_iterator ci = _components.begin();
00410        ci != _components.end();
00411        ++ci) {
00412     int this_result = (*ci)->contains_line(line);
00413     if ((this_result & IF_dont_understand) != 0) {
00414       result |= IF_dont_understand;
00415       break;
00416     }
00417     result &= this_result;
00418     if ((result & IF_possible) == 0) {
00419       // No point in looking further.
00420       break;
00421     }
00422   }
00423 
00424   return result;
00425 }
00426 
00427 ////////////////////////////////////////////////////////////////////
00428 //     Function: IntersectionBoundingVolume::contains_plane
00429 //       Access: Protected, Virtual
00430 //  Description: Double-dispatch support: called by contains_other()
00431 //               when the type we're testing for intersection is known
00432 //               to be a plane.
00433 ////////////////////////////////////////////////////////////////////
00434 int IntersectionBoundingVolume::
00435 contains_plane(const BoundingPlane *plane) const {
00436   int result = IF_possible | IF_some | IF_all;
00437   for (Components::const_iterator ci = _components.begin();
00438        ci != _components.end();
00439        ++ci) {
00440     int this_result = (*ci)->contains_plane(plane);
00441     if ((this_result & IF_dont_understand) != 0) {
00442       result |= IF_dont_understand;
00443       break;
00444     }
00445     result &= this_result;
00446     if ((result & IF_possible) == 0) {
00447       // No point in looking further.
00448       break;
00449     }
00450   }
00451 
00452   return result;
00453 }
00454 
00455 ////////////////////////////////////////////////////////////////////
00456 //     Function: IntersectionBoundingVolume::contains_union
00457 //       Access: Protected, Virtual
00458 //  Description: Double-dispatch support: called by contains_other()
00459 //               when the type we're testing for intersection is known
00460 //               to be a union object.
00461 ////////////////////////////////////////////////////////////////////
00462 int IntersectionBoundingVolume::
00463 contains_union(const UnionBoundingVolume *unionv) const {
00464   int result = IF_possible | IF_some | IF_all;
00465   for (Components::const_iterator ci = _components.begin();
00466        ci != _components.end();
00467        ++ci) {
00468     int this_result = (*ci)->contains_union(unionv);
00469     if ((this_result & IF_dont_understand) != 0) {
00470       result |= IF_dont_understand;
00471       break;
00472     }
00473     result &= this_result;
00474     if ((result & IF_possible) == 0) {
00475       // No point in looking further.
00476       break;
00477     }
00478   }
00479 
00480   return result;
00481 }
00482 
00483 ////////////////////////////////////////////////////////////////////
00484 //     Function: IntersectionBoundingVolume::contains_intersection
00485 //       Access: Protected, Virtual
00486 //  Description: Double-dispatch support: called by contains_other()
00487 //               when the type we're testing for intersection is known
00488 //               to be an intersection object.
00489 ////////////////////////////////////////////////////////////////////
00490 int IntersectionBoundingVolume::
00491 contains_intersection(const IntersectionBoundingVolume *intersection) const {
00492   int result = IF_possible | IF_some | IF_all;
00493   for (Components::const_iterator ci = _components.begin();
00494        ci != _components.end();
00495        ++ci) {
00496     int this_result = (*ci)->contains_intersection(intersection);
00497     if ((this_result & IF_dont_understand) != 0) {
00498       result |= IF_dont_understand;
00499       break;
00500     }
00501     result &= this_result;
00502     if ((result & IF_possible) == 0) {
00503       // No point in looking further.
00504       break;
00505     }
00506   }
00507 
00508   return result;
00509 }
00510 
00511 ////////////////////////////////////////////////////////////////////
00512 //     Function: IntersectionBoundingVolume::contains_finite
00513 //       Access: Protected, Virtual
00514 //  Description: Generic handler for a FiniteBoundingVolume.
00515 ////////////////////////////////////////////////////////////////////
00516 int IntersectionBoundingVolume::
00517 contains_finite(const FiniteBoundingVolume *volume) const {
00518   int result = IF_possible | IF_some | IF_all;
00519   for (Components::const_iterator ci = _components.begin();
00520        ci != _components.end();
00521        ++ci) {
00522     int this_result = (*ci)->contains_finite(volume);
00523     if ((this_result & IF_dont_understand) != 0) {
00524       result |= IF_dont_understand;
00525       break;
00526     }
00527     result &= this_result;
00528     if ((result & IF_possible) == 0) {
00529       // No point in looking further.
00530       break;
00531     }
00532   }
00533 
00534   return result;
00535 }
00536 
00537 ////////////////////////////////////////////////////////////////////
00538 //     Function: IntersectionBoundingVolume::contains_geometric
00539 //       Access: Protected, Virtual
00540 //  Description: Generic handler for a GeometricBoundingVolume.
00541 ////////////////////////////////////////////////////////////////////
00542 int IntersectionBoundingVolume::
00543 contains_geometric(const GeometricBoundingVolume *volume) const {
00544   int result = IF_possible | IF_some | IF_all;
00545   for (Components::const_iterator ci = _components.begin();
00546        ci != _components.end();
00547        ++ci) {
00548     int this_result = (*ci)->contains_geometric(volume);
00549     if ((this_result & IF_dont_understand) != 0) {
00550       result |= IF_dont_understand;
00551       break;
00552     }
00553     result &= this_result;
00554     if ((result & IF_possible) == 0) {
00555       // No point in looking further.
00556       break;
00557     }
00558   }
00559 
00560   return result;
00561 }
00562 
00563 
00564 ////////////////////////////////////////////////////////////////////
00565 //     Function: IntersectionBoundingVolume::other_contains_intersection
00566 //       Access: Protected, Virtual
00567 //  Description: Generic reverse-direction comparison.  Called by
00568 //               BoundingVolumes that do not implement
00569 //               contains_intersection() explicitly.  This returns the test
00570 //               of whether the other volume contains this volume.
00571 ////////////////////////////////////////////////////////////////////
00572 int IntersectionBoundingVolume::
00573 other_contains_intersection(const BoundingVolume *volume) const {
00574   int result = IF_possible | IF_some | IF_all;
00575   for (Components::const_iterator ci = _components.begin();
00576        ci != _components.end();
00577        ++ci) {
00578     int this_result = volume->contains(*ci);
00579     if ((this_result & IF_dont_understand) != 0) {
00580       result |= IF_dont_understand;
00581       break;
00582     }
00583     result &= this_result;
00584     if ((result & IF_possible) == 0) {
00585       // No point in looking further.
00586       break;
00587     }
00588   }
00589 
00590   return result;
00591 }
00592 
 All Classes Functions Variables Enumerations