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  */
245  _colliders.clear();
246  _ordered_colliders.clear();
247  _handlers.clear();
248 }
249 
250 /**
251  *
252  */
253 void CollisionTraverser::
254 traverse(const NodePath &root) {
255  PStatTimer timer(_this_pcollector);
256 
257  #ifdef DO_COLLISION_RECORDING
258  if (has_recorder()) {
259  get_recorder()->begin_traversal();
260  }
261  #endif // DO_COLLISION_RECORDING
262 
263  Handlers::iterator hi;
264  for (hi = _handlers.begin(); hi != _handlers.end(); ++hi) {
265  if ((*hi).first->wants_all_potential_collidees()) {
266  (*hi).first->set_root(root);
267  }
268  (*hi).first->begin_group();
269  }
270 
271  bool traversal_done = false;
272  if ((int)_colliders.size() <= CollisionLevelStateSingle::get_max_colliders() ||
273  !allow_collider_multiple) {
274  // Use the single-word-at-a-time traverser, which might need to make lots
275  // of passes.
276  LevelStatesSingle level_states;
277  prepare_colliders_single(level_states, root);
278 
279  if (level_states.size() == 1 || !allow_collider_multiple) {
280  traversal_done = true;
281 
282  // Make a number of passes, one for each group of 32 Colliders (or
283  // whatever number of bits we have available in CurrentMask).
284  for (size_t pass = 0; pass < level_states.size(); ++pass) {
285 #ifdef DO_PSTATS
286  PStatTimer pass_timer(get_pass_collector(pass));
287 #endif
288  r_traverse_single(level_states[pass], pass);
289  }
290  }
291  }
292 
293  if (!traversal_done &&
294  (int)_colliders.size() <= CollisionLevelStateDouble::get_max_colliders()) {
295  // Try the double-word-at-a-time traverser.
296  LevelStatesDouble level_states;
297  prepare_colliders_double(level_states, root);
298 
299  if (level_states.size() == 1) {
300  traversal_done = true;
301 
302  for (size_t pass = 0; pass < level_states.size(); ++pass) {
303 #ifdef DO_PSTATS
304  PStatTimer pass_timer(get_pass_collector(pass));
305 #endif
306  r_traverse_double(level_states[pass], pass);
307  }
308  }
309  }
310 
311  if (!traversal_done) {
312  // OK, do the quad-word-at-a-time traverser.
313  LevelStatesQuad level_states;
314  prepare_colliders_quad(level_states, root);
315 
316  traversal_done = true;
317 
318  for (size_t pass = 0; pass < level_states.size(); ++pass) {
319 #ifdef DO_PSTATS
320  PStatTimer pass_timer(get_pass_collector(pass));
321 #endif
322  r_traverse_quad(level_states[pass], pass);
323  }
324  }
325 
326  hi = _handlers.begin();
327  while (hi != _handlers.end()) {
328  if (!(*hi).first->end_group()) {
329  // This handler wants to remove itself from the traversal list.
330  hi = remove_handler(hi);
331  } else {
332  ++hi;
333  }
334  }
335 
336  #ifdef DO_COLLISION_RECORDING
337  if (has_recorder()) {
338  get_recorder()->end_traversal();
339  }
340  #endif // DO_COLLISION_RECORDING
341 
342  CollisionLevelStateBase::_node_volume_pcollector.flush_level();
343  _cnode_volume_pcollector.flush_level();
344  _gnode_volume_pcollector.flush_level();
345  _geom_volume_pcollector.flush_level();
346 
352 }
353 
354 #if defined(DO_COLLISION_RECORDING) || !defined(CPPPARSER)
355 /**
356  * Uses the indicated CollisionRecorder object to start recording the
357  * intersection tests made by each subsequent call to traverse() on this
358  * object. A particular CollisionRecorder object can only record one
359  * traverser at a time; if this object has already been assigned to another
360  * traverser, that assignment is broken.
361  *
362  * This is intended to be used in a debugging mode to try to determine what
363  * work is being performed by the collision traversal. Usually, attaching a
364  * recorder will impose significant runtime overhead.
365  *
366  * This does not transfer ownership of the CollisionRecorder pointer;
367  * maintenance of that remains the caller's responsibility. If the
368  * CollisionRecorder is destructed, it will cleanly remove itself from the
369  * traverser.
370  */
372 set_recorder(CollisionRecorder *recorder) {
373 #ifdef DO_COLLISION_RECORDING
374  if (recorder != _recorder) {
375  // Remove the old recorder, if any.
376  if (_recorder != nullptr) {
377  nassertv(_recorder->_trav == this);
378  _recorder->_trav = nullptr;
379  }
380 
381  _recorder = recorder;
382 
383  // Tell the new recorder about his new owner.
384  if (_recorder != nullptr) {
385  nassertv(_recorder->_trav != this);
386  if (_recorder->_trav != nullptr) {
387  _recorder->_trav->clear_recorder();
388  }
389  nassertv(_recorder->_trav == nullptr);
390  _recorder->_trav = this;
391  }
392  }
393 #endif
394 }
395 
396 /**
397  * This is a high-level function to create a CollisionVisualizer object to
398  * render the collision tests performed by this traverser. The supplied root
399  * should be any node in the scene graph; typically, the top node (e.g.
400  * render). The CollisionVisualizer will be attached to this node.
401  */
402 CollisionVisualizer *CollisionTraverser::
403 show_collisions(const NodePath &root) {
404 #ifdef DO_COLLISION_RECORDING
405  hide_collisions();
406  CollisionVisualizer *viz = new CollisionVisualizer("show_collisions");
407  _collision_visualizer_np = root.attach_new_node(viz);
408  set_recorder(viz);
409  return viz;
410 #else
411  return nullptr;
412 #endif
413 }
414 
415 /**
416  * Undoes the effect of a previous call to show_collisions().
417  */
420 #ifdef DO_COLLISION_RECORDING
421  if (!_collision_visualizer_np.is_empty()) {
422  _collision_visualizer_np.remove_node();
423  }
424  clear_recorder();
425 #endif
426 }
427 
428 #endif // DO_COLLISION_RECORDING
429 
430 /**
431  *
432  */
433 void CollisionTraverser::
434 output(std::ostream &out) const {
435  out << "CollisionTraverser, " << _colliders.size()
436  << " colliders and " << _handlers.size() << " handlers.\n";
437 }
438 
439 /**
440  *
441  */
442 void CollisionTraverser::
443 write(std::ostream &out, int indent_level) const {
444  indent(out, indent_level)
445  << "CollisionTraverser, " << _colliders.size()
446  << " colliders and " << _handlers.size() << " handlers:\n";
447 
448  OrderedColliders::const_iterator oci;
449  for (oci = _ordered_colliders.begin();
450  oci != _ordered_colliders.end();
451  ++oci) {
452  NodePath cnode_path = (*oci)._node_path;
453  bool in_graph = (*oci)._in_graph;
454 
455  Colliders::const_iterator ci;
456  ci = _colliders.find(cnode_path);
457  nassertv(ci != _colliders.end());
458 
459  CollisionHandler *handler = (*ci).second;
460  nassertv(handler != nullptr);
461 
462  indent(out, indent_level + 2)
463  << cnode_path;
464  if (in_graph) {
465  out << " handled by " << handler->get_type() << "\n";
466  } else {
467  out << " ignored\n";
468  }
469 
470  if (!cnode_path.is_empty() && cnode_path.node()->is_collision_node()) {
471  CollisionNode *cnode = DCAST(CollisionNode, cnode_path.node());
472 
473  int num_solids = cnode->get_num_solids();
474  for (int i = 0; i < num_solids; ++i) {
475  cnode->get_solid(i)->write(out, indent_level + 4);
476  }
477  }
478  }
479 }
480 
481 /**
482  * Fills up the set of LevelStates corresponding to the active colliders in
483  * use.
484  *
485  * This flavor uses a CollisionLevelStateSingle, which is limited to a certain
486  * number of colliders per pass (typically 32).
487  */
488 void CollisionTraverser::
489 prepare_colliders_single(CollisionTraverser::LevelStatesSingle &level_states,
490  const NodePath &root) {
491  int num_colliders = _colliders.size();
492  int max_colliders = CollisionLevelStateSingle::get_max_colliders();
493 
494  CollisionLevelStateSingle level_state(root);
495  // This reserve() call is only correct if there is exactly one solid per
496  // collider added to the traverser, which is the normal case. If there is
497  // more than one solid in any of the colliders, this reserve() call won't
498  // reserve enough, but the code is otherwise correct.
499  level_state.reserve(min(num_colliders, max_colliders));
500 
501  // Create an indirect index array to walk through the colliders in sorted
502  // order, without affect the actual collider order.
503  int *indirect = (int *)alloca(sizeof(int) * num_colliders);
504  int i;
505  for (i = 0; i < num_colliders; ++i) {
506  indirect[i] = i;
507  }
508  std::sort(indirect, indirect + num_colliders, SortByColliderSort(*this));
509 
510  int num_remaining_colliders = num_colliders;
511  for (i = 0; i < num_colliders; ++i) {
512  OrderedColliderDef &ocd = _ordered_colliders[indirect[i]];
513  NodePath cnode_path = ocd._node_path;
514 
515  if (!cnode_path.is_same_graph(root)) {
516  if (ocd._in_graph) {
517  // Only report this warning once.
518  collide_cat.info()
519  << "Collider " << cnode_path
520  << " is not in scene graph. Ignoring.\n";
521  ocd._in_graph = false;
522  }
523 
524  } else {
525  ocd._in_graph = true;
526  CollisionNode *cnode = DCAST(CollisionNode, cnode_path.node());
527 
529  def._node = cnode;
530  def._node_path = cnode_path;
531 
532  int num_solids = cnode->get_num_solids();
533  for (int s = 0; s < num_solids; ++s) {
534  CPT(CollisionSolid) collider = cnode->get_solid(s);
535  def._collider = collider;
536  level_state.prepare_collider(def, root);
537 
538  if (level_state.get_num_colliders() == max_colliders) {
539  // That's the limit. Save off this level state and make a new one.
540  level_states.push_back(level_state);
541  level_state.clear();
542  level_state.reserve(min(num_remaining_colliders, max_colliders));
543  }
544  }
545  }
546 
547  --num_remaining_colliders;
548  nassertv(num_remaining_colliders >= 0);
549  }
550 
551  if (level_state.get_num_colliders() != 0) {
552  level_states.push_back(level_state);
553  }
554  nassertv(num_remaining_colliders == 0);
555 }
556 
557 /**
558  *
559  */
560 void CollisionTraverser::
561 r_traverse_single(CollisionLevelStateSingle &level_state, size_t pass) {
562  if (!level_state.any_in_bounds()) {
563  return;
564  }
565  if (!level_state.apply_transform()) {
566  return;
567  }
568 
569  PandaNode *node = level_state.node();
570  if (node->is_collision_node()) {
571  CollisionNode *cnode;
572  DCAST_INTO_V(cnode, node);
573  CPT(BoundingVolume) node_bv = cnode->get_bounds();
574  const GeometricBoundingVolume *node_gbv = nullptr;
575  if (node_bv->is_of_type(GeometricBoundingVolume::get_class_type())) {
576  DCAST_INTO_V(node_gbv, node_bv);
577  }
578 
579  CollisionEntry entry;
580  entry._into_node = cnode;
581  entry._into_node_path = level_state.get_node_path();
582  if (_respect_prev_transform) {
583  entry._flags |= CollisionEntry::F_respect_prev_transform;
584  }
585 
586  int num_colliders = level_state.get_num_colliders();
587  for (int c = 0; c < num_colliders; ++c) {
588  if (level_state.has_collider(c)) {
589  entry._from_node = level_state.get_collider_node(c);
590 
591  if ((entry._from_node->get_from_collide_mask() &
592  cnode->get_into_collide_mask()) != 0) {
593  #ifdef DO_PSTATS
594  // PStatTimer collide_timer(_solid_collide_collectors[pass]);
595  #endif
596  entry._from_node_path = level_state.get_collider_node_path(c);
597  entry._from = level_state.get_collider(c);
598 
599  compare_collider_to_node(
600  entry,
601  level_state.get_parent_bound(c),
602  level_state.get_local_bound(c),
603  node_gbv);
604  }
605  }
606  }
607 
608  } else if (node->is_geom_node()) {
609  #ifndef NDEBUG
610  if (collide_cat.is_spam()) {
611  collide_cat.spam()
612  << "Reached " << *node << "\n";
613  }
614  #endif
615 
616  GeomNode *gnode;
617  DCAST_INTO_V(gnode, node);
618  CPT(BoundingVolume) node_bv = gnode->get_bounds();
619  const GeometricBoundingVolume *node_gbv = nullptr;
620  if (node_bv->is_of_type(GeometricBoundingVolume::get_class_type())) {
621  DCAST_INTO_V(node_gbv, node_bv);
622  }
623 
624  CollisionEntry entry;
625  entry._into_node = gnode;
626  entry._into_node_path = level_state.get_node_path();
627  if (_respect_prev_transform) {
628  entry._flags |= CollisionEntry::F_respect_prev_transform;
629  }
630 
631  int num_colliders = level_state.get_num_colliders();
632  for (int c = 0; c < num_colliders; ++c) {
633  if (level_state.has_collider(c)) {
634  entry._from_node = level_state.get_collider_node(c);
635 
636  if ((entry._from_node->get_from_collide_mask() &
637  gnode->get_into_collide_mask()) != 0) {
638  #ifdef DO_PSTATS
639  // PStatTimer collide_timer(_solid_collide_collectors[pass]);
640  #endif
641  entry._from_node_path = level_state.get_collider_node_path(c);
642  entry._from = level_state.get_collider(c);
643 
644  compare_collider_to_geom_node(
645  entry,
646  level_state.get_parent_bound(c),
647  level_state.get_local_bound(c),
648  node_gbv);
649  }
650  }
651  }
652  }
653 
654  if (node->has_single_child_visibility()) {
655  // If it's a switch node or sequence node, visit just the one visible
656  // child.
657  int index = node->get_visible_child();
658  if (index >= 0 && index < node->get_num_children()) {
659  CollisionLevelStateSingle next_state(level_state, node->get_child(index));
660  r_traverse_single(next_state, pass);
661  }
662 
663  } else if (node->is_lod_node()) {
664  // If it's an LODNode, visit the lowest level of detail with all bits,
665  // allowing collision with geometry under the lowest level of default; and
666  // visit all other levels without GeomNode::get_default_collide_mask(),
667  // allowing only collision with CollisionNodes and special geometry under
668  // higher levels of detail.
669  int index = DCAST(LODNode, node)->get_lowest_switch();
670  PandaNode::Children children = node->get_children();
671  int num_children = children.get_num_children();
672  for (int i = 0; i < num_children; ++i) {
673  CollisionLevelStateSingle next_state(level_state, children.get_child(i));
674  if (i != index) {
675  next_state.set_include_mask(next_state.get_include_mask() &
677  }
678  r_traverse_single(next_state, pass);
679  }
680 
681  } else {
682  // Otherwise, visit all the children.
683  PandaNode::Children children = node->get_children();
684  int num_children = children.get_num_children();
685  for (int i = 0; i < num_children; ++i) {
686  CollisionLevelStateSingle next_state(level_state, children.get_child(i));
687  r_traverse_single(next_state, pass);
688  }
689  }
690 }
691 
692 /**
693  * Fills up the set of LevelStates corresponding to the active colliders in
694  * use.
695  *
696  * This flavor uses a CollisionLevelStateDouble, which is limited to a certain
697  * number of colliders per pass (typically 32).
698  */
699 void CollisionTraverser::
700 prepare_colliders_double(CollisionTraverser::LevelStatesDouble &level_states,
701  const NodePath &root) {
702  int num_colliders = _colliders.size();
703  int max_colliders = CollisionLevelStateDouble::get_max_colliders();
704 
705  CollisionLevelStateDouble level_state(root);
706  // This reserve() call is only correct if there is exactly one solid per
707  // collider added to the traverser, which is the normal case. If there is
708  // more than one solid in any of the colliders, this reserve() call won't
709  // reserve enough, but the code is otherwise correct.
710  level_state.reserve(min(num_colliders, max_colliders));
711 
712  // Create an indirect index array to walk through the colliders in sorted
713  // order, without affect the actual collider order.
714  int *indirect = (int *)alloca(sizeof(int) * num_colliders);
715  int i;
716  for (i = 0; i < num_colliders; ++i) {
717  indirect[i] = i;
718  }
719  std::sort(indirect, indirect + num_colliders, SortByColliderSort(*this));
720 
721  int num_remaining_colliders = num_colliders;
722  for (i = 0; i < num_colliders; ++i) {
723  OrderedColliderDef &ocd = _ordered_colliders[indirect[i]];
724  NodePath cnode_path = ocd._node_path;
725 
726  if (!cnode_path.is_same_graph(root)) {
727  if (ocd._in_graph) {
728  // Only report this warning once.
729  collide_cat.info()
730  << "Collider " << cnode_path
731  << " is not in scene graph. Ignoring.\n";
732  ocd._in_graph = false;
733  }
734 
735  } else {
736  ocd._in_graph = true;
737  CollisionNode *cnode = DCAST(CollisionNode, cnode_path.node());
738 
740  def._node = cnode;
741  def._node_path = cnode_path;
742 
743  int num_solids = cnode->get_num_solids();
744  for (int s = 0; s < num_solids; ++s) {
745  CPT(CollisionSolid) collider = cnode->get_solid(s);
746  def._collider = collider;
747  level_state.prepare_collider(def, root);
748 
749  if (level_state.get_num_colliders() == max_colliders) {
750  // That's the limit. Save off this level state and make a new one.
751  level_states.push_back(level_state);
752  level_state.clear();
753  level_state.reserve(min(num_remaining_colliders, max_colliders));
754  }
755  }
756  }
757 
758  --num_remaining_colliders;
759  nassertv(num_remaining_colliders >= 0);
760  }
761 
762  if (level_state.get_num_colliders() != 0) {
763  level_states.push_back(level_state);
764  }
765  nassertv(num_remaining_colliders == 0);
766 }
767 
768 /**
769  *
770  */
771 void CollisionTraverser::
772 r_traverse_double(CollisionLevelStateDouble &level_state, size_t pass) {
773  if (!level_state.any_in_bounds()) {
774  return;
775  }
776  if (!level_state.apply_transform()) {
777  return;
778  }
779 
780  PandaNode *node = level_state.node();
781  if (node->is_collision_node()) {
782  CollisionNode *cnode;
783  DCAST_INTO_V(cnode, node);
784  CPT(BoundingVolume) node_bv = cnode->get_bounds();
785  const GeometricBoundingVolume *node_gbv = nullptr;
786  if (node_bv->is_of_type(GeometricBoundingVolume::get_class_type())) {
787  DCAST_INTO_V(node_gbv, node_bv);
788  }
789 
790  CollisionEntry entry;
791  entry._into_node = cnode;
792  entry._into_node_path = level_state.get_node_path();
793  if (_respect_prev_transform) {
794  entry._flags |= CollisionEntry::F_respect_prev_transform;
795  }
796 
797  int num_colliders = level_state.get_num_colliders();
798  for (int c = 0; c < num_colliders; ++c) {
799  if (level_state.has_collider(c)) {
800  entry._from_node = level_state.get_collider_node(c);
801 
802  if ((entry._from_node->get_from_collide_mask() &
803  cnode->get_into_collide_mask()) != 0) {
804  #ifdef DO_PSTATS
805  // PStatTimer collide_timer(_solid_collide_collectors[pass]);
806  #endif
807  entry._from_node_path = level_state.get_collider_node_path(c);
808  entry._from = level_state.get_collider(c);
809 
810  compare_collider_to_node(
811  entry,
812  level_state.get_parent_bound(c),
813  level_state.get_local_bound(c),
814  node_gbv);
815  }
816  }
817  }
818 
819  } else if (node->is_geom_node()) {
820  #ifndef NDEBUG
821  if (collide_cat.is_spam()) {
822  collide_cat.spam()
823  << "Reached " << *node << "\n";
824  }
825  #endif
826 
827  GeomNode *gnode;
828  DCAST_INTO_V(gnode, node);
829  CPT(BoundingVolume) node_bv = gnode->get_bounds();
830  const GeometricBoundingVolume *node_gbv = nullptr;
831  if (node_bv->is_of_type(GeometricBoundingVolume::get_class_type())) {
832  DCAST_INTO_V(node_gbv, node_bv);
833  }
834 
835  CollisionEntry entry;
836  entry._into_node = gnode;
837  entry._into_node_path = level_state.get_node_path();
838  if (_respect_prev_transform) {
839  entry._flags |= CollisionEntry::F_respect_prev_transform;
840  }
841 
842  int num_colliders = level_state.get_num_colliders();
843  for (int c = 0; c < num_colliders; ++c) {
844  if (level_state.has_collider(c)) {
845  entry._from_node = level_state.get_collider_node(c);
846 
847  if ((entry._from_node->get_from_collide_mask() &
848  gnode->get_into_collide_mask()) != 0) {
849  #ifdef DO_PSTATS
850  // PStatTimer collide_timer(_solid_collide_collectors[pass]);
851  #endif
852  entry._from_node_path = level_state.get_collider_node_path(c);
853  entry._from = level_state.get_collider(c);
854 
855  compare_collider_to_geom_node(
856  entry,
857  level_state.get_parent_bound(c),
858  level_state.get_local_bound(c),
859  node_gbv);
860  }
861  }
862  }
863  }
864 
865  if (node->has_single_child_visibility()) {
866  // If it's a switch node or sequence node, visit just the one visible
867  // child.
868  int index = node->get_visible_child();
869  if (index >= 0 && index < node->get_num_children()) {
870  CollisionLevelStateDouble next_state(level_state, node->get_child(index));
871  r_traverse_double(next_state, pass);
872  }
873 
874  } else if (node->is_lod_node()) {
875  // If it's an LODNode, visit the lowest level of detail with all bits,
876  // allowing collision with geometry under the lowest level of default; and
877  // visit all other levels without GeomNode::get_default_collide_mask(),
878  // allowing only collision with CollisionNodes and special geometry under
879  // higher levels of detail.
880  int index = DCAST(LODNode, node)->get_lowest_switch();
881  PandaNode::Children children = node->get_children();
882  int num_children = children.get_num_children();
883  for (int i = 0; i < num_children; ++i) {
884  CollisionLevelStateDouble next_state(level_state, children.get_child(i));
885  if (i != index) {
886  next_state.set_include_mask(next_state.get_include_mask() &
888  }
889  r_traverse_double(next_state, pass);
890  }
891 
892  } else {
893  // Otherwise, visit all the children.
894  PandaNode::Children children = node->get_children();
895  int num_children = children.get_num_children();
896  for (int i = 0; i < num_children; ++i) {
897  CollisionLevelStateDouble next_state(level_state, children.get_child(i));
898  r_traverse_double(next_state, pass);
899  }
900  }
901 }
902 
903 /**
904  * Fills up the set of LevelStates corresponding to the active colliders in
905  * use.
906  *
907  * This flavor uses a CollisionLevelStateQuad, which is limited to a certain
908  * number of colliders per pass (typically 32).
909  */
910 void CollisionTraverser::
911 prepare_colliders_quad(CollisionTraverser::LevelStatesQuad &level_states,
912  const NodePath &root) {
913  int num_colliders = _colliders.size();
914  int max_colliders = CollisionLevelStateQuad::get_max_colliders();
915 
916  CollisionLevelStateQuad level_state(root);
917  // This reserve() call is only correct if there is exactly one solid per
918  // collider added to the traverser, which is the normal case. If there is
919  // more than one solid in any of the colliders, this reserve() call won't
920  // reserve enough, but the code is otherwise correct.
921  level_state.reserve(min(num_colliders, max_colliders));
922 
923  // Create an indirect index array to walk through the colliders in sorted
924  // order, without affect the actual collider order.
925  int *indirect = (int *)alloca(sizeof(int) * num_colliders);
926  int i;
927  for (i = 0; i < num_colliders; ++i) {
928  indirect[i] = i;
929  }
930  std::sort(indirect, indirect + num_colliders, SortByColliderSort(*this));
931 
932  int num_remaining_colliders = num_colliders;
933  for (i = 0; i < num_colliders; ++i) {
934  OrderedColliderDef &ocd = _ordered_colliders[indirect[i]];
935  NodePath cnode_path = ocd._node_path;
936 
937  if (!cnode_path.is_same_graph(root)) {
938  if (ocd._in_graph) {
939  // Only report this warning once.
940  collide_cat.info()
941  << "Collider " << cnode_path
942  << " is not in scene graph. Ignoring.\n";
943  ocd._in_graph = false;
944  }
945 
946  } else {
947  ocd._in_graph = true;
948  CollisionNode *cnode = DCAST(CollisionNode, cnode_path.node());
949 
951  def._node = cnode;
952  def._node_path = cnode_path;
953 
954  int num_solids = cnode->get_num_solids();
955  for (int s = 0; s < num_solids; ++s) {
956  CPT(CollisionSolid) collider = cnode->get_solid(s);
957  def._collider = collider;
958  level_state.prepare_collider(def, root);
959 
960  if (level_state.get_num_colliders() == max_colliders) {
961  // That's the limit. Save off this level state and make a new one.
962  level_states.push_back(level_state);
963  level_state.clear();
964  level_state.reserve(min(num_remaining_colliders, max_colliders));
965  }
966  }
967  }
968 
969  --num_remaining_colliders;
970  nassertv(num_remaining_colliders >= 0);
971  }
972 
973  if (level_state.get_num_colliders() != 0) {
974  level_states.push_back(level_state);
975  }
976  nassertv(num_remaining_colliders == 0);
977 }
978 
979 /**
980  *
981  */
982 void CollisionTraverser::
983 r_traverse_quad(CollisionLevelStateQuad &level_state, size_t pass) {
984  if (!level_state.any_in_bounds()) {
985  return;
986  }
987  if (!level_state.apply_transform()) {
988  return;
989  }
990 
991  PandaNode *node = level_state.node();
992  if (node->is_collision_node()) {
993  CollisionNode *cnode;
994  DCAST_INTO_V(cnode, node);
995  CPT(BoundingVolume) node_bv = cnode->get_bounds();
996  const GeometricBoundingVolume *node_gbv = nullptr;
997  if (node_bv->is_of_type(GeometricBoundingVolume::get_class_type())) {
998  DCAST_INTO_V(node_gbv, node_bv);
999  }
1000 
1001  CollisionEntry entry;
1002  entry._into_node = cnode;
1003  entry._into_node_path = level_state.get_node_path();
1004  if (_respect_prev_transform) {
1005  entry._flags |= CollisionEntry::F_respect_prev_transform;
1006  }
1007 
1008  int num_colliders = level_state.get_num_colliders();
1009  for (int c = 0; c < num_colliders; ++c) {
1010  if (level_state.has_collider(c)) {
1011  entry._from_node = level_state.get_collider_node(c);
1012 
1013  if ((entry._from_node->get_from_collide_mask() &
1014  cnode->get_into_collide_mask()) != 0) {
1015  #ifdef DO_PSTATS
1016  // PStatTimer collide_timer(_solid_collide_collectors[pass]);
1017  #endif
1018  entry._from_node_path = level_state.get_collider_node_path(c);
1019  entry._from = level_state.get_collider(c);
1020 
1021  compare_collider_to_node(
1022  entry,
1023  level_state.get_parent_bound(c),
1024  level_state.get_local_bound(c),
1025  node_gbv);
1026  }
1027  }
1028  }
1029 
1030  } else if (node->is_geom_node()) {
1031  #ifndef NDEBUG
1032  if (collide_cat.is_spam()) {
1033  collide_cat.spam()
1034  << "Reached " << *node << "\n";
1035  }
1036  #endif
1037 
1038  GeomNode *gnode;
1039  DCAST_INTO_V(gnode, node);
1040  CPT(BoundingVolume) node_bv = gnode->get_bounds();
1041  const GeometricBoundingVolume *node_gbv = nullptr;
1042  if (node_bv->is_of_type(GeometricBoundingVolume::get_class_type())) {
1043  DCAST_INTO_V(node_gbv, node_bv);
1044  }
1045 
1046  CollisionEntry entry;
1047  entry._into_node = gnode;
1048  entry._into_node_path = level_state.get_node_path();
1049  if (_respect_prev_transform) {
1050  entry._flags |= CollisionEntry::F_respect_prev_transform;
1051  }
1052 
1053  int num_colliders = level_state.get_num_colliders();
1054  for (int c = 0; c < num_colliders; ++c) {
1055  if (level_state.has_collider(c)) {
1056  entry._from_node = level_state.get_collider_node(c);
1057 
1058  if ((entry._from_node->get_from_collide_mask() &
1059  gnode->get_into_collide_mask()) != 0) {
1060  #ifdef DO_PSTATS
1061  // PStatTimer collide_timer(_solid_collide_collectors[pass]);
1062  #endif
1063  entry._from_node_path = level_state.get_collider_node_path(c);
1064  entry._from = level_state.get_collider(c);
1065 
1066  compare_collider_to_geom_node(
1067  entry,
1068  level_state.get_parent_bound(c),
1069  level_state.get_local_bound(c),
1070  node_gbv);
1071  }
1072  }
1073  }
1074  }
1075 
1076  if (node->has_single_child_visibility()) {
1077  // If it's a switch node or sequence node, visit just the one visible
1078  // child.
1079  int index = node->get_visible_child();
1080  if (index >= 0 && index < node->get_num_children()) {
1081  CollisionLevelStateQuad next_state(level_state, node->get_child(index));
1082  r_traverse_quad(next_state, pass);
1083  }
1084 
1085  } else if (node->is_lod_node()) {
1086  // If it's an LODNode, visit the lowest level of detail with all bits,
1087  // allowing collision with geometry under the lowest level of default; and
1088  // visit all other levels without GeomNode::get_default_collide_mask(),
1089  // allowing only collision with CollisionNodes and special geometry under
1090  // higher levels of detail.
1091  int index = DCAST(LODNode, node)->get_lowest_switch();
1092  PandaNode::Children children = node->get_children();
1093  int num_children = children.get_num_children();
1094  for (int i = 0; i < num_children; ++i) {
1095  CollisionLevelStateQuad next_state(level_state, children.get_child(i));
1096  if (i != index) {
1097  next_state.set_include_mask(next_state.get_include_mask() &
1099  }
1100  r_traverse_quad(next_state, pass);
1101  }
1102 
1103  } else {
1104  // Otherwise, visit all the children.
1105  PandaNode::Children children = node->get_children();
1106  int num_children = children.get_num_children();
1107  for (int i = 0; i < num_children; ++i) {
1108  CollisionLevelStateQuad next_state(level_state, children.get_child(i));
1109  r_traverse_quad(next_state, pass);
1110  }
1111  }
1112 }
1113 
1114 /**
1115  *
1116  */
1117 void CollisionTraverser::
1118 compare_collider_to_node(CollisionEntry &entry,
1119  const GeometricBoundingVolume *from_parent_gbv,
1120  const GeometricBoundingVolume *from_node_gbv,
1121  const GeometricBoundingVolume *into_node_gbv) {
1122  bool within_node_bounds = true;
1123  if (from_parent_gbv != nullptr &&
1124  into_node_gbv != nullptr) {
1125  within_node_bounds = (into_node_gbv->contains(from_parent_gbv) != 0);
1126  _cnode_volume_pcollector.add_level(1);
1127  }
1128 
1129  if (within_node_bounds) {
1130  Thread *current_thread = Thread::get_current_thread();
1131 
1132  CollisionNode *cnode;
1133  DCAST_INTO_V(cnode, entry._into_node);
1134 
1135  int num_solids = cnode->get_num_solids();
1136  if (collide_cat.is_spam()) {
1137  collide_cat.spam()
1138  << "Colliding against CollisionNode " << entry._into_node
1139  << " which has " << num_solids << " collision solids.\n";
1140  }
1141 
1142  // Only bother to test against each solid's bounding volume if we have
1143  // more than one solid in the node, as a slight optimization. (If the
1144  // node contains just one solid, then the node's bounding volume, which
1145  // we just tested, is the same as the solid's bounding volume.)
1146  if (num_solids == 1) {
1147  entry._into = cnode->_solids[0].get_read_pointer(current_thread);
1148  Colliders::const_iterator ci;
1149  ci = _colliders.find(entry.get_from_node_path());
1150  nassertv(ci != _colliders.end());
1151  entry.test_intersection((*ci).second, this);
1152  } else {
1153  CollisionNode::Solids::const_iterator si;
1154  for (si = cnode->_solids.begin(); si != cnode->_solids.end(); ++si) {
1155  entry._into = (*si).get_read_pointer(current_thread);
1156 
1157  // We should allow a collision test for solid into itself, because the
1158  // solid might be simply instanced into multiple different
1159  // CollisionNodes. We are already filtering out tests for a
1160  // CollisionNode into itself.
1161  CPT(BoundingVolume) solid_bv = entry._into->get_bounds();
1162  const GeometricBoundingVolume *solid_gbv = nullptr;
1163  if (solid_bv->is_of_type(GeometricBoundingVolume::get_class_type())) {
1164  solid_gbv = (const GeometricBoundingVolume *)solid_bv.p();
1165  }
1166 
1167  compare_collider_to_solid(entry, from_node_gbv, solid_gbv);
1168  }
1169  }
1170  }
1171 }
1172 
1173 /**
1174  *
1175  */
1176 void CollisionTraverser::
1177 compare_collider_to_geom_node(CollisionEntry &entry,
1178  const GeometricBoundingVolume *from_parent_gbv,
1179  const GeometricBoundingVolume *from_node_gbv,
1180  const GeometricBoundingVolume *into_node_gbv) {
1181  bool within_node_bounds = true;
1182  if (from_parent_gbv != nullptr &&
1183  into_node_gbv != nullptr) {
1184  within_node_bounds = (into_node_gbv->contains(from_parent_gbv) != 0);
1185  _gnode_volume_pcollector.add_level(1);
1186  }
1187 
1188  if (within_node_bounds) {
1189  GeomNode *gnode;
1190  DCAST_INTO_V(gnode, entry._into_node);
1191  int num_geoms = gnode->get_num_geoms();
1192  for (int s = 0; s < num_geoms; ++s) {
1193  entry._into = nullptr;
1194  const Geom *geom = DCAST(Geom, gnode->get_geom(s));
1195  if (geom != nullptr) {
1196  CPT(BoundingVolume) geom_bv = geom->get_bounds();
1197  const GeometricBoundingVolume *geom_gbv = nullptr;
1198  if (num_geoms > 1 &&
1199  geom_bv->is_of_type(GeometricBoundingVolume::get_class_type())) {
1200  // Only bother to test against each geom's bounding volume if we
1201  // have more than one geom in the node, as a slight optimization.
1202  // (If the node contains just one geom, then the node's bounding
1203  // volume, which we just tested, is the same as the geom's bounding
1204  // volume.)
1205  DCAST_INTO_V(geom_gbv, geom_bv);
1206  }
1207 
1208  compare_collider_to_geom(entry, geom, from_node_gbv, geom_gbv);
1209  }
1210  }
1211  }
1212 }
1213 
1214 /**
1215  *
1216  */
1217 void CollisionTraverser::
1218 compare_collider_to_solid(CollisionEntry &entry,
1219  const GeometricBoundingVolume *from_node_gbv,
1220  const GeometricBoundingVolume *solid_gbv) {
1221  bool within_solid_bounds = true;
1222  if (from_node_gbv != nullptr &&
1223  solid_gbv != nullptr) {
1224  within_solid_bounds = (solid_gbv->contains(from_node_gbv) != 0);
1225  #ifdef DO_PSTATS
1226  ((CollisionSolid *)entry.get_into())->get_volume_pcollector().add_level(1);
1227  #endif // DO_PSTATS
1228 #ifndef NDEBUG
1229  if (collide_cat.is_spam()) {
1230  collide_cat.spam(false)
1231  << "Comparing to solid: " << *from_node_gbv
1232  << " to " << *solid_gbv << ", within_solid_bounds = "
1233  << within_solid_bounds << "\n";
1234  }
1235 #endif // NDEBUG
1236  }
1237  if (within_solid_bounds) {
1238  Colliders::const_iterator ci;
1239  ci = _colliders.find(entry.get_from_node_path());
1240  nassertv(ci != _colliders.end());
1241  entry.test_intersection((*ci).second, this);
1242  }
1243 }
1244 
1245 /**
1246  *
1247  */
1248 void CollisionTraverser::
1249 compare_collider_to_geom(CollisionEntry &entry, const Geom *geom,
1250  const GeometricBoundingVolume *from_node_gbv,
1251  const GeometricBoundingVolume *geom_gbv) {
1252  bool within_geom_bounds = true;
1253  if (from_node_gbv != nullptr &&
1254  geom_gbv != nullptr) {
1255  within_geom_bounds = (geom_gbv->contains(from_node_gbv) != 0);
1256  _geom_volume_pcollector.add_level(1);
1257  }
1258  if (within_geom_bounds) {
1259  Colliders::const_iterator ci;
1260  ci = _colliders.find(entry.get_from_node_path());
1261  nassertv(ci != _colliders.end());
1262 
1263  if (geom->get_primitive_type() == Geom::PT_polygons) {
1264  Thread *current_thread = Thread::get_current_thread();
1265  CPT(GeomVertexData) data = geom->get_animated_vertex_data(true, current_thread);
1266  GeomVertexReader vertex(data, InternalName::get_vertex());
1267 
1268  int num_primitives = geom->get_num_primitives();
1269  for (int i = 0; i < num_primitives; ++i) {
1270  const GeomPrimitive *primitive = geom->get_primitive(i);
1271  CPT(GeomPrimitive) tris = primitive->decompose();
1272  nassertv(tris->is_of_type(GeomTriangles::get_class_type()));
1273 
1274  if (tris->is_indexed()) {
1275  // Indexed case.
1276  GeomVertexReader index(tris->get_vertices(), 0);
1277  while (!index.is_at_end()) {
1278  LPoint3 v[3];
1279 
1280  vertex.set_row_unsafe(index.get_data1i());
1281  v[0] = vertex.get_data3();
1282  vertex.set_row_unsafe(index.get_data1i());
1283  v[1] = vertex.get_data3();
1284  vertex.set_row_unsafe(index.get_data1i());
1285  v[2] = vertex.get_data3();
1286 
1287  // Generate a temporary CollisionGeom on the fly for each triangle
1288  // in the Geom.
1289  if (CollisionPolygon::verify_points(v[0], v[1], v[2])) {
1290  bool within_solid_bounds = true;
1291  if (from_node_gbv != nullptr) {
1292  PT(BoundingSphere) sphere = new BoundingSphere;
1293  sphere->around(v, v + 3);
1294  within_solid_bounds = (sphere->contains(from_node_gbv) != 0);
1295 #ifdef DO_PSTATS
1296  CollisionGeom::_volume_pcollector.add_level(1);
1297 #endif // DO_PSTATS
1298  }
1299  if (within_solid_bounds) {
1300  PT(CollisionGeom) cgeom = new CollisionGeom(LVecBase3(v[0]), LVecBase3(v[1]), LVecBase3(v[2]));
1301  entry._into = cgeom;
1302  entry.test_intersection((*ci).second, this);
1303  }
1304  }
1305  }
1306  } else {
1307  // Non-indexed case.
1308  vertex.set_row_unsafe(primitive->get_first_vertex());
1309  int num_vertices = primitive->get_num_vertices();
1310  for (int i = 0; i < num_vertices; i += 3) {
1311  LPoint3 v[3];
1312 
1313  v[0] = vertex.get_data3();
1314  v[1] = vertex.get_data3();
1315  v[2] = vertex.get_data3();
1316 
1317  // Generate a temporary CollisionGeom on the fly for each triangle
1318  // in the Geom.
1319  if (CollisionPolygon::verify_points(v[0], v[1], v[2])) {
1320  bool within_solid_bounds = true;
1321  if (from_node_gbv != nullptr) {
1322  PT(BoundingSphere) sphere = new BoundingSphere;
1323  sphere->around(v, v + 3);
1324  within_solid_bounds = (sphere->contains(from_node_gbv) != 0);
1325 #ifdef DO_PSTATS
1326  CollisionGeom::_volume_pcollector.add_level(1);
1327 #endif // DO_PSTATS
1328  }
1329  if (within_solid_bounds) {
1330  PT(CollisionGeom) cgeom = new CollisionGeom(LVecBase3(v[0]), LVecBase3(v[1]), LVecBase3(v[2]));
1331  entry._into = cgeom;
1332  entry.test_intersection((*ci).second, this);
1333  }
1334  }
1335  }
1336  }
1337  }
1338  }
1339  }
1340 }
1341 
1342 /**
1343  * Removes the indicated CollisionHandler from the list of handlers to be
1344  * processed, and returns the iterator to the next handler in the list. This
1345  * is designed to be called safely from within a traversal of the handler
1346  * list.
1347  *
1348  * This also removes any colliders that depend on this handler, to keep
1349  * internal structures intact.
1350  */
1351 CollisionTraverser::Handlers::iterator CollisionTraverser::
1352 remove_handler(CollisionTraverser::Handlers::iterator hi) {
1353  nassertr(hi != _handlers.end(), hi);
1354 
1355  CollisionHandler *handler = (*hi).first;
1356  Handlers::iterator hnext = hi;
1357  ++hnext;
1358  _handlers.erase(hi);
1359  hi = hnext;
1360 
1361  // Now scan for colliders that reference this handler.
1362  Colliders::iterator ci;
1363  ci = _colliders.begin();
1364  while (ci != _colliders.end()) {
1365  if ((*ci).second == handler) {
1366  // This collider references this handler; remove it.
1367  NodePath node_path = (*ci).first;
1368 
1369  Colliders::iterator cnext = ci;
1370  ++cnext;
1371  _colliders.erase(ci);
1372  ci = cnext;
1373 
1374  // Also remove it from the ordered list.
1375  OrderedColliders::iterator oci;
1376  oci = _ordered_colliders.begin();
1377  while (oci != _ordered_colliders.end() &&
1378  (*oci)._node_path != node_path) {
1379  ++oci;
1380  }
1381  nassertr(oci != _ordered_colliders.end(), hi);
1382  _ordered_colliders.erase(oci);
1383 
1384  nassertr(_ordered_colliders.size() == _colliders.size(), hi);
1385 
1386  } else {
1387  // This collider references some other handler; keep it.
1388  ++ci;
1389  }
1390  }
1391 
1392  return hi;
1393 }
1394 
1395 /**
1396  * Returns the PStatCollector suitable for timing the nth pass.
1397  */
1398 PStatCollector &CollisionTraverser::
1399 get_pass_collector(int pass) {
1400  nassertr(pass >= 0, _this_pcollector);
1401  while ((int)_pass_collectors.size() <= pass) {
1402  std::ostringstream name;
1403  name << "pass" << (_pass_collectors.size() + 1);
1404  PStatCollector col(_this_pcollector, name.str());
1405  _pass_collectors.push_back(col);
1406  PStatCollector sc_col(col, "solid_collide");
1407  _solid_collide_collectors.push_back(sc_col);
1408  }
1409 
1410  return _pass_collectors[pass];
1411 }
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:403
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:419
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
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
CollisionPolygon::verify_points
static bool verify_points(const LPoint3 &a, const LPoint3 &b, const LPoint3 &c)
Verifies that the indicated set of points will define a valid CollisionPolygon: that is,...
Definition: collisionPolygon.I:82
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
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:563
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:64
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