Panda3D
eggBinMaker.cxx
Go to the documentation of this file.
1 /**
2  * PANDA 3D SOFTWARE
3  * Copyright (c) Carnegie Mellon University. All rights reserved.
4  *
5  * All use of this software is subject to the terms of the revised BSD
6  * license. You should have received a copy of this license along
7  * with this source code in a file named "LICENSE."
8  *
9  * @file eggBinMaker.cxx
10  * @author drose
11  * @date 1999-01-21
12  */
13 
14 #include "eggBinMaker.h"
15 #include "eggGroupNode.h"
16 #include "eggGroup.h"
17 #include "eggBin.h"
18 
19 #include "dcast.h"
20 #include "pnotify.h"
21 
22 TypeHandle EggBinMaker::_type_handle;
23 
24 
25 /**
26  * Called by the SortedNodes set to put nodes into bin order. Returns true if
27  * the first node falls into an earlier bin than the second node, false
28  * otherwise.
29  */
31 operator ()(const EggNode *a, const EggNode *b) const {
32  int bin_number_a = _ebm->get_bin_number(a);
33  int bin_number_b = _ebm->get_bin_number(b);
34 
35  if (bin_number_a != bin_number_b) {
36  // If the two nodes return different bin numbers, then they sort based on
37  // those numbers.
38  return bin_number_a < bin_number_b;
39  }
40 
41  // The two nodes fell into the same bin number, so fall back on the
42  // comparison function to see if they should be differentiated.
43  return _ebm->sorts_less(bin_number_a, a, b);
44 }
45 
46 /**
47  *
48  */
49 EggBinMaker::
50 EggBinMaker() {
51 }
52 
53 /**
54  *
55  */
56 EggBinMaker::
57 ~EggBinMaker() {
58 }
59 
60 
61 /**
62  * The main entry point to EggBinMaker. Walks the egg scene graph beginning
63  * at the indicated root node, and moves all binnable nodes into EggBin
64  * objects. Returns the number of EggBins created.
65  */
66 int EggBinMaker::
67 make_bins(EggGroupNode *root_group) {
68  _group_nodes.clear();
69 
70  collect_nodes(root_group);
71 
72  int num_bins = 0;
73  GroupNodes::const_iterator gi;
74  for (gi = _group_nodes.begin(); gi != _group_nodes.end(); ++gi) {
75  num_bins += get_bins_for_group(gi);
76  }
77 
78  return num_bins;
79 }
80 
81 /**
82  * May be overridden in derived classes to perform some setup work as each
83  * node is encountered. This will be called once for each node in the egg
84  * hierarchy.
85  */
86 void EggBinMaker::
88 }
89 
90 /**
91  * May be overridden in derived classes to create additional bins within a
92  * particular bin number, based on some arbitrary property of nodes. This
93  * function establishes an arbitrary but fixed ordering between nodes; if two
94  * nodes do not sort to the same position, different bins are created for each
95  * one (with the same bin number on each bin).
96  */
97 bool EggBinMaker::
98 sorts_less(int, const EggNode *, const EggNode *) {
99  return false;
100 }
101 
102 /**
103  * May be overridden in derived classes to specify whether a particular group
104  * node, apparently redundant, may be safely collapsed out.
105  */
106 bool EggBinMaker::
107 collapse_group(const EggGroup *, int) {
108  return false;
109 }
110 
111 /**
112  * May be overridden in derived classes to define a name for each new bin,
113  * based on its bin number, and a sample child.
114  */
115 std::string EggBinMaker::
116 get_bin_name(int, const EggNode *) {
117  return std::string();
118 }
119 
120 /**
121  * May be overridden in derived classes to construct a new EggBin object (or
122  * some derived class, if needed), and preload some initial data into as
123  * required.
124  *
125  * child is an arbitrary child of the bin, and collapse_from is the group the
126  * bin is being collapsed with, if any (implying collapse_group() returned
127  * true), or NULL if not.
128  */
129 PT(EggBin) EggBinMaker::
130 make_bin(int, const EggNode *, EggGroup *collapse_from) {
131  if (collapse_from == nullptr) {
132  return new EggBin;
133  } else {
134  return new EggBin(*collapse_from);
135  }
136 }
137 
138 /**
139  * Walks the egg scene graph, identifying nodes to be binned and moving them
140  * from the scene graph into the internal bin structure.
141  */
142 void EggBinMaker::
143 collect_nodes(EggGroupNode *group) {
144  // We have to play games with this next iterator, because we might be
145  // destructively operating on the child list as we traverse it.
146  EggGroupNode::iterator i, next;
147 
148  bool first_in_group = true;
149  GroupNodes::iterator gni = _group_nodes.end();
150 
151  i = group->begin();
152  next = i;
153  while (i != group->end()) {
154  EggNode *node = (*i);
155  ++next;
156 
157  prepare_node(node);
158 
159  if (get_bin_number(node) != 0) {
160  // Ok, here's a node to be binned. Add it to the appropriate bin.
161  if (first_in_group) {
162  // If this is the first time this group has been encountered, we need
163  // to create a new entry in _group_nodes for it.
164 
165  std::pair<GroupNodes::iterator, bool> result;
166  result = _group_nodes.insert
167  (GroupNodes::value_type
168  (group, SortedNodes(EggBinMakerCompareNodes(this))));
169 
170  nassertv(result.second);
171  gni = result.first;
172  first_in_group = false;
173  }
174 
175  // Add this node to the set of all nodes being binned for the group.
176  // This also puts the nodes into bin order.
177  nassertv(gni != _group_nodes.end());
178  (*gni).second.insert(node);
179 
180  // And remove it from the scene graph.
181  group->erase(i);
182  }
183 
184  if (node->is_of_type(EggGroupNode::get_class_type())) {
185  // Recursively traverse.
186  collect_nodes(DCAST(EggGroupNode, node));
187  }
188 
189  i = next;
190  }
191 }
192 
193 
194 /**
195  * Breaks the set of nodes for a given group up into individual bins.
196  */
197 int EggBinMaker::
198 get_bins_for_group(GroupNodes::const_iterator gi) {
199  EggGroupNode *group = (*gi).first;
200  const SortedNodes &nodes = (*gi).second;
201 
202  // It shouldn't be possible for this to be empty.
203  nassertr(!nodes.empty(), 0);
204 
205  Bins bins;
206  EggBinMakerCompareNodes cn(this);
207  SortedNodes::const_iterator sni, last;
208  sni = nodes.begin();
209  last = sni;
210 
211  bins.push_back(Nodes());
212  bins.back().push_back(*sni);
213  ++sni;
214  while (sni != nodes.end()) {
215  if (cn(*last, *sni)) {
216  // Begin a new bin.
217  bins.push_back(Nodes());
218  }
219  bins.back().push_back(*sni);
220 
221  last = sni;
222  ++sni;
223  }
224 
225  make_bins_for_group(group, bins);
226  return bins.size();
227 }
228 
229 /**
230  * Creates the EggBin nodes indicated by the internal bin structure for each
231  * group.
232  */
233 void EggBinMaker::
234 make_bins_for_group(EggGroupNode *group, const Bins &bins) {
235  // We shouldn't be able to get here if we have no bins!
236  nassertv(!bins.empty());
237 
238  // If the group will have only one bin, and no other children, and the group
239  // is not the root node (and it is not some funny group-like node like a
240  // <Table>), maybe we should collapse the group and its bin together.
241 
242  bool collapse = false;
243 
244  if (group->empty() &&
245  bins.size() == 1 &&
246  group->get_parent() != nullptr &&
247  group->is_of_type(EggGroup::get_class_type())) {
248  const Nodes &nodes = bins.front();
249  nassertv(!nodes.empty());
250  int bin_number = get_bin_number(nodes.front());
251  collapse = collapse_group(DCAST(EggGroup, group), bin_number);
252  }
253 
254  if (collapse) {
255  const Nodes &nodes = bins.front();
256  nassertv(!nodes.empty());
257  int bin_number = get_bin_number(nodes.front());
258  PT(EggBin) bin = make_bin(bin_number, nodes.front(), DCAST(EggGroup, group));
259  setup_bin(bin, nodes);
260 
261  EggGroupNode *parent = group->get_parent();
262  parent->remove_child(group);
263  parent->add_child(bin);
264 
265  } else {
266  Bins::const_iterator bi;
267  for (bi = bins.begin(); bi != bins.end(); ++bi) {
268  const Nodes &nodes = (*bi);
269  nassertv(!nodes.empty());
270  int bin_number = get_bin_number(nodes.front());
271  PT(EggBin) bin = make_bin(bin_number, nodes.front(), nullptr);
272  setup_bin(bin, nodes);
273 
274  group->add_child(bin);
275  }
276  }
277 }
278 
279 
280 /**
281  * Sets up a recently-created EggBin structure with all of its children.
282  */
283 void EggBinMaker::
284 setup_bin(EggBin *bin, const Nodes &nodes) {
285  nassertv(!nodes.empty());
286  int bin_number = get_bin_number(nodes.front());
287  bin->set_bin_number(bin_number);
288 
289  std::string bin_name = get_bin_name(bin_number, nodes.front());
290  if (!bin_name.empty()) {
291  bin->set_name(bin_name);
292  }
293 
294  Nodes::const_iterator ni;
295  for (ni = nodes.begin(); ni != nodes.end(); ++ni) {
296  bin->add_child(*ni);
297  }
298 }
EggBinMaker::prepare_node
virtual void prepare_node(EggNode *node)
May be overridden in derived classes to perform some setup work as each node is encountered.
Definition: eggBinMaker.cxx:87
EggBinMaker::sorts_less
virtual bool sorts_less(int bin_number, const EggNode *a, const EggNode *b)
May be overridden in derived classes to create additional bins within a particular bin number,...
Definition: eggBinMaker.cxx:98
dcast.h
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
EggBinMakerCompareNodes
This is just an STL function object, used to sort nodes within EggBinMaker.
Definition: eggBinMaker.h:142
PT
PT(EggBin) EggBinMaker
May be overridden in derived classes to construct a new EggBin object (or some derived class,...
Definition: eggBinMaker.cxx:129
EggBinMakerCompareNodes::operator()
bool operator()(const EggNode *a, const EggNode *b) const
Called by the SortedNodes set to put nodes into bin order.
Definition: eggBinMaker.cxx:31
EggGroupNode
A base class for nodes in the hierarchy that are not leaf nodes.
Definition: eggGroupNode.h:46
pnotify.h
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
TypeHandle
TypeHandle is the identifier used to differentiate C++ class types.
Definition: typeHandle.h:81
eggBinMaker.h
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
EggBinMaker::get_bin_name
virtual std::string get_bin_name(int bin_number, const EggNode *child)
May be overridden in derived classes to define a name for each new bin, based on its bin number,...
Definition: eggBinMaker.cxx:116
eggGroupNode.h
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
eggBin.h
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
EggBinMaker::make_bins
int make_bins(EggGroupNode *root_group)
The main entry point to EggBinMaker.
Definition: eggBinMaker.cxx:67
EggNode
A base class for things that may be directly added into the egg hierarchy.
Definition: eggNode.h:35
EggGroup
The main glue of the egg hierarchy, this corresponds to the <Group>, <Instance>, and <Joint> type nod...
Definition: eggGroup.h:34
EggGroupNode::add_child
EggNode * add_child(EggNode *node)
Adds the indicated child to the group and returns it.
Definition: eggGroupNode.cxx:243
EggBinMaker::collapse_group
virtual bool collapse_group(const EggGroup *group, int bin_number)
May be overridden in derived classes to specify whether a particular group node, apparently redundant...
Definition: eggBinMaker.cxx:107
eggGroup.h
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
EggBin
A type of group node that holds related subnodes.
Definition: eggBin.h:26
TypedObject::is_of_type
bool is_of_type(TypeHandle handle) const
Returns true if the current object is or derives from the indicated type.
Definition: typedObject.I:28