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 }
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
This defines a bounding sphere, consisting of a center and a radius.
This is an abstract class for any volume in any sense which can be said to define the locality of ref...
static void flush_level()
Flushes the PStatCollectors used during traversal.
Definition: collisionBox.I:83
static void flush_level()
Flushes the PStatCollectors used during traversal.
Defines a single collision event.
get_into
Returns the CollisionSolid pointer for the particular solid was collided into.
get_from_node_path
Returns the NodePath that represents the CollisionNode that contains the CollisionSolid that triggere...
A special CollisionPolygon created just for the purpose of detecting collision against geometry.
Definition: collisionGeom.h:29
The abstract interface to a number of classes that decide what to do when a collision is detected.
void reserve(int num_colliders)
Indicates an intention to add the indicated number of colliders to the level state.
const GeometricBoundingVolume * get_parent_bound(int n) const
Returns the bounding volume of the indicated collider, transformed into the previous node's transform...
PandaNode * node() const
Returns the PandaNode pointer of the node we have traversed to.
const GeometricBoundingVolume * get_local_bound(int n) const
Returns the bounding volume of the indicated collider, transformed into the current node's transform ...
NodePath get_node_path() const
Returns the NodePath representing the node instance we have traversed to.
This is the state information the CollisionTraverser retains for each level during traversal.
bool any_in_bounds()
Checks the bounding volume of the current node against each of our colliders.
bool has_collider(int n) const
Returns true if the nth collider in the LevelState is still part of the level.
void prepare_collider(const ColliderDef &def, const NodePath &root)
Adds the indicated Collider to the set of Colliders in the current level state.
bool apply_transform()
Applies the inverse transform from the current node, if any, onto all the colliders in the level stat...
static int get_max_colliders()
Returns the maximum number of colliders that may be added to the CollisionLevelStateBase at any one t...
A node in the scene graph that can hold any number of CollisionSolids.
Definition: collisionNode.h:30
get_into_collide_mask
Returns the current "into" CollideMask.
Definition: collisionNode.h:61
static void flush_level()
Flushes the PStatCollectors used during traversal.
static bool verify_points(const LPoint3 *begin, const LPoint3 *end)
Verifies that the indicated set of points will define a valid CollisionPolygon: that is,...
static void flush_level()
Flushes the PStatCollectors used during traversal.
The abstract base class for all things that can collide with other things in the world,...
static void flush_level()
Flushes the PStatCollectors used during traversal.
This class manages the traversal through the scene graph to detect collisions.
CollisionHandler * get_handler(const NodePath &collider) const
Returns the handler that is currently assigned to serve the indicated collision node,...
get_collider
Returns the nth CollisionNode that has been added to the traverser via add_collider().
bool remove_collider(const NodePath &collider)
Removes the collider (and its associated handler) from the set of CollisionNodes that will be tested ...
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 ...
set_recorder
Uses the indicated CollisionRecorder object to start recording the intersection tests made by each su...
void clear_colliders()
Completely empties the set of collision nodes and their associated handlers.
CollisionVisualizer * show_collisions(const NodePath &root)
This is a high-level function to create a CollisionVisualizer object to render the collision tests pe...
void add_collider(const NodePath &collider, CollisionHandler *handler)
Adds a new CollisionNode, representing an object that will be tested for collisions into other object...
get_num_colliders
Returns the number of CollisionNodes that have been added to the traverser via add_collider().
void hide_collisions()
Undoes the effect of a previous call to show_collisions().
void traverse(const NodePath &root)
Perform the traversal.
A node that holds Geom objects, renderable pieces of geometry.
Definition: geomNode.h:34
get_num_geoms
Returns the number of geoms in the node.
Definition: geomNode.h:71
get_default_collide_mask
Returns the default into_collide_mask assigned to new GeomNodes.
Definition: geomNode.h:92
This is an abstract base class for a family of classes that represent the fundamental geometry primit...
Definition: geomPrimitive.h:56
get_num_vertices
Returns the number of indices used by all the primitives in this object.
Definition: geomPrimitive.h:99
int get_first_vertex() const
Returns the first vertex number referenced by the primitive.
Definition: geomPrimitive.I:98
This defines the actual numeric vertex data stored in a Geom, in the structure defined by a particula...
This object provides a high-level interface for quickly reading a sequence of numeric values from a v...
A container for geometry primitives.
Definition: geom.h:54
get_primitive_type
Returns the fundamental primitive type that is common to all GeomPrimitives added within the Geom.
Definition: geom.h:74
This is another abstract class, for a general class of bounding volumes that actually enclose points ...
int contains(const GeometricBoundingVolume *vol) const
Returns the appropriate set of IntersectionFlags to indicate the amount of intersection with the indi...
bool around(const GeometricBoundingVolume **first, const GeometricBoundingVolume **last)
Resets the volume to enclose only the volumes indicated.
A Level-of-Detail node.
Definition: lodNode.h:28
A base class for all things which can have a name.
Definition: namable.h:26
NodePath is the fundamental system for disambiguating instances, and also provides a higher-level int...
Definition: nodePath.h:159
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
bool is_empty() const
Returns true if the NodePath contains no nodes.
Definition: nodePath.I:188
PandaNode * node() const
Returns the referenced node of the path.
Definition: nodePath.I:227
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:600
A lightweight class that represents a single element that may be timed and/or counted via stats.
A lightweight class that can be used to automatically start and stop a PStatCollector around a sectio...
Definition: pStatTimer.h:30
PandaNode * get_child(size_t n) const
Returns the nth child of the node.
Definition: pandaNode.I:962
size_t get_num_children() const
Returns the number of children of the node.
Definition: pandaNode.I:953
A basic node of the scene graph or data graph.
Definition: pandaNode.h:65
virtual bool is_geom_node() const
A simple downcast check.
Definition: pandaNode.cxx:2062
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
virtual int get_visible_child() const
Returns the index number of the currently visible child of this node.
Definition: pandaNode.cxx:451
get_into_collide_mask
Returns the "into" collide mask for this node.
Definition: pandaNode.h:264
get_child
Returns the nth child node of this node.
Definition: pandaNode.h:124
virtual bool is_lod_node() const
A simple downcast check.
Definition: pandaNode.cxx:2074
virtual bool is_collision_node() const
A simple downcast check.
Definition: pandaNode.cxx:2086
get_children
Returns an object that can be used to walk through the list of children of the node.
Definition: pandaNode.h:782
A thread; that is, a lightweight process.
Definition: thread.h:46
get_current_thread
Returns a pointer to the currently-executing Thread object.
Definition: thread.h:109
TypeHandle is the identifier used to differentiate C++ class types.
Definition: typeHandle.h:81
This is our own Panda specialization on the default STL vector.
Definition: pvector.h:42
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
std::ostream & indent(std::ostream &out, int indent_level)
A handy function for doing text formatting.
Definition: indent.cxx:20
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.