Panda3D
|
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 ©) : 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