1 /****************************************************************************** 2 3 @File PVRTTriStrip.cpp 4 5 @Title PVRTTriStrip 6 7 @Version @Version 8 9 @Copyright Copyright (c) Imagination Technologies Limited. 10 11 @Platform Independent 12 13 @Description Strips a triangle list. 14 15 ******************************************************************************/ 16 17 /**************************************************************************** 18 ** Includes 19 ****************************************************************************/ 20 #include <stdlib.h> 21 22 #include "PVRTGlobal.h" 23 #include "PVRTContext.h" 24 #include "PVRTTriStrip.h" 25 26 /**************************************************************************** 27 ** Defines 28 ****************************************************************************/ 29 #define RND_TRIS_ORDER 30 31 /**************************************************************************** 32 ** Structures 33 ****************************************************************************/ 34 35 /**************************************************************************** 36 ** Class: CTri 37 ****************************************************************************/ 38 class CTri; 39 40 /*!*************************************************************************** 41 @Class CTriState 42 @Description Stores a pointer to the triangles either side of itself, 43 as well as it's winding. 44 *****************************************************************************/ 45 class CTriState 46 { 47 public: 48 CTri *pRev, *pFwd; 49 bool bWindFwd; 50 51 CTriState() 52 { 53 bWindFwd = true; // Initial value irrelevent 54 pRev = NULL; 55 pFwd = NULL; 56 } 57 }; 58 /*!*************************************************************************** 59 @Class CTri 60 @Description Object used to store information about the triangle, such as 61 the vertex indices it is made from, which triangles are 62 adjacent to it, etc. 63 *****************************************************************************/ 64 class CTri 65 { 66 public: 67 CTriState sNew, sOld; 68 69 CTri *pAdj[3]; 70 bool bInStrip; 71 72 const unsigned int *pIdx; // three indices for the tri 73 bool bOutput; 74 75 public: 76 CTri(); 77 int FindEdge(const unsigned int pw0, const unsigned int pw1) const; 78 void Cement(); 79 void Undo(); 80 int EdgeFromAdjTri(const CTri &tri) const; // Find the index of the adjacent tri 81 }; 82 83 /*!*************************************************************************** 84 @Class CStrip 85 @Description Object used to store the triangles that a given strip is 86 composed from. 87 *****************************************************************************/ 88 class CStrip 89 { 90 protected: 91 unsigned int m_nTriCnt; 92 CTri *m_pTri; 93 unsigned int m_nStrips; 94 95 CTri **m_psStrip; // Working space for finding strips 96 97 public: 98 CStrip( 99 const unsigned int * const pui32TriList, 100 const unsigned int nTriCnt); 101 ~CStrip(); 102 103 protected: 104 bool StripGrow( 105 CTri &triFrom, 106 const unsigned int nEdgeFrom, 107 const int nMaxChange); 108 109 public: 110 void StripFromEdges(); 111 void StripImprove(); 112 113 void Output( 114 unsigned int **ppui32Strips, 115 unsigned int **ppnStripLen, 116 unsigned int *pnStripCnt); 117 }; 118 119 /**************************************************************************** 120 ** Constants 121 ****************************************************************************/ 122 123 /**************************************************************************** 124 ** Code: Class: CTri 125 ****************************************************************************/ 126 CTri::CTri() 127 { 128 pAdj[0] = NULL; 129 pAdj[1] = NULL; 130 pAdj[2] = NULL; 131 bInStrip = false; 132 bOutput = false; 133 } 134 135 /*!*************************************************************************** 136 @Function FindEdge 137 @Input pw0 The first index 138 @Input pw1 The second index 139 @Return The index of the edge 140 @Description Finds the index of the edge that the current object shares 141 with the two vertex index values that have been passed in 142 (or returns -1 if they dont share an edge). 143 *****************************************************************************/ 144 int CTri::FindEdge(const unsigned int pw0, const unsigned int pw1) const 145 { 146 if((pIdx[0] == pw0 && pIdx[1] == pw1)) 147 return 0; 148 if((pIdx[1] == pw0 && pIdx[2] == pw1)) 149 return 1; 150 if((pIdx[2] == pw0 && pIdx[0] == pw1)) 151 return 2; 152 return -1; 153 } 154 /*!*************************************************************************** 155 @Function Cement 156 @Description Assigns the new state as the old state. 157 *****************************************************************************/ 158 void CTri::Cement() 159 { 160 sOld = sNew; 161 } 162 /*!*************************************************************************** 163 @Function Undo 164 @Description Reverts the new state to the old state. 165 *****************************************************************************/ 166 void CTri::Undo() 167 { 168 sNew = sOld; 169 } 170 /*!*************************************************************************** 171 @Function EdgeFromAdjTri 172 @Input tri The triangle to compare 173 @Return int Index of adjacent triangle (-1 if not adjacent) 174 @Description If the input triangle is adjacent to the current triangle, 175 it's index is returned. 176 *****************************************************************************/ 177 int CTri::EdgeFromAdjTri(const CTri &tri) const 178 { 179 for(int i = 0; i < 3; ++i) 180 { 181 if(pAdj[i] == &tri) 182 { 183 return i; 184 } 185 } 186 _ASSERT(false); 187 return -1; 188 } 189 190 /**************************************************************************** 191 ** Local code 192 ****************************************************************************/ 193 /*!*************************************************************************** 194 @Function OrphanTri 195 @Input tri The triangle test 196 @Return int Returns 1 if change was made 197 @Description If the input triangle is not wound forward and is not the last 198 triangle in the strip, the connection with the next triangle 199 in the strip is removed. 200 *****************************************************************************/ 201 static int OrphanTri( 202 CTri * const pTri) 203 { 204 _ASSERT(!pTri->bInStrip); 205 if(pTri->sNew.bWindFwd || !pTri->sNew.pFwd) 206 return 0; 207 208 pTri->sNew.pFwd->sNew.pRev = NULL; 209 pTri->sNew.pFwd = NULL; 210 return 1; 211 } 212 /*!*************************************************************************** 213 @Function TakeTri 214 @Input pTri The triangle to take 215 @Input pRevNew The triangle that is before pTri in the new strip 216 @Return int Returns 1 if a new strip has been created 217 @Description Removes the triangle from it's current strip 218 and places it in a new one (following pRevNew in the new strip). 219 *****************************************************************************/ 220 static int TakeTri( 221 CTri * const pTri, 222 CTri * const pRevNew, 223 const bool bFwd) 224 { 225 int nRet; 226 227 _ASSERT(!pTri->bInStrip); 228 229 if(pTri->sNew.pFwd && pTri->sNew.pRev) 230 { 231 _ASSERT(pTri->sNew.pFwd->sNew.pRev == pTri); 232 pTri->sNew.pFwd->sNew.pRev = NULL; 233 _ASSERT(pTri->sNew.pRev->sNew.pFwd == pTri); 234 pTri->sNew.pRev->sNew.pFwd = NULL; 235 236 // If in the middle of a Strip, this will generate a new Strip 237 nRet = 1; 238 239 // The second tri in the strip may need to be orphaned, or it will have wrong winding order 240 nRet += OrphanTri(pTri->sNew.pFwd); 241 } 242 else if(pTri->sNew.pFwd) 243 { 244 _ASSERT(pTri->sNew.pFwd->sNew.pRev == pTri); 245 pTri->sNew.pFwd->sNew.pRev = NULL; 246 247 // If at the beginning of a Strip, no change 248 nRet = 0; 249 250 // The second tri in the strip may need to be orphaned, or it will have wrong winding order 251 nRet += OrphanTri(pTri->sNew.pFwd); 252 } 253 else if(pTri->sNew.pRev) 254 { 255 _ASSERT(pTri->sNew.pRev->sNew.pFwd == pTri); 256 pTri->sNew.pRev->sNew.pFwd = NULL; 257 258 // If at the end of a Strip, no change 259 nRet = 0; 260 } 261 else 262 { 263 // Otherwise it's a lonesome triangle; one Strip removed! 264 nRet = -1; 265 } 266 267 pTri->sNew.pFwd = NULL; 268 pTri->sNew.pRev = pRevNew; 269 pTri->bInStrip = true; 270 pTri->sNew.bWindFwd = bFwd; 271 272 if(pRevNew) 273 { 274 _ASSERT(!pRevNew->sNew.pFwd); 275 pRevNew->sNew.pFwd = pTri; 276 } 277 278 return nRet; 279 } 280 /*!*************************************************************************** 281 @Function TryLinkEdge 282 @Input src The source triangle 283 @Input cmp The triangle to compare with 284 @Input nSrcEdge The edge of souce triangle to compare 285 @Input idx0 Vertex index 0 of the compare triangle 286 @Input idx1 Vertex index 1 of the compare triangle 287 @Description If the triangle to compare currently has no adjacent 288 triangle along the specified edge, link the source triangle 289 (along it's specified edge) with the compare triangle. 290 *****************************************************************************/ 291 static bool TryLinkEdge( 292 CTri &src, 293 CTri &cmp, 294 const int nSrcEdge, 295 const unsigned int idx0, 296 const unsigned int idx1) 297 { 298 int nCmpEdge; 299 300 nCmpEdge = cmp.FindEdge(idx0, idx1); 301 if(nCmpEdge != -1 && !cmp.pAdj[nCmpEdge]) 302 { 303 cmp.pAdj[nCmpEdge] = &src; 304 src.pAdj[nSrcEdge] = &cmp; 305 return true; 306 } 307 return false; 308 } 309 310 /**************************************************************************** 311 ** Code: Class: CStrip 312 ****************************************************************************/ 313 CStrip::CStrip( 314 const unsigned int * const pui32TriList, 315 const unsigned int nTriCnt) 316 { 317 unsigned int i, j; 318 bool b0, b1, b2; 319 320 m_nTriCnt = nTriCnt; 321 322 /* 323 Generate adjacency info 324 */ 325 m_pTri = new CTri[nTriCnt]; 326 for(i = 0; i < nTriCnt; ++i) 327 { 328 // Set pointer to indices 329 m_pTri[i].pIdx = &pui32TriList[3 * i]; 330 331 b0 = false; 332 b1 = false; 333 b2 = false; 334 for(j = 0; j < i && !(b0 & b1 & b2); ++j) 335 { 336 if(!b0) 337 b0 = TryLinkEdge(m_pTri[i], m_pTri[j], 0, m_pTri[i].pIdx[1], m_pTri[i].pIdx[0]); 338 339 if(!b1) 340 b1 = TryLinkEdge(m_pTri[i], m_pTri[j], 1, m_pTri[i].pIdx[2], m_pTri[i].pIdx[1]); 341 342 if(!b2) 343 b2 = TryLinkEdge(m_pTri[i], m_pTri[j], 2, m_pTri[i].pIdx[0], m_pTri[i].pIdx[2]); 344 } 345 } 346 347 // Initially, every triangle is a strip. 348 m_nStrips = m_nTriCnt; 349 350 // Allocate working space for the strippers 351 m_psStrip = new CTri*[m_nTriCnt]; 352 } 353 354 CStrip::~CStrip() 355 { 356 delete [] m_pTri; 357 delete [] m_psStrip; 358 } 359 /*!*************************************************************************** 360 @Function StripGrow 361 @Input triFrom The triangle to begin from 362 @Input nEdgeFrom The edge of the triangle to begin from 363 @Input maxChange The maximum number of changes to be made 364 @Description Takes triFrom as a starting point of triangles to add to 365 the list and adds triangles sequentially by finding the next 366 triangle that is adjacent to the current triangle. 367 This is repeated until the maximum number of changes 368 have been made. 369 *****************************************************************************/ 370 bool CStrip::StripGrow( 371 CTri &triFrom, 372 const unsigned int nEdgeFrom, 373 const int nMaxChange) 374 { 375 unsigned int i; 376 bool bFwd; 377 int nDiff, nDiffTot, nEdge; 378 CTri *pTri, *pTriPrev, *pTmp; 379 unsigned int nStripLen; 380 381 // Start strip from this tri 382 pTri = &triFrom; 383 pTriPrev = NULL; 384 385 nDiffTot = 0; 386 nStripLen = 0; 387 388 // Start strip from this edge 389 nEdge = nEdgeFrom; 390 bFwd = true; 391 392 // Extend the strip until we run out, or we find an improvement 393 nDiff = 1; 394 while(nDiff > nMaxChange) 395 { 396 // Add pTri to the strip 397 _ASSERT(pTri); 398 nDiff += TakeTri(pTri, pTriPrev, bFwd); 399 _ASSERT(nStripLen < m_nTriCnt); 400 m_psStrip[nStripLen++] = pTri; 401 402 // Jump to next tri 403 pTriPrev = pTri; 404 pTri = pTri->pAdj[nEdge]; 405 if(!pTri) 406 break; // No more tris, gotta stop 407 408 if(pTri->bInStrip) 409 break; // No more tris, gotta stop 410 411 // Find which edge we came over 412 nEdge = pTri->EdgeFromAdjTri(*pTriPrev); 413 414 // Find the edge to leave over 415 if(bFwd) 416 { 417 if(--nEdge < 0) 418 nEdge = 2; 419 } 420 else 421 { 422 if(++nEdge > 2) 423 nEdge = 0; 424 } 425 426 // Swap the winding order for the next tri 427 bFwd = !bFwd; 428 } 429 _ASSERT(!pTriPrev->sNew.pFwd); 430 431 /* 432 Accept or reject this strip. 433 434 Accepting changes which don't change the number of strips 435 adds variety, which can help better strips to develop. 436 */ 437 if(nDiff <= nMaxChange) 438 { 439 nDiffTot += nDiff; 440 441 // Great, take the Strip 442 for(i = 0; i < nStripLen; ++i) 443 { 444 pTri = m_psStrip[i]; 445 _ASSERT(pTri->bInStrip); 446 447 // Cement affected tris 448 pTmp = pTri->sOld.pFwd; 449 if(pTmp && !pTmp->bInStrip) 450 { 451 if(pTmp->sOld.pFwd && !pTmp->sOld.pFwd->bInStrip) 452 pTmp->sOld.pFwd->Cement(); 453 pTmp->Cement(); 454 } 455 456 pTmp = pTri->sOld.pRev; 457 if(pTmp && !pTmp->bInStrip) 458 { 459 pTmp->Cement(); 460 } 461 462 // Cement this tris 463 pTri->bInStrip = false; 464 pTri->Cement(); 465 } 466 } 467 else 468 { 469 // Shame, undo the strip 470 for(i = 0; i < nStripLen; ++i) 471 { 472 pTri = m_psStrip[i]; 473 _ASSERT(pTri->bInStrip); 474 475 // Undo affected tris 476 pTmp = pTri->sOld.pFwd; 477 if(pTmp && !pTmp->bInStrip) 478 { 479 if(pTmp->sOld.pFwd && !pTmp->sOld.pFwd->bInStrip) 480 pTmp->sOld.pFwd->Undo(); 481 pTmp->Undo(); 482 } 483 484 pTmp = pTri->sOld.pRev; 485 if(pTmp && !pTmp->bInStrip) 486 { 487 pTmp->Undo(); 488 } 489 490 // Undo this tris 491 pTri->bInStrip = false; 492 pTri->Undo(); 493 } 494 } 495 496 #ifdef _DEBUG 497 for(int nDbg = 0; nDbg < (int)m_nTriCnt; ++nDbg) 498 { 499 _ASSERT(m_pTri[nDbg].bInStrip == false); 500 _ASSERT(m_pTri[nDbg].bOutput == false); 501 _ASSERT(m_pTri[nDbg].sOld.pRev == m_pTri[nDbg].sNew.pRev); 502 _ASSERT(m_pTri[nDbg].sOld.pFwd == m_pTri[nDbg].sNew.pFwd); 503 504 if(m_pTri[nDbg].sNew.pRev) 505 { 506 _ASSERT(m_pTri[nDbg].sNew.pRev->sNew.pFwd == &m_pTri[nDbg]); 507 } 508 509 if(m_pTri[nDbg].sNew.pFwd) 510 { 511 _ASSERT(m_pTri[nDbg].sNew.pFwd->sNew.pRev == &m_pTri[nDbg]); 512 } 513 } 514 #endif 515 516 if(nDiffTot) 517 { 518 m_nStrips += nDiffTot; 519 return true; 520 } 521 return false; 522 } 523 524 /*!*************************************************************************** 525 @Function StripFromEdges 526 @Description Creates a strip from the object's edge information. 527 *****************************************************************************/ 528 void CStrip::StripFromEdges() 529 { 530 unsigned int i, j, nTest; 531 CTri *pTri, *pTriPrev; 532 int nEdge = 0; 533 534 /* 535 Attempt to create grid-oriented strips. 536 */ 537 for(i = 0; i < m_nTriCnt; ++i) 538 { 539 pTri = &m_pTri[i]; 540 541 // Count the number of empty edges 542 nTest = 0; 543 for(j = 0; j < 3; ++j) 544 { 545 if(!pTri->pAdj[j]) 546 { 547 ++nTest; 548 } 549 else 550 { 551 nEdge = j; 552 } 553 } 554 555 if(nTest != 2) 556 continue; 557 558 for(;;) 559 { 560 // A tri with two empty edges is a corner (there are other corners too, but this works so...) 561 while(StripGrow(*pTri, nEdge, -1)) {}; 562 563 pTriPrev = pTri; 564 pTri = pTri->pAdj[nEdge]; 565 if(!pTri) 566 break; 567 568 // Find the edge we came over 569 nEdge = pTri->EdgeFromAdjTri(*pTriPrev); 570 571 // Step around to the next edge 572 if(++nEdge > 2) 573 nEdge = 0; 574 575 pTriPrev = pTri; 576 pTri = pTri->pAdj[nEdge]; 577 if(!pTri) 578 break; 579 580 // Find the edge we came over 581 nEdge = pTri->EdgeFromAdjTri(*pTriPrev); 582 583 // Step around to the next edge 584 if(--nEdge < 0) 585 nEdge = 2; 586 587 #if 0 588 // If we're not tracking the edge, give up 589 nTest = nEdge - 1; 590 if(nTest < 0) 591 nTest = 2; 592 if(pTri->pAdj[nTest]) 593 break; 594 else 595 continue; 596 #endif 597 } 598 } 599 } 600 601 #ifdef RND_TRIS_ORDER 602 struct pair 603 { 604 unsigned int i, o; 605 }; 606 607 static int compare(const void *arg1, const void *arg2) 608 { 609 return ((pair*)arg1)->i - ((pair*)arg2)->i; 610 } 611 #endif 612 /*!*************************************************************************** 613 @Function StripImprove 614 @Description Optimises the strip 615 *****************************************************************************/ 616 void CStrip::StripImprove() 617 { 618 unsigned int i, j; 619 bool bChanged; 620 int nRepCnt, nChecks; 621 int nMaxChange; 622 #ifdef RND_TRIS_ORDER 623 pair *pnOrder; 624 625 /* 626 Create a random order to process the tris 627 */ 628 pnOrder = new pair[m_nTriCnt]; 629 #endif 630 631 nRepCnt = 0; 632 nChecks = 2; 633 nMaxChange = 0; 634 635 /* 636 Reduce strip count by growing each of the three strips each tri can start. 637 */ 638 while(nChecks) 639 { 640 --nChecks; 641 642 bChanged = false; 643 644 #ifdef RND_TRIS_ORDER 645 /* 646 Create a random order to process the tris 647 */ 648 for(i = 0; i < m_nTriCnt; ++i) 649 { 650 pnOrder[i].i = rand() * rand(); 651 pnOrder[i].o = i; 652 } 653 qsort(pnOrder, m_nTriCnt, sizeof(*pnOrder), compare); 654 #endif 655 656 /* 657 Process the tris 658 */ 659 for(i = 0; i < m_nTriCnt; ++i) 660 { 661 for(j = 0; j < 3; ++j) 662 { 663 #ifdef RND_TRIS_ORDER 664 bChanged |= StripGrow(m_pTri[pnOrder[i].o], j, nMaxChange); 665 #else 666 bChanged |= StripGrow(m_pTri[i], j, nMaxChange); 667 #endif 668 } 669 } 670 ++nRepCnt; 671 672 // Check the results once or twice 673 if(bChanged) 674 nChecks = 2; 675 676 nMaxChange = (nMaxChange == 0 ? -1 : 0); 677 } 678 679 #ifdef RND_TRIS_ORDER 680 delete [] pnOrder; 681 #endif 682 _RPT1(_CRT_WARN, "Reps: %d\n", nRepCnt); 683 } 684 /*!*************************************************************************** 685 @Function Output 686 @Output ppui32Strips 687 @Output ppnStripLen The length of the strip 688 @Output pnStripCnt 689 @Description Outputs key information about the strip to the output 690 parameters. 691 *****************************************************************************/ 692 void CStrip::Output( 693 unsigned int **ppui32Strips, 694 unsigned int **ppnStripLen, 695 unsigned int *pnStripCnt) 696 { 697 unsigned int *pui32Strips; 698 unsigned int *pnStripLen; 699 unsigned int i, j, nIdx, nStrip; 700 CTri *pTri; 701 702 /* 703 Output Strips 704 */ 705 pnStripLen = (unsigned int*)malloc(m_nStrips * sizeof(*pnStripLen)); 706 pui32Strips = (unsigned int*)malloc((m_nTriCnt + m_nStrips * 2) * sizeof(*pui32Strips)); 707 nStrip = 0; 708 nIdx = 0; 709 for(i = 0; i < m_nTriCnt; ++i) 710 { 711 pTri = &m_pTri[i]; 712 713 if(pTri->sNew.pRev) 714 continue; 715 _ASSERT(!pTri->sNew.pFwd || pTri->sNew.bWindFwd); 716 _ASSERT(pTri->bOutput == false); 717 718 if(!pTri->sNew.pFwd) 719 { 720 pui32Strips[nIdx++] = pTri->pIdx[0]; 721 pui32Strips[nIdx++] = pTri->pIdx[1]; 722 pui32Strips[nIdx++] = pTri->pIdx[2]; 723 pnStripLen[nStrip] = 1; 724 pTri->bOutput = true; 725 } 726 else 727 { 728 if(pTri->sNew.pFwd == pTri->pAdj[0]) 729 { 730 pui32Strips[nIdx++] = pTri->pIdx[2]; 731 pui32Strips[nIdx++] = pTri->pIdx[0]; 732 } 733 else if(pTri->sNew.pFwd == pTri->pAdj[1]) 734 { 735 pui32Strips[nIdx++] = pTri->pIdx[0]; 736 pui32Strips[nIdx++] = pTri->pIdx[1]; 737 } 738 else 739 { 740 _ASSERT(pTri->sNew.pFwd == pTri->pAdj[2]); 741 pui32Strips[nIdx++] = pTri->pIdx[1]; 742 pui32Strips[nIdx++] = pTri->pIdx[2]; 743 } 744 745 pnStripLen[nStrip] = 0; 746 do 747 { 748 _ASSERT(pTri->bOutput == false); 749 750 // Increment tris-in-this-strip counter 751 ++pnStripLen[nStrip]; 752 753 // Output the new vertex index 754 for(j = 0; j < 3; ++j) 755 { 756 if( 757 (pui32Strips[nIdx-2] != pTri->pIdx[j]) && 758 (pui32Strips[nIdx-1] != pTri->pIdx[j])) 759 { 760 break; 761 } 762 } 763 _ASSERT(j != 3); 764 pui32Strips[nIdx++] = pTri->pIdx[j]; 765 766 // Double-check that the previous three indices are the indices of this tris (in some order) 767 _ASSERT( 768 ((pui32Strips[nIdx-3] == pTri->pIdx[0]) && (pui32Strips[nIdx-2] == pTri->pIdx[1]) && (pui32Strips[nIdx-1] == pTri->pIdx[2])) || 769 ((pui32Strips[nIdx-3] == pTri->pIdx[1]) && (pui32Strips[nIdx-2] == pTri->pIdx[2]) && (pui32Strips[nIdx-1] == pTri->pIdx[0])) || 770 ((pui32Strips[nIdx-3] == pTri->pIdx[2]) && (pui32Strips[nIdx-2] == pTri->pIdx[0]) && (pui32Strips[nIdx-1] == pTri->pIdx[1])) || 771 ((pui32Strips[nIdx-3] == pTri->pIdx[2]) && (pui32Strips[nIdx-2] == pTri->pIdx[1]) && (pui32Strips[nIdx-1] == pTri->pIdx[0])) || 772 ((pui32Strips[nIdx-3] == pTri->pIdx[1]) && (pui32Strips[nIdx-2] == pTri->pIdx[0]) && (pui32Strips[nIdx-1] == pTri->pIdx[2])) || 773 ((pui32Strips[nIdx-3] == pTri->pIdx[0]) && (pui32Strips[nIdx-2] == pTri->pIdx[2]) && (pui32Strips[nIdx-1] == pTri->pIdx[1]))); 774 775 // Check that the latest three indices are not degenerate 776 _ASSERT(pui32Strips[nIdx-1] != pui32Strips[nIdx-2]); 777 _ASSERT(pui32Strips[nIdx-1] != pui32Strips[nIdx-3]); 778 _ASSERT(pui32Strips[nIdx-2] != pui32Strips[nIdx-3]); 779 780 pTri->bOutput = true; 781 782 // Check that the next triangle is adjacent to this triangle 783 _ASSERT( 784 (pTri->sNew.pFwd == pTri->pAdj[0]) || 785 (pTri->sNew.pFwd == pTri->pAdj[1]) || 786 (pTri->sNew.pFwd == pTri->pAdj[2]) || 787 (!pTri->sNew.pFwd)); 788 // Check that this triangle is adjacent to the next triangle 789 _ASSERT( 790 (!pTri->sNew.pFwd) || 791 (pTri == pTri->sNew.pFwd->pAdj[0]) || 792 (pTri == pTri->sNew.pFwd->pAdj[1]) || 793 (pTri == pTri->sNew.pFwd->pAdj[2])); 794 795 pTri = pTri->sNew.pFwd; 796 } while(pTri); 797 } 798 799 ++nStrip; 800 } 801 _ASSERT(nIdx == m_nTriCnt + m_nStrips * 2); 802 _ASSERT(nStrip == m_nStrips); 803 804 // Check all triangles have been output 805 for(i = 0; i < m_nTriCnt; ++i) 806 { 807 _ASSERT(m_pTri[i].bOutput == true); 808 } 809 810 // Check all triangles are present 811 j = 0; 812 for(i = 0; i < m_nStrips; ++i) 813 { 814 j += pnStripLen[i]; 815 } 816 _ASSERT(j == m_nTriCnt); 817 818 // Output data 819 *pnStripCnt = m_nStrips; 820 *ppui32Strips = pui32Strips; 821 *ppnStripLen = pnStripLen; 822 } 823 824 /**************************************************************************** 825 ** Code 826 ****************************************************************************/ 827 828 /*!*************************************************************************** 829 @Function PVRTTriStrip 830 @Output ppui32Strips 831 @Output ppnStripLen 832 @Output pnStripCnt 833 @Input pui32TriList 834 @Input nTriCnt 835 @Description Reads a triangle list and generates an optimised triangle strip. 836 *****************************************************************************/ 837 void PVRTTriStrip( 838 unsigned int **ppui32Strips, 839 unsigned int **ppnStripLen, 840 unsigned int *pnStripCnt, 841 const unsigned int * const pui32TriList, 842 const unsigned int nTriCnt) 843 { 844 unsigned int *pui32Strips; 845 unsigned int *pnStripLen; 846 unsigned int nStripCnt; 847 848 /* 849 If the order in which triangles are tested as strip roots is 850 randomised, then several attempts can be made. Use the best result. 851 */ 852 for(int i = 0; i < 853 #ifdef RND_TRIS_ORDER 854 5 855 #else 856 1 857 #endif 858 ; ++i) 859 { 860 CStrip stripper(pui32TriList, nTriCnt); 861 862 #ifdef RND_TRIS_ORDER 863 srand(i); 864 #endif 865 866 stripper.StripFromEdges(); 867 stripper.StripImprove(); 868 stripper.Output(&pui32Strips, &pnStripLen, &nStripCnt); 869 870 if(!i || nStripCnt < *pnStripCnt) 871 { 872 if(i) 873 { 874 FREE(*ppui32Strips); 875 FREE(*ppnStripLen); 876 } 877 878 *ppui32Strips = pui32Strips; 879 *ppnStripLen = pnStripLen; 880 *pnStripCnt = nStripCnt; 881 } 882 else 883 { 884 FREE(pui32Strips); 885 FREE(pnStripLen); 886 } 887 } 888 } 889 890 /*!*************************************************************************** 891 @Function PVRTTriStripList 892 @Modified pui32TriList 893 @Input nTriCnt 894 @Description Reads a triangle list and generates an optimised triangle strip. 895 Result is converted back to a triangle list. 896 *****************************************************************************/ 897 void PVRTTriStripList(unsigned int * const pui32TriList, const unsigned int nTriCnt) 898 { 899 unsigned int *pui32Strips; 900 unsigned int *pnStripLength; 901 unsigned int nNumStrips; 902 unsigned int *pui32TriPtr, *pui32StripPtr; 903 904 /* 905 Strip the geometry 906 */ 907 PVRTTriStrip(&pui32Strips, &pnStripLength, &nNumStrips, pui32TriList, nTriCnt); 908 909 /* 910 Convert back to a triangle list 911 */ 912 pui32StripPtr = pui32Strips; 913 pui32TriPtr = pui32TriList; 914 for(unsigned int i = 0; i < nNumStrips; ++i) 915 { 916 *pui32TriPtr++ = *pui32StripPtr++; 917 *pui32TriPtr++ = *pui32StripPtr++; 918 *pui32TriPtr++ = *pui32StripPtr++; 919 920 for(unsigned int j = 1; j < pnStripLength[i]; ++j) 921 { 922 // Use two indices from previous triangle, flipping tri order alternately. 923 if(j & 0x01) 924 { 925 *pui32TriPtr++ = pui32StripPtr[-1]; 926 *pui32TriPtr++ = pui32StripPtr[-2]; 927 } 928 else 929 { 930 *pui32TriPtr++ = pui32StripPtr[-2]; 931 *pui32TriPtr++ = pui32StripPtr[-1]; 932 } 933 934 *pui32TriPtr++ = *pui32StripPtr++; 935 } 936 } 937 938 free(pui32Strips); 939 free(pnStripLength); 940 } 941 942 /***************************************************************************** 943 End of file (PVRTTriStrip.cpp) 944 *****************************************************************************/ 945 946
