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