Debian Codegraph @

apps/tools/ivfix/IfStripper.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/SbDict.h>
38 #include <Inventor/nodes/SoCoordinate3.h>
39 #include <Inventor/nodes/SoIndexedTriangleStripSet.h>
40
41 #include "IfAssert.h"
42 #include "IfStripper.h"
43 #include "IfHolder.h"
44
45 /////////////////////////////////////////////////////////////////////////////
46 //
47 // Constructor. Initializes data structures.
48 //
49 /////////////////////////////////////////////////////////////////////////////
50
51 IfStripper::IfStripper()
52 {
53 holder = NULL;
54 }
55
56 /////////////////////////////////////////////////////////////////////////////
57 //
58 // Destructor.
59 //
60 /////////////////////////////////////////////////////////////////////////////
61
62 IfStripper::~IfStripper()
63 {
64 }
65
66 /////////////////////////////////////////////////////////////////////////////
67 //
68 // This takes a scene graph produced by flattening and condensing a
69 // graph and produces better triangle strips, if possible.
70 //
71 /////////////////////////////////////////////////////////////////////////////
72
73 void
74 IfStripper::strip(IfHolder *_holder)
75 {
76 holder = _holder;
77
78 // There had better be an SoIndexedTriangleStripSet in the IfHolder
79 ASSERT(holder->stripSet != NULL);
80
81 // This assumes that there is currently 1 triangle per strip in
82 // the SoIndexedTriangleStripSet
83 ASSERT(holder->stripSet->coordIndex.getNum() % 4 == 0);
84 numTriangles = holder->stripSet->coordIndex.getNum() / 4;
85
86 // See if there are any normal, texture coord, and material indices
87 haveNormals = (holder->doNormals &&
88 holder->stripSet->normalIndex.getNum() > 1);
89 haveTexCoords = (holder->doTexCoords &&
90 holder->stripSet->textureCoordIndex.getNum() > 1);
91 haveMaterials = (holder->stripSet->materialIndex.getNum() > 1);
92
93 // Coordinate, normal, and texture coordinate values have been
94 // condensed, but we don't know how many distinct vertices there
95 // are. If two vertices have all identical indices, they are
96 // duplicates. (It's possible for two vertices to share
97 // coordinates, but not normals, for example.) Determine
98 // how many distinct vertices there are and allocate StripVertex
99 // structures for them.
100 createVertexList();
101
102 // Allocate and fill in triangle data structures
103 createTriangleList();
104
105 // Find adjacent triangles
106 findNeighborTriangles();
107
108 // Set up the pending triangle lists
109 setUpPendingTriangleLists();
110
111 // We are going to fill in the vertex pointer list (vertexPtrList)
112 // with pointers to the vertices forming the new triangle
113 // strips. A NULL pointer indicates the end of a strip. First,
114 // create the list with a reasonable size guess, to avoid lots of
115 // reallocing.
116 vertexPtrList = new SbPList(numTriangles * 2);
117
118 // Create strips from the connected triangles
119 createStrips();
120
121 // Change the indices in the triangle strip
122 adjustIndices();
123
124 // Clean up
125 delete [] vertices;
126 delete [] triangles;
127 delete vertexPtrList;
128 }
129
130 ////////////////////////////////////////////////////////////////////////
131 //
132 // Fills in StripVertex structures that represent triangle
133 // vertices. Returns the number of distinct vertices.
134 //
135 ////////////////////////////////////////////////////////////////////////
136
137 void
138 IfStripper::createVertexList()
139 {
140 // Step 0: Access the fields we will need to use
141 int numCoordIndices = holder->stripSet->coordIndex.getNum();
142 const int32_t *coordIndices = holder->stripSet->coordIndex.getValues(0);
143 const int32_t *normalIndices = (! haveNormals ? NULL :
144 holder->stripSet->normalIndex.getValues(0));
145 const int32_t *texCoordIndices = (! haveTexCoords ? NULL :
146 holder->stripSet->
147 textureCoordIndex.getValues(0));
148 const int32_t *mtlIndices = (! haveMaterials ? NULL :
149 holder->stripSet->materialIndex.getValues(0));
150
151 // Step 1: Assume the worst: all coordinates are distinct
152 int maxNumVertices = numTriangles * 3;
153
154 // Step 2: Allocate an array of StripVertex instances big enough
155 // to hold all of them
156 StripVertex *allVertices = new StripVertex[maxNumVertices];
157
158 // Step 3: Create an array of pointers to StripVertex instances,
159 // indexed by coordinate index. This will allow use to find
160 // duplicates very easily. (Note that the maximum coordinate index
161 // we can find is the number of coordinate values - 1.)
162 int i, numCoords = holder->coords->point.getNum();
163 StripVertex **table = new StripVertex *[numCoords];
164 for (i = 0; i < numCoords; i++)
165 table[i] = NULL;
166
167 // Step 4: Also create an array of indices into the StripVertex
168 // instances, indexed by the index into the coordIndex field. This
169 // is used later on to create triangles from the StripVertex
170 // instances.
171 vertexMap = new int [numCoordIndices];
172
173 // Step 5: Fill in the StripVertex instances with actual indices,
174 // checking for duplicates. If we find a duplicate, we don't save
175 // it.
176 StripVertex *curVert = allVertices;
177 for (i = 0; i < numCoordIndices; i++) {
178
179 int coordIndex = coordIndices[i];
180
181 if (coordIndex < 0) {
182 vertexMap[i] = -1;
183 continue;
184 }
185
186 // Fill in the next StripVertex instance
187 curVert->coordIndex = coordIndex;
188 curVert->normIndex = (haveNormals ? normalIndices[i] : -1);
189 curVert->texCoordIndex = (haveTexCoords ? texCoordIndices[i] : -1);
190 curVert->mtlIndex = (haveMaterials ? mtlIndices[i] : -1);
191 curVert->uniqueID = curVert - allVertices;
192
193 // See if we have any entries at that slot in the table
194 StripVertex *oldVert;
195 for (oldVert = table[coordIndex]; oldVert != NULL;
196 oldVert = oldVert->next) {
197
198 if (oldVert->normIndex == curVert->normIndex &&
199 oldVert->texCoordIndex == curVert->texCoordIndex &&
200 oldVert->mtlIndex == curVert->mtlIndex)
201 break;
202 }
203
204 // If we found a match, re-use the old vertex
205 if (oldVert != NULL)
206 vertexMap[i] = oldVert->uniqueID;
207
208 // Otherwise, store this vertex in the table and prepare for
209 // the next vertex
210 else {
211 curVert->next = table[coordIndex];
212 table[coordIndex] = curVert;
213 vertexMap[i] = curVert->uniqueID;
214 curVert++;
215 }
216 }
217
218 // Step 6: The number of vertices we stored is the number of
219 // distinct vertices
220 numVertices = curVert - allVertices;
221
222 // Step 7: Copy the distinct vertices into the real array
223 vertices = new StripVertex[numVertices];
224 for (i = 0; i < numVertices; i++)
225 vertices[i] = allVertices[i];
226
227 // Step 8: Get rid of the stuff we don't need any more
228 delete [] table;
229 delete [] allVertices;
230 }
231
232 ////////////////////////////////////////////////////////////////////////
233 //
234 // Creates structures that will be easier to deal with when creating
235 // triangle strips.
236 //
237 ////////////////////////////////////////////////////////////////////////
238
239 void
240 IfStripper::createTriangleList()
241 {
242 const int32_t *coordIndices = holder->stripSet->coordIndex.getValues(0);
243
244 // Allocate triangles
245 triangles = new StripTriangle[numTriangles];
246
247 // Fill in triangle structures, using the vertexMap created in
248 // createVertexList
249 for (int i = 0; i < numTriangles; i++) {
250
251 StripTriangle *tri = &triangles[i];
252
253 tri->index = i;
254
255 for (int j = 0; j < 3; j++) {
256 ASSERT(coordIndices[4*i + j] >= 0);
257 int vertexIndex = vertexMap[4*i + j];
258 ASSERT(vertexIndex >= 0);
259 ASSERT(vertexIndex < numVertices);
260 tri->v[j] = &vertices[vertexIndex];
261 }
262
263 // No neighbors yet
264 tri->t[0] = tri->t[1] = tri->t[2] = NULL;
265
266 // Not used in a real strip yet
267 tri->isUsed = FALSE;
268
269 // We have no neighbor info yet. We will compute this later.
270 tri->numUnusedNeighbors = -1;
271
272 // Not in a list yet
273 tri->prev = tri->next = NULL;
274 }
275
276 // We don't need this any more
277 delete [] vertexMap;
278 }
279
280 /////////////////////////////////////////////////////////////////////////////
281 //
282 // Finds adjacent triangles
283 //
284 /////////////////////////////////////////////////////////////////////////////
285
286 void
287 IfStripper::findNeighborTriangles()
288 {
289 // Allocate edge structures
290 StripEdge *edges = new StripEdge[3 * numTriangles];
291
292 // Create a dictionary for finding edges
293 edgeDict = new SbDict(1235);
294
295 // Run through triangles, storing edge structures and finding neighbors
296 StripEdge *edge = edges;
297 for (int i = 0; i < numTriangles; i++) {
298
299 StripTriangle *tri = &triangles[i];
300
301 // Look for a neighbor edge for each of the 3 edges. If found,
302 // mark the two triangles as neighbors and remove the neighbor
303 // edge from the list of unpaired edges. If not found, add the
304 // edge to the list.
305
306 #define DO_EDGE(VA, VB, WHICH) \
307 edge->v1 = tri->v[VA]; \
308 edge->v2 = tri->v[VB]; \
309 edge->tri = tri; \
310 edge->which = WHICH; \
311 edge->next = NULL; \
312 addEdge(edge); \
313 edge++
314
315 DO_EDGE(1, 2, 0);
316 DO_EDGE(2, 0, 1);
317 DO_EDGE(0, 1, 2);
318
319 #undef DO_EDGE
320 }
321
322 // We created the edges only to set up the neighbor relationships
323 // in triangles. Now that that is done, we don't need the edges
324 // any more
325 delete [] edges;
326 delete edgeDict;
327 }
328
329 /////////////////////////////////////////////////////////////////////////////
330 //
331 // Adds an edge to the list of edges, checking for neighbors
332 //
333 /////////////////////////////////////////////////////////////////////////////
334
335 void
336 IfStripper::addEdge(StripEdge *newEdge)
337 {
338 // See if any edges like this one are already in the dictionary
339 uint32_t key = hashEdge(newEdge);
340 void *listPtr;
341 if (edgeDict->find(key, listPtr)) {
342
343 // Look through edge list for a neighbor
344 SbBool foundNeighbor = FALSE;
345 StripEdge *prevEdge = NULL;
346 for (StripEdge *edge = (StripEdge *) listPtr;
347 edge != NULL;
348 edge = edge->next) {
349
350 // See if the edges are neighbors
351 if (edge->v1 == newEdge->v2 && edge->v2 == newEdge->v1) {
352
353 // Store the neighbor relationship in both triangles
354 edge->tri->t[edge->which] = newEdge->tri;
355 newEdge->tri->t[newEdge->which] = edge->tri;
356
357 // Remove the neighbor edge from the dictionary
358 if (prevEdge != NULL)
359 prevEdge->next = edge->next;
360 else {
361 listPtr = edge->next;
362
363 // If nothing left in list, remove the whole list
364 // from dictionary
365 if (listPtr == NULL)
366 edgeDict->remove(key);
367 }
368
369 // No need to keep looking
370 foundNeighbor = TRUE;
371 break;
372 }
373
374 prevEdge = edge;
375 }
376
377 // Add the new edge to the end of the list if no neighbor was found
378 if (! foundNeighbor)
379 prevEdge->next = newEdge;
380 }
381
382 // If no list exists yet for this hash key, create a new one
383 else
384 edgeDict->enter(key, newEdge);
385 }
386
387 /////////////////////////////////////////////////////////////////////////////
388 //
389 // Hash function for edges. This function is guaranteed to return the
390 // same value for two edges containing the same vertices, regardless
391 // of direction; i.e., it's symmetric.
392 //
393 /////////////////////////////////////////////////////////////////////////////
394
395 uint32_t
396 IfStripper::hashEdge(StripEdge *edge)
397 {
398 // Use the unique ID in each vertex to create the hashing key.
399 // Since we have to maintain symmetry, use the smaller index first.
400 int i1 = edge->v1->uniqueID;
401 int i2 = edge->v2->uniqueID;
402 if (i2 < i1) {
403 int t = i1;
404 i1 = i2;
405 i2 = t;
406 }
407
408 // Note: this function is not guaranteed to produce all unique
409 // keys (if there are > 65536 unique vertices), but that's no
410 // problem, because there is a list of edges in each hash slot.
411 return (i1 << 16) + i2;
412 }
413
414 /////////////////////////////////////////////////////////////////////////////
415 //
416 // Sets up the pending triangle lists.
417 //
418 /////////////////////////////////////////////////////////////////////////////
419
420 void
421 IfStripper::setUpPendingTriangleLists()
422 {
423 int i;
424 for (i = 0; i < 4; i++)
425 pendingTriList[i] = NULL;
426
427 // Now that all neighbors are known, figure out how many neighbors
428 // each triangle has and set numUnusedNeighbors to that
429 // number. Then add the triangle to the appropriate list.
430 for (i = 0; i < numTriangles; i++) {
431 StripTriangle *tri = &triangles[i];
432
433 tri->numUnusedNeighbors = 0;
434
435 for (int j = 0; j < 3; j++)
436 if (tri->t[j] != NULL)
437 tri->numUnusedNeighbors++;
438
439 addTriangle(tri, tri->numUnusedNeighbors);
440 }
441 }
442
443 /////////////////////////////////////////////////////////////////////////////
444 //
445 // Creates strips from the connected triangles.
446 //
447 /////////////////////////////////////////////////////////////////////////////
448
449 void
450 IfStripper::createStrips()
451 {
452 StripTriangle *tri;
453
454 // Repeat until there are no more unmarked triangles
455 while (chooseStartTriangle(tri)) {
456
457 // Find a shared edge (if any)
458 int shared = 3;
459 for (int j = 0; j < 3; j++) {
460 if (tri->t[j] != NULL && ! tri->t[j]->isUsed) {
461 shared = j;
462 break;
463 }
464 }
465
466 // Add 3 vertices of triangle, starting with vertex opposite
467 // shared edge to strip
468 switch (shared) {
469 case 0:
470 vertexPtrList->append(tri->v[0]);
471 vertexPtrList->append(tri->v[1]);
472 vertexPtrList->append(tri->v[2]);
473 break;
474 case 1:
475 vertexPtrList->append(tri->v[1]);
476 vertexPtrList->append(tri->v[2]);
477 vertexPtrList->append(tri->v[0]);
478 break;
479 case 2:
480 case 3: // No shared edges; order doesn't matter
481 vertexPtrList->append(tri->v[2]);
482 vertexPtrList->append(tri->v[0]);
483 vertexPtrList->append(tri->v[1]);
484 break;
485 }
486
487 // No shared edges? Mark triangle as used, terminate strip,
488 // and try another triangle
489 if (shared == 3) {
490 markTriangleUsed(tri);
491 vertexPtrList->append(NULL);
492 continue;
493 }
494
495 // This is used to choose which edge to go to next. It
496 // alternates after each triangle, to form a proper strip.
497 SbBool oddFace = TRUE;
498
499 while (TRUE) {
500
501 markTriangleUsed(tri);
502
503 // Get the next triangle
504 ASSERT(shared != 3);
505 StripTriangle *nextTri = tri->t[shared];
506
507 // Stop if there isn't any next triangle
508 if (nextTri == NULL || nextTri->isUsed)
509 break;
510
511 // Add the vertex of this triangle opposite the shared edge
512 if (nextTri->t[0] == tri) {
513 vertexPtrList->append(nextTri->v[0]);
514 shared = (oddFace ? 2 : 1);
515 }
516 else if (nextTri->t[1] == tri) {
517 vertexPtrList->append(nextTri->v[1]);
518 shared = (oddFace ? 0 : 2);
519 }
520 else if (nextTri->t[2] == tri) {
521 vertexPtrList->append(nextTri->v[2]);
522 shared = (oddFace ? 1 : 0);
523 }
524
525 // It's possible (if more than 2 triangles share an edge)
526 // that nextTri does not consider tri to be a neighbor. If
527 // this happens, end the current strip and start another.
528 else
529 break;
530
531 // Prepare for next triangle
532 tri = nextTri;
533 oddFace = ! oddFace;
534 }
535
536 // Terminate the strip
537 vertexPtrList->append(NULL);
538 }
539 }
540
541 ////////////////////////////////////////////////////////////////////////
542 //
543 // Chooses and returns a good starting triangle for tstrip generation.
544 //
545 ////////////////////////////////////////////////////////////////////////
546
547 SbBool
548 IfStripper::chooseStartTriangle(StripTriangle *&tri)
549 {
550 // Choose the triangle with the fewest unused neighbors
551
552 for (int i = 0; i < 4; i++) {
553 if (pendingTriList[i] != NULL) {
554 tri = pendingTriList[i];
555 ASSERT(! tri->isUsed);
556 return TRUE;
557 }
558 }
559
560 tri = NULL;
561 return FALSE;
562 }
563
564 /////////////////////////////////////////////////////////////////////////////
565 //
566 // Marks a triangle as used, removing it from the pending list and
567 // changing the status of all neighbor triangles.
568 //
569 /////////////////////////////////////////////////////////////////////////////
570
571 void
572 IfStripper::markTriangleUsed(StripTriangle *tri)
573 {
574 ASSERT(! tri->isUsed);
575
576 tri->isUsed = TRUE;
577
578 // Remove it from its current list
579 removeTriangle(tri, tri->numUnusedNeighbors);
580
581 // Decrement the numUnusedNeighbors in all neighbors and move them
582 // to the correct list
583 for (int i = 0; i < 3; i++) {
584 StripTriangle *neigh = tri->t[i];
585 if (neigh != NULL && ! neigh->isUsed) {
586 ASSERT(neigh->numUnusedNeighbors > 0);
587 removeTriangle(neigh, neigh->numUnusedNeighbors);
588 addTriangle(neigh, --neigh->numUnusedNeighbors);
589 }
590 }
591 }
592
593 /////////////////////////////////////////////////////////////////////////////
594 //
595 // Adds a triangle to the given pending list.
596 //
597 /////////////////////////////////////////////////////////////////////////////
598
599 void
600 IfStripper::addTriangle(StripTriangle *tri, int listIndex)
601 {
602 StripTriangle *first = pendingTriList[listIndex];
603
604 if (first != NULL)
605 first->prev = tri;
606 tri->next = first;
607 tri->prev = NULL;
608 pendingTriList[listIndex] = tri;
609 }
610
611 /////////////////////////////////////////////////////////////////////////////
612 //
613 // Removes a triangle from the given pending list.
614 //
615 /////////////////////////////////////////////////////////////////////////////
616
617 void
618 IfStripper::removeTriangle(StripTriangle *tri, int listIndex)
619 {
620 if (tri->prev != NULL)
621 tri->prev->next = tri->next;
622 else
623 pendingTriList[listIndex] = tri->next;
624
625 if (tri->next != NULL)
626 tri->next->prev = tri->prev;
627 }
628
629 /////////////////////////////////////////////////////////////////////////////
630 //
631 // Changes the indices in the triangle strip.
632 //
633 /////////////////////////////////////////////////////////////////////////////
634
635 void
636 IfStripper::adjustIndices()
637 {
638 int numVertices = vertexPtrList->getLength();
639
640 // Fill in the coordinate indices
641 holder->stripSet->coordIndex.setNum(numVertices);
642 int32_t *indices = holder->stripSet->coordIndex.startEditing();
643 for (int i = 0; i < numVertices; i++) {
644 StripVertex *vert = (StripVertex *) (*vertexPtrList)[i];
645 indices[i] = (vert == NULL ? -1 : vert->coordIndex);
646 }
647 holder->stripSet->coordIndex.finishEditing();
648
649 // Do same for normal indices, if necessary
650 if (haveNormals) {
651 holder->stripSet->normalIndex.setNum(numVertices);
652 indices = holder->stripSet->normalIndex.startEditing();
653 for (int i = 0; i < numVertices; i++) {
654 StripVertex *vert = (StripVertex *) (*vertexPtrList)[i];
655 indices[i] = (vert == NULL ? -1 : vert->normIndex);
656 }
657 holder->stripSet->normalIndex.finishEditing();
658 }
659
660 // Do same for texture coordinate indices, if necessary
661 if (haveTexCoords) {
662 holder->stripSet->textureCoordIndex.setNum(numVertices);
663 indices = holder->stripSet->textureCoordIndex.startEditing();
664 for (int i = 0; i < numVertices; i++) {
665 StripVertex *vert = (StripVertex *) (*vertexPtrList)[i];
666 indices[i] = (vert == NULL ? -1 : vert->texCoordIndex);
667 }
668 holder->stripSet->textureCoordIndex.finishEditing();
669 }
670
671 // Do same for material indices, if necessary
672 if (haveMaterials) {
673 holder->stripSet->materialIndex.setNum(numVertices);
674 indices = holder->stripSet->materialIndex.startEditing();
675 for (int i = 0; i < numVertices; i++) {
676 StripVertex *vert = (StripVertex *) (*vertexPtrList)[i];
677 indices[i] = (vert == NULL ? -1 : vert->mtlIndex);
678 }
679 holder->stripSet->materialIndex.finishEditing();
680 }
681 }