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  */
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  */
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  */
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  */
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 
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  */
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 }
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.