00001 // Filename: eggBinMaker.cxx 00002 // Created by: drose (21Jan99) 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 "eggBinMaker.h" 00016 #include "eggGroupNode.h" 00017 #include "eggGroup.h" 00018 #include "eggBin.h" 00019 00020 #include "dcast.h" 00021 #include "pnotify.h" 00022 00023 TypeHandle EggBinMaker::_type_handle; 00024 00025 00026 //////////////////////////////////////////////////////////////////// 00027 // Function: EggBinMakerCompareNodes::Function operator 00028 // Access: Public 00029 // Description: Called by the SortedNodes set to put nodes into bin 00030 // order. Returns true if the first node falls into an 00031 // earlier bin than the second node, false otherwise. 00032 //////////////////////////////////////////////////////////////////// 00033 bool EggBinMakerCompareNodes:: 00034 operator ()(const EggNode *a, const EggNode *b) const { 00035 int bin_number_a = _ebm->get_bin_number(a); 00036 int bin_number_b = _ebm->get_bin_number(b); 00037 00038 if (bin_number_a != bin_number_b) { 00039 // If the two nodes return different bin numbers, then they 00040 // sort based on those numbers. 00041 return bin_number_a < bin_number_b; 00042 } 00043 00044 // The two nodes fell into the same bin number, so fall back on the 00045 // comparison function to see if they should be differentiated. 00046 return _ebm->sorts_less(bin_number_a, a, b); 00047 } 00048 00049 //////////////////////////////////////////////////////////////////// 00050 // Function: EggBinMaker::Constructor 00051 // Access: Public 00052 // Description: 00053 //////////////////////////////////////////////////////////////////// 00054 EggBinMaker:: 00055 EggBinMaker() { 00056 } 00057 00058 //////////////////////////////////////////////////////////////////// 00059 // Function: EggBinMaker::Destructor 00060 // Access: Public 00061 // Description: 00062 //////////////////////////////////////////////////////////////////// 00063 EggBinMaker:: 00064 ~EggBinMaker() { 00065 } 00066 00067 00068 //////////////////////////////////////////////////////////////////// 00069 // Function: EggBinMaker::make_bins 00070 // Access: Public 00071 // Description: The main entry point to EggBinMaker. Walks the egg 00072 // scene graph beginning at the indicated root node, and 00073 // moves all binnable nodes into EggBin objects. 00074 // Returns the number of EggBins created. 00075 //////////////////////////////////////////////////////////////////// 00076 int EggBinMaker:: 00077 make_bins(EggGroupNode *root_group) { 00078 _group_nodes.clear(); 00079 00080 collect_nodes(root_group); 00081 00082 int num_bins = 0; 00083 GroupNodes::const_iterator gi; 00084 for (gi = _group_nodes.begin(); gi != _group_nodes.end(); ++gi) { 00085 num_bins += get_bins_for_group(gi); 00086 } 00087 00088 return num_bins; 00089 } 00090 00091 //////////////////////////////////////////////////////////////////// 00092 // Function: EggBinMaker::prepare_node 00093 // Access: Public, Virtual 00094 // Description: May be overridden in derived classes to perform some 00095 // setup work as each node is encountered. This will be 00096 // called once for each node in the egg hierarchy. 00097 //////////////////////////////////////////////////////////////////// 00098 void EggBinMaker:: 00099 prepare_node(EggNode *) { 00100 } 00101 00102 //////////////////////////////////////////////////////////////////// 00103 // Function: EggBinMaker::sorts_less 00104 // Access: Public, Virtual 00105 // Description: May be overridden in derived classes to create 00106 // additional bins within a particular bin number, based 00107 // on some arbitrary property of nodes. This function 00108 // establishes an arbitrary but fixed ordering between 00109 // nodes; if two nodes do not sort to the same position, 00110 // different bins are created for each one (with the 00111 // same bin number on each bin). 00112 //////////////////////////////////////////////////////////////////// 00113 bool EggBinMaker:: 00114 sorts_less(int, const EggNode *, const EggNode *) { 00115 return false; 00116 } 00117 00118 //////////////////////////////////////////////////////////////////// 00119 // Function: EggBinMaker::collapse_group 00120 // Access: Public, Virtual 00121 // Description: May be overridden in derived classes to specify 00122 // whether a particular group node, apparently 00123 // redundant, may be safely collapsed out. 00124 //////////////////////////////////////////////////////////////////// 00125 bool EggBinMaker:: 00126 collapse_group(const EggGroup *, int) { 00127 return false; 00128 } 00129 00130 //////////////////////////////////////////////////////////////////// 00131 // Function: EggBinMaker::get_bin_name 00132 // Access: Public, Virtual 00133 // Description: May be overridden in derived classes to define a name 00134 // for each new bin, based on its bin number, and a 00135 // sample child. 00136 //////////////////////////////////////////////////////////////////// 00137 string EggBinMaker:: 00138 get_bin_name(int, const EggNode *) { 00139 return string(); 00140 } 00141 00142 //////////////////////////////////////////////////////////////////// 00143 // Function: EggBinMaker::make_bin 00144 // Access: Public, Virtual 00145 // Description: May be overridden in derived classes to construct a 00146 // new EggBin object (or some derived class, if needed), 00147 // and preload some initial data into as required. 00148 // 00149 // child is an arbitrary child of the bin, and 00150 // collapse_from is the group the bin is being collapsed 00151 // with, if any (implying collapse_group() returned 00152 // true), or NULL if not. 00153 //////////////////////////////////////////////////////////////////// 00154 PT(EggBin) EggBinMaker:: 00155 make_bin(int, const EggNode *, EggGroup *collapse_from) { 00156 if (collapse_from == (EggGroup *)NULL) { 00157 return new EggBin; 00158 } else { 00159 return new EggBin(*collapse_from); 00160 } 00161 } 00162 00163 //////////////////////////////////////////////////////////////////// 00164 // Function: EggBinMaker::collect_nodes 00165 // Access: Private 00166 // Description: Walks the egg scene graph, identifying nodes to be 00167 // binned and moving them from the scene graph into the 00168 // internal bin structure. 00169 //////////////////////////////////////////////////////////////////// 00170 void EggBinMaker:: 00171 collect_nodes(EggGroupNode *group) { 00172 // We have to play games with this next iterator, because we might 00173 // be destructively operating on the child list as we traverse it. 00174 EggGroupNode::iterator i, next; 00175 00176 bool first_in_group = true; 00177 GroupNodes::iterator gni = _group_nodes.end(); 00178 00179 i = group->begin(); 00180 next = i; 00181 while (i != group->end()) { 00182 EggNode *node = (*i); 00183 ++next; 00184 00185 prepare_node(node); 00186 00187 if (get_bin_number(node) != 0) { 00188 // Ok, here's a node to be binned. Add it to the appropriate 00189 // bin. 00190 if (first_in_group) { 00191 // If this is the first time this group has been encountered, 00192 // we need to create a new entry in _group_nodes for it. 00193 00194 pair<GroupNodes::iterator, bool> result; 00195 result = _group_nodes.insert 00196 (GroupNodes::value_type 00197 (group, SortedNodes(EggBinMakerCompareNodes(this)))); 00198 00199 nassertv(result.second); 00200 gni = result.first; 00201 first_in_group = false; 00202 } 00203 00204 // Add this node to the set of all nodes being binned for the 00205 // group. This also puts the nodes into bin order. 00206 nassertv(gni != _group_nodes.end()); 00207 (*gni).second.insert(node); 00208 00209 // And remove it from the scene graph. 00210 group->erase(i); 00211 } 00212 00213 if (node->is_of_type(EggGroupNode::get_class_type())) { 00214 // Recursively traverse. 00215 collect_nodes(DCAST(EggGroupNode, node)); 00216 } 00217 00218 i = next; 00219 } 00220 } 00221 00222 00223 //////////////////////////////////////////////////////////////////// 00224 // Function: EggBinMaker::get_bins_for_group 00225 // Access: Private 00226 // Description: Breaks the set of nodes for a given group up into 00227 // individual bins. 00228 //////////////////////////////////////////////////////////////////// 00229 int EggBinMaker:: 00230 get_bins_for_group(GroupNodes::const_iterator gi) { 00231 EggGroupNode *group = (*gi).first; 00232 const SortedNodes &nodes = (*gi).second; 00233 00234 // It shouldn't be possible for this to be empty. 00235 nassertr(!nodes.empty(), 0); 00236 00237 Bins bins; 00238 EggBinMakerCompareNodes cn(this); 00239 SortedNodes::const_iterator sni, last; 00240 sni = nodes.begin(); 00241 last = sni; 00242 00243 bins.push_back(Nodes()); 00244 bins.back().push_back(*sni); 00245 ++sni; 00246 while (sni != nodes.end()) { 00247 if (cn(*last, *sni)) { 00248 // Begin a new bin. 00249 bins.push_back(Nodes()); 00250 } 00251 bins.back().push_back(*sni); 00252 00253 last = sni; 00254 ++sni; 00255 } 00256 00257 make_bins_for_group(group, bins); 00258 return bins.size(); 00259 } 00260 00261 //////////////////////////////////////////////////////////////////// 00262 // Function: EggBinMaker::make_bins_for_group 00263 // Access: Private 00264 // Description: Creates the EggBin nodes indicated by the internal 00265 // bin structure for each group. 00266 //////////////////////////////////////////////////////////////////// 00267 void EggBinMaker:: 00268 make_bins_for_group(EggGroupNode *group, const Bins &bins) { 00269 // We shouldn't be able to get here if we have no bins! 00270 nassertv(!bins.empty()); 00271 00272 // If the group will have only one bin, and no other children, and 00273 // the group is not the root node (and it is not some funny 00274 // group-like node like a <Table>), maybe we should collapse the 00275 // group and its bin together. 00276 00277 bool collapse = false; 00278 00279 if (group->empty() && 00280 bins.size() == 1 && 00281 group->get_parent() != NULL && 00282 group->is_of_type(EggGroup::get_class_type())) { 00283 const Nodes &nodes = bins.front(); 00284 nassertv(!nodes.empty()); 00285 int bin_number = get_bin_number(nodes.front()); 00286 collapse = collapse_group(DCAST(EggGroup, group), bin_number); 00287 } 00288 00289 if (collapse) { 00290 const Nodes &nodes = bins.front(); 00291 nassertv(!nodes.empty()); 00292 int bin_number = get_bin_number(nodes.front()); 00293 PT(EggBin) bin = make_bin(bin_number, nodes.front(), DCAST(EggGroup, group)); 00294 setup_bin(bin, nodes); 00295 00296 EggGroupNode *parent = group->get_parent(); 00297 parent->remove_child(group); 00298 parent->add_child(bin); 00299 00300 } else { 00301 Bins::const_iterator bi; 00302 for (bi = bins.begin(); bi != bins.end(); ++bi) { 00303 const Nodes &nodes = (*bi); 00304 nassertv(!nodes.empty()); 00305 int bin_number = get_bin_number(nodes.front()); 00306 PT(EggBin) bin = make_bin(bin_number, nodes.front(), NULL); 00307 setup_bin(bin, nodes); 00308 00309 group->add_child(bin); 00310 } 00311 } 00312 } 00313 00314 00315 //////////////////////////////////////////////////////////////////// 00316 // Function: EggBinMaker::setup_bin 00317 // Access: Private 00318 // Description: Sets up a recently-created EggBin structure with all 00319 // of its children. 00320 //////////////////////////////////////////////////////////////////// 00321 void EggBinMaker:: 00322 setup_bin(EggBin *bin, const Nodes &nodes) { 00323 nassertv(!nodes.empty()); 00324 int bin_number = get_bin_number(nodes.front()); 00325 bin->set_bin_number(bin_number); 00326 00327 string bin_name = get_bin_name(bin_number, nodes.front()); 00328 if (!bin_name.empty()) { 00329 bin->set_name(bin_name); 00330 } 00331 00332 Nodes::const_iterator ni; 00333 for (ni = nodes.begin(); ni != nodes.end(); ++ni) { 00334 bin->add_child(*ni); 00335 } 00336 } 00337