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