/******************************************************************************
|
|
@File PVRTBoneBatch.cpp
|
|
@Title PVRTBoneBatch
|
|
@Version
|
|
@Copyright Copyright (c) Imagination Technologies Limited.
|
|
@Platform ANSI compatible
|
|
@Description Utility functions which process vertices.
|
|
******************************************************************************/
|
|
/****************************************************************************
|
** Includes
|
****************************************************************************/
|
#include "PVRTGlobal.h"
|
#include "PVRTContext.h"
|
|
#include <vector>
|
#include <list>
|
|
#include "PVRTMatrix.h"
|
#include "PVRTVertex.h"
|
#include "PVRTBoneBatch.h"
|
|
/****************************************************************************
|
** Defines
|
****************************************************************************/
|
|
/****************************************************************************
|
** Macros
|
****************************************************************************/
|
|
/****************************************************************************
|
** Structures
|
****************************************************************************/
|
/*!***************************************************************************
|
@Class CBatch
|
@Brief Class to contain and manage batch information.
|
*****************************************************************************/
|
class CBatch
|
{
|
protected:
|
int m_nCapacity, // Maximum size of the batch
|
m_nCnt, // Number of elements currently contained in the batch
|
*m_pnPalette; // Array of palette indices
|
|
public:
|
/*!***************************************************************************
|
@Function CBatch
|
@Description The default constructor
|
*****************************************************************************/
|
CBatch() : m_nCapacity(0),
|
m_nCnt(0),
|
m_pnPalette(0)
|
{
|
}
|
|
/*!***************************************************************************
|
@Function CBatch
|
@Input src CBatch to copy
|
@Description Copy constructor
|
*****************************************************************************/
|
CBatch(const CBatch &src) : m_pnPalette(0)
|
{
|
SetSize(src.m_nCapacity);
|
*this = src;
|
}
|
|
/*!***************************************************************************
|
@Function ~CBatch
|
@Description Destructor
|
*****************************************************************************/
|
~CBatch()
|
{
|
FREE(m_pnPalette);
|
}
|
|
/*!***************************************************************************
|
@Function operator=
|
@Description Operator overload for the '=' operand
|
*****************************************************************************/
|
CBatch& operator= (const CBatch &src)
|
{
|
_ASSERT(m_nCapacity == src.m_nCapacity);
|
m_nCnt = src.m_nCnt;
|
memcpy(m_pnPalette, src.m_pnPalette, m_nCnt * sizeof(*m_pnPalette));
|
return *this;
|
}
|
|
/*!***************************************************************************
|
@Function SetSize
|
@Input nSize The new size of the batch
|
@Description Delete all current information and resizes the batch
|
to the value that has been passed in.
|
*****************************************************************************/
|
void SetSize(const int nSize)
|
{
|
FREE(m_pnPalette);
|
|
m_nCapacity = nSize;
|
m_nCnt = 0;
|
m_pnPalette = (int*)malloc(m_nCapacity * sizeof(*m_pnPalette));
|
}
|
|
/*!***************************************************************************
|
@Function Clear
|
@Description Resets the count
|
*****************************************************************************/
|
void Clear()
|
{
|
m_nCnt = 0;
|
}
|
|
/*!***************************************************************************
|
@Function Clear
|
@Input n The index of the new item
|
Return bool Returns true if the item already exists or has been added.
|
@Description Adds a new item to the batch, providing it has not already
|
been added to the batch and the count doesn't exceed the
|
maximum number of bones the batch can hold.
|
*****************************************************************************/
|
bool Add(const int n)
|
{
|
int i;
|
|
if(n < 0)
|
return false;
|
|
// If we already have this item, do nothing
|
for(i = 0; i < m_nCnt; ++i)
|
{
|
if(m_pnPalette[i] == n)
|
return true;
|
}
|
|
// Add the new item
|
if(m_nCnt < m_nCapacity)
|
{
|
m_pnPalette[m_nCnt] = n;
|
++m_nCnt;
|
return true;
|
}
|
else
|
{
|
return false;
|
}
|
}
|
|
/*!***************************************************************************
|
@Function Merge
|
@Input src The batch to merge with
|
@Description Merges the input batch with the current batch.
|
*****************************************************************************/
|
void Merge(const CBatch &src)
|
{
|
int i;
|
|
for(i = 0; i < src.m_nCnt; ++i)
|
Add(src.m_pnPalette[i]);
|
}
|
|
/*!***************************************************************************
|
@Function TestMerge
|
@Input src The batch to merge with
|
@Return int The number of items that are not already
|
present in the batch. -1 if the merge will
|
exceed the capacity of the batch
|
@Description Tests how many of the items of the input batch are not
|
already contained in the batch. This returns the number of
|
items that would need to be added, or -1 if the number
|
of additional items would exceed the capacity of the batch.
|
*****************************************************************************/
|
int TestMerge(const CBatch &src)
|
{
|
int i, nCnt;
|
|
nCnt = 0;
|
for(i = 0; i < src.m_nCnt; ++i)
|
if(!Contains(src.m_pnPalette[i]))
|
++nCnt;
|
|
return m_nCnt+nCnt > m_nCapacity ? -1 : nCnt;
|
}
|
|
/*!***************************************************************************
|
@Function Contains
|
@Input src The batch to compare
|
@Return bool Returns true if the batch and the input batch
|
have at least one item in common
|
@Description Returns true if the batch's have at least one item in common
|
*****************************************************************************/
|
bool Contains(const CBatch &batch) const
|
{
|
int i;
|
|
for(i = 0; i < batch.m_nCnt; ++i)
|
if(!Contains(batch.m_pnPalette[i]))
|
return false;
|
|
return true;
|
}
|
|
/*!***************************************************************************
|
@Function Contains
|
@Input n The index of the new item
|
@Return bool Returns true if the batch contains the item
|
@Description Returns true if the batch contains the item.
|
*****************************************************************************/
|
bool Contains(const int n) const
|
{
|
int i;
|
|
for(i = 0; i < m_nCnt; ++i)
|
if(m_pnPalette[i] == n)
|
return true;
|
|
return false;
|
}
|
|
/*!***************************************************************************
|
@Function Write
|
@Output pn The array of items to overwrite
|
@Output pnCnt The number of items in the array
|
@Description Writes the array of items and the number of items to the output
|
parameters.
|
*****************************************************************************/
|
void Write(
|
int * const pn,
|
int * const pnCnt) const
|
{
|
memcpy(pn, m_pnPalette, m_nCnt * sizeof(*pn));
|
*pnCnt = m_nCnt;
|
}
|
|
/*!***************************************************************************
|
@Function GetVertexBoneIndices
|
@Modified pfI Returned index
|
@Input pfW Weight?
|
@Input n Length of index array
|
@Description For each element of the input array, the index value is compared
|
with the palette's index value. If the values are equal, the
|
value of the current input array element is replaced with the
|
palette index, otherwise the value is set to zero.
|
*****************************************************************************/
|
void GetVertexBoneIndices(
|
float * const pfI,
|
const float * const pfW,
|
const int n)
|
{
|
int i, j;
|
|
for(i = 0; i < n; ++i)
|
{
|
if(pfW[i] != 0)
|
{
|
for(j = 0; j < m_nCnt; ++j)
|
{
|
if(pfI[i] != m_pnPalette[j])
|
continue;
|
|
pfI[i] = (float)j;
|
break;
|
}
|
|
// This batch *must* contain this vertex
|
_ASSERT(j != m_nCnt);
|
}
|
else
|
{
|
pfI[i] = 0;
|
}
|
}
|
}
|
};
|
|
/*!***************************************************************************
|
@Class CGrowableArray
|
@Brief Class that provides an array structure that can change its size dynamically.
|
*****************************************************************************/
|
class CGrowableArray
|
{
|
protected:
|
char *m_p;
|
int m_nSize;
|
int m_nCnt;
|
|
public:
|
/*!***************************************************************************
|
@Function CGrowableArray
|
@Input nSize The size of the data (in bytes) that the array will contain
|
@Description Initialises the size of the data the array will contain to the
|
value that has been passed in and initialises the remaining
|
data members with default values.
|
*****************************************************************************/
|
CGrowableArray(const int nSize)
|
{
|
m_p = NULL;
|
m_nSize = nSize;
|
m_nCnt = 0;
|
}
|
|
/*!***************************************************************************
|
@Function ~CGrowableArray
|
@Description The destructor
|
*****************************************************************************/
|
~CGrowableArray()
|
{
|
FREE(m_p);
|
}
|
|
/*!***************************************************************************
|
@Function Append
|
@Input pData The data to append
|
@Input nCnt The amount of data elements to append
|
@Description Resizes the array and appends the new data that has been passed in.
|
*****************************************************************************/
|
void Append(const void * const pData, const int nCnt)
|
{
|
m_p = (char*)realloc(m_p, (m_nCnt + nCnt) * m_nSize);
|
_ASSERT(m_p);
|
|
memcpy(&m_p[m_nCnt * m_nSize], pData, nCnt * m_nSize);
|
m_nCnt += nCnt;
|
}
|
|
/*!***************************************************************************
|
@Function last
|
@Return char* The last element of the array
|
@Description Returns a pointer to the last element of the array.
|
*****************************************************************************/
|
char *last()
|
{
|
return at(m_nCnt-1);
|
}
|
|
/*!***************************************************************************
|
@Function at
|
@Input nIdx The index of the requested element
|
@Return char* The element at the specified index of the array
|
@Description Returns a pointer to the data at the specified index of the array.
|
*****************************************************************************/
|
char *at(const int nIdx)
|
{
|
return &m_p[nIdx * m_nSize];
|
}
|
|
/*!***************************************************************************
|
@Function size
|
@Return int The number of elements contained in the array
|
@Description Returns the number of elements contained in the array.
|
*****************************************************************************/
|
int size() const
|
{
|
return m_nCnt;
|
}
|
|
/*!***************************************************************************
|
@Function Surrender
|
@Output pData The pointer to surrender the data to
|
@Description Assigns the memory address of the data to the pointer that has
|
been passed in. Sets the class's number of elements and
|
data pointer back to their default values.
|
*****************************************************************************/
|
int Surrender(
|
char ** const pData)
|
{
|
int nCnt;
|
|
*pData = m_p;
|
nCnt = m_nCnt;
|
|
m_p = NULL;
|
m_nCnt = 0;
|
|
return nCnt;
|
}
|
};
|
|
/****************************************************************************
|
** Constants
|
****************************************************************************/
|
|
/****************************************************************************
|
** Local function definitions
|
****************************************************************************/
|
static bool FillBatch(
|
CBatch &batch,
|
const unsigned int * const pui32Idx, // input AND output; index array for triangle list
|
const char * const pVtx, // Input vertices
|
const int nStride, // Size of a vertex (in bytes)
|
const int nOffsetWeight, // Offset in bytes to the vertex bone-weights
|
EPVRTDataType eTypeWeight, // Data type of the vertex bone-weights
|
const int nOffsetIdx, // Offset in bytes to the vertex bone-indices
|
EPVRTDataType eTypeIdx, // Data type of the vertex bone-indices
|
const int nVertexBones); // Number of bones affecting each vertex
|
|
static bool BonesMatch(
|
const float * const pfIdx0,
|
const float * const pfIdx1);
|
|
/*****************************************************************************
|
** Functions
|
*****************************************************************************/
|
|
/*!***************************************************************************
|
@Function Create
|
@Output pnVtxNumOut vertex count
|
@Output pVtxOut Output vertices (program must free() this)
|
@Modified pui32Idx index array for triangle list
|
@Input nVtxNum vertex count
|
@Input pVtx vertices
|
@Input nStride Size of a vertex (in bytes)
|
@Input nOffsetWeight Offset in bytes to the vertex bone-weights
|
@Input eTypeWeight Data type of the vertex bone-weights
|
@Input nOffsetIdx Offset in bytes to the vertex bone-indices
|
@Input eTypeIdx Data type of the vertex bone-indices
|
@Input nTriNum Number of triangles
|
@Input nBatchBoneMax Number of bones a batch can reference
|
@Input nVertexBones Number of bones affecting each vertex
|
@Returns PVR_SUCCESS if successful
|
@Description Fills the bone batch structure
|
*****************************************************************************/
|
EPVRTError CPVRTBoneBatches::Create(
|
int * const pnVtxNumOut,
|
char ** const pVtxOut,
|
unsigned int * const pui32Idx,
|
const int nVtxNum,
|
const char * const pVtx,
|
const int nStride,
|
const int nOffsetWeight,
|
const EPVRTDataType eTypeWeight,
|
const int nOffsetIdx,
|
const EPVRTDataType eTypeIdx,
|
const int nTriNum,
|
const int nBatchBoneMax,
|
const int nVertexBones)
|
{
|
int i, j, k, nTriCnt;
|
CBatch batch;
|
std::list<CBatch> lBatch;
|
std::list<CBatch>::iterator iBatch, iBatch2;
|
CBatch **ppBatch;
|
unsigned int *pui32IdxNew;
|
const char *pV, *pV2;
|
PVRTVECTOR4 vWeight, vIdx;
|
PVRTVECTOR4 vWeight2, vIdx2;
|
std::vector<int> *pvDup;
|
CGrowableArray *pVtxBuf;
|
unsigned int ui32SrcIdx;
|
|
memset(this, 0, sizeof(*this));
|
|
if(nVertexBones <= 0 || nVertexBones > 4)
|
{
|
_RPT0(_CRT_WARN, "CPVRTBoneBatching() will only handle 1..4 bones per vertex.\n");
|
return PVR_FAIL;
|
}
|
|
memset(&vWeight, 0, sizeof(vWeight));
|
memset(&vWeight2, 0, sizeof(vWeight2));
|
memset(&vIdx, 0, sizeof(vIdx));
|
memset(&vIdx2, 0, sizeof(vIdx2));
|
|
batch.SetSize(nBatchBoneMax);
|
|
// Allocate some working space
|
ppBatch = (CBatch**)malloc(nTriNum * sizeof(*ppBatch));
|
pui32IdxNew = (unsigned int*)malloc(nTriNum * 3 * sizeof(*pui32IdxNew));
|
pvDup = new std::vector<int>[nVtxNum];
|
pVtxBuf = new CGrowableArray(nStride);
|
|
// Check what batches are necessary
|
for(i = 0; i < nTriNum; ++i)
|
{
|
// Build the batch
|
if(!FillBatch(batch, &pui32Idx[i * 3], pVtx, nStride, nOffsetWeight, eTypeWeight, nOffsetIdx, eTypeIdx, nVertexBones))
|
{
|
free(pui32IdxNew);
|
return PVR_FAIL;
|
}
|
|
// Update the batch list
|
for(iBatch = lBatch.begin(); iBatch != lBatch.end(); ++iBatch)
|
{
|
// Do nothing if an existing batch is a superset of this new batch
|
if(iBatch->Contains(batch))
|
{
|
break;
|
}
|
|
// If this new batch is a superset of an existing batch, replace the old with the new
|
if(batch.Contains(*iBatch))
|
{
|
*iBatch = batch;
|
break;
|
}
|
}
|
|
// If no suitable batch exists, create a new one
|
if(iBatch == lBatch.end())
|
{
|
lBatch.push_back(batch);
|
}
|
}
|
|
// Group batches into fewer batches. This simple greedy algorithm could be improved.
|
int nCurrent, nShortest;
|
std::list<CBatch>::iterator iShortest;
|
|
for(iBatch = lBatch.begin(); iBatch != lBatch.end(); ++iBatch)
|
{
|
for(;;)
|
{
|
nShortest = nBatchBoneMax;
|
iBatch2 = iBatch;
|
++iBatch2;
|
for(; iBatch2 != lBatch.end(); ++iBatch2)
|
{
|
nCurrent = iBatch->TestMerge(*iBatch2);
|
|
if(nCurrent >= 0 && nCurrent < nShortest)
|
{
|
nShortest = nCurrent;
|
iShortest = iBatch2;
|
}
|
}
|
|
if(nShortest < nBatchBoneMax)
|
{
|
iBatch->Merge(*iShortest);
|
lBatch.erase(iShortest);
|
}
|
else
|
{
|
break;
|
}
|
}
|
}
|
|
// Place each triangle in a batch.
|
for(i = 0; i < nTriNum; ++i)
|
{
|
if(!FillBatch(batch, &pui32Idx[i * 3], pVtx, nStride, nOffsetWeight, eTypeWeight, nOffsetIdx, eTypeIdx, nVertexBones))
|
{
|
free(pui32IdxNew);
|
return PVR_FAIL;
|
}
|
|
for(iBatch = lBatch.begin(); iBatch != lBatch.end(); ++iBatch)
|
{
|
if(iBatch->Contains(batch))
|
{
|
ppBatch[i] = &*iBatch;
|
break;
|
}
|
}
|
|
_ASSERT(iBatch != lBatch.end());
|
}
|
|
// Now that we know how many batches there are, we can allocate the output arrays
|
CPVRTBoneBatches::nBatchBoneMax = nBatchBoneMax;
|
pnBatches = (int*) calloc(lBatch.size() * nBatchBoneMax, sizeof(*pnBatches));
|
pnBatchBoneCnt = (int*) calloc(lBatch.size(), sizeof(*pnBatchBoneCnt));
|
pnBatchOffset = (int*) calloc(lBatch.size(), sizeof(*pnBatchOffset));
|
|
// Create the new triangle index list, the new vertex list, and the batch information.
|
nTriCnt = 0;
|
nBatchCnt = 0;
|
|
for(iBatch = lBatch.begin(); iBatch != lBatch.end(); ++iBatch)
|
{
|
// Write pnBatches, pnBatchBoneCnt and pnBatchOffset for this batch.
|
iBatch->Write(&pnBatches[nBatchCnt * nBatchBoneMax], &pnBatchBoneCnt[nBatchCnt]);
|
pnBatchOffset[nBatchCnt] = nTriCnt;
|
++nBatchCnt;
|
|
// Copy any triangle indices for this batch
|
for(i = 0; i < nTriNum; ++i)
|
{
|
if(ppBatch[i] != &*iBatch)
|
continue;
|
|
for(j = 0; j < 3; ++j)
|
{
|
ui32SrcIdx = pui32Idx[3 * i + j];
|
|
// Get desired bone indices for this vertex/tri
|
pV = &pVtx[ui32SrcIdx * nStride];
|
|
PVRTVertexRead(&vWeight, &pV[nOffsetWeight], eTypeWeight, nVertexBones);
|
PVRTVertexRead(&vIdx, &pV[nOffsetIdx], eTypeIdx, nVertexBones);
|
|
iBatch->GetVertexBoneIndices(&vIdx.x, &vWeight.x, nVertexBones);
|
_ASSERT(vIdx.x == 0 || vIdx.x != vIdx.y);
|
|
// Check the list of copies of this vertex for one with suitable bone indices
|
for(k = 0; k < (int)pvDup[ui32SrcIdx].size(); ++k)
|
{
|
pV2 = pVtxBuf->at(pvDup[ui32SrcIdx][k]);
|
|
PVRTVertexRead(&vWeight2, &pV2[nOffsetWeight], eTypeWeight, nVertexBones);
|
PVRTVertexRead(&vIdx2, &pV2[nOffsetIdx], eTypeIdx, nVertexBones);
|
|
if(BonesMatch(&vIdx2.x, &vIdx.x))
|
{
|
pui32IdxNew[3 * nTriCnt + j] = pvDup[ui32SrcIdx][k];
|
break;
|
}
|
}
|
|
if(k != (int)pvDup[ui32SrcIdx].size())
|
continue;
|
|
// Did not find a suitable duplicate of the vertex, so create one
|
pVtxBuf->Append(pV, 1);
|
pvDup[ui32SrcIdx].push_back(pVtxBuf->size() - 1);
|
|
PVRTVertexWrite(&pVtxBuf->last()[nOffsetIdx], eTypeIdx, nVertexBones, &vIdx);
|
|
pui32IdxNew[3 * nTriCnt + j] = pVtxBuf->size() - 1;
|
}
|
++nTriCnt;
|
}
|
}
|
_ASSERTE(nTriCnt == nTriNum);
|
_ASSERTE(nBatchCnt == (int)lBatch.size());
|
|
// Copy indices to output
|
memcpy(pui32Idx, pui32IdxNew, nTriNum * 3 * sizeof(*pui32IdxNew));
|
|
// Move vertices to output
|
*pnVtxNumOut = pVtxBuf->Surrender(pVtxOut);
|
|
// Free working memory
|
delete [] pvDup;
|
delete pVtxBuf;
|
FREE(ppBatch);
|
FREE(pui32IdxNew);
|
|
return PVR_SUCCESS;
|
}
|
|
/****************************************************************************
|
** Local functions
|
****************************************************************************/
|
|
/*!***********************************************************************
|
@Function FillBatch
|
@Modified batch The batch to fill
|
@Input pui32Idx Input index array for triangle list
|
@Input pVtx Input vertices
|
@Input nStride Size of a vertex (in bytes)
|
@Input nOffsetWeight Offset in bytes to the vertex bone-weights
|
@Input eTypeWeight Data type of the vertex bone-weights
|
@Input nOffsetIdx Offset in bytes to the vertex bone-indices
|
@Input eTypeIdx Data type of the vertex bone-indices
|
@Input nVertexBones Number of bones affecting each vertex
|
@Returns True if successful
|
@Description Creates a bone batch from a triangle.
|
*************************************************************************/
|
static bool FillBatch(
|
CBatch &batch,
|
const unsigned int * const pui32Idx,
|
const char * const pVtx,
|
const int nStride,
|
const int nOffsetWeight,
|
EPVRTDataType eTypeWeight,
|
const int nOffsetIdx,
|
EPVRTDataType eTypeIdx,
|
const int nVertexBones)
|
{
|
PVRTVECTOR4 vWeight, vIdx;
|
const char *pV;
|
int i;
|
bool bOk;
|
|
bOk = true;
|
batch.Clear();
|
for(i = 0; i < 3; ++i)
|
{
|
pV = &pVtx[pui32Idx[i] * nStride];
|
|
memset(&vWeight, 0, sizeof(vWeight));
|
PVRTVertexRead(&vWeight, &pV[nOffsetWeight], eTypeWeight, nVertexBones);
|
PVRTVertexRead(&vIdx, &pV[nOffsetIdx], eTypeIdx, nVertexBones);
|
|
if(nVertexBones >= 1 && vWeight.x != 0) bOk &= batch.Add((int)vIdx.x);
|
if(nVertexBones >= 2 && vWeight.y != 0) bOk &= batch.Add((int)vIdx.y);
|
if(nVertexBones >= 3 && vWeight.z != 0) bOk &= batch.Add((int)vIdx.z);
|
if(nVertexBones >= 4 && vWeight.w != 0) bOk &= batch.Add((int)vIdx.w);
|
}
|
return bOk;
|
}
|
|
/*!***********************************************************************
|
@Function BonesMatch
|
@Input pfIdx0 A float 4 array
|
@Input pfIdx1 A float 4 array
|
@Returns True if the two float4 arraus are identical
|
@Description Checks if the two float4 arrays are identical.
|
*************************************************************************/
|
static bool BonesMatch(
|
const float * const pfIdx0,
|
const float * const pfIdx1)
|
{
|
int i;
|
|
for(i = 0; i < 4; ++i)
|
{
|
if(pfIdx0[i] != pfIdx1[i])
|
return false;
|
}
|
|
return true;
|
}
|
|
/*****************************************************************************
|
End of file (PVRTBoneBatch.cpp)
|
*****************************************************************************/
|
