/******************************************************************************
@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)
*****************************************************************************/