1 /****************************************************************************** 2 3 @File PVRTBoneBatch.cpp 4 5 @Title PVRTBoneBatch 6 7 @Version 8 9 @Copyright Copyright (c) Imagination Technologies Limited. 10 11 @Platform ANSI compatible 12 13 @Description Utility functions which process vertices. 14 15 ******************************************************************************/ 16 17 /**************************************************************************** 18 ** Includes 19 ****************************************************************************/ 20 #include "PVRTGlobal.h" 21 #include "PVRTContext.h" 22 23 #include <vector> 24 #include <list> 25 26 #include "PVRTMatrix.h" 27 #include "PVRTVertex.h" 28 #include "PVRTBoneBatch.h" 29 30 /**************************************************************************** 31 ** Defines 32 ****************************************************************************/ 33 34 /**************************************************************************** 35 ** Macros 36 ****************************************************************************/ 37 38 /**************************************************************************** 39 ** Structures 40 ****************************************************************************/ 41 /*!*************************************************************************** 42 @Class CBatch 43 @Brief Class to contain and manage batch information. 44 *****************************************************************************/ 45 class CBatch 46 { 47 protected: 48 int m_nCapacity, // Maximum size of the batch 49 m_nCnt, // Number of elements currently contained in the batch 50 *m_pnPalette; // Array of palette indices 51 52 public: 53 /*!*************************************************************************** 54 @Function CBatch 55 @Description The default constructor 56 *****************************************************************************/ 57 CBatch() : m_nCapacity(0), 58 m_nCnt(0), 59 m_pnPalette(0) 60 { 61 } 62 63 /*!*************************************************************************** 64 @Function CBatch 65 @Input src CBatch to copy 66 @Description Copy constructor 67 *****************************************************************************/ 68 CBatch(const CBatch &src) : m_pnPalette(0) 69 { 70 SetSize(src.m_nCapacity); 71 *this = src; 72 } 73 74 /*!*************************************************************************** 75 @Function ~CBatch 76 @Description Destructor 77 *****************************************************************************/ 78 ~CBatch() 79 { 80 FREE(m_pnPalette); 81 } 82 83 /*!*************************************************************************** 84 @Function operator= 85 @Description Operator overload for the '=' operand 86 *****************************************************************************/ 87 CBatch& operator= (const CBatch &src) 88 { 89 _ASSERT(m_nCapacity == src.m_nCapacity); 90 m_nCnt = src.m_nCnt; 91 memcpy(m_pnPalette, src.m_pnPalette, m_nCnt * sizeof(*m_pnPalette)); 92 return *this; 93 } 94 95 /*!*************************************************************************** 96 @Function SetSize 97 @Input nSize The new size of the batch 98 @Description Delete all current information and resizes the batch 99 to the value that has been passed in. 100 *****************************************************************************/ 101 void SetSize(const int nSize) 102 { 103 FREE(m_pnPalette); 104 105 m_nCapacity = nSize; 106 m_nCnt = 0; 107 m_pnPalette = (int*)malloc(m_nCapacity * sizeof(*m_pnPalette)); 108 } 109 110 /*!*************************************************************************** 111 @Function Clear 112 @Description Resets the count 113 *****************************************************************************/ 114 void Clear() 115 { 116 m_nCnt = 0; 117 } 118 119 /*!*************************************************************************** 120 @Function Clear 121 @Input n The index of the new item 122 Return bool Returns true if the item already exists or has been added. 123 @Description Adds a new item to the batch, providing it has not already 124 been added to the batch and the count doesn't exceed the 125 maximum number of bones the batch can hold. 126 *****************************************************************************/ 127 bool Add(const int n) 128 { 129 int i; 130 131 if(n < 0) 132 return false; 133 134 // If we already have this item, do nothing 135 for(i = 0; i < m_nCnt; ++i) 136 { 137 if(m_pnPalette[i] == n) 138 return true; 139 } 140 141 // Add the new item 142 if(m_nCnt < m_nCapacity) 143 { 144 m_pnPalette[m_nCnt] = n; 145 ++m_nCnt; 146 return true; 147 } 148 else 149 { 150 return false; 151 } 152 } 153 154 /*!*************************************************************************** 155 @Function Merge 156 @Input src The batch to merge with 157 @Description Merges the input batch with the current batch. 158 *****************************************************************************/ 159 void Merge(const CBatch &src) 160 { 161 int i; 162 163 for(i = 0; i < src.m_nCnt; ++i) 164 Add(src.m_pnPalette[i]); 165 } 166 167 /*!*************************************************************************** 168 @Function TestMerge 169 @Input src The batch to merge with 170 @Return int The number of items that are not already 171 present in the batch. -1 if the merge will 172 exceed the capacity of the batch 173 @Description Tests how many of the items of the input batch are not 174 already contained in the batch. This returns the number of 175 items that would need to be added, or -1 if the number 176 of additional items would exceed the capacity of the batch. 177 *****************************************************************************/ 178 int TestMerge(const CBatch &src) 179 { 180 int i, nCnt; 181 182 nCnt = 0; 183 for(i = 0; i < src.m_nCnt; ++i) 184 if(!Contains(src.m_pnPalette[i])) 185 ++nCnt; 186 187 return m_nCnt+nCnt > m_nCapacity ? -1 : nCnt; 188 } 189 190 /*!*************************************************************************** 191 @Function Contains 192 @Input src The batch to compare 193 @Return bool Returns true if the batch and the input batch 194 have at least one item in common 195 @Description Returns true if the batch's have at least one item in common 196 *****************************************************************************/ 197 bool Contains(const CBatch &batch) const 198 { 199 int i; 200 201 for(i = 0; i < batch.m_nCnt; ++i) 202 if(!Contains(batch.m_pnPalette[i])) 203 return false; 204 205 return true; 206 } 207 208 /*!*************************************************************************** 209 @Function Contains 210 @Input n The index of the new item 211 @Return bool Returns true if the batch contains the item 212 @Description Returns true if the batch contains the item. 213 *****************************************************************************/ 214 bool Contains(const int n) const 215 { 216 int i; 217 218 for(i = 0; i < m_nCnt; ++i) 219 if(m_pnPalette[i] == n) 220 return true; 221 222 return false; 223 } 224 225 /*!*************************************************************************** 226 @Function Write 227 @Output pn The array of items to overwrite 228 @Output pnCnt The number of items in the array 229 @Description Writes the array of items and the number of items to the output 230 parameters. 231 *****************************************************************************/ 232 void Write( 233 int * const pn, 234 int * const pnCnt) const 235 { 236 memcpy(pn, m_pnPalette, m_nCnt * sizeof(*pn)); 237 *pnCnt = m_nCnt; 238 } 239 240 /*!*************************************************************************** 241 @Function GetVertexBoneIndices 242 @Modified pfI Returned index 243 @Input pfW Weight? 244 @Input n Length of index array 245 @Description For each element of the input array, the index value is compared 246 with the palette's index value. If the values are equal, the 247 value of the current input array element is replaced with the 248 palette index, otherwise the value is set to zero. 249 *****************************************************************************/ 250 void GetVertexBoneIndices( 251 float * const pfI, 252 const float * const pfW, 253 const int n) 254 { 255 int i, j; 256 257 for(i = 0; i < n; ++i) 258 { 259 if(pfW[i] != 0) 260 { 261 for(j = 0; j < m_nCnt; ++j) 262 { 263 if(pfI[i] != m_pnPalette[j]) 264 continue; 265 266 pfI[i] = (float)j; 267 break; 268 } 269 270 // This batch *must* contain this vertex 271 _ASSERT(j != m_nCnt); 272 } 273 else 274 { 275 pfI[i] = 0; 276 } 277 } 278 } 279 }; 280 281 /*!*************************************************************************** 282 @Class CGrowableArray 283 @Brief Class that provides an array structure that can change its size dynamically. 284 *****************************************************************************/ 285 class CGrowableArray 286 { 287 protected: 288 char *m_p; 289 int m_nSize; 290 int m_nCnt; 291 292 public: 293 /*!*************************************************************************** 294 @Function CGrowableArray 295 @Input nSize The size of the data (in bytes) that the array will contain 296 @Description Initialises the size of the data the array will contain to the 297 value that has been passed in and initialises the remaining 298 data members with default values. 299 *****************************************************************************/ 300 CGrowableArray(const int nSize) 301 { 302 m_p = NULL; 303 m_nSize = nSize; 304 m_nCnt = 0; 305 } 306 307 /*!*************************************************************************** 308 @Function ~CGrowableArray 309 @Description The destructor 310 *****************************************************************************/ 311 ~CGrowableArray() 312 { 313 FREE(m_p); 314 } 315 316 /*!*************************************************************************** 317 @Function Append 318 @Input pData The data to append 319 @Input nCnt The amount of data elements to append 320 @Description Resizes the array and appends the new data that has been passed in. 321 *****************************************************************************/ 322 void Append(const void * const pData, const int nCnt) 323 { 324 m_p = (char*)realloc(m_p, (m_nCnt + nCnt) * m_nSize); 325 _ASSERT(m_p); 326 327 memcpy(&m_p[m_nCnt * m_nSize], pData, nCnt * m_nSize); 328 m_nCnt += nCnt; 329 } 330 331 /*!*************************************************************************** 332 @Function last 333 @Return char* The last element of the array 334 @Description Returns a pointer to the last element of the array. 335 *****************************************************************************/ 336 char *last() 337 { 338 return at(m_nCnt-1); 339 } 340 341 /*!*************************************************************************** 342 @Function at 343 @Input nIdx The index of the requested element 344 @Return char* The element at the specified index of the array 345 @Description Returns a pointer to the data at the specified index of the array. 346 *****************************************************************************/ 347 char *at(const int nIdx) 348 { 349 return &m_p[nIdx * m_nSize]; 350 } 351 352 /*!*************************************************************************** 353 @Function size 354 @Return int The number of elements contained in the array 355 @Description Returns the number of elements contained in the array. 356 *****************************************************************************/ 357 int size() const 358 { 359 return m_nCnt; 360 } 361 362 /*!*************************************************************************** 363 @Function Surrender 364 @Output pData The pointer to surrender the data to 365 @Description Assigns the memory address of the data to the pointer that has 366 been passed in. Sets the class's number of elements and 367 data pointer back to their default values. 368 *****************************************************************************/ 369 int Surrender( 370 char ** const pData) 371 { 372 int nCnt; 373 374 *pData = m_p; 375 nCnt = m_nCnt; 376 377 m_p = NULL; 378 m_nCnt = 0; 379 380 return nCnt; 381 } 382 }; 383 384 /**************************************************************************** 385 ** Constants 386 ****************************************************************************/ 387 388 /**************************************************************************** 389 ** Local function definitions 390 ****************************************************************************/ 391 static bool FillBatch( 392 CBatch &batch, 393 const unsigned int * const pui32Idx, // input AND output; index array for triangle list 394 const char * const pVtx, // Input vertices 395 const int nStride, // Size of a vertex (in bytes) 396 const int nOffsetWeight, // Offset in bytes to the vertex bone-weights 397 EPVRTDataType eTypeWeight, // Data type of the vertex bone-weights 398 const int nOffsetIdx, // Offset in bytes to the vertex bone-indices 399 EPVRTDataType eTypeIdx, // Data type of the vertex bone-indices 400 const int nVertexBones); // Number of bones affecting each vertex 401 402 static bool BonesMatch( 403 const float * const pfIdx0, 404 const float * const pfIdx1); 405 406 /***************************************************************************** 407 ** Functions 408 *****************************************************************************/ 409 410 /*!*************************************************************************** 411 @Function Create 412 @Output pnVtxNumOut vertex count 413 @Output pVtxOut Output vertices (program must free() this) 414 @Modified pui32Idx index array for triangle list 415 @Input nVtxNum vertex count 416 @Input pVtx vertices 417 @Input nStride Size of a vertex (in bytes) 418 @Input nOffsetWeight Offset in bytes to the vertex bone-weights 419 @Input eTypeWeight Data type of the vertex bone-weights 420 @Input nOffsetIdx Offset in bytes to the vertex bone-indices 421 @Input eTypeIdx Data type of the vertex bone-indices 422 @Input nTriNum Number of triangles 423 @Input nBatchBoneMax Number of bones a batch can reference 424 @Input nVertexBones Number of bones affecting each vertex 425 @Returns PVR_SUCCESS if successful 426 @Description Fills the bone batch structure 427 *****************************************************************************/ 428 EPVRTError CPVRTBoneBatches::Create( 429 int * const pnVtxNumOut, 430 char ** const pVtxOut, 431 unsigned int * const pui32Idx, 432 const int nVtxNum, 433 const char * const pVtx, 434 const int nStride, 435 const int nOffsetWeight, 436 const EPVRTDataType eTypeWeight, 437 const int nOffsetIdx, 438 const EPVRTDataType eTypeIdx, 439 const int nTriNum, 440 const int nBatchBoneMax, 441 const int nVertexBones) 442 { 443 int i, j, k, nTriCnt; 444 CBatch batch; 445 std::list<CBatch> lBatch; 446 std::list<CBatch>::iterator iBatch, iBatch2; 447 CBatch **ppBatch; 448 unsigned int *pui32IdxNew; 449 const char *pV, *pV2; 450 PVRTVECTOR4 vWeight, vIdx; 451 PVRTVECTOR4 vWeight2, vIdx2; 452 std::vector<int> *pvDup; 453 CGrowableArray *pVtxBuf; 454 unsigned int ui32SrcIdx; 455 456 memset(this, 0, sizeof(*this)); 457 458 if(nVertexBones <= 0 || nVertexBones > 4) 459 { 460 _RPT0(_CRT_WARN, "CPVRTBoneBatching() will only handle 1..4 bones per vertex.\n"); 461 return PVR_FAIL; 462 } 463 464 memset(&vWeight, 0, sizeof(vWeight)); 465 memset(&vWeight2, 0, sizeof(vWeight2)); 466 memset(&vIdx, 0, sizeof(vIdx)); 467 memset(&vIdx2, 0, sizeof(vIdx2)); 468 469 batch.SetSize(nBatchBoneMax); 470 471 // Allocate some working space 472 ppBatch = (CBatch**)malloc(nTriNum * sizeof(*ppBatch)); 473 pui32IdxNew = (unsigned int*)malloc(nTriNum * 3 * sizeof(*pui32IdxNew)); 474 pvDup = new std::vector<int>[nVtxNum]; 475 pVtxBuf = new CGrowableArray(nStride); 476 477 // Check what batches are necessary 478 for(i = 0; i < nTriNum; ++i) 479 { 480 // Build the batch 481 if(!FillBatch(batch, &pui32Idx[i * 3], pVtx, nStride, nOffsetWeight, eTypeWeight, nOffsetIdx, eTypeIdx, nVertexBones)) 482 { 483 free(pui32IdxNew); 484 return PVR_FAIL; 485 } 486 487 // Update the batch list 488 for(iBatch = lBatch.begin(); iBatch != lBatch.end(); ++iBatch) 489 { 490 // Do nothing if an existing batch is a superset of this new batch 491 if(iBatch->Contains(batch)) 492 { 493 break; 494 } 495 496 // If this new batch is a superset of an existing batch, replace the old with the new 497 if(batch.Contains(*iBatch)) 498 { 499 *iBatch = batch; 500 break; 501 } 502 } 503 504 // If no suitable batch exists, create a new one 505 if(iBatch == lBatch.end()) 506 { 507 lBatch.push_back(batch); 508 } 509 } 510 511 // Group batches into fewer batches. This simple greedy algorithm could be improved. 512 int nCurrent, nShortest; 513 std::list<CBatch>::iterator iShortest; 514 515 for(iBatch = lBatch.begin(); iBatch != lBatch.end(); ++iBatch) 516 { 517 for(;;) 518 { 519 nShortest = nBatchBoneMax; 520 iBatch2 = iBatch; 521 ++iBatch2; 522 for(; iBatch2 != lBatch.end(); ++iBatch2) 523 { 524 nCurrent = iBatch->TestMerge(*iBatch2); 525 526 if(nCurrent >= 0 && nCurrent < nShortest) 527 { 528 nShortest = nCurrent; 529 iShortest = iBatch2; 530 } 531 } 532 533 if(nShortest < nBatchBoneMax) 534 { 535 iBatch->Merge(*iShortest); 536 lBatch.erase(iShortest); 537 } 538 else 539 { 540 break; 541 } 542 } 543 } 544 545 // Place each triangle in a batch. 546 for(i = 0; i < nTriNum; ++i) 547 { 548 if(!FillBatch(batch, &pui32Idx[i * 3], pVtx, nStride, nOffsetWeight, eTypeWeight, nOffsetIdx, eTypeIdx, nVertexBones)) 549 { 550 free(pui32IdxNew); 551 return PVR_FAIL; 552 } 553 554 for(iBatch = lBatch.begin(); iBatch != lBatch.end(); ++iBatch) 555 { 556 if(iBatch->Contains(batch)) 557 { 558 ppBatch[i] = &*iBatch; 559 break; 560 } 561 } 562 563 _ASSERT(iBatch != lBatch.end()); 564 } 565 566 // Now that we know how many batches there are, we can allocate the output arrays 567 CPVRTBoneBatches::nBatchBoneMax = nBatchBoneMax; 568 pnBatches = (int*) calloc(lBatch.size() * nBatchBoneMax, sizeof(*pnBatches)); 569 pnBatchBoneCnt = (int*) calloc(lBatch.size(), sizeof(*pnBatchBoneCnt)); 570 pnBatchOffset = (int*) calloc(lBatch.size(), sizeof(*pnBatchOffset)); 571 572 // Create the new triangle index list, the new vertex list, and the batch information. 573 nTriCnt = 0; 574 nBatchCnt = 0; 575 576 for(iBatch = lBatch.begin(); iBatch != lBatch.end(); ++iBatch) 577 { 578 // Write pnBatches, pnBatchBoneCnt and pnBatchOffset for this batch. 579 iBatch->Write(&pnBatches[nBatchCnt * nBatchBoneMax], &pnBatchBoneCnt[nBatchCnt]); 580 pnBatchOffset[nBatchCnt] = nTriCnt; 581 ++nBatchCnt; 582 583 // Copy any triangle indices for this batch 584 for(i = 0; i < nTriNum; ++i) 585 { 586 if(ppBatch[i] != &*iBatch) 587 continue; 588 589 for(j = 0; j < 3; ++j) 590 { 591 ui32SrcIdx = pui32Idx[3 * i + j]; 592 593 // Get desired bone indices for this vertex/tri 594 pV = &pVtx[ui32SrcIdx * nStride]; 595 596 PVRTVertexRead(&vWeight, &pV[nOffsetWeight], eTypeWeight, nVertexBones); 597 PVRTVertexRead(&vIdx, &pV[nOffsetIdx], eTypeIdx, nVertexBones); 598 599 iBatch->GetVertexBoneIndices(&vIdx.x, &vWeight.x, nVertexBones); 600 _ASSERT(vIdx.x == 0 || vIdx.x != vIdx.y); 601 602 // Check the list of copies of this vertex for one with suitable bone indices 603 for(k = 0; k < (int)pvDup[ui32SrcIdx].size(); ++k) 604 { 605 pV2 = pVtxBuf->at(pvDup[ui32SrcIdx][k]); 606 607 PVRTVertexRead(&vWeight2, &pV2[nOffsetWeight], eTypeWeight, nVertexBones); 608 PVRTVertexRead(&vIdx2, &pV2[nOffsetIdx], eTypeIdx, nVertexBones); 609 610 if(BonesMatch(&vIdx2.x, &vIdx.x)) 611 { 612 pui32IdxNew[3 * nTriCnt + j] = pvDup[ui32SrcIdx][k]; 613 break; 614 } 615 } 616 617 if(k != (int)pvDup[ui32SrcIdx].size()) 618 continue; 619 620 // Did not find a suitable duplicate of the vertex, so create one 621 pVtxBuf->Append(pV, 1); 622 pvDup[ui32SrcIdx].push_back(pVtxBuf->size() - 1); 623 624 PVRTVertexWrite(&pVtxBuf->last()[nOffsetIdx], eTypeIdx, nVertexBones, &vIdx); 625 626 pui32IdxNew[3 * nTriCnt + j] = pVtxBuf->size() - 1; 627 } 628 ++nTriCnt; 629 } 630 } 631 _ASSERTE(nTriCnt == nTriNum); 632 _ASSERTE(nBatchCnt == (int)lBatch.size()); 633 634 // Copy indices to output 635 memcpy(pui32Idx, pui32IdxNew, nTriNum * 3 * sizeof(*pui32IdxNew)); 636 637 // Move vertices to output 638 *pnVtxNumOut = pVtxBuf->Surrender(pVtxOut); 639 640 // Free working memory 641 delete [] pvDup; 642 delete pVtxBuf; 643 FREE(ppBatch); 644 FREE(pui32IdxNew); 645 646 return PVR_SUCCESS; 647 } 648 649 /**************************************************************************** 650 ** Local functions 651 ****************************************************************************/ 652 653 /*!*********************************************************************** 654 @Function FillBatch 655 @Modified batch The batch to fill 656 @Input pui32Idx Input index array for triangle list 657 @Input pVtx Input vertices 658 @Input nStride Size of a vertex (in bytes) 659 @Input nOffsetWeight Offset in bytes to the vertex bone-weights 660 @Input eTypeWeight Data type of the vertex bone-weights 661 @Input nOffsetIdx Offset in bytes to the vertex bone-indices 662 @Input eTypeIdx Data type of the vertex bone-indices 663 @Input nVertexBones Number of bones affecting each vertex 664 @Returns True if successful 665 @Description Creates a bone batch from a triangle. 666 *************************************************************************/ 667 static bool FillBatch( 668 CBatch &batch, 669 const unsigned int * const pui32Idx, 670 const char * const pVtx, 671 const int nStride, 672 const int nOffsetWeight, 673 EPVRTDataType eTypeWeight, 674 const int nOffsetIdx, 675 EPVRTDataType eTypeIdx, 676 const int nVertexBones) 677 { 678 PVRTVECTOR4 vWeight, vIdx; 679 const char *pV; 680 int i; 681 bool bOk; 682 683 bOk = true; 684 batch.Clear(); 685 for(i = 0; i < 3; ++i) 686 { 687 pV = &pVtx[pui32Idx[i] * nStride]; 688 689 memset(&vWeight, 0, sizeof(vWeight)); 690 PVRTVertexRead(&vWeight, &pV[nOffsetWeight], eTypeWeight, nVertexBones); 691 PVRTVertexRead(&vIdx, &pV[nOffsetIdx], eTypeIdx, nVertexBones); 692 693 if(nVertexBones >= 1 && vWeight.x != 0) bOk &= batch.Add((int)vIdx.x); 694 if(nVertexBones >= 2 && vWeight.y != 0) bOk &= batch.Add((int)vIdx.y); 695 if(nVertexBones >= 3 && vWeight.z != 0) bOk &= batch.Add((int)vIdx.z); 696 if(nVertexBones >= 4 && vWeight.w != 0) bOk &= batch.Add((int)vIdx.w); 697 } 698 return bOk; 699 } 700 701 /*!*********************************************************************** 702 @Function BonesMatch 703 @Input pfIdx0 A float 4 array 704 @Input pfIdx1 A float 4 array 705 @Returns True if the two float4 arraus are identical 706 @Description Checks if the two float4 arrays are identical. 707 *************************************************************************/ 708 static bool BonesMatch( 709 const float * const pfIdx0, 710 const float * const pfIdx1) 711 { 712 int i; 713 714 for(i = 0; i < 4; ++i) 715 { 716 if(pfIdx0[i] != pfIdx1[i]) 717 return false; 718 } 719 720 return true; 721 } 722 723 /***************************************************************************** 724 End of file (PVRTBoneBatch.cpp) 725 *****************************************************************************/ 726 727