| 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 |
} |