1 /* 2 * Copyright (c) 2009-2010 jMonkeyEngine 3 * All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions are 7 * met: 8 * 9 * * Redistributions of source code must retain the above copyright 10 * notice, this list of conditions and the following disclaimer. 11 * 12 * * Redistributions in binary form must reproduce the above copyright 13 * notice, this list of conditions and the following disclaimer in the 14 * documentation and/or other materials provided with the distribution. 15 * 16 * * Neither the name of 'jMonkeyEngine' nor the names of its contributors 17 * may be used to endorse or promote products derived from this software 18 * without specific prior written permission. 19 * 20 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 21 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED 22 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 23 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR 24 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, 25 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, 26 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 27 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF 28 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING 29 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 30 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 31 */ 32 33 package jme3tools.converters.model.strip; 34 35 import java.util.HashSet; 36 import java.util.logging.Logger; 37 38 /** 39 * 40 */ 41 class Stripifier { 42 private static final Logger logger = Logger.getLogger(Stripifier.class 43 .getName()); 44 45 public static int CACHE_INEFFICIENCY = 6; 46 47 IntVec indices = new IntVec(); 48 49 int cacheSize; 50 51 int minStripLength; 52 53 float meshJump; 54 55 boolean bFirstTimeResetPoint; 56 Stripifier()57 Stripifier() { 58 super(); 59 } 60 61 /////////////////////////////////////////////////////////////////////////////////////////// 62 // FindEdgeInfo() 63 // 64 // find the edge info for these two indices 65 // findEdgeInfo(EdgeInfoVec edgeInfos, int v0, int v1)66 static EdgeInfo findEdgeInfo(EdgeInfoVec edgeInfos, int v0, int v1) { 67 68 // we can get to it through either array 69 // because the edge infos have a v0 and v1 70 // and there is no order except how it was 71 // first created. 72 EdgeInfo infoIter = edgeInfos.at(v0); 73 while (infoIter != null) { 74 if (infoIter.m_v0 == v0) { 75 if (infoIter.m_v1 == v1) 76 return infoIter; 77 78 infoIter = infoIter.m_nextV0; 79 } else { 80 if (infoIter.m_v0 == v1) 81 return infoIter; 82 83 infoIter = infoIter.m_nextV1; 84 } 85 } 86 return null; 87 } 88 89 /////////////////////////////////////////////////////////////////////////////////////////// 90 // FindOtherFace 91 // 92 // find the other face sharing these vertices 93 // exactly like the edge info above 94 // findOtherFace(EdgeInfoVec edgeInfos, int v0, int v1, FaceInfo faceInfo)95 static FaceInfo findOtherFace(EdgeInfoVec edgeInfos, int v0, int v1, 96 FaceInfo faceInfo) { 97 EdgeInfo edgeInfo = findEdgeInfo(edgeInfos, v0, v1); 98 99 if ((edgeInfo == null) || (v0 == v1)) { 100 //we've hit a degenerate 101 return null; 102 } 103 104 return (edgeInfo.m_face0 == faceInfo ? edgeInfo.m_face1 105 : edgeInfo.m_face0); 106 } 107 alreadyExists(FaceInfo faceInfo, FaceInfoVec faceInfos)108 static boolean alreadyExists(FaceInfo faceInfo, FaceInfoVec faceInfos) { 109 for (int i = 0; i < faceInfos.size(); ++i) { 110 FaceInfo o = faceInfos.at(i); 111 if ((o.m_v0 == faceInfo.m_v0) && (o.m_v1 == faceInfo.m_v1) 112 && (o.m_v2 == faceInfo.m_v2)) 113 return true; 114 } 115 return false; 116 } 117 118 /////////////////////////////////////////////////////////////////////////////////////////// 119 // BuildStripifyInfo() 120 // 121 // Builds the list of all face and edge infos 122 // buildStripifyInfo(FaceInfoVec faceInfos, EdgeInfoVec edgeInfos, int maxIndex)123 void buildStripifyInfo(FaceInfoVec faceInfos, EdgeInfoVec edgeInfos, 124 int maxIndex) { 125 // reserve space for the face infos, but do not resize them. 126 int numIndices = indices.size(); 127 faceInfos.reserve(numIndices / 3); 128 129 // we actually resize the edge infos, so we must initialize to null 130 for (int i = 0; i < maxIndex + 1; i++) 131 edgeInfos.add(null); 132 133 // iterate through the triangles of the triangle list 134 int numTriangles = numIndices / 3; 135 int index = 0; 136 boolean[] bFaceUpdated = new boolean[3]; 137 138 for (int i = 0; i < numTriangles; i++) { 139 boolean bMightAlreadyExist = true; 140 bFaceUpdated[0] = false; 141 bFaceUpdated[1] = false; 142 bFaceUpdated[2] = false; 143 144 // grab the indices 145 int v0 = indices.get(index++); 146 int v1 = indices.get(index++); 147 int v2 = indices.get(index++); 148 149 //we disregard degenerates 150 if (isDegenerate(v0, v1, v2)) 151 continue; 152 153 // create the face info and add it to the list of faces, but only 154 // if this exact face doesn't already 155 // exist in the list 156 FaceInfo faceInfo = new FaceInfo(v0, v1, v2); 157 158 // grab the edge infos, creating them if they do not already exist 159 EdgeInfo edgeInfo01 = findEdgeInfo(edgeInfos, v0, v1); 160 if (edgeInfo01 == null) { 161 //since one of it's edges isn't in the edge data structure, it 162 // can't already exist in the face structure 163 bMightAlreadyExist = false; 164 165 // create the info 166 edgeInfo01 = new EdgeInfo(v0, v1); 167 168 // update the linked list on both 169 edgeInfo01.m_nextV0 = edgeInfos.at(v0); 170 edgeInfo01.m_nextV1 = edgeInfos.at(v1); 171 edgeInfos.set(v0, edgeInfo01); 172 edgeInfos.set(v1, edgeInfo01); 173 174 // set face 0 175 edgeInfo01.m_face0 = faceInfo; 176 } else { 177 if (edgeInfo01.m_face1 != null) { 178 logger.info("BuildStripifyInfo: > 2 triangles on an edge" 179 + v0 + "," + v1 + "... uncertain consequences\n"); 180 } else { 181 edgeInfo01.m_face1 = faceInfo; 182 bFaceUpdated[0] = true; 183 } 184 } 185 186 // grab the edge infos, creating them if they do not already exist 187 EdgeInfo edgeInfo12 = findEdgeInfo(edgeInfos, v1, v2); 188 if (edgeInfo12 == null) { 189 bMightAlreadyExist = false; 190 191 // create the info 192 edgeInfo12 = new EdgeInfo(v1, v2); 193 194 // update the linked list on both 195 edgeInfo12.m_nextV0 = edgeInfos.at(v1); 196 edgeInfo12.m_nextV1 = edgeInfos.at(v2); 197 edgeInfos.set(v1, edgeInfo12); 198 edgeInfos.set(v2, edgeInfo12); 199 200 // set face 0 201 edgeInfo12.m_face0 = faceInfo; 202 } else { 203 if (edgeInfo12.m_face1 != null) { 204 logger.info("BuildStripifyInfo: > 2 triangles on an edge" 205 + v1 206 + "," 207 + v2 208 + "... uncertain consequences\n"); 209 } else { 210 edgeInfo12.m_face1 = faceInfo; 211 bFaceUpdated[1] = true; 212 } 213 } 214 215 // grab the edge infos, creating them if they do not already exist 216 EdgeInfo edgeInfo20 = findEdgeInfo(edgeInfos, v2, v0); 217 if (edgeInfo20 == null) { 218 bMightAlreadyExist = false; 219 220 // create the info 221 edgeInfo20 = new EdgeInfo(v2, v0); 222 223 // update the linked list on both 224 edgeInfo20.m_nextV0 = edgeInfos.at(v2); 225 edgeInfo20.m_nextV1 = edgeInfos.at(v0); 226 edgeInfos.set(v2, edgeInfo20); 227 edgeInfos.set(v0, edgeInfo20); 228 229 // set face 0 230 edgeInfo20.m_face0 = faceInfo; 231 } else { 232 if (edgeInfo20.m_face1 != null) { 233 logger.info("BuildStripifyInfo: > 2 triangles on an edge" 234 + v2 235 + "," 236 + v0 237 + "... uncertain consequences\n"); 238 } else { 239 edgeInfo20.m_face1 = faceInfo; 240 bFaceUpdated[2] = true; 241 } 242 } 243 244 if (bMightAlreadyExist) { 245 if (!alreadyExists(faceInfo, faceInfos)) 246 faceInfos.add(faceInfo); 247 else { 248 249 //cleanup pointers that point to this deleted face 250 if (bFaceUpdated[0]) 251 edgeInfo01.m_face1 = null; 252 if (bFaceUpdated[1]) 253 edgeInfo12.m_face1 = null; 254 if (bFaceUpdated[2]) 255 edgeInfo20.m_face1 = null; 256 } 257 } else { 258 faceInfos.add(faceInfo); 259 } 260 261 } 262 } 263 isDegenerate(FaceInfo face)264 static boolean isDegenerate(FaceInfo face) { 265 if (face.m_v0 == face.m_v1) 266 return true; 267 else if (face.m_v0 == face.m_v2) 268 return true; 269 else if (face.m_v1 == face.m_v2) 270 return true; 271 else 272 return false; 273 } 274 isDegenerate(int v0, int v1, int v2)275 static boolean isDegenerate(int v0, int v1, int v2) { 276 if (v0 == v1) 277 return true; 278 else if (v0 == v2) 279 return true; 280 else if (v1 == v2) 281 return true; 282 else 283 return false; 284 } 285 286 /////////////////////////////////////////////////////////////////////////////////////////// 287 // GetNextIndex() 288 // 289 // Returns vertex of the input face which is "next" in the input index list 290 // getNextIndex(IntVec indices, FaceInfo face)291 static int getNextIndex(IntVec indices, FaceInfo face) { 292 293 int numIndices = indices.size(); 294 295 int v0 = indices.get(numIndices - 2); 296 int v1 = indices.get(numIndices - 1); 297 298 int fv0 = face.m_v0; 299 int fv1 = face.m_v1; 300 int fv2 = face.m_v2; 301 302 if (fv0 != v0 && fv0 != v1) { 303 if ((fv1 != v0 && fv1 != v1) || (fv2 != v0 && fv2 != v1)) { 304 logger.info("GetNextIndex: Triangle doesn't have all of its vertices\n"); 305 logger.info("GetNextIndex: Duplicate triangle probably got us derailed\n"); 306 } 307 return fv0; 308 } 309 if (fv1 != v0 && fv1 != v1) { 310 if ((fv0 != v0 && fv0 != v1) || (fv2 != v0 && fv2 != v1)) { 311 logger.info("GetNextIndex: Triangle doesn't have all of its vertices\n"); 312 logger.info("GetNextIndex: Duplicate triangle probably got us derailed\n"); 313 } 314 return fv1; 315 } 316 if (fv2 != v0 && fv2 != v1) { 317 if ((fv0 != v0 && fv0 != v1) || (fv1 != v0 && fv1 != v1)) { 318 logger.info("GetNextIndex: Triangle doesn't have all of its vertices\n"); 319 logger.info("GetNextIndex: Duplicate triangle probably got us derailed\n"); 320 } 321 return fv2; 322 } 323 324 // shouldn't get here, but let's try and fail gracefully 325 if ((fv0 == fv1) || (fv0 == fv2)) 326 return fv0; 327 else if ((fv1 == fv0) || (fv1 == fv2)) 328 return fv1; 329 else if ((fv2 == fv0) || (fv2 == fv1)) 330 return fv2; 331 else 332 return -1; 333 } 334 335 /////////////////////////////////////////////////////////////////////////////////////////// 336 // FindStartPoint() 337 // 338 // Finds a good starting point, namely one which has only one neighbor 339 // findStartPoint(FaceInfoVec faceInfos, EdgeInfoVec edgeInfos)340 static int findStartPoint(FaceInfoVec faceInfos, EdgeInfoVec edgeInfos) { 341 int bestCtr = -1; 342 int bestIndex = -1; 343 344 for (int i = 0; i < faceInfos.size(); i++) { 345 int ctr = 0; 346 347 if (findOtherFace(edgeInfos, faceInfos.at(i).m_v0, 348 faceInfos.at(i).m_v1, faceInfos.at(i)) == null) 349 ctr++; 350 if (findOtherFace(edgeInfos, faceInfos.at(i).m_v1, 351 faceInfos.at(i).m_v2, faceInfos.at(i)) == null) 352 ctr++; 353 if (findOtherFace(edgeInfos, faceInfos.at(i).m_v2, 354 faceInfos.at(i).m_v0, faceInfos.at(i)) == null) 355 ctr++; 356 if (ctr > bestCtr) { 357 bestCtr = ctr; 358 bestIndex = i; 359 //return i; 360 } 361 } 362 //return -1; 363 364 if (bestCtr == 0) 365 return -1; 366 367 return bestIndex; 368 } 369 370 /////////////////////////////////////////////////////////////////////////////////////////// 371 // FindGoodResetPoint() 372 // 373 // A good reset point is one near other commited areas so that 374 // we know that when we've made the longest strips its because 375 // we're stripifying in the same general orientation. 376 // findGoodResetPoint(FaceInfoVec faceInfos, EdgeInfoVec edgeInfos)377 FaceInfo findGoodResetPoint(FaceInfoVec faceInfos, EdgeInfoVec edgeInfos) { 378 // we hop into different areas of the mesh to try to get 379 // other large open spans done. Areas of small strips can 380 // just be left to triangle lists added at the end. 381 FaceInfo result = null; 382 383 if (result == null) { 384 int numFaces = faceInfos.size(); 385 int startPoint; 386 if (bFirstTimeResetPoint) { 387 //first time, find a face with few neighbors (look for an edge 388 // of the mesh) 389 startPoint = findStartPoint(faceInfos, edgeInfos); 390 bFirstTimeResetPoint = false; 391 } else 392 startPoint = (int) (((float) numFaces - 1) * meshJump); 393 394 if (startPoint == -1) { 395 startPoint = (int) (((float) numFaces - 1) * meshJump); 396 397 //meshJump += 0.1f; 398 //if (meshJump > 1.0f) 399 // meshJump = .05f; 400 } 401 402 int i = startPoint; 403 do { 404 405 // if this guy isn't visited, try him 406 if (faceInfos.at(i).m_stripId < 0) { 407 result = faceInfos.at(i); 408 break; 409 } 410 411 // update the index and clamp to 0-(numFaces-1) 412 if (++i >= numFaces) 413 i = 0; 414 415 } while (i != startPoint); 416 417 // update the meshJump 418 meshJump += 0.1f; 419 if (meshJump > 1.0f) 420 meshJump = .05f; 421 } 422 423 // return the best face we found 424 return result; 425 } 426 427 /////////////////////////////////////////////////////////////////////////////////////////// 428 // GetUniqueVertexInB() 429 // 430 // Returns the vertex unique to faceB 431 // getUniqueVertexInB(FaceInfo faceA, FaceInfo faceB)432 static int getUniqueVertexInB(FaceInfo faceA, FaceInfo faceB) { 433 434 int facev0 = faceB.m_v0; 435 if (facev0 != faceA.m_v0 && facev0 != faceA.m_v1 436 && facev0 != faceA.m_v2) 437 return facev0; 438 439 int facev1 = faceB.m_v1; 440 if (facev1 != faceA.m_v0 && facev1 != faceA.m_v1 441 && facev1 != faceA.m_v2) 442 return facev1; 443 444 int facev2 = faceB.m_v2; 445 if (facev2 != faceA.m_v0 && facev2 != faceA.m_v1 446 && facev2 != faceA.m_v2) 447 return facev2; 448 449 // nothing is different 450 return -1; 451 } 452 453 /////////////////////////////////////////////////////////////////////////////////////////// 454 // GetSharedVertices() 455 // 456 // Returns the (at most) two vertices shared between the two faces 457 // getSharedVertices(FaceInfo faceA, FaceInfo faceB, int[] vertex)458 static void getSharedVertices(FaceInfo faceA, FaceInfo faceB, int[] vertex) { 459 vertex[0] = -1; 460 vertex[1] = -1; 461 462 int facev0 = faceB.m_v0; 463 if (facev0 == faceA.m_v0 || facev0 == faceA.m_v1 464 || facev0 == faceA.m_v2) { 465 if (vertex[0] == -1) 466 vertex[0] = facev0; 467 else { 468 vertex[1] = facev0; 469 return; 470 } 471 } 472 473 int facev1 = faceB.m_v1; 474 if (facev1 == faceA.m_v0 || facev1 == faceA.m_v1 475 || facev1 == faceA.m_v2) { 476 if (vertex[0] == -1) 477 vertex[0] = facev1; 478 else { 479 vertex[1] = facev1; 480 return; 481 } 482 } 483 484 int facev2 = faceB.m_v2; 485 if (facev2 == faceA.m_v0 || facev2 == faceA.m_v1 486 || facev2 == faceA.m_v2) { 487 if (vertex[0] == -1) 488 vertex[0] = facev2; 489 else { 490 vertex[1] = facev2; 491 return; 492 } 493 } 494 495 } 496 497 /////////////////////////////////////////////////////////////////////////////////////////// 498 // CommitStrips() 499 // 500 // "Commits" the input strips by setting their m_experimentId to -1 and 501 // adding to the allStrips 502 // vector 503 // commitStrips(StripInfoVec allStrips, StripInfoVec strips)504 static void commitStrips(StripInfoVec allStrips, StripInfoVec strips) { 505 // Iterate through strips 506 int numStrips = strips.size(); 507 for (int i = 0; i < numStrips; i++) { 508 509 // Tell the strip that it is now real 510 StripInfo strip = strips.at(i); 511 strip.m_experimentId = -1; 512 513 // add to the list of real strips 514 allStrips.add(strip); 515 516 // Iterate through the faces of the strip 517 // Tell the faces of the strip that they belong to a real strip now 518 FaceInfoVec faces = strips.at(i).m_faces; 519 int numFaces = faces.size(); 520 521 for (int j = 0; j < numFaces; j++) { 522 strip.markTriangle(faces.at(j)); 523 } 524 } 525 } 526 527 /////////////////////////////////////////////////////////////////////////////////////////// 528 // NextIsCW() 529 // 530 // Returns true if the next face should be ordered in CW fashion 531 // nextIsCW(int numIndices)532 static boolean nextIsCW(int numIndices) { 533 return ((numIndices % 2) == 0); 534 } 535 536 /////////////////////////////////////////////////////////////////////////////////////////// 537 // UpdateCacheFace() 538 // 539 // Updates the input vertex cache with this face's vertices 540 // updateCacheFace(VertexCache vcache, FaceInfo face)541 static void updateCacheFace(VertexCache vcache, FaceInfo face) { 542 if (!vcache.inCache(face.m_v0)) 543 vcache.addEntry(face.m_v0); 544 545 if (!vcache.inCache(face.m_v1)) 546 vcache.addEntry(face.m_v1); 547 548 if (!vcache.inCache(face.m_v2)) 549 vcache.addEntry(face.m_v2); 550 } 551 552 /////////////////////////////////////////////////////////////////////////////////////////// 553 // UpdateCacheStrip() 554 // 555 // Updates the input vertex cache with this strip's vertices 556 // updateCacheStrip(VertexCache vcache, StripInfo strip)557 static void updateCacheStrip(VertexCache vcache, StripInfo strip) { 558 for (int i = 0; i < strip.m_faces.size(); ++i) { 559 if (!vcache.inCache(strip.m_faces.at(i).m_v0)) 560 vcache.addEntry(strip.m_faces.at(i).m_v0); 561 562 if (!vcache.inCache(strip.m_faces.at(i).m_v1)) 563 vcache.addEntry(strip.m_faces.at(i).m_v1); 564 565 if (!vcache.inCache(strip.m_faces.at(i).m_v2)) 566 vcache.addEntry(strip.m_faces.at(i).m_v2); 567 } 568 } 569 570 /////////////////////////////////////////////////////////////////////////////////////////// 571 // CalcNumHitsStrip() 572 // 573 // returns the number of cache hits per face in the strip 574 // calcNumHitsStrip(VertexCache vcache, StripInfo strip)575 static float calcNumHitsStrip(VertexCache vcache, StripInfo strip) { 576 int numHits = 0; 577 int numFaces = 0; 578 579 for (int i = 0; i < strip.m_faces.size(); i++) { 580 if (vcache.inCache(strip.m_faces.at(i).m_v0)) 581 ++numHits; 582 583 if (vcache.inCache(strip.m_faces.at(i).m_v1)) 584 ++numHits; 585 586 if (vcache.inCache(strip.m_faces.at(i).m_v2)) 587 ++numHits; 588 589 numFaces++; 590 } 591 592 return ((float) numHits / (float) numFaces); 593 } 594 595 /////////////////////////////////////////////////////////////////////////////////////////// 596 // AvgStripSize() 597 // 598 // Finds the average strip size of the input vector of strips 599 // avgStripSize(StripInfoVec strips)600 static float avgStripSize(StripInfoVec strips) { 601 int sizeAccum = 0; 602 int numStrips = strips.size(); 603 for (int i = 0; i < numStrips; i++) { 604 StripInfo strip = strips.at(i); 605 sizeAccum += strip.m_faces.size(); 606 sizeAccum -= strip.m_numDegenerates; 607 } 608 return ((float) sizeAccum) / ((float) numStrips); 609 } 610 611 /////////////////////////////////////////////////////////////////////////////////////////// 612 // CalcNumHitsFace() 613 // 614 // returns the number of cache hits in the face 615 // calcNumHitsFace(VertexCache vcache, FaceInfo face)616 static int calcNumHitsFace(VertexCache vcache, FaceInfo face) { 617 int numHits = 0; 618 619 if (vcache.inCache(face.m_v0)) 620 numHits++; 621 622 if (vcache.inCache(face.m_v1)) 623 numHits++; 624 625 if (vcache.inCache(face.m_v2)) 626 numHits++; 627 628 return numHits; 629 } 630 631 /////////////////////////////////////////////////////////////////////////////////////////// 632 // NumNeighbors() 633 // 634 // Returns the number of neighbors that this face has 635 // numNeighbors(FaceInfo face, EdgeInfoVec edgeInfoVec)636 static int numNeighbors(FaceInfo face, EdgeInfoVec edgeInfoVec) { 637 int numNeighbors = 0; 638 639 if (findOtherFace(edgeInfoVec, face.m_v0, face.m_v1, face) != null) { 640 numNeighbors++; 641 } 642 643 if (findOtherFace(edgeInfoVec, face.m_v1, face.m_v2, face) != null) { 644 numNeighbors++; 645 } 646 647 if (findOtherFace(edgeInfoVec, face.m_v2, face.m_v0, face) != null) { 648 numNeighbors++; 649 } 650 651 return numNeighbors; 652 } 653 654 /////////////////////////////////////////////////////////////////////////////////////////// 655 // IsCW() 656 // 657 // Returns true if the face is ordered in CW fashion 658 // isCW(FaceInfo faceInfo, int v0, int v1)659 static boolean isCW(FaceInfo faceInfo, int v0, int v1) { 660 if (faceInfo.m_v0 == v0) 661 return (faceInfo.m_v1 == v1); 662 else if (faceInfo.m_v1 == v0) 663 return (faceInfo.m_v2 == v1); 664 else 665 return (faceInfo.m_v0 == v1); 666 667 } 668 faceContainsIndex(FaceInfo face, int index)669 static boolean faceContainsIndex(FaceInfo face, int index) { 670 return ((face.m_v0 == index) || (face.m_v1 == index) || (face.m_v2 == index)); 671 } 672 673 /////////////////////////////////////////////////////////////////////////////////////////// 674 // FindTraversal() 675 // 676 // Finds the next face to start the next strip on. 677 // findTraversal(FaceInfoVec faceInfos, EdgeInfoVec edgeInfos, StripInfo strip, StripStartInfo startInfo)678 static boolean findTraversal(FaceInfoVec faceInfos, EdgeInfoVec edgeInfos, 679 StripInfo strip, StripStartInfo startInfo) { 680 681 // if the strip was v0.v1 on the edge, then v1 will be a vertex in the 682 // next edge. 683 int v = (strip.m_startInfo.m_toV1 ? strip.m_startInfo.m_startEdge.m_v1 684 : strip.m_startInfo.m_startEdge.m_v0); 685 686 FaceInfo untouchedFace = null; 687 EdgeInfo edgeIter = edgeInfos.at(v); 688 while (edgeIter != null) { 689 FaceInfo face0 = edgeIter.m_face0; 690 FaceInfo face1 = edgeIter.m_face1; 691 if ((face0 != null && !strip.isInStrip(face0)) && face1 != null 692 && !strip.isMarked(face1)) { 693 untouchedFace = face1; 694 break; 695 } 696 if ((face1 != null && !strip.isInStrip(face1)) && face0 != null 697 && !strip.isMarked(face0)) { 698 untouchedFace = face0; 699 break; 700 } 701 702 // find the next edgeIter 703 edgeIter = (edgeIter.m_v0 == v ? edgeIter.m_nextV0 704 : edgeIter.m_nextV1); 705 } 706 707 startInfo.m_startFace = untouchedFace; 708 startInfo.m_startEdge = edgeIter; 709 if (edgeIter != null) { 710 if (strip.sharesEdge(startInfo.m_startFace, edgeInfos)) 711 startInfo.m_toV1 = (edgeIter.m_v0 == v); //note! used to be 712 // m_v1 713 else 714 startInfo.m_toV1 = (edgeIter.m_v1 == v); 715 } 716 return (startInfo.m_startFace != null); 717 } 718 719 //////////////////////////////////////////////////////////////////////////////////////// 720 // RemoveSmallStrips() 721 // 722 // allStrips is the whole strip vector...all small strips will be deleted 723 // from this list, to avoid leaking mem 724 // allBigStrips is an out parameter which will contain all strips above 725 // minStripLength 726 // faceList is an out parameter which will contain all faces which were 727 // removed from the striplist 728 // removeSmallStrips(StripInfoVec allStrips, StripInfoVec allBigStrips, FaceInfoVec faceList)729 void removeSmallStrips(StripInfoVec allStrips, StripInfoVec allBigStrips, 730 FaceInfoVec faceList) { 731 faceList.clear(); 732 allBigStrips.clear(); //make sure these are empty 733 FaceInfoVec tempFaceList = new FaceInfoVec(); 734 735 for (int i = 0; i < allStrips.size(); i++) { 736 if (allStrips.at(i).m_faces.size() < minStripLength) { 737 //strip is too small, add faces to faceList 738 for (int j = 0; j < allStrips.at(i).m_faces.size(); j++) 739 tempFaceList.add(allStrips.at(i).m_faces.at(j)); 740 741 } else { 742 allBigStrips.add(allStrips.at(i)); 743 } 744 } 745 746 boolean[] bVisitedList = new boolean[tempFaceList.size()]; 747 748 VertexCache vcache = new VertexCache(cacheSize); 749 750 int bestNumHits = -1; 751 int numHits; 752 int bestIndex = -9999; 753 754 while (true) { 755 bestNumHits = -1; 756 757 //find best face to add next, given the current cache 758 for (int i = 0; i < tempFaceList.size(); i++) { 759 if (bVisitedList[i]) 760 continue; 761 762 numHits = calcNumHitsFace(vcache, tempFaceList.at(i)); 763 if (numHits > bestNumHits) { 764 bestNumHits = numHits; 765 bestIndex = i; 766 } 767 } 768 769 if (bestNumHits == -1.0f) 770 break; 771 bVisitedList[bestIndex] = true; 772 updateCacheFace(vcache, tempFaceList.at(bestIndex)); 773 faceList.add(tempFaceList.at(bestIndex)); 774 } 775 } 776 777 //////////////////////////////////////////////////////////////////////////////////////// 778 // CreateStrips() 779 // 780 // Generates actual strips from the list-in-strip-order. 781 // createStrips(StripInfoVec allStrips, IntVec stripIndices, boolean bStitchStrips)782 int createStrips(StripInfoVec allStrips, IntVec stripIndices, 783 boolean bStitchStrips) { 784 int numSeparateStrips = 0; 785 786 FaceInfo tLastFace = new FaceInfo(0, 0, 0); 787 int nStripCount = allStrips.size(); 788 789 //we infer the cw/ccw ordering depending on the number of indices 790 //this is screwed up by the fact that we insert -1s to denote changing 791 // strips 792 //this is to account for that 793 int accountForNegatives = 0; 794 795 for (int i = 0; i < nStripCount; i++) { 796 StripInfo strip = allStrips.at(i); 797 int nStripFaceCount = strip.m_faces.size(); 798 799 // Handle the first face in the strip 800 { 801 FaceInfo tFirstFace = new FaceInfo(strip.m_faces.at(0).m_v0, 802 strip.m_faces.at(0).m_v1, strip.m_faces.at(0).m_v2); 803 804 // If there is a second face, reorder vertices such that the 805 // unique vertex is first 806 if (nStripFaceCount > 1) { 807 int nUnique = getUniqueVertexInB(strip.m_faces.at(1), 808 tFirstFace); 809 if (nUnique == tFirstFace.m_v1) { 810 int tmp = tFirstFace.m_v0; 811 tFirstFace.m_v0 = tFirstFace.m_v1; 812 tFirstFace.m_v1 = tmp; 813 } else if (nUnique == tFirstFace.m_v2) { 814 int tmp = tFirstFace.m_v0; 815 tFirstFace.m_v0 = tFirstFace.m_v2; 816 tFirstFace.m_v2 = tmp; 817 } 818 819 // If there is a third face, reorder vertices such that the 820 // shared vertex is last 821 if (nStripFaceCount > 2) { 822 if (isDegenerate(strip.m_faces.at(1))) { 823 int pivot = strip.m_faces.at(1).m_v1; 824 if (tFirstFace.m_v1 == pivot) { 825 int tmp = tFirstFace.m_v1; 826 tFirstFace.m_v1 = tFirstFace.m_v2; 827 tFirstFace.m_v2 = tmp; 828 } 829 } else { 830 int[] nShared = new int[2]; 831 getSharedVertices(strip.m_faces.at(2), tFirstFace, 832 nShared); 833 if ((nShared[0] == tFirstFace.m_v1) 834 && (nShared[1] == -1)) { 835 int tmp = tFirstFace.m_v1; 836 tFirstFace.m_v1 = tFirstFace.m_v2; 837 tFirstFace.m_v2 = tmp; 838 } 839 } 840 } 841 } 842 843 if ((i == 0) || !bStitchStrips) { 844 if (!isCW(strip.m_faces.at(0), tFirstFace.m_v0, 845 tFirstFace.m_v1)) 846 stripIndices.add(tFirstFace.m_v0); 847 } else { 848 // Double tap the first in the new strip 849 stripIndices.add(tFirstFace.m_v0); 850 851 // Check CW/CCW ordering 852 if (nextIsCW(stripIndices.size() - accountForNegatives) != isCW( 853 strip.m_faces.at(0), tFirstFace.m_v0, 854 tFirstFace.m_v1)) { 855 stripIndices.add(tFirstFace.m_v0); 856 } 857 } 858 859 stripIndices.add(tFirstFace.m_v0); 860 stripIndices.add(tFirstFace.m_v1); 861 stripIndices.add(tFirstFace.m_v2); 862 863 // Update last face info 864 tLastFace.set(tFirstFace); 865 } 866 867 for (int j = 1; j < nStripFaceCount; j++) { 868 int nUnique = getUniqueVertexInB(tLastFace, strip.m_faces.at(j)); 869 if (nUnique != -1) { 870 stripIndices.add(nUnique); 871 872 // Update last face info 873 tLastFace.m_v0 = tLastFace.m_v1; 874 tLastFace.m_v1 = tLastFace.m_v2; 875 tLastFace.m_v2 = nUnique; 876 } else { 877 //we've hit a degenerate 878 stripIndices.add(strip.m_faces.at(j).m_v2); 879 tLastFace.m_v0 = strip.m_faces.at(j).m_v0; //tLastFace.m_v1; 880 tLastFace.m_v1 = strip.m_faces.at(j).m_v1; //tLastFace.m_v2; 881 tLastFace.m_v2 = strip.m_faces.at(j).m_v2; //tLastFace.m_v1; 882 883 } 884 } 885 886 // Double tap between strips. 887 if (bStitchStrips) { 888 if (i != nStripCount - 1) 889 stripIndices.add(tLastFace.m_v2); 890 } else { 891 //-1 index indicates next strip 892 stripIndices.add(-1); 893 accountForNegatives++; 894 numSeparateStrips++; 895 } 896 897 // Update last face info 898 tLastFace.m_v0 = tLastFace.m_v1; 899 tLastFace.m_v1 = tLastFace.m_v2; 900 tLastFace.m_v2 = tLastFace.m_v2; 901 } 902 903 if (bStitchStrips) 904 numSeparateStrips = 1; 905 return numSeparateStrips; 906 } 907 908 /////////////////////////////////////////////////////////////////////////////////////////// 909 // FindAllStrips() 910 // 911 // Does the stripification, puts output strips into vector allStrips 912 // 913 // Works by setting runnning a number of experiments in different areas of 914 // the mesh, and 915 // accepting the one which results in the longest strips. It then accepts 916 // this, and moves 917 // on to a different area of the mesh. We try to jump around the mesh some, 918 // to ensure that 919 // large open spans of strips get generated. 920 // findAllStrips(StripInfoVec allStrips, FaceInfoVec allFaceInfos, EdgeInfoVec allEdgeInfos, int numSamples)921 void findAllStrips(StripInfoVec allStrips, FaceInfoVec allFaceInfos, 922 EdgeInfoVec allEdgeInfos, int numSamples) { 923 // the experiments 924 int experimentId = 0; 925 int stripId = 0; 926 boolean done = false; 927 928 int loopCtr = 0; 929 930 while (!done) { 931 loopCtr++; 932 933 // 934 // PHASE 1: Set up numSamples * numEdges experiments 935 // 936 StripInfoVec[] experiments = new StripInfoVec[numSamples * 6]; 937 for (int i = 0; i < experiments.length; i++) 938 experiments[i] = new StripInfoVec(); 939 940 int experimentIndex = 0; 941 HashSet<FaceInfo> resetPoints = new HashSet<FaceInfo>(); /* NvFaceInfo */ 942 for (int i = 0; i < numSamples; i++) { 943 // Try to find another good reset point. 944 // If there are none to be found, we are done 945 FaceInfo nextFace = findGoodResetPoint(allFaceInfos, 946 allEdgeInfos); 947 if (nextFace == null) { 948 done = true; 949 break; 950 } 951 // If we have already evaluated starting at this face in this 952 // slew of experiments, then skip going any further 953 else if (resetPoints.contains(nextFace)) { 954 continue; 955 } 956 957 // trying it now... 958 resetPoints.add(nextFace); 959 960 // otherwise, we shall now try experiments for starting on the 961 // 01,12, and 20 edges 962 963 // build the strip off of this face's 0-1 edge 964 EdgeInfo edge01 = findEdgeInfo(allEdgeInfos, nextFace.m_v0, 965 nextFace.m_v1); 966 StripInfo strip01 = new StripInfo(new StripStartInfo(nextFace, 967 edge01, true), stripId++, experimentId++); 968 experiments[experimentIndex++].add(strip01); 969 970 // build the strip off of this face's 1-0 edge 971 EdgeInfo edge10 = findEdgeInfo(allEdgeInfos, nextFace.m_v0, 972 nextFace.m_v1); 973 StripInfo strip10 = new StripInfo(new StripStartInfo(nextFace, 974 edge10, false), stripId++, experimentId++); 975 experiments[experimentIndex++].add(strip10); 976 977 // build the strip off of this face's 1-2 edge 978 EdgeInfo edge12 = findEdgeInfo(allEdgeInfos, nextFace.m_v1, 979 nextFace.m_v2); 980 StripInfo strip12 = new StripInfo(new StripStartInfo(nextFace, 981 edge12, true), stripId++, experimentId++); 982 experiments[experimentIndex++].add(strip12); 983 984 // build the strip off of this face's 2-1 edge 985 EdgeInfo edge21 = findEdgeInfo(allEdgeInfos, nextFace.m_v1, 986 nextFace.m_v2); 987 StripInfo strip21 = new StripInfo(new StripStartInfo(nextFace, 988 edge21, false), stripId++, experimentId++); 989 experiments[experimentIndex++].add(strip21); 990 991 // build the strip off of this face's 2-0 edge 992 EdgeInfo edge20 = findEdgeInfo(allEdgeInfos, nextFace.m_v2, 993 nextFace.m_v0); 994 StripInfo strip20 = new StripInfo(new StripStartInfo(nextFace, 995 edge20, true), stripId++, experimentId++); 996 experiments[experimentIndex++].add(strip20); 997 998 // build the strip off of this face's 0-2 edge 999 EdgeInfo edge02 = findEdgeInfo(allEdgeInfos, nextFace.m_v2, 1000 nextFace.m_v0); 1001 StripInfo strip02 = new StripInfo(new StripStartInfo(nextFace, 1002 edge02, false), stripId++, experimentId++); 1003 experiments[experimentIndex++].add(strip02); 1004 } 1005 1006 // 1007 // PHASE 2: Iterate through that we setup in the last phase 1008 // and really build each of the strips and strips that follow to 1009 // see how 1010 // far we get 1011 // 1012 int numExperiments = experimentIndex; 1013 for (int i = 0; i < numExperiments; i++) { 1014 1015 // get the strip set 1016 1017 // build the first strip of the list 1018 experiments[i].at(0).build(allEdgeInfos, allFaceInfos); 1019 int experimentId2 = experiments[i].at(0).m_experimentId; 1020 1021 StripInfo stripIter = experiments[i].at(0); 1022 StripStartInfo startInfo = new StripStartInfo(null, null, false); 1023 while (findTraversal(allFaceInfos, allEdgeInfos, stripIter, 1024 startInfo)) { 1025 1026 // create the new strip info 1027 //TODO startInfo clone ? 1028 stripIter = new StripInfo(startInfo, stripId++, 1029 experimentId2); 1030 1031 // build the next strip 1032 stripIter.build(allEdgeInfos, allFaceInfos); 1033 1034 // add it to the list 1035 experiments[i].add(stripIter); 1036 } 1037 } 1038 1039 // 1040 // Phase 3: Find the experiment that has the most promise 1041 // 1042 int bestIndex = 0; 1043 double bestValue = 0; 1044 for (int i = 0; i < numExperiments; i++) { 1045 float avgStripSizeWeight = 1.0f; 1046 //float numTrisWeight = 0.0f; 1047 float numStripsWeight = 0.0f; 1048 float avgStripSize = avgStripSize(experiments[i]); 1049 float numStrips = experiments[i].size(); 1050 float value = avgStripSize * avgStripSizeWeight 1051 + (numStrips * numStripsWeight); 1052 //float value = 1.f / numStrips; 1053 //float value = numStrips * avgStripSize; 1054 1055 if (value > bestValue) { 1056 bestValue = value; 1057 bestIndex = i; 1058 } 1059 } 1060 1061 // 1062 // Phase 4: commit the best experiment of the bunch 1063 // 1064 commitStrips(allStrips, experiments[bestIndex]); 1065 } 1066 } 1067 1068 /////////////////////////////////////////////////////////////////////////////////////////// 1069 // SplitUpStripsAndOptimize() 1070 // 1071 // Splits the input vector of strips (allBigStrips) into smaller, cache 1072 // friendly pieces, then 1073 // reorders these pieces to maximize cache hits 1074 // The final strips are output through outStrips 1075 // splitUpStripsAndOptimize(StripInfoVec allStrips, StripInfoVec outStrips, EdgeInfoVec edgeInfos, FaceInfoVec outFaceList)1076 void splitUpStripsAndOptimize(StripInfoVec allStrips, 1077 StripInfoVec outStrips, EdgeInfoVec edgeInfos, 1078 FaceInfoVec outFaceList) { 1079 int threshold = cacheSize; 1080 StripInfoVec tempStrips = new StripInfoVec(); 1081 int j; 1082 1083 //split up strips into threshold-sized pieces 1084 for (int i = 0; i < allStrips.size(); i++) { 1085 StripInfo currentStrip; 1086 StripStartInfo startInfo = new StripStartInfo(null, null, false); 1087 1088 int actualStripSize = 0; 1089 for (j = 0; j < allStrips.at(i).m_faces.size(); ++j) { 1090 if (!isDegenerate(allStrips.at(i).m_faces.at(j))) 1091 actualStripSize++; 1092 } 1093 1094 if (actualStripSize /* allStrips.at(i).m_faces.size() */ 1095 > threshold) { 1096 1097 int numTimes = actualStripSize /* allStrips.at(i).m_faces.size() */ 1098 / threshold; 1099 int numLeftover = actualStripSize /* allStrips.at(i).m_faces.size() */ 1100 % threshold; 1101 1102 int degenerateCount = 0; 1103 for (j = 0; j < numTimes; j++) { 1104 currentStrip = new StripInfo(startInfo, 0, -1); 1105 1106 int faceCtr = j * threshold + degenerateCount; 1107 boolean bFirstTime = true; 1108 while (faceCtr < threshold + (j * threshold) 1109 + degenerateCount) { 1110 if (isDegenerate(allStrips.at(i).m_faces.at(faceCtr))) { 1111 degenerateCount++; 1112 1113 //last time or first time through, no need for a 1114 // degenerate 1115 if ((((faceCtr + 1) != threshold + (j * threshold) 1116 + degenerateCount) || ((j == numTimes - 1) 1117 && (numLeftover < 4) && (numLeftover > 0))) 1118 && !bFirstTime) { 1119 currentStrip.m_faces 1120 .add(allStrips.at(i).m_faces 1121 .at(faceCtr++)); 1122 } else 1123 ++faceCtr; 1124 } else { 1125 currentStrip.m_faces.add(allStrips.at(i).m_faces 1126 .at(faceCtr++)); 1127 bFirstTime = false; 1128 } 1129 } 1130 /* 1131 * threshold; faceCtr < threshold+(j*threshold); faceCtr++) { 1132 * currentStrip.m_faces.add(allStrips.at(i).m_faces.at(faceCtr]); } 1133 */ 1134 ///* 1135 if (j == numTimes - 1) //last time through 1136 { 1137 if ((numLeftover < 4) && (numLeftover > 0)) //way too 1138 // small 1139 { 1140 //just add to last strip 1141 int ctr = 0; 1142 while (ctr < numLeftover) { 1143 if (!isDegenerate(allStrips.at(i).m_faces 1144 .at(faceCtr))) { 1145 currentStrip.m_faces 1146 .add(allStrips.at(i).m_faces 1147 .at(faceCtr++)); 1148 ++ctr; 1149 } else { 1150 currentStrip.m_faces 1151 .add(allStrips.at(i).m_faces 1152 .at(faceCtr++)); 1153 ++degenerateCount; 1154 } 1155 } 1156 numLeftover = 0; 1157 } 1158 } 1159 //*/ 1160 tempStrips.add(currentStrip); 1161 } 1162 1163 int leftOff = j * threshold + degenerateCount; 1164 1165 if (numLeftover != 0) { 1166 currentStrip = new StripInfo(startInfo, 0, -1); 1167 1168 int ctr = 0; 1169 boolean bFirstTime = true; 1170 while (ctr < numLeftover) { 1171 if (!isDegenerate(allStrips.at(i).m_faces.at(leftOff))) { 1172 ctr++; 1173 bFirstTime = false; 1174 currentStrip.m_faces.add(allStrips.at(i).m_faces 1175 .at(leftOff++)); 1176 } else if (!bFirstTime) 1177 currentStrip.m_faces.add(allStrips.at(i).m_faces 1178 .at(leftOff++)); 1179 else 1180 leftOff++; 1181 } 1182 /* 1183 * for(int k = 0; k < numLeftover; k++) { 1184 * currentStrip.m_faces.add(allStrips.at(i).m_faces[leftOff++]); } 1185 */ 1186 1187 tempStrips.add(currentStrip); 1188 } 1189 } else { 1190 //we're not just doing a tempStrips.add(allBigStrips[i]) 1191 // because 1192 // this way we can delete allBigStrips later to free the memory 1193 currentStrip = new StripInfo(startInfo, 0, -1); 1194 1195 for (j = 0; j < allStrips.at(i).m_faces.size(); j++) 1196 currentStrip.m_faces.add(allStrips.at(i).m_faces.at(j)); 1197 1198 tempStrips.add(currentStrip); 1199 } 1200 } 1201 1202 //add small strips to face list 1203 StripInfoVec tempStrips2 = new StripInfoVec(); 1204 removeSmallStrips(tempStrips, tempStrips2, outFaceList); 1205 1206 outStrips.clear(); 1207 //screw optimization for now 1208 // for(i = 0; i < tempStrips.size(); ++i) 1209 // outStrips.add(tempStrips[i]); 1210 1211 if (tempStrips2.size() != 0) { 1212 //Optimize for the vertex cache 1213 VertexCache vcache = new VertexCache(cacheSize); 1214 1215 float bestNumHits = -1.0f; 1216 float numHits; 1217 int bestIndex = -99999; 1218 1219 int firstIndex = 0; 1220 float minCost = 10000.0f; 1221 1222 for (int i = 0; i < tempStrips2.size(); i++) { 1223 int numNeighbors = 0; 1224 1225 //find strip with least number of neighbors per face 1226 for (j = 0; j < tempStrips2.at(i).m_faces.size(); j++) { 1227 numNeighbors += numNeighbors(tempStrips2.at(i).m_faces 1228 .at(j), edgeInfos); 1229 } 1230 1231 float currCost = (float) numNeighbors 1232 / (float) tempStrips2.at(i).m_faces.size(); 1233 if (currCost < minCost) { 1234 minCost = currCost; 1235 firstIndex = i; 1236 } 1237 } 1238 1239 updateCacheStrip(vcache, tempStrips2.at(firstIndex)); 1240 outStrips.add(tempStrips2.at(firstIndex)); 1241 1242 tempStrips2.at(firstIndex).visited = true; 1243 1244 boolean bWantsCW = (tempStrips2.at(firstIndex).m_faces.size() % 2) == 0; 1245 1246 //this n^2 algo is what slows down stripification so much.... 1247 // needs to be improved 1248 while (true) { 1249 bestNumHits = -1.0f; 1250 1251 //find best strip to add next, given the current cache 1252 for (int i = 0; i < tempStrips2.size(); i++) { 1253 if (tempStrips2.at(i).visited) 1254 continue; 1255 1256 numHits = calcNumHitsStrip(vcache, tempStrips2.at(i)); 1257 if (numHits > bestNumHits) { 1258 bestNumHits = numHits; 1259 bestIndex = i; 1260 } else if (numHits >= bestNumHits) { 1261 //check previous strip to see if this one requires it 1262 // to switch polarity 1263 StripInfo strip = tempStrips2.at(i); 1264 int nStripFaceCount = strip.m_faces.size(); 1265 1266 FaceInfo tFirstFace = new FaceInfo( 1267 strip.m_faces.at(0).m_v0, 1268 strip.m_faces.at(0).m_v1, 1269 strip.m_faces.at(0).m_v2); 1270 1271 // If there is a second face, reorder vertices such 1272 // that the 1273 // unique vertex is first 1274 if (nStripFaceCount > 1) { 1275 int nUnique = getUniqueVertexInB(strip.m_faces 1276 .at(1), tFirstFace); 1277 if (nUnique == tFirstFace.m_v1) { 1278 int tmp = tFirstFace.m_v0; 1279 tFirstFace.m_v0 = tFirstFace.m_v1; 1280 tFirstFace.m_v1 = tmp; 1281 } else if (nUnique == tFirstFace.m_v2) { 1282 int tmp = tFirstFace.m_v0; 1283 tFirstFace.m_v0 = tFirstFace.m_v2; 1284 tFirstFace.m_v2 = tmp; 1285 } 1286 1287 // If there is a third face, reorder vertices such 1288 // that the 1289 // shared vertex is last 1290 if (nStripFaceCount > 2) { 1291 int[] nShared = new int[2]; 1292 getSharedVertices(strip.m_faces.at(2), 1293 tFirstFace, nShared); 1294 if ((nShared[0] == tFirstFace.m_v1) 1295 && (nShared[1] == -1)) { 1296 int tmp = tFirstFace.m_v2; 1297 tFirstFace.m_v2 = tFirstFace.m_v1; 1298 tFirstFace.m_v1 = tmp; 1299 } 1300 } 1301 } 1302 1303 // Check CW/CCW ordering 1304 if (bWantsCW == isCW(strip.m_faces.at(0), 1305 tFirstFace.m_v0, tFirstFace.m_v1)) { 1306 //I like this one! 1307 bestIndex = i; 1308 } 1309 } 1310 } 1311 1312 if (bestNumHits == -1.0f) 1313 break; 1314 tempStrips2.at(bestIndex).visited = true; 1315 updateCacheStrip(vcache, tempStrips2.at(bestIndex)); 1316 outStrips.add(tempStrips2.at(bestIndex)); 1317 bWantsCW = (tempStrips2.at(bestIndex).m_faces.size() % 2 == 0) ? bWantsCW 1318 : !bWantsCW; 1319 } 1320 } 1321 } 1322 1323 /////////////////////////////////////////////////////////////////////////////////////////// 1324 // Stripify() 1325 // 1326 // 1327 // in_indices are the input indices of the mesh to stripify 1328 // in_cacheSize is the target cache size 1329 // stripify(IntVec in_indices, int in_cacheSize, int in_minStripLength, int maxIndex, StripInfoVec outStrips, FaceInfoVec outFaceList)1330 void stripify(IntVec in_indices, int in_cacheSize, int in_minStripLength, 1331 int maxIndex, StripInfoVec outStrips, FaceInfoVec outFaceList) { 1332 meshJump = 0.0f; 1333 bFirstTimeResetPoint = true; //used in FindGoodResetPoint() 1334 1335 //the number of times to run the experiments 1336 int numSamples = 10; 1337 1338 //the cache size, clamped to one 1339 cacheSize = Math.max(1, in_cacheSize - CACHE_INEFFICIENCY); 1340 1341 minStripLength = in_minStripLength; 1342 //this is the strip size threshold below which we dump the strip into 1343 // a list 1344 1345 indices = in_indices; 1346 1347 // build the stripification info 1348 FaceInfoVec allFaceInfos = new FaceInfoVec(); 1349 EdgeInfoVec allEdgeInfos = new EdgeInfoVec(); 1350 1351 buildStripifyInfo(allFaceInfos, allEdgeInfos, maxIndex); 1352 1353 StripInfoVec allStrips = new StripInfoVec(); 1354 1355 // stripify 1356 findAllStrips(allStrips, allFaceInfos, allEdgeInfos, numSamples); 1357 1358 //split up the strips into cache friendly pieces, optimize them, then 1359 // dump these into outStrips 1360 splitUpStripsAndOptimize(allStrips, outStrips, allEdgeInfos, 1361 outFaceList); 1362 1363 } 1364 1365 }