Panda3D
intersectionBoundingVolume.cxx
1 // Filename: intersectionBoundingVolume.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 "intersectionBoundingVolume.h"
16 #include "unionBoundingVolume.h"
17 #include "config_mathutil.h"
18 #include "dcast.h"
19 
20 TypeHandle IntersectionBoundingVolume::_type_handle;
21 
22 ////////////////////////////////////////////////////////////////////
23 // Function: IntersectionBoundingVolume::Copy Constructor
24 // Access: Public
25 // Description:
26 ////////////////////////////////////////////////////////////////////
30  _components(copy._components)
31 {
32 }
33 
34 ////////////////////////////////////////////////////////////////////
35 // Function: IntersectionBoundingVolume::make_copy
36 // Access: Public, Virtual
37 // Description:
38 ////////////////////////////////////////////////////////////////////
39 BoundingVolume *IntersectionBoundingVolume::
40 make_copy() const {
41  return new IntersectionBoundingVolume(*this);
42 }
43 
44 ////////////////////////////////////////////////////////////////////
45 // Function: IntersectionBoundingVolume::get_approx_center
46 // Access: Public, Virtual
47 // Description:
48 ////////////////////////////////////////////////////////////////////
49 LPoint3 IntersectionBoundingVolume::
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: IntersectionBoundingVolume::xform
66 // Access: Public, Virtual
67 // Description:
68 ////////////////////////////////////////////////////////////////////
69 void IntersectionBoundingVolume::
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: IntersectionBoundingVolume::output
84 // Access: Public, Virtual
85 // Description:
86 ////////////////////////////////////////////////////////////////////
87 void IntersectionBoundingVolume::
88 output(ostream &out) const {
89  if (is_empty()) {
90  out << "intersection, empty";
91  } else if (is_infinite()) {
92  out << "intersection, infinite";
93  } else {
94  out << "intersection [";
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: IntersectionBoundingVolume::write
106 // Access: Public, Virtual
107 // Description:
108 ////////////////////////////////////////////////////////////////////
109 void IntersectionBoundingVolume::
110 write(ostream &out, int indent_level) const {
111  if (is_empty()) {
112  indent(out, indent_level) << "intersection, empty\n";
113  } else if (is_infinite()) {
114  indent(out, indent_level) << "intersection, infinite\n";
115  } else {
116  indent(out, indent_level) << "intersection {\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: IntersectionBoundingVolume::clear_components
128 // Access: Published
129 // Description: Removes all components from the volume.
130 ////////////////////////////////////////////////////////////////////
133  _components.clear();
134  _flags = F_infinite;
135 }
136 
137 ////////////////////////////////////////////////////////////////////
138 // Function: IntersectionBoundingVolume::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  CPT(GeometricBoundingVolume) gbv;
151 
152  if (component->is_exact_type(UnionBoundingVolume::get_class_type())) {
153  // Here's a special case. We'll construct a new union that
154  // includes only those components that have some intersection with
155  // our existing components. (No need to include the components
156  // that have no intersection.)
157  PT(UnionBoundingVolume) unionv = DCAST(UnionBoundingVolume, component->make_copy());
158  unionv->filter_intersection(this);
159 
160  // Save the modified union in a PT() so it won't be destructed.
161  gbv = unionv.p();
162 
163  if (unionv->get_num_components() == 1) {
164  // If there's only one component left, use just that one.
165  gbv = unionv->get_component(0);
166  }
167 
168  component = gbv;
169  }
170 
171  if (component->is_empty()) {
172  _flags = F_empty;
173  _components.clear();
174 
175  } else if (component->is_infinite() || is_empty()) {
176  // No-op.
177 
178  } else if (component->is_exact_type(IntersectionBoundingVolume::get_class_type())) {
179  // Another special case. Just more components.
180  const IntersectionBoundingVolume *other = DCAST(IntersectionBoundingVolume, component);
181  for (Components::const_iterator ci = other->_components.begin();
182  ci != other->_components.end();
183  ++ci) {
184  add_component(*ci);
185  }
186 
187  } else {
188  // The general case.
189  size_t i = 0;
190  while (i < _components.size()) {
191  const GeometricBoundingVolume *existing = _components[i];
192  ++i;
193 
194  int result = component->contains(existing);
195  if ((result & IF_all) != 0) {
196  // The existing component is entirely within this one; no need
197  // to do anything with it.
198  return;
199 
200  } else if (result == 0) {
201  // No intersection between these components; we're now empty.
202  _flags = F_empty;
203  _components.clear();
204  return;
205  }
206 
207  result = existing->contains(component);
208  if ((result & IF_all) != 0) {
209  // This new component is entirely within an existing
210  // component; no need to keep the existing one.
211  --i;
212  _components.erase(_components.begin() + i);
213 
214  } else if (result == 0) {
215  // No intersection between these components; we're now empty.
216  _flags = F_empty;
217  _components.clear();
218  return;
219  }
220  }
221 
222  _flags &= ~F_infinite;
223  _components.push_back(component);
224  }
225 }
226 
227 ////////////////////////////////////////////////////////////////////
228 // Function: IntersectionBoundingVolume::extend_other
229 // Access: Protected, Virtual
230 // Description:
231 ////////////////////////////////////////////////////////////////////
232 bool IntersectionBoundingVolume::
233 extend_other(BoundingVolume *other) const {
234  return other->extend_by_intersection(this);
235 }
236 
237 ////////////////////////////////////////////////////////////////////
238 // Function: IntersectionBoundingVolume::around_other
239 // Access: Protected, Virtual
240 // Description:
241 ////////////////////////////////////////////////////////////////////
242 bool IntersectionBoundingVolume::
243 around_other(BoundingVolume *other,
244  const BoundingVolume **first,
245  const BoundingVolume **last) const {
246  return other->around_intersections(first, last);
247 }
248 
249 ////////////////////////////////////////////////////////////////////
250 // Function: IntersectionBoundingVolume::contains_other
251 // Access: Protected, Virtual
252 // Description:
253 ////////////////////////////////////////////////////////////////////
254 int IntersectionBoundingVolume::
255 contains_other(const BoundingVolume *other) const {
256  return other->contains_intersection(this);
257 }
258 
259 ////////////////////////////////////////////////////////////////////
260 // Function: IntersectionBoundingVolume::contains_point
261 // Access: Protected, Virtual
262 // Description:
263 ////////////////////////////////////////////////////////////////////
264 int IntersectionBoundingVolume::
265 contains_point(const LPoint3 &point) const {
266  nassertr(!point.is_nan(), IF_no_intersection);
267 
268  int result = IF_possible | IF_some | IF_all;
269  for (Components::const_iterator ci = _components.begin();
270  ci != _components.end();
271  ++ci) {
272  int this_result = (*ci)->contains(point);
273  if ((this_result & IF_dont_understand) != 0) {
274  result |= IF_dont_understand;
275  break;
276  }
277  result &= this_result;
278  if ((result & IF_possible) == 0) {
279  // No point in looking further.
280  break;
281  }
282  }
283 
284  return result;
285 }
286 
287 ////////////////////////////////////////////////////////////////////
288 // Function: IntersectionBoundingVolume::contains_lineseg
289 // Access: Protected, Virtual
290 // Description:
291 ////////////////////////////////////////////////////////////////////
292 int IntersectionBoundingVolume::
293 contains_lineseg(const LPoint3 &a, const LPoint3 &b) const {
294  nassertr(!a.is_nan() && !b.is_nan(), IF_no_intersection);
295 
296  int result = IF_possible | IF_some | IF_all;
297  for (Components::const_iterator ci = _components.begin();
298  ci != _components.end();
299  ++ci) {
300  int this_result = (*ci)->contains(a, b);
301  if ((this_result & IF_dont_understand) != 0) {
302  result |= IF_dont_understand;
303  break;
304  }
305  result &= this_result;
306  if ((result & IF_possible) == 0) {
307  // No point in looking further.
308  break;
309  }
310  }
311 
312  return result;
313 }
314 
315 ////////////////////////////////////////////////////////////////////
316 // Function: IntersectionBoundingVolume::contains_sphere
317 // Access: Protected, Virtual
318 // Description: Double-dispatch support: called by contains_other()
319 // when the type we're testing for intersection is known
320 // to be a sphere.
321 ////////////////////////////////////////////////////////////////////
322 int IntersectionBoundingVolume::
323 contains_sphere(const BoundingSphere *sphere) const {
324  int result = IF_possible | IF_some | IF_all;
325  for (Components::const_iterator ci = _components.begin();
326  ci != _components.end();
327  ++ci) {
328  int this_result = (*ci)->contains_sphere(sphere);
329  if ((this_result & IF_dont_understand) != 0) {
330  result |= IF_dont_understand;
331  break;
332  }
333  result &= this_result;
334  if ((result & IF_possible) == 0) {
335  // No point in looking further.
336  break;
337  }
338  }
339 
340  return result;
341 }
342 
343 ////////////////////////////////////////////////////////////////////
344 // Function: IntersectionBoundingVolume::contains_box
345 // Access: Protected, Virtual
346 // Description: Double-dispatch support: called by contains_other()
347 // when the type we're testing for intersection is known
348 // to be a box.
349 ////////////////////////////////////////////////////////////////////
350 int IntersectionBoundingVolume::
351 contains_box(const BoundingBox *box) const {
352  int result = IF_possible | IF_some | IF_all;
353  for (Components::const_iterator ci = _components.begin();
354  ci != _components.end();
355  ++ci) {
356  int this_result = (*ci)->contains_box(box);
357  if ((this_result & IF_dont_understand) != 0) {
358  result |= IF_dont_understand;
359  break;
360  }
361  result &= this_result;
362  if ((result & IF_possible) == 0) {
363  // No point in looking further.
364  break;
365  }
366  }
367 
368  return result;
369 }
370 
371 ////////////////////////////////////////////////////////////////////
372 // Function: IntersectionBoundingVolume::contains_hexahedron
373 // Access: Protected, Virtual
374 // Description: Double-dispatch support: called by contains_other()
375 // when the type we're testing for intersection is known
376 // to be a hexahedron.
377 ////////////////////////////////////////////////////////////////////
378 int IntersectionBoundingVolume::
379 contains_hexahedron(const BoundingHexahedron *hexahedron) const {
380  int result = IF_possible | IF_some | IF_all;
381  for (Components::const_iterator ci = _components.begin();
382  ci != _components.end();
383  ++ci) {
384  int this_result = (*ci)->contains_hexahedron(hexahedron);
385  if ((this_result & IF_dont_understand) != 0) {
386  result |= IF_dont_understand;
387  break;
388  }
389  result &= this_result;
390  if ((result & IF_possible) == 0) {
391  // No point in looking further.
392  break;
393  }
394  }
395 
396  return result;
397 }
398 
399 ////////////////////////////////////////////////////////////////////
400 // Function: IntersectionBoundingVolume::contains_line
401 // Access: Protected, Virtual
402 // Description: Double-dispatch support: called by contains_other()
403 // when the type we're testing for intersection is known
404 // to be a line.
405 ////////////////////////////////////////////////////////////////////
406 int IntersectionBoundingVolume::
407 contains_line(const BoundingLine *line) const {
408  int result = IF_possible | IF_some | IF_all;
409  for (Components::const_iterator ci = _components.begin();
410  ci != _components.end();
411  ++ci) {
412  int this_result = (*ci)->contains_line(line);
413  if ((this_result & IF_dont_understand) != 0) {
414  result |= IF_dont_understand;
415  break;
416  }
417  result &= this_result;
418  if ((result & IF_possible) == 0) {
419  // No point in looking further.
420  break;
421  }
422  }
423 
424  return result;
425 }
426 
427 ////////////////////////////////////////////////////////////////////
428 // Function: IntersectionBoundingVolume::contains_plane
429 // Access: Protected, Virtual
430 // Description: Double-dispatch support: called by contains_other()
431 // when the type we're testing for intersection is known
432 // to be a plane.
433 ////////////////////////////////////////////////////////////////////
434 int IntersectionBoundingVolume::
435 contains_plane(const BoundingPlane *plane) const {
436  int result = IF_possible | IF_some | IF_all;
437  for (Components::const_iterator ci = _components.begin();
438  ci != _components.end();
439  ++ci) {
440  int this_result = (*ci)->contains_plane(plane);
441  if ((this_result & IF_dont_understand) != 0) {
442  result |= IF_dont_understand;
443  break;
444  }
445  result &= this_result;
446  if ((result & IF_possible) == 0) {
447  // No point in looking further.
448  break;
449  }
450  }
451 
452  return result;
453 }
454 
455 ////////////////////////////////////////////////////////////////////
456 // Function: IntersectionBoundingVolume::contains_union
457 // Access: Protected, Virtual
458 // Description: Double-dispatch support: called by contains_other()
459 // when the type we're testing for intersection is known
460 // to be a union object.
461 ////////////////////////////////////////////////////////////////////
462 int IntersectionBoundingVolume::
463 contains_union(const UnionBoundingVolume *unionv) const {
464  int result = IF_possible | IF_some | IF_all;
465  for (Components::const_iterator ci = _components.begin();
466  ci != _components.end();
467  ++ci) {
468  int this_result = (*ci)->contains_union(unionv);
469  if ((this_result & IF_dont_understand) != 0) {
470  result |= IF_dont_understand;
471  break;
472  }
473  result &= this_result;
474  if ((result & IF_possible) == 0) {
475  // No point in looking further.
476  break;
477  }
478  }
479 
480  return result;
481 }
482 
483 ////////////////////////////////////////////////////////////////////
484 // Function: IntersectionBoundingVolume::contains_intersection
485 // Access: Protected, Virtual
486 // Description: Double-dispatch support: called by contains_other()
487 // when the type we're testing for intersection is known
488 // to be an intersection object.
489 ////////////////////////////////////////////////////////////////////
490 int IntersectionBoundingVolume::
491 contains_intersection(const IntersectionBoundingVolume *intersection) const {
492  int result = IF_possible | IF_some | IF_all;
493  for (Components::const_iterator ci = _components.begin();
494  ci != _components.end();
495  ++ci) {
496  int this_result = (*ci)->contains_intersection(intersection);
497  if ((this_result & IF_dont_understand) != 0) {
498  result |= IF_dont_understand;
499  break;
500  }
501  result &= this_result;
502  if ((result & IF_possible) == 0) {
503  // No point in looking further.
504  break;
505  }
506  }
507 
508  return result;
509 }
510 
511 ////////////////////////////////////////////////////////////////////
512 // Function: IntersectionBoundingVolume::contains_finite
513 // Access: Protected, Virtual
514 // Description: Generic handler for a FiniteBoundingVolume.
515 ////////////////////////////////////////////////////////////////////
516 int IntersectionBoundingVolume::
517 contains_finite(const FiniteBoundingVolume *volume) const {
518  int result = IF_possible | IF_some | IF_all;
519  for (Components::const_iterator ci = _components.begin();
520  ci != _components.end();
521  ++ci) {
522  int this_result = (*ci)->contains_finite(volume);
523  if ((this_result & IF_dont_understand) != 0) {
524  result |= IF_dont_understand;
525  break;
526  }
527  result &= this_result;
528  if ((result & IF_possible) == 0) {
529  // No point in looking further.
530  break;
531  }
532  }
533 
534  return result;
535 }
536 
537 ////////////////////////////////////////////////////////////////////
538 // Function: IntersectionBoundingVolume::contains_geometric
539 // Access: Protected, Virtual
540 // Description: Generic handler for a GeometricBoundingVolume.
541 ////////////////////////////////////////////////////////////////////
542 int IntersectionBoundingVolume::
543 contains_geometric(const GeometricBoundingVolume *volume) const {
544  int result = IF_possible | IF_some | IF_all;
545  for (Components::const_iterator ci = _components.begin();
546  ci != _components.end();
547  ++ci) {
548  int this_result = (*ci)->contains_geometric(volume);
549  if ((this_result & IF_dont_understand) != 0) {
550  result |= IF_dont_understand;
551  break;
552  }
553  result &= this_result;
554  if ((result & IF_possible) == 0) {
555  // No point in looking further.
556  break;
557  }
558  }
559 
560  return result;
561 }
562 
563 
564 ////////////////////////////////////////////////////////////////////
565 // Function: IntersectionBoundingVolume::other_contains_intersection
566 // Access: Protected, Virtual
567 // Description: Generic reverse-direction comparison. Called by
568 // BoundingVolumes that do not implement
569 // contains_intersection() explicitly. This returns the test
570 // of whether the other volume contains this volume.
571 ////////////////////////////////////////////////////////////////////
572 int IntersectionBoundingVolume::
573 other_contains_intersection(const BoundingVolume *volume) const {
574  int result = IF_possible | IF_some | IF_all;
575  for (Components::const_iterator ci = _components.begin();
576  ci != _components.end();
577  ++ci) {
578  int this_result = volume->contains(*ci);
579  if ((this_result & IF_dont_understand) != 0) {
580  result |= IF_dont_understand;
581  break;
582  }
583  result &= this_result;
584  if ((result & IF_possible) == 0) {
585  // No point in looking further.
586  break;
587  }
588  }
589 
590  return result;
591 }
592 
int get_num_components() const
Returns the number of components in the union.
An axis-aligned bounding box; that is, a minimum and maximum coordinate triple.
Definition: boundingBox.h:31
bool is_exact_type(TypeHandle handle) const
Returns true if the current object is the indicated type exactly.
Definition: typedObject.I:74
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...
bool is_empty() const
Any kind of volume might be empty.
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...
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
void clear_components()
Removes all components from the volume.
const GeometricBoundingVolume * get_component(int n) const
Returns the nth component in the union.
A special kind of GeometricBoundingVolume that is known to be finite.
TypeHandle is the identifier used to differentiate C++ class types.
Definition: typeHandle.h:85
This defines a bounding convex hexahedron.
void add_component(const GeometricBoundingVolume *component)
Adds a new component to the volume.
This funny bounding volume is an infinite line with no thickness and extending to infinity in both di...
Definition: boundingLine.h:33
IntersectionBoundingVolume()
Constructs an empty intersection.