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