Add the ChameleonMan PowerVR sample.
BUG=14598298
Change-Id: Id6dcaebe793cf3d3a10af571348f461023d2a9d2
Reviewed-on: https://swiftshader-review.googlesource.com/1090
Reviewed-by: Nicolas Capens <nicolascapens@google.com>
diff --git a/tests/third_party/PowerVR/Tools/PVRTGeometry.cpp b/tests/third_party/PowerVR/Tools/PVRTGeometry.cpp
new file mode 100644
index 0000000..8c0cabe
--- /dev/null
+++ b/tests/third_party/PowerVR/Tools/PVRTGeometry.cpp
@@ -0,0 +1,1500 @@
+/******************************************************************************
+
+ @File PVRTGeometry.cpp
+
+ @Title PVRTGeometry
+
+ @Version
+
+ @Copyright Copyright (c) Imagination Technologies Limited.
+
+ @Platform Independant
+
+ @Description Code to affect triangle mesh geometry.
+
+******************************************************************************/
+
+/*****************************************************************************
+ For each vertex with only one free triangle
+ Start collecting triangles from there
+ Add the triangle which gives the highest triangles/vertex number (extra tris usually come for free)
+ When full, test against current best
+ If markedly better tri/vtx, take new block
+ If close-enough to prev tri/vtx, take block which closes the highest number of edges (and opens fewest)
+ If not quite full, goto 1 to continue filling block
+ If no block has been found, start at any free triangle and use resulting block
+ Copy block to output, empty it and goto 1.
+*****************************************************************************/
+
+/****************************************************************************
+** Build options
+****************************************************************************/
+#undef PVRTRISORT_ENABLE_VERIFY_RESULTS
+
+/****************************************************************************
+** Includes
+****************************************************************************/
+#include <vector>
+#include <math.h>
+
+#include "PVRTGeometry.h"
+
+#ifdef PVRTRISORT_ENABLE_VERIFY_RESULTS
+#include "PvrVGPBlockTest.h"
+#endif
+
+#include "PVRTGlobal.h"
+#include "PVRTContext.h"
+/****************************************************************************
+** Structures
+****************************************************************************/
+
+struct SVtx;
+
+/****************************************************************************
+@Function SEdg
+@Description Information about an "edge" - the shared boundary between two triangles
+****************************************************************************/
+struct SEdg {
+ const SVtx *psVtx[2]; // Identify the edge by the two vertices it joins
+ int nTriNumFree; // Number of triangle using this edge
+};
+
+/****************************************************************************
+@Function STri
+@Description Information about a triangle
+****************************************************************************/
+struct STri {
+ const PVRTGEOMETRY_IDX *pwIdx; // Vertex indices forming this triangle
+ SEdg *psEdg[3]; // Pointer to the three triangle edges
+ bool bUsed;
+};
+
+/****************************************************************************
+@Function SVtx
+@Description Information about a vertex
+****************************************************************************/
+struct SVtx {
+ STri **psTri; // Allocated array of pointers to the triangles sharing this vertex
+ int nTriNumTot; // Length of the above array
+ int nTriNumFree; // Number of triangles unused in the above array
+ SVtx **ppMeshPos; // Position in VtxByMesh list
+};
+
+/****************************************************************************
+@Function SMesh
+@Description Information about a mesh
+****************************************************************************/
+struct SMesh {
+ SVtx **ppVtx;
+ int nVtxNum;
+};
+
+/****************************************************************************
+@Function CObject
+@Description Information about an object (i.e. collection of mesh's to form
+ a single entity)
+****************************************************************************/
+class CObject {
+public:
+ STri *m_pTri; // Array of all the triangles in the mesh
+ SEdg *m_pEdg; // Array of all the edges in the mesh
+ SVtx *m_pVtx; // Array of all the vertices in a mesh
+
+ int m_nTriNumFree;
+
+ std::vector<SMesh> *m_pvMesh;
+ std::vector<SMesh> m_vMeshLg;
+
+protected:
+ int m_nVtxTot; // Total vertices in the object
+ int m_nEdgTot; // Total edges in the object
+ int m_nTriTot; // Total triangles in the object
+
+ int m_nVtxLimit; // Maximum number of vertices a block can contain
+ int m_nTriLimit; // Maximum number of triangles a block can contain
+
+ SVtx **m_ppVtxByMesh;
+
+public:
+ CObject(
+ const PVRTGEOMETRY_IDX * const pwIdx,
+ const int nVtxTot,
+ const int nTriTot,
+ const int nVtxLimit,
+ const int nTriLimit);
+
+ ~CObject();
+
+ int GetVertexCount() const;
+ int GetTriangleCount() const;
+ void SplitMesh(
+ SMesh * const pMesh,
+ const int nVtxNum,
+ SVtx ** const ppVtx);
+
+ void ResizeMesh(
+ const int nVtxNum,
+ SVtx ** const ppVtx);
+
+protected:
+ SEdg *BuildEdgeList(
+ const SVtx * const pVtx0,
+ const SVtx * const pVtx1);
+
+ void CreateMeshList();
+};
+
+/****************************************************************************
+@Function CBlockOption
+@Description A possible group of polygons to use
+****************************************************************************/
+struct CBlockOption {
+protected:
+ struct SEdgeDelta {
+ const SEdg *pEdg;
+ int nRefCnt;
+ };
+
+public:
+ int nVtxNum; // Number of vertices in the block
+ int nEdgNum; // Number of edges in the block
+ int nTriNum; // Number of triangles in the block
+
+ SVtx **psVtx; // Pointers to vertices
+protected:
+ SEdgeDelta *psEdgeDelta;
+ STri **psTri; // Pointers to triangles
+
+ int m_nVtxLimit; // Maximum number of vertices a block can contain
+ int m_nTriLimit; // Maximum number of triangles a block can contain
+
+public:
+ ~CBlockOption();
+
+ void Init(
+ const int nVtxLimit,
+ const int nTriLimit);
+ void Copy(const CBlockOption * const pSrc);
+
+ void Clear();
+
+ void Output(
+ PVRTGEOMETRY_IDX * const pwOut,
+ int * const pnVtxCnt,
+ int * const pnTriCnt,
+ const CObject * const pOb) const;
+
+ bool UsingVertex(const SVtx * const pVtx) const;
+ bool Contains(const STri * const pTri) const;
+
+ bool IsEmpty() const;
+ bool IsFull() const;
+
+ void AddVertex(SVtx * const pVtx);
+ void AddVertexCheckDup(SVtx * const pVtx);
+
+ void AddTriangleCheckDup(STri * const pTri);
+
+ void AddEdgeCheckDup(const SEdg * const pEdg);
+
+ void AddTriangle(STri * const pTri);
+
+ void AddOneTriangle(
+ STri * const pTri,
+ const CObject * const pOb);
+
+ int GetClosedEdgeDelta() const;
+ bool IsBetterThan(const CBlockOption * const pCmp) const;
+
+ void Add(
+ const CBlockOption * const pSrc,
+ const CObject * const pOb);
+
+ void Add(
+ const SMesh * const pMesh);
+};
+
+/****************************************************************************
+@Function CBlock
+@Description A model of a HW block (triangles and vertices)
+****************************************************************************/
+class CBlock {
+protected:
+ CBlockOption m_sOpt, m_sOptBest;
+
+ int m_nVtxLimit; // Maximum number of vertices a block can contain
+ int m_nTriLimit; // Maximum number of triangles a block can contain
+
+ CBlockOption m_sJob0, m_sJob1; // Workspace: to find the best triangle to add
+
+public:
+ CBlock(
+ const int nBufferVtxLimit,
+ const int nBufferTriLimit);
+
+ void Clear();
+
+ bool FillFrom(
+ SMesh * const pMesh,
+ SVtx * const pVtx,
+ CObject * const pOb);
+
+ int Fill(
+ CObject * const pOb);
+
+ void Output(
+ PVRTGEOMETRY_IDX * const pwOut,
+ int * const pnVtxCnt,
+ int * const pnTriCnt,
+ const CObject * const pOb) const;
+
+protected:
+ bool AddBestTrianglesAppraise(
+ CBlockOption * const pJob,
+ const CObject * const pOb,
+ const STri * const pTriAppraise);
+
+ void AddBestTriangles(CObject * const pOb);
+};
+
+/****************************************************************************
+** Local function prototypes
+****************************************************************************/
+
+/****************************************************************************
+@Function CObject
+@Input pwIdx Array of indices
+@Input nVrxTot Total number of vertices
+@Input nTriTot Total number of triangles
+@Input nVtxLimit Max number of vertices a block can contain
+@Input nTriLimit Max number of triangles a block can contain
+@Description The class's constructor.
+****************************************************************************/
+CObject::CObject(
+ const PVRTGEOMETRY_IDX * const pwIdx,
+ const int nVtxTot,
+ const int nTriTot,
+ const int nVtxLimit,
+ const int nTriLimit)
+{
+ int i;
+ SVtx *pVtx0, *pVtx1, *pVtx2;
+
+ m_nVtxLimit = nVtxLimit;
+ m_nTriLimit = nTriLimit;
+
+ m_pvMesh = new std::vector<SMesh>[nVtxLimit-2];
+ _ASSERT(m_pvMesh);
+
+ m_ppVtxByMesh = (SVtx**)calloc(nVtxTot, sizeof(*m_ppVtxByMesh));
+ _ASSERT(m_ppVtxByMesh);
+
+ m_nVtxTot = nVtxTot;
+ m_nEdgTot = 0;
+ m_nTriTot = nTriTot;
+
+ m_nTriNumFree = m_nTriTot;
+
+ m_pTri = (STri*)calloc(nTriTot, sizeof(*m_pTri));
+ _ASSERT(m_pTri);
+
+ m_pEdg = (SEdg*)calloc(nTriTot*3, sizeof(*m_pEdg)); // Allocate the maximum possible number of edges, though it should be far fewer than this
+ _ASSERT(m_pEdg);
+
+ m_pVtx = (SVtx*)calloc(nVtxTot, sizeof(*m_pVtx));
+ _ASSERT(m_pVtx);
+
+ // Run through triangles...
+ for(i = 0; i < nTriTot; ++i) {
+ pVtx0 = &m_pVtx[pwIdx[3*i+0]];
+ pVtx1 = &m_pVtx[pwIdx[3*i+1]];
+ pVtx2 = &m_pVtx[pwIdx[3*i+2]];
+
+ // Mark each vertex for the number of times it's referenced
+ ++pVtx0->nTriNumFree;
+ ++pVtx1->nTriNumFree;
+ ++pVtx2->nTriNumFree;
+
+ // Build the edge list
+ m_pTri[i].psEdg[0] = BuildEdgeList(pVtx0, pVtx1);
+ m_pTri[i].psEdg[1] = BuildEdgeList(pVtx1, pVtx2);
+ m_pTri[i].psEdg[2] = BuildEdgeList(pVtx2, pVtx0);
+ }
+
+ // Run through vertices, creating enough space for pointers to each triangle using this vertex
+ for(i = 0; i < nVtxTot; ++i)
+ m_pVtx[i].psTri = (STri**)calloc(m_pVtx[i].nTriNumFree, sizeof(*m_pVtx[i].psTri));
+
+ // Run through triangles, marking each vertex used with a pointer to this tri
+ for(i = 0; i < nTriTot; ++i) {
+ pVtx0 = &m_pVtx[pwIdx[3*i+0]];
+ pVtx1 = &m_pVtx[pwIdx[3*i+1]];
+ pVtx2 = &m_pVtx[pwIdx[3*i+2]];
+
+ pVtx0->psTri[pVtx0->nTriNumTot++] = &m_pTri[i];
+ pVtx1->psTri[pVtx1->nTriNumTot++] = &m_pTri[i];
+ pVtx2->psTri[pVtx2->nTriNumTot++] = &m_pTri[i];
+
+ // Give each triangle a pointer to its indices
+ m_pTri[i].pwIdx = &pwIdx[3*i];
+ }
+
+#ifdef _DEBUG
+ for(i = 0; i < nVtxTot; ++i) {
+ _ASSERTE(m_pVtx[i].nTriNumFree == m_pVtx[i].nTriNumTot);
+ }
+#endif
+
+ CreateMeshList();
+}
+
+/****************************************************************************
+@Function ~CObject
+@Description Destructor
+****************************************************************************/
+CObject::~CObject()
+{
+ _ASSERT(m_nTriNumFree == 0);
+
+ while(m_nVtxTot) {
+ --m_nVtxTot;
+ FREE(m_pVtx[m_nVtxTot].psTri);
+ _ASSERTE(m_pVtx[m_nVtxTot].nTriNumFree == 0);
+ _ASSERTE(m_pVtx[m_nVtxTot].ppMeshPos);
+ }
+
+#ifdef _DEBUG
+ while(m_nEdgTot) {
+ --m_nEdgTot;
+ _ASSERTE(m_pEdg[m_nEdgTot].nTriNumFree == 0);
+ }
+ while(m_nTriTot) {
+ --m_nTriTot;
+ _ASSERTE(m_pTri[m_nTriTot].bUsed);
+ }
+#endif
+
+ FREE(m_pTri);
+ FREE(m_pEdg);
+ FREE(m_pVtx);
+
+ delete [] m_pvMesh;
+ FREE(m_ppVtxByMesh);
+}
+
+/****************************************************************************
+@Function GetVertexCount
+@Return int
+@Description Return the vertex count
+****************************************************************************/
+int CObject::GetVertexCount() const
+{
+ return m_nVtxTot;
+}
+
+/****************************************************************************
+@Function GetTriangleCount
+@Return int
+@Description Return the triangle count
+****************************************************************************/
+int CObject::GetTriangleCount() const
+{
+ return m_nTriTot;
+}
+
+/****************************************************************************
+@Function BuildEdgeList
+@Input pVtx0 Edge 0
+@Input pVtx1 Edge 1
+@Return SEdg*
+@Description If the vertices that have been passed in are already used by an edge,
+ the number of triangles sharing the edge is increased by one and a
+ pointer to the edge is returned. If the edge is not already in the
+ list, the edge is added to the list.
+****************************************************************************/
+SEdg *CObject::BuildEdgeList(
+ const SVtx * const pVtx0,
+ const SVtx * const pVtx1)
+{
+ SEdg *pEdg;
+ const SVtx *pVtxL, *pVtxH;
+ int i;
+
+ pVtxL = pVtx0 < pVtx1 ? pVtx0 : pVtx1;
+ pVtxH = pVtx0 > pVtx1 ? pVtx0 : pVtx1;
+
+ // Do nothing if the edge already exists
+ i = m_nEdgTot;
+ while(i) {
+ --i;
+
+ pEdg = &m_pEdg[i];
+ if(pEdg->psVtx[0] == pVtxL && pEdg->psVtx[1] == pVtxH)
+ {
+ ++pEdg->nTriNumFree;
+ return pEdg;
+ }
+ }
+
+ // Add the new edge
+ _ASSERT(m_nEdgTot < m_nTriTot*3);
+ pEdg = &m_pEdg[m_nEdgTot++];
+ pEdg->psVtx[0] = pVtxL;
+ pEdg->psVtx[1] = pVtxH;
+ pEdg->nTriNumFree = 1;
+
+ return pEdg;
+}
+
+/****************************************************************************
+@Function CreateMeshList
+@Description Creates the mesh list
+****************************************************************************/
+void CObject::CreateMeshList()
+{
+ SVtx **ppR, **ppW, *pVtx;
+ STri *pTri;
+ int i, j, k;
+ SMesh sMesh;
+ int nMeshCnt;
+
+ nMeshCnt = 0;
+
+ ppR = m_ppVtxByMesh;
+ ppW = m_ppVtxByMesh;
+
+ for(i = 0; i < m_nVtxTot; ++i) {
+ pVtx = &m_pVtx[i];
+
+ if(pVtx->ppMeshPos) {
+ _ASSERT(pVtx->ppMeshPos < ppW);
+ continue;
+ }
+
+ ++nMeshCnt;
+ sMesh.ppVtx = ppW;
+
+ *ppW = pVtx;
+ pVtx->ppMeshPos = ppW;
+ ++ppW;
+
+ do {
+ // Add all the vertices of all the triangles of *ppR to the list - unless they're already in there
+ for(j = 0; j < (*ppR)->nTriNumTot; ++j) {
+ pTri = (*ppR)->psTri[j];
+
+ for(k = 0; k < 3; ++k) {
+ pVtx = &m_pVtx[pTri->pwIdx[k]];
+
+ if(pVtx->ppMeshPos) {
+ _ASSERT(pVtx->ppMeshPos < ppW);
+ continue;
+ }
+
+ *ppW = pVtx;
+ pVtx->ppMeshPos = ppW;
+ ++ppW;
+ }
+ }
+
+ ++ppR;
+ } while(ppR != ppW);
+
+ sMesh.nVtxNum = (int)(ppR - sMesh.ppVtx);
+// _RPT2(_CRT_WARN, "CreateMeshList() mesh %d %dvtx\n", nMeshCnt, sMesh.nVtxNum);
+ if(sMesh.nVtxNum >= 3)
+ {
+ if(sMesh.nVtxNum >= m_nVtxLimit)
+ m_vMeshLg.push_back(sMesh);
+ else
+ m_pvMesh[sMesh.nVtxNum-3].push_back(sMesh);
+ }
+ else
+ {
+ /*
+ Vertex is not used by any triangles; this may be because we're
+ optimising a subset of the mesh (e.g. for bone batching).
+ */
+ _ASSERT(sMesh.nVtxNum == 1);
+ }
+ }
+
+ _ASSERT(ppR == &m_ppVtxByMesh[m_nVtxTot]);
+ _ASSERT(ppW == &m_ppVtxByMesh[m_nVtxTot]);
+// _RPT1(_CRT_WARN, "CreateMeshList() %d meshes\n", nMeshCnt);
+
+#ifdef _DEBUG
+/* for(i = 0; i < m_nVtxLimit-2; ++i)
+ if(m_pvMesh[i].size())
+ _RPT2(_CRT_WARN, "%d:%d ", i+3, m_pvMesh[i].size());
+ _RPT1(_CRT_WARN, "lg:%d\n", m_vMeshLg.size());*/
+#endif
+}
+
+/****************************************************************************
+@Function SplitMesh
+@Input pMesh Pointer to mesh data
+@Input nVtxNum Number of vertices in the mesh?
+@Output ppVtx Array of vertices
+@Description Note: Ask Aaron
+****************************************************************************/
+void CObject::SplitMesh(
+ SMesh * const pMesh,
+ const int nVtxNum,
+ SVtx ** const ppVtx)
+{
+ SVtx *pTmp;
+ int i;
+ SMesh sNew;
+
+ _ASSERT(nVtxNum);
+
+ for(i = 0; i < nVtxNum; ++i) {
+ pTmp = pMesh->ppVtx[i]; // Keep a record of the old vtx that's already here
+
+ pMesh->ppVtx[i] = ppVtx[i]; // Move the new vtx into place
+ *ppVtx[i]->ppMeshPos = pTmp; // Move the old vtx into place
+
+ pTmp->ppMeshPos = ppVtx[i]->ppMeshPos; // Tell the old vtx where it is now
+ ppVtx[i]->ppMeshPos = &pMesh->ppVtx[i]; // Tell the new vtx where it is now
+
+ _ASSERT(pMesh->ppVtx[i]->nTriNumFree);
+ }
+
+ sNew.nVtxNum = nVtxNum;
+ sNew.ppVtx = pMesh->ppVtx;
+ m_pvMesh[nVtxNum-3].push_back(sNew);
+
+ pMesh->ppVtx = &pMesh->ppVtx[nVtxNum];
+ pMesh->nVtxNum -= nVtxNum;
+ if(pMesh->nVtxNum < m_nVtxLimit) {
+ ResizeMesh(pMesh->nVtxNum, pMesh->ppVtx);
+ m_vMeshLg.pop_back();
+#ifdef _DEBUG
+/* } else {
+ for(i = 0; i < m_nVtxLimit-2; ++i)
+ if(m_pvMesh[i].size())
+ _RPT2(_CRT_WARN, "%d:%d ", i+3, m_pvMesh[i].size());
+ _RPT1(_CRT_WARN, "lg:%d\n", m_vMeshLg.size());*/
+#endif
+ }
+}
+
+/****************************************************************************
+@Function ResizeMesh
+@Input nVtxNum The size of the array of vertices being passed in
+@Input ppVtx Array of vertices
+@Description Note: Ask Aaron
+****************************************************************************/
+void CObject::ResizeMesh(
+ const int nVtxNum,
+ SVtx ** const ppVtx)
+{
+ SVtx **ppR, **ppW;
+ SMesh sNew;
+ int i;
+
+ ppR = ppVtx;
+ ppW = ppVtx;
+
+ // Make a list of vertices that have unused triangles in their array of triangles
+ for(i = 0; i < nVtxNum; ++i) {
+ if((*ppR)->nTriNumFree) {
+ (*ppW) = (*ppR);
+ ++ppW;
+ }
+ ++ppR;
+ }
+
+ sNew.nVtxNum = (int)(ppW - ppVtx);
+ _ASSERT(sNew.nVtxNum <= nVtxNum);
+
+ // If any mesh still exists, add it to the relevant list
+ if(sNew.nVtxNum) {
+ _ASSERT(sNew.nVtxNum >= 3);
+ _ASSERT(sNew.nVtxNum < m_nVtxLimit);
+
+ sNew.ppVtx = ppVtx;
+ m_pvMesh[sNew.nVtxNum-3].push_back(sNew);
+ }
+
+#ifdef _DEBUG
+/* for(i = 0; i < m_nVtxLimit-2; ++i)
+ if(m_pvMesh[i].size())
+ _RPT2(_CRT_WARN, "%d:%d ", i+3, m_pvMesh[i].size());
+ _RPT1(_CRT_WARN, "lg:%d\n", m_vMeshLg.size());*/
+#endif
+}
+
+/****************************************************************************
+@Function ~CBlockOption
+@Description Default destructor
+****************************************************************************/
+CBlockOption::~CBlockOption()
+{
+ FREE(psVtx);
+ FREE(psTri);
+ FREE(psEdgeDelta);
+}
+
+/****************************************************************************
+@Function Init
+@Input nVertexLimit The maximum number of vertices a block can contain
+@Input nTriLimit The maximum number of triangles a block can contain
+@Description Initialises the class
+****************************************************************************/
+void CBlockOption::Init(
+ const int nVtxLimit,
+ const int nTriLimit)
+{
+ m_nVtxLimit = nVtxLimit;
+ m_nTriLimit = nTriLimit;
+
+ psVtx = (SVtx**)malloc(nVtxLimit * sizeof(*psVtx));
+ psTri = (STri**)malloc(nTriLimit * sizeof(*psTri));
+ psEdgeDelta = (SEdgeDelta*)malloc(3 * nTriLimit * sizeof(*psEdgeDelta));
+}
+
+/****************************************************************************
+@Function Copy
+@Input pSrc Pointer to the source data
+@Description Overwrites the data in the current instance with the data from
+ the input CBlockOption.
+****************************************************************************/
+void CBlockOption::Copy(const CBlockOption * const pSrc)
+{
+ nVtxNum = pSrc->nVtxNum;
+ nEdgNum = pSrc->nEdgNum;
+ nTriNum = pSrc->nTriNum;
+
+ memcpy(psVtx, pSrc->psVtx, nVtxNum * sizeof(*psVtx));
+ memcpy(psEdgeDelta, pSrc->psEdgeDelta, nEdgNum * sizeof(*psEdgeDelta));
+ memcpy(psTri, pSrc->psTri, nTriNum * sizeof(*psTri));
+}
+
+/****************************************************************************
+@Function Clear
+@Description Sets the value of the number of vertices, edges and triangles
+ to zero.
+****************************************************************************/
+void CBlockOption::Clear()
+{
+ nVtxNum = 0;
+ nEdgNum = 0;
+ nTriNum = 0;
+}
+
+/****************************************************************************
+@Function Output
+@Output pwOut Index output
+@Output pnVtxCnt Vertex count
+@Output pnTriCnt Triangle count
+@Modified pOb Pointer to an object
+@Description Outputs key information about the instance of CBlockOption
+****************************************************************************/
+void CBlockOption::Output(
+ PVRTGEOMETRY_IDX * const pwOut,
+ int * const pnVtxCnt,
+ int * const pnTriCnt,
+ const CObject * const pOb) const
+{
+ STri *pTri;
+ int i, j;
+
+ for(i = 0; i < nTriNum; ++i) {
+ pTri = psTri[i];
+
+ _ASSERT(!pTri->bUsed);
+
+ for(j = 0; j < 3; ++j) {
+ _ASSERT(pOb->m_pVtx[pTri->pwIdx[j]].nTriNumFree > 0);
+ _ASSERT(pTri->psEdg[j]->nTriNumFree > 0);
+
+ --pOb->m_pVtx[pTri->pwIdx[j]].nTriNumFree;
+ --pTri->psEdg[j]->nTriNumFree;
+
+ _ASSERT(pOb->m_pVtx[pTri->pwIdx[j]].nTriNumFree >= 0);
+ _ASSERT(pTri->psEdg[j]->nTriNumFree >= 0);
+ }
+
+ pTri->bUsed = true;
+
+ // Copy indices into output
+ memcpy(&pwOut[3*i], pTri->pwIdx, 3 * sizeof(*pTri->pwIdx));
+ }
+
+ *pnVtxCnt = nVtxNum;
+ *pnTriCnt = nTriNum;
+}
+
+/****************************************************************************
+@Function UsingVertex
+@Input pVtx Vertex to compare
+@Return bool True on success
+@Description Returns true if the supplied vertex is already being used
+ in the block option.
+****************************************************************************/
+bool CBlockOption::UsingVertex(
+ const SVtx * const pVtx) const
+{
+ int i;
+
+ i = nVtxNum;
+ while(i) {
+ --i;
+
+ if(psVtx[i] == pVtx)
+ return true;
+ }
+
+ return false;
+}
+
+/****************************************************************************
+@Function Contains
+@Input pVtx Triangle to compare
+@Return bool True on success
+@Description Returns true if the supplied triangle is already being used
+ in the block option.
+****************************************************************************/
+bool CBlockOption::Contains(const STri * const pTri) const
+{
+ int i;
+
+ i = nTriNum;
+ while(i) {
+ --i;
+
+ if(psTri[i] == pTri)
+ return true;
+ }
+
+ return false;
+}
+
+/****************************************************************************
+@Function IsEmpty
+@Return bool True if the block option is empty
+@Description Returns true if the block option is empty.
+****************************************************************************/
+bool CBlockOption::IsEmpty() const
+{
+ return !(nVtxNum + nEdgNum + nTriNum);
+}
+
+/****************************************************************************
+@Function IsFull
+@Return bool True if the block option is full
+@Description Returns true if the block option is full.
+****************************************************************************/
+bool CBlockOption::IsFull() const
+{
+ return (m_nVtxLimit - nVtxNum) < 3 || nTriNum == m_nTriLimit;
+}
+
+/****************************************************************************
+@Function AddVertex
+@Input pVtx Vertex to add
+@Description Providing the current number of vertices is less than the
+ maximum, the input vertex is added to the end of the array.
+****************************************************************************/
+void CBlockOption::AddVertex(SVtx * const pVtx)
+{
+ _ASSERT(nVtxNum < m_nVtxLimit);
+ psVtx[nVtxNum++] = pVtx;
+}
+
+/****************************************************************************
+@Function AddVertexCheckDup
+@Input pVtx Vertex to add
+@Description Checks that the input vertex is not already contained in the
+ vertex array. If it is new, it is added to the array.
+****************************************************************************/
+void CBlockOption::AddVertexCheckDup(SVtx * const pVtx)
+{
+ int i;
+
+ for(i = 0; i < nVtxNum; ++i)
+ if(psVtx[i] == pVtx)
+ return;
+
+ AddVertex(pVtx);
+}
+
+/****************************************************************************
+@Function AddTriangleCheckDup
+@Input pTri Triangle to add
+@Description Checks that the input triangle is not already contained in the
+ triangle array. If it is new, it is added to the array.
+****************************************************************************/
+void CBlockOption::AddTriangleCheckDup(STri * const pTri)
+{
+ int i;
+
+ for(i = 0; i < nTriNum; ++i)
+ if(psTri[i] == pTri)
+ return;
+
+ _ASSERT(nTriNum < m_nTriLimit);
+ psTri[nTriNum++] = pTri;
+}
+
+/****************************************************************************
+@Function AddEdgeCheckDup
+@Input pEdg Edge to add
+@Description Checks that the input edge is not already contained in the
+ edge array. If it is new, it is added to the array.
+****************************************************************************/
+void CBlockOption::AddEdgeCheckDup(const SEdg * const pEdg)
+{
+ int i;
+
+ for(i = 0; i < nEdgNum; ++i) {
+ if(psEdgeDelta[i].pEdg == pEdg) {
+ ++psEdgeDelta[i].nRefCnt;
+ return;
+ }
+ }
+
+ _ASSERT(nEdgNum < 3*m_nTriLimit);
+ psEdgeDelta[nEdgNum].pEdg = pEdg;
+ psEdgeDelta[nEdgNum].nRefCnt = 1;
+ ++nEdgNum;
+}
+
+/****************************************************************************
+@Function AddTriangle
+@Input pTri Triangle to add
+@Description Providing the current number of triangles is less than the
+ maximum, the input triangle is added to the end of the array.
+ Once this has been done, the array of edges is updated.
+****************************************************************************/
+// TODO: if this is only used to add fresh triangles, all edges must be added
+void CBlockOption::AddTriangle(STri * const pTri)
+{
+ int i;
+
+ _ASSERT(nTriNum < m_nTriLimit);
+ psTri[nTriNum++] = pTri;
+
+ // Keep a count of edges and the number of tris which share them
+ for(i = 0; i < 3; ++i)
+ AddEdgeCheckDup(pTri->psEdg[i]);
+}
+
+/****************************************************************************
+@Function AddOneTriangle
+@Input pTri Triangle to add
+@Input pOb Object to copy vertices from
+@Description Calls the AddTriangle function.
+ Once this has been done, the array of vertices is updated.
+****************************************************************************/
+// TODO: if this is only called to add a fresh start triangle, all vertices must be added
+void CBlockOption::AddOneTriangle(
+ STri * const pTri,
+ const CObject * const pOb)
+{
+ int i;
+
+ // Add the triangle to the block
+ AddTriangle(pTri);
+
+ // Add the vertices to the block
+ for(i = 0; i < 3; ++i)
+ AddVertexCheckDup(&pOb->m_pVtx[pTri->pwIdx[i]]);
+}
+
+/****************************************************************************
+@Function GetClosedEdgeDelta
+@Return int The delta value of closed edges
+@Description This method returns a value that represents the average state of
+ the edges. If the value is greater than zero, the majority of
+ edges are closed. If the value is less than zero, the majority
+ of edges are open.
+****************************************************************************/
+int CBlockOption::GetClosedEdgeDelta() const
+{
+ int i, nDelta;
+
+ nDelta = 0;
+ for(i = 0; i < nEdgNum; ++i) {
+ _ASSERT(psEdgeDelta[i].pEdg->nTriNumFree >= psEdgeDelta[i].nRefCnt);
+
+ // Check how many tris will use the edge if these are taken away
+ switch(psEdgeDelta[i].pEdg->nTriNumFree - psEdgeDelta[i].nRefCnt) {
+ case 0:
+ // If the edge was open, and is now closed, that's good
+ if(psEdgeDelta[i].pEdg->nTriNumFree == 1)
+ ++nDelta;
+ break;
+ case 1:
+ // if the edge is now open, that's bad
+ --nDelta;
+ break;
+ }
+ }
+
+ return nDelta;
+}
+
+/****************************************************************************
+@Function IsBetterThan
+@Input pCmp The block option to compare with
+@Return bool True if the current block option is best
+@Description Returns true if the current block option is better than the
+ block option that has been passed in. Otherwise, it returns false.
+****************************************************************************/
+bool CBlockOption::IsBetterThan(const CBlockOption * const pCmp) const
+{
+ float fWorth0, fWorth1;
+ int nClosed0, nClosed1;
+
+ // Check "worth" - TrisAdded/VtxAdded
+ fWorth0 = (float)nTriNum / (float)nVtxNum;
+ fWorth1 = (float)pCmp->nTriNum / (float)pCmp->nVtxNum;
+
+ nClosed0 = GetClosedEdgeDelta();
+ nClosed1 = pCmp->GetClosedEdgeDelta();
+
+ if(fabsf(fWorth0 - fWorth1) > 0.1f) {
+ return fWorth0 > fWorth1;
+ } else if(nClosed0 != nClosed1) {
+ return nClosed0 > nClosed1;
+ } else {
+ return nTriNum > pCmp->nTriNum;
+ }
+}
+
+/****************************************************************************
+@Function Add
+@Input pSrc The block option to add
+@Input pOb Object to use vertices from
+@Description Add's the input vertex and triangle data to the current block option
+****************************************************************************/
+void CBlockOption::Add(
+ const CBlockOption * const pSrc,
+ const CObject * const pOb)
+{
+ PVRT_UNREFERENCED_PARAMETER(pOb);
+
+ int i;
+
+ // Add vertices from job to block
+ for(i = 0; i < pSrc->nVtxNum; ++i)
+ AddVertexCheckDup(pSrc->psVtx[i]);
+
+ // Add triangles from job to block
+ for(i = 0; i < pSrc->nTriNum; ++i)
+ AddTriangle(pSrc->psTri[i]);
+}
+
+/****************************************************************************
+@Function Add
+@Input pMesh The mesh to add
+@Description Add's the input mesh to the current block option
+****************************************************************************/
+void CBlockOption::Add(
+ const SMesh * const pMesh)
+{
+ int i, j;
+ SVtx *pVtx;
+
+ for(i = 0; i < pMesh->nVtxNum; ++i) {
+ pVtx = pMesh->ppVtx[i];
+
+ AddVertexCheckDup(pVtx);
+
+ for(j = 0; j < pVtx->nTriNumTot; ++j) {
+ if(!pVtx->psTri[j]->bUsed)
+ AddTriangleCheckDup(pVtx->psTri[j]);
+ }
+ }
+}
+
+/****************************************************************************
+@Function CBlock
+@Description Default constructor
+****************************************************************************/
+CBlock::CBlock(
+ const int nBufferVtxLimit,
+ const int nBufferTriLimit)
+{
+ m_nVtxLimit = nBufferVtxLimit;
+ m_nTriLimit = nBufferTriLimit;
+
+ m_sOpt.Init(m_nVtxLimit, m_nTriLimit);
+ m_sOptBest.Init(m_nVtxLimit, m_nTriLimit);
+
+ // Intialise "job" blocks
+ m_sJob0.Init(3, m_nTriLimit);
+ m_sJob1.Init(3, m_nTriLimit);
+}
+
+/****************************************************************************
+@Function Clear
+@Description Clears the current and best block options
+****************************************************************************/
+void CBlock::Clear()
+{
+ m_sOpt.Clear();
+ m_sOptBest.Clear();
+}
+
+/****************************************************************************
+@Function Output
+@Output pwOut Index output
+@Output pnVtxCnt Vertex count
+@Output pnTriCnt Triangle count
+@Modified pOb Pointer to an object
+@Description Outputs key information about the instance of CBlockOption
+****************************************************************************/
+void CBlock::Output(
+ PVRTGEOMETRY_IDX * const pwOut,
+ int * const pnVtxCnt,
+ int * const pnTriCnt,
+ const CObject * const pOb) const
+{
+ m_sOptBest.Output(pwOut, pnVtxCnt, pnTriCnt, pOb);
+}
+
+/****************************************************************************
+@Function AddBestTrianglesAppraise
+@Modified pJob The block object to alter
+@Input pOb The object
+@Input pTriAppraise The triangle to appraise
+@Return bool
+@Description Uses the input object and triangle to create a new block option.
+****************************************************************************/
+bool CBlock::AddBestTrianglesAppraise(
+ CBlockOption * const pJob,
+ const CObject * const pOb,
+ const STri * const pTriAppraise)
+{
+ SVtx *pVtx;
+ STri *pTri;
+ int i, j;
+
+ pJob->Clear();
+
+ // Add vertices
+ for(i = 0; i < 3; ++i) {
+ pVtx = &pOb->m_pVtx[pTriAppraise->pwIdx[i]];
+ if(!m_sOpt.UsingVertex(pVtx))
+ pJob->AddVertex(pVtx);
+ }
+
+ if(pJob->nVtxNum > (m_nVtxLimit-m_sOpt.nVtxNum))
+ return false;
+
+ // Add triangles referenced by each vertex
+ for(i = 0; i < 3; ++i) {
+ pVtx = &pOb->m_pVtx[pTriAppraise->pwIdx[i]];
+
+ _ASSERT(pVtx->nTriNumFree >= 1);
+ _ASSERT(pVtx->nTriNumFree <= pVtx->nTriNumTot);
+
+ for(j = 0; j < pVtx->nTriNumTot; ++j) {
+ if(pJob->nTriNum >= (m_nTriLimit-m_sOpt.nTriNum))
+ break;
+
+ pTri = pVtx->psTri[j];
+
+ // Don't count the same triangle twice!
+ if(pTri->bUsed || m_sOpt.Contains(pTri) || pJob->Contains(pTri))
+ continue;
+
+ // If all the triangle's vertices are or will be in the block, then increase nTri
+ if(
+ (
+ pTri->pwIdx[0] == pTriAppraise->pwIdx[0] ||
+ pTri->pwIdx[0] == pTriAppraise->pwIdx[1] ||
+ pTri->pwIdx[0] == pTriAppraise->pwIdx[2] ||
+ m_sOpt.UsingVertex(&pOb->m_pVtx[pTri->pwIdx[0]])
+ ) && (
+ pTri->pwIdx[1] == pTriAppraise->pwIdx[0] ||
+ pTri->pwIdx[1] == pTriAppraise->pwIdx[1] ||
+ pTri->pwIdx[1] == pTriAppraise->pwIdx[2] ||
+ m_sOpt.UsingVertex(&pOb->m_pVtx[pTri->pwIdx[1]])
+ ) && (
+ pTri->pwIdx[2] == pTriAppraise->pwIdx[0] ||
+ pTri->pwIdx[2] == pTriAppraise->pwIdx[1] ||
+ pTri->pwIdx[2] == pTriAppraise->pwIdx[2] ||
+ m_sOpt.UsingVertex(&pOb->m_pVtx[pTri->pwIdx[2]])
+ )
+ )
+ {
+ pJob->AddTriangle(pTri);
+ }
+ }
+ }
+
+ _ASSERT(pJob->nTriNum);
+ _ASSERT(pJob->nTriNum <= (m_nTriLimit-m_sOpt.nTriNum));
+
+ return true;
+}
+
+/****************************************************************************
+@Function AddBestTriangles
+@Input pOb The object
+@Description Finds the best triangles and adds them to the current block option (m_sOpt)
+****************************************************************************/
+void CBlock::AddBestTriangles(CObject * const pOb)
+{
+ int i, j;
+ const SVtx *pVtx;
+ STri *pTri;
+ CBlockOption *pJob, *pJobBest;
+
+ pJob = &m_sJob0;
+
+ do {
+ pJobBest = 0;
+
+ for(i = 0; i < m_sOpt.nVtxNum; ++i) {
+ pVtx = m_sOpt.psVtx[i];
+
+ if(!pVtx->nTriNumFree)
+ continue;
+
+ for(j = 0; j < pVtx->nTriNumTot; ++j) {
+ pTri = pVtx->psTri[j];
+
+ if(pTri->bUsed || m_sOpt.Contains(pTri))
+ continue;
+
+ // Find out how many triangles and vertices this tri adds
+ if(!AddBestTrianglesAppraise(pJob, pOb, pTri))
+ continue;
+
+ if(!pJobBest || pJob->IsBetterThan(pJobBest)) {
+ pJobBest = pJob;
+ pJob = (pJob == &m_sJob0 ? &m_sJob1 : &m_sJob0);
+ }
+ }
+ }
+
+ if(pJobBest) {
+ m_sOpt.Add(pJobBest, pOb);
+ }
+ } while(pJobBest && m_nTriLimit != m_sOpt.nTriNum);
+}
+
+/****************************************************************************
+@Function FillFrom
+@Input pMesh Mesh to fill with
+@Input pVtx Vertex to fill with
+@Input pOb Object to fill with
+@Return bool Returns true if the current block option isn't full
+@Description Returns TRUE if Fill() needs to be called again - i.e. blockOption is already filled
+****************************************************************************/
+bool CBlock::FillFrom(
+ SMesh * const pMesh,
+ SVtx * const pVtx,
+ CObject * const pOb)
+{
+ // Let's try starting from this vertex then
+ _ASSERT(pVtx->nTriNumFree);
+ m_sOpt.Clear();
+ m_sOpt.AddVertex(pVtx);
+ AddBestTriangles(pOb);
+
+ if(m_sOpt.IsFull()) {
+ if(m_sOptBest.IsEmpty() || m_sOpt.IsBetterThan(&m_sOptBest))
+ m_sOptBest.Copy(&m_sOpt);
+ return false;
+ }
+ else
+ {
+ _ASSERT(!m_sOpt.IsEmpty());
+ pOb->SplitMesh(pMesh, m_sOpt.nVtxNum, m_sOpt.psVtx); // Split the sub-mesh into its own mesh
+ return true;
+ }
+}
+
+/****************************************************************************
+@Function Fill
+@Input pOb Object to fill with
+@Return int -1 if the block if the best option is already full
+@Description Note: Ask Aaron
+****************************************************************************/
+int CBlock::Fill(
+ CObject * const pOb)
+{
+ SVtx *pVtx;
+ int i;
+ SMesh *pMesh;
+
+ /*
+ Build blocks from the large meshes
+ */
+ if(!pOb->m_vMeshLg.empty()) {
+ pMesh = &pOb->m_vMeshLg.back();
+
+// _RPT1(_CRT_WARN, "Fill() using large with %d vtx\n", pMesh->nVtxNum);
+
+ // Find the vertex with the fewest unused triangles
+ for(i = 0; i < pMesh->nVtxNum; ++i) {
+ pVtx = pMesh->ppVtx[i];
+
+ if(pVtx->nTriNumFree == 1) {
+ if(FillFrom(pMesh, pVtx, pOb))
+ return Fill(pOb);
+ }
+ }
+
+ if(m_sOptBest.IsEmpty()) {
+ // Just start from any old vertex
+ for(i = 0; i < pMesh->nVtxNum; ++i) {
+ pVtx = pMesh->ppVtx[i];
+
+ if(pVtx->nTriNumFree) {
+ if(FillFrom(pMesh, pVtx, pOb))
+ return Fill(pOb);
+ break;
+ }
+ }
+
+ if(m_sOptBest.IsEmpty()) {
+ pOb->m_vMeshLg.pop_back(); // Delete the mesh from the list
+ return Fill(pOb);
+ }
+ }
+
+ if(m_sOptBest.IsFull())
+ return -1;
+ }
+
+ /*
+ Match together the small meshes into blocks
+ */
+ _ASSERT(m_sOptBest.IsEmpty());
+ i = m_nVtxLimit - m_sOptBest.nVtxNum - 3;
+
+// _RPT0(_CRT_WARN, "Fill() grouping small ");
+
+ // Starting with the largest meshes, lump them into this block
+ while(i >= 0 && (m_nVtxLimit - m_sOptBest.nVtxNum) >= 3) {
+ if(pOb->m_pvMesh[i].empty()) {
+ --i;
+ continue;
+ }
+
+ pMesh = &pOb->m_pvMesh[i].back();
+ m_sOptBest.Add(pMesh);
+// _RPT1(_CRT_WARN, "+%d", pMesh->nVtxNum);
+ pOb->m_pvMesh[i].pop_back();
+ i = PVRT_MIN(i, m_nVtxLimit - m_sOptBest.nVtxNum - 3);
+ }
+
+ // If there's any space left in this block (and clearly there are no blocks
+ // just the right size to fit) then take SOME of the largest block available.
+ if(!m_sOptBest.IsFull()) {
+ m_sOpt.Copy(&m_sOptBest);
+
+ // Note: This loop purposely does not check m_pvMesh[0] - any block
+ // which is looking to grab more geometry would have already sucked
+ // up those meshes
+ for(i = (m_nVtxLimit-3); i; --i) {
+ if(!pOb->m_pvMesh[i].empty()) {
+ pMesh = &pOb->m_pvMesh[i].back();
+
+ _ASSERT(pMesh->ppVtx[0]->nTriNumFree);
+ _ASSERT(!m_sOpt.UsingVertex(pMesh->ppVtx[0]));
+
+ m_sOpt.AddVertex(pMesh->ppVtx[0]);
+// _RPT1(_CRT_WARN, "(+%d)\n", pMesh->nVtxNum);
+ AddBestTriangles(pOb);
+
+ m_sOptBest.Copy(&m_sOpt);
+ _ASSERT(m_sOptBest.IsFull());
+ return i;
+ }
+ }
+ }
+// _RPT0(_CRT_WARN, "\n");
+ return -1;
+}
+
+/****************************************************************************
+** Local functions
+****************************************************************************/
+/****************************************************************************
+@Function Fill
+@Input pVtxData Vertex data
+@Input pwIdx Index array
+@Input nStride Stride
+@Input nVertNum Number of vertices
+@Input nIdxNum Number of indices
+@Description Sorts the vertices.
+****************************************************************************/
+static void SortVertices(
+ void * const pVtxData,
+ PVRTGEOMETRY_IDX * const pwIdx,
+ const int nStride,
+ const int nVertNum,
+ const int nIdxNum)
+{
+ void *pVtxNew;
+ int *pnVtxDest;
+ int i;
+ PVRTGEOMETRY_IDX wNext;
+
+ pVtxNew = malloc(nVertNum * nStride);
+ _ASSERT(pVtxNew);
+
+ pnVtxDest = (int*)malloc(nVertNum * sizeof(*pnVtxDest));
+ _ASSERT(pnVtxDest);
+
+ wNext = 0;
+
+ // Default all indices to an invalid number
+ for(i = 0; i < nVertNum; ++i)
+ pnVtxDest[i] = -1;
+
+ // Let's get on with it then.
+ for(i = 0; i < nIdxNum; ++i) {
+ if(pnVtxDest[pwIdx[i]] == -1) {
+ _ASSERT((int) wNext < nVertNum);
+ memcpy((char*)pVtxNew+(wNext*nStride), (char*)pVtxData+(pwIdx[i]*nStride), nStride);
+ pnVtxDest[pwIdx[i]] = wNext++;
+ }
+
+ pwIdx[i] = pnVtxDest[pwIdx[i]];
+ }
+
+ /*
+ This assert will fail if sorting a sub-set of the triangles (e.g. if
+ the mesh is bone-batched).
+
+ In that situation vertex sorting should be performed only once after
+ all the tri sorting is finished, not per tri-sort.
+ */
+ _ASSERT((int) wNext == nVertNum);
+ memcpy(pVtxData, pVtxNew, nVertNum * nStride);
+
+ FREE(pnVtxDest);
+ FREE(pVtxNew);
+}
+
+/****************************************************************************
+** Functions
+****************************************************************************/
+/*!***************************************************************************
+ @Function PVRTGeometrySort
+ @Modified pVtxData Pointer to array of vertices
+ @Modified pwIdx Pointer to array of indices
+ @Input nStride Size of a vertex (in bytes)
+ @Input nVertNum Number of vertices. Length of pVtxData array
+ @Input nTriNum Number of triangles. Length of pwIdx array is 3* this
+ @Input nBufferVtxLimit Number of vertices that can be stored in a buffer
+ @Input nBufferTriLimit Number of triangles that can be stored in a buffer
+ @Input dwFlags PVRTGEOMETRY_SORT_* flags
+ @Description Triangle sorter
+*****************************************************************************/
+void PVRTGeometrySort(
+ void * const pVtxData,
+ PVRTGEOMETRY_IDX * const pwIdx,
+ const int nStride,
+ const int nVertNum,
+ const int nTriNum,
+ const int nBufferVtxLimit,
+ const int nBufferTriLimit,
+ const unsigned int dwFlags)
+{
+ CObject sOb(pwIdx, nVertNum, nTriNum, nBufferVtxLimit, nBufferTriLimit);
+ CBlock sBlock(nBufferVtxLimit, nBufferTriLimit);
+ PVRTGEOMETRY_IDX *pwIdxOut;
+ int nTriCnt, nVtxCnt;
+ int nOutTriCnt, nOutVtxCnt, nOutBlockCnt;
+ int nMeshToResize;
+#ifdef PVRTRISORT_ENABLE_VERIFY_RESULTS
+ int i;
+ int pnBlockTriCnt[PVRVGPBLOCKTEST_MAX_BLOCKS];
+ SVGPModel sVGPMdlBefore;
+ SVGPModel sVGPMdlAfter;
+#endif
+
+ if(dwFlags & PVRTGEOMETRY_SORT_VERTEXCACHE) {
+#ifdef PVRTRISORT_ENABLE_VERIFY_RESULTS
+ VGP590Test(&sVGPMdlBefore, pwIdx, nTriNum);
+ _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);
+#endif
+
+ pwIdxOut = (PVRTGEOMETRY_IDX*)malloc(nTriNum * 3 * sizeof(*pwIdxOut));
+ _ASSERT(pwIdxOut);
+
+ // Sort geometry into blocks
+ nOutTriCnt = 0;
+ nOutVtxCnt = 0;
+ nOutBlockCnt = 0;
+ do {
+ // Clear & fill the block
+ sBlock.Clear();
+ nMeshToResize = sBlock.Fill(&sOb);
+
+ // Copy indices into output
+ sBlock.Output(&pwIdxOut[3*nOutTriCnt], &nVtxCnt, &nTriCnt, &sOb);
+ sOb.m_nTriNumFree -= nTriCnt;
+ nOutTriCnt += nTriCnt;
+
+ if(nMeshToResize >= 0) {
+ SMesh *pMesh;
+ _ASSERT(nMeshToResize <= (nBufferVtxLimit-3));
+ pMesh = &sOb.m_pvMesh[nMeshToResize].back();
+ sOb.ResizeMesh(pMesh->nVtxNum, pMesh->ppVtx);
+ sOb.m_pvMesh[nMeshToResize].pop_back();
+ }
+
+ _ASSERT(nVtxCnt <= nBufferVtxLimit);
+ _ASSERT(nTriCnt <= nBufferTriLimit);
+
+#ifdef PVRTRISORT_ENABLE_VERIFY_RESULTS
+ _ASSERT(nOutBlockCnt < PVRVGPBLOCKTEST_MAX_BLOCKS);
+ pnBlockTriCnt[nOutBlockCnt] = nTriCnt;
+#endif
+ nOutVtxCnt += nVtxCnt;
+ nOutBlockCnt++;
+
+// _RPT4(_CRT_WARN, "%d/%d tris (+%d), %d blocks\n", nOutTriCnt, nTriNum, nTriCnt, nOutBlockCnt);
+
+ _ASSERT(nTriCnt == nBufferTriLimit || (nBufferVtxLimit - nVtxCnt) < 3 || nOutTriCnt == nTriNum);
+ } while(nOutTriCnt < nTriNum);
+
+ _ASSERT(nOutTriCnt == nTriNum);
+ // The following will fail if optimising a subset of the mesh (e.g. a bone batching)
+ //_ASSERT(nOutVtxCnt >= nVertNum);
+
+ // Done!
+ memcpy(pwIdx, pwIdxOut, nTriNum * 3 * sizeof(*pwIdx));
+ FREE(pwIdxOut);
+
+ _RPT3(_CRT_WARN, "OptimiseTriListPVR() In: Tri: %d, Vtx: %d, vtx/tri=%f\n", nTriNum, nVertNum, (float)nVertNum / (float)nTriNum);
+ _RPT4(_CRT_WARN, "OptimiseTriListPVR() HW: Tri: %d, Vtx: %d, vtx/tri=%f Blocks=%d\n", nOutTriCnt, nOutVtxCnt, (float)nOutVtxCnt / (float)nOutTriCnt, nOutBlockCnt);
+
+#ifdef PVRTRISORT_ENABLE_VERIFY_RESULTS
+ VGP590Test(&sVGPMdlAfter, pwIdx, nTriNum);
+ _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);
+ _ASSERTE(sVGPMdlAfter.nVtxCnt <= sVGPMdlBefore.nVtxCnt);
+ _ASSERTE(sVGPMdlAfter.nBlockCnt <= sVGPMdlBefore.nBlockCnt);
+
+ for(i = 0; i < nOutBlockCnt; ++i) {
+ _ASSERT(pnBlockTriCnt[i] == sVGPMdlAfter.pnBlockTriCnt[i]);
+ }
+#endif
+ }
+
+ if(!(dwFlags & PVRTGEOMETRY_SORT_IGNOREVERTS)) {
+ // Re-order the vertices so maybe they're accessed in a more linear
+ // manner. Should cut page-breaks on the initial memory read of
+ // vertices. Affects both the order of vertices, and the values
+ // of indices, but the triangle order is unchanged.
+ SortVertices(pVtxData, pwIdx, nStride, nVertNum, nTriNum*3);
+ }
+}
+
+/*****************************************************************************
+ End of file (PVRTGeometry.cpp)
+*****************************************************************************/
+
