Panda3D
sceneGraphReducer.cxx
1 // Filename: SceneGraphReducer.cxx
2 // Created by: drose (14Mar02)
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 "sceneGraphReducer.h"
16 #include "config_pgraph.h"
17 #include "accumulatedAttribs.h"
18 #include "boundingSphere.h"
19 #include "modelNode.h"
20 #include "pointerTo.h"
21 #include "plist.h"
22 #include "pmap.h"
23 #include "geomNode.h"
24 #include "config_gobj.h"
25 #include "thread.h"
26 
27 PStatCollector SceneGraphReducer::_flatten_collector("*:Flatten:flatten");
28 PStatCollector SceneGraphReducer::_apply_collector("*:Flatten:apply");
29 PStatCollector SceneGraphReducer::_remove_column_collector("*:Flatten:remove column");
30 PStatCollector SceneGraphReducer::_compatible_state_collector("*:Flatten:compatible colors");
31 PStatCollector SceneGraphReducer::_collect_collector("*:Flatten:collect");
32 PStatCollector SceneGraphReducer::_make_nonindexed_collector("*:Flatten:make nonindexed");
33 PStatCollector SceneGraphReducer::_unify_collector("*:Flatten:unify");
34 PStatCollector SceneGraphReducer::_remove_unused_collector("*:Flatten:remove unused vertices");
35 PStatCollector SceneGraphReducer::_premunge_collector("*:Premunge");
36 
37 ////////////////////////////////////////////////////////////////////
38 // Function: SceneGraphReducer::set_gsg
39 // Access: Published
40 // Description: Specifies the particular GraphicsStateGuardian that
41 // this object will attempt to optimize to. The GSG may
42 // specify parameters such as maximum number of vertices
43 // per vertex data, max number of vertices per
44 // primitive, and whether triangle strips are preferred.
45 // It also affects the types of vertex column data that
46 // is created by premunge().
47 ////////////////////////////////////////////////////////////////////
50  if (gsg != (GraphicsStateGuardianBase *)NULL) {
51  _gsg = gsg;
52  } else {
54  }
55 
56  int max_vertices = max_collect_vertices;
57 
58  if (_gsg != (GraphicsStateGuardianBase *)NULL) {
59  max_vertices = min(max_vertices, _gsg->get_max_vertices_per_array());
60  }
61 
62  _transformer.set_max_collect_vertices(max_vertices);
63 }
64 
65 ////////////////////////////////////////////////////////////////////
66 // Function: SceneGraphReducer::clear_gsg
67 // Access: Published
68 // Description: Specifies that no particular GraphicsStateGuardian
69 // will be used to guide the optimization. The
70 // SceneGraphReducer will instead use config variables
71 // such as max-collect-vertices and max-collect-indices.
72 ////////////////////////////////////////////////////////////////////
75  _gsg = NULL;
76  _transformer.set_max_collect_vertices(max_collect_vertices);
77 }
78 
79 ////////////////////////////////////////////////////////////////////
80 // Function: SceneGraphReducer::flatten
81 // Access: Published
82 // Description: Simplifies the graph by removing unnecessary nodes
83 // and nodes.
84 //
85 // In general, a node (and its parent node) is a
86 // candidate for removal if the node has no siblings and
87 // the node has no special properties.
88 //
89 // If combine_siblings_bits is nonzero, some sibling
90 // nodes (according to the bits set in
91 // combine_siblings_bits) may also be collapsed into a
92 // single node. This will further reduce scene graph
93 // complexity, sometimes substantially, at the cost of
94 // reduced spatial separation.
95 //
96 // Returns the number of nodes removed from the graph.
97 ////////////////////////////////////////////////////////////////////
99 flatten(PandaNode *root, int combine_siblings_bits) {
100  nassertr(check_live_flatten(root), 0);
101 
102  PStatTimer timer(_flatten_collector);
103  int num_total_nodes = 0;
104  int num_pass_nodes;
105 
106  do {
107  num_pass_nodes = 0;
108 
109  // Get a copy of the children list, so we don't have to worry
110  // about self-modifications.
111  PandaNode::Children cr = root->get_children();
112 
113  // Now visit each of the children in turn.
114  int num_children = cr.get_num_children();
115  for (int i = 0; i < num_children; i++) {
116  PT(PandaNode) child_node = cr.get_child(i);
117  num_pass_nodes += r_flatten(root, child_node, combine_siblings_bits);
118  }
119 
120  if (combine_siblings_bits != 0 &&
121  root->get_num_children() >= 2 &&
122  root->safe_to_combine_children()) {
123  num_pass_nodes += flatten_siblings(root, combine_siblings_bits);
124  }
125 
126  num_total_nodes += num_pass_nodes;
127 
128  // If combine_siblings_bits has CS_recurse set, we should repeat
129  // the above until we don't get any more benefit from flattening,
130  // because each pass could convert cousins into siblings, which
131  // may get flattened next pass.
132  } while ((combine_siblings_bits & CS_recurse) != 0 && num_pass_nodes != 0);
133 
134  return num_total_nodes;
135 }
136 
137 ////////////////////////////////////////////////////////////////////
138 // Function: SceneGraphReducer::remove_column
139 // Access: Published
140 // Description: Removes the indicated data column from any
141 // GeomVertexDatas found at the indicated root and
142 // below. Returns the number of GeomNodes modified.
143 ////////////////////////////////////////////////////////////////////
145 remove_column(PandaNode *root, const InternalName *column) {
146  nassertr(check_live_flatten(root), 0);
147 
148  PStatTimer timer(_remove_column_collector);
149  int count = r_remove_column(root, column, _transformer);
150  _transformer.finish_apply();
151  return count;
152 }
153 
154 ////////////////////////////////////////////////////////////////////
155 // Function: SceneGraphReducer::make_compatible_state
156 // Access: Published
157 // Description: Searches for GeomNodes that contain multiple Geoms
158 // that differ only in their ColorAttribs. If such a
159 // GeomNode is found, then all the colors are pushed
160 // down into the vertices. This makes it feasible for
161 // the geoms to be unified later.
162 ////////////////////////////////////////////////////////////////////
165  nassertr(check_live_flatten(root), 0);
166 
167  PStatTimer timer(_compatible_state_collector);
168  int count = r_make_compatible_state(root, _transformer);
169  _transformer.finish_apply();
170  return count;
171 }
172 
173 ////////////////////////////////////////////////////////////////////
174 // Function: SceneGraphReducer::decompose
175 // Access: Published
176 // Description: Calls decompose() on every GeomNode at this level and
177 // below.
178 //
179 // There is usually no reason to call this explicitly,
180 // since unify() will do this anyway if it needs to be
181 // done. However, calling it ahead of time can make
182 // that future call to unify() run a little bit faster.
183 //
184 // This operation has no effect if the config variable
185 // preserve-triangle-strips has been set true.
186 ////////////////////////////////////////////////////////////////////
189  nassertv(check_live_flatten(root));
190 
191  if (!preserve_triangle_strips) {
192  PStatTimer timer(_unify_collector);
193  r_decompose(root);
194  }
195 }
196 
197 ////////////////////////////////////////////////////////////////////
198 // Function: SceneGraphReducer::unify
199 // Access: Published
200 // Description: Calls unify() on every GeomNode at this level and
201 // below. This attempts to reduce the total number of
202 // individual Geoms and GeomPrimitives by combining
203 // these objects wherever possible. See
204 // GeomNode::unify().
205 ////////////////////////////////////////////////////////////////////
207 unify(PandaNode *root, bool preserve_order) {
208  nassertv(check_live_flatten(root));
209  PStatTimer timer(_unify_collector);
210 
211  int max_indices = max_collect_indices;
212  if (_gsg != (GraphicsStateGuardianBase *)NULL) {
213  max_indices = min(max_indices, _gsg->get_max_vertices_per_primitive());
214  }
215  r_unify(root, max_indices, preserve_order);
216 }
217 
218 ////////////////////////////////////////////////////////////////////
219 // Function: SceneGraphReducer::remove_unused_vertices
220 // Access: Published
221 // Description: Removes any vertices in GeomVertexDatas that are no
222 // longer used at this level and below. This requires
223 // remapping vertex indices in all of the
224 // GeomPrimitives, to remove holes in the
225 // GeomVertexDatas. It is normally not necessary to
226 // call this explicitly.
227 ////////////////////////////////////////////////////////////////////
230  nassertv(check_live_flatten(root));
231  PStatTimer timer(_remove_unused_collector);
232 
233  r_register_vertices(root, _transformer);
234  _transformer.finish_apply();
236 }
237 
238 ////////////////////////////////////////////////////////////////////
239 // Function: SceneGraphReducer::check_live_flatten
240 // Access: Published
241 // Description: In a non-release build, returns false if the node is
242 // correctly not in a live scene graph. (Calling
243 // flatten on a node that is part of a live scene graph,
244 // for instance, a node somewhere under render, can
245 // cause problems in a multithreaded environment.)
246 //
247 // If allow_live_flatten is true, or in a release build,
248 // this always returns true.
249 ////////////////////////////////////////////////////////////////////
252 #ifndef NDEBUG
253  if (allow_live_flatten) {
254  return true;
255  }
256 
257  if (node->is_under_scene_root()) {
258  return false;
259  }
260 
261 #endif // NDEBUG
262  return true;
263 }
264 
265 ////////////////////////////////////////////////////////////////////
266 // Function: SceneGraphReducer::r_apply_attribs
267 // Access: Protected
268 // Description: The recursive implementation of apply_attribs().
269 ////////////////////////////////////////////////////////////////////
270 void SceneGraphReducer::
271 r_apply_attribs(PandaNode *node, const AccumulatedAttribs &attribs,
272  int attrib_types, GeomTransformer &transformer) {
273  if (pgraph_cat.is_spam()) {
274  pgraph_cat.spam()
275  << "r_apply_attribs(" << *node << "), node's attribs are:\n";
276  node->get_transform()->write(pgraph_cat.spam(false), 2);
277  node->get_state()->write(pgraph_cat.spam(false), 2);
278  node->get_effects()->write(pgraph_cat.spam(false), 2);
279  }
280 
281  AccumulatedAttribs next_attribs(attribs);
282  next_attribs.collect(node, attrib_types);
283 
284  if (pgraph_cat.is_spam()) {
285  pgraph_cat.spam()
286  << "Got attribs from " << *node << "\n"
287  << "Accumulated attribs are:\n";
288  next_attribs.write(pgraph_cat.spam(false), attrib_types, 2);
289  }
290 
291  // Check to see if we can't propagate any of these attribs past
292  // this node for some reason.
293  if (!node->safe_to_flatten_below()) {
294  if (pgraph_cat.is_spam()) {
295  pgraph_cat.spam()
296  << "Not applying further; " << *node
297  << " doesn't allow flattening below itself.\n";
298  }
299  next_attribs.apply_to_node(node, attrib_types);
300  return;
301  }
302 
303  int apply_types = 0;
304 
305  const RenderEffects *effects = node->get_effects();
306  if (!effects->safe_to_transform()) {
307  if (pgraph_cat.is_spam()) {
308  pgraph_cat.spam()
309  << "Node " << *node
310  << " contains a non-transformable effect; leaving transform here.\n";
311  }
312  next_attribs._transform = effects->prepare_flatten_transform(next_attribs._transform);
313  apply_types |= TT_transform;
314  }
315  if (!node->safe_to_transform()) {
316  if (pgraph_cat.is_spam()) {
317  pgraph_cat.spam()
318  << "Cannot safely transform nodes of type " << node->get_type()
319  << "; leaving a transform here but carrying on otherwise.\n";
320  }
321  apply_types |= TT_transform;
322  }
323  apply_types |= node->get_unsafe_to_apply_attribs();
324 
325  // Also, check the children of this node. If any of them indicates
326  // it is not safe to modify its transform, we must drop our
327  // transform here.
328  int num_children = node->get_num_children();
329  int i;
330  if ((apply_types & TT_transform) == 0) {
331  bool children_transform_friendly = true;
332  for (i = 0; i < num_children && children_transform_friendly; i++) {
333  PandaNode *child_node = node->get_child(i);
334  children_transform_friendly = child_node->safe_to_modify_transform();
335  }
336 
337  if (!children_transform_friendly) {
338  if (pgraph_cat.is_spam()) {
339  pgraph_cat.spam()
340  << "Node " << *node
341  << " has a child that cannot modify its transform; leaving transform here.\n";
342  }
343  apply_types |= TT_transform;
344  }
345  }
346 
347  // Directly store whatever attributes we must,
348  next_attribs.apply_to_node(node, attrib_types & apply_types);
349 
350  // And apply the rest to the vertices.
351  node->apply_attribs_to_vertices(next_attribs, attrib_types, transformer);
352 
353  // Do we need to copy any children to flatten instances?
354  bool resist_copy = false;
355  for (i = 0; i < num_children; i++) {
356  PandaNode *child_node = node->get_child(i);
357 
358  if (child_node->get_num_parents() > 1) {
359  if (!child_node->safe_to_flatten()) {
360  if (pgraph_cat.is_spam()) {
361  pgraph_cat.spam()
362  << "Cannot duplicate nodes of type " << child_node->get_type()
363  << ".\n";
364  }
365  resist_copy = true;
366 
367  } else {
368  PT(PandaNode) new_node = child_node->dupe_for_flatten();
369  if (new_node->get_type() != child_node->get_type()) {
370  pgraph_cat.error()
371  << "Don't know how to copy nodes of type "
372  << child_node->get_type() << "\n";
373 
374  if (no_unsupported_copy) {
375  nassertv(false);
376  }
377  resist_copy = true;
378 
379  } else {
380  if (pgraph_cat.is_spam()) {
381  pgraph_cat.spam()
382  << "Duplicated " << *child_node << "\n";
383  }
384 
385  new_node->copy_children(child_node);
386  node->replace_child(child_node, new_node);
387  child_node = new_node;
388  }
389  }
390  }
391  }
392 
393  if (resist_copy) {
394  // If any of our children should have been copied but weren't, we
395  // need to drop the state here before continuing.
396  next_attribs.apply_to_node(node, attrib_types);
397  }
398 
399  // Now it's safe to traverse through all of our children.
400  nassertv(num_children == node->get_num_children());
401  for (i = 0; i < num_children; i++) {
402  PandaNode *child_node = node->get_child(i);
403  r_apply_attribs(child_node, next_attribs, attrib_types, transformer);
404  }
406 }
407 
408 
409 ////////////////////////////////////////////////////////////////////
410 // Function: SceneGraphReducer::r_flatten
411 // Access: Protected
412 // Description: The recursive implementation of flatten().
413 ////////////////////////////////////////////////////////////////////
414 int SceneGraphReducer::
415 r_flatten(PandaNode *grandparent_node, PandaNode *parent_node,
416  int combine_siblings_bits) {
417  if (pgraph_cat.is_spam()) {
418  pgraph_cat.spam()
419  << "SceneGraphReducer::r_flatten(" << *grandparent_node << ", "
420  << *parent_node << ", " << hex << combine_siblings_bits << dec
421  << ")\n";
422  }
423 
424  if ((combine_siblings_bits & (CS_geom_node | CS_other | CS_recurse)) != 0) {
425  // Unset CS_within_radius, since we're going to flatten everything
426  // anyway. This avoids needlessly calculating the bounding volume.
427  combine_siblings_bits &= ~CS_within_radius;
428  }
429 
430  int num_nodes = 0;
431 
432  if (!parent_node->safe_to_flatten_below()) {
433  if (pgraph_cat.is_spam()) {
434  pgraph_cat.spam()
435  << "Not traversing further; " << *parent_node
436  << " doesn't allow flattening below itself.\n";
437  }
438 
439  } else {
440  if ((combine_siblings_bits & CS_within_radius) != 0) {
441  CPT(BoundingVolume) bv = parent_node->get_bounds();
442  if (bv->is_of_type(BoundingSphere::get_class_type())) {
443  const BoundingSphere *bs = DCAST(BoundingSphere, bv);
444  if (pgraph_cat.is_spam()) {
445  pgraph_cat.spam()
446  << "considering radius of " << *parent_node
447  << ": " << *bs << " vs. " << _combine_radius << "\n";
448  }
449  if (!bs->is_infinite() && (bs->is_empty() || bs->get_radius() <= _combine_radius)) {
450  // This node fits within the specified radius; from here on
451  // down, we will have CS_other set, instead of
452  // CS_within_radius.
453  if (pgraph_cat.is_spam()) {
454  pgraph_cat.spam()
455  << "node fits within radius; flattening tighter.\n";
456  }
457  combine_siblings_bits &= ~CS_within_radius;
458  combine_siblings_bits |= (CS_geom_node | CS_other | CS_recurse);
459  }
460  }
461  }
462 
463  // First, recurse on each of the children.
464  {
465  PandaNode::Children cr = parent_node->get_children();
466  int num_children = cr.get_num_children();
467  for (int i = 0; i < num_children; i++) {
468  PT(PandaNode) child_node = cr.get_child(i);
469  num_nodes += r_flatten(parent_node, child_node, combine_siblings_bits);
470  }
471  }
472 
473  // Now that the above loop has removed some children, the child
474  // list saved above is no longer accurate, so hereafter we must
475  // ask the node for its real child list.
476 
477  // If we have CS_recurse set, then we flatten siblings before
478  // trying to flatten children. Otherwise, we flatten children
479  // first, and then flatten siblings, which avoids overly
480  // enthusiastic flattening.
481  if ((combine_siblings_bits & CS_recurse) != 0 &&
482  parent_node->get_num_children() >= 2 &&
483  parent_node->safe_to_combine_children()) {
484  num_nodes += flatten_siblings(parent_node, combine_siblings_bits);
485  }
486 
487  if (parent_node->get_num_children() == 1) {
488  // If we now have exactly one child, consider flattening the node
489  // out.
490  PT(PandaNode) child_node = parent_node->get_child(0);
491  int child_sort = parent_node->get_child_sort(0);
492 
493  if (consider_child(grandparent_node, parent_node, child_node)) {
494  // Ok, do it.
495  parent_node->remove_child(child_node);
496 
497  if (do_flatten_child(grandparent_node, parent_node, child_node)) {
498  // Done!
499  num_nodes++;
500  } else {
501  // Chicken out.
502  parent_node->add_child(child_node, child_sort);
503  }
504  }
505  }
506 
507  if ((combine_siblings_bits & CS_recurse) == 0 &&
508  (combine_siblings_bits & ~CS_recurse) != 0 &&
509  parent_node->get_num_children() >= 2 &&
510  parent_node->safe_to_combine_children()) {
511  num_nodes += flatten_siblings(parent_node, combine_siblings_bits);
512  }
513 
514  // Finally, if any of our remaining children are plain PandaNodes
515  // with no children, just remove them.
516  if (parent_node->safe_to_combine_children()) {
517  for (int i = parent_node->get_num_children() - 1; i >= 0; --i) {
518  PandaNode *child_node = parent_node->get_child(i);
519  if (child_node->is_exact_type(PandaNode::get_class_type()) &&
520  child_node->get_num_children() == 0 &&
521  child_node->get_transform()->is_identity() &&
522  child_node->get_effects()->is_empty()) {
523  parent_node->remove_child(child_node);
524  ++num_nodes;
525  }
526  }
527  }
528  }
529 
530  return num_nodes;
531 }
532 
533 class SortByState {
534 public:
535  INLINE bool
536  operator () (const PandaNode *node1, const PandaNode *node2) const;
537 };
538 
539 INLINE bool SortByState::
540 operator () (const PandaNode *node1, const PandaNode *node2) const {
541  if (node1->get_transform() != node2->get_transform()) {
542  return node1->get_transform() < node2->get_transform();
543  }
544  if (node1->get_state() != node2->get_state()) {
545  return node1->get_state() < node2->get_state();
546  }
547  if (node1->get_effects() != node2->get_effects()) {
548  return node1->get_effects() < node2->get_effects();
549  }
550  if (node1->get_draw_control_mask() != node2->get_draw_control_mask()) {
551  return node1->get_draw_control_mask() < node2->get_draw_control_mask();
552  }
553  if (node1->get_draw_show_mask() != node2->get_draw_show_mask()) {
554  return node1->get_draw_show_mask() < node2->get_draw_show_mask();
555  }
556  int cmp = (node1->compare_tags(node2));
557  if (cmp != 0) {
558  return cmp < 0;
559  }
560 
561  return 0;
562 }
563 
564 
565 ////////////////////////////////////////////////////////////////////
566 // Function: SceneGraphReducer::flatten_siblings
567 // Access: Protected
568 // Description: Attempts to collapse together any pairs of siblings
569 // of the indicated node that share the same properties.
570 ////////////////////////////////////////////////////////////////////
571 int SceneGraphReducer::
572 flatten_siblings(PandaNode *parent_node, int combine_siblings_bits) {
573  int num_nodes = 0;
574 
575  // First, collect the children into groups of nodes with common
576  // properties.
577  typedef plist< PT(PandaNode) > NodeList;
579  Collected collected;
580 
581  {
582  // Protect this within a local scope, so the Children member will
583  // destruct and free the read pointer before we try to write to
584  // these nodes.
585  PandaNode::Children cr = parent_node->get_children();
586  int num_children = cr.get_num_children();
587  for (int i = 0; i < num_children; i++) {
588  PandaNode *child_node = cr.get_child(i);
589  bool safe_to_combine = child_node->safe_to_combine();
590  if (safe_to_combine) {
591  if (child_node->is_geom_node()) {
592  safe_to_combine = (combine_siblings_bits & CS_geom_node) != 0;
593  } else {
594  safe_to_combine = (combine_siblings_bits & CS_other) != 0;
595  }
596  }
597 
598  if (safe_to_combine) {
599  collected[child_node].push_back(child_node);
600  }
601  }
602  }
603 
604  // Now visit each of those groups and try to collapse them together.
605  // A O(n^2) operation, but presumably the number of nodes in each
606  // group is small. And if each node in the group can collapse with
607  // any other node, it becomes a O(n) operation.
608  Collected::iterator ci;
609  for (ci = collected.begin(); ci != collected.end(); ++ci) {
610  const RenderEffects *effects = (*ci).first->get_effects();
611  if (effects->safe_to_combine()) {
612  NodeList &nodes = (*ci).second;
613 
614  NodeList::iterator ai1;
615  ai1 = nodes.begin();
616  while (ai1 != nodes.end()) {
617  NodeList::iterator ai1_hold = ai1;
618  PandaNode *child1 = (*ai1);
619  ++ai1;
620  NodeList::iterator ai2 = ai1;
621  while (ai2 != nodes.end()) {
622  NodeList::iterator ai2_hold = ai2;
623  PandaNode *child2 = (*ai2);
624  ++ai2;
625 
626  if (consider_siblings(parent_node, child1, child2)) {
627  PT(PandaNode) new_node =
628  do_flatten_siblings(parent_node, child1, child2);
629  if (new_node != (PandaNode *)NULL) {
630  // We successfully collapsed a node.
631  (*ai1_hold) = new_node;
632  nodes.erase(ai2_hold);
633  ai1 = nodes.begin();
634  ai2 = nodes.end();
635  num_nodes++;
636  }
637  }
638  }
639  }
640  }
641  }
642 
643  return num_nodes;
644 }
645 
646 ////////////////////////////////////////////////////////////////////
647 // Function: SceneGraphReducer::consider_child
648 // Access: Protected
649 // Description: Decides whether or not the indicated child node is a
650 // suitable candidate for removal. Returns true if the
651 // node may be removed, false if it should be kept.
652 ////////////////////////////////////////////////////////////////////
653 bool SceneGraphReducer::
654 consider_child(PandaNode *grandparent_node, PandaNode *parent_node,
655  PandaNode *child_node) {
656  if (!parent_node->safe_to_combine() || !child_node->safe_to_combine()) {
657  // One or both nodes cannot be safely combined with another node;
658  // do nothing.
659  return false;
660  }
661 
662  if (parent_node->get_transform() != child_node->get_transform() ||
663  parent_node->get_state() != child_node->get_state() ||
664  parent_node->get_effects() != child_node->get_effects() ||
665  parent_node->get_draw_control_mask() != child_node->get_draw_control_mask() ||
666  parent_node->get_draw_show_mask() != child_node->get_draw_show_mask() ||
667  parent_node->compare_tags(child_node) != 0) {
668  // The two nodes have a different state; too bad.
669  return false;
670  }
671 
672  if (!parent_node->get_effects()->safe_to_combine()) {
673  // The effects don't want to be combined.
674  return false;
675  }
676 
677  return true;
678 }
679 
680 ////////////////////////////////////////////////////////////////////
681 // Function: SceneGraphReducer::consider_siblings
682 // Access: Protected
683 // Description: Decides whether or not the indicated sibling nodes
684 // should be collapsed into a single node or not.
685 // Returns true if the nodes may be collapsed, false if
686 // they should be kept distinct.
687 ////////////////////////////////////////////////////////////////////
688 bool SceneGraphReducer::
689 consider_siblings(PandaNode *parent_node, PandaNode *child1,
690  PandaNode *child2) {
691  // We don't have to worry about the states being different betweeen
692  // child1 and child2, since the SortByState object already
693  // guaranteed we only consider children that have the same state.
694  return true;
695 }
696 
697 ////////////////////////////////////////////////////////////////////
698 // Function: SceneGraphReducer::do_flatten_child
699 // Access: Protected
700 // Description: Collapses together the indicated parent node and
701 // child node and leaves the result attached to the
702 // grandparent. The return value is true if the node is
703 // successfully collapsed, false if we chickened out.
704 ////////////////////////////////////////////////////////////////////
705 bool SceneGraphReducer::
706 do_flatten_child(PandaNode *grandparent_node, PandaNode *parent_node,
707  PandaNode *child_node) {
708  if (pgraph_cat.is_spam()) {
709  pgraph_cat.spam()
710  << "Collapsing " << *parent_node << " and " << *child_node << "\n";
711  }
712 
713  PT(PandaNode) new_parent = collapse_nodes(parent_node, child_node, false);
714  if (new_parent == (PandaNode *)NULL) {
715  if (pgraph_cat.is_spam()) {
716  pgraph_cat.spam()
717  << "Decided not to collapse " << *parent_node
718  << " and " << *child_node << "\n";
719  }
720  return false;
721  }
722 
723  choose_name(new_parent, parent_node, child_node);
724 
725  new_parent->replace_node(child_node);
726  new_parent->replace_node(parent_node);
727 
728  return true;
729 }
730 
731 ////////////////////////////////////////////////////////////////////
732 // Function: SceneGraphReducer::do_flatten_siblings
733 // Access: Protected
734 // Description: Performs the work of collapsing two sibling nodes
735 // together into a single node, leaving the resulting
736 // node attached to the parent.
737 //
738 // Returns a pointer to a PandaNode that reflects the
739 // combined node (which may be either of the source nodes,
740 // or a new node altogether) if the siblings are
741 // successfully collapsed, or NULL if we chickened out.
742 ////////////////////////////////////////////////////////////////////
743 PandaNode *SceneGraphReducer::
744 do_flatten_siblings(PandaNode *parent_node, PandaNode *child1,
745  PandaNode *child2) {
746  if (pgraph_cat.is_spam()) {
747  pgraph_cat.spam()
748  << "Collapsing " << *child1 << " and " << *child2 << "\n";
749  }
750 
751  PT(PandaNode) new_child = collapse_nodes(child2, child1, true);
752  if (new_child == (PandaNode *)NULL) {
753  if (pgraph_cat.is_spam()) {
754  pgraph_cat.spam()
755  << "Decided not to collapse " << *child1 << " and " << *child2 << "\n";
756  }
757  return NULL;
758  }
759 
760  choose_name(new_child, child2, child1);
761 
762  // Make sure the new child list has child1's children first,
763  // followed by child2's children.
764  child1->replace_node(child2);
765  new_child->replace_node(child1);
766 
767  return new_child;
768 }
769 
770 ////////////////////////////////////////////////////////////////////
771 // Function: SceneGraphReducer::collapse_nodes
772 // Access: Protected
773 // Description: Collapses the two nodes into a single node, if
774 // possible. The 'siblings' flag is true if the two
775 // nodes are siblings nodes; otherwise, node1 is a
776 // parent of node2. The return value is the resulting
777 // node, which may be either one of the source nodes, or
778 // a new node altogether, or it may be NULL to indicate
779 // that the collapse operation could not take place.
780 ////////////////////////////////////////////////////////////////////
781 PT(PandaNode) SceneGraphReducer::
782 collapse_nodes(PandaNode *node1, PandaNode *node2, bool siblings) {
783  PT(PandaNode) result = node2->combine_with(node1);
784  if (result == NULL) {
785  result = node1->combine_with(node2);
786  }
787  return result;
788 }
789 
790 
791 ////////////////////////////////////////////////////////////////////
792 // Function: SceneGraphReducer::choose_name
793 // Access: Protected
794 // Description: Chooses a suitable name for the collapsed node, based
795 // on the names of the two sources nodes.
796 ////////////////////////////////////////////////////////////////////
797 void SceneGraphReducer::
798 choose_name(PandaNode *preserve, PandaNode *source1, PandaNode *source2) {
799  string name;
800  bool got_name = false;
801 
802  name = source1->get_name();
803  got_name = !name.empty() || source1->preserve_name();
804 
805  if (source2->preserve_name() || !got_name) {
806  name = source2->get_name();
807  got_name = !name.empty() || source2->preserve_name();
808  }
809 
810  if (got_name) {
811  preserve->set_name(name);
812  }
813 }
814 
815 ////////////////////////////////////////////////////////////////////
816 // Function: SceneGraphReducer::r_remove_column
817 // Access: Private
818 // Description: The recursive implementation of remove_column().
819 ////////////////////////////////////////////////////////////////////
820 int SceneGraphReducer::
821 r_remove_column(PandaNode *node, const InternalName *column,
822  GeomTransformer &transformer) {
823  int num_changed = 0;
824 
825  if (node->is_geom_node()) {
826  if (transformer.remove_column(DCAST(GeomNode, node), column)) {
827  ++num_changed;
828  }
829  }
830 
831  PandaNode::Children children = node->get_children();
832  int num_children = children.get_num_children();
833  for (int i = 0; i < num_children; ++i) {
834  num_changed +=
835  r_remove_column(children.get_child(i), column, transformer);
836  }
837 
838  return num_changed;
839 }
840 
841 ////////////////////////////////////////////////////////////////////
842 // Function: SceneGraphReducer::r_make_compatible_state
843 // Access: Private
844 // Description: The recursive implementation of make_compatible_state().
845 ////////////////////////////////////////////////////////////////////
846 int SceneGraphReducer::
847 r_make_compatible_state(PandaNode *node, GeomTransformer &transformer) {
848  int num_changed = 0;
849 
850  if (node->is_geom_node()) {
851  if (transformer.make_compatible_state(DCAST(GeomNode, node))) {
852  ++num_changed;
853  }
854  }
855 
856  PandaNode::Children children = node->get_children();
857  int num_children = children.get_num_children();
858  for (int i = 0; i < num_children; ++i) {
859  num_changed +=
860  r_make_compatible_state(children.get_child(i), transformer);
861  }
862 
863  return num_changed;
864 }
865 
866 ////////////////////////////////////////////////////////////////////
867 // Function: SceneGraphReducer::r_collect_vertex_data
868 // Access: Private
869 // Description: The recursive implementation of
870 // collect_vertex_data().
871 ////////////////////////////////////////////////////////////////////
872 int SceneGraphReducer::
873 r_collect_vertex_data(PandaNode *node, int collect_bits,
874  GeomTransformer &transformer, bool format_only) {
875  int num_adjusted = 0;
876 
877  int this_node_bits = 0;
878  if (node->is_of_type(ModelNode::get_class_type())) {
879  this_node_bits |= CVD_model;
880  }
881  if (!node->get_transform()->is_identity()) {
882  this_node_bits |= CVD_transform;
883  }
884  if (node->is_geom_node()) {
885  this_node_bits |= CVD_one_node_only;
886  }
887 
888  if ((collect_bits & this_node_bits) != 0) {
889  // We need to start a unique collection here.
890  GeomTransformer new_transformer(transformer);
891 
892  if (node->is_geom_node()) {
893  // When we come to a geom node, collect.
894  num_adjusted += new_transformer.collect_vertex_data(DCAST(GeomNode, node), collect_bits, format_only);
895  }
896 
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  num_adjusted +=
901  r_collect_vertex_data(children.get_child(i), collect_bits, new_transformer, format_only);
902  }
903 
904  num_adjusted += new_transformer.finish_collect(format_only);
905 
906  } else {
907  // Keep the same collection.
908 
909  if (node->is_geom_node()) {
910  num_adjusted += transformer.collect_vertex_data(DCAST(GeomNode, node), collect_bits, format_only);
911  }
912 
913  PandaNode::Children children = node->get_children();
914  int num_children = children.get_num_children();
915  for (int i = 0; i < num_children; ++i) {
916  num_adjusted +=
917  r_collect_vertex_data(children.get_child(i), collect_bits, transformer, format_only);
918  }
919  }
920 
922  return num_adjusted;
923 }
924 
925 ////////////////////////////////////////////////////////////////////
926 // Function: SceneGraphReducer::r_make_nonindexed
927 // Access: Private
928 // Description: The recursive implementation of
929 // make_nonindexed().
930 ////////////////////////////////////////////////////////////////////
931 int SceneGraphReducer::
932 r_make_nonindexed(PandaNode *node, int nonindexed_bits) {
933  int num_changed = 0;
934 
935  if (node->is_geom_node()) {
936  GeomNode *geom_node = DCAST(GeomNode, node);
937  int num_geoms = geom_node->get_num_geoms();
938  for (int i = 0; i < num_geoms; ++i) {
939  const Geom *geom = geom_node->get_geom(i);
940 
941  // Check whether the geom is animated or dynamic, and skip it
942  // if the user specified so.
943  const GeomVertexData *data = geom->get_vertex_data();
944  int this_geom_bits = 0;
945  if (data->get_format()->get_animation().get_animation_type() !=
946  Geom::AT_none) {
947  this_geom_bits |= MN_avoid_animated;
948  }
949  if (data->get_usage_hint() != Geom::UH_static ||
950  geom->get_usage_hint() != Geom::UH_static) {
951  this_geom_bits |= MN_avoid_dynamic;
952  }
953 
954  if ((nonindexed_bits & this_geom_bits) == 0) {
955  // The geom meets the user's qualifications for making
956  // nonindexed, so do it.
957  PT(Geom) mgeom = geom_node->modify_geom(i);
958  num_changed += mgeom->make_nonindexed((nonindexed_bits & MN_composite_only) != 0);
959  }
960  }
961  }
962 
963  PandaNode::Children children = node->get_children();
964  int num_children = children.get_num_children();
965  for (int i = 0; i < num_children; ++i) {
966  num_changed +=
967  r_make_nonindexed(children.get_child(i), nonindexed_bits);
968  }
969 
970  return num_changed;
971 }
972 
973 ////////////////////////////////////////////////////////////////////
974 // Function: SceneGraphReducer::r_unify
975 // Access: Private
976 // Description: The recursive implementation of unify().
977 ////////////////////////////////////////////////////////////////////
978 void SceneGraphReducer::
979 r_unify(PandaNode *node, int max_indices, bool preserve_order) {
980  if (node->is_geom_node()) {
981  GeomNode *geom_node = DCAST(GeomNode, node);
982  geom_node->unify(max_indices, preserve_order);
983  }
984 
985  PandaNode::Children children = node->get_children();
986  int num_children = children.get_num_children();
987  for (int i = 0; i < num_children; ++i) {
988  r_unify(children.get_child(i), max_indices, preserve_order);
989  }
991 }
992 
993 ////////////////////////////////////////////////////////////////////
994 // Function: SceneGraphReducer::r_register_vertices
995 // Access: Private
996 // Description: Recursively calls
997 // GeomTransformer::register_vertices() on all GeomNodes
998 // at the indicated root and below.
999 ////////////////////////////////////////////////////////////////////
1000 void SceneGraphReducer::
1001 r_register_vertices(PandaNode *node, GeomTransformer &transformer) {
1002  if (node->is_geom_node()) {
1003  GeomNode *geom_node = DCAST(GeomNode, node);
1004  transformer.register_vertices(geom_node, true);
1005  }
1006 
1007  PandaNode::Children children = node->get_children();
1008  int num_children = children.get_num_children();
1009  for (int i = 0; i < num_children; ++i) {
1010  r_register_vertices(children.get_child(i), transformer);
1011  }
1012 }
1013 
1014 ////////////////////////////////////////////////////////////////////
1015 // Function: SceneGraphReducer::r_decompose
1016 // Access: Private
1017 // Description: The recursive implementation of decompose().
1018 ////////////////////////////////////////////////////////////////////
1019 void SceneGraphReducer::
1020 r_decompose(PandaNode *node) {
1021  if (node->is_geom_node()) {
1022  GeomNode *geom_node = DCAST(GeomNode, node);
1023  geom_node->decompose();
1024  }
1025 
1026  PandaNode::Children children = node->get_children();
1027  int num_children = children.get_num_children();
1028  for (int i = 0; i < num_children; ++i) {
1029  r_decompose(children.get_child(i));
1030  }
1031 }
1032 
1033 ////////////////////////////////////////////////////////////////////
1034 // Function: SceneGraphReducer::r_premunge
1035 // Access: Private
1036 // Description: The recursive implementation of premunge().
1037 ////////////////////////////////////////////////////////////////////
1038 void SceneGraphReducer::
1039 r_premunge(PandaNode *node, const RenderState *state) {
1040  CPT(RenderState) next_state = state->compose(node->get_state());
1041 
1042  if (node->is_geom_node()) {
1043  GeomNode *geom_node = DCAST(GeomNode, node);
1044  geom_node->do_premunge(_gsg, next_state, _transformer);
1045  }
1046 
1047  int i;
1048  PandaNode::Children children = node->get_children();
1049  int num_children = children.get_num_children();
1050  for (i = 0; i < num_children; ++i) {
1051  r_premunge(children.get_child(i), next_state);
1052  }
1053 
1054  PandaNode::Stashed stashed = node->get_stashed();
1055  int num_stashed = stashed.get_num_stashed();
1056  for (i = 0; i < num_stashed; ++i) {
1057  r_premunge(stashed.get_stashed(i), next_state);
1058  }
1059 }
void remove_unused_vertices(PandaNode *root)
Removes any vertices in GeomVertexDatas that are no longer used at this level and below...
int get_num_children() const
Returns the number of children of the node.
Definition: pandaNode.I:1163
virtual bool preserve_name() const
Returns true if the node&#39;s name has extrinsic meaning and must be preserved across a flatten operatio...
Definition: pandaNode.cxx:319
A basic node of the scene graph or data graph.
Definition: pandaNode.h:72
void remove_child(int child_index, Thread *current_thread=Thread::get_current_thread())
Removes the nth child from the node.
Definition: pandaNode.cxx:697
bool is_exact_type(TypeHandle handle) const
Returns true if the current object is the indicated type exactly.
Definition: typedObject.I:74
This is our own Panda specialization on the default STL map.
Definition: pmap.h:52
int get_num_stashed(Thread *current_thread=Thread::get_current_thread()) const
Returns the number of stashed nodes this node has.
Definition: pandaNode.I:176
void register_vertices(Geom *geom, bool might_have_unused)
Records the association of the Geom with its GeomVertexData, for the purpose of later removing unused...
bool replace_child(PandaNode *orig_child, PandaNode *new_child, Thread *current_thread=Thread::get_current_thread())
Searches for the orig_child node in the node&#39;s list of children, and replaces it with the new_child i...
Definition: pandaNode.cxx:771
virtual void apply_attribs_to_vertices(const AccumulatedAttribs &attribs, int attrib_types, GeomTransformer &transformer)
Applies whatever attributes are specified in the AccumulatedAttribs object (and by the attrib_types b...
Definition: pandaNode.cxx:352
virtual bool safe_to_modify_transform() const
Returns true if it is safe to automatically adjust the transform on this kind of node.
Definition: pandaNode.cxx:266
virtual PandaNode * combine_with(PandaNode *other)
Collapses this PandaNode with the other PandaNode, if possible, and returns a pointer to the combined...
Definition: pandaNode.cxx:397
DrawMask get_draw_control_mask() const
Returns the set of bits in draw_show_mask that are considered meaningful.
Definition: pandaNode.I:559
int get_num_children(Thread *current_thread=Thread::get_current_thread()) const
Returns the number of child nodes this node has.
Definition: pandaNode.I:68
bool is_empty() const
Any kind of volume might be empty.
void collect(PandaNode *node, int attrib_types)
Collects the state and transform from the indicated node and adds it to the accumulator, removing it from the node.
UsageHint get_usage_hint() const
Returns the minimum (i.e.
Definition: geom.I:67
This defines a bounding sphere, consisting of a center and a radius.
bool is_infinite() const
The other side of the empty coin is an infinite volume.
bool safe_to_transform() const
Returns true if all of the effects in this set can safely be transformed, and therefore the complete ...
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 collect_vertex_data(Geom *geom, int collect_bits, bool format_only)
Collects together GeomVertexDatas from different geoms into one big (or several big) GeomVertexDatas...
virtual bool safe_to_combine_children() const
Returns true if it is generally safe to combine the children of this PandaNode with each other...
Definition: pandaNode.cxx:295
A lightweight class that can be used to automatically start and stop a PStatCollector around a sectio...
Definition: pStatTimer.h:34
This is our own Panda specialization on the default STL list.
Definition: plist.h:38
int get_num_geoms() const
Returns the number of geoms in the node.
Definition: geomNode.I:46
void decompose()
Calls decompose() on each Geom with the GeomNode.
Definition: geomNode.cxx:747
static void consider_yield()
Possibly suspends the current thread for the rest of the current epoch, if it has run for enough this...
Definition: thread.I:263
virtual bool safe_to_combine() const
Returns true if it is generally safe to combine this particular kind of PandaNode with other kinds of...
Definition: pandaNode.cxx:281
void clear_gsg()
Specifies that no particular GraphicsStateGuardian will be used to guide the optimization.
PandaNode * get_stashed(int n, Thread *current_thread=Thread::get_current_thread()) const
Returns the nth stashed child of this node.
Definition: pandaNode.I:191
void set_max_collect_vertices(int max_collect_vertices)
Specifies the maximum number of vertices that may be put into a single GeomVertexData as a result of ...
This is an abstract class for any volume in any sense which can be said to define the locality of ref...
void decompose(PandaNode *root)
Calls decompose() on every GeomNode at this level and below.
A lightweight class that represents a single element that may be timed and/or counted via stats...
DrawMask get_draw_show_mask() const
Returns the hide/show bits of this particular node.
Definition: pandaNode.I:571
int remove_column(PandaNode *root, const InternalName *column)
Removes the indicated data column from any GeomVertexDatas found at the indicated root and below...
void do_premunge(GraphicsStateGuardianBase *gsg, const RenderState *node_state, GeomTransformer &transformer)
Uses the indicated GSG to premunge the Geoms in this node to optimize them for eventual rendering...
Definition: geomNode.cxx:955
void set_gsg(GraphicsStateGuardianBase *gsg)
Specifies the particular GraphicsStateGuardian that this object will attempt to optimize to...
int finish_collect(bool format_only)
This should be called after a call to collect_vertex_data() to finalize the changes and apply them to...
int compare_tags(const PandaNode *other) const
Returns a number less than 0, 0, or greater than 0, to indicate the similarity of tags between this n...
Definition: pandaNode.cxx:1567
This class is used by the SceneGraphReducer to maintain and accumulate the set of attributes we have ...
void unify(PandaNode *root, bool preserve_order)
Calls unify() on every GeomNode at this level and below.
const GeomVertexFormat * get_format() const
Returns a pointer to the GeomVertexFormat structure that defines this data.
UsageHint get_usage_hint() const
Returns the usage hint that was passed to the constructor, and which will be passed to each array dat...
bool is_under_scene_root() const
Returns true if this particular node is in a live scene graph: that is, it is a child or descendent o...
Definition: pandaNode.cxx:2166
virtual PandaNode * dupe_for_flatten() const
This is similar to make_copy(), but it makes a copy for the specific purpose of flatten.
Definition: pandaNode.cxx:222
This defines the actual numeric vertex data stored in a Geom, in the structure defined by a particula...
static GraphicsStateGuardianBase * get_default_gsg()
Returns a pointer to the "default" GSG.
A container for geometry primitives.
Definition: geom.h:58
virtual bool safe_to_flatten_below() const
Returns true if a flatten operation may safely continue past this node, or false if nodes below this ...
Definition: pandaNode.cxx:307
int get_child_sort(int n, Thread *current_thread=Thread::get_current_thread()) const
Returns the sort index of the nth child node of this node (that is, the number that was passed to add...
Definition: pandaNode.I:97
virtual int get_unsafe_to_apply_attribs() const
Returns the union of all attributes from SceneGraphReducer::AttribTypes that may not safely be applie...
Definition: pandaNode.cxx:335
int flatten(PandaNode *root, int combine_siblings_bits)
Simplifies the graph by removing unnecessary nodes and nodes.
bool check_live_flatten(PandaNode *node)
In a non-release build, returns false if the node is correctly not in a live scene graph...
bool remove_column(Geom *geom, const InternalName *column)
Removes the named column from the vertex data in the Geom.
This represents a unique collection of RenderAttrib objects that correspond to a particular renderabl...
Definition: renderState.h:53
int get_num_parents(Thread *current_thread=Thread::get_current_thread()) const
Returns the number of parent nodes this node has.
Definition: pandaNode.I:26
void finish_apply()
Should be called after performing any operations–particularly PandaNode::apply_attribs_to_vertices()...
This is a base class for the GraphicsStateGuardian class, which is itself a base class for the variou...
void replace_node(PandaNode *other)
Inserts this node into the scene graph in place of the other one, and removes the other node...
Definition: pandaNode.cxx:1777
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
void unify(int max_indices, bool preserve_order)
Attempts to unify all of the Geoms contained within this node into a single Geom, or at least as few ...
Definition: geomNode.cxx:789
bool is_of_type(TypeHandle handle) const
Returns true if the current object is or derives from the indicated type.
Definition: typedObject.I:63
PandaNode * get_child(int n) const
Returns the nth child of the node.
Definition: pandaNode.I:1174
virtual bool safe_to_transform() const
Returns true if it is generally safe to transform this particular kind of PandaNode by calling the xf...
Definition: pandaNode.cxx:249
virtual bool is_geom_node() const
A simple downcast check.
Definition: pandaNode.cxx:2486
bool make_compatible_state(GeomNode *node)
Checks if the different geoms in the GeomNode have different RenderStates.
void copy_children(PandaNode *other, Thread *current_thread=Thread::get_current_thread())
Makes another instance of all the children of the other node, copying them to this node...
Definition: pandaNode.cxx:1076
void apply_to_node(PandaNode *node, int attrib_types)
Stores the indicated attributes in the node&#39;s transform and state information; does not attempt to ap...
This represents a unique collection of RenderEffect objects that correspond to a particular renderabl...
Definition: renderEffects.h:46
A node that holds Geom objects, renderable pieces of geometry.
Definition: geomNode.h:37
virtual bool safe_to_flatten() const
Returns true if it is generally safe to flatten out this particular kind of PandaNode by duplicating ...
Definition: pandaNode.cxx:237
int make_compatible_state(PandaNode *root)
Searches for GeomNodes that contain multiple Geoms that differ only in their ColorAttribs.
An object specifically designed to transform the vertices of a Geom without disturbing indexing or af...