third_party/PowerVR_SDK/Tools/PVRTTriStrip.cpp

/******************************************************************************

 @File         PVRTTriStrip.cpp

 @Title        PVRTTriStrip

 @Version       @Version      

 @Copyright    Copyright (c) Imagination Technologies Limited.

 @Platform     Independent

 @Description  Strips a triangle list.

******************************************************************************/

/****************************************************************************
** Includes
****************************************************************************/
#include <stdlib.h>

#include "PVRTGlobal.h"
#include "PVRTContext.h"
#include "PVRTTriStrip.h"

/****************************************************************************
** Defines
****************************************************************************/
#define RND_TRIS_ORDER

/****************************************************************************
** Structures
****************************************************************************/

/****************************************************************************
** Class: CTri
****************************************************************************/
class CTri;

/*!***************************************************************************
 @Class				CTriState
 @Description		Stores a pointer to the triangles either side of itself,
					as well as it's winding.
*****************************************************************************/
class CTriState
{
public:
	CTri	*pRev, *pFwd;
	bool	bWindFwd;

	CTriState()
	{
		bWindFwd	= true;		// Initial value irrelevent
		pRev		= NULL;
		pFwd		= NULL;
	}
};
/*!***************************************************************************
 @Class				CTri
 @Description		Object used to store information about the triangle, such as
					the vertex indices it is made from, which triangles are
					adjacent to it, etc.
*****************************************************************************/
class CTri
{
public:
	CTriState	sNew, sOld;

	CTri	*pAdj[3];
	bool	bInStrip;

	const unsigned int	*pIdx;		// three indices for the tri
	bool					bOutput;

public:
	CTri();
	int FindEdge(const unsigned int pw0, const unsigned int pw1) const;
	void Cement();
	void Undo();
	int EdgeFromAdjTri(const CTri &tri) const;	// Find the index of the adjacent tri
};

/*!***************************************************************************
 @Class				CStrip
 @Description		Object used to store the triangles that a given strip is
					composed from.
*****************************************************************************/
class CStrip
{
protected:
	unsigned int	m_nTriCnt;
	CTri			*m_pTri;
	unsigned int	m_nStrips;

	CTri			**m_psStrip;	// Working space for finding strips

public:
	CStrip(
		const unsigned int	* const pui32TriList,
		const unsigned int		nTriCnt);
	~CStrip();

protected:
	bool StripGrow(
		CTri				&triFrom,
		const unsigned int	nEdgeFrom,
		const int			nMaxChange);

public:
	void StripFromEdges();
	void StripImprove();

	void Output(
		unsigned int	**ppui32Strips,
		unsigned int	**ppnStripLen,
		unsigned int	*pnStripCnt);
};

/****************************************************************************
** Constants
****************************************************************************/

/****************************************************************************
** Code: Class: CTri
****************************************************************************/
CTri::CTri()
{
	pAdj[0]		= NULL;
	pAdj[1]		= NULL;
	pAdj[2]		= NULL;
	bInStrip	= false;
	bOutput		= false;
}

/*!***************************************************************************
 @Function			FindEdge
 @Input				pw0			The first index
 @Input				pw1			The second index
 @Return			The index of the edge
 @Description		Finds the index of the edge that the current object shares
					with the two vertex index values that have been passed in
					(or returns -1 if they dont share an edge).
*****************************************************************************/
int CTri::FindEdge(const unsigned int pw0, const unsigned int pw1) const
{
	if((pIdx[0] == pw0 && pIdx[1] == pw1))
		return 0;
	if((pIdx[1] == pw0 && pIdx[2] == pw1))
		return 1;
	if((pIdx[2] == pw0 && pIdx[0] == pw1))
		return 2;
	return -1;
}
/*!***************************************************************************
 @Function			Cement
 @Description		Assigns the new state as the old state.
*****************************************************************************/
void CTri::Cement()
{
	sOld = sNew;
}
/*!***************************************************************************
 @Function			Undo
 @Description		Reverts the new state to the old state.
*****************************************************************************/
void CTri::Undo()
{
	sNew = sOld;
}
/*!***************************************************************************
 @Function			EdgeFromAdjTri
 @Input				tri			The triangle to compare
 @Return			int			Index of adjacent triangle (-1 if not adjacent)
 @Description		If the input triangle is adjacent to the current triangle,
					it's index is returned.
*****************************************************************************/
int CTri::EdgeFromAdjTri(const CTri &tri) const
{
	for(int i = 0; i < 3; ++i)
	{
		if(pAdj[i] == &tri)
		{
			return i;
		}
	}
	_ASSERT(false);
	return -1;
}

/****************************************************************************
** Local code
****************************************************************************/
/*!***************************************************************************
 @Function			OrphanTri
 @Input				tri			The triangle test
 @Return			int			Returns 1 if change was made
 @Description		If the input triangle is not wound forward and is not the last
					triangle in the strip, the connection with the next triangle
					in the strip is removed.
*****************************************************************************/
static int OrphanTri(
	CTri		* const pTri)
{
	_ASSERT(!pTri->bInStrip);
	if(pTri->sNew.bWindFwd || !pTri->sNew.pFwd)
		return 0;

	pTri->sNew.pFwd->sNew.pRev = NULL;
	pTri->sNew.pFwd = NULL;
	return 1;
}
/*!***************************************************************************
 @Function			TakeTri
 @Input				pTri		The triangle to take
 @Input				pRevNew		The triangle that is before pTri in the new strip
 @Return			int			Returns 1 if a new strip has been created
 @Description		Removes the triangle from it's current strip
					and places it in a new one (following pRevNew in the new strip).
*****************************************************************************/
static int TakeTri(
	CTri		* const pTri,
	CTri		* const pRevNew,
	const bool	bFwd)
{
	int	nRet;

	_ASSERT(!pTri->bInStrip);

	if(pTri->sNew.pFwd && pTri->sNew.pRev)
	{
		_ASSERT(pTri->sNew.pFwd->sNew.pRev == pTri);
		pTri->sNew.pFwd->sNew.pRev = NULL;
		_ASSERT(pTri->sNew.pRev->sNew.pFwd == pTri);
		pTri->sNew.pRev->sNew.pFwd = NULL;

		// If in the middle of a Strip, this will generate a new Strip
		nRet = 1;

		// The second tri in the strip may need to be orphaned, or it will have wrong winding order
		nRet += OrphanTri(pTri->sNew.pFwd);
	}
	else if(pTri->sNew.pFwd)
	{
		_ASSERT(pTri->sNew.pFwd->sNew.pRev == pTri);
		pTri->sNew.pFwd->sNew.pRev = NULL;

		// If at the beginning of a Strip, no change
		nRet = 0;

		// The second tri in the strip may need to be orphaned, or it will have wrong winding order
		nRet += OrphanTri(pTri->sNew.pFwd);
	}
	else if(pTri->sNew.pRev)
	{
		_ASSERT(pTri->sNew.pRev->sNew.pFwd == pTri);
		pTri->sNew.pRev->sNew.pFwd = NULL;

		// If at the end of a Strip, no change
		nRet = 0;
	}
	else
	{
		// Otherwise it's a lonesome triangle; one Strip removed!
		nRet = -1;
	}

	pTri->sNew.pFwd		= NULL;
	pTri->sNew.pRev		= pRevNew;
	pTri->bInStrip		= true;
	pTri->sNew.bWindFwd	= bFwd;

	if(pRevNew)
	{
		_ASSERT(!pRevNew->sNew.pFwd);
		pRevNew->sNew.pFwd	= pTri;
	}

	return nRet;
}
/*!***************************************************************************
 @Function			TryLinkEdge
 @Input				src			The source triangle
 @Input				cmp			The triangle to compare with
 @Input				nSrcEdge	The edge of souce triangle to compare
 @Input				idx0		Vertex index 0 of the compare triangle
 @Input				idx1		Vertex index 1 of the compare triangle
 @Description		If the triangle to compare currently has no adjacent
					triangle along the specified edge, link the source triangle
					(along it's specified edge) with the compare triangle.
*****************************************************************************/
static bool TryLinkEdge(
	CTri				&src,
	CTri				&cmp,
	const int			nSrcEdge,
	const unsigned int	idx0,
	const unsigned int	idx1)
{
	int nCmpEdge;

	nCmpEdge = cmp.FindEdge(idx0, idx1);
	if(nCmpEdge != -1 && !cmp.pAdj[nCmpEdge])
	{
		cmp.pAdj[nCmpEdge] = &src;
		src.pAdj[nSrcEdge] = &cmp;
		return true;
	}
	return false;
}

/****************************************************************************
** Code: Class: CStrip
****************************************************************************/
CStrip::CStrip(
	const unsigned int	* const pui32TriList,
	const unsigned int	nTriCnt)
{
	unsigned int	i, j;
	bool			b0, b1, b2;

	m_nTriCnt = nTriCnt;

	/*
		Generate adjacency info
	*/
	m_pTri = new CTri[nTriCnt];
	for(i = 0; i < nTriCnt; ++i)
	{
		// Set pointer to indices
		m_pTri[i].pIdx = &pui32TriList[3 * i];

		b0 = false;
		b1 = false;
		b2 = false;
		for(j = 0; j < i && !(b0 & b1 & b2); ++j)
		{
			if(!b0)
				b0 = TryLinkEdge(m_pTri[i], m_pTri[j], 0, m_pTri[i].pIdx[1], m_pTri[i].pIdx[0]);

			if(!b1)
				b1 = TryLinkEdge(m_pTri[i], m_pTri[j], 1, m_pTri[i].pIdx[2], m_pTri[i].pIdx[1]);

			if(!b2)
				b2 = TryLinkEdge(m_pTri[i], m_pTri[j], 2, m_pTri[i].pIdx[0], m_pTri[i].pIdx[2]);
		}
	}

	// Initially, every triangle is a strip.
	m_nStrips = m_nTriCnt;

	// Allocate working space for the strippers
	m_psStrip = new CTri*[m_nTriCnt];
}

CStrip::~CStrip()
{
	delete [] m_pTri;
	delete [] m_psStrip;
}
/*!***************************************************************************
 @Function			StripGrow
 @Input				triFrom			The triangle to begin from
 @Input				nEdgeFrom		The edge of the triangle to begin from
 @Input				maxChange		The maximum number of changes to be made
 @Description		Takes triFrom as a starting point of triangles to add to
					the list and adds triangles sequentially by finding the next
					triangle that is adjacent to the current triangle.
					This is repeated until the maximum number of changes
					have been made.
*****************************************************************************/
bool CStrip::StripGrow(
	CTri				&triFrom,
	const unsigned int	nEdgeFrom,
	const int			nMaxChange)
{
	unsigned int	i;
	bool			bFwd;
	int				nDiff, nDiffTot, nEdge;
	CTri			*pTri, *pTriPrev, *pTmp;
	unsigned int	nStripLen;

	// Start strip from this tri
	pTri		= &triFrom;
	pTriPrev	= NULL;

	nDiffTot	= 0;
	nStripLen	= 0;

	// Start strip from this edge
	nEdge	= nEdgeFrom;
	bFwd	= true;

	// Extend the strip until we run out, or we find an improvement
	nDiff = 1;
	while(nDiff > nMaxChange)
	{
		// Add pTri to the strip
		_ASSERT(pTri);
		nDiff += TakeTri(pTri, pTriPrev, bFwd);
		_ASSERT(nStripLen < m_nTriCnt);
		m_psStrip[nStripLen++] = pTri;

		// Jump to next tri
		pTriPrev = pTri;
		pTri = pTri->pAdj[nEdge];
		if(!pTri)
			break;	// No more tris, gotta stop

		if(pTri->bInStrip)
			break;	// No more tris, gotta stop

		// Find which edge we came over
		nEdge = pTri->EdgeFromAdjTri(*pTriPrev);

		// Find the edge to leave over
		if(bFwd)
		{
			if(--nEdge < 0)
				nEdge = 2;
		}
		else
		{
			if(++nEdge > 2)
				nEdge = 0;
		}

		// Swap the winding order for the next tri
		bFwd = !bFwd;
	}
	_ASSERT(!pTriPrev->sNew.pFwd);

	/*
		Accept or reject this strip.

		Accepting changes which don't change the number of strips
		adds variety, which can help better strips to develop.
	*/
	if(nDiff <= nMaxChange)
	{
		nDiffTot += nDiff;

		// Great, take the Strip
		for(i = 0; i < nStripLen; ++i)
		{
			pTri = m_psStrip[i];
			_ASSERT(pTri->bInStrip);

			// Cement affected tris
			pTmp = pTri->sOld.pFwd;
			if(pTmp && !pTmp->bInStrip)
			{
				if(pTmp->sOld.pFwd && !pTmp->sOld.pFwd->bInStrip)
					pTmp->sOld.pFwd->Cement();
				pTmp->Cement();
			}

			pTmp = pTri->sOld.pRev;
			if(pTmp && !pTmp->bInStrip)
			{
				pTmp->Cement();
			}

			// Cement this tris
			pTri->bInStrip = false;
			pTri->Cement();
		}
	}
	else
	{
		// Shame, undo the strip
		for(i = 0; i < nStripLen; ++i)
		{
			pTri = m_psStrip[i];
			_ASSERT(pTri->bInStrip);

			// Undo affected tris
			pTmp = pTri->sOld.pFwd;
			if(pTmp && !pTmp->bInStrip)
			{
				if(pTmp->sOld.pFwd && !pTmp->sOld.pFwd->bInStrip)
					pTmp->sOld.pFwd->Undo();
				pTmp->Undo();
			}

			pTmp = pTri->sOld.pRev;
			if(pTmp && !pTmp->bInStrip)
			{
				pTmp->Undo();
			}

			// Undo this tris
			pTri->bInStrip = false;
			pTri->Undo();
		}
	}

#ifdef _DEBUG
	for(int nDbg = 0; nDbg < (int)m_nTriCnt; ++nDbg)
	{
		_ASSERT(m_pTri[nDbg].bInStrip == false);
		_ASSERT(m_pTri[nDbg].bOutput == false);
		_ASSERT(m_pTri[nDbg].sOld.pRev == m_pTri[nDbg].sNew.pRev);
		_ASSERT(m_pTri[nDbg].sOld.pFwd == m_pTri[nDbg].sNew.pFwd);

		if(m_pTri[nDbg].sNew.pRev)
		{
			_ASSERT(m_pTri[nDbg].sNew.pRev->sNew.pFwd == &m_pTri[nDbg]);
		}

		if(m_pTri[nDbg].sNew.pFwd)
		{
			_ASSERT(m_pTri[nDbg].sNew.pFwd->sNew.pRev == &m_pTri[nDbg]);
		}
	}
#endif

	if(nDiffTot)
	{
		m_nStrips += nDiffTot;
		return true;
	}
	return false;
}

/*!***************************************************************************
 @Function			StripFromEdges
 @Description		Creates a strip from the object's edge information.
*****************************************************************************/
void CStrip::StripFromEdges()
{
	unsigned int	i, j, nTest;
	CTri			*pTri, *pTriPrev;
	int				nEdge = 0;

	/*
		Attempt to create grid-oriented strips.
	*/
	for(i = 0; i < m_nTriCnt; ++i)
	{
		pTri = &m_pTri[i];

		// Count the number of empty edges
		nTest = 0;
		for(j = 0; j < 3; ++j)
		{
			if(!pTri->pAdj[j])
			{
				++nTest;
			}
			else
			{
				nEdge = j;
			}
		}

		if(nTest != 2)
			continue;

		for(;;)
		{
			// A tri with two empty edges is a corner (there are other corners too, but this works so...)
			while(StripGrow(*pTri, nEdge, -1)) {};

			pTriPrev = pTri;
			pTri = pTri->pAdj[nEdge];
			if(!pTri)
				break;

			// Find the edge we came over
			nEdge = pTri->EdgeFromAdjTri(*pTriPrev);

			// Step around to the next edge
			if(++nEdge > 2)
				nEdge = 0;

			pTriPrev = pTri;
			pTri = pTri->pAdj[nEdge];
			if(!pTri)
				break;

			// Find the edge we came over
			nEdge = pTri->EdgeFromAdjTri(*pTriPrev);

			// Step around to the next edge
			if(--nEdge < 0)
				nEdge = 2;

#if 0
			// If we're not tracking the edge, give up
			nTest = nEdge - 1;
			if(nTest < 0)
				nTest = 2;
			if(pTri->pAdj[nTest])
				break;
			else
				continue;
#endif
		}
	}
}

#ifdef RND_TRIS_ORDER
struct pair
{
	unsigned int i, o;
};

static int compare(const void *arg1, const void *arg2)
{
	return ((pair*)arg1)->i - ((pair*)arg2)->i;
}
#endif
/*!***************************************************************************
 @Function			StripImprove
 @Description		Optimises the strip
*****************************************************************************/
void CStrip::StripImprove()
{
	unsigned int	i, j;
	bool			bChanged;
	int				nRepCnt, nChecks;
	int				nMaxChange;
#ifdef RND_TRIS_ORDER
	pair			*pnOrder;

	/*
		Create a random order to process the tris
	*/
	pnOrder = new pair[m_nTriCnt];
#endif

	nRepCnt = 0;
	nChecks = 2;
	nMaxChange	= 0;

	/*
		Reduce strip count by growing each of the three strips each tri can start.
	*/
	while(nChecks)
	{
		--nChecks;

		bChanged = false;

#ifdef RND_TRIS_ORDER
		/*
			Create a random order to process the tris
		*/
		for(i = 0; i < m_nTriCnt; ++i)
		{
			pnOrder[i].i = rand() * rand();
			pnOrder[i].o = i;
		}
		qsort(pnOrder, m_nTriCnt, sizeof(*pnOrder), compare);
#endif

		/*
			Process the tris
		*/
		for(i = 0; i < m_nTriCnt; ++i)
		{
			for(j = 0; j < 3; ++j)
			{
#ifdef RND_TRIS_ORDER
				bChanged |= StripGrow(m_pTri[pnOrder[i].o], j, nMaxChange);
#else
				bChanged |= StripGrow(m_pTri[i], j, nMaxChange);
#endif
			}
		}
		++nRepCnt;

		// Check the results once or twice
		if(bChanged)
			nChecks = 2;

		nMaxChange = (nMaxChange == 0 ? -1 : 0);
	}

#ifdef RND_TRIS_ORDER
	delete [] pnOrder;
#endif
	_RPT1(_CRT_WARN, "Reps: %d\n", nRepCnt);
}
/*!***************************************************************************
 @Function			Output
 @Output			ppui32Strips
 @Output			ppnStripLen			The length of the strip
 @Output			pnStripCnt
 @Description		Outputs key information about the strip to the output
					parameters.
*****************************************************************************/
void CStrip::Output(
	unsigned int	**ppui32Strips,
	unsigned int	**ppnStripLen,
	unsigned int	*pnStripCnt)
{
	unsigned int	*pui32Strips;
	unsigned int	*pnStripLen;
	unsigned int	i, j, nIdx, nStrip;
	CTri			*pTri;

	/*
		Output Strips
	*/
	pnStripLen = (unsigned int*)malloc(m_nStrips * sizeof(*pnStripLen));
	pui32Strips = (unsigned int*)malloc((m_nTriCnt + m_nStrips * 2) * sizeof(*pui32Strips));
	nStrip = 0;
	nIdx = 0;
	for(i = 0; i < m_nTriCnt; ++i)
	{
		pTri = &m_pTri[i];

		if(pTri->sNew.pRev)
			continue;
		_ASSERT(!pTri->sNew.pFwd || pTri->sNew.bWindFwd);
		_ASSERT(pTri->bOutput == false);

		if(!pTri->sNew.pFwd)
		{
			pui32Strips[nIdx++] = pTri->pIdx[0];
			pui32Strips[nIdx++] = pTri->pIdx[1];
			pui32Strips[nIdx++] = pTri->pIdx[2];
			pnStripLen[nStrip] = 1;
			pTri->bOutput = true;
		}
		else
		{
			if(pTri->sNew.pFwd == pTri->pAdj[0])
			{
				pui32Strips[nIdx++] = pTri->pIdx[2];
				pui32Strips[nIdx++] = pTri->pIdx[0];
			}
			else if(pTri->sNew.pFwd == pTri->pAdj[1])
			{
				pui32Strips[nIdx++] = pTri->pIdx[0];
				pui32Strips[nIdx++] = pTri->pIdx[1];
			}
			else
			{
				_ASSERT(pTri->sNew.pFwd == pTri->pAdj[2]);
				pui32Strips[nIdx++] = pTri->pIdx[1];
				pui32Strips[nIdx++] = pTri->pIdx[2];
			}

			pnStripLen[nStrip] = 0;
			do
			{
				_ASSERT(pTri->bOutput == false);

				// Increment tris-in-this-strip counter
				++pnStripLen[nStrip];

				// Output the new vertex index
				for(j = 0; j < 3; ++j)
				{
					if(
						(pui32Strips[nIdx-2] != pTri->pIdx[j]) &&
						(pui32Strips[nIdx-1] != pTri->pIdx[j]))
					{
						break;
					}
				}
				_ASSERT(j != 3);
				pui32Strips[nIdx++] = pTri->pIdx[j];

				// Double-check that the previous three indices are the indices of this tris (in some order)
				_ASSERT(
					((pui32Strips[nIdx-3] == pTri->pIdx[0]) && (pui32Strips[nIdx-2] == pTri->pIdx[1]) && (pui32Strips[nIdx-1] == pTri->pIdx[2])) ||
					((pui32Strips[nIdx-3] == pTri->pIdx[1]) && (pui32Strips[nIdx-2] == pTri->pIdx[2]) && (pui32Strips[nIdx-1] == pTri->pIdx[0])) ||
					((pui32Strips[nIdx-3] == pTri->pIdx[2]) && (pui32Strips[nIdx-2] == pTri->pIdx[0]) && (pui32Strips[nIdx-1] == pTri->pIdx[1])) ||
					((pui32Strips[nIdx-3] == pTri->pIdx[2]) && (pui32Strips[nIdx-2] == pTri->pIdx[1]) && (pui32Strips[nIdx-1] == pTri->pIdx[0])) ||
					((pui32Strips[nIdx-3] == pTri->pIdx[1]) && (pui32Strips[nIdx-2] == pTri->pIdx[0]) && (pui32Strips[nIdx-1] == pTri->pIdx[2])) ||
					((pui32Strips[nIdx-3] == pTri->pIdx[0]) && (pui32Strips[nIdx-2] == pTri->pIdx[2]) && (pui32Strips[nIdx-1] == pTri->pIdx[1])));

				// Check that the latest three indices are not degenerate
				_ASSERT(pui32Strips[nIdx-1] != pui32Strips[nIdx-2]);
				_ASSERT(pui32Strips[nIdx-1] != pui32Strips[nIdx-3]);
				_ASSERT(pui32Strips[nIdx-2] != pui32Strips[nIdx-3]);

				pTri->bOutput = true;

				// Check that the next triangle is adjacent to this triangle
				_ASSERT(
					(pTri->sNew.pFwd == pTri->pAdj[0]) ||
					(pTri->sNew.pFwd == pTri->pAdj[1]) ||
					(pTri->sNew.pFwd == pTri->pAdj[2]) ||
					(!pTri->sNew.pFwd));
				// Check that this triangle is adjacent to the next triangle
				_ASSERT(
					(!pTri->sNew.pFwd) ||
					(pTri == pTri->sNew.pFwd->pAdj[0]) ||
					(pTri == pTri->sNew.pFwd->pAdj[1]) ||
					(pTri == pTri->sNew.pFwd->pAdj[2]));

				pTri = pTri->sNew.pFwd;
			} while(pTri);
		}

		++nStrip;
	}
	_ASSERT(nIdx == m_nTriCnt + m_nStrips * 2);
	_ASSERT(nStrip == m_nStrips);

	// Check all triangles have been output
	for(i = 0; i < m_nTriCnt; ++i)
	{
		_ASSERT(m_pTri[i].bOutput == true);
	}

	// Check all triangles are present
	j = 0;
	for(i = 0; i < m_nStrips; ++i)
	{
		j += pnStripLen[i];
	}
	_ASSERT(j == m_nTriCnt);

	// Output data
	*pnStripCnt		= m_nStrips;
	*ppui32Strips		= pui32Strips;
	*ppnStripLen	= pnStripLen;
}

/****************************************************************************
** Code
****************************************************************************/

/*!***************************************************************************
 @Function			PVRTTriStrip
 @Output			ppui32Strips
 @Output			ppnStripLen
 @Output			pnStripCnt
 @Input				pui32TriList
 @Input				nTriCnt
 @Description		Reads a triangle list and generates an optimised triangle strip.
*****************************************************************************/
void PVRTTriStrip(
	unsigned int			**ppui32Strips,
	unsigned int			**ppnStripLen,
	unsigned int			*pnStripCnt,
	const unsigned int	* const pui32TriList,
	const unsigned int		nTriCnt)
{
	unsigned int	*pui32Strips;
	unsigned int	*pnStripLen;
	unsigned int	nStripCnt;

	/*
		If the order in which triangles are tested as strip roots is
		randomised, then several attempts can be made. Use the best result.
	*/
	for(int i = 0; i <
#ifdef RND_TRIS_ORDER
		5
#else
		1
#endif
		; ++i)
	{
		CStrip stripper(pui32TriList, nTriCnt);

#ifdef RND_TRIS_ORDER
		srand(i);
#endif

		stripper.StripFromEdges();
		stripper.StripImprove();
		stripper.Output(&pui32Strips, &pnStripLen, &nStripCnt);

		if(!i || nStripCnt < *pnStripCnt)
		{
			if(i)
			{
				FREE(*ppui32Strips);
				FREE(*ppnStripLen);
			}

			*ppui32Strips		= pui32Strips;
			*ppnStripLen	= pnStripLen;
			*pnStripCnt		= nStripCnt;
		}
		else
		{
			FREE(pui32Strips);
			FREE(pnStripLen);
		}
	}
}

/*!***************************************************************************
 @Function			PVRTTriStripList
 @Modified			pui32TriList
 @Input				nTriCnt
 @Description		Reads a triangle list and generates an optimised triangle strip.
 					Result is converted back to a triangle list.
*****************************************************************************/
void PVRTTriStripList(unsigned int * const pui32TriList, const unsigned int nTriCnt)
{
	unsigned int	*pui32Strips;
	unsigned int	*pnStripLength;
	unsigned int	nNumStrips;
	unsigned int	*pui32TriPtr, *pui32StripPtr;

	/*
		Strip the geometry
	*/
	PVRTTriStrip(&pui32Strips, &pnStripLength, &nNumStrips, pui32TriList, nTriCnt);

	/*
		Convert back to a triangle list
	*/
	pui32StripPtr	= pui32Strips;
	pui32TriPtr	= pui32TriList;
	for(unsigned int i = 0; i < nNumStrips; ++i)
	{
		*pui32TriPtr++ = *pui32StripPtr++;
		*pui32TriPtr++ = *pui32StripPtr++;
		*pui32TriPtr++ = *pui32StripPtr++;

		for(unsigned int j = 1; j < pnStripLength[i]; ++j)
		{
			// Use two indices from previous triangle, flipping tri order alternately.
			if(j & 0x01)
			{
				*pui32TriPtr++ = pui32StripPtr[-1];
				*pui32TriPtr++ = pui32StripPtr[-2];
			}
			else
			{
				*pui32TriPtr++ = pui32StripPtr[-2];
				*pui32TriPtr++ = pui32StripPtr[-1];
			}

			*pui32TriPtr++ = *pui32StripPtr++;
		}
	}

	free(pui32Strips);
	free(pnStripLength);
}

/*****************************************************************************
 End of file (PVRTTriStrip.cpp)
*****************************************************************************/