Panda3D
intersectionBoundingVolume.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 intersectionBoundingVolume.cxx
10  * @author drose
11  * @date 2012-02-08
12  */
13 
15 #include "unionBoundingVolume.h"
16 #include "config_mathutil.h"
17 #include "dcast.h"
18 
19 TypeHandle IntersectionBoundingVolume::_type_handle;
20 
21 /**
22  *
23  */
27  _components(copy._components)
28 {
29 }
30 
31 /**
32  *
33  */
34 BoundingVolume *IntersectionBoundingVolume::
35 make_copy() const {
36  return new IntersectionBoundingVolume(*this);
37 }
38 
39 /**
40  *
41  */
42 LPoint3 IntersectionBoundingVolume::
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 IntersectionBoundingVolume::
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 IntersectionBoundingVolume::
77 output(std::ostream &out) const {
78  if (is_empty()) {
79  out << "intersection, empty";
80  } else if (is_infinite()) {
81  out << "intersection, infinite";
82  } else {
83  out << "intersection [";
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 IntersectionBoundingVolume::
97 write(std::ostream &out, int indent_level) const {
98  if (is_empty()) {
99  indent(out, indent_level) << "intersection, empty\n";
100  } else if (is_infinite()) {
101  indent(out, indent_level) << "intersection, infinite\n";
102  } else {
103  indent(out, indent_level) << "intersection {\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_infinite;
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  CPT(GeometricBoundingVolume) gbv;
132 
133  if (component->is_exact_type(UnionBoundingVolume::get_class_type())) {
134  // Here's a special case. We'll construct a new union that includes only
135  // those components that have some intersection with our existing
136  // components. (No need to include the components that have no
137  // intersection.)
138  PT(UnionBoundingVolume) unionv = DCAST(UnionBoundingVolume, component->make_copy());
139  unionv->filter_intersection(this);
140 
141  // Save the modified union in a PT() so it won't be destructed.
142  gbv = unionv.p();
143 
144  if (unionv->get_num_components() == 1) {
145  // If there's only one component left, use just that one.
146  gbv = unionv->get_component(0);
147  }
148 
149  component = gbv;
150  }
151 
152  if (component->is_empty()) {
153  _flags = F_empty;
154  _components.clear();
155 
156  } else if (component->is_infinite() || is_empty()) {
157  // No-op.
158 
159  } else if (component->is_exact_type(IntersectionBoundingVolume::get_class_type())) {
160  // Another special case. Just more components.
161  const IntersectionBoundingVolume *other = DCAST(IntersectionBoundingVolume, component);
162  for (Components::const_iterator ci = other->_components.begin();
163  ci != other->_components.end();
164  ++ci) {
165  add_component(*ci);
166  }
167 
168  } else {
169  // The general case.
170  size_t i = 0;
171  while (i < _components.size()) {
172  const GeometricBoundingVolume *existing = _components[i];
173  ++i;
174 
175  int result = component->contains(existing);
176  if ((result & IF_all) != 0) {
177  // The existing component is entirely within this one; no need to do
178  // anything with it.
179  return;
180 
181  } else if (result == 0) {
182  // No intersection between these components; we're now empty.
183  _flags = F_empty;
184  _components.clear();
185  return;
186  }
187 
188  result = existing->contains(component);
189  if ((result & IF_all) != 0) {
190  // This new component is entirely within an existing component; no
191  // need to keep the existing one.
192  --i;
193  _components.erase(_components.begin() + i);
194 
195  } else if (result == 0) {
196  // No intersection between these components; we're now empty.
197  _flags = F_empty;
198  _components.clear();
199  return;
200  }
201  }
202 
203  _flags &= ~F_infinite;
204  _components.push_back(component);
205  }
206 }
207 
208 /**
209  *
210  */
211 bool IntersectionBoundingVolume::
212 extend_other(BoundingVolume *other) const {
213  return other->extend_by_intersection(this);
214 }
215 
216 /**
217  *
218  */
219 bool IntersectionBoundingVolume::
220 around_other(BoundingVolume *other,
221  const BoundingVolume **first,
222  const BoundingVolume **last) const {
223  return other->around_intersections(first, last);
224 }
225 
226 /**
227  *
228  */
229 int IntersectionBoundingVolume::
230 contains_other(const BoundingVolume *other) const {
231  return other->contains_intersection(this);
232 }
233 
234 /**
235  *
236  */
237 int IntersectionBoundingVolume::
238 contains_point(const LPoint3 &point) const {
239  nassertr(!point.is_nan(), IF_no_intersection);
240 
241  int result = IF_possible | IF_some | IF_all;
242  for (Components::const_iterator ci = _components.begin();
243  ci != _components.end();
244  ++ci) {
245  int this_result = (*ci)->contains(point);
246  if ((this_result & IF_dont_understand) != 0) {
247  result |= IF_dont_understand;
248  break;
249  }
250  result &= this_result;
251  if ((result & IF_possible) == 0) {
252  // No point in looking further.
253  break;
254  }
255  }
256 
257  return result;
258 }
259 
260 /**
261  *
262  */
263 int IntersectionBoundingVolume::
264 contains_lineseg(const LPoint3 &a, const LPoint3 &b) const {
265  nassertr(!a.is_nan() && !b.is_nan(), IF_no_intersection);
266 
267  int result = IF_possible | IF_some | IF_all;
268  for (Components::const_iterator ci = _components.begin();
269  ci != _components.end();
270  ++ci) {
271  int this_result = (*ci)->contains(a, b);
272  if ((this_result & IF_dont_understand) != 0) {
273  result |= IF_dont_understand;
274  break;
275  }
276  result &= this_result;
277  if ((result & IF_possible) == 0) {
278  // No point in looking further.
279  break;
280  }
281  }
282 
283  return result;
284 }
285 
286 /**
287  * Double-dispatch support: called by contains_other() when the type we're
288  * testing for intersection is known to be a sphere.
289  */
290 int IntersectionBoundingVolume::
291 contains_sphere(const BoundingSphere *sphere) const {
292  int result = IF_possible | IF_some | IF_all;
293  for (Components::const_iterator ci = _components.begin();
294  ci != _components.end();
295  ++ci) {
296  int this_result = (*ci)->contains_sphere(sphere);
297  if ((this_result & IF_dont_understand) != 0) {
298  result |= IF_dont_understand;
299  break;
300  }
301  result &= this_result;
302  if ((result & IF_possible) == 0) {
303  // No point in looking further.
304  break;
305  }
306  }
307 
308  return result;
309 }
310 
311 /**
312  * Double-dispatch support: called by contains_other() when the type we're
313  * testing for intersection is known to be a box.
314  */
315 int IntersectionBoundingVolume::
316 contains_box(const BoundingBox *box) const {
317  int result = IF_possible | IF_some | IF_all;
318  for (Components::const_iterator ci = _components.begin();
319  ci != _components.end();
320  ++ci) {
321  int this_result = (*ci)->contains_box(box);
322  if ((this_result & IF_dont_understand) != 0) {
323  result |= IF_dont_understand;
324  break;
325  }
326  result &= this_result;
327  if ((result & IF_possible) == 0) {
328  // No point in looking further.
329  break;
330  }
331  }
332 
333  return result;
334 }
335 
336 /**
337  * Double-dispatch support: called by contains_other() when the type we're
338  * testing for intersection is known to be a hexahedron.
339  */
340 int IntersectionBoundingVolume::
341 contains_hexahedron(const BoundingHexahedron *hexahedron) const {
342  int result = IF_possible | IF_some | IF_all;
343  for (Components::const_iterator ci = _components.begin();
344  ci != _components.end();
345  ++ci) {
346  int this_result = (*ci)->contains_hexahedron(hexahedron);
347  if ((this_result & IF_dont_understand) != 0) {
348  result |= IF_dont_understand;
349  break;
350  }
351  result &= this_result;
352  if ((result & IF_possible) == 0) {
353  // No point in looking further.
354  break;
355  }
356  }
357 
358  return result;
359 }
360 
361 /**
362  * Double-dispatch support: called by contains_other() when the type we're
363  * testing for intersection is known to be a line.
364  */
365 int IntersectionBoundingVolume::
366 contains_line(const BoundingLine *line) const {
367  int result = IF_possible | IF_some | IF_all;
368  for (Components::const_iterator ci = _components.begin();
369  ci != _components.end();
370  ++ci) {
371  int this_result = (*ci)->contains_line(line);
372  if ((this_result & IF_dont_understand) != 0) {
373  result |= IF_dont_understand;
374  break;
375  }
376  result &= this_result;
377  if ((result & IF_possible) == 0) {
378  // No point in looking further.
379  break;
380  }
381  }
382 
383  return result;
384 }
385 
386 /**
387  * Double-dispatch support: called by contains_other() when the type we're
388  * testing for intersection is known to be a plane.
389  */
390 int IntersectionBoundingVolume::
391 contains_plane(const BoundingPlane *plane) const {
392  int result = IF_possible | IF_some | IF_all;
393  for (Components::const_iterator ci = _components.begin();
394  ci != _components.end();
395  ++ci) {
396  int this_result = (*ci)->contains_plane(plane);
397  if ((this_result & IF_dont_understand) != 0) {
398  result |= IF_dont_understand;
399  break;
400  }
401  result &= this_result;
402  if ((result & IF_possible) == 0) {
403  // No point in looking further.
404  break;
405  }
406  }
407 
408  return result;
409 }
410 
411 /**
412  * Double-dispatch support: called by contains_other() when the type we're
413  * testing for intersection is known to be a union object.
414  */
415 int IntersectionBoundingVolume::
416 contains_union(const UnionBoundingVolume *unionv) const {
417  int result = IF_possible | IF_some | IF_all;
418  for (Components::const_iterator ci = _components.begin();
419  ci != _components.end();
420  ++ci) {
421  int this_result = (*ci)->contains_union(unionv);
422  if ((this_result & IF_dont_understand) != 0) {
423  result |= IF_dont_understand;
424  break;
425  }
426  result &= this_result;
427  if ((result & IF_possible) == 0) {
428  // No point in looking further.
429  break;
430  }
431  }
432 
433  return result;
434 }
435 
436 /**
437  * Double-dispatch support: called by contains_other() when the type we're
438  * testing for intersection is known to be an intersection object.
439  */
440 int IntersectionBoundingVolume::
441 contains_intersection(const IntersectionBoundingVolume *intersection) const {
442  int result = IF_possible | IF_some | IF_all;
443  for (Components::const_iterator ci = _components.begin();
444  ci != _components.end();
445  ++ci) {
446  int this_result = (*ci)->contains_intersection(intersection);
447  if ((this_result & IF_dont_understand) != 0) {
448  result |= IF_dont_understand;
449  break;
450  }
451  result &= this_result;
452  if ((result & IF_possible) == 0) {
453  // No point in looking further.
454  break;
455  }
456  }
457 
458  return result;
459 }
460 
461 /**
462  * Generic handler for a FiniteBoundingVolume.
463  */
464 int IntersectionBoundingVolume::
465 contains_finite(const FiniteBoundingVolume *volume) const {
466  int result = IF_possible | IF_some | IF_all;
467  for (Components::const_iterator ci = _components.begin();
468  ci != _components.end();
469  ++ci) {
470  int this_result = (*ci)->contains_finite(volume);
471  if ((this_result & IF_dont_understand) != 0) {
472  result |= IF_dont_understand;
473  break;
474  }
475  result &= this_result;
476  if ((result & IF_possible) == 0) {
477  // No point in looking further.
478  break;
479  }
480  }
481 
482  return result;
483 }
484 
485 /**
486  * Generic handler for a GeometricBoundingVolume.
487  */
488 int IntersectionBoundingVolume::
489 contains_geometric(const GeometricBoundingVolume *volume) const {
490  int result = IF_possible | IF_some | IF_all;
491  for (Components::const_iterator ci = _components.begin();
492  ci != _components.end();
493  ++ci) {
494  int this_result = (*ci)->contains_geometric(volume);
495  if ((this_result & IF_dont_understand) != 0) {
496  result |= IF_dont_understand;
497  break;
498  }
499  result &= this_result;
500  if ((result & IF_possible) == 0) {
501  // No point in looking further.
502  break;
503  }
504  }
505 
506  return result;
507 }
508 
509 
510 /**
511  * Generic reverse-direction comparison. Called by BoundingVolumes that do
512  * not implement contains_intersection() explicitly. This returns the test of
513  * whether the other volume contains this volume.
514  */
515 int IntersectionBoundingVolume::
516 other_contains_intersection(const BoundingVolume *volume) const {
517  int result = IF_possible | IF_some | IF_all;
518  for (Components::const_iterator ci = _components.begin();
519  ci != _components.end();
520  ++ci) {
521  int this_result = volume->contains(*ci);
522  if ((this_result & IF_dont_understand) != 0) {
523  result |= IF_dont_understand;
524  break;
525  }
526  result &= this_result;
527  if ((result & IF_possible) == 0) {
528  // No point in looking further.
529  break;
530  }
531  }
532 
533  return result;
534 }
indent
std::ostream & indent(std::ostream &out, int indent_level)
A handy function for doing text formatting.
Definition: indent.cxx:20
BoundingSphere
This defines a bounding sphere, consisting of a center and a radius.
Definition: boundingSphere.h:25
FiniteBoundingVolume
A special kind of GeometricBoundingVolume that is known to be finite.
Definition: finiteBoundingVolume.h:27
dcast.h
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
BoundingBox
An axis-aligned bounding box; that is, a minimum and maximum coordinate triple.
Definition: boundingBox.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
IntersectionBoundingVolume::add_component
void add_component(const GeometricBoundingVolume *component)
Adds a new component to the volume.
Definition: intersectionBoundingVolume.cxx:130
TypeHandle
TypeHandle is the identifier used to differentiate C++ class types.
Definition: typeHandle.h:81
BoundingVolume::is_infinite
bool is_infinite() const
The other side of the empty coin is an infinite volume.
Definition: boundingVolume.I:44
UnionBoundingVolume
This special bounding volume is the union of all of its constituent bounding volumes.
Definition: unionBoundingVolume.h:29
GeometricBoundingVolume
This is another abstract class, for a general class of bounding volumes that actually enclose points ...
Definition: geometricBoundingVolume.h: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
BoundingLine
This funny bounding volume is an infinite line with no thickness and extending to infinity in both di...
Definition: boundingLine.h:29
IntersectionBoundingVolume::clear_components
void clear_components()
Removes all components from the volume.
Definition: intersectionBoundingVolume.cxx:117
config_mathutil.h
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
intersectionBoundingVolume.h
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
BoundingHexahedron
This defines a bounding convex hexahedron.
Definition: boundingHexahedron.h:32
BoundingVolume::is_empty
bool is_empty() const
Any kind of volume might be empty.
Definition: boundingVolume.I:29
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
TypedObject::is_exact_type
bool is_exact_type(TypeHandle handle) const
Returns true if the current object is the indicated type exactly.
Definition: typedObject.I:38
IntersectionBoundingVolume::IntersectionBoundingVolume
IntersectionBoundingVolume()
Constructs an empty intersection.
Definition: intersectionBoundingVolume.I:18
IntersectionBoundingVolume
This special bounding volume is the intersection of all of its constituent bounding volumes.
Definition: intersectionBoundingVolume.h:29
BoundingPlane
This funny bounding volume is an infinite plane that divides space into two regions: the part behind ...
Definition: boundingPlane.h:28
unionBoundingVolume.h
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.