Panda3D
collisionTraverser.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 collisionTraverser.cxx
10  * @author drose
11  * @date 2002-03-16
12  */
13 
14 #include "collisionTraverser.h"
15 #include "collisionNode.h"
16 #include "collisionEntry.h"
17 #include "collisionPolygon.h"
18 #include "collisionGeom.h"
19 #include "collisionRecorder.h"
20 #include "collisionVisualizer.h"
21 #include "collisionSphere.h"
22 #include "collisionBox.h"
23 #include "collisionCapsule.h"
24 #include "collisionPolygon.h"
25 #include "collisionPlane.h"
26 #include "config_collide.h"
27 #include "boundingSphere.h"
28 #include "transformState.h"
29 #include "geomNode.h"
30 #include "geom.h"
31 #include "geom.h"
32 #include "geomTriangles.h"
33 #include "geomVertexReader.h"
34 #include "lodNode.h"
35 #include "nodePath.h"
36 #include "pStatTimer.h"
37 #include "indent.h"
38 
39 #include <algorithm>
40 
41 using std::min;
42 
43 PStatCollector CollisionTraverser::_collisions_pcollector("App:Collisions");
44 
45 PStatCollector CollisionTraverser::_cnode_volume_pcollector("Collision Volumes:CollisionNode");
46 PStatCollector CollisionTraverser::_gnode_volume_pcollector("Collision Volumes:GeomNode");
47 PStatCollector CollisionTraverser::_geom_volume_pcollector("Collision Volumes:Geom");
48 
49 TypeHandle CollisionTraverser::_type_handle;
50 
51 // This function object class is used in prepare_colliders(), below.
52 class SortByColliderSort {
53 public:
54  SortByColliderSort(const CollisionTraverser &trav) :
55  _trav(trav)
56  {
57  }
58 
59  inline bool operator () (int a, int b) const {
60  const CollisionTraverser::OrderedColliderDef &ocd_a = _trav._ordered_colliders[a];
61  const CollisionTraverser::OrderedColliderDef &ocd_b = _trav._ordered_colliders[b];
62  return ((const CollisionNode *)ocd_a._node_path.node())->get_collider_sort() < ((const CollisionNode *)ocd_b._node_path.node())->get_collider_sort();
63  }
64 
65  const CollisionTraverser &_trav;
66 };
67 
68 /**
69  *
70  */
71 CollisionTraverser::
72 CollisionTraverser(const std::string &name) :
73  Namable(name),
74  _this_pcollector(_collisions_pcollector, name)
75 {
76  _respect_prev_transform = respect_prev_transform;
77  #ifdef DO_COLLISION_RECORDING
78  _recorder = nullptr;
79  #endif
80 }
81 
82 /**
83  *
84  */
85 CollisionTraverser::
86 ~CollisionTraverser() {
87  #ifdef DO_COLLISION_RECORDING
88  clear_recorder();
89  #endif
90 }
91 
92 /**
93  * Adds a new CollisionNode, representing an object that will be tested for
94  * collisions into other objects, along with the handler that will serve each
95  * detected collision. Each CollisionNode may be served by only one handler
96  * at a time, but a given handler may serve many CollisionNodes.
97  *
98  * The handler that serves a particular node may be changed from time to time
99  * by calling add_collider() again on the same node.
100  */
102 add_collider(const NodePath &collider, CollisionHandler *handler) {
103  nassertv(_ordered_colliders.size() == _colliders.size());
104  nassertv(!collider.is_empty() && collider.node()->is_collision_node());
105  nassertv(handler != nullptr);
106 
107  Colliders::iterator ci = _colliders.find(collider);
108  if (ci != _colliders.end()) {
109  // We already knew about this collider.
110  if ((*ci).second != handler) {
111  // Change the handler.
112  PT(CollisionHandler) old_handler = (*ci).second;
113  (*ci).second = handler;
114 
115  // Now update our own reference counts within our handler set.
116  Handlers::iterator hi = _handlers.find(old_handler);
117  nassertv(hi != _handlers.end());
118  (*hi).second--;
119  nassertv((*hi).second >= 0);
120  if ((*hi).second == 0) {
121  _handlers.erase(hi);
122  }
123 
124  hi = _handlers.find(handler);
125  if (hi == _handlers.end()) {
126  _handlers.insert(Handlers::value_type(handler, 1));
127  } else {
128  ++(*hi).second;
129  }
130  }
131 
132  } else {
133  // We hadn't already known about this collider.
134  _colliders.insert(Colliders::value_type(collider, handler));
135  OrderedColliderDef ocdef;
136  ocdef._node_path = collider;
137  ocdef._in_graph = true;
138  _ordered_colliders.push_back(ocdef);
139 
140  Handlers::iterator hi = _handlers.find(handler);
141  if (hi == _handlers.end()) {
142  _handlers.insert(Handlers::value_type(handler, 1));
143  } else {
144  ++(*hi).second;
145  }
146  }
147 
148  nassertv(_ordered_colliders.size() == _colliders.size());
149 }
150 
151 /**
152  * Removes the collider (and its associated handler) from the set of
153  * CollisionNodes that will be tested each frame for collisions into other
154  * objects. Returns true if the definition was found and removed, false if it
155  * wasn't present to begin with.
156  */
158 remove_collider(const NodePath &collider) {
159  nassertr(_ordered_colliders.size() == _colliders.size(), false);
160 
161  Colliders::iterator ci = _colliders.find(collider);
162  if (ci == _colliders.end()) {
163  // We didn't know about this node.
164  return false;
165  }
166 
167  CollisionHandler *handler = (*ci).second;
168 
169  // Update the set of handlers.
170  Handlers::iterator hi = _handlers.find(handler);
171  nassertr(hi != _handlers.end(), false);
172  (*hi).second--;
173  nassertr((*hi).second >= 0, false);
174  if ((*hi).second == 0) {
175  _handlers.erase(hi);
176  }
177 
178  _colliders.erase(ci);
179 
180  OrderedColliders::iterator oci;
181  oci = _ordered_colliders.begin();
182  while (oci != _ordered_colliders.end() &&
183  (*oci)._node_path != collider) {
184  ++oci;
185  }
186 
187  nassertr(oci != _ordered_colliders.end(), false);
188  _ordered_colliders.erase(oci);
189 
190  nassertr(_ordered_colliders.size() == _colliders.size(), false);
191  return true;
192 }
193 
194 /**
195  * Returns true if the indicated node is current in the set of nodes that will
196  * be tested each frame for collisions into other objects.
197  */
199 has_collider(const NodePath &collider) const {
200  Colliders::const_iterator ci = _colliders.find(collider);
201  return (ci != _colliders.end());
202 }
203 
204 /**
205  * Returns the number of CollisionNodes that have been added to the traverser
206  * via add_collider().
207  */
209 get_num_colliders() const {
210  nassertr(_ordered_colliders.size() == _colliders.size(), 0);
211  return _ordered_colliders.size();
212 }
213 
214 /**
215  * Returns the nth CollisionNode that has been added to the traverser via
216  * add_collider().
217  */
219 get_collider(int n) const {
220  nassertr(_ordered_colliders.size() == _colliders.size(), NodePath());
221  nassertr(n >= 0 && n < (int)_ordered_colliders.size(), NodePath());
222  return _ordered_colliders[n]._node_path;
223 }
224 
225 /**
226  * Returns the handler that is currently assigned to serve the indicated
227  * collision node, or NULL if the node is not on the traverser's set of active
228  * nodes.
229  */
231 get_handler(const NodePath &collider) const {
232  Colliders::const_iterator ci = _colliders.find(collider);
233  if (ci != _colliders.end()) {
234  return (*ci).second;
235  }
236  return nullptr;
237 }
238 
239 /**
240  * Completely empties the set of collision nodes and their associated
241  * handlers.
242  */
244 clear_colliders() {
245  _colliders.clear();
246  _ordered_colliders.clear();
247  _handlers.clear();
248 }
249 
250 /**
251  * Perform the traversal. Begins at the indicated root and detects all
252  * collisions with any of its collider objects against nodes at or below the
253  * indicated root, calling the appropriate CollisionHandler for each detected
254  * collision.
255  */
257 traverse(const NodePath &root) {
258  PStatTimer timer(_this_pcollector);
259 
260  #ifdef DO_COLLISION_RECORDING
261  if (has_recorder()) {
262  get_recorder()->begin_traversal();
263  }
264  #endif // DO_COLLISION_RECORDING
265 
266  Handlers::iterator hi;
267  for (hi = _handlers.begin(); hi != _handlers.end(); ++hi) {
268  if ((*hi).first->wants_all_potential_collidees()) {
269  (*hi).first->set_root(root);
270  }
271  (*hi).first->begin_group();
272  }
273 
274  bool traversal_done = false;
275  if ((int)_colliders.size() <= CollisionLevelStateSingle::get_max_colliders() ||
276  !allow_collider_multiple) {
277  // Use the single-word-at-a-time traverser, which might need to make lots
278  // of passes.
279  LevelStatesSingle level_states;
280  prepare_colliders_single(level_states, root);
281 
282  if (level_states.size() == 1 || !allow_collider_multiple) {
283  traversal_done = true;
284 
285  // Make a number of passes, one for each group of 32 Colliders (or
286  // whatever number of bits we have available in CurrentMask).
287  for (size_t pass = 0; pass < level_states.size(); ++pass) {
288 #ifdef DO_PSTATS
289  PStatTimer pass_timer(get_pass_collector(pass));
290 #endif
291  r_traverse_single(level_states[pass], pass);
292  }
293  }
294  }
295 
296  if (!traversal_done &&
297  (int)_colliders.size() <= CollisionLevelStateDouble::get_max_colliders()) {
298  // Try the double-word-at-a-time traverser.
299  LevelStatesDouble level_states;
300  prepare_colliders_double(level_states, root);
301 
302  if (level_states.size() == 1) {
303  traversal_done = true;
304 
305  for (size_t pass = 0; pass < level_states.size(); ++pass) {
306 #ifdef DO_PSTATS
307  PStatTimer pass_timer(get_pass_collector(pass));
308 #endif
309  r_traverse_double(level_states[pass], pass);
310  }
311  }
312  }
313 
314  if (!traversal_done) {
315  // OK, do the quad-word-at-a-time traverser.
316  LevelStatesQuad level_states;
317  prepare_colliders_quad(level_states, root);
318 
319  traversal_done = true;
320 
321  for (size_t pass = 0; pass < level_states.size(); ++pass) {
322 #ifdef DO_PSTATS
323  PStatTimer pass_timer(get_pass_collector(pass));
324 #endif
325  r_traverse_quad(level_states[pass], pass);
326  }
327  }
328 
329  hi = _handlers.begin();
330  while (hi != _handlers.end()) {
331  if (!(*hi).first->end_group()) {
332  // This handler wants to remove itself from the traversal list.
333  hi = remove_handler(hi);
334  } else {
335  ++hi;
336  }
337  }
338 
339  #ifdef DO_COLLISION_RECORDING
340  if (has_recorder()) {
341  get_recorder()->end_traversal();
342  }
343  #endif // DO_COLLISION_RECORDING
344 
345  CollisionLevelStateBase::_node_volume_pcollector.flush_level();
346  _cnode_volume_pcollector.flush_level();
347  _gnode_volume_pcollector.flush_level();
348  _geom_volume_pcollector.flush_level();
349 
355 }
356 
357 #if defined(DO_COLLISION_RECORDING) || !defined(CPPPARSER)
358 /**
359  * Uses the indicated CollisionRecorder object to start recording the
360  * intersection tests made by each subsequent call to traverse() on this
361  * object. A particular CollisionRecorder object can only record one
362  * traverser at a time; if this object has already been assigned to another
363  * traverser, that assignment is broken.
364  *
365  * This is intended to be used in a debugging mode to try to determine what
366  * work is being performed by the collision traversal. Usually, attaching a
367  * recorder will impose significant runtime overhead.
368  *
369  * This does not transfer ownership of the CollisionRecorder pointer;
370  * maintenance of that remains the caller's responsibility. If the
371  * CollisionRecorder is destructed, it will cleanly remove itself from the
372  * traverser.
373  */
375 set_recorder(CollisionRecorder *recorder) {
376 #ifdef DO_COLLISION_RECORDING
377  if (recorder != _recorder) {
378  // Remove the old recorder, if any.
379  if (_recorder != nullptr) {
380  nassertv(_recorder->_trav == this);
381  _recorder->_trav = nullptr;
382  }
383 
384  _recorder = recorder;
385 
386  // Tell the new recorder about his new owner.
387  if (_recorder != nullptr) {
388  nassertv(_recorder->_trav != this);
389  if (_recorder->_trav != nullptr) {
390  _recorder->_trav->clear_recorder();
391  }
392  nassertv(_recorder->_trav == nullptr);
393  _recorder->_trav = this;
394  }
395  }
396 #endif
397 }
398 
399 /**
400  * This is a high-level function to create a CollisionVisualizer object to
401  * render the collision tests performed by this traverser. The supplied root
402  * should be any node in the scene graph; typically, the top node (e.g.
403  * render). The CollisionVisualizer will be attached to this node.
404  */
405 CollisionVisualizer *CollisionTraverser::
406 show_collisions(const NodePath &root) {
407 #ifdef DO_COLLISION_RECORDING
408  hide_collisions();
409  CollisionVisualizer *viz = new CollisionVisualizer("show_collisions");
410  _collision_visualizer_np = root.attach_new_node(viz);
411  set_recorder(viz);
412  return viz;
413 #else
414  return nullptr;
415 #endif
416 }
417 
418 /**
419  * Undoes the effect of a previous call to show_collisions().
420  */
422 hide_collisions() {
423 #ifdef DO_COLLISION_RECORDING
424  if (!_collision_visualizer_np.is_empty()) {
425  _collision_visualizer_np.remove_node();
426  }
427  clear_recorder();
428 #endif
429 }
430 
431 #endif // DO_COLLISION_RECORDING
432 
433 /**
434  *
435  */
436 void CollisionTraverser::
437 output(std::ostream &out) const {
438  out << "CollisionTraverser, " << _colliders.size()
439  << " colliders and " << _handlers.size() << " handlers.\n";
440 }
441 
442 /**
443  *
444  */
445 void CollisionTraverser::
446 write(std::ostream &out, int indent_level) const {
447  indent(out, indent_level)
448  << "CollisionTraverser, " << _colliders.size()
449  << " colliders and " << _handlers.size() << " handlers:\n";
450 
451  OrderedColliders::const_iterator oci;
452  for (oci = _ordered_colliders.begin();
453  oci != _ordered_colliders.end();
454  ++oci) {
455  NodePath cnode_path = (*oci)._node_path;
456  bool in_graph = (*oci)._in_graph;
457 
458  Colliders::const_iterator ci;
459  ci = _colliders.find(cnode_path);
460  nassertv(ci != _colliders.end());
461 
462  CollisionHandler *handler = (*ci).second;
463  nassertv(handler != nullptr);
464 
465  indent(out, indent_level + 2)
466  << cnode_path;
467  if (in_graph) {
468  out << " handled by " << handler->get_type() << "\n";
469  } else {
470  out << " ignored\n";
471  }
472 
473  if (!cnode_path.is_empty() && cnode_path.node()->is_collision_node()) {
474  CollisionNode *cnode = DCAST(CollisionNode, cnode_path.node());
475 
476  int num_solids = cnode->get_num_solids();
477  for (int i = 0; i < num_solids; ++i) {
478  cnode->get_solid(i)->write(out, indent_level + 4);
479  }
480  }
481  }
482 }
483 
484 /**
485  * Fills up the set of LevelStates corresponding to the active colliders in
486  * use.
487  *
488  * This flavor uses a CollisionLevelStateSingle, which is limited to a certain
489  * number of colliders per pass (typically 32).
490  */
491 void CollisionTraverser::
492 prepare_colliders_single(CollisionTraverser::LevelStatesSingle &level_states,
493  const NodePath &root) {
494  int num_colliders = _colliders.size();
495  int max_colliders = CollisionLevelStateSingle::get_max_colliders();
496 
497  CollisionLevelStateSingle level_state(root);
498  // This reserve() call is only correct if there is exactly one solid per
499  // collider added to the traverser, which is the normal case. If there is
500  // more than one solid in any of the colliders, this reserve() call won't
501  // reserve enough, but the code is otherwise correct.
502  level_state.reserve(min(num_colliders, max_colliders));
503 
504  // Create an indirect index array to walk through the colliders in sorted
505  // order, without affect the actual collider order.
506  int *indirect = (int *)alloca(sizeof(int) * num_colliders);
507  int i;
508  for (i = 0; i < num_colliders; ++i) {
509  indirect[i] = i;
510  }
511  std::sort(indirect, indirect + num_colliders, SortByColliderSort(*this));
512 
513  int num_remaining_colliders = num_colliders;
514  for (i = 0; i < num_colliders; ++i) {
515  OrderedColliderDef &ocd = _ordered_colliders[indirect[i]];
516  NodePath cnode_path = ocd._node_path;
517 
518  if (!cnode_path.is_same_graph(root)) {
519  if (ocd._in_graph) {
520  // Only report this warning once.
521  collide_cat.info()
522  << "Collider " << cnode_path
523  << " is not in scene graph. Ignoring.\n";
524  ocd._in_graph = false;
525  }
526 
527  } else {
528  ocd._in_graph = true;
529  CollisionNode *cnode = DCAST(CollisionNode, cnode_path.node());
530 
532  def._node = cnode;
533  def._node_path = cnode_path;
534 
535  int num_solids = cnode->get_num_solids();
536  for (int s = 0; s < num_solids; ++s) {
537  CPT(CollisionSolid) collider = cnode->get_solid(s);
538  def._collider = collider;
539  level_state.prepare_collider(def, root);
540 
541  if (level_state.get_num_colliders() == max_colliders) {
542  // That's the limit. Save off this level state and make a new one.
543  level_states.push_back(level_state);
544  level_state.clear();
545  level_state.reserve(min(num_remaining_colliders, max_colliders));
546  }
547  }
548  }
549 
550  --num_remaining_colliders;
551  nassertv(num_remaining_colliders >= 0);
552  }
553 
554  if (level_state.get_num_colliders() != 0) {
555  level_states.push_back(level_state);
556  }
557  nassertv(num_remaining_colliders == 0);
558 }
559 
560 /**
561  *
562  */
563 void CollisionTraverser::
564 r_traverse_single(CollisionLevelStateSingle &level_state, size_t pass) {
565  if (!level_state.any_in_bounds()) {
566  return;
567  }
568  if (!level_state.apply_transform()) {
569  return;
570  }
571 
572  PandaNode *node = level_state.node();
573  if (node->is_collision_node()) {
574  CollisionNode *cnode;
575  DCAST_INTO_V(cnode, node);
576  CPT(BoundingVolume) node_bv = cnode->get_bounds();
577  const GeometricBoundingVolume *node_gbv = nullptr;
578  if (node_bv->is_of_type(GeometricBoundingVolume::get_class_type())) {
579  DCAST_INTO_V(node_gbv, node_bv);
580  }
581 
582  CollisionEntry entry;
583  entry._into_node = cnode;
584  entry._into_node_path = level_state.get_node_path();
585  if (_respect_prev_transform) {
586  entry._flags |= CollisionEntry::F_respect_prev_transform;
587  }
588 
589  int num_colliders = level_state.get_num_colliders();
590  for (int c = 0; c < num_colliders; ++c) {
591  if (level_state.has_collider(c)) {
592  entry._from_node = level_state.get_collider_node(c);
593 
594  if ((entry._from_node->get_from_collide_mask() &
595  cnode->get_into_collide_mask()) != 0) {
596  #ifdef DO_PSTATS
597  // PStatTimer collide_timer(_solid_collide_collectors[pass]);
598  #endif
599  entry._from_node_path = level_state.get_collider_node_path(c);
600  entry._from = level_state.get_collider(c);
601 
602  compare_collider_to_node(
603  entry,
604  level_state.get_parent_bound(c),
605  level_state.get_local_bound(c),
606  node_gbv);
607  }
608  }
609  }
610 
611  } else if (node->is_geom_node()) {
612  #ifndef NDEBUG
613  if (collide_cat.is_spam()) {
614  collide_cat.spam()
615  << "Reached " << *node << "\n";
616  }
617  #endif
618 
619  GeomNode *gnode;
620  DCAST_INTO_V(gnode, node);
621  CPT(BoundingVolume) node_bv = gnode->get_bounds();
622  const GeometricBoundingVolume *node_gbv = nullptr;
623  if (node_bv->is_of_type(GeometricBoundingVolume::get_class_type())) {
624  DCAST_INTO_V(node_gbv, node_bv);
625  }
626 
627  CollisionEntry entry;
628  entry._into_node = gnode;
629  entry._into_node_path = level_state.get_node_path();
630  if (_respect_prev_transform) {
631  entry._flags |= CollisionEntry::F_respect_prev_transform;
632  }
633 
634  int num_colliders = level_state.get_num_colliders();
635  for (int c = 0; c < num_colliders; ++c) {
636  if (level_state.has_collider(c)) {
637  entry._from_node = level_state.get_collider_node(c);
638 
639  if ((entry._from_node->get_from_collide_mask() &
640  gnode->get_into_collide_mask()) != 0) {
641  #ifdef DO_PSTATS
642  // PStatTimer collide_timer(_solid_collide_collectors[pass]);
643  #endif
644  entry._from_node_path = level_state.get_collider_node_path(c);
645  entry._from = level_state.get_collider(c);
646 
647  compare_collider_to_geom_node(
648  entry,
649  level_state.get_parent_bound(c),
650  level_state.get_local_bound(c),
651  node_gbv);
652  }
653  }
654  }
655  }
656 
657  if (node->has_single_child_visibility()) {
658  // If it's a switch node or sequence node, visit just the one visible
659  // child.
660  int index = node->get_visible_child();
661  if (index >= 0 && index < node->get_num_children()) {
662  CollisionLevelStateSingle next_state(level_state, node->get_child(index));
663  r_traverse_single(next_state, pass);
664  }
665 
666  } else if (node->is_lod_node()) {
667  // If it's an LODNode, visit the lowest level of detail with all bits,
668  // allowing collision with geometry under the lowest level of default; and
669  // visit all other levels without GeomNode::get_default_collide_mask(),
670  // allowing only collision with CollisionNodes and special geometry under
671  // higher levels of detail.
672  int index = DCAST(LODNode, node)->get_lowest_switch();
673  PandaNode::Children children = node->get_children();
674  int num_children = children.get_num_children();
675  for (int i = 0; i < num_children; ++i) {
676  CollisionLevelStateSingle next_state(level_state, children.get_child(i));
677  if (i != index) {
678  next_state.set_include_mask(next_state.get_include_mask() &
680  }
681  r_traverse_single(next_state, pass);
682  }
683 
684  } else {
685  // Otherwise, visit all the children.
686  PandaNode::Children children = node->get_children();
687  int num_children = children.get_num_children();
688  for (int i = 0; i < num_children; ++i) {
689  CollisionLevelStateSingle next_state(level_state, children.get_child(i));
690  r_traverse_single(next_state, pass);
691  }
692  }
693 }
694 
695 /**
696  * Fills up the set of LevelStates corresponding to the active colliders in
697  * use.
698  *
699  * This flavor uses a CollisionLevelStateDouble, which is limited to a certain
700  * number of colliders per pass (typically 32).
701  */
702 void CollisionTraverser::
703 prepare_colliders_double(CollisionTraverser::LevelStatesDouble &level_states,
704  const NodePath &root) {
705  int num_colliders = _colliders.size();
706  int max_colliders = CollisionLevelStateDouble::get_max_colliders();
707 
708  CollisionLevelStateDouble level_state(root);
709  // This reserve() call is only correct if there is exactly one solid per
710  // collider added to the traverser, which is the normal case. If there is
711  // more than one solid in any of the colliders, this reserve() call won't
712  // reserve enough, but the code is otherwise correct.
713  level_state.reserve(min(num_colliders, max_colliders));
714 
715  // Create an indirect index array to walk through the colliders in sorted
716  // order, without affect the actual collider order.
717  int *indirect = (int *)alloca(sizeof(int) * num_colliders);
718  int i;
719  for (i = 0; i < num_colliders; ++i) {
720  indirect[i] = i;
721  }
722  std::sort(indirect, indirect + num_colliders, SortByColliderSort(*this));
723 
724  int num_remaining_colliders = num_colliders;
725  for (i = 0; i < num_colliders; ++i) {
726  OrderedColliderDef &ocd = _ordered_colliders[indirect[i]];
727  NodePath cnode_path = ocd._node_path;
728 
729  if (!cnode_path.is_same_graph(root)) {
730  if (ocd._in_graph) {
731  // Only report this warning once.
732  collide_cat.info()
733  << "Collider " << cnode_path
734  << " is not in scene graph. Ignoring.\n";
735  ocd._in_graph = false;
736  }
737 
738  } else {
739  ocd._in_graph = true;
740  CollisionNode *cnode = DCAST(CollisionNode, cnode_path.node());
741 
743  def._node = cnode;
744  def._node_path = cnode_path;
745 
746  int num_solids = cnode->get_num_solids();
747  for (int s = 0; s < num_solids; ++s) {
748  CPT(CollisionSolid) collider = cnode->get_solid(s);
749  def._collider = collider;
750  level_state.prepare_collider(def, root);
751 
752  if (level_state.get_num_colliders() == max_colliders) {
753  // That's the limit. Save off this level state and make a new one.
754  level_states.push_back(level_state);
755  level_state.clear();
756  level_state.reserve(min(num_remaining_colliders, max_colliders));
757  }
758  }
759  }
760 
761  --num_remaining_colliders;
762  nassertv(num_remaining_colliders >= 0);
763  }
764 
765  if (level_state.get_num_colliders() != 0) {
766  level_states.push_back(level_state);
767  }
768  nassertv(num_remaining_colliders == 0);
769 }
770 
771 /**
772  *
773  */
774 void CollisionTraverser::
775 r_traverse_double(CollisionLevelStateDouble &level_state, size_t pass) {
776  if (!level_state.any_in_bounds()) {
777  return;
778  }
779  if (!level_state.apply_transform()) {
780  return;
781  }
782 
783  PandaNode *node = level_state.node();
784  if (node->is_collision_node()) {
785  CollisionNode *cnode;
786  DCAST_INTO_V(cnode, node);
787  CPT(BoundingVolume) node_bv = cnode->get_bounds();
788  const GeometricBoundingVolume *node_gbv = nullptr;
789  if (node_bv->is_of_type(GeometricBoundingVolume::get_class_type())) {
790  DCAST_INTO_V(node_gbv, node_bv);
791  }
792 
793  CollisionEntry entry;
794  entry._into_node = cnode;
795  entry._into_node_path = level_state.get_node_path();
796  if (_respect_prev_transform) {
797  entry._flags |= CollisionEntry::F_respect_prev_transform;
798  }
799 
800  int num_colliders = level_state.get_num_colliders();
801  for (int c = 0; c < num_colliders; ++c) {
802  if (level_state.has_collider(c)) {
803  entry._from_node = level_state.get_collider_node(c);
804 
805  if ((entry._from_node->get_from_collide_mask() &
806  cnode->get_into_collide_mask()) != 0) {
807  #ifdef DO_PSTATS
808  // PStatTimer collide_timer(_solid_collide_collectors[pass]);
809  #endif
810  entry._from_node_path = level_state.get_collider_node_path(c);
811  entry._from = level_state.get_collider(c);
812 
813  compare_collider_to_node(
814  entry,
815  level_state.get_parent_bound(c),
816  level_state.get_local_bound(c),
817  node_gbv);
818  }
819  }
820  }
821 
822  } else if (node->is_geom_node()) {
823  #ifndef NDEBUG
824  if (collide_cat.is_spam()) {
825  collide_cat.spam()
826  << "Reached " << *node << "\n";
827  }
828  #endif
829 
830  GeomNode *gnode;
831  DCAST_INTO_V(gnode, node);
832  CPT(BoundingVolume) node_bv = gnode->get_bounds();
833  const GeometricBoundingVolume *node_gbv = nullptr;
834  if (node_bv->is_of_type(GeometricBoundingVolume::get_class_type())) {
835  DCAST_INTO_V(node_gbv, node_bv);
836  }
837 
838  CollisionEntry entry;
839  entry._into_node = gnode;
840  entry._into_node_path = level_state.get_node_path();
841  if (_respect_prev_transform) {
842  entry._flags |= CollisionEntry::F_respect_prev_transform;
843  }
844 
845  int num_colliders = level_state.get_num_colliders();
846  for (int c = 0; c < num_colliders; ++c) {
847  if (level_state.has_collider(c)) {
848  entry._from_node = level_state.get_collider_node(c);
849 
850  if ((entry._from_node->get_from_collide_mask() &
851  gnode->get_into_collide_mask()) != 0) {
852  #ifdef DO_PSTATS
853  // PStatTimer collide_timer(_solid_collide_collectors[pass]);
854  #endif
855  entry._from_node_path = level_state.get_collider_node_path(c);
856  entry._from = level_state.get_collider(c);
857 
858  compare_collider_to_geom_node(
859  entry,
860  level_state.get_parent_bound(c),
861  level_state.get_local_bound(c),
862  node_gbv);
863  }
864  }
865  }
866  }
867 
868  if (node->has_single_child_visibility()) {
869  // If it's a switch node or sequence node, visit just the one visible
870  // child.
871  int index = node->get_visible_child();
872  if (index >= 0 && index < node->get_num_children()) {
873  CollisionLevelStateDouble next_state(level_state, node->get_child(index));
874  r_traverse_double(next_state, pass);
875  }
876 
877  } else if (node->is_lod_node()) {
878  // If it's an LODNode, visit the lowest level of detail with all bits,
879  // allowing collision with geometry under the lowest level of default; and
880  // visit all other levels without GeomNode::get_default_collide_mask(),
881  // allowing only collision with CollisionNodes and special geometry under
882  // higher levels of detail.
883  int index = DCAST(LODNode, node)->get_lowest_switch();
884  PandaNode::Children children = node->get_children();
885  int num_children = children.get_num_children();
886  for (int i = 0; i < num_children; ++i) {
887  CollisionLevelStateDouble next_state(level_state, children.get_child(i));
888  if (i != index) {
889  next_state.set_include_mask(next_state.get_include_mask() &
891  }
892  r_traverse_double(next_state, pass);
893  }
894 
895  } else {
896  // Otherwise, visit all the children.
897  PandaNode::Children children = node->get_children();
898  int num_children = children.get_num_children();
899  for (int i = 0; i < num_children; ++i) {
900  CollisionLevelStateDouble next_state(level_state, children.get_child(i));
901  r_traverse_double(next_state, pass);
902  }
903  }
904 }
905 
906 /**
907  * Fills up the set of LevelStates corresponding to the active colliders in
908  * use.
909  *
910  * This flavor uses a CollisionLevelStateQuad, which is limited to a certain
911  * number of colliders per pass (typically 32).
912  */
913 void CollisionTraverser::
914 prepare_colliders_quad(CollisionTraverser::LevelStatesQuad &level_states,
915  const NodePath &root) {
916  int num_colliders = _colliders.size();
917  int max_colliders = CollisionLevelStateQuad::get_max_colliders();
918 
919  CollisionLevelStateQuad level_state(root);
920  // This reserve() call is only correct if there is exactly one solid per
921  // collider added to the traverser, which is the normal case. If there is
922  // more than one solid in any of the colliders, this reserve() call won't
923  // reserve enough, but the code is otherwise correct.
924  level_state.reserve(min(num_colliders, max_colliders));
925 
926  // Create an indirect index array to walk through the colliders in sorted
927  // order, without affect the actual collider order.
928  int *indirect = (int *)alloca(sizeof(int) * num_colliders);
929  int i;
930  for (i = 0; i < num_colliders; ++i) {
931  indirect[i] = i;
932  }
933  std::sort(indirect, indirect + num_colliders, SortByColliderSort(*this));
934 
935  int num_remaining_colliders = num_colliders;
936  for (i = 0; i < num_colliders; ++i) {
937  OrderedColliderDef &ocd = _ordered_colliders[indirect[i]];
938  NodePath cnode_path = ocd._node_path;
939 
940  if (!cnode_path.is_same_graph(root)) {
941  if (ocd._in_graph) {
942  // Only report this warning once.
943  collide_cat.info()
944  << "Collider " << cnode_path
945  << " is not in scene graph. Ignoring.\n";
946  ocd._in_graph = false;
947  }
948 
949  } else {
950  ocd._in_graph = true;
951  CollisionNode *cnode = DCAST(CollisionNode, cnode_path.node());
952 
954  def._node = cnode;
955  def._node_path = cnode_path;
956 
957  int num_solids = cnode->get_num_solids();
958  for (int s = 0; s < num_solids; ++s) {
959  CPT(CollisionSolid) collider = cnode->get_solid(s);
960  def._collider = collider;
961  level_state.prepare_collider(def, root);
962 
963  if (level_state.get_num_colliders() == max_colliders) {
964  // That's the limit. Save off this level state and make a new one.
965  level_states.push_back(level_state);
966  level_state.clear();
967  level_state.reserve(min(num_remaining_colliders, max_colliders));
968  }
969  }
970  }
971 
972  --num_remaining_colliders;
973  nassertv(num_remaining_colliders >= 0);
974  }
975 
976  if (level_state.get_num_colliders() != 0) {
977  level_states.push_back(level_state);
978  }
979  nassertv(num_remaining_colliders == 0);
980 }
981 
982 /**
983  *
984  */
985 void CollisionTraverser::
986 r_traverse_quad(CollisionLevelStateQuad &level_state, size_t pass) {
987  if (!level_state.any_in_bounds()) {
988  return;
989  }
990  if (!level_state.apply_transform()) {
991  return;
992  }
993 
994  PandaNode *node = level_state.node();
995  if (node->is_collision_node()) {
996  CollisionNode *cnode;
997  DCAST_INTO_V(cnode, node);
998  CPT(BoundingVolume) node_bv = cnode->get_bounds();
999  const GeometricBoundingVolume *node_gbv = nullptr;
1000  if (node_bv->is_of_type(GeometricBoundingVolume::get_class_type())) {
1001  DCAST_INTO_V(node_gbv, node_bv);
1002  }
1003 
1004  CollisionEntry entry;
1005  entry._into_node = cnode;
1006  entry._into_node_path = level_state.get_node_path();
1007  if (_respect_prev_transform) {
1008  entry._flags |= CollisionEntry::F_respect_prev_transform;
1009  }
1010 
1011  int num_colliders = level_state.get_num_colliders();
1012  for (int c = 0; c < num_colliders; ++c) {
1013  if (level_state.has_collider(c)) {
1014  entry._from_node = level_state.get_collider_node(c);
1015 
1016  if ((entry._from_node->get_from_collide_mask() &
1017  cnode->get_into_collide_mask()) != 0) {
1018  #ifdef DO_PSTATS
1019  // PStatTimer collide_timer(_solid_collide_collectors[pass]);
1020  #endif
1021  entry._from_node_path = level_state.get_collider_node_path(c);
1022  entry._from = level_state.get_collider(c);
1023 
1024  compare_collider_to_node(
1025  entry,
1026  level_state.get_parent_bound(c),
1027  level_state.get_local_bound(c),
1028  node_gbv);
1029  }
1030  }
1031  }
1032 
1033  } else if (node->is_geom_node()) {
1034  #ifndef NDEBUG
1035  if (collide_cat.is_spam()) {
1036  collide_cat.spam()
1037  << "Reached " << *node << "\n";
1038  }
1039  #endif
1040 
1041  GeomNode *gnode;
1042  DCAST_INTO_V(gnode, node);
1043  CPT(BoundingVolume) node_bv = gnode->get_bounds();
1044  const GeometricBoundingVolume *node_gbv = nullptr;
1045  if (node_bv->is_of_type(GeometricBoundingVolume::get_class_type())) {
1046  DCAST_INTO_V(node_gbv, node_bv);
1047  }
1048 
1049  CollisionEntry entry;
1050  entry._into_node = gnode;
1051  entry._into_node_path = level_state.get_node_path();
1052  if (_respect_prev_transform) {
1053  entry._flags |= CollisionEntry::F_respect_prev_transform;
1054  }
1055 
1056  int num_colliders = level_state.get_num_colliders();
1057  for (int c = 0; c < num_colliders; ++c) {
1058  if (level_state.has_collider(c)) {
1059  entry._from_node = level_state.get_collider_node(c);
1060 
1061  if ((entry._from_node->get_from_collide_mask() &
1062  gnode->get_into_collide_mask()) != 0) {
1063  #ifdef DO_PSTATS
1064  // PStatTimer collide_timer(_solid_collide_collectors[pass]);
1065  #endif
1066  entry._from_node_path = level_state.get_collider_node_path(c);
1067  entry._from = level_state.get_collider(c);
1068 
1069  compare_collider_to_geom_node(
1070  entry,
1071  level_state.get_parent_bound(c),
1072  level_state.get_local_bound(c),
1073  node_gbv);
1074  }
1075  }
1076  }
1077  }
1078 
1079  if (node->has_single_child_visibility()) {
1080  // If it's a switch node or sequence node, visit just the one visible
1081  // child.
1082  int index = node->get_visible_child();
1083  if (index >= 0 && index < node->get_num_children()) {
1084  CollisionLevelStateQuad next_state(level_state, node->get_child(index));
1085  r_traverse_quad(next_state, pass);
1086  }
1087 
1088  } else if (node->is_lod_node()) {
1089  // If it's an LODNode, visit the lowest level of detail with all bits,
1090  // allowing collision with geometry under the lowest level of default; and
1091  // visit all other levels without GeomNode::get_default_collide_mask(),
1092  // allowing only collision with CollisionNodes and special geometry under
1093  // higher levels of detail.
1094  int index = DCAST(LODNode, node)->get_lowest_switch();
1095  PandaNode::Children children = node->get_children();
1096  int num_children = children.get_num_children();
1097  for (int i = 0; i < num_children; ++i) {
1098  CollisionLevelStateQuad next_state(level_state, children.get_child(i));
1099  if (i != index) {
1100  next_state.set_include_mask(next_state.get_include_mask() &
1102  }
1103  r_traverse_quad(next_state, pass);
1104  }
1105 
1106  } else {
1107  // Otherwise, visit all the children.
1108  PandaNode::Children children = node->get_children();
1109  int num_children = children.get_num_children();
1110  for (int i = 0; i < num_children; ++i) {
1111  CollisionLevelStateQuad next_state(level_state, children.get_child(i));
1112  r_traverse_quad(next_state, pass);
1113  }
1114  }
1115 }
1116 
1117 /**
1118  *
1119  */
1120 void CollisionTraverser::
1121 compare_collider_to_node(CollisionEntry &entry,
1122  const GeometricBoundingVolume *from_parent_gbv,
1123  const GeometricBoundingVolume *from_node_gbv,
1124  const GeometricBoundingVolume *into_node_gbv) {
1125  bool within_node_bounds = true;
1126  if (from_parent_gbv != nullptr &&
1127  into_node_gbv != nullptr) {
1128  within_node_bounds = (into_node_gbv->contains(from_parent_gbv) != 0);
1129  _cnode_volume_pcollector.add_level(1);
1130  }
1131 
1132  if (within_node_bounds) {
1133  Thread *current_thread = Thread::get_current_thread();
1134 
1135  CollisionNode *cnode;
1136  DCAST_INTO_V(cnode, entry._into_node);
1137 
1138  int num_solids = cnode->get_num_solids();
1139  if (collide_cat.is_spam()) {
1140  collide_cat.spam()
1141  << "Colliding against CollisionNode " << entry._into_node
1142  << " which has " << num_solids << " collision solids.\n";
1143  }
1144 
1145  // Only bother to test against each solid's bounding volume if we have
1146  // more than one solid in the node, as a slight optimization. (If the
1147  // node contains just one solid, then the node's bounding volume, which
1148  // we just tested, is the same as the solid's bounding volume.)
1149  if (num_solids == 1) {
1150  entry._into = cnode->_solids[0].get_read_pointer(current_thread);
1151  Colliders::const_iterator ci;
1152  ci = _colliders.find(entry.get_from_node_path());
1153  nassertv(ci != _colliders.end());
1154  entry.test_intersection((*ci).second, this);
1155  } else {
1156  CollisionNode::Solids::const_iterator si;
1157  for (si = cnode->_solids.begin(); si != cnode->_solids.end(); ++si) {
1158  entry._into = (*si).get_read_pointer(current_thread);
1159 
1160  // We should allow a collision test for solid into itself, because the
1161  // solid might be simply instanced into multiple different
1162  // CollisionNodes. We are already filtering out tests for a
1163  // CollisionNode into itself.
1164  CPT(BoundingVolume) solid_bv = entry._into->get_bounds();
1165  const GeometricBoundingVolume *solid_gbv = nullptr;
1166  if (solid_bv->is_of_type(GeometricBoundingVolume::get_class_type())) {
1167  solid_gbv = (const GeometricBoundingVolume *)solid_bv.p();
1168  }
1169 
1170  compare_collider_to_solid(entry, from_node_gbv, solid_gbv);
1171  }
1172  }
1173  }
1174 }
1175 
1176 /**
1177  *
1178  */
1179 void CollisionTraverser::
1180 compare_collider_to_geom_node(CollisionEntry &entry,
1181  const GeometricBoundingVolume *from_parent_gbv,
1182  const GeometricBoundingVolume *from_node_gbv,
1183  const GeometricBoundingVolume *into_node_gbv) {
1184  bool within_node_bounds = true;
1185  if (from_parent_gbv != nullptr &&
1186  into_node_gbv != nullptr) {
1187  within_node_bounds = (into_node_gbv->contains(from_parent_gbv) != 0);
1188  _gnode_volume_pcollector.add_level(1);
1189  }
1190 
1191  if (within_node_bounds) {
1192  GeomNode *gnode;
1193  DCAST_INTO_V(gnode, entry._into_node);
1194  int num_geoms = gnode->get_num_geoms();
1195  for (int s = 0; s < num_geoms; ++s) {
1196  entry._into = nullptr;
1197  const Geom *geom = DCAST(Geom, gnode->get_geom(s));
1198  if (geom != nullptr) {
1199  CPT(BoundingVolume) geom_bv = geom->get_bounds();
1200  const GeometricBoundingVolume *geom_gbv = nullptr;
1201  if (num_geoms > 1 &&
1202  geom_bv->is_of_type(GeometricBoundingVolume::get_class_type())) {
1203  // Only bother to test against each geom's bounding volume if we
1204  // have more than one geom in the node, as a slight optimization.
1205  // (If the node contains just one geom, then the node's bounding
1206  // volume, which we just tested, is the same as the geom's bounding
1207  // volume.)
1208  DCAST_INTO_V(geom_gbv, geom_bv);
1209  }
1210 
1211  compare_collider_to_geom(entry, geom, from_node_gbv, geom_gbv);
1212  }
1213  }
1214  }
1215 }
1216 
1217 /**
1218  *
1219  */
1220 void CollisionTraverser::
1221 compare_collider_to_solid(CollisionEntry &entry,
1222  const GeometricBoundingVolume *from_node_gbv,
1223  const GeometricBoundingVolume *solid_gbv) {
1224  bool within_solid_bounds = true;
1225  if (from_node_gbv != nullptr &&
1226  solid_gbv != nullptr) {
1227  within_solid_bounds = (solid_gbv->contains(from_node_gbv) != 0);
1228  #ifdef DO_PSTATS
1229  ((CollisionSolid *)entry.get_into())->get_volume_pcollector().add_level(1);
1230  #endif // DO_PSTATS
1231 #ifndef NDEBUG
1232  if (collide_cat.is_spam()) {
1233  collide_cat.spam(false)
1234  << "Comparing to solid: " << *from_node_gbv
1235  << " to " << *solid_gbv << ", within_solid_bounds = "
1236  << within_solid_bounds << "\n";
1237  }
1238 #endif // NDEBUG
1239  }
1240  if (within_solid_bounds) {
1241  Colliders::const_iterator ci;
1242  ci = _colliders.find(entry.get_from_node_path());
1243  nassertv(ci != _colliders.end());
1244  entry.test_intersection((*ci).second, this);
1245  }
1246 }
1247 
1248 /**
1249  *
1250  */
1251 void CollisionTraverser::
1252 compare_collider_to_geom(CollisionEntry &entry, const Geom *geom,
1253  const GeometricBoundingVolume *from_node_gbv,
1254  const GeometricBoundingVolume *geom_gbv) {
1255  bool within_geom_bounds = true;
1256  if (from_node_gbv != nullptr &&
1257  geom_gbv != nullptr) {
1258  within_geom_bounds = (geom_gbv->contains(from_node_gbv) != 0);
1259  _geom_volume_pcollector.add_level(1);
1260  }
1261  if (within_geom_bounds) {
1262  Colliders::const_iterator ci;
1263  ci = _colliders.find(entry.get_from_node_path());
1264  nassertv(ci != _colliders.end());
1265 
1266  if (geom->get_primitive_type() == Geom::PT_polygons) {
1267  Thread *current_thread = Thread::get_current_thread();
1268  CPT(GeomVertexData) data = geom->get_animated_vertex_data(true, current_thread);
1269  GeomVertexReader vertex(data, InternalName::get_vertex());
1270 
1271  int num_primitives = geom->get_num_primitives();
1272  for (int i = 0; i < num_primitives; ++i) {
1273  const GeomPrimitive *primitive = geom->get_primitive(i);
1274  CPT(GeomPrimitive) tris = primitive->decompose();
1275  nassertv(tris->is_of_type(GeomTriangles::get_class_type()));
1276 
1277  if (tris->is_indexed()) {
1278  // Indexed case.
1279  GeomVertexReader index(tris->get_vertices(), 0);
1280  while (!index.is_at_end()) {
1281  LPoint3 v[3];
1282 
1283  vertex.set_row_unsafe(index.get_data1i());
1284  v[0] = vertex.get_data3();
1285  vertex.set_row_unsafe(index.get_data1i());
1286  v[1] = vertex.get_data3();
1287  vertex.set_row_unsafe(index.get_data1i());
1288  v[2] = vertex.get_data3();
1289 
1290  // Generate a temporary CollisionGeom on the fly for each triangle
1291  // in the Geom.
1292  if (CollisionPolygon::verify_points(v[0], v[1], v[2])) {
1293  bool within_solid_bounds = true;
1294  if (from_node_gbv != nullptr) {
1295  PT(BoundingSphere) sphere = new BoundingSphere;
1296  sphere->around(v, v + 3);
1297  within_solid_bounds = (sphere->contains(from_node_gbv) != 0);
1298 #ifdef DO_PSTATS
1299  CollisionGeom::_volume_pcollector.add_level(1);
1300 #endif // DO_PSTATS
1301  }
1302  if (within_solid_bounds) {
1303  PT(CollisionGeom) cgeom = new CollisionGeom(LVecBase3(v[0]), LVecBase3(v[1]), LVecBase3(v[2]));
1304  entry._into = cgeom;
1305  entry.test_intersection((*ci).second, this);
1306  }
1307  }
1308  }
1309  } else {
1310  // Non-indexed case.
1311  vertex.set_row_unsafe(primitive->get_first_vertex());
1312  int num_vertices = primitive->get_num_vertices();
1313  for (int i = 0; i < num_vertices; i += 3) {
1314  LPoint3 v[3];
1315 
1316  v[0] = vertex.get_data3();
1317  v[1] = vertex.get_data3();
1318  v[2] = vertex.get_data3();
1319 
1320  // Generate a temporary CollisionGeom on the fly for each triangle
1321  // in the Geom.
1322  if (CollisionPolygon::verify_points(v[0], v[1], v[2])) {
1323  bool within_solid_bounds = true;
1324  if (from_node_gbv != nullptr) {
1325  PT(BoundingSphere) sphere = new BoundingSphere;
1326  sphere->around(v, v + 3);
1327  within_solid_bounds = (sphere->contains(from_node_gbv) != 0);
1328 #ifdef DO_PSTATS
1329  CollisionGeom::_volume_pcollector.add_level(1);
1330 #endif // DO_PSTATS
1331  }
1332  if (within_solid_bounds) {
1333  PT(CollisionGeom) cgeom = new CollisionGeom(LVecBase3(v[0]), LVecBase3(v[1]), LVecBase3(v[2]));
1334  entry._into = cgeom;
1335  entry.test_intersection((*ci).second, this);
1336  }
1337  }
1338  }
1339  }
1340  }
1341  }
1342  }
1343 }
1344 
1345 /**
1346  * Removes the indicated CollisionHandler from the list of handlers to be
1347  * processed, and returns the iterator to the next handler in the list. This
1348  * is designed to be called safely from within a traversal of the handler
1349  * list.
1350  *
1351  * This also removes any colliders that depend on this handler, to keep
1352  * internal structures intact.
1353  */
1354 CollisionTraverser::Handlers::iterator CollisionTraverser::
1355 remove_handler(CollisionTraverser::Handlers::iterator hi) {
1356  nassertr(hi != _handlers.end(), hi);
1357 
1358  CollisionHandler *handler = (*hi).first;
1359  Handlers::iterator hnext = hi;
1360  ++hnext;
1361  _handlers.erase(hi);
1362  hi = hnext;
1363 
1364  // Now scan for colliders that reference this handler.
1365  Colliders::iterator ci;
1366  ci = _colliders.begin();
1367  while (ci != _colliders.end()) {
1368  if ((*ci).second == handler) {
1369  // This collider references this handler; remove it.
1370  NodePath node_path = (*ci).first;
1371 
1372  Colliders::iterator cnext = ci;
1373  ++cnext;
1374  _colliders.erase(ci);
1375  ci = cnext;
1376 
1377  // Also remove it from the ordered list.
1378  OrderedColliders::iterator oci;
1379  oci = _ordered_colliders.begin();
1380  while (oci != _ordered_colliders.end() &&
1381  (*oci)._node_path != node_path) {
1382  ++oci;
1383  }
1384  nassertr(oci != _ordered_colliders.end(), hi);
1385  _ordered_colliders.erase(oci);
1386 
1387  nassertr(_ordered_colliders.size() == _colliders.size(), hi);
1388 
1389  } else {
1390  // This collider references some other handler; keep it.
1391  ++ci;
1392  }
1393  }
1394 
1395  return hi;
1396 }
1397 
1398 /**
1399  * Returns the PStatCollector suitable for timing the nth pass.
1400  */
1401 PStatCollector &CollisionTraverser::
1402 get_pass_collector(int pass) {
1403  nassertr(pass >= 0, _this_pcollector);
1404  while ((int)_pass_collectors.size() <= pass) {
1405  std::ostringstream name;
1406  name << "pass" << (_pass_collectors.size() + 1);
1407  PStatCollector col(_this_pcollector, name.str());
1408  _pass_collectors.push_back(col);
1409  PStatCollector sc_col(col, "solid_collide");
1410  _solid_collide_collectors.push_back(sc_col);
1411  }
1412 
1413  return _pass_collectors[pass];
1414 }
PandaNode::is_lod_node
virtual bool is_lod_node() const
A simple downcast check.
Definition: pandaNode.cxx:2074
Geom
A container for geometry primitives.
Definition: geom.h:54
CollisionTraverser::show_collisions
CollisionVisualizer * show_collisions(const NodePath &root)
This is a high-level function to create a CollisionVisualizer object to render the collision tests pe...
Definition: collisionTraverser.cxx:406
indent
std::ostream & indent(std::ostream &out, int indent_level)
A handy function for doing text formatting.
Definition: indent.cxx:20
nodePath.h
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
CollisionLevelStateBase::node
PandaNode * node() const
Returns the PandaNode pointer of the node we have traversed to.
Definition: collisionLevelStateBase.I:74
PandaNode::is_geom_node
virtual bool is_geom_node() const
A simple downcast check.
Definition: pandaNode.cxx:2062
collisionGeom.h
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
GeomPrimitive::get_first_vertex
int get_first_vertex() const
Returns the first vertex number referenced by the primitive.
Definition: geomPrimitive.I:98
Geom::get_primitive_type
get_primitive_type
Returns the fundamental primitive type that is common to all GeomPrimitives added within the Geom.
Definition: geom.h:74
CollisionLevelState::prepare_collider
void prepare_collider(const ColliderDef &def, const NodePath &root)
Adds the indicated Collider to the set of Colliders in the current level state.
Definition: collisionLevelState.I:84
PandaNode::get_visible_child
virtual int get_visible_child() const
Returns the index number of the currently visible child of this node.
Definition: pandaNode.cxx:451
pvector
This is our own Panda specialization on the default STL vector.
Definition: pvector.h:42
CollisionTraverser::get_num_colliders
get_num_colliders
Returns the number of CollisionNodes that have been added to the traverser via add_collider().
Definition: collisionTraverser.h:62
GeomVertexData
This defines the actual numeric vertex data stored in a Geom, in the structure defined by a particula...
Definition: geomVertexData.h:68
CollisionEntry::get_from_node_path
get_from_node_path
Returns the NodePath that represents the CollisionNode that contains the CollisionSolid that triggere...
Definition: collisionEntry.h:101
BoundingSphere
This defines a bounding sphere, consisting of a center and a radius.
Definition: boundingSphere.h:25
collisionBox.h
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
CollisionTraverser::get_collider
get_collider
Returns the nth CollisionNode that has been added to the traverser via add_collider().
Definition: collisionTraverser.h:62
geomVertexReader.h
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
CollisionEntry
Defines a single collision event.
Definition: collisionEntry.h:42
collisionSphere.h
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
LODNode
A Level-of-Detail node.
Definition: lodNode.h:28
CollisionSphere::flush_level
static void flush_level()
Flushes the PStatCollectors used during traversal.
Definition: collisionSphere.I:56
CollisionCapsule::flush_level
static void flush_level()
Flushes the PStatCollectors used during traversal.
Definition: collisionCapsule.I:62
pStatTimer.h
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
collisionVisualizer.h
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
PandaNode::Children::get_child
PandaNode * get_child(size_t n) const
Returns the nth child of the node.
Definition: pandaNode.I:962
GeomVertexReader
This object provides a high-level interface for quickly reading a sequence of numeric values from a v...
Definition: geomVertexReader.h:47
GeomNode::get_default_collide_mask
get_default_collide_mask
Returns the default into_collide_mask assigned to new GeomNodes.
Definition: geomNode.h:92
collisionNode.h
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
PandaNode::get_children
get_children
Returns an object that can be used to walk through the list of children of the node.
Definition: pandaNode.h:782
GeomNode::get_num_geoms
get_num_geoms
Returns the number of geoms in the node.
Definition: geomNode.h:71
CollisionLevelState::has_collider
bool has_collider(int n) const
Returns true if the nth collider in the LevelState is still part of the level.
Definition: collisionLevelState.I:310
CollisionTraverser::hide_collisions
void hide_collisions()
Undoes the effect of a previous call to show_collisions().
Definition: collisionTraverser.cxx:422
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
Thread::get_current_thread
get_current_thread
Returns a pointer to the currently-executing Thread object.
Definition: thread.h:109
PStatTimer
A lightweight class that can be used to automatically start and stop a PStatCollector around a sectio...
Definition: pStatTimer.h:30
TypeHandle
TypeHandle is the identifier used to differentiate C++ class types.
Definition: typeHandle.h:81
GeomNode
A node that holds Geom objects, renderable pieces of geometry.
Definition: geomNode.h:34
CollisionPolygon::verify_points
static bool verify_points(const LPoint3 *begin, const LPoint3 *end)
Verifies that the indicated set of points will define a valid CollisionPolygon: that is,...
Definition: collisionPolygon.cxx:80
PandaNode::Children
Definition: pandaNode.h:706
CollisionLevelStateBase::get_node_path
NodePath get_node_path() const
Returns the NodePath representing the node instance we have traversed to.
Definition: collisionLevelStateBase.I:66
PandaNode::has_single_child_visibility
virtual bool has_single_child_visibility() const
Should be overridden by derived classes to return true if this kind of node has the special property ...
Definition: pandaNode.cxx:442
transformState.h
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
GeomPrimitive::get_num_vertices
get_num_vertices
Returns the number of indices used by all the primitives in this object.
Definition: geomPrimitive.h:99
GeometricBoundingVolume
This is another abstract class, for a general class of bounding volumes that actually enclose points ...
Definition: geometricBoundingVolume.h:29
boundingSphere.h
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
CollisionHandler
The abstract interface to a number of classes that decide what to do when a collision is detected.
Definition: collisionHandler.h:30
lodNode.h
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
PStatCollector
A lightweight class that represents a single element that may be timed and/or counted via stats.
Definition: pStatCollector.h:43
PandaNode::Children::get_num_children
size_t get_num_children() const
Returns the number of children of the node.
Definition: pandaNode.I:953
CollisionLevelState::any_in_bounds
bool any_in_bounds()
Checks the bounding volume of the current node against each of our colliders.
Definition: collisionLevelState.I:103
PandaNode::get_child
get_child
Returns the nth child node of this node.
Definition: pandaNode.h:124
CollisionTraverser::has_collider
bool has_collider(const NodePath &collider) const
Returns true if the indicated node is current in the set of nodes that will be tested each frame for ...
Definition: collisionTraverser.cxx:199
geomTriangles.h
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
CollisionBox::flush_level
static void flush_level()
Flushes the PStatCollectors used during traversal.
Definition: collisionBox.I:83
collisionCapsule.h
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
geom.h
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
CollisionTraverser::get_handler
CollisionHandler * get_handler(const NodePath &collider) const
Returns the handler that is currently assigned to serve the indicated collision node,...
Definition: collisionTraverser.cxx:231
CollisionTraverser::set_recorder
set_recorder
Uses the indicated CollisionRecorder object to start recording the intersection tests made by each su...
Definition: collisionTraverser.h:75
CollisionSolid
The abstract base class for all things that can collide with other things in the world,...
Definition: collisionSolid.h:45
collisionEntry.h
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
NodePath::is_same_graph
bool is_same_graph(const NodePath &other, Thread *current_thread=Thread::get_current_thread()) const
Returns true if the node represented by this NodePath is parented within the same graph as that of th...
Definition: nodePath.I:275
NodePath
NodePath is the fundamental system for disambiguating instances, and also provides a higher-level int...
Definition: nodePath.h:159
CollisionLevelStateBase::get_local_bound
const GeometricBoundingVolume * get_local_bound(int n) const
Returns the bounding volume of the indicated collider, transformed into the current node's transform ...
Definition: collisionLevelStateBase.I:121
CollisionPlane::flush_level
static void flush_level()
Flushes the PStatCollectors used during traversal.
Definition: collisionPlane.I:45
CollisionTraverser::add_collider
void add_collider(const NodePath &collider, CollisionHandler *handler)
Adds a new CollisionNode, representing an object that will be tested for collisions into other object...
Definition: collisionTraverser.cxx:102
CollisionTraverser::traverse
void traverse(const NodePath &root)
Perform the traversal.
Definition: collisionTraverser.cxx:257
CollisionPolygon::flush_level
static void flush_level()
Flushes the PStatCollectors used during traversal.
Definition: collisionPolygon.I:111
CollisionGeom
A special CollisionPolygon created just for the purpose of detecting collision against geometry.
Definition: collisionGeom.h:29
CollisionLevelState
This is the state information the CollisionTraverser retains for each level during traversal.
Definition: collisionLevelState.h:33
Namable
A base class for all things which can have a name.
Definition: namable.h:26
CollisionLevelState::apply_transform
bool apply_transform()
Applies the inverse transform from the current node, if any, onto all the colliders in the level stat...
Definition: collisionLevelState.I:220
GeometricBoundingVolume::around
bool around(const GeometricBoundingVolume **first, const GeometricBoundingVolume **last)
Resets the volume to enclose only the volumes indicated.
Definition: geometricBoundingVolume.I:44
CollisionEntry::get_into
get_into
Returns the CollisionSolid pointer for the particular solid was collided into.
Definition: collisionEntry.h:98
CollisionLevelStateBase::reserve
void reserve(int num_colliders)
Indicates an intention to add the indicated number of colliders to the level state.
Definition: collisionLevelStateBase.cxx:39
CollisionLevelStateBase::ColliderDef
Definition: collisionLevelStateBase.h:45
NodePath::attach_new_node
NodePath attach_new_node(PandaNode *node, int sort=0, Thread *current_thread=Thread::get_current_thread()) const
Attaches a new node, with or without existing parents, to the scene graph below the referenced node o...
Definition: nodePath.cxx:596
collisionRecorder.h
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
collisionPolygon.h
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
PandaNode::get_into_collide_mask
get_into_collide_mask
Returns the "into" collide mask for this node.
Definition: pandaNode.h:264
geomNode.h
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
indent.h
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
CollisionTraverser::remove_collider
bool remove_collider(const NodePath &collider)
Removes the collider (and its associated handler) from the set of CollisionNodes that will be tested ...
Definition: collisionTraverser.cxx:158
CollisionLevelState::get_max_colliders
static int get_max_colliders()
Returns the maximum number of colliders that may be added to the CollisionLevelStateBase at any one t...
Definition: collisionLevelState.I:298
config_collide.h
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
CollisionTraverser
This class manages the traversal through the scene graph to detect collisions.
Definition: collisionTraverser.h:45
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
CollisionTraverser::clear_colliders
void clear_colliders()
Completely empties the set of collision nodes and their associated handlers.
Definition: collisionTraverser.cxx:244
PandaNode
A basic node of the scene graph or data graph.
Definition: pandaNode.h:65
NodePath::node
PandaNode * node() const
Returns the referenced node of the path.
Definition: nodePath.I:227
Thread
A thread; that is, a lightweight process.
Definition: thread.h:46
collisionPlane.h
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
CollisionNode::get_into_collide_mask
get_into_collide_mask
Returns the current "into" CollideMask.
Definition: collisionNode.h:61
CollisionNode
A node in the scene graph that can hold any number of CollisionSolids.
Definition: collisionNode.h:30
PandaNode::is_collision_node
virtual bool is_collision_node() const
A simple downcast check.
Definition: pandaNode.cxx:2086
CollisionLevelStateBase::get_parent_bound
const GeometricBoundingVolume * get_parent_bound(int n) const
Returns the bounding volume of the indicated collider, transformed into the previous node's transform...
Definition: collisionLevelStateBase.I:139
GeomPrimitive
This is an abstract base class for a family of classes that represent the fundamental geometry primit...
Definition: geomPrimitive.h:56
collisionTraverser.h
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
NodePath::is_empty
bool is_empty() const
Returns true if the NodePath contains no nodes.
Definition: nodePath.I:188