Panda3D
|
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 }