Panda3D
 All Classes Functions Variables Enumerations
sceneGraphReducer.cxx
00001 // Filename: SceneGraphReducer.cxx
00002 // Created by:  drose (14Mar02)
00003 //
00004 ////////////////////////////////////////////////////////////////////
00005 //
00006 // PANDA 3D SOFTWARE
00007 // Copyright (c) Carnegie Mellon University.  All rights reserved.
00008 //
00009 // All use of this software is subject to the terms of the revised BSD
00010 // license.  You should have received a copy of this license along
00011 // with this source code in a file named "LICENSE."
00012 //
00013 ////////////////////////////////////////////////////////////////////
00014 
00015 #include "sceneGraphReducer.h"
00016 #include "config_pgraph.h"
00017 #include "accumulatedAttribs.h"
00018 #include "boundingSphere.h"
00019 #include "modelNode.h"
00020 #include "pointerTo.h"
00021 #include "plist.h"
00022 #include "pmap.h"
00023 #include "geomNode.h"
00024 #include "config_gobj.h"
00025 #include "thread.h"
00026 
00027 PStatCollector SceneGraphReducer::_flatten_collector("*:Flatten:flatten");
00028 PStatCollector SceneGraphReducer::_apply_collector("*:Flatten:apply");
00029 PStatCollector SceneGraphReducer::_remove_column_collector("*:Flatten:remove column");
00030 PStatCollector SceneGraphReducer::_compatible_state_collector("*:Flatten:compatible colors");
00031 PStatCollector SceneGraphReducer::_collect_collector("*:Flatten:collect");
00032 PStatCollector SceneGraphReducer::_make_nonindexed_collector("*:Flatten:make nonindexed");
00033 PStatCollector SceneGraphReducer::_unify_collector("*:Flatten:unify");
00034 PStatCollector SceneGraphReducer::_remove_unused_collector("*:Flatten:remove unused vertices");
00035 PStatCollector SceneGraphReducer::_premunge_collector("*:Premunge");
00036 
00037 ////////////////////////////////////////////////////////////////////
00038 //     Function: SceneGraphReducer::set_gsg
00039 //       Access: Published
00040 //  Description: Specifies the particular GraphicsStateGuardian that
00041 //               this object will attempt to optimize to.  The GSG may
00042 //               specify parameters such as maximum number of vertices
00043 //               per vertex data, max number of vertices per
00044 //               primitive, and whether triangle strips are preferred.
00045 //               It also affects the types of vertex column data that
00046 //               is created by premunge().
00047 ////////////////////////////////////////////////////////////////////
00048 void SceneGraphReducer::
00049 set_gsg(GraphicsStateGuardianBase *gsg) {
00050   if (gsg != (GraphicsStateGuardianBase *)NULL) {
00051     _gsg = gsg;
00052   } else {
00053     _gsg = GraphicsStateGuardianBase::get_default_gsg();
00054   }
00055 
00056   int max_vertices = max_collect_vertices;
00057 
00058   if (_gsg != (GraphicsStateGuardianBase *)NULL) {
00059     max_vertices = min(max_vertices, _gsg->get_max_vertices_per_array());
00060   }
00061 
00062   _transformer.set_max_collect_vertices(max_vertices);
00063 }
00064 
00065 ////////////////////////////////////////////////////////////////////
00066 //     Function: SceneGraphReducer::clear_gsg
00067 //       Access: Published
00068 //  Description: Specifies that no particular GraphicsStateGuardian
00069 //               will be used to guide the optimization.  The
00070 //               SceneGraphReducer will instead use config variables
00071 //               such as max-collect-vertices and max-collect-indices.
00072 ////////////////////////////////////////////////////////////////////
00073 void SceneGraphReducer::
00074 clear_gsg() {
00075   _gsg = NULL;
00076   _transformer.set_max_collect_vertices(max_collect_vertices);
00077 }
00078 
00079 ////////////////////////////////////////////////////////////////////
00080 //     Function: SceneGraphReducer::flatten
00081 //       Access: Published
00082 //  Description: Simplifies the graph by removing unnecessary nodes
00083 //               and nodes.
00084 //
00085 //               In general, a node (and its parent node) is a
00086 //               candidate for removal if the node has no siblings and
00087 //               the node has no special properties.
00088 //
00089 //               If combine_siblings_bits is nonzero, some sibling
00090 //               nodes (according to the bits set in
00091 //               combine_siblings_bits) may also be collapsed into a
00092 //               single node.  This will further reduce scene graph
00093 //               complexity, sometimes substantially, at the cost of
00094 //               reduced spatial separation.
00095 //
00096 //               Returns the number of nodes removed from the graph.
00097 ////////////////////////////////////////////////////////////////////
00098 int SceneGraphReducer::
00099 flatten(PandaNode *root, int combine_siblings_bits) {
00100   nassertr(check_live_flatten(root), 0);
00101 
00102   PStatTimer timer(_flatten_collector);
00103   int num_total_nodes = 0;
00104   int num_pass_nodes;
00105 
00106   do {
00107     num_pass_nodes = 0;
00108 
00109     // Get a copy of the children list, so we don't have to worry
00110     // about self-modifications.
00111     PandaNode::Children cr = root->get_children();
00112 
00113     // Now visit each of the children in turn.
00114     int num_children = cr.get_num_children();
00115     for (int i = 0; i < num_children; i++) {
00116       PT(PandaNode) child_node = cr.get_child(i);
00117       num_pass_nodes += r_flatten(root, child_node, combine_siblings_bits);
00118     }
00119 
00120     if (combine_siblings_bits != 0 && 
00121         root->get_num_children() >= 2 && 
00122         root->safe_to_combine_children()) {
00123       num_pass_nodes += flatten_siblings(root, combine_siblings_bits);
00124     }
00125 
00126     num_total_nodes += num_pass_nodes;
00127 
00128     // If combine_siblings_bits has CS_recurse set, we should repeat
00129     // the above until we don't get any more benefit from flattening,
00130     // because each pass could convert cousins into siblings, which
00131     // may get flattened next pass.
00132   } while ((combine_siblings_bits & CS_recurse) != 0 && num_pass_nodes != 0);
00133 
00134   return num_total_nodes;
00135 }
00136 
00137 ////////////////////////////////////////////////////////////////////
00138 //     Function: SceneGraphReducer::remove_column
00139 //       Access: Published
00140 //  Description: Removes the indicated data column from any
00141 //               GeomVertexDatas found at the indicated root and
00142 //               below.  Returns the number of GeomNodes modified.
00143 ////////////////////////////////////////////////////////////////////
00144 int SceneGraphReducer::
00145 remove_column(PandaNode *root, const InternalName *column) {
00146   nassertr(check_live_flatten(root), 0);
00147 
00148   PStatTimer timer(_remove_column_collector);
00149   int count = r_remove_column(root, column, _transformer);
00150   _transformer.finish_apply();
00151   return count;
00152 }
00153 
00154 ////////////////////////////////////////////////////////////////////
00155 //     Function: SceneGraphReducer::make_compatible_state
00156 //       Access: Published
00157 //  Description: Searches for GeomNodes that contain multiple Geoms
00158 //               that differ only in their ColorAttribs.  If such a
00159 //               GeomNode is found, then all the colors are pushed
00160 //               down into the vertices.  This makes it feasible for
00161 //               the geoms to be unified later.
00162 ////////////////////////////////////////////////////////////////////
00163 int SceneGraphReducer::
00164 make_compatible_state(PandaNode *root) {
00165   nassertr(check_live_flatten(root), 0);
00166 
00167   PStatTimer timer(_compatible_state_collector);
00168   int count = r_make_compatible_state(root, _transformer);
00169   _transformer.finish_apply();
00170   return count;
00171 }
00172 
00173 ////////////////////////////////////////////////////////////////////
00174 //     Function: SceneGraphReducer::decompose
00175 //       Access: Published
00176 //  Description: Calls decompose() on every GeomNode at this level and
00177 //               below.
00178 //
00179 //               There is usually no reason to call this explicitly,
00180 //               since unify() will do this anyway if it needs to be
00181 //               done.  However, calling it ahead of time can make
00182 //               that future call to unify() run a little bit faster.
00183 //
00184 //               This operation has no effect if the config variable
00185 //               preserve-triangle-strips has been set true.
00186 ////////////////////////////////////////////////////////////////////
00187 void SceneGraphReducer::
00188 decompose(PandaNode *root) {
00189   nassertv(check_live_flatten(root));
00190 
00191   if (!preserve_triangle_strips) {
00192     PStatTimer timer(_unify_collector);
00193     r_decompose(root);
00194   }
00195 }
00196 
00197 ////////////////////////////////////////////////////////////////////
00198 //     Function: SceneGraphReducer::unify
00199 //       Access: Published
00200 //  Description: Calls unify() on every GeomNode at this level and
00201 //               below.  This attempts to reduce the total number of
00202 //               individual Geoms and GeomPrimitives by combining
00203 //               these objects wherever possible.  See
00204 //               GeomNode::unify().
00205 ////////////////////////////////////////////////////////////////////
00206 void SceneGraphReducer::
00207 unify(PandaNode *root, bool preserve_order) {
00208   nassertv(check_live_flatten(root));
00209   PStatTimer timer(_unify_collector);
00210 
00211   int max_indices = max_collect_indices;
00212   if (_gsg != (GraphicsStateGuardianBase *)NULL) {
00213     max_indices = min(max_indices, _gsg->get_max_vertices_per_primitive());
00214   }
00215   r_unify(root, max_indices, preserve_order);
00216 }
00217 
00218 ////////////////////////////////////////////////////////////////////
00219 //     Function: SceneGraphReducer::remove_unused_vertices
00220 //       Access: Published
00221 //  Description: Removes any vertices in GeomVertexDatas that are no
00222 //               longer used at this level and below.  This requires
00223 //               remapping vertex indices in all of the
00224 //               GeomPrimitives, to remove holes in the
00225 //               GeomVertexDatas.  It is normally not necessary to
00226 //               call this explicitly.
00227 ////////////////////////////////////////////////////////////////////
00228 void SceneGraphReducer::
00229 remove_unused_vertices(PandaNode *root) {
00230   nassertv(check_live_flatten(root));
00231   PStatTimer timer(_remove_unused_collector);
00232 
00233   r_register_vertices(root, _transformer);
00234   _transformer.finish_apply();
00235   Thread::consider_yield();
00236 }
00237 
00238 ////////////////////////////////////////////////////////////////////
00239 //     Function: SceneGraphReducer::check_live_flatten
00240 //       Access: Published
00241 //  Description: In a non-release build, returns false if the node is
00242 //               correctly not in a live scene graph.  (Calling
00243 //               flatten on a node that is part of a live scene graph,
00244 //               for instance, a node somewhere under render, can
00245 //               cause problems in a multithreaded environment.)
00246 //
00247 //               If allow_live_flatten is true, or in a release build,
00248 //               this always returns true.
00249 ////////////////////////////////////////////////////////////////////
00250 bool SceneGraphReducer::
00251 check_live_flatten(PandaNode *node) {
00252 #ifndef NDEBUG
00253   if (allow_live_flatten) {
00254     return true;
00255   }
00256 
00257   if (node->is_under_scene_root()) {
00258     return false;
00259   }
00260 
00261 #endif  // NDEBUG
00262   return true;
00263 }
00264 
00265 ////////////////////////////////////////////////////////////////////
00266 //     Function: SceneGraphReducer::r_apply_attribs
00267 //       Access: Protected
00268 //  Description: The recursive implementation of apply_attribs().
00269 ////////////////////////////////////////////////////////////////////
00270 void SceneGraphReducer::
00271 r_apply_attribs(PandaNode *node, const AccumulatedAttribs &attribs,
00272                 int attrib_types, GeomTransformer &transformer) {
00273   if (pgraph_cat.is_spam()) {
00274     pgraph_cat.spam()
00275       << "r_apply_attribs(" << *node << "), node's attribs are:\n";
00276     node->get_transform()->write(pgraph_cat.spam(false), 2);
00277     node->get_state()->write(pgraph_cat.spam(false), 2);
00278     node->get_effects()->write(pgraph_cat.spam(false), 2);
00279   }
00280 
00281   AccumulatedAttribs next_attribs(attribs);
00282   next_attribs.collect(node, attrib_types);
00283 
00284   if (pgraph_cat.is_spam()) {
00285     pgraph_cat.spam()
00286       << "Got attribs from " << *node << "\n"
00287       << "Accumulated attribs are:\n";
00288     next_attribs.write(pgraph_cat.spam(false), attrib_types, 2);
00289   }
00290 
00291   // Check to see if we can't propagate any of these attribs past
00292   // this node for some reason.
00293   if (!node->safe_to_flatten_below()) {
00294     if (pgraph_cat.is_spam()) {
00295       pgraph_cat.spam()
00296         << "Not applying further; " << *node
00297         << " doesn't allow flattening below itself.\n";
00298     }
00299     next_attribs.apply_to_node(node, attrib_types);
00300     return;
00301   }
00302 
00303   int apply_types = 0;
00304 
00305   const RenderEffects *effects = node->get_effects();
00306   if (!effects->safe_to_transform()) {
00307     if (pgraph_cat.is_spam()) {
00308       pgraph_cat.spam()
00309         << "Node " << *node
00310         << " contains a non-transformable effect; leaving transform here.\n";
00311     }
00312     next_attribs._transform = effects->prepare_flatten_transform(next_attribs._transform);
00313     apply_types |= TT_transform;
00314   }
00315   if (!node->safe_to_transform()) {
00316     if (pgraph_cat.is_spam()) {
00317       pgraph_cat.spam()
00318         << "Cannot safely transform nodes of type " << node->get_type()
00319         << "; leaving a transform here but carrying on otherwise.\n";
00320     }
00321     apply_types |= TT_transform;
00322   }
00323   apply_types |= node->get_unsafe_to_apply_attribs();
00324 
00325   // Also, check the children of this node.  If any of them indicates
00326   // it is not safe to modify its transform, we must drop our
00327   // transform here.
00328   int num_children = node->get_num_children();
00329   int i;
00330   if ((apply_types & TT_transform) == 0) {
00331     bool children_transform_friendly = true;
00332     for (i = 0; i < num_children && children_transform_friendly; i++) {
00333       PandaNode *child_node = node->get_child(i);
00334       children_transform_friendly = child_node->safe_to_modify_transform();
00335     }
00336 
00337     if (!children_transform_friendly) {
00338       if (pgraph_cat.is_spam()) {
00339         pgraph_cat.spam()
00340           << "Node " << *node
00341           << " has a child that cannot modify its transform; leaving transform here.\n";
00342       }
00343       apply_types |= TT_transform;
00344     }
00345   }
00346 
00347   // Directly store whatever attributes we must,
00348   next_attribs.apply_to_node(node, attrib_types & apply_types);
00349 
00350   // And apply the rest to the vertices.
00351   node->apply_attribs_to_vertices(next_attribs, attrib_types, transformer);
00352 
00353   // Do we need to copy any children to flatten instances?
00354   bool resist_copy = false;
00355   for (i = 0; i < num_children; i++) {
00356     PandaNode *child_node = node->get_child(i);
00357 
00358     if (child_node->get_num_parents() > 1) {
00359       if (!child_node->safe_to_flatten()) {
00360         if (pgraph_cat.is_spam()) {
00361           pgraph_cat.spam()
00362             << "Cannot duplicate nodes of type " << child_node->get_type()
00363             << ".\n";
00364         }
00365         resist_copy = true;
00366 
00367       } else {
00368         PT(PandaNode) new_node = child_node->dupe_for_flatten();
00369         if (new_node->get_type() != child_node->get_type()) {
00370           pgraph_cat.error()
00371             << "Don't know how to copy nodes of type "
00372             << child_node->get_type() << "\n";
00373 
00374           if (no_unsupported_copy) {
00375             nassertv(false);
00376           }
00377           resist_copy = true;
00378 
00379         } else {
00380           if (pgraph_cat.is_spam()) {
00381             pgraph_cat.spam()
00382               << "Duplicated " << *child_node << "\n";
00383           }
00384           
00385           new_node->copy_children(child_node);
00386           node->replace_child(child_node, new_node);
00387           child_node = new_node;
00388         }
00389       }
00390     }
00391   }
00392 
00393   if (resist_copy) {
00394     // If any of our children should have been copied but weren't, we
00395     // need to drop the state here before continuing.
00396     next_attribs.apply_to_node(node, attrib_types);
00397   }
00398 
00399   // Now it's safe to traverse through all of our children.
00400   nassertv(num_children == node->get_num_children());
00401   for (i = 0; i < num_children; i++) {
00402     PandaNode *child_node = node->get_child(i);
00403     r_apply_attribs(child_node, next_attribs, attrib_types, transformer);
00404   }
00405   Thread::consider_yield();
00406 }
00407 
00408 
00409 ////////////////////////////////////////////////////////////////////
00410 //     Function: SceneGraphReducer::r_flatten
00411 //       Access: Protected
00412 //  Description: The recursive implementation of flatten().
00413 ////////////////////////////////////////////////////////////////////
00414 int SceneGraphReducer::
00415 r_flatten(PandaNode *grandparent_node, PandaNode *parent_node,
00416           int combine_siblings_bits) {
00417   if (pgraph_cat.is_spam()) {
00418     pgraph_cat.spam()
00419       << "SceneGraphReducer::r_flatten(" << *grandparent_node << ", " 
00420       << *parent_node << ", " << hex << combine_siblings_bits << dec
00421       << ")\n";
00422   }
00423   int num_nodes = 0;
00424 
00425   if (!parent_node->safe_to_flatten_below()) {
00426     if (pgraph_cat.is_spam()) {
00427       pgraph_cat.spam()
00428         << "Not traversing further; " << *parent_node
00429         << " doesn't allow flattening below itself.\n";
00430     }
00431     
00432   } else {
00433     if ((combine_siblings_bits & CS_within_radius) != 0) {
00434       CPT(BoundingVolume) bv = parent_node->get_bounds();
00435       if (bv->is_of_type(BoundingSphere::get_class_type())) {
00436         const BoundingSphere *bs = DCAST(BoundingSphere, bv);
00437         if (pgraph_cat.is_spam()) {
00438           pgraph_cat.spam()
00439             << "considering radius of " << *parent_node
00440             << ": " << *bs << " vs. " << _combine_radius << "\n";
00441         }
00442         if (!bs->is_infinite() && (bs->is_empty() || bs->get_radius() <= _combine_radius)) {
00443           // This node fits within the specified radius; from here on
00444           // down, we will have CS_other set, instead of
00445           // CS_within_radius.
00446           if (pgraph_cat.is_spam()) {
00447             pgraph_cat.spam()
00448               << "node fits within radius; flattening tighter.\n";
00449           }
00450           combine_siblings_bits &= ~CS_within_radius;
00451           combine_siblings_bits |= (CS_geom_node | CS_other | CS_recurse);
00452         }
00453       }
00454     }
00455 
00456     // First, recurse on each of the children.
00457     {
00458       PandaNode::Children cr = parent_node->get_children();
00459       int num_children = cr.get_num_children();
00460       for (int i = 0; i < num_children; i++) {
00461         PT(PandaNode) child_node = cr.get_child(i);
00462         num_nodes += r_flatten(parent_node, child_node, combine_siblings_bits);
00463       }
00464     }
00465     
00466     // Now that the above loop has removed some children, the child
00467     // list saved above is no longer accurate, so hereafter we must
00468     // ask the node for its real child list.
00469     
00470     // If we have CS_recurse set, then we flatten siblings before
00471     // trying to flatten children.  Otherwise, we flatten children
00472     // first, and then flatten siblings, which avoids overly
00473     // enthusiastic flattening.
00474     if ((combine_siblings_bits & CS_recurse) != 0 && 
00475         parent_node->get_num_children() >= 2 &&
00476         parent_node->safe_to_combine_children()) {
00477       num_nodes += flatten_siblings(parent_node, combine_siblings_bits);
00478     }
00479 
00480     if (parent_node->get_num_children() == 1) {
00481       // If we now have exactly one child, consider flattening the node
00482       // out.
00483       PT(PandaNode) child_node = parent_node->get_child(0);
00484       int child_sort = parent_node->get_child_sort(0);
00485       
00486       if (consider_child(grandparent_node, parent_node, child_node)) {
00487         // Ok, do it.
00488         parent_node->remove_child(child_node);
00489         
00490         if (do_flatten_child(grandparent_node, parent_node, child_node)) {
00491           // Done!
00492           num_nodes++;
00493         } else {
00494           // Chicken out.
00495           parent_node->add_child(child_node, child_sort);
00496         }
00497       }
00498     }
00499 
00500     if ((combine_siblings_bits & CS_recurse) == 0 &&
00501         (combine_siblings_bits & ~CS_recurse) != 0 && 
00502         parent_node->get_num_children() >= 2 &&
00503         parent_node->safe_to_combine_children()) {
00504       num_nodes += flatten_siblings(parent_node, combine_siblings_bits);
00505     }
00506 
00507     // Finally, if any of our remaining children are plain PandaNodes
00508     // with no children, just remove them.
00509     if (parent_node->safe_to_combine_children()) {
00510       for (int i = parent_node->get_num_children() - 1; i >= 0; --i) {
00511         PandaNode *child_node = parent_node->get_child(i);
00512         if (child_node->is_exact_type(PandaNode::get_class_type()) &&
00513             child_node->get_num_children() == 0 &&
00514             child_node->get_transform()->is_identity() &&
00515             child_node->get_effects()->is_empty()) {
00516           parent_node->remove_child(child_node);
00517           ++num_nodes;
00518         }
00519       }
00520     }
00521   }
00522 
00523   return num_nodes;
00524 }
00525 
00526 class SortByState {
00527 public:
00528   INLINE bool
00529   operator () (const PandaNode *node1, const PandaNode *node2) const;
00530 };
00531 
00532 INLINE bool SortByState::
00533 operator () (const PandaNode *node1, const PandaNode *node2) const {
00534   if (node1->get_transform() != node2->get_transform()) {
00535     return node1->get_transform() < node2->get_transform();
00536   }
00537   if (node1->get_state() != node2->get_state()) {
00538     return node1->get_state() < node2->get_state();
00539   }
00540   if (node1->get_effects() != node2->get_effects()) {
00541     return node1->get_effects() < node2->get_effects();
00542   }
00543   if (node1->get_draw_control_mask() != node2->get_draw_control_mask()) {
00544     return node1->get_draw_control_mask() < node2->get_draw_control_mask();
00545   }
00546   if (node1->get_draw_show_mask() != node2->get_draw_show_mask()) {
00547     return node1->get_draw_show_mask() < node2->get_draw_show_mask();
00548   }
00549   int cmp = (node1->compare_tags(node2));
00550   if (cmp != 0) {
00551     return cmp < 0;
00552   }
00553 
00554   return 0;
00555 }
00556 
00557 
00558 ////////////////////////////////////////////////////////////////////
00559 //     Function: SceneGraphReducer::flatten_siblings
00560 //       Access: Protected
00561 //  Description: Attempts to collapse together any pairs of siblings
00562 //               of the indicated node that share the same properties.
00563 ////////////////////////////////////////////////////////////////////
00564 int SceneGraphReducer::
00565 flatten_siblings(PandaNode *parent_node, int combine_siblings_bits) {
00566   int num_nodes = 0;
00567 
00568   // First, collect the children into groups of nodes with common
00569   // properties.
00570   typedef plist< PT(PandaNode) > NodeList;
00571   typedef pmap<PandaNode *, NodeList, SortByState> Collected;
00572   Collected collected;
00573 
00574   {
00575     // Protect this within a local scope, so the Children member will
00576     // destruct and free the read pointer before we try to write to
00577     // these nodes.
00578     PandaNode::Children cr = parent_node->get_children();
00579     int num_children = cr.get_num_children();
00580     for (int i = 0; i < num_children; i++) {
00581       PandaNode *child_node = cr.get_child(i);
00582       bool safe_to_combine = child_node->safe_to_combine();
00583       if (safe_to_combine) {
00584         if (child_node->is_geom_node()) {
00585           safe_to_combine = (combine_siblings_bits & CS_geom_node) != 0;
00586         } else {
00587           safe_to_combine = (combine_siblings_bits & CS_other) != 0;
00588         }
00589       }
00590 
00591       if (safe_to_combine) {
00592         collected[child_node].push_back(child_node);
00593       }
00594     }
00595   }
00596 
00597   // Now visit each of those groups and try to collapse them together.
00598   // A O(n^2) operation, but presumably the number of nodes in each
00599   // group is small.  And if each node in the group can collapse with
00600   // any other node, it becomes a O(n) operation.
00601   Collected::iterator ci;
00602   for (ci = collected.begin(); ci != collected.end(); ++ci) {
00603     const RenderEffects *effects = (*ci).first->get_effects();
00604     if (effects->safe_to_combine()) {
00605       NodeList &nodes = (*ci).second;
00606 
00607       NodeList::iterator ai1;
00608       ai1 = nodes.begin();
00609       while (ai1 != nodes.end()) {
00610         NodeList::iterator ai1_hold = ai1;
00611         PandaNode *child1 = (*ai1);
00612         ++ai1;
00613         NodeList::iterator ai2 = ai1;
00614         while (ai2 != nodes.end()) {
00615           NodeList::iterator ai2_hold = ai2;
00616           PandaNode *child2 = (*ai2);
00617           ++ai2;
00618 
00619           if (consider_siblings(parent_node, child1, child2)) {
00620             PT(PandaNode) new_node = 
00621               do_flatten_siblings(parent_node, child1, child2);
00622             if (new_node != (PandaNode *)NULL) {
00623               // We successfully collapsed a node.
00624               (*ai1_hold) = new_node;
00625               nodes.erase(ai2_hold);
00626               ai1 = nodes.begin();
00627               ai2 = nodes.end();
00628               num_nodes++;
00629             }
00630           }
00631         }
00632       }
00633     }
00634   }
00635 
00636   return num_nodes;
00637 }
00638 
00639 ////////////////////////////////////////////////////////////////////
00640 //     Function: SceneGraphReducer::consider_child
00641 //       Access: Protected
00642 //  Description: Decides whether or not the indicated child node is a
00643 //               suitable candidate for removal.  Returns true if the
00644 //               node may be removed, false if it should be kept.
00645 ////////////////////////////////////////////////////////////////////
00646 bool SceneGraphReducer::
00647 consider_child(PandaNode *grandparent_node, PandaNode *parent_node, 
00648                PandaNode *child_node) {
00649   if (!parent_node->safe_to_combine() || !child_node->safe_to_combine()) {
00650     // One or both nodes cannot be safely combined with another node;
00651     // do nothing.
00652     return false;
00653   }
00654 
00655   if (parent_node->get_transform() != child_node->get_transform() ||
00656       parent_node->get_state() != child_node->get_state() ||
00657       parent_node->get_effects() != child_node->get_effects() ||
00658       parent_node->get_draw_control_mask() != child_node->get_draw_control_mask() ||
00659       parent_node->get_draw_show_mask() != child_node->get_draw_show_mask() ||
00660       parent_node->compare_tags(child_node) != 0) {
00661     // The two nodes have a different state; too bad.
00662     return false;
00663   }
00664 
00665   if (!parent_node->get_effects()->safe_to_combine()) {
00666     // The effects don't want to be combined.
00667     return false;
00668   }
00669 
00670   return true;
00671 }
00672 
00673 ////////////////////////////////////////////////////////////////////
00674 //     Function: SceneGraphReducer::consider_siblings
00675 //       Access: Protected
00676 //  Description: Decides whether or not the indicated sibling nodes
00677 //               should be collapsed into a single node or not.
00678 //               Returns true if the nodes may be collapsed, false if
00679 //               they should be kept distinct.
00680 ////////////////////////////////////////////////////////////////////
00681 bool SceneGraphReducer::
00682 consider_siblings(PandaNode *parent_node, PandaNode *child1,
00683                   PandaNode *child2) {
00684   // We don't have to worry about the states being different betweeen
00685   // child1 and child2, since the SortByState object already
00686   // guaranteed we only consider children that have the same state.
00687   return true;
00688 }
00689 
00690 ////////////////////////////////////////////////////////////////////
00691 //     Function: SceneGraphReducer::do_flatten_child
00692 //       Access: Protected
00693 //  Description: Collapses together the indicated parent node and
00694 //               child node and leaves the result attached to the
00695 //               grandparent.  The return value is true if the node is
00696 //               successfully collapsed, false if we chickened out.
00697 ////////////////////////////////////////////////////////////////////
00698 bool SceneGraphReducer::
00699 do_flatten_child(PandaNode *grandparent_node, PandaNode *parent_node, 
00700                  PandaNode *child_node) {
00701   if (pgraph_cat.is_spam()) {
00702     pgraph_cat.spam()
00703       << "Collapsing " << *parent_node << " and " << *child_node << "\n";
00704   }
00705 
00706   PT(PandaNode) new_parent = collapse_nodes(parent_node, child_node, false);
00707   if (new_parent == (PandaNode *)NULL) {
00708     if (pgraph_cat.is_spam()) {
00709       pgraph_cat.spam()
00710         << "Decided not to collapse " << *parent_node 
00711         << " and " << *child_node << "\n";
00712     }
00713     return false;
00714   }
00715 
00716   choose_name(new_parent, parent_node, child_node);
00717 
00718   new_parent->replace_node(child_node);
00719   new_parent->replace_node(parent_node);
00720 
00721   return true;
00722 }
00723 
00724 ////////////////////////////////////////////////////////////////////
00725 //     Function: SceneGraphReducer::do_flatten_siblings
00726 //       Access: Protected
00727 //  Description: Performs the work of collapsing two sibling nodes
00728 //               together into a single node, leaving the resulting
00729 //               node attached to the parent.
00730 //
00731 //               Returns a pointer to a PandaNode that reflects the
00732 //               combined node (which may be either of the source nodes,
00733 //               or a new node altogether) if the siblings are
00734 //               successfully collapsed, or NULL if we chickened out.
00735 ////////////////////////////////////////////////////////////////////
00736 PandaNode *SceneGraphReducer::
00737 do_flatten_siblings(PandaNode *parent_node, PandaNode *child1,
00738                     PandaNode *child2) {
00739   if (pgraph_cat.is_spam()) {
00740     pgraph_cat.spam()
00741       << "Collapsing " << *child1 << " and " << *child2 << "\n";
00742   }
00743 
00744   PT(PandaNode) new_child = collapse_nodes(child2, child1, true);
00745   if (new_child == (PandaNode *)NULL) {
00746     if (pgraph_cat.is_spam()) {
00747       pgraph_cat.spam()
00748         << "Decided not to collapse " << *child1 << " and " << *child2 << "\n";
00749     }
00750     return NULL;
00751   }
00752 
00753   choose_name(new_child, child2, child1);
00754 
00755   // Make sure the new child list has child1's children first,
00756   // followed by child2's children.
00757   child1->replace_node(child2);
00758   new_child->replace_node(child1);
00759 
00760   return new_child;
00761 }
00762 
00763 ////////////////////////////////////////////////////////////////////
00764 //     Function: SceneGraphReducer::collapse_nodes
00765 //       Access: Protected
00766 //  Description: Collapses the two nodes into a single node, if
00767 //               possible.  The 'siblings' flag is true if the two
00768 //               nodes are siblings nodes; otherwise, node1 is a
00769 //               parent of node2.  The return value is the resulting
00770 //               node, which may be either one of the source nodes, or
00771 //               a new node altogether, or it may be NULL to indicate
00772 //               that the collapse operation could not take place.
00773 ////////////////////////////////////////////////////////////////////
00774 PT(PandaNode) SceneGraphReducer::
00775 collapse_nodes(PandaNode *node1, PandaNode *node2, bool siblings) {
00776   PT(PandaNode) result = node2->combine_with(node1);
00777   if (result == NULL) {
00778     result = node1->combine_with(node2);
00779   }
00780   return result;
00781 }
00782 
00783 
00784 ////////////////////////////////////////////////////////////////////
00785 //     Function: SceneGraphReducer::choose_name
00786 //       Access: Protected
00787 //  Description: Chooses a suitable name for the collapsed node, based
00788 //               on the names of the two sources nodes.
00789 ////////////////////////////////////////////////////////////////////
00790 void SceneGraphReducer::
00791 choose_name(PandaNode *preserve, PandaNode *source1, PandaNode *source2) {
00792   string name;
00793   bool got_name = false;
00794 
00795   name = source1->get_name();
00796   got_name = !name.empty() || source1->preserve_name();
00797 
00798   if (source2->preserve_name() || !got_name) {
00799     name = source2->get_name();
00800     got_name = !name.empty() || source2->preserve_name();
00801   }
00802 
00803   if (got_name) {
00804     preserve->set_name(name);
00805   }
00806 }
00807 
00808 ////////////////////////////////////////////////////////////////////
00809 //     Function: SceneGraphReducer::r_remove_column
00810 //       Access: Private
00811 //  Description: The recursive implementation of remove_column().
00812 ////////////////////////////////////////////////////////////////////
00813 int SceneGraphReducer::
00814 r_remove_column(PandaNode *node, const InternalName *column,
00815                 GeomTransformer &transformer) {
00816   int num_changed = 0;
00817 
00818   if (node->is_geom_node()) {
00819     if (transformer.remove_column(DCAST(GeomNode, node), column)) {
00820       ++num_changed;
00821     }
00822   }
00823     
00824   PandaNode::Children children = node->get_children();
00825   int num_children = children.get_num_children();
00826   for (int i = 0; i < num_children; ++i) {
00827     num_changed +=
00828       r_remove_column(children.get_child(i), column, transformer);
00829   }
00830 
00831   return num_changed;
00832 }
00833 
00834 ////////////////////////////////////////////////////////////////////
00835 //     Function: SceneGraphReducer::r_make_compatible_state
00836 //       Access: Private
00837 //  Description: The recursive implementation of make_compatible_state().
00838 ////////////////////////////////////////////////////////////////////
00839 int SceneGraphReducer::
00840 r_make_compatible_state(PandaNode *node, GeomTransformer &transformer) {
00841   int num_changed = 0;
00842 
00843   if (node->is_geom_node()) {
00844     if (transformer.make_compatible_state(DCAST(GeomNode, node))) {
00845       ++num_changed;
00846     }
00847   }
00848   
00849   PandaNode::Children children = node->get_children();
00850   int num_children = children.get_num_children();
00851   for (int i = 0; i < num_children; ++i) {
00852     num_changed +=
00853       r_make_compatible_state(children.get_child(i), transformer);
00854   }
00855 
00856   return num_changed;
00857 }
00858 
00859 ////////////////////////////////////////////////////////////////////
00860 //     Function: SceneGraphReducer::r_collect_vertex_data
00861 //       Access: Private
00862 //  Description: The recursive implementation of
00863 //               collect_vertex_data().
00864 ////////////////////////////////////////////////////////////////////
00865 int SceneGraphReducer::
00866 r_collect_vertex_data(PandaNode *node, int collect_bits,
00867                       GeomTransformer &transformer, bool format_only) {
00868   int num_adjusted = 0;
00869 
00870   int this_node_bits = 0;
00871   if (node->is_of_type(ModelNode::get_class_type())) {
00872     this_node_bits |= CVD_model;
00873   }
00874   if (!node->get_transform()->is_identity()) {
00875     this_node_bits |= CVD_transform;
00876   }
00877   if (node->is_geom_node()) {
00878     this_node_bits |= CVD_one_node_only;
00879   }
00880 
00881   if ((collect_bits & this_node_bits) != 0) {
00882     // We need to start a unique collection here.
00883     GeomTransformer new_transformer(transformer);
00884 
00885     if (node->is_geom_node()) {
00886       // When we come to a geom node, collect.
00887       num_adjusted += new_transformer.collect_vertex_data(DCAST(GeomNode, node), collect_bits, format_only);
00888     }
00889 
00890     PandaNode::Children children = node->get_children();
00891     int num_children = children.get_num_children();
00892     for (int i = 0; i < num_children; ++i) {
00893       num_adjusted += 
00894         r_collect_vertex_data(children.get_child(i), collect_bits, new_transformer, format_only);
00895     }
00896 
00897     num_adjusted += new_transformer.finish_collect(format_only);
00898 
00899   } else {
00900     // Keep the same collection.
00901 
00902     if (node->is_geom_node()) {
00903       num_adjusted += transformer.collect_vertex_data(DCAST(GeomNode, node), collect_bits, format_only);
00904     }
00905     
00906     PandaNode::Children children = node->get_children();
00907     int num_children = children.get_num_children();
00908     for (int i = 0; i < num_children; ++i) {
00909       num_adjusted +=
00910         r_collect_vertex_data(children.get_child(i), collect_bits, transformer, format_only);
00911     }
00912   }
00913 
00914   Thread::consider_yield();
00915   return num_adjusted;
00916 }
00917 
00918 ////////////////////////////////////////////////////////////////////
00919 //     Function: SceneGraphReducer::r_make_nonindexed
00920 //       Access: Private
00921 //  Description: The recursive implementation of
00922 //               make_nonindexed().
00923 ////////////////////////////////////////////////////////////////////
00924 int SceneGraphReducer::
00925 r_make_nonindexed(PandaNode *node, int nonindexed_bits) {
00926   int num_changed = 0;
00927 
00928   if (node->is_geom_node()) {
00929     GeomNode *geom_node = DCAST(GeomNode, node);
00930     int num_geoms = geom_node->get_num_geoms();
00931     for (int i = 0; i < num_geoms; ++i) {
00932       const Geom *geom = geom_node->get_geom(i);
00933 
00934       // Check whether the geom is animated or dynamic, and skip it
00935       // if the user specified so.
00936       const GeomVertexData *data = geom->get_vertex_data();
00937       int this_geom_bits = 0;
00938       if (data->get_format()->get_animation().get_animation_type() !=
00939           Geom::AT_none) {
00940         this_geom_bits |= MN_avoid_animated;
00941       }
00942       if (data->get_usage_hint() != Geom::UH_static ||
00943           geom->get_usage_hint() != Geom::UH_static) {
00944         this_geom_bits |= MN_avoid_dynamic;
00945       }
00946       
00947       if ((nonindexed_bits & this_geom_bits) == 0) {
00948         // The geom meets the user's qualifications for making
00949         // nonindexed, so do it.
00950         Geom *mgeom = DCAST(Geom, geom_node->modify_geom(i));
00951         num_changed += mgeom->make_nonindexed((nonindexed_bits & MN_composite_only) != 0);
00952       }
00953     }
00954   }
00955 
00956   PandaNode::Children children = node->get_children();
00957   int num_children = children.get_num_children();
00958   for (int i = 0; i < num_children; ++i) {
00959     num_changed += 
00960       r_make_nonindexed(children.get_child(i), nonindexed_bits);
00961   }
00962     
00963   return num_changed;
00964 }
00965 
00966 ////////////////////////////////////////////////////////////////////
00967 //     Function: SceneGraphReducer::r_unify
00968 //       Access: Private
00969 //  Description: The recursive implementation of unify().
00970 ////////////////////////////////////////////////////////////////////
00971 void SceneGraphReducer::
00972 r_unify(PandaNode *node, int max_indices, bool preserve_order) {
00973   if (node->is_geom_node()) {
00974     GeomNode *geom_node = DCAST(GeomNode, node);
00975     geom_node->unify(max_indices, preserve_order);
00976   }
00977 
00978   PandaNode::Children children = node->get_children();
00979   int num_children = children.get_num_children();
00980   for (int i = 0; i < num_children; ++i) {
00981     r_unify(children.get_child(i), max_indices, preserve_order);
00982   }
00983   Thread::consider_yield();
00984 }
00985 
00986 ////////////////////////////////////////////////////////////////////
00987 //     Function: SceneGraphReducer::r_register_vertices
00988 //       Access: Private
00989 //  Description: Recursively calls
00990 //               GeomTransformer::register_vertices() on all GeomNodes
00991 //               at the indicated root and below.
00992 ////////////////////////////////////////////////////////////////////
00993 void SceneGraphReducer::
00994 r_register_vertices(PandaNode *node, GeomTransformer &transformer) {
00995   if (node->is_geom_node()) {
00996     GeomNode *geom_node = DCAST(GeomNode, node);
00997     transformer.register_vertices(geom_node, true);
00998   }
00999 
01000   PandaNode::Children children = node->get_children();
01001   int num_children = children.get_num_children();
01002   for (int i = 0; i < num_children; ++i) {
01003     r_register_vertices(children.get_child(i), transformer);
01004   }
01005 }
01006 
01007 ////////////////////////////////////////////////////////////////////
01008 //     Function: SceneGraphReducer::r_decompose
01009 //       Access: Private
01010 //  Description: The recursive implementation of decompose().
01011 ////////////////////////////////////////////////////////////////////
01012 void SceneGraphReducer::
01013 r_decompose(PandaNode *node) {
01014   if (node->is_geom_node()) {
01015     GeomNode *geom_node = DCAST(GeomNode, node);
01016     geom_node->decompose();
01017   }
01018 
01019   PandaNode::Children children = node->get_children();
01020   int num_children = children.get_num_children();
01021   for (int i = 0; i < num_children; ++i) {
01022     r_decompose(children.get_child(i));
01023   }
01024 }
01025 
01026 ////////////////////////////////////////////////////////////////////
01027 //     Function: SceneGraphReducer::r_premunge
01028 //       Access: Private
01029 //  Description: The recursive implementation of premunge().
01030 ////////////////////////////////////////////////////////////////////
01031 void SceneGraphReducer::
01032 r_premunge(PandaNode *node, const RenderState *state) {
01033   CPT(RenderState) next_state = state->compose(node->get_state());
01034 
01035   if (node->is_geom_node()) {
01036     GeomNode *geom_node = DCAST(GeomNode, node);
01037     geom_node->do_premunge(_gsg, next_state, _transformer);
01038   }
01039 
01040   int i;
01041   PandaNode::Children children = node->get_children();
01042   int num_children = children.get_num_children();
01043   for (i = 0; i < num_children; ++i) {
01044     r_premunge(children.get_child(i), next_state);
01045   }
01046 
01047   PandaNode::Stashed stashed = node->get_stashed();
01048   int num_stashed = stashed.get_num_stashed();
01049   for (i = 0; i < num_stashed; ++i) {
01050     r_premunge(stashed.get_stashed(i), next_state);
01051   }
01052 }
 All Classes Functions Variables Enumerations