Debian Codegraph @

apps/tools/ivfix/IfWeeder.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 #include <Inventor/actions/SoSearchAction.h>
38 #include <Inventor/nodes/SoMaterial.h>
39 #include <Inventor/nodes/SoSeparator.h>
40 #include <Inventor/nodes/SoIndexedFaceSet.h>
41 #include <Inventor/nodes/SoIndexedTriangleStripSet.h>
42 #include <Inventor/nodes/SoVertexProperty.h>
43
44 #include "IfAssert.h"
45 #include "IfShape.h"
46 #include "IfTypes.h"
47 #include "IfWeeder.h"
48
49 /////////////////////////////////////////////////////////////////////////////
50 //
51 // Constructor.
52 //
53 /////////////////////////////////////////////////////////////////////////////
54
55 IfWeeder::IfWeeder()
56 {
57 }
58
59 /////////////////////////////////////////////////////////////////////////////
60 //
61 // Destructor.
62 //
63 /////////////////////////////////////////////////////////////////////////////
64
65 IfWeeder::~IfWeeder()
66 {
67 }
68
69 /////////////////////////////////////////////////////////////////////////////
70 //
71 // This weeds out unnecessary items from the given fixed scene graph.
72 //
73 /////////////////////////////////////////////////////////////////////////////
74
75 void
76 IfWeeder::weed(SoNode *root)
77 {
78 // Weed out duplicate and unused materials from all SoMaterial
79 // nodes in the graph
80 weedMaterials(root);
81 }
82
83 /////////////////////////////////////////////////////////////////////////////
84 //
85 // This type is used by weedMaterials() to determine material-shape
86 // dependencies.
87 //
88 /////////////////////////////////////////////////////////////////////////////
89
90 struct IfWeederMaterialEntry {
91 SoMaterial *material; // Pointer to material
92 SoNodeList shapes; // IfShapes that use material
93 SbBool canWeed; // TRUE if material can be weeded
94 };
95
96 /////////////////////////////////////////////////////////////////////////////
97 //
98 // This weeds out values in SoMaterial nodes that are not used by any
99 // shape. It also removes duplicate material values.
100 //
101 /////////////////////////////////////////////////////////////////////////////
102
103 void
104 IfWeeder::weedMaterials(SoNode *root)
105 {
106 // Find all SoMaterial nodes in the scene graph and determine
107 // which shape nodes are affected by each one. Note that because
108 // materials may be multiply instanced, this is a little more
109 // complicated than just looking at each subgraph with a
110 // material. The resulting materials are stored in the
111 // materialList, which is a list of pointers to
112 // IfWeederMaterialEntry instances.
113 findMaterialsAndShapes(root);
114
115 // Weed each material in the resulting list
116 int i;
117 for (i = 0; i < materialList->getLength(); i++) {
118 IfWeederMaterialEntry *entry = (IfWeederMaterialEntry *)
119 (*materialList)[i];
120
121 if (entry->canWeed)
122 weedMaterial(root, entry);
123 }
124
125 // Clean up
126 for (i = 0; i < materialList->getLength(); i++)
127 delete (IfWeederMaterialEntry *) (*materialList)[i];
128 delete materialList;
129 }
130
131 /////////////////////////////////////////////////////////////////////////////
132 //
133 // Finds all materials in the given graph and the shapes that depend
134 // on them.
135 //
136 /////////////////////////////////////////////////////////////////////////////
137
138 void
139 IfWeeder::findMaterialsAndShapes(SoNode *root)
140 {
141 // Since we know the structure of the given scene graph (which is
142 // after fixing has occurred), we can be efficient here. Just
143 // search for all materials in the scene. For each material, the
144 // shapes affected by it must be under the separator that is the
145 // material's parent node. So just search for all shapes under
146 // that separator, making sure that the path to the shape comes
147 // after the material.
148
149 // First, create a dictionary so we can tell when we've found a
150 // multiple instance of a material
151 SbDict materialDict;
152
153 // Search for all materials in the scene
154 SoSearchAction sa;
155 sa.setType(SoMaterial::getClassTypeId());
156 sa.setInterest(SoSearchAction::ALL);
157 sa.apply(root);
158
159 // Set up another search action to find all shapes using a
160 // material. Note that we have to search for all node types that
161 // should be considered shapes.
162 SoSearchAction sa2;
163 sa2.setInterest(SoSearchAction::ALL);
164
165 // These are the shape types
166 SoTypeList shapeTypes;
167 IfTypes::getShapeTypes(&shapeTypes);
168
169 // Process each material, adding new ones to the list
170 materialList = new SbPList;
171 for (int i = 0; i < sa.getPaths().getLength(); i++) {
172
173 const SoPath *path = (const SoPath *) sa.getPaths()[i];
174
175 ASSERT(path->getLength() > 1);
176 ASSERT(path->getTail()->getTypeId() == SoMaterial::getClassTypeId());
177
178 SoMaterial *material = (SoMaterial *) path->getTail();
179
180 // Add to the dictionary if necessary, or use the existing
181 // entry
182 void *entryPtr;
183 IfWeederMaterialEntry *entry;
184 if (materialDict.find((unsigned long) material, entryPtr)) {
185 entry = (IfWeederMaterialEntry *) entryPtr;
186 if (! entry->canWeed)
187 continue;
188 }
189 else {
190 entry = new IfWeederMaterialEntry;
191 entry->material = material;
192 entry->canWeed = TRUE;
193 materialDict.enter((unsigned long) material, entry);
194 materialList->append(entry);
195 }
196
197 // If any node above the material in the path is an opaque
198 // group, we can't really weed this material
199 int j;
200 for (j = path->getLength() - 2; j >= 0; j--) {
201 if (IfTypes::isOpaqueGroupType(path->getNode(j)->getTypeId())) {
202 entry->canWeed = FALSE;
203 break;
204 }
205 }
206 if (! entry->canWeed)
207 continue;
208
209 ASSERT(path->getNodeFromTail(1)->
210 isOfType(SoSeparator::getClassTypeId()));
211
212 SoSeparator *parent = (SoSeparator *) path->getNodeFromTail(1);
213 int materialIndex = path->getIndexFromTail(0);
214
215 // Find all shapes using the material, adding them to the list
216 // of shapes in the material's entry. Store all the paths to
217 // them in this list
218 SoPathList pathsToShapes;
219 for (int type = 0; type < shapeTypes.getLength(); type++) {
220 sa2.setType(shapeTypes[type]);
221 sa2.apply(parent);
222 for (j = 0; j < sa2.getPaths().getLength(); j++)
223 pathsToShapes.append(sa2.getPaths()[j]);
224 }
225
226 for (j = 0; j < pathsToShapes.getLength(); j++) {
227
228 const SoPath *shapePath = (const SoPath *) pathsToShapes[j];
229
230 // We can't weed the material at all if a shape other than
231 // the one we created is found
232 SoType tailType = shapePath->getTail()->getTypeId();
233 if (tailType != SoIndexedTriangleStripSet::getClassTypeId() &&
234 tailType != SoIndexedFaceSet::getClassTypeId()) {
235 entry->canWeed = FALSE;
236 break;
237 }
238
239 // Make sure the shape comes after the material and does
240 // not get its materials from a vertex property
241 // node.
242 else if (shapePath->getIndex(1) > materialIndex) {
243 SoIndexedShape *is = (SoIndexedShape *) shapePath->getTail();
244
245 // ??? If the shape's materialIndex field has the
246 // ??? default value, we assume that it might have to
247 // ??? access all the material values. To check, we would
248 // ??? have to look at the coordIndex values if the
249 // ??? material binding is not OVERALL. This change could
250 // ??? not be done in time for the release. See bug 311071.
251 if (is->materialIndex.getNum() == 1 &&
252 is->materialIndex[0] < 0) {
253 entry->canWeed = FALSE;
254 break;
255 }
256
257 SoVertexProperty *vp =
258 (SoVertexProperty *) is->vertexProperty.getValue();
259 if (vp == NULL || vp->orderedRGBA.getNum() == 0)
260 entry->shapes.append(shapePath->getTail());
261 }
262 }
263 }
264 }
265
266 /////////////////////////////////////////////////////////////////////////////
267 //
268 // Weeds the material in the given entry.
269 //
270 /////////////////////////////////////////////////////////////////////////////
271
272 void
273 IfWeeder::weedMaterial(SoNode *root, IfWeederMaterialEntry *entry)
274 {
275 // If the material affects no shapes at all, get rid of it. This
276 // can happen when vertex property nodes are used.
277 if (entry->shapes.getLength() == 0) {
278 SoSearchAction sa;
279 sa.setNode(entry->material);
280 sa.setInterest(SoSearchAction::ALL);
281 sa.apply(root);
282 for (int i = 0; i < sa.getPaths().getLength(); i++) {
283 SoPath *path = sa.getPaths()[i];
284 SoSeparator *parent = (SoSeparator *) path->getNodeFromTail(1);
285 int index = path->getIndexFromTail(0);
286 ASSERT(parent->isOfType(SoSeparator::getClassTypeId()));
287 ASSERT(parent->getChild(index) == entry->material);
288 parent->removeChild(index);
289 }
290 }
291
292 // Remove all material values from the material node that are
293 // not used by any dependent shapes. Adjust the indices in the
294 // dependent shapes accordingly.
295 removeDuplicateMaterials(entry);
296
297 // Now remove all material values that are not used by any
298 // dependent shapes. Again, adjust the indices in the dependent
299 // shapes.
300 removeUnusedMaterials(entry);
301 }
302
303 /////////////////////////////////////////////////////////////////////////////
304 //
305 // Finds and removes duplicate materials, adjusting material
306 // indices in all dependent shapes.
307 //
308 /////////////////////////////////////////////////////////////////////////////
309
310 void
311 IfWeeder::removeDuplicateMaterials(IfWeederMaterialEntry *entry)
312 {
313 ////////////////////////////////////////////
314 //
315 // To find duplicate materials, we create a hash table of material
316 // values. Each entry in the hash table contains an index into the
317 // material node's values. The entries in the table use the
318 // material values as the hash key, so that duplicate materials
319 // will be in the same slot in the table. If we find a duplicate,
320 // we store that fact in a table of index duplicates. For example,
321 // if material index 32 is the same as material index 21, we store
322 // 21 in entry 32 in the duplicates array. When we are done with
323 // the hash table, the duplicates array will tell us which
324 // material values we need to keep in the material node and also
325 // how to adjust the material indices in the SoIndexedShapes.
326 //
327
328 // Instances of this structure is stored in the hash table.
329 struct IfWeederMaterialInfo {
330 int index; // Index of material value
331 IfWeederMaterialInfo *next; // For making lists in the hash table
332 };
333
334 // Access the fields of the material node for faster referencing
335 curMaterial = entry->material;
336 ambi = curMaterial->ambientColor.getValues(0);
337 diff = curMaterial->diffuseColor.getValues(0);
338 spec = curMaterial->specularColor.getValues(0);
339 emis = curMaterial->emissiveColor.getValues(0);
340 shin = curMaterial->shininess.getValues(0);
341 tran = curMaterial->transparency.getValues(0);
342
343 int numMaterials = curMaterial->diffuseColor.getNum();
344
345 // Create an array of structures to insert into the table
346 IfWeederMaterialInfo *infos = new IfWeederMaterialInfo[numMaterials];
347
348 // Create an array to hold the duplicate info
349 int *duplicates = new int [numMaterials];
350
351 // Create a hash table of a reasonable size
352 SbDict *hashTable = new SbDict(1 + numMaterials / 4);
353
354 // Add each material index to the hash table, looking for
355 // duplicates
356 int i, numMatches = 0;
357
358 for (i = 0; i < numMaterials; i++) {
359
360 // Assume that there is no duplicate. We'll overwrite this if
361 // we find one below
362 duplicates[i] = -1;
363
364 // Prepare an info instance to insert
365 infos[i].index = i;
366 infos[i].next = NULL;
367
368 // Compute a hash value for the material based on the material
369 // values
370 uint32_t hashKey = computeMaterialHashKey(i);
371
372 // See if there is anything in the hash table with that key
373 void *entry;
374 if (hashTable->find(hashKey, entry)) {
375 // Look for an exact match
376 IfWeederMaterialInfo *info, *prevInfo = NULL;
377 for (info = (IfWeederMaterialInfo *) entry;
378 info != NULL; info = info->next) {
379
380 // If there's a match, record the duplicate
381 if (isSameMaterial(info->index, i)) {
382 duplicates[i] = info->index;
383 numMatches++;
384 break;
385 }
386
387 prevInfo = info;
388 }
389
390 // If we didn't find a duplicate, add a new entry to the
391 // end of the list
392 if (duplicates[i] == -1) {
393 ASSERT(prevInfo != NULL);
394 prevInfo->next = &infos[i];
395 }
396 }
397
398 // If there was nothing in the table for this key, add a new entry
399 else
400 hashTable->enter(hashKey, &infos[i]);
401 }
402
403 // We're done with the hash table
404 delete hashTable;
405 delete [] infos;
406
407 // Now we can adjust the material indices in the shapes affected
408 // by the material. Don't bother doing this unless we weeded at
409 // least one material.
410 if (numMatches > 0) {
411
412 for (i = 0; i < entry->shapes.getLength(); i++) {
413
414 // Adjust material indices to use only original materials,
415 // not duplicates
416 SoIndexedShape *iShape = (SoIndexedShape *) entry->shapes[i];
417 int num = iShape->materialIndex.getNum();
418 int32_t *m = iShape->materialIndex.startEditing();
419 for (int i = 0; i < num; i++) {
420
421 // If the material index is off the end, cycle it
422 if (m[i] >= numMaterials)
423 m[i] %= numMaterials;
424
425 // Now check for duplicates
426 if (m[i] >= 0 && duplicates[m[i]] != -1)
427 m[i] = duplicates[m[i]];
428 }
429 iShape->materialIndex.finishEditing();
430 }
431 }
432
433 delete [] duplicates;
434 }
435
436 /////////////////////////////////////////////////////////////////////////////
437 //
438 // Computes a hash key for the material value with the given index.
439 //
440 /////////////////////////////////////////////////////////////////////////////
441
442 uint32_t
443 IfWeeder::computeMaterialHashKey(int index)
444 {
445 // Just use the diffuse color to compute a key, since it's most
446 // likely to vary between materials
447
448 // Since we care only about exact matches, we can use any hash
449 // function we like here. Just pick one that distributes the
450 // materials in the range 0-10000. We can do this because we know
451 // the color values range from 0 to 1.
452
453 return (uint32_t) (diff[index][0] * 8871 +
454 diff[index][1] * 1104 +
455 diff[index][2] * 25);
456 }
457
458 /////////////////////////////////////////////////////////////////////////////
459 //
460 // Returns TRUE if the two material values with the given indices
461 // are the same.
462 //
463 /////////////////////////////////////////////////////////////////////////////
464
465 SbBool
466 IfWeeder::isSameMaterial(int i1, int i2)
467 {
468 // Trivial case of same indices
469 if (i1 == i2)
470 return TRUE;
471
472 // Diffuse colors always have to be the same
473 if (diff[i1] != diff[i2])
474 return FALSE;
475
476 #define TEST_FIELD(FIELD,VAR) \
477 if (curMaterial->FIELD.getNum() > 1 && VAR[i1] != VAR[i2]) \
478 return FALSE
479
480 // The rest depends on what varies
481 TEST_FIELD(ambientColor, ambi);
482 TEST_FIELD(specularColor, spec);
483 TEST_FIELD(emissiveColor, emis);
484 TEST_FIELD(shininess, shin);
485 TEST_FIELD(transparency, tran);
486
487 #undef TEST_FIELD
488
489 // If we got here, they're the same
490 return TRUE;
491 }
492
493 /////////////////////////////////////////////////////////////////////////////
494 //
495 // Removes any unused material values and updates the indices in all
496 // dependent shapes.
497 //
498 /////////////////////////////////////////////////////////////////////////////
499
500 void
501 IfWeeder::removeUnusedMaterials(IfWeederMaterialEntry *entry)
502 {
503 SoMaterial *material = entry->material;
504 int numMaterials = material->diffuseColor.getNum();
505 if (numMaterials == 0)
506 return;
507
508 ////////////////////////////////////////////
509 //
510 // Scan the lists of material indices in each shape to see which
511 // (and how many) materials are used. Store the results in an
512 // array of flags and a counter.
513
514 int i, numUsed = 0;
515 SbBool *materialUsed = new SbBool[numMaterials];
516 for (i = 0; i < numMaterials; i++)
517 materialUsed[i] = FALSE;
518 for (i = 0; i < entry->shapes.getLength(); i++) {
519 SoIndexedShape *iShape = (SoIndexedShape *) entry->shapes[i];
520 int numIndices = iShape->materialIndex.getNum();
521 const int32_t *oldIndices = iShape->materialIndex.getValues(0);
522 if (numIndices == 1) {
523
524 // If there is only one material index, that means the
525 // shape uses overall material binding, so we can set the
526 // materialIndex field to the default value and skip the
527 // shape.
528 if (! materialUsed[0]) {
529 materialUsed[0] = TRUE;
530 numUsed++;
531 }
532 iShape->materialIndex = -1;
533 iShape->materialIndex.setDefault(TRUE);
534 continue;
535 }
536 for (int j = 0; j < numIndices; j++) {
537 int mi = oldIndices[j];
538 // The material index should have already been brought
539 // into the correct range
540 ASSERT(mi < numMaterials);
541 if (mi >= 0 && ! materialUsed[mi]) {
542 materialUsed[mi] = TRUE;
543 numUsed++;
544 }
545 }
546 }
547
548 // If all materials are used, stop
549 ASSERT(numUsed <= numMaterials);
550 if (numUsed == numMaterials) {
551 delete [] materialUsed;
552 return;
553 }
554
555 ////////////////////////////////////////////
556 //
557 // Set up an array of correspondences from old material indices
558 // to new ones. Store -1 for those materials that are not used.
559
560 int *materialIndex = new int[numMaterials];
561 int curNewIndex = 0;
562 for (i = 0; i < numMaterials; i++) {
563 if (materialUsed[i])
564 materialIndex[i] = curNewIndex++;
565 else
566 materialIndex[i] = -1;
567 }
568 ASSERT(curNewIndex == numUsed);
569
570 ////////////////////////////////////////////
571 //
572 // Update the material indices in the shapes
573
574 for (i = 0; i < entry->shapes.getLength(); i++) {
575 SoIndexedShape *iShape = (SoIndexedShape *) entry->shapes[i];
576 int numIndices = iShape->materialIndex.getNum();
577 if (numIndices == 1) {
578
579 // If there is only one material index and its value is 0
580 // or default, that means the shape uses overall material
581 // binding, so we can skip the shape.
582 if (iShape->materialIndex.isDefault() ||
583 iShape->materialIndex[0] == 0)
584 continue;
585
586 numIndices = iShape->coordIndex.getNum();
587 iShape->materialIndex.setValues(0, numIndices,
588 iShape->coordIndex.getValues(0));
589 }
590 int32_t *newIndices = iShape->materialIndex.startEditing();
591 for (i = 0; i < numIndices; i++) {
592 int mi = newIndices[i];
593 if (mi >= 0) {
594 // The material index should have already been brought
595 // into the correct range
596 ASSERT(mi < numMaterials);
597 newIndices[i] = materialIndex[mi];
598 ASSERT(newIndices[i] >= 0);
599 }
600 }
601 iShape->materialIndex.finishEditing();
602 }
603
604 ////////////////////////////////////////////
605 //
606 // Now we need to compress the material values themselves. Save
607 // the existing fields, then copy the needed values into the real
608 // fields. Do each field that has more than 1 value.
609 //
610
611 SoMFColor saveColors;
612 SoMFFloat saveFloats;
613 saveColors.setContainer(NULL);
614 saveFloats.setContainer(NULL);
615
616 #define COMPRESS_COLOR(FIELD) \
617 if (material->FIELD.getNum() > 1) { \
618 saveColors = material->FIELD; \
619 material->FIELD.setNum(numUsed); \
620 const SbColor *oldColors = saveColors.getValues(0); \
621 SbColor *newColors = material->FIELD.startEditing(); \
622 curNewIndex = 0; \
623 for (i = 0; i < numMaterials; i++) \
624 if (materialUsed[i]) \
625 newColors[curNewIndex++] = oldColors[i]; \
626 material->FIELD.finishEditing(); \
627 }
628
629 #define COMPRESS_FLOAT(FIELD) \
630 if (material->FIELD.getNum() > 1) { \
631 saveFloats = material->FIELD; \
632 material->FIELD.setNum(numUsed); \
633 const float *oldFloats = saveFloats.getValues(0); \
634 float *newFloats = material->FIELD.startEditing(); \
635 curNewIndex = 0; \
636 for (i = 0; i < numMaterials; i++) \
637 if (materialUsed[i]) \
638 newFloats[curNewIndex++] = oldFloats[i]; \
639 material->FIELD.finishEditing(); \
640 }
641
642 COMPRESS_COLOR(ambientColor);
643 COMPRESS_COLOR(diffuseColor);
644 COMPRESS_COLOR(specularColor);
645 COMPRESS_COLOR(emissiveColor);
646 COMPRESS_FLOAT(shininess);
647 COMPRESS_FLOAT(transparency);
648
649 // Clean up
650 delete [] materialUsed;
651 delete [] materialIndex;
652
653 #undef COMPRESS_COLOR
654 #undef COMPRESS_FLOAT
655 }