1 /****************************************************************************** 2 3 @File PVRTGeometry.cpp 4 5 @Title PVRTGeometry 6 7 @Version 8 9 @Copyright Copyright (c) Imagination Technologies Limited. 10 11 @Platform Independant 12 13 @Description Code to affect triangle mesh geometry. 14 15 ******************************************************************************/ 16 17 /***************************************************************************** 18 For each vertex with only one free triangle 19 Start collecting triangles from there 20 Add the triangle which gives the highest triangles/vertex number (extra tris usually come for free) 21 When full, test against current best 22 If markedly better tri/vtx, take new block 23 If close-enough to prev tri/vtx, take block which closes the highest number of edges (and opens fewest) 24 If not quite full, goto 1 to continue filling block 25 If no block has been found, start at any free triangle and use resulting block 26 Copy block to output, empty it and goto 1. 27 *****************************************************************************/ 28 29 /**************************************************************************** 30 ** Build options 31 ****************************************************************************/ 32 #undef PVRTRISORT_ENABLE_VERIFY_RESULTS 33 34 /**************************************************************************** 35 ** Includes 36 ****************************************************************************/ 37 #include <vector> 38 #include <math.h> 39 40 #include "PVRTGeometry.h" 41 42 #ifdef PVRTRISORT_ENABLE_VERIFY_RESULTS 43 #include "PvrVGPBlockTest.h" 44 #endif 45 46 #include "PVRTGlobal.h" 47 #include "PVRTContext.h" 48 /**************************************************************************** 49 ** Structures 50 ****************************************************************************/ 51 52 struct SVtx; 53 54 /**************************************************************************** 55 @Function SEdg 56 @Description Information about an "edge" - the shared boundary between two triangles 57 ****************************************************************************/ 58 struct SEdg { 59 const SVtx *psVtx[2]; // Identify the edge by the two vertices it joins 60 int nTriNumFree; // Number of triangle using this edge 61 }; 62 63 /**************************************************************************** 64 @Function STri 65 @Description Information about a triangle 66 ****************************************************************************/ 67 struct STri { 68 const PVRTGEOMETRY_IDX *pwIdx; // Vertex indices forming this triangle 69 SEdg *psEdg[3]; // Pointer to the three triangle edges 70 bool bUsed; 71 }; 72 73 /**************************************************************************** 74 @Function SVtx 75 @Description Information about a vertex 76 ****************************************************************************/ 77 struct SVtx { 78 STri **psTri; // Allocated array of pointers to the triangles sharing this vertex 79 int nTriNumTot; // Length of the above array 80 int nTriNumFree; // Number of triangles unused in the above array 81 SVtx **ppMeshPos; // Position in VtxByMesh list 82 }; 83 84 /**************************************************************************** 85 @Function SMesh 86 @Description Information about a mesh 87 ****************************************************************************/ 88 struct SMesh { 89 SVtx **ppVtx; 90 int nVtxNum; 91 }; 92 93 /**************************************************************************** 94 @Function CObject 95 @Description Information about an object (i.e. collection of mesh's to form 96 a single entity) 97 ****************************************************************************/ 98 class CObject { 99 public: 100 STri *m_pTri; // Array of all the triangles in the mesh 101 SEdg *m_pEdg; // Array of all the edges in the mesh 102 SVtx *m_pVtx; // Array of all the vertices in a mesh 103 104 int m_nTriNumFree; 105 106 std::vector<SMesh> *m_pvMesh; 107 std::vector<SMesh> m_vMeshLg; 108 109 protected: 110 int m_nVtxTot; // Total vertices in the object 111 int m_nEdgTot; // Total edges in the object 112 int m_nTriTot; // Total triangles in the object 113 114 int m_nVtxLimit; // Maximum number of vertices a block can contain 115 int m_nTriLimit; // Maximum number of triangles a block can contain 116 117 SVtx **m_ppVtxByMesh; 118 119 public: 120 CObject( 121 const PVRTGEOMETRY_IDX * const pwIdx, 122 const int nVtxTot, 123 const int nTriTot, 124 const int nVtxLimit, 125 const int nTriLimit); 126 127 ~CObject(); 128 129 int GetVertexCount() const; 130 int GetTriangleCount() const; 131 void SplitMesh( 132 SMesh * const pMesh, 133 const int nVtxNum, 134 SVtx ** const ppVtx); 135 136 void ResizeMesh( 137 const int nVtxNum, 138 SVtx ** const ppVtx); 139 140 protected: 141 SEdg *BuildEdgeList( 142 const SVtx * const pVtx0, 143 const SVtx * const pVtx1); 144 145 void CreateMeshList(); 146 }; 147 148 /**************************************************************************** 149 @Function CBlockOption 150 @Description A possible group of polygons to use 151 ****************************************************************************/ 152 struct CBlockOption { 153 protected: 154 struct SEdgeDelta { 155 const SEdg *pEdg; 156 int nRefCnt; 157 }; 158 159 public: 160 int nVtxNum; // Number of vertices in the block 161 int nEdgNum; // Number of edges in the block 162 int nTriNum; // Number of triangles in the block 163 164 SVtx **psVtx; // Pointers to vertices 165 protected: 166 SEdgeDelta *psEdgeDelta; 167 STri **psTri; // Pointers to triangles 168 169 int m_nVtxLimit; // Maximum number of vertices a block can contain 170 int m_nTriLimit; // Maximum number of triangles a block can contain 171 172 public: 173 ~CBlockOption(); 174 175 void Init( 176 const int nVtxLimit, 177 const int nTriLimit); 178 void Copy(const CBlockOption * const pSrc); 179 180 void Clear(); 181 182 void Output( 183 PVRTGEOMETRY_IDX * const pwOut, 184 int * const pnVtxCnt, 185 int * const pnTriCnt, 186 const CObject * const pOb) const; 187 188 bool UsingVertex(const SVtx * const pVtx) const; 189 bool Contains(const STri * const pTri) const; 190 191 bool IsEmpty() const; 192 bool IsFull() const; 193 194 void AddVertex(SVtx * const pVtx); 195 void AddVertexCheckDup(SVtx * const pVtx); 196 197 void AddTriangleCheckDup(STri * const pTri); 198 199 void AddEdgeCheckDup(const SEdg * const pEdg); 200 201 void AddTriangle(STri * const pTri); 202 203 void AddOneTriangle( 204 STri * const pTri, 205 const CObject * const pOb); 206 207 int GetClosedEdgeDelta() const; 208 bool IsBetterThan(const CBlockOption * const pCmp) const; 209 210 void Add( 211 const CBlockOption * const pSrc, 212 const CObject * const pOb); 213 214 void Add( 215 const SMesh * const pMesh); 216 }; 217 218 /**************************************************************************** 219 @Function CBlock 220 @Description A model of a HW block (triangles and vertices) 221 ****************************************************************************/ 222 class CBlock { 223 protected: 224 CBlockOption m_sOpt, m_sOptBest; 225 226 int m_nVtxLimit; // Maximum number of vertices a block can contain 227 int m_nTriLimit; // Maximum number of triangles a block can contain 228 229 CBlockOption m_sJob0, m_sJob1; // Workspace: to find the best triangle to add 230 231 public: 232 CBlock( 233 const int nBufferVtxLimit, 234 const int nBufferTriLimit); 235 236 void Clear(); 237 238 bool FillFrom( 239 SMesh * const pMesh, 240 SVtx * const pVtx, 241 CObject * const pOb); 242 243 int Fill( 244 CObject * const pOb); 245 246 void Output( 247 PVRTGEOMETRY_IDX * const pwOut, 248 int * const pnVtxCnt, 249 int * const pnTriCnt, 250 const CObject * const pOb) const; 251 252 protected: 253 bool AddBestTrianglesAppraise( 254 CBlockOption * const pJob, 255 const CObject * const pOb, 256 const STri * const pTriAppraise); 257 258 void AddBestTriangles(CObject * const pOb); 259 }; 260 261 /**************************************************************************** 262 ** Local function prototypes 263 ****************************************************************************/ 264 265 /**************************************************************************** 266 @Function CObject 267 @Input pwIdx Array of indices 268 @Input nVrxTot Total number of vertices 269 @Input nTriTot Total number of triangles 270 @Input nVtxLimit Max number of vertices a block can contain 271 @Input nTriLimit Max number of triangles a block can contain 272 @Description The class's constructor. 273 ****************************************************************************/ 274 CObject::CObject( 275 const PVRTGEOMETRY_IDX * const pwIdx, 276 const int nVtxTot, 277 const int nTriTot, 278 const int nVtxLimit, 279 const int nTriLimit) 280 { 281 int i; 282 SVtx *pVtx0, *pVtx1, *pVtx2; 283 284 m_nVtxLimit = nVtxLimit; 285 m_nTriLimit = nTriLimit; 286 287 m_pvMesh = new std::vector<SMesh>[nVtxLimit-2]; 288 _ASSERT(m_pvMesh); 289 290 m_ppVtxByMesh = (SVtx**)calloc(nVtxTot, sizeof(*m_ppVtxByMesh)); 291 _ASSERT(m_ppVtxByMesh); 292 293 m_nVtxTot = nVtxTot; 294 m_nEdgTot = 0; 295 m_nTriTot = nTriTot; 296 297 m_nTriNumFree = m_nTriTot; 298 299 m_pTri = (STri*)calloc(nTriTot, sizeof(*m_pTri)); 300 _ASSERT(m_pTri); 301 302 m_pEdg = (SEdg*)calloc(nTriTot*3, sizeof(*m_pEdg)); // Allocate the maximum possible number of edges, though it should be far fewer than this 303 _ASSERT(m_pEdg); 304 305 m_pVtx = (SVtx*)calloc(nVtxTot, sizeof(*m_pVtx)); 306 _ASSERT(m_pVtx); 307 308 // Run through triangles... 309 for(i = 0; i < nTriTot; ++i) { 310 pVtx0 = &m_pVtx[pwIdx[3*i+0]]; 311 pVtx1 = &m_pVtx[pwIdx[3*i+1]]; 312 pVtx2 = &m_pVtx[pwIdx[3*i+2]]; 313 314 // Mark each vertex for the number of times it's referenced 315 ++pVtx0->nTriNumFree; 316 ++pVtx1->nTriNumFree; 317 ++pVtx2->nTriNumFree; 318 319 // Build the edge list 320 m_pTri[i].psEdg[0] = BuildEdgeList(pVtx0, pVtx1); 321 m_pTri[i].psEdg[1] = BuildEdgeList(pVtx1, pVtx2); 322 m_pTri[i].psEdg[2] = BuildEdgeList(pVtx2, pVtx0); 323 } 324 325 // Run through vertices, creating enough space for pointers to each triangle using this vertex 326 for(i = 0; i < nVtxTot; ++i) 327 m_pVtx[i].psTri = (STri**)calloc(m_pVtx[i].nTriNumFree, sizeof(*m_pVtx[i].psTri)); 328 329 // Run through triangles, marking each vertex used with a pointer to this tri 330 for(i = 0; i < nTriTot; ++i) { 331 pVtx0 = &m_pVtx[pwIdx[3*i+0]]; 332 pVtx1 = &m_pVtx[pwIdx[3*i+1]]; 333 pVtx2 = &m_pVtx[pwIdx[3*i+2]]; 334 335 pVtx0->psTri[pVtx0->nTriNumTot++] = &m_pTri[i]; 336 pVtx1->psTri[pVtx1->nTriNumTot++] = &m_pTri[i]; 337 pVtx2->psTri[pVtx2->nTriNumTot++] = &m_pTri[i]; 338 339 // Give each triangle a pointer to its indices 340 m_pTri[i].pwIdx = &pwIdx[3*i]; 341 } 342 343 #ifdef _DEBUG 344 for(i = 0; i < nVtxTot; ++i) { 345 _ASSERTE(m_pVtx[i].nTriNumFree == m_pVtx[i].nTriNumTot); 346 } 347 #endif 348 349 CreateMeshList(); 350 } 351 352 /**************************************************************************** 353 @Function ~CObject 354 @Description Destructor 355 ****************************************************************************/ 356 CObject::~CObject() 357 { 358 _ASSERT(m_nTriNumFree == 0); 359 360 while(m_nVtxTot) { 361 --m_nVtxTot; 362 FREE(m_pVtx[m_nVtxTot].psTri); 363 _ASSERTE(m_pVtx[m_nVtxTot].nTriNumFree == 0); 364 _ASSERTE(m_pVtx[m_nVtxTot].ppMeshPos); 365 } 366 367 #ifdef _DEBUG 368 while(m_nEdgTot) { 369 --m_nEdgTot; 370 _ASSERTE(m_pEdg[m_nEdgTot].nTriNumFree == 0); 371 } 372 while(m_nTriTot) { 373 --m_nTriTot; 374 _ASSERTE(m_pTri[m_nTriTot].bUsed); 375 } 376 #endif 377 378 FREE(m_pTri); 379 FREE(m_pEdg); 380 FREE(m_pVtx); 381 382 delete [] m_pvMesh; 383 FREE(m_ppVtxByMesh); 384 } 385 386 /**************************************************************************** 387 @Function GetVertexCount 388 @Return int 389 @Description Return the vertex count 390 ****************************************************************************/ 391 int CObject::GetVertexCount() const 392 { 393 return m_nVtxTot; 394 } 395 396 /**************************************************************************** 397 @Function GetTriangleCount 398 @Return int 399 @Description Return the triangle count 400 ****************************************************************************/ 401 int CObject::GetTriangleCount() const 402 { 403 return m_nTriTot; 404 } 405 406 /**************************************************************************** 407 @Function BuildEdgeList 408 @Input pVtx0 Edge 0 409 @Input pVtx1 Edge 1 410 @Return SEdg* 411 @Description If the vertices that have been passed in are already used by an edge, 412 the number of triangles sharing the edge is increased by one and a 413 pointer to the edge is returned. If the edge is not already in the 414 list, the edge is added to the list. 415 ****************************************************************************/ 416 SEdg *CObject::BuildEdgeList( 417 const SVtx * const pVtx0, 418 const SVtx * const pVtx1) 419 { 420 SEdg *pEdg; 421 const SVtx *pVtxL, *pVtxH; 422 int i; 423 424 pVtxL = pVtx0 < pVtx1 ? pVtx0 : pVtx1; 425 pVtxH = pVtx0 > pVtx1 ? pVtx0 : pVtx1; 426 427 // Do nothing if the edge already exists 428 i = m_nEdgTot; 429 while(i) { 430 --i; 431 432 pEdg = &m_pEdg[i]; 433 if(pEdg->psVtx[0] == pVtxL && pEdg->psVtx[1] == pVtxH) 434 { 435 ++pEdg->nTriNumFree; 436 return pEdg; 437 } 438 } 439 440 // Add the new edge 441 _ASSERT(m_nEdgTot < m_nTriTot*3); 442 pEdg = &m_pEdg[m_nEdgTot++]; 443 pEdg->psVtx[0] = pVtxL; 444 pEdg->psVtx[1] = pVtxH; 445 pEdg->nTriNumFree = 1; 446 447 return pEdg; 448 } 449 450 /**************************************************************************** 451 @Function CreateMeshList 452 @Description Creates the mesh list 453 ****************************************************************************/ 454 void CObject::CreateMeshList() 455 { 456 SVtx **ppR, **ppW, *pVtx; 457 STri *pTri; 458 int i, j, k; 459 SMesh sMesh; 460 int nMeshCnt; 461 462 nMeshCnt = 0; 463 464 ppR = m_ppVtxByMesh; 465 ppW = m_ppVtxByMesh; 466 467 for(i = 0; i < m_nVtxTot; ++i) { 468 pVtx = &m_pVtx[i]; 469 470 if(pVtx->ppMeshPos) { 471 _ASSERT(pVtx->ppMeshPos < ppW); 472 continue; 473 } 474 475 ++nMeshCnt; 476 sMesh.ppVtx = ppW; 477 478 *ppW = pVtx; 479 pVtx->ppMeshPos = ppW; 480 ++ppW; 481 482 do { 483 // Add all the vertices of all the triangles of *ppR to the list - unless they're already in there 484 for(j = 0; j < (*ppR)->nTriNumTot; ++j) { 485 pTri = (*ppR)->psTri[j]; 486 487 for(k = 0; k < 3; ++k) { 488 pVtx = &m_pVtx[pTri->pwIdx[k]]; 489 490 if(pVtx->ppMeshPos) { 491 _ASSERT(pVtx->ppMeshPos < ppW); 492 continue; 493 } 494 495 *ppW = pVtx; 496 pVtx->ppMeshPos = ppW; 497 ++ppW; 498 } 499 } 500 501 ++ppR; 502 } while(ppR != ppW); 503 504 sMesh.nVtxNum = (int)(ppR - sMesh.ppVtx); 505 // _RPT2(_CRT_WARN, "CreateMeshList() mesh %d %dvtx\n", nMeshCnt, sMesh.nVtxNum); 506 if(sMesh.nVtxNum >= 3) 507 { 508 if(sMesh.nVtxNum >= m_nVtxLimit) 509 m_vMeshLg.push_back(sMesh); 510 else 511 m_pvMesh[sMesh.nVtxNum-3].push_back(sMesh); 512 } 513 else 514 { 515 /* 516 Vertex is not used by any triangles; this may be because we're 517 optimising a subset of the mesh (e.g. for bone batching). 518 */ 519 _ASSERT(sMesh.nVtxNum == 1); 520 } 521 } 522 523 _ASSERT(ppR == &m_ppVtxByMesh[m_nVtxTot]); 524 _ASSERT(ppW == &m_ppVtxByMesh[m_nVtxTot]); 525 // _RPT1(_CRT_WARN, "CreateMeshList() %d meshes\n", nMeshCnt); 526 527 #ifdef _DEBUG 528 /* for(i = 0; i < m_nVtxLimit-2; ++i) 529 if(m_pvMesh[i].size()) 530 _RPT2(_CRT_WARN, "%d:%d ", i+3, m_pvMesh[i].size()); 531 _RPT1(_CRT_WARN, "lg:%d\n", m_vMeshLg.size());*/ 532 #endif 533 } 534 535 /**************************************************************************** 536 @Function SplitMesh 537 @Input pMesh Pointer to mesh data 538 @Input nVtxNum Number of vertices in the mesh? 539 @Output ppVtx Array of vertices 540 @Description Note: Ask Aaron 541 ****************************************************************************/ 542 void CObject::SplitMesh( 543 SMesh * const pMesh, 544 const int nVtxNum, 545 SVtx ** const ppVtx) 546 { 547 SVtx *pTmp; 548 int i; 549 SMesh sNew; 550 551 _ASSERT(nVtxNum); 552 553 for(i = 0; i < nVtxNum; ++i) { 554 pTmp = pMesh->ppVtx[i]; // Keep a record of the old vtx that's already here 555 556 pMesh->ppVtx[i] = ppVtx[i]; // Move the new vtx into place 557 *ppVtx[i]->ppMeshPos = pTmp; // Move the old vtx into place 558 559 pTmp->ppMeshPos = ppVtx[i]->ppMeshPos; // Tell the old vtx where it is now 560 ppVtx[i]->ppMeshPos = &pMesh->ppVtx[i]; // Tell the new vtx where it is now 561 562 _ASSERT(pMesh->ppVtx[i]->nTriNumFree); 563 } 564 565 sNew.nVtxNum = nVtxNum; 566 sNew.ppVtx = pMesh->ppVtx; 567 m_pvMesh[nVtxNum-3].push_back(sNew); 568 569 pMesh->ppVtx = &pMesh->ppVtx[nVtxNum]; 570 pMesh->nVtxNum -= nVtxNum; 571 if(pMesh->nVtxNum < m_nVtxLimit) { 572 ResizeMesh(pMesh->nVtxNum, pMesh->ppVtx); 573 m_vMeshLg.pop_back(); 574 #ifdef _DEBUG 575 /* } else { 576 for(i = 0; i < m_nVtxLimit-2; ++i) 577 if(m_pvMesh[i].size()) 578 _RPT2(_CRT_WARN, "%d:%d ", i+3, m_pvMesh[i].size()); 579 _RPT1(_CRT_WARN, "lg:%d\n", m_vMeshLg.size());*/ 580 #endif 581 } 582 } 583 584 /**************************************************************************** 585 @Function ResizeMesh 586 @Input nVtxNum The size of the array of vertices being passed in 587 @Input ppVtx Array of vertices 588 @Description Note: Ask Aaron 589 ****************************************************************************/ 590 void CObject::ResizeMesh( 591 const int nVtxNum, 592 SVtx ** const ppVtx) 593 { 594 SVtx **ppR, **ppW; 595 SMesh sNew; 596 int i; 597 598 ppR = ppVtx; 599 ppW = ppVtx; 600 601 // Make a list of vertices that have unused triangles in their array of triangles 602 for(i = 0; i < nVtxNum; ++i) { 603 if((*ppR)->nTriNumFree) { 604 (*ppW) = (*ppR); 605 ++ppW; 606 } 607 ++ppR; 608 } 609 610 sNew.nVtxNum = (int)(ppW - ppVtx); 611 _ASSERT(sNew.nVtxNum <= nVtxNum); 612 613 // If any mesh still exists, add it to the relevant list 614 if(sNew.nVtxNum) { 615 _ASSERT(sNew.nVtxNum >= 3); 616 _ASSERT(sNew.nVtxNum < m_nVtxLimit); 617 618 sNew.ppVtx = ppVtx; 619 m_pvMesh[sNew.nVtxNum-3].push_back(sNew); 620 } 621 622 #ifdef _DEBUG 623 /* for(i = 0; i < m_nVtxLimit-2; ++i) 624 if(m_pvMesh[i].size()) 625 _RPT2(_CRT_WARN, "%d:%d ", i+3, m_pvMesh[i].size()); 626 _RPT1(_CRT_WARN, "lg:%d\n", m_vMeshLg.size());*/ 627 #endif 628 } 629 630 /**************************************************************************** 631 @Function ~CBlockOption 632 @Description Default destructor 633 ****************************************************************************/ 634 CBlockOption::~CBlockOption() 635 { 636 FREE(psVtx); 637 FREE(psTri); 638 FREE(psEdgeDelta); 639 } 640 641 /**************************************************************************** 642 @Function Init 643 @Input nVertexLimit The maximum number of vertices a block can contain 644 @Input nTriLimit The maximum number of triangles a block can contain 645 @Description Initialises the class 646 ****************************************************************************/ 647 void CBlockOption::Init( 648 const int nVtxLimit, 649 const int nTriLimit) 650 { 651 m_nVtxLimit = nVtxLimit; 652 m_nTriLimit = nTriLimit; 653 654 psVtx = (SVtx**)malloc(nVtxLimit * sizeof(*psVtx)); 655 psTri = (STri**)malloc(nTriLimit * sizeof(*psTri)); 656 psEdgeDelta = (SEdgeDelta*)malloc(3 * nTriLimit * sizeof(*psEdgeDelta)); 657 } 658 659 /**************************************************************************** 660 @Function Copy 661 @Input pSrc Pointer to the source data 662 @Description Overwrites the data in the current instance with the data from 663 the input CBlockOption. 664 ****************************************************************************/ 665 void CBlockOption::Copy(const CBlockOption * const pSrc) 666 { 667 nVtxNum = pSrc->nVtxNum; 668 nEdgNum = pSrc->nEdgNum; 669 nTriNum = pSrc->nTriNum; 670 671 memcpy(psVtx, pSrc->psVtx, nVtxNum * sizeof(*psVtx)); 672 memcpy(psEdgeDelta, pSrc->psEdgeDelta, nEdgNum * sizeof(*psEdgeDelta)); 673 memcpy(psTri, pSrc->psTri, nTriNum * sizeof(*psTri)); 674 } 675 676 /**************************************************************************** 677 @Function Clear 678 @Description Sets the value of the number of vertices, edges and triangles 679 to zero. 680 ****************************************************************************/ 681 void CBlockOption::Clear() 682 { 683 nVtxNum = 0; 684 nEdgNum = 0; 685 nTriNum = 0; 686 } 687 688 /**************************************************************************** 689 @Function Output 690 @Output pwOut Index output 691 @Output pnVtxCnt Vertex count 692 @Output pnTriCnt Triangle count 693 @Modified pOb Pointer to an object 694 @Description Outputs key information about the instance of CBlockOption 695 ****************************************************************************/ 696 void CBlockOption::Output( 697 PVRTGEOMETRY_IDX * const pwOut, 698 int * const pnVtxCnt, 699 int * const pnTriCnt, 700 const CObject * const pOb) const 701 { 702 STri *pTri; 703 int i, j; 704 705 for(i = 0; i < nTriNum; ++i) { 706 pTri = psTri[i]; 707 708 _ASSERT(!pTri->bUsed); 709 710 for(j = 0; j < 3; ++j) { 711 _ASSERT(pOb->m_pVtx[pTri->pwIdx[j]].nTriNumFree > 0); 712 _ASSERT(pTri->psEdg[j]->nTriNumFree > 0); 713 714 --pOb->m_pVtx[pTri->pwIdx[j]].nTriNumFree; 715 --pTri->psEdg[j]->nTriNumFree; 716 717 _ASSERT(pOb->m_pVtx[pTri->pwIdx[j]].nTriNumFree >= 0); 718 _ASSERT(pTri->psEdg[j]->nTriNumFree >= 0); 719 } 720 721 pTri->bUsed = true; 722 723 // Copy indices into output 724 memcpy(&pwOut[3*i], pTri->pwIdx, 3 * sizeof(*pTri->pwIdx)); 725 } 726 727 *pnVtxCnt = nVtxNum; 728 *pnTriCnt = nTriNum; 729 } 730 731 /**************************************************************************** 732 @Function UsingVertex 733 @Input pVtx Vertex to compare 734 @Return bool True on success 735 @Description Returns true if the supplied vertex is already being used 736 in the block option. 737 ****************************************************************************/ 738 bool CBlockOption::UsingVertex( 739 const SVtx * const pVtx) const 740 { 741 int i; 742 743 i = nVtxNum; 744 while(i) { 745 --i; 746 747 if(psVtx[i] == pVtx) 748 return true; 749 } 750 751 return false; 752 } 753 754 /**************************************************************************** 755 @Function Contains 756 @Input pVtx Triangle to compare 757 @Return bool True on success 758 @Description Returns true if the supplied triangle is already being used 759 in the block option. 760 ****************************************************************************/ 761 bool CBlockOption::Contains(const STri * const pTri) const 762 { 763 int i; 764 765 i = nTriNum; 766 while(i) { 767 --i; 768 769 if(psTri[i] == pTri) 770 return true; 771 } 772 773 return false; 774 } 775 776 /**************************************************************************** 777 @Function IsEmpty 778 @Return bool True if the block option is empty 779 @Description Returns true if the block option is empty. 780 ****************************************************************************/ 781 bool CBlockOption::IsEmpty() const 782 { 783 return !(nVtxNum + nEdgNum + nTriNum); 784 } 785 786 /**************************************************************************** 787 @Function IsFull 788 @Return bool True if the block option is full 789 @Description Returns true if the block option is full. 790 ****************************************************************************/ 791 bool CBlockOption::IsFull() const 792 { 793 return (m_nVtxLimit - nVtxNum) < 3 || nTriNum == m_nTriLimit; 794 } 795 796 /**************************************************************************** 797 @Function AddVertex 798 @Input pVtx Vertex to add 799 @Description Providing the current number of vertices is less than the 800 maximum, the input vertex is added to the end of the array. 801 ****************************************************************************/ 802 void CBlockOption::AddVertex(SVtx * const pVtx) 803 { 804 _ASSERT(nVtxNum < m_nVtxLimit); 805 psVtx[nVtxNum++] = pVtx; 806 } 807 808 /**************************************************************************** 809 @Function AddVertexCheckDup 810 @Input pVtx Vertex to add 811 @Description Checks that the input vertex is not already contained in the 812 vertex array. If it is new, it is added to the array. 813 ****************************************************************************/ 814 void CBlockOption::AddVertexCheckDup(SVtx * const pVtx) 815 { 816 int i; 817 818 for(i = 0; i < nVtxNum; ++i) 819 if(psVtx[i] == pVtx) 820 return; 821 822 AddVertex(pVtx); 823 } 824 825 /**************************************************************************** 826 @Function AddTriangleCheckDup 827 @Input pTri Triangle to add 828 @Description Checks that the input triangle is not already contained in the 829 triangle array. If it is new, it is added to the array. 830 ****************************************************************************/ 831 void CBlockOption::AddTriangleCheckDup(STri * const pTri) 832 { 833 int i; 834 835 for(i = 0; i < nTriNum; ++i) 836 if(psTri[i] == pTri) 837 return; 838 839 _ASSERT(nTriNum < m_nTriLimit); 840 psTri[nTriNum++] = pTri; 841 } 842 843 /**************************************************************************** 844 @Function AddEdgeCheckDup 845 @Input pEdg Edge to add 846 @Description Checks that the input edge is not already contained in the 847 edge array. If it is new, it is added to the array. 848 ****************************************************************************/ 849 void CBlockOption::AddEdgeCheckDup(const SEdg * const pEdg) 850 { 851 int i; 852 853 for(i = 0; i < nEdgNum; ++i) { 854 if(psEdgeDelta[i].pEdg == pEdg) { 855 ++psEdgeDelta[i].nRefCnt; 856 return; 857 } 858 } 859 860 _ASSERT(nEdgNum < 3*m_nTriLimit); 861 psEdgeDelta[nEdgNum].pEdg = pEdg; 862 psEdgeDelta[nEdgNum].nRefCnt = 1; 863 ++nEdgNum; 864 } 865 866 /**************************************************************************** 867 @Function AddTriangle 868 @Input pTri Triangle to add 869 @Description Providing the current number of triangles is less than the 870 maximum, the input triangle is added to the end of the array. 871 Once this has been done, the array of edges is updated. 872 ****************************************************************************/ 873 // TODO: if this is only used to add fresh triangles, all edges must be added 874 void CBlockOption::AddTriangle(STri * const pTri) 875 { 876 int i; 877 878 _ASSERT(nTriNum < m_nTriLimit); 879 psTri[nTriNum++] = pTri; 880 881 // Keep a count of edges and the number of tris which share them 882 for(i = 0; i < 3; ++i) 883 AddEdgeCheckDup(pTri->psEdg[i]); 884 } 885 886 /**************************************************************************** 887 @Function AddOneTriangle 888 @Input pTri Triangle to add 889 @Input pOb Object to copy vertices from 890 @Description Calls the AddTriangle function. 891 Once this has been done, the array of vertices is updated. 892 ****************************************************************************/ 893 // TODO: if this is only called to add a fresh start triangle, all vertices must be added 894 void CBlockOption::AddOneTriangle( 895 STri * const pTri, 896 const CObject * const pOb) 897 { 898 int i; 899 900 // Add the triangle to the block 901 AddTriangle(pTri); 902 903 // Add the vertices to the block 904 for(i = 0; i < 3; ++i) 905 AddVertexCheckDup(&pOb->m_pVtx[pTri->pwIdx[i]]); 906 } 907 908 /**************************************************************************** 909 @Function GetClosedEdgeDelta 910 @Return int The delta value of closed edges 911 @Description This method returns a value that represents the average state of 912 the edges. If the value is greater than zero, the majority of 913 edges are closed. If the value is less than zero, the majority 914 of edges are open. 915 ****************************************************************************/ 916 int CBlockOption::GetClosedEdgeDelta() const 917 { 918 int i, nDelta; 919 920 nDelta = 0; 921 for(i = 0; i < nEdgNum; ++i) { 922 _ASSERT(psEdgeDelta[i].pEdg->nTriNumFree >= psEdgeDelta[i].nRefCnt); 923 924 // Check how many tris will use the edge if these are taken away 925 switch(psEdgeDelta[i].pEdg->nTriNumFree - psEdgeDelta[i].nRefCnt) { 926 case 0: 927 // If the edge was open, and is now closed, that's good 928 if(psEdgeDelta[i].pEdg->nTriNumFree == 1) 929 ++nDelta; 930 break; 931 case 1: 932 // if the edge is now open, that's bad 933 --nDelta; 934 break; 935 } 936 } 937 938 return nDelta; 939 } 940 941 /**************************************************************************** 942 @Function IsBetterThan 943 @Input pCmp The block option to compare with 944 @Return bool True if the current block option is best 945 @Description Returns true if the current block option is better than the 946 block option that has been passed in. Otherwise, it returns false. 947 ****************************************************************************/ 948 bool CBlockOption::IsBetterThan(const CBlockOption * const pCmp) const 949 { 950 float fWorth0, fWorth1; 951 int nClosed0, nClosed1; 952 953 // Check "worth" - TrisAdded/VtxAdded 954 fWorth0 = (float)nTriNum / (float)nVtxNum; 955 fWorth1 = (float)pCmp->nTriNum / (float)pCmp->nVtxNum; 956 957 nClosed0 = GetClosedEdgeDelta(); 958 nClosed1 = pCmp->GetClosedEdgeDelta(); 959 960 if(fabsf(fWorth0 - fWorth1) > 0.1f) { 961 return fWorth0 > fWorth1; 962 } else if(nClosed0 != nClosed1) { 963 return nClosed0 > nClosed1; 964 } else { 965 return nTriNum > pCmp->nTriNum; 966 } 967 } 968 969 /**************************************************************************** 970 @Function Add 971 @Input pSrc The block option to add 972 @Input pOb Object to use vertices from 973 @Description Add's the input vertex and triangle data to the current block option 974 ****************************************************************************/ 975 void CBlockOption::Add( 976 const CBlockOption * const pSrc, 977 const CObject * const pOb) 978 { 979 PVRT_UNREFERENCED_PARAMETER(pOb); 980 981 int i; 982 983 // Add vertices from job to block 984 for(i = 0; i < pSrc->nVtxNum; ++i) 985 AddVertexCheckDup(pSrc->psVtx[i]); 986 987 // Add triangles from job to block 988 for(i = 0; i < pSrc->nTriNum; ++i) 989 AddTriangle(pSrc->psTri[i]); 990 } 991 992 /**************************************************************************** 993 @Function Add 994 @Input pMesh The mesh to add 995 @Description Add's the input mesh to the current block option 996 ****************************************************************************/ 997 void CBlockOption::Add( 998 const SMesh * const pMesh) 999 { 1000 int i, j; 1001 SVtx *pVtx; 1002 1003 for(i = 0; i < pMesh->nVtxNum; ++i) { 1004 pVtx = pMesh->ppVtx[i]; 1005 1006 AddVertexCheckDup(pVtx); 1007 1008 for(j = 0; j < pVtx->nTriNumTot; ++j) { 1009 if(!pVtx->psTri[j]->bUsed) 1010 AddTriangleCheckDup(pVtx->psTri[j]); 1011 } 1012 } 1013 } 1014 1015 /**************************************************************************** 1016 @Function CBlock 1017 @Description Default constructor 1018 ****************************************************************************/ 1019 CBlock::CBlock( 1020 const int nBufferVtxLimit, 1021 const int nBufferTriLimit) 1022 { 1023 m_nVtxLimit = nBufferVtxLimit; 1024 m_nTriLimit = nBufferTriLimit; 1025 1026 m_sOpt.Init(m_nVtxLimit, m_nTriLimit); 1027 m_sOptBest.Init(m_nVtxLimit, m_nTriLimit); 1028 1029 // Intialise "job" blocks 1030 m_sJob0.Init(3, m_nTriLimit); 1031 m_sJob1.Init(3, m_nTriLimit); 1032 } 1033 1034 /**************************************************************************** 1035 @Function Clear 1036 @Description Clears the current and best block options 1037 ****************************************************************************/ 1038 void CBlock::Clear() 1039 { 1040 m_sOpt.Clear(); 1041 m_sOptBest.Clear(); 1042 } 1043 1044 /**************************************************************************** 1045 @Function Output 1046 @Output pwOut Index output 1047 @Output pnVtxCnt Vertex count 1048 @Output pnTriCnt Triangle count 1049 @Modified pOb Pointer to an object 1050 @Description Outputs key information about the instance of CBlockOption 1051 ****************************************************************************/ 1052 void CBlock::Output( 1053 PVRTGEOMETRY_IDX * const pwOut, 1054 int * const pnVtxCnt, 1055 int * const pnTriCnt, 1056 const CObject * const pOb) const 1057 { 1058 m_sOptBest.Output(pwOut, pnVtxCnt, pnTriCnt, pOb); 1059 } 1060 1061 /**************************************************************************** 1062 @Function AddBestTrianglesAppraise 1063 @Modified pJob The block object to alter 1064 @Input pOb The object 1065 @Input pTriAppraise The triangle to appraise 1066 @Return bool 1067 @Description Uses the input object and triangle to create a new block option. 1068 ****************************************************************************/ 1069 bool CBlock::AddBestTrianglesAppraise( 1070 CBlockOption * const pJob, 1071 const CObject * const pOb, 1072 const STri * const pTriAppraise) 1073 { 1074 SVtx *pVtx; 1075 STri *pTri; 1076 int i, j; 1077 1078 pJob->Clear(); 1079 1080 // Add vertices 1081 for(i = 0; i < 3; ++i) { 1082 pVtx = &pOb->m_pVtx[pTriAppraise->pwIdx[i]]; 1083 if(!m_sOpt.UsingVertex(pVtx)) 1084 pJob->AddVertex(pVtx); 1085 } 1086 1087 if(pJob->nVtxNum > (m_nVtxLimit-m_sOpt.nVtxNum)) 1088 return false; 1089 1090 // Add triangles referenced by each vertex 1091 for(i = 0; i < 3; ++i) { 1092 pVtx = &pOb->m_pVtx[pTriAppraise->pwIdx[i]]; 1093 1094 _ASSERT(pVtx->nTriNumFree >= 1); 1095 _ASSERT(pVtx->nTriNumFree <= pVtx->nTriNumTot); 1096 1097 for(j = 0; j < pVtx->nTriNumTot; ++j) { 1098 if(pJob->nTriNum >= (m_nTriLimit-m_sOpt.nTriNum)) 1099 break; 1100 1101 pTri = pVtx->psTri[j]; 1102 1103 // Don't count the same triangle twice! 1104 if(pTri->bUsed || m_sOpt.Contains(pTri) || pJob->Contains(pTri)) 1105 continue; 1106 1107 // If all the triangle's vertices are or will be in the block, then increase nTri 1108 if( 1109 ( 1110 pTri->pwIdx[0] == pTriAppraise->pwIdx[0] || 1111 pTri->pwIdx[0] == pTriAppraise->pwIdx[1] || 1112 pTri->pwIdx[0] == pTriAppraise->pwIdx[2] || 1113 m_sOpt.UsingVertex(&pOb->m_pVtx[pTri->pwIdx[0]]) 1114 ) && ( 1115 pTri->pwIdx[1] == pTriAppraise->pwIdx[0] || 1116 pTri->pwIdx[1] == pTriAppraise->pwIdx[1] || 1117 pTri->pwIdx[1] == pTriAppraise->pwIdx[2] || 1118 m_sOpt.UsingVertex(&pOb->m_pVtx[pTri->pwIdx[1]]) 1119 ) && ( 1120 pTri->pwIdx[2] == pTriAppraise->pwIdx[0] || 1121 pTri->pwIdx[2] == pTriAppraise->pwIdx[1] || 1122 pTri->pwIdx[2] == pTriAppraise->pwIdx[2] || 1123 m_sOpt.UsingVertex(&pOb->m_pVtx[pTri->pwIdx[2]]) 1124 ) 1125 ) 1126 { 1127 pJob->AddTriangle(pTri); 1128 } 1129 } 1130 } 1131 1132 _ASSERT(pJob->nTriNum); 1133 _ASSERT(pJob->nTriNum <= (m_nTriLimit-m_sOpt.nTriNum)); 1134 1135 return true; 1136 } 1137 1138 /**************************************************************************** 1139 @Function AddBestTriangles 1140 @Input pOb The object 1141 @Description Finds the best triangles and adds them to the current block option (m_sOpt) 1142 ****************************************************************************/ 1143 void CBlock::AddBestTriangles(CObject * const pOb) 1144 { 1145 int i, j; 1146 const SVtx *pVtx; 1147 STri *pTri; 1148 CBlockOption *pJob, *pJobBest; 1149 1150 pJob = &m_sJob0; 1151 1152 do { 1153 pJobBest = 0; 1154 1155 for(i = 0; i < m_sOpt.nVtxNum; ++i) { 1156 pVtx = m_sOpt.psVtx[i]; 1157 1158 if(!pVtx->nTriNumFree) 1159 continue; 1160 1161 for(j = 0; j < pVtx->nTriNumTot; ++j) { 1162 pTri = pVtx->psTri[j]; 1163 1164 if(pTri->bUsed || m_sOpt.Contains(pTri)) 1165 continue; 1166 1167 // Find out how many triangles and vertices this tri adds 1168 if(!AddBestTrianglesAppraise(pJob, pOb, pTri)) 1169 continue; 1170 1171 if(!pJobBest || pJob->IsBetterThan(pJobBest)) { 1172 pJobBest = pJob; 1173 pJob = (pJob == &m_sJob0 ? &m_sJob1 : &m_sJob0); 1174 } 1175 } 1176 } 1177 1178 if(pJobBest) { 1179 m_sOpt.Add(pJobBest, pOb); 1180 } 1181 } while(pJobBest && m_nTriLimit != m_sOpt.nTriNum); 1182 } 1183 1184 /**************************************************************************** 1185 @Function FillFrom 1186 @Input pMesh Mesh to fill with 1187 @Input pVtx Vertex to fill with 1188 @Input pOb Object to fill with 1189 @Return bool Returns true if the current block option isn't full 1190 @Description Returns TRUE if Fill() needs to be called again - i.e. blockOption is already filled 1191 ****************************************************************************/ 1192 bool CBlock::FillFrom( 1193 SMesh * const pMesh, 1194 SVtx * const pVtx, 1195 CObject * const pOb) 1196 { 1197 // Let's try starting from this vertex then 1198 _ASSERT(pVtx->nTriNumFree); 1199 m_sOpt.Clear(); 1200 m_sOpt.AddVertex(pVtx); 1201 AddBestTriangles(pOb); 1202 1203 if(m_sOpt.IsFull()) { 1204 if(m_sOptBest.IsEmpty() || m_sOpt.IsBetterThan(&m_sOptBest)) 1205 m_sOptBest.Copy(&m_sOpt); 1206 return false; 1207 } 1208 else 1209 { 1210 _ASSERT(!m_sOpt.IsEmpty()); 1211 pOb->SplitMesh(pMesh, m_sOpt.nVtxNum, m_sOpt.psVtx); // Split the sub-mesh into its own mesh 1212 return true; 1213 } 1214 } 1215 1216 /**************************************************************************** 1217 @Function Fill 1218 @Input pOb Object to fill with 1219 @Return int -1 if the block if the best option is already full 1220 @Description Note: Ask Aaron 1221 ****************************************************************************/ 1222 int CBlock::Fill( 1223 CObject * const pOb) 1224 { 1225 SVtx *pVtx; 1226 int i; 1227 SMesh *pMesh; 1228 1229 /* 1230 Build blocks from the large meshes 1231 */ 1232 if(!pOb->m_vMeshLg.empty()) { 1233 pMesh = &pOb->m_vMeshLg.back(); 1234 1235 // _RPT1(_CRT_WARN, "Fill() using large with %d vtx\n", pMesh->nVtxNum); 1236 1237 // Find the vertex with the fewest unused triangles 1238 for(i = 0; i < pMesh->nVtxNum; ++i) { 1239 pVtx = pMesh->ppVtx[i]; 1240 1241 if(pVtx->nTriNumFree == 1) { 1242 if(FillFrom(pMesh, pVtx, pOb)) 1243 return Fill(pOb); 1244 } 1245 } 1246 1247 if(m_sOptBest.IsEmpty()) { 1248 // Just start from any old vertex 1249 for(i = 0; i < pMesh->nVtxNum; ++i) { 1250 pVtx = pMesh->ppVtx[i]; 1251 1252 if(pVtx->nTriNumFree) { 1253 if(FillFrom(pMesh, pVtx, pOb)) 1254 return Fill(pOb); 1255 break; 1256 } 1257 } 1258 1259 if(m_sOptBest.IsEmpty()) { 1260 pOb->m_vMeshLg.pop_back(); // Delete the mesh from the list 1261 return Fill(pOb); 1262 } 1263 } 1264 1265 if(m_sOptBest.IsFull()) 1266 return -1; 1267 } 1268 1269 /* 1270 Match together the small meshes into blocks 1271 */ 1272 _ASSERT(m_sOptBest.IsEmpty()); 1273 i = m_nVtxLimit - m_sOptBest.nVtxNum - 3; 1274 1275 // _RPT0(_CRT_WARN, "Fill() grouping small "); 1276 1277 // Starting with the largest meshes, lump them into this block 1278 while(i >= 0 && (m_nVtxLimit - m_sOptBest.nVtxNum) >= 3) { 1279 if(pOb->m_pvMesh[i].empty()) { 1280 --i; 1281 continue; 1282 } 1283 1284 pMesh = &pOb->m_pvMesh[i].back(); 1285 m_sOptBest.Add(pMesh); 1286 // _RPT1(_CRT_WARN, "+%d", pMesh->nVtxNum); 1287 pOb->m_pvMesh[i].pop_back(); 1288 i = PVRT_MIN(i, m_nVtxLimit - m_sOptBest.nVtxNum - 3); 1289 } 1290 1291 // If there's any space left in this block (and clearly there are no blocks 1292 // just the right size to fit) then take SOME of the largest block available. 1293 if(!m_sOptBest.IsFull()) { 1294 m_sOpt.Copy(&m_sOptBest); 1295 1296 // Note: This loop purposely does not check m_pvMesh[0] - any block 1297 // which is looking to grab more geometry would have already sucked 1298 // up those meshes 1299 for(i = (m_nVtxLimit-3); i; --i) { 1300 if(!pOb->m_pvMesh[i].empty()) { 1301 pMesh = &pOb->m_pvMesh[i].back(); 1302 1303 _ASSERT(pMesh->ppVtx[0]->nTriNumFree); 1304 _ASSERT(!m_sOpt.UsingVertex(pMesh->ppVtx[0])); 1305 1306 m_sOpt.AddVertex(pMesh->ppVtx[0]); 1307 // _RPT1(_CRT_WARN, "(+%d)\n", pMesh->nVtxNum); 1308 AddBestTriangles(pOb); 1309 1310 m_sOptBest.Copy(&m_sOpt); 1311 _ASSERT(m_sOptBest.IsFull()); 1312 return i; 1313 } 1314 } 1315 } 1316 // _RPT0(_CRT_WARN, "\n"); 1317 return -1; 1318 } 1319 1320 /**************************************************************************** 1321 ** Local functions 1322 ****************************************************************************/ 1323 /**************************************************************************** 1324 @Function Fill 1325 @Input pVtxData Vertex data 1326 @Input pwIdx Index array 1327 @Input nStride Stride 1328 @Input nVertNum Number of vertices 1329 @Input nIdxNum Number of indices 1330 @Description Sorts the vertices. 1331 ****************************************************************************/ 1332 static void SortVertices( 1333 void * const pVtxData, 1334 PVRTGEOMETRY_IDX * const pwIdx, 1335 const int nStride, 1336 const int nVertNum, 1337 const int nIdxNum) 1338 { 1339 void *pVtxNew; 1340 int *pnVtxDest; 1341 int i; 1342 PVRTGEOMETRY_IDX wNext; 1343 1344 pVtxNew = malloc(nVertNum * nStride); 1345 _ASSERT(pVtxNew); 1346 1347 pnVtxDest = (int*)malloc(nVertNum * sizeof(*pnVtxDest)); 1348 _ASSERT(pnVtxDest); 1349 1350 wNext = 0; 1351 1352 // Default all indices to an invalid number 1353 for(i = 0; i < nVertNum; ++i) 1354 pnVtxDest[i] = -1; 1355 1356 // Let's get on with it then. 1357 for(i = 0; i < nIdxNum; ++i) { 1358 if(pnVtxDest[pwIdx[i]] == -1) { 1359 _ASSERT((int) wNext < nVertNum); 1360 memcpy((char*)pVtxNew+(wNext*nStride), (char*)pVtxData+(pwIdx[i]*nStride), nStride); 1361 pnVtxDest[pwIdx[i]] = wNext++; 1362 } 1363 1364 pwIdx[i] = pnVtxDest[pwIdx[i]]; 1365 } 1366 1367 /* 1368 This assert will fail if sorting a sub-set of the triangles (e.g. if 1369 the mesh is bone-batched). 1370 1371 In that situation vertex sorting should be performed only once after 1372 all the tri sorting is finished, not per tri-sort. 1373 */ 1374 _ASSERT((int) wNext == nVertNum); 1375 memcpy(pVtxData, pVtxNew, nVertNum * nStride); 1376 1377 FREE(pnVtxDest); 1378 FREE(pVtxNew); 1379 } 1380 1381 /**************************************************************************** 1382 ** Functions 1383 ****************************************************************************/ 1384 /*!*************************************************************************** 1385 @Function PVRTGeometrySort 1386 @Modified pVtxData Pointer to array of vertices 1387 @Modified pwIdx Pointer to array of indices 1388 @Input nStride Size of a vertex (in bytes) 1389 @Input nVertNum Number of vertices. Length of pVtxData array 1390 @Input nTriNum Number of triangles. Length of pwIdx array is 3* this 1391 @Input nBufferVtxLimit Number of vertices that can be stored in a buffer 1392 @Input nBufferTriLimit Number of triangles that can be stored in a buffer 1393 @Input dwFlags PVRTGEOMETRY_SORT_* flags 1394 @Description Triangle sorter 1395 *****************************************************************************/ 1396 void PVRTGeometrySort( 1397 void * const pVtxData, 1398 PVRTGEOMETRY_IDX * const pwIdx, 1399 const int nStride, 1400 const int nVertNum, 1401 const int nTriNum, 1402 const int nBufferVtxLimit, 1403 const int nBufferTriLimit, 1404 const unsigned int dwFlags) 1405 { 1406 CObject sOb(pwIdx, nVertNum, nTriNum, nBufferVtxLimit, nBufferTriLimit); 1407 CBlock sBlock(nBufferVtxLimit, nBufferTriLimit); 1408 PVRTGEOMETRY_IDX *pwIdxOut; 1409 int nTriCnt, nVtxCnt; 1410 int nOutTriCnt, nOutVtxCnt, nOutBlockCnt; 1411 int nMeshToResize; 1412 #ifdef PVRTRISORT_ENABLE_VERIFY_RESULTS 1413 int i; 1414 int pnBlockTriCnt[PVRVGPBLOCKTEST_MAX_BLOCKS]; 1415 SVGPModel sVGPMdlBefore; 1416 SVGPModel sVGPMdlAfter; 1417 #endif 1418 1419 if(dwFlags & PVRTGEOMETRY_SORT_VERTEXCACHE) { 1420 #ifdef PVRTRISORT_ENABLE_VERIFY_RESULTS 1421 VGP590Test(&sVGPMdlBefore, pwIdx, nTriNum); 1422 _RPT4(_CRT_WARN, "OptimiseTriListPVR() Before: Tri: %d, Vtx: %d, vtx/tri=%f Blocks=%d\n", nTriNum, sVGPMdlBefore.nVtxCnt, (float)sVGPMdlBefore.nVtxCnt / (float)nTriNum, sVGPMdlBefore.nBlockCnt); 1423 #endif 1424 1425 pwIdxOut = (PVRTGEOMETRY_IDX*)malloc(nTriNum * 3 * sizeof(*pwIdxOut)); 1426 _ASSERT(pwIdxOut); 1427 1428 // Sort geometry into blocks 1429 nOutTriCnt = 0; 1430 nOutVtxCnt = 0; 1431 nOutBlockCnt = 0; 1432 do { 1433 // Clear & fill the block 1434 sBlock.Clear(); 1435 nMeshToResize = sBlock.Fill(&sOb); 1436 1437 // Copy indices into output 1438 sBlock.Output(&pwIdxOut[3*nOutTriCnt], &nVtxCnt, &nTriCnt, &sOb); 1439 sOb.m_nTriNumFree -= nTriCnt; 1440 nOutTriCnt += nTriCnt; 1441 1442 if(nMeshToResize >= 0) { 1443 SMesh *pMesh; 1444 _ASSERT(nMeshToResize <= (nBufferVtxLimit-3)); 1445 pMesh = &sOb.m_pvMesh[nMeshToResize].back(); 1446 sOb.ResizeMesh(pMesh->nVtxNum, pMesh->ppVtx); 1447 sOb.m_pvMesh[nMeshToResize].pop_back(); 1448 } 1449 1450 _ASSERT(nVtxCnt <= nBufferVtxLimit); 1451 _ASSERT(nTriCnt <= nBufferTriLimit); 1452 1453 #ifdef PVRTRISORT_ENABLE_VERIFY_RESULTS 1454 _ASSERT(nOutBlockCnt < PVRVGPBLOCKTEST_MAX_BLOCKS); 1455 pnBlockTriCnt[nOutBlockCnt] = nTriCnt; 1456 #endif 1457 nOutVtxCnt += nVtxCnt; 1458 nOutBlockCnt++; 1459 1460 // _RPT4(_CRT_WARN, "%d/%d tris (+%d), %d blocks\n", nOutTriCnt, nTriNum, nTriCnt, nOutBlockCnt); 1461 1462 _ASSERT(nTriCnt == nBufferTriLimit || (nBufferVtxLimit - nVtxCnt) < 3 || nOutTriCnt == nTriNum); 1463 } while(nOutTriCnt < nTriNum); 1464 1465 _ASSERT(nOutTriCnt == nTriNum); 1466 // The following will fail if optimising a subset of the mesh (e.g. a bone batching) 1467 //_ASSERT(nOutVtxCnt >= nVertNum); 1468 1469 // Done! 1470 memcpy(pwIdx, pwIdxOut, nTriNum * 3 * sizeof(*pwIdx)); 1471 FREE(pwIdxOut); 1472 1473 _RPT3(_CRT_WARN, "OptimiseTriListPVR() In: Tri: %d, Vtx: %d, vtx/tri=%f\n", nTriNum, nVertNum, (float)nVertNum / (float)nTriNum); 1474 _RPT4(_CRT_WARN, "OptimiseTriListPVR() HW: Tri: %d, Vtx: %d, vtx/tri=%f Blocks=%d\n", nOutTriCnt, nOutVtxCnt, (float)nOutVtxCnt / (float)nOutTriCnt, nOutBlockCnt); 1475 1476 #ifdef PVRTRISORT_ENABLE_VERIFY_RESULTS 1477 VGP590Test(&sVGPMdlAfter, pwIdx, nTriNum); 1478 _RPT4(_CRT_WARN, "OptimiseTriListPVR() After : Tri: %d, Vtx: %d, vtx/tri=%f Blocks=%d\n", nTriNum, sVGPMdlAfter.nVtxCnt, (float)sVGPMdlAfter.nVtxCnt / (float)nTriNum, sVGPMdlAfter.nBlockCnt); 1479 _ASSERTE(sVGPMdlAfter.nVtxCnt <= sVGPMdlBefore.nVtxCnt); 1480 _ASSERTE(sVGPMdlAfter.nBlockCnt <= sVGPMdlBefore.nBlockCnt); 1481 1482 for(i = 0; i < nOutBlockCnt; ++i) { 1483 _ASSERT(pnBlockTriCnt[i] == sVGPMdlAfter.pnBlockTriCnt[i]); 1484 } 1485 #endif 1486 } 1487 1488 if(!(dwFlags & PVRTGEOMETRY_SORT_IGNOREVERTS)) { 1489 // Re-order the vertices so maybe they're accessed in a more linear 1490 // manner. Should cut page-breaks on the initial memory read of 1491 // vertices. Affects both the order of vertices, and the values 1492 // of indices, but the triangle order is unchanged. 1493 SortVertices(pVtxData, pwIdx, nStride, nVertNum, nTriNum*3); 1494 } 1495 } 1496 1497 /***************************************************************************** 1498 End of file (PVRTGeometry.cpp) 1499 *****************************************************************************/ 1500 1501