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
19 TypeHandle UnionBoundingVolume::_type_handle;
20
21 /**
22 *
23 */
24 UnionBoundingVolume::
25 UnionBoundingVolume(const UnionBoundingVolume &copy) :
26 GeometricBoundingVolume(copy),
27 _components(copy._components)
28 {
29 }
30
31 /**
32 *
33 */
34 BoundingVolume *UnionBoundingVolume::
35 make_copy() const {
36 return new UnionBoundingVolume(*this);
37 }
38
39 /**
40 *
41 */
42 LPoint3 UnionBoundingVolume::
43 get_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 */
60 void UnionBoundingVolume::
61 xform(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 */
76 void UnionBoundingVolume::
77 output(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 */
96 void UnionBoundingVolume::
97 write(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 */
116 void UnionBoundingVolume::
117 clear_components() {
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 */
129 void UnionBoundingVolume::
130 add_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 */
169 void UnionBoundingVolume::
170 filter_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 */
192 bool UnionBoundingVolume::
193 extend_other(BoundingVolume *other) const {
194 return other->extend_by_union(this);
195 }
196
197 /**
198 *
199 */
200 bool UnionBoundingVolume::
201 around_other(BoundingVolume *other,
202 const BoundingVolume **first,
203 const BoundingVolume **last) const {
204 return other->around_unions(first, last);
205 }
206
207 /**
208 *
209 */
210 int UnionBoundingVolume::
211 contains_other(const BoundingVolume *other) const {
212 return other->contains_union(this);
213 }
214
215 /**
216 *
217 */
218 bool UnionBoundingVolume::
219 extend_by_geometric(const GeometricBoundingVolume *volume) {
220 add_component(volume);
221 return true;
222 }
223
224 /**
225 *
226 */
227 bool UnionBoundingVolume::
228 around_geometric(const BoundingVolume **first,
229 const BoundingVolume **last) {
230 nassertr(first != last, false);
231
232 clear_components();
233
234 const BoundingVolume **p = first;
235 while (p != last) {
236 nassertr(!(*p)->is_infinite(), false);
237 if (!(*p)->is_empty()) {
238 const GeometricBoundingVolume *volume = (*p)->as_geometric_bounding_volume();
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 */
255 int UnionBoundingVolume::
256 contains_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 */
276 int UnionBoundingVolume::
277 contains_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 */
298 int UnionBoundingVolume::
299 contains_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 */
318 int UnionBoundingVolume::
319 contains_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 */
338 int UnionBoundingVolume::
339 contains_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 */
358 int UnionBoundingVolume::
359 contains_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 */
378 int UnionBoundingVolume::
379 contains_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 */
398 int UnionBoundingVolume::
399 contains_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 */
418 int UnionBoundingVolume::
419 contains_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 */
437 int UnionBoundingVolume::
438 contains_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 */
456 int UnionBoundingVolume::
457 contains_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 */
477 int UnionBoundingVolume::
478 other_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 }
BoundingBox
An axis-aligned bounding box; that is, a minimum and maximum coordinate triple.
Definition: boundingBox.h:29
BoundingHexahedron
This defines a bounding convex hexahedron.
Definition: boundingHexahedron.h:32
BoundingLine
This funny bounding volume is an infinite line with no thickness and extending to infinity in both di...
Definition: boundingLine.h:29
BoundingPlane
This funny bounding volume is an infinite plane that divides space into two regions: the part behind ...
Definition: boundingPlane.h:28
BoundingSphere
This defines a bounding sphere, consisting of a center and a radius.
Definition: boundingSphere.h:25
BoundingVolume
This is an abstract class for any volume in any sense which can be said to define the locality of ref...
Definition: boundingVolume.h:41
BoundingVolume::set_infinite
void set_infinite()
Marks the volume as infinite, even if it is normally finite.
Definition: boundingVolume.I:53
BoundingVolume::is_empty
bool is_empty() const
Any kind of volume might be empty.
Definition: boundingVolume.I:29
BoundingVolume::contains
int contains(const BoundingVolume *vol) const
Returns the appropriate set of IntersectionFlags to indicate the amount of intersection with the indi...
Definition: boundingVolume.I:80
BoundingVolume::is_infinite
bool is_infinite() const
The other side of the empty coin is an infinite volume.
Definition: boundingVolume.I:44
FiniteBoundingVolume
A special kind of GeometricBoundingVolume that is known to be finite.
Definition: finiteBoundingVolume.h:27
GeometricBoundingVolume
This is another abstract class, for a general class of bounding volumes that actually enclose points ...
Definition: geometricBoundingVolume.h:29
GeometricBoundingVolume::contains
int contains(const GeometricBoundingVolume *vol) const
Returns the appropriate set of IntersectionFlags to indicate the amount of intersection with the indi...
Definition: geometricBoundingVolume.I:68
GeometricBoundingVolume::as_geometric_bounding_volume
virtual GeometricBoundingVolume * as_geometric_bounding_volume() final
Virtual downcast method.
Definition: geometricBoundingVolume.cxx:24
IntersectionBoundingVolume
This special bounding volume is the intersection of all of its constituent bounding volumes.
Definition: intersectionBoundingVolume.h:29
TypeHandle
TypeHandle is the identifier used to differentiate C++ class types.
Definition: typeHandle.h:81
UnionBoundingVolume
This special bounding volume is the union of all of its constituent bounding volumes.
Definition: unionBoundingVolume.h:29
UnionBoundingVolume::clear_components
void clear_components()
Removes all components from the volume.
Definition: unionBoundingVolume.cxx:117
UnionBoundingVolume::filter_intersection
void filter_intersection(const BoundingVolume *volume)
Removes from the union any components that have no intersection with the indicated volume.
Definition: unionBoundingVolume.cxx:170
UnionBoundingVolume::add_component
void add_component(const GeometricBoundingVolume *component)
Adds a new component to the volume.
Definition: unionBoundingVolume.cxx:130
UnionBoundingVolume::UnionBoundingVolume
UnionBoundingVolume()
Constructs an empty union.
Definition: unionBoundingVolume.I:18
config_mathutil.h
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
dcast.h
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
indent
std::ostream & indent(std::ostream &out, int indent_level)
A handy function for doing text formatting.
Definition: indent.cxx:20
indent.h
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
unionBoundingVolume.h
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.