Panda3D
unionBoundingVolume.cxx
Go to the documentation of this file.
1/**
2 * PANDA 3D SOFTWARE
3 * Copyright (c) Carnegie Mellon University. All rights reserved.
4 *
5 * All use of this software is subject to the terms of the revised BSD
6 * license. You should have received a copy of this license along
7 * with this source code in a file named "LICENSE."
8 *
9 * @file unionBoundingVolume.cxx
10 * @author drose
11 * @date 2012-02-08
12 */
13
14#include "unionBoundingVolume.h"
15#include "config_mathutil.h"
16#include "dcast.h"
17#include "indent.h"
18
19TypeHandle UnionBoundingVolume::_type_handle;
20
21/**
22 *
23 */
27 _components(copy._components)
28{
29}
30
31/**
32 *
33 */
34BoundingVolume *UnionBoundingVolume::
35make_copy() const {
36 return new UnionBoundingVolume(*this);
37}
38
39/**
40 *
41 */
42LPoint3 UnionBoundingVolume::
43get_approx_center() const {
44 nassertr(!is_empty(), LPoint3::zero());
45 nassertr(!is_infinite(), LPoint3::zero());
46
47 LPoint3 center = LPoint3::zero();
48 for (Components::const_iterator ci = _components.begin();
49 ci != _components.end();
50 ++ci) {
51 center += (*ci)->get_approx_center();
52 }
53
54 return center / (PN_stdfloat)_components.size();
55}
56
57/**
58 *
59 */
60void UnionBoundingVolume::
61xform(const LMatrix4 &mat) {
62 nassertv(!mat.is_nan());
63
64 for (Components::iterator ci = _components.begin();
65 ci != _components.end();
66 ++ci) {
67 PT(GeometricBoundingVolume) copy = DCAST(GeometricBoundingVolume, (*ci)->make_copy());
68 copy->xform(mat);
69 (*ci) = copy;
70 }
71}
72
73/**
74 *
75 */
76void UnionBoundingVolume::
77output(std::ostream &out) const {
78 if (is_empty()) {
79 out << "union, empty";
80 } else if (is_infinite()) {
81 out << "union, infinite";
82 } else {
83 out << "union [";
84 for (Components::const_iterator ci = _components.begin();
85 ci != _components.end();
86 ++ci) {
87 out << " " << *(*ci);
88 }
89 out << " ]";
90 }
91}
92
93/**
94 *
95 */
96void UnionBoundingVolume::
97write(std::ostream &out, int indent_level) const {
98 if (is_empty()) {
99 indent(out, indent_level) << "union, empty\n";
100 } else if (is_infinite()) {
101 indent(out, indent_level) << "union, infinite\n";
102 } else {
103 indent(out, indent_level) << "union {\n";
104 for (Components::const_iterator ci = _components.begin();
105 ci != _components.end();
106 ++ci) {
107 (*ci)->write(out, indent_level + 2);
108 }
109 indent(out, indent_level) << "}\n";
110 }
111}
112
113/**
114 * Removes all components from the volume.
115 */
118 _components.clear();
119 _flags = F_empty;
120}
121
122/**
123 * Adds a new component to the volume. This does not necessarily increase the
124 * total number of components by one, and you may or may not be able to find
125 * this component in the volume by a subsequent call to get_component();
126 * certain optimizations may prevent the component from being added, or have
127 * other unexpected effects on the total set of components.
128 */
130add_component(const GeometricBoundingVolume *component) {
131 if (component->is_infinite()) {
132 _flags = F_infinite;
133 _components.clear();
134
135 } else if (component->is_empty() || is_infinite()) {
136 // No-op.
137
138 } else {
139 size_t i = 0;
140 while (i < _components.size()) {
141 const GeometricBoundingVolume *existing = _components[i];
142 ++i;
143
144 int result = existing->contains(component);
145 if ((result & IF_all) != 0) {
146 // This new component is entirely within an existing component; no
147 // need to do anything with it.
148 return;
149 }
150
151 result = component->contains(existing);
152 if ((result & IF_all) != 0) {
153 // The existing component is entirely within this one; no need to keep
154 // the existing one.
155 --i;
156 _components.erase(_components.begin() + i);
157 }
158 }
159
160 _flags &= ~F_empty;
161 _components.push_back(component);
162 }
163}
164
165/**
166 * Removes from the union any components that have no intersection with the
167 * indicated volume.
168 */
170filter_intersection(const BoundingVolume *volume) {
171 size_t i = 0;
172 while (i < _components.size()) {
173 const GeometricBoundingVolume *existing = _components[i];
174 ++i;
175
176 int result = volume->contains(existing);
177 if ((result & IF_possible) == 0) {
178 // There is no intersection. Remove this component.
179 --i;
180 _components.erase(_components.begin() + i);
181 }
182 }
183
184 if (_components.empty()) {
185 _flags |= F_empty;
186 }
187}
188
189/**
190 *
191 */
192bool UnionBoundingVolume::
193extend_other(BoundingVolume *other) const {
194 return other->extend_by_union(this);
195}
196
197/**
198 *
199 */
200bool UnionBoundingVolume::
201around_other(BoundingVolume *other,
202 const BoundingVolume **first,
203 const BoundingVolume **last) const {
204 return other->around_unions(first, last);
205}
206
207/**
208 *
209 */
210int UnionBoundingVolume::
211contains_other(const BoundingVolume *other) const {
212 return other->contains_union(this);
213}
214
215/**
216 *
217 */
218bool UnionBoundingVolume::
219extend_by_geometric(const GeometricBoundingVolume *volume) {
220 add_component(volume);
221 return true;
222}
223
224/**
225 *
226 */
227bool UnionBoundingVolume::
228around_geometric(const BoundingVolume **first,
229 const BoundingVolume **last) {
230 nassertr(first != last, false);
231
233
234 const BoundingVolume **p = first;
235 while (p != last) {
236 nassertr(!(*p)->is_infinite(), false);
237 if (!(*p)->is_empty()) {
239 if (volume != nullptr) {
240 add_component(volume);
241 } else {
242 set_infinite();
243 _components.clear();
244 return false;
245 }
246 }
247 }
248
249 return true;
250}
251
252/**
253 *
254 */
255int UnionBoundingVolume::
256contains_point(const LPoint3 &point) const {
257 nassertr(!point.is_nan(), IF_no_intersection);
258
259 int result = 0;
260 for (Components::const_iterator ci = _components.begin();
261 ci != _components.end();
262 ++ci) {
263 result |= (*ci)->contains(point);
264 if ((result & (IF_all | IF_dont_understand)) != 0) {
265 // No point in looking further.
266 break;
267 }
268 }
269
270 return result;
271}
272
273/**
274 *
275 */
276int UnionBoundingVolume::
277contains_lineseg(const LPoint3 &a, const LPoint3 &b) const {
278 nassertr(!a.is_nan() && !b.is_nan(), IF_no_intersection);
279
280 int result = 0;
281 for (Components::const_iterator ci = _components.begin();
282 ci != _components.end();
283 ++ci) {
284 result |= (*ci)->contains(a, b);
285 if ((result & (IF_all | IF_dont_understand)) != 0) {
286 // No point in looking further.
287 break;
288 }
289 }
290
291 return result;
292}
293
294/**
295 * Double-dispatch support: called by contains_other() when the type we're
296 * testing for intersection is known to be a sphere.
297 */
298int UnionBoundingVolume::
299contains_sphere(const BoundingSphere *sphere) const {
300 int result = 0;
301 for (Components::const_iterator ci = _components.begin();
302 ci != _components.end();
303 ++ci) {
304 result |= (*ci)->contains_sphere(sphere);
305 if ((result & (IF_all | IF_dont_understand)) != 0) {
306 // No point in looking further.
307 break;
308 }
309 }
310
311 return result;
312}
313
314/**
315 * Double-dispatch support: called by contains_other() when the type we're
316 * testing for intersection is known to be a box.
317 */
318int UnionBoundingVolume::
319contains_box(const BoundingBox *box) const {
320 int result = 0;
321 for (Components::const_iterator ci = _components.begin();
322 ci != _components.end();
323 ++ci) {
324 result |= (*ci)->contains_box(box);
325 if ((result & (IF_all | IF_dont_understand)) != 0) {
326 // No point in looking further.
327 break;
328 }
329 }
330
331 return result;
332}
333
334/**
335 * Double-dispatch support: called by contains_other() when the type we're
336 * testing for intersection is known to be a hexahedron.
337 */
338int UnionBoundingVolume::
339contains_hexahedron(const BoundingHexahedron *hexahedron) const {
340 int result = 0;
341 for (Components::const_iterator ci = _components.begin();
342 ci != _components.end();
343 ++ci) {
344 result |= (*ci)->contains_hexahedron(hexahedron);
345 if ((result & (IF_all | IF_dont_understand)) != 0) {
346 // No point in looking further.
347 break;
348 }
349 }
350
351 return result;
352}
353
354/**
355 * Double-dispatch support: called by contains_other() when the type we're
356 * testing for intersection is known to be a line.
357 */
358int UnionBoundingVolume::
359contains_line(const BoundingLine *line) const {
360 int result = 0;
361 for (Components::const_iterator ci = _components.begin();
362 ci != _components.end();
363 ++ci) {
364 result |= (*ci)->contains_line(line);
365 if ((result & (IF_all | IF_dont_understand)) != 0) {
366 // No point in looking further.
367 break;
368 }
369 }
370
371 return result;
372}
373
374/**
375 * Double-dispatch support: called by contains_other() when the type we're
376 * testing for intersection is known to be a plane.
377 */
378int UnionBoundingVolume::
379contains_plane(const BoundingPlane *plane) const {
380 int result = 0;
381 for (Components::const_iterator ci = _components.begin();
382 ci != _components.end();
383 ++ci) {
384 result |= (*ci)->contains_plane(plane);
385 if ((result & (IF_all | IF_dont_understand)) != 0) {
386 // No point in looking further.
387 break;
388 }
389 }
390
391 return result;
392}
393
394/**
395 * Double-dispatch support: called by contains_other() when the type we're
396 * testing for intersection is known to be a union object.
397 */
398int UnionBoundingVolume::
399contains_union(const UnionBoundingVolume *unionv) const {
400 int result = 0;
401 for (Components::const_iterator ci = _components.begin();
402 ci != _components.end();
403 ++ci) {
404 result |= (*ci)->contains_union(unionv);
405 if ((result & (IF_all | IF_dont_understand)) != 0) {
406 // No point in looking further.
407 break;
408 }
409 }
410
411 return result;
412}
413
414/**
415 * Double-dispatch support: called by contains_other() when the type we're
416 * testing for intersection is known to be an intersection object.
417 */
418int UnionBoundingVolume::
419contains_intersection(const IntersectionBoundingVolume *intersection) const {
420 int result = 0;
421 for (Components::const_iterator ci = _components.begin();
422 ci != _components.end();
423 ++ci) {
424 result |= (*ci)->contains_intersection(intersection);
425 if ((result & (IF_all | IF_dont_understand)) != 0) {
426 // No point in looking further.
427 break;
428 }
429 }
430
431 return result;
432}
433
434/**
435 * Generic handler for a FiniteBoundingVolume.
436 */
437int UnionBoundingVolume::
438contains_finite(const FiniteBoundingVolume *volume) const {
439 int result = 0;
440 for (Components::const_iterator ci = _components.begin();
441 ci != _components.end();
442 ++ci) {
443 result |= (*ci)->contains_finite(volume);
444 if ((result & (IF_all | IF_dont_understand)) != 0) {
445 // No point in looking further.
446 break;
447 }
448 }
449
450 return result;
451}
452
453/**
454 * Generic handler for a GeometricBoundingVolume.
455 */
456int UnionBoundingVolume::
457contains_geometric(const GeometricBoundingVolume *volume) const {
458 int result = 0;
459 for (Components::const_iterator ci = _components.begin();
460 ci != _components.end();
461 ++ci) {
462 result |= (*ci)->contains_geometric(volume);
463 if ((result & (IF_all | IF_dont_understand)) != 0) {
464 // No point in looking further.
465 break;
466 }
467 }
468
469 return result;
470}
471
472/**
473 * Generic reverse-direction comparison. Called by BoundingVolumes that do
474 * not implement contains_union() explicitly. This returns the test of
475 * whether the other volume contains this volume.
476 */
477int UnionBoundingVolume::
478other_contains_union(const BoundingVolume *volume) const {
479 int all_result = IF_possible | IF_some | IF_all;
480 int some_result = 0;
481 for (Components::const_iterator ci = _components.begin();
482 ci != _components.end();
483 ++ci) {
484 int this_result = volume->contains(*ci);
485 if ((this_result & IF_dont_understand) != 0) {
486 some_result |= IF_dont_understand;
487 break;
488 }
489 all_result &= this_result;
490 some_result |= this_result;
491 }
492
493 some_result &= ~IF_all;
494 return some_result | all_result;
495}
An axis-aligned bounding box; that is, a minimum and maximum coordinate triple.
Definition: boundingBox.h:29
This defines a bounding convex hexahedron.
This funny bounding volume is an infinite line with no thickness and extending to infinity in both di...
Definition: boundingLine.h:29
This funny bounding volume is an infinite plane that divides space into two regions: the part behind ...
Definition: boundingPlane.h:28
This defines a bounding sphere, consisting of a center and a radius.
This is an abstract class for any volume in any sense which can be said to define the locality of ref...
void set_infinite()
Marks the volume as infinite, even if it is normally finite.
bool is_empty() const
Any kind of volume might be empty.
int contains(const BoundingVolume *vol) const
Returns the appropriate set of IntersectionFlags to indicate the amount of intersection with the indi...
bool is_infinite() const
The other side of the empty coin is an infinite volume.
A special kind of GeometricBoundingVolume that is known to be finite.
This is another abstract class, for a general class of bounding volumes that actually enclose points ...
int contains(const GeometricBoundingVolume *vol) const
Returns the appropriate set of IntersectionFlags to indicate the amount of intersection with the indi...
virtual GeometricBoundingVolume * as_geometric_bounding_volume() final
Virtual downcast method.
This special bounding volume is the intersection of all of its constituent bounding volumes.
TypeHandle is the identifier used to differentiate C++ class types.
Definition: typeHandle.h:81
This special bounding volume is the union of all of its constituent bounding volumes.
void clear_components()
Removes all components from the volume.
void filter_intersection(const BoundingVolume *volume)
Removes from the union any components that have no intersection with the indicated volume.
void add_component(const GeometricBoundingVolume *component)
Adds a new component to the volume.
UnionBoundingVolume()
Constructs an empty union.
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
std::ostream & indent(std::ostream &out, int indent_level)
A handy function for doing text formatting.
Definition: indent.cxx:20
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.