Debian Codegraph @

apps/tools/ivfix/IfBuilder.c++

raw
1 /*
2 *
3 * Copyright (C) 2000 Silicon Graphics, Inc. All Rights Reserved.
4 *
5 * This library is free software; you can redistribute it and/or
6 * modify it under the terms of the GNU Lesser General Public
7 * License as published by the Free Software Foundation; either
8 * version 2.1 of the License, or (at your option) any later version.
9 *
10 * This library is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 * Lesser General Public License for more details.
14 *
15 * Further, this software is distributed without any warranty that it is
16 * free of the rightful claim of any third person regarding infringement
17 * or the like. Any license provided herein, whether implied or
18 * otherwise, applies only to this software file. Patent licenses, if
19 * any, provided herein do not apply to combinations of this program with
20 * other software, or any other product whatsoever.
21 *
22 * You should have received a copy of the GNU Lesser General Public
23 * License along with this library; if not, write to the Free Software
24 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
25 *
26 * Contact information: Silicon Graphics, Inc., 1600 Amphitheatre Pkwy,
27 * Mountain View, CA 94043, or:
28 *
29 * http://www.sgi.com
30 *
31 * For further information regarding this notice, see:
32 *
33 * http://oss.sgi.com/projects/GenInfo/NoticeExplan/
34 *
35 */
36
37 #define DEBUG_WRITE 0
38
39 #include <Inventor/actions/SoSearchAction.h>
40 #include <Inventor/elements/SoLazyElement.h>
41 #include <Inventor/elements/SoTextureImageElement.h>
42 #include <Inventor/nodes/SoMaterial.h>
43 #include <Inventor/nodes/SoSeparator.h>
44
45 #include "IfAssert.h"
46 #include "IfBuilder.h"
47 #include "IfCondenser.h"
48 #include "IfFlattener.h"
49 #include "IfHolder.h"
50 #include "IfReporter.h"
51 #include "IfShape.h"
52 #include "IfStripper.h"
53
54 // All roots at Level 5 have this name so we can find them easily:
55 #define LEVEL_5_ROOT_NAME "__level5Root"
56
57 #if DEBUG_WRITE
58 #include <Inventor/actions/SoWriteAction.h>
59 #endif
60
61 /////////////////////////////////////////////////////////////////////////////
62 //
63 // Constructor.
64 //
65 /////////////////////////////////////////////////////////////////////////////
66
67 IfBuilder::IfBuilder()
68 {
69 }
70
71 /////////////////////////////////////////////////////////////////////////////
72 //
73 // Destructor.
74 //
75 /////////////////////////////////////////////////////////////////////////////
76
77 IfBuilder::~IfBuilder()
78 {
79 }
80
81 /////////////////////////////////////////////////////////////////////////////
82 //
83 // This takes a sorted IfShapeList and builds a minimal scene graph that
84 // represents it.
85 //
86 /////////////////////////////////////////////////////////////////////////////
87
88 SoNode *
89 IfBuilder::build(const IfShapeList &shapeList, SbBool _doStrips, SbBool _doVP,
90 SbBool _doAnyNormals, SbBool _doAnyTexCoords)
91 {
92 doStrips = _doStrips;
93 doVP = _doVP;
94 doAnyNormals = _doAnyNormals;
95 doAnyTexCoords = _doAnyTexCoords;
96
97 //////////////////////////////////////////////////////////////////
98 //
99 // We are going to build a 5-level scene graph. The top level (0)
100 // is just a root node. Levels 1-5 are separators under which
101 // nodes of the corresponding levels are stored, as well as the
102 // lower-level root separators. These nodes are stored only when
103 // they differ between shapes.
104 //
105 // When we are done, we will prune out any unnecessary separators
106 // at levels that do not contain differences.
107 //
108
109 // Build the top-level root
110 roots[0] = new SoSeparator;
111 roots[0]->ref();
112
113 // Build the other 5 roots
114 IfShape *shape = shapeList[0];
115 buildRoots(1, shape);
116
117 // Run through the sorted list of shapes. Every time we hit a
118 // shape that differs from the previous shape at Level 1, 2, 3, or
119 // 4, we create a new root at the appropriate level and add the
120 // nodes at that level to it.
121
122 for (int i = 1; i < shapeList.getLength(); i++) {
123
124 IfShape *shape = shapeList[i];
125
126 // Skip over a shape that is the same as the previous one (as
127 // a result of merging)
128 if (shape == shapeList[i - 1])
129 continue;
130
131 ASSERT(shape->differenceLevel >= 0 && shape->differenceLevel <= 5);
132
133 if (shape->differenceLevel > 0)
134 buildRoots(shape->differenceLevel, shape);
135
136 // Always add the appropriate nodes for Level 5
137 else
138 shape->addNodesForLevel(roots[5], 5);
139
140 // We are done with the nodes in this shape, so unref them to
141 // see if we can free up some memory
142 shape->clearNodes();
143 }
144
145 #if DEBUG_WRITE
146 {
147 SoWriteAction wa;
148 wa.getOutput()->openFile("PREFLATTEN.iv");
149 wa.apply(roots[0]);
150 }
151 #endif
152
153 // Now replace all level-5 roots with the result of flattening,
154 // condensing, and so forth
155 replaceLevel5();
156
157 #if DEBUG_WRITE
158 {
159 SoWriteAction wa;
160 wa.getOutput()->openFile("PREREMOVE.iv");
161 wa.apply(roots[0]);
162 }
163 #endif
164
165 // Now remove any separators that have only one child
166 removeUnnecessarySeparators(roots[0], 0);
167
168 // Get rid of the top separator if it has only one child
169 while (roots[0]->getNumChildren() == 1) {
170 SoSeparator *newRoot = (SoSeparator *) roots[0]->getChild(0);
171 newRoot->ref();
172 roots[0]->unref();
173 roots[0] = newRoot;
174
175 // If the new top root isn't really a separator, stop. (It
176 // might be a derived class.)
177 if (roots[0]->getTypeId() != SoSeparator::getClassTypeId())
178 break;
179 }
180
181 #if DEBUG_WRITE
182 {
183 SoWriteAction wa;
184 wa.getOutput()->openFile("POSTREMOVE.iv");
185 wa.apply(roots[0]);
186 }
187 #endif
188
189 roots[0]->unrefNoDelete();
190 return roots[0];
191 }
192
193 /////////////////////////////////////////////////////////////////////////////
194 //
195 // Builds the roots from the given level down.
196 //
197 /////////////////////////////////////////////////////////////////////////////
198
199 void
200 IfBuilder::buildRoots(int startLevel, IfShape *shape)
201 {
202 ASSERT(startLevel > 0 && startLevel <= 5);
203
204 for (int level = startLevel; level <= 5; level++) {
205
206 roots[level] = new SoSeparator;
207 roots[level-1]->addChild(roots[level]);
208
209 // Add the appropriate nodes for the level
210 shape->addNodesForLevel(roots[level], level);
211 }
212
213 // Every time this is called, a new Level 5 root is built. Name it
214 // so we can find all of them easily later on, unless we really
215 // don't want to flatten it because the IfShape says so.
216 if (! shape->dontFlatten)
217 roots[5]->setName(LEVEL_5_ROOT_NAME);
218 }
219
220 /////////////////////////////////////////////////////////////////////////////
221 //
222 // Replaces all level-5 roots with the result of flattening.
223 //
224 /////////////////////////////////////////////////////////////////////////////
225
226 void
227 IfBuilder::replaceLevel5()
228 {
229 // Find all paths to the roots with the Level 5 name
230 SoSearchAction sa;
231 sa.setName(LEVEL_5_ROOT_NAME);
232 sa.setInterest(SoSearchAction::ALL);
233 sa.apply(roots[0]);
234
235 // There may not be any, depending on the shape types we found
236 int numSubGraphs = sa.getPaths().getLength();
237
238 for (int i = 0; i < numSubGraphs; i++) {
239
240 IfReporter::reportIndex("Doing subgraph", i, numSubGraphs);
241
242 const SoPath *path = sa.getPaths()[i];
243 SoNode *level5Root = path->getTail();
244 ASSERT(path->getLength() > 1);
245 ASSERT(level5Root->getTypeId() == SoSeparator::getClassTypeId());
246
247 // Traverse the path with a callback action to determine if
248 // normals and texture coordinates are required
249 SbBool doNormals, doTexCoords;
250 getFlags((SoPath *) path, doNormals, doTexCoords);
251
252 // Replace the level 5 root with the result of flattening its
253 // subgraph
254 SoNode *flatRoot = flatten(path,
255 doAnyNormals && doNormals,
256 doAnyTexCoords && doTexCoords);
257 SoSeparator *parent = (SoSeparator *) path->getNodeFromTail(1);
258 ASSERT(parent->getTypeId() == SoSeparator::getClassTypeId());
259 parent->replaceChild(level5Root, flatRoot);
260 }
261 }
262
263 /////////////////////////////////////////////////////////////////////////////
264 //
265 // Traverses the given path with a callback action to determine if
266 // normals and texture coordinates are required for shapes in it.
267 //
268 /////////////////////////////////////////////////////////////////////////////
269
270 void
271 IfBuilder::getFlags(SoPath *path, SbBool &doNormals, SbBool &doTexCoords)
272 {
273 // The callback will store the flag values in this array, which we
274 // pass in as user data
275 SbBool flags[2];
276
277 SoCallbackAction ca;
278 ca.addPreTailCallback(flagCB, flags);
279 ca.apply(path);
280
281 // Access the stored flags
282 doNormals = flags[0];
283 doTexCoords = flags[1];
284 }
285
286 /////////////////////////////////////////////////////////////////////////////
287 //
288 // This is called through the callback.
289 //
290 /////////////////////////////////////////////////////////////////////////////
291
292 void
293 IfBuilder::setFlags(SoCallbackAction *cba, SbBool *flags)
294 {
295 // Do normals only if lighting is on
296 flags[0] = (SoLazyElement::getLightModel(cba->getState()) ==
297 SoLazyElement::PHONG);
298
299 // Do texture coordinates only if there is a texture
300 SbVec2s s;
301 int nc, wrapS, wrapT, model;
302 SbColor blendColor;
303 flags[1] = (SoTextureImageElement::get(cba->getState(), s, nc,
304 wrapS, wrapT,
305 model, blendColor) != NULL);
306 }
307
308 /////////////////////////////////////////////////////////////////////////////
309 //
310 // Flattens the subgraph at the tail of the given path, returning
311 // the resulting graph.
312 //
313 /////////////////////////////////////////////////////////////////////////////
314
315 SoNode *
316 IfBuilder::flatten(const SoPath *path, SbBool doNormals, SbBool doTexCoords)
317 {
318 // Copy all properties from higher in the path to this root, just
319 // in case the subgraph at the tail needs them. Specifically,
320 // SoShapeHints nodes that are higher up will affect the triangle
321 // generation, so we need to make sure they are included.
322 SoSeparator *root = collectObject(path);
323 root->ref();
324
325 // Create a IfHolder to hold everything
326 IfHolder *holder = new IfHolder(root, doStrips, doNormals, doTexCoords);
327 root->unref();
328
329 // Flatten to produce triangles
330
331 IfReporter::startReport(" Flattening", TRUE);
332 IfFlattener *flattener = new IfFlattener;
333 flattener->flatten(holder);
334 delete flattener;
335 IfReporter::finishReport(TRUE);
336
337 IfReporter::reportHolder(" After flattening", holder);
338
339 // Condense the result
340 IfReporter::startReport(" Condensing", TRUE);
341 IfCondenser *condenser = new IfCondenser;
342 condenser->condense(holder);
343 delete condenser;
344 IfReporter::finishReport(TRUE);
345
346 IfReporter::reportHolder(" After condensing", holder);
347
348 if (doStrips) {
349 // Produce better triangle strips
350 IfReporter::startReport(" Stripping ", TRUE);
351 IfStripper *stripper = new IfStripper;
352 stripper->strip(holder);
353 delete stripper;
354 IfReporter::finishReport(TRUE);
355
356 IfReporter::reportHolder(" After stripping ", holder);
357 }
358
359 if (doVP) {
360 // Find the last material in the object
361 int i;
362 for (i = root->getNumChildren() - 1; i >= 0; i--) {
363 if (root->getChild(i)->isOfType(SoMaterial::getClassTypeId()))
364 break;
365 }
366 SoMaterial *mtl = (i >= 0 ? (SoMaterial *) root->getChild(i) : NULL);
367 holder->convertToVertexProperty(mtl);
368 }
369
370 SoNode *result = holder->root;
371 result->ref();
372 delete holder;
373 result->unrefNoDelete();
374
375 return result;
376 }
377
378 /////////////////////////////////////////////////////////////////////////////
379 //
380 // Collects all properties along the given path (above the tail)
381 // and returns a separator-rooted graph that contains all of them
382 // and the tail of the path.
383 //
384 /////////////////////////////////////////////////////////////////////////////
385
386 SoSeparator *
387 IfBuilder::collectObject(const SoPath *path)
388 {
389 // Create a separator to hold everything
390 SoSeparator *root = new SoSeparator;
391 root->ref();
392
393 // Traverse all nodes along the path. They should all be separators.
394 int numAboveTail = path->getLength() - 1;
395 for (int i = 0; i < numAboveTail; i++) {
396 ASSERT(path->getNode(i)->isOfType(SoSeparator::getClassTypeId()));
397
398 SoSeparator *sep = (SoSeparator *) path->getNode(i);
399
400 int nextIndexInPath = path->getIndex(i+1);
401
402 for (int j = 0; j < nextIndexInPath; j++) {
403 SoNode *node = sep->getChild(j);
404 if (node->affectsState())
405 root->addChild(node);
406 }
407 }
408
409 root->addChild(path->getTail());
410
411 root->unrefNoDelete();
412 return root;
413 }
414
415 /////////////////////////////////////////////////////////////////////////////
416 //
417 // Recursive procedure that removes any separators that have only one
418 // child.
419 //
420 /////////////////////////////////////////////////////////////////////////////
421
422 void
423 IfBuilder::removeUnnecessarySeparators(SoSeparator *root, int level)
424 {
425 // If the last child is a separator, move its children here and
426 // remove it.
427
428 int curLevel = level;
429 while (TRUE) {
430
431 SoNode *lastKid = root->getChild(root->getNumChildren() - 1);
432
433 if (lastKid->getTypeId() == SoSeparator::getClassTypeId()) {
434
435 // A Level 2 separator should NOT be removed unless there
436 // is no camera under its Level 1 separator. This keeps
437 // caching ok under the camera.
438 if (curLevel == 1 && root->getNumChildren() > 1)
439 break;
440
441 SoSeparator *kidSep = (SoSeparator *) lastKid;
442
443 // Remove the kid from the root
444 kidSep->ref();
445 root->removeChild(root->getNumChildren() - 1);
446
447 // Move the children
448 for (int i = 0; i < kidSep->getNumChildren(); i++)
449 root->addChild(kidSep->getChild(i));
450
451 kidSep->unref();
452 }
453 else
454 break;
455
456 curLevel++;
457 }
458
459 // Recurse on the children
460 for (int i = 0; i < root->getNumChildren(); i++) {
461 SoNode *kid = root->getChild(i);
462 if (kid->getTypeId() == SoSeparator::getClassTypeId())
463 removeUnnecessarySeparators((SoSeparator *) kid, level + 1);
464 }
465 }