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