1522 lines
48 KiB
C++
1522 lines
48 KiB
C++
//--------------------------------------------------------------------------------------
|
|
// AtgStrip.cpp
|
|
//
|
|
// Tristrip routines (which convert a mesh into a list of optimized
|
|
// triangle strips).
|
|
//
|
|
// Xbox Advanced Technology Group.
|
|
// Copyright (C) Microsoft Corporation. All rights reserved.
|
|
//--------------------------------------------------------------------------------------
|
|
#include "stdafx.h"
|
|
#include "AtgStrip.h"
|
|
|
|
|
|
// Cache size to optimize for.
|
|
const int CACHE_SIZE = 16;
|
|
|
|
|
|
// Estimated length of the vertex shader to use when comparing the cost of
|
|
// different stripifications.
|
|
const int SHADER_CYCLES = 20;
|
|
|
|
|
|
//--------------------------------------------------------------------------------------
|
|
// Structs
|
|
//--------------------------------------------------------------------------------------
|
|
typedef WORD (*TRIANGLELIST)[3];
|
|
|
|
|
|
struct TRIANGLEINFO
|
|
{
|
|
INT neighbortri[3]; // Triangle sharing edge (i,i+1), or -1
|
|
INT neighboredge[3]; // Edge (j,j+1) of neighboring triangle.
|
|
};
|
|
|
|
|
|
//--------------------------------------------------------------------------------------
|
|
// Name: struct CStrip
|
|
// Desc: A single triangle strip. After a mesh is stripified, it typically is
|
|
// composed of several of these.
|
|
//--------------------------------------------------------------------------------------
|
|
struct CStrip
|
|
{
|
|
BOOL m_bIsStripCW;
|
|
|
|
DWORD m_dwNumTriangles;
|
|
INT* m_pTriangles;
|
|
|
|
DWORD m_dwNumIndices;
|
|
WORD* m_pIndices;
|
|
|
|
DWORD m_dwNumNeighbors;
|
|
|
|
CStrip( DWORD dwNumTris, DWORD dwNumIndices )
|
|
{
|
|
m_dwNumTriangles = dwNumTris;
|
|
m_pTriangles = new int[ dwNumTris ];
|
|
|
|
m_dwNumIndices = dwNumIndices;
|
|
m_pIndices = new WORD[ dwNumIndices ];
|
|
}
|
|
|
|
~CStrip()
|
|
{
|
|
delete[] m_pTriangles;
|
|
delete[] m_pIndices;
|
|
}
|
|
};
|
|
|
|
|
|
//--------------------------------------------------------------------------------------
|
|
// Name: struct CSubStrip
|
|
// Desc: A structure that specifies part of a strip in a striplist.
|
|
//--------------------------------------------------------------------------------------
|
|
struct CSubStrip
|
|
{
|
|
INT m_iStrip; // Index into striplist.
|
|
INT m_iStart; // Starting triangle index
|
|
INT m_iEnd; // Ending triangle index.
|
|
};
|
|
|
|
|
|
//--------------------------------------------------------------------------------------
|
|
// Name: struct CStripList
|
|
// Desc: A list of triangle strips.
|
|
//--------------------------------------------------------------------------------------
|
|
struct CStripList
|
|
{
|
|
CStrip** m_pStrips;
|
|
DWORD m_dwNumStrips;
|
|
|
|
CStrip** begin()
|
|
{
|
|
return (m_dwNumStrips) ? &m_pStrips[0] : NULL;
|
|
}
|
|
|
|
VOID RemoveStripFromList( CStrip** pStrip )
|
|
{
|
|
for( DWORD i=0; i<m_dwNumStrips; i++ )
|
|
{
|
|
if( &m_pStrips[i] == pStrip )
|
|
{
|
|
delete m_pStrips[i];
|
|
m_dwNumStrips--;
|
|
|
|
while( i < m_dwNumStrips )
|
|
{
|
|
m_pStrips[i] = m_pStrips[i+1];
|
|
i++;
|
|
}
|
|
break;
|
|
}
|
|
}
|
|
}
|
|
|
|
VOID RemoveFirst()
|
|
{
|
|
RemoveStripFromList( &m_pStrips[0] );
|
|
}
|
|
|
|
VOID AddStripToList( CStrip* pStrip )
|
|
{
|
|
m_pStrips[m_dwNumStrips++] = pStrip;
|
|
}
|
|
|
|
CStripList(DWORD dwMaxSize)
|
|
{
|
|
m_pStrips = new CStrip*[dwMaxSize];
|
|
m_dwNumStrips = 0L;
|
|
}
|
|
|
|
~CStripList()
|
|
{
|
|
for( DWORD i=0; i<m_dwNumStrips; i++ )
|
|
{
|
|
delete m_pStrips[i];
|
|
}
|
|
|
|
delete[] m_pStrips;
|
|
}
|
|
};
|
|
|
|
|
|
//--------------------------------------------------------------------------------------
|
|
// Name: struct SortEntry
|
|
// Desc: Class used to vertices for locality of access.
|
|
//--------------------------------------------------------------------------------------
|
|
struct SortEntry
|
|
{
|
|
INT iFirstUsed;
|
|
INT iOrigIndex;
|
|
|
|
// Define the < operator, which is needed for the STL sort() routine.
|
|
BOOL operator<( const SortEntry& rhs ) { return iFirstUsed < rhs.iFirstUsed; }
|
|
};
|
|
|
|
|
|
//--------------------------------------------------------------------------------------
|
|
// Name: class CVertCache
|
|
// Desc: Vertex cache class
|
|
//--------------------------------------------------------------------------------------
|
|
class CVertCache
|
|
{
|
|
public:
|
|
CVertCache() { Reset(); }
|
|
~CVertCache() {};
|
|
|
|
// Reset cache
|
|
void Reset()
|
|
{
|
|
m_iCachePtr = 0;
|
|
m_cachehits = 0;
|
|
memset( m_rgCache, 0xff, sizeof(m_rgCache) );
|
|
}
|
|
|
|
// Add vertindex to cache
|
|
int Add(int strip, int vertindex);
|
|
|
|
// Check if a vert is in the cache.
|
|
BOOL IsCached(int vertindex)
|
|
{
|
|
for( int iCache = 0; iCache < CACHE_SIZE; iCache++ )
|
|
{
|
|
if( vertindex == m_rgCache[iCache] )
|
|
{
|
|
// Item is in the cache
|
|
return TRUE;
|
|
}
|
|
}
|
|
|
|
return FALSE;
|
|
}
|
|
|
|
// Check if a vert uses one of the last two cached verts.
|
|
BOOL IsOld(int vertindex)
|
|
{
|
|
if( vertindex == m_rgCache[m_iCachePtr] )
|
|
{
|
|
// Item is in the cache
|
|
return TRUE;
|
|
}
|
|
|
|
return FALSE;
|
|
}
|
|
|
|
int NumCacheHits() const
|
|
{
|
|
return m_cachehits;
|
|
}
|
|
|
|
private:
|
|
int m_cachehits; // current # of cache hits
|
|
WORD m_rgCache[CACHE_SIZE]; // vertex cache
|
|
int m_rgCacheStrip[CACHE_SIZE]; // strip # which added or re-used vert
|
|
int m_iCachePtr; // FIFO ptr
|
|
bool m_bReUsed[CACHE_SIZE]; // true if vert was re-used.
|
|
};
|
|
|
|
|
|
//--------------------------------------------------------------------------------------
|
|
// Name: class CStripper
|
|
// Desc: Main stripper class
|
|
//--------------------------------------------------------------------------------------
|
|
class CStripper
|
|
{
|
|
public:
|
|
int m_dwNumTris; // Number of tris
|
|
TRIANGLELIST m_pTriangles; // Trilist
|
|
|
|
TRIANGLEINFO* m_pTriInfo; // Tri edge, neighbor info
|
|
int* m_pUsed; // Tri used flag
|
|
|
|
// Ctors/dtors
|
|
CStripper( int dwNumtris, TRIANGLELIST pTriangles );
|
|
~CStripper();
|
|
|
|
// Initialize tri info
|
|
VOID InitTriangleInfo( int tri, int vert );
|
|
|
|
// Get maximum length strip from tri/vert
|
|
int CreateStrip( int tri, int vert, int maxlen, int *pswaps,
|
|
BOOL bLookAhead, BOOL bNonSequential, BOOL bStartCW,
|
|
int* pTris );
|
|
|
|
// Turn a list of triangles into indices.
|
|
int CreateIndices( BOOL bStartCW, int iNumTriangles, int* pTriangles,
|
|
WORD* pStripVerts );
|
|
|
|
// Stripify entire mesh
|
|
VOID BuildStrips( CStripList* pStripList, int maxlen, BOOL bLookAhead,
|
|
BOOL bNonSequential, BOOL bSwapOrientation );
|
|
|
|
// Blast strip indices to ppstripindices
|
|
int CreateManyStrips( CStripList *pstriplist, WORD **ppstripindices );
|
|
int CreateLongStrip( CStripList *pstriplist, WORD **ppstripindices );
|
|
int CreateCachedStrip( CStripList *pstriplist, WORD **ppstripindices );
|
|
|
|
// Find the best cached strip.
|
|
CStrip** FindBestCachedStrip( CStripList* pStripList, const CVertCache &VertexCache );
|
|
|
|
int GetNeighborCount( int tri )
|
|
{
|
|
int count = 0;
|
|
for( int vert = 0; vert < 3; vert++ )
|
|
{
|
|
int neighbortri = m_pTriInfo[tri].neighbortri[vert];
|
|
count += (neighbortri != -1) && !m_pUsed[neighbortri];
|
|
}
|
|
return count;
|
|
}
|
|
};
|
|
|
|
|
|
//--------------------------------------------------------------------------------------
|
|
// Name: CreateStrip()
|
|
// Desc: Get maximum length of strip starting at tri/vert
|
|
//--------------------------------------------------------------------------------------
|
|
int CStripper::CreateStrip( int tri, int vert, int maxlen, int *pswaps,
|
|
BOOL bLookAhead, BOOL bNonSequential,
|
|
BOOL bStartCW, int* pTris )
|
|
{
|
|
*pswaps = 0;
|
|
|
|
// this guy has already been used?
|
|
if(m_pUsed[tri])
|
|
return 0;
|
|
|
|
// mark tri as used
|
|
m_pUsed[tri] = 1;
|
|
|
|
int swaps = 0;
|
|
|
|
// add first tri
|
|
int iNumTris = 0;
|
|
pTris[iNumTris++] = tri;
|
|
|
|
// toggle orientation
|
|
bStartCW = !bStartCW;
|
|
|
|
// get next tri information
|
|
int edge = (bStartCW ? vert + 2 : vert + 1) % 3;
|
|
int nexttri = m_pTriInfo[tri].neighbortri[edge];
|
|
int nextvert = m_pTriInfo[tri].neighboredge[edge];
|
|
|
|
// start building the strip until we run out of room or indices
|
|
for(int stripcount = 3; stripcount < maxlen; stripcount++)
|
|
{
|
|
// dead end?
|
|
if(nexttri == -1 || m_pUsed[nexttri])
|
|
break;
|
|
|
|
// move to next tri
|
|
tri = nexttri;
|
|
vert = nextvert;
|
|
|
|
// toggle orientation
|
|
bStartCW = !bStartCW;
|
|
|
|
// find the next natural edge
|
|
edge = (bStartCW ? vert + 2 : vert + 1) % 3;
|
|
nexttri = m_pTriInfo[tri].neighbortri[edge];
|
|
nextvert = m_pTriInfo[tri].neighboredge[edge];
|
|
|
|
BOOL bSwap = FALSE;
|
|
if(nexttri == -1 || m_pUsed[nexttri])
|
|
{
|
|
// if the next tri is a dead end - try swapping orientation
|
|
bSwap = TRUE;
|
|
}
|
|
else if( bLookAhead )
|
|
{
|
|
// try a swap and see who our new neighbor would be
|
|
int edgeswap = (bStartCW ? vert + 1 : vert + 2) % 3;
|
|
int nexttriswap = m_pTriInfo[tri].neighbortri[edgeswap];
|
|
int nextvertswap = m_pTriInfo[tri].neighboredge[edgeswap];
|
|
|
|
if( nexttriswap != -1 && !m_pUsed[nexttriswap] )
|
|
{
|
|
// if the swap neighbor has a lower count, change directions
|
|
if( GetNeighborCount(nexttriswap) < GetNeighborCount(nexttri) )
|
|
{
|
|
bSwap = TRUE;
|
|
}
|
|
else if( GetNeighborCount(nexttriswap) == GetNeighborCount(nexttri) )
|
|
{
|
|
// if they have the same number of neighbors - check their neighbors
|
|
edgeswap = (bStartCW ? nextvertswap + 2 : nextvertswap + 1) % 3;
|
|
nexttriswap = m_pTriInfo[nexttriswap].neighbortri[edgeswap];
|
|
|
|
int edge1 = (bStartCW ? nextvert + 1 : nextvert + 2) % 3;
|
|
int nexttri1 = m_pTriInfo[nexttri].neighbortri[edge1];
|
|
|
|
if( nexttri1 == -1 || m_pUsed[nexttri1] )
|
|
{
|
|
// natural winding order leads us to a dead end so turn
|
|
bSwap = TRUE;
|
|
}
|
|
else if( nexttriswap != -1 && !m_pUsed[nexttriswap] )
|
|
{
|
|
// check neighbor counts on both directions and swap if it's better
|
|
if( GetNeighborCount(nexttriswap) < GetNeighborCount(nexttri1) )
|
|
bSwap = TRUE;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
if( bSwap && bNonSequential )
|
|
{
|
|
// we've been told to change directions so make sure we actually can
|
|
// and then add the swap vertex
|
|
int edgeswap = (bStartCW ? vert + 1 : vert + 2) % 3;
|
|
nexttri = m_pTriInfo[tri].neighbortri[edgeswap];
|
|
nextvert = m_pTriInfo[tri].neighboredge[edgeswap];
|
|
|
|
if( nexttri != -1 && !m_pUsed[nexttri] )
|
|
{
|
|
stripcount++;
|
|
swaps++;
|
|
bStartCW = !bStartCW;
|
|
}
|
|
}
|
|
|
|
pTris[iNumTris++] = tri;
|
|
|
|
// mark triangle as used
|
|
m_pUsed[tri] = 1;
|
|
}
|
|
|
|
// clear the used flags
|
|
for( int j = 0; j < iNumTris; j++ )
|
|
m_pUsed[pTris[j]] = 0;
|
|
|
|
// return swap count and striplen
|
|
*pswaps = swaps;
|
|
|
|
return iNumTris;
|
|
}
|
|
|
|
|
|
//--------------------------------------------------------------------------------------
|
|
// Name: CreateIndices()
|
|
// Desc: Make strip indices from triangle list.
|
|
//--------------------------------------------------------------------------------------
|
|
int CStripper::CreateIndices( BOOL bStartCW, int iNumTriangles, int* pTriangles, WORD* pStripVerts )
|
|
{
|
|
int stripcount = 0;
|
|
BOOL bCW = bStartCW;
|
|
int in_edge = -1;
|
|
|
|
for( int i = 0; i < iNumTriangles; i++ )
|
|
{
|
|
int out_edge;
|
|
|
|
int tri = pTriangles[i];
|
|
|
|
// get next tri information
|
|
if( i < iNumTriangles-1 )
|
|
{
|
|
int nexttri = pTriangles[i+1];
|
|
|
|
for( out_edge = 0; out_edge < 3; out_edge++ )
|
|
if( m_pTriInfo[tri].neighbortri[out_edge] == nexttri )
|
|
break;
|
|
}
|
|
else
|
|
{
|
|
out_edge = (bCW ? (in_edge + 1) : (in_edge + 2)) % 3;
|
|
}
|
|
|
|
if( i == 0 )
|
|
{
|
|
if( bCW )
|
|
{
|
|
pStripVerts[0] = m_pTriangles[tri][(out_edge + 2) % 3];
|
|
pStripVerts[1] = m_pTriangles[tri][(out_edge + 0) % 3];
|
|
pStripVerts[2] = m_pTriangles[tri][(out_edge + 1) % 3];
|
|
}
|
|
else
|
|
{
|
|
pStripVerts[0] = m_pTriangles[tri][(out_edge + 2) % 3];
|
|
pStripVerts[1] = m_pTriangles[tri][(out_edge + 1) % 3];
|
|
pStripVerts[2] = m_pTriangles[tri][(out_edge + 0) % 3];
|
|
}
|
|
|
|
stripcount = 3;
|
|
}
|
|
else
|
|
{
|
|
if( out_edge == (bCW ? (in_edge + 1) : (in_edge + 2)) % 3 )
|
|
{
|
|
// In order.
|
|
pStripVerts[stripcount++] = m_pTriangles[tri][(in_edge + 2) % 3];
|
|
}
|
|
else
|
|
{
|
|
// Swap.
|
|
if( bCW )
|
|
{
|
|
pStripVerts[stripcount++] = m_pTriangles[tri][(in_edge + 0) % 3];
|
|
pStripVerts[stripcount++] = m_pTriangles[tri][(in_edge + 2) % 3];
|
|
}
|
|
else
|
|
{
|
|
pStripVerts[stripcount++] = m_pTriangles[tri][(in_edge + 1) % 3];
|
|
pStripVerts[stripcount++] = m_pTriangles[tri][(in_edge + 2) % 3];
|
|
}
|
|
|
|
bCW = !bCW;
|
|
}
|
|
}
|
|
|
|
in_edge = m_pTriInfo[tri].neighboredge[out_edge];
|
|
bCW = !bCW;
|
|
}
|
|
|
|
return stripcount;
|
|
}
|
|
|
|
|
|
//--------------------------------------------------------------------------------------
|
|
// Name: FindBestStrip()
|
|
// Desc: Given a striplist and current cache state, pick the best next strip
|
|
//--------------------------------------------------------------------------------------
|
|
CStrip** FindBestStrip( CStripList* pStripList, const CVertCache &VertexCache )
|
|
{
|
|
if( 0 == pStripList->m_dwNumStrips )
|
|
return NULL;
|
|
|
|
CStrip** ppBestStrip = pStripList->begin();
|
|
DWORD dwBestStripLen = (*ppBestStrip)->m_dwNumIndices;
|
|
BOOL bStartCW = (*ppBestStrip)->m_bIsStripCW;
|
|
BOOL bBestStripFlipped = FALSE;
|
|
int MaxCacheHits = -1;
|
|
|
|
// Go through all the other strips looking for the best caching
|
|
for( DWORD i = 0; i < pStripList->m_dwNumStrips; i++ )
|
|
{
|
|
CStrip* pStrip = pStripList->m_pStrips[i];
|
|
DWORD dwStripLen = pStrip->m_dwNumIndices;
|
|
BOOL bStripFlipped = FALSE;
|
|
|
|
// Check cache if this strip is the same type as us (ie: cw/odd)
|
|
if( ( pStrip->m_bIsStripCW == bStartCW) && ( (dwBestStripLen & 0x1) == (dwStripLen & 0x1) ) )
|
|
{
|
|
// Copy current state of cache
|
|
CVertCache NewVertexCache = VertexCache;
|
|
|
|
// Figure out what this guy would do to our cache
|
|
for( DWORD ivert = 0; ivert < dwStripLen; ivert++ )
|
|
NewVertexCache.Add( 2, pStrip->m_pIndices[ivert] );
|
|
|
|
// For even length strips - see if we can get better cache hits
|
|
// if we reverse the vertex cache contents
|
|
if( !(dwStripLen & 0x1) )
|
|
{
|
|
// Create a copy of the vertex cache, with all vertices flipped
|
|
CVertCache FlippedVertexCache = VertexCache;
|
|
for( int ivert = pStrip->m_dwNumIndices-1; ivert >= 0; ivert-- )
|
|
FlippedVertexCache.Add( 2, pStrip->m_pIndices[ivert] );
|
|
|
|
// Accept the flipped cache if it gives us more cahce hits
|
|
if( FlippedVertexCache.NumCacheHits() > NewVertexCache.NumCacheHits() )
|
|
{
|
|
NewVertexCache = FlippedVertexCache;
|
|
bStripFlipped = TRUE;
|
|
}
|
|
}
|
|
|
|
// Record the best number of cache hits to date
|
|
int NumCacheHits = NewVertexCache.NumCacheHits() - VertexCache.NumCacheHits();
|
|
|
|
if( NumCacheHits > MaxCacheHits )
|
|
{
|
|
MaxCacheHits = NumCacheHits;
|
|
ppBestStrip = &pStripList->m_pStrips[i];
|
|
dwBestStripLen = dwStripLen;//? added by mikey
|
|
bBestStripFlipped = bStripFlipped;
|
|
}
|
|
}
|
|
}
|
|
|
|
if( bBestStripFlipped )
|
|
{
|
|
CStrip* pStrip = *ppBestStrip;
|
|
int first = 0;
|
|
int last = pStrip->m_dwNumIndices - 1;
|
|
|
|
while( first < last )
|
|
{
|
|
// Swap vertex indices
|
|
WORD temp = pStrip->m_pIndices[first];
|
|
pStrip->m_pIndices[first] = pStrip->m_pIndices[last];
|
|
pStrip->m_pIndices[last] = temp;
|
|
first++;
|
|
last--;
|
|
}
|
|
}
|
|
|
|
// Make sure we keep the list in order and always pull off
|
|
// the first dude.
|
|
if( ppBestStrip != pStripList->begin() )
|
|
{
|
|
// Swap strips
|
|
CStrip* temp = (*ppBestStrip);
|
|
(*ppBestStrip) = (*pStripList->begin());
|
|
(*pStripList->begin()) = temp;
|
|
}
|
|
|
|
return pStripList->begin();
|
|
}
|
|
|
|
|
|
//--------------------------------------------------------------------------------------
|
|
// Name: FindBestCachedStrip()
|
|
// Desc: Given a striplist and current cache state, pick the best next strip
|
|
//--------------------------------------------------------------------------------------
|
|
CStrip** CStripper::FindBestCachedStrip( CStripList* pStripList,
|
|
const CVertCache& VertexCache )
|
|
{
|
|
if( 0 == pStripList->m_dwNumStrips )
|
|
return NULL;
|
|
|
|
CStrip** ppBestStrip = pStripList->begin();
|
|
|
|
BOOL bBestStripFlipped = FALSE;
|
|
|
|
int MaxCacheHits = -1;
|
|
|
|
DWORD dwBestNeighborCount = (*ppBestStrip)->m_dwNumNeighbors;
|
|
|
|
// Go through all the other strips looking for the best caching
|
|
for( DWORD i = 0; i < pStripList->m_dwNumStrips; i++ )
|
|
{
|
|
CStrip* pStrip = pStripList->m_pStrips[i];
|
|
DWORD dwStripLen = pStrip->m_dwNumIndices;
|
|
BOOL bStripFlipped = FALSE;
|
|
|
|
// Copy current state of cache
|
|
CVertCache NewVertexCache = VertexCache;
|
|
|
|
// Figure out what this guy would do to our cache
|
|
for( DWORD ivert = 0; ivert < dwStripLen; ivert++ )
|
|
NewVertexCache.Add( 2, pStrip->m_pIndices[ivert] );
|
|
|
|
// See if we can get better cache hits if we reverse the order we draw
|
|
// the strip in.
|
|
{
|
|
// Create a copy of the vertex cache, with all vertices flipped
|
|
CVertCache FlippedVertexCache = VertexCache;
|
|
for( int ivert = pStrip->m_dwNumIndices-1; ivert >= 0; ivert-- )
|
|
FlippedVertexCache.Add( 2, pStrip->m_pIndices[ivert] );
|
|
|
|
// Accept the flipped cache if it gives us more cache hits
|
|
if( FlippedVertexCache.NumCacheHits() > NewVertexCache.NumCacheHits() )
|
|
{
|
|
NewVertexCache = FlippedVertexCache;
|
|
bStripFlipped = TRUE;
|
|
}
|
|
}
|
|
|
|
// Record the best number of cache hits to date
|
|
int NumCacheHits = NewVertexCache.NumCacheHits() - VertexCache.NumCacheHits();
|
|
|
|
if( NumCacheHits > MaxCacheHits )
|
|
{
|
|
MaxCacheHits = NumCacheHits;
|
|
ppBestStrip = &pStripList->m_pStrips[i];
|
|
bBestStripFlipped = bStripFlipped;
|
|
dwBestNeighborCount = pStripList->m_pStrips[i]->m_dwNumNeighbors;
|
|
}
|
|
else if ( NumCacheHits == MaxCacheHits &&
|
|
pStripList->m_pStrips[i]->m_dwNumNeighbors < dwBestNeighborCount )
|
|
{
|
|
ppBestStrip = &pStripList->m_pStrips[i];
|
|
bBestStripFlipped = bStripFlipped;
|
|
dwBestNeighborCount = pStripList->m_pStrips[i]->m_dwNumNeighbors;
|
|
}
|
|
}
|
|
|
|
if( bBestStripFlipped )
|
|
{
|
|
CStrip* pStrip = *ppBestStrip;
|
|
int first = 0;
|
|
int last = pStrip->m_dwNumIndices - 1;
|
|
|
|
while( first < last )
|
|
{
|
|
// Swap vertex indices
|
|
WORD temp = pStrip->m_pIndices[first];
|
|
pStrip->m_pIndices[first] = pStrip->m_pIndices[last];
|
|
pStrip->m_pIndices[last] = temp;
|
|
first++;
|
|
last--;
|
|
}
|
|
|
|
// We must also reverse the starting winding for odd length strips.
|
|
if( (pStrip->m_dwNumIndices & 0x1) )
|
|
{
|
|
pStrip->m_bIsStripCW = !pStrip->m_bIsStripCW;
|
|
}
|
|
}
|
|
|
|
// Make sure we keep the list in order and always pull off
|
|
// the first dude.
|
|
if( ppBestStrip != pStripList->begin() )
|
|
{
|
|
// Swap strips
|
|
CStrip* temp = (*ppBestStrip);
|
|
(*ppBestStrip) = (*pStripList->begin());
|
|
(*pStripList->begin()) = temp;
|
|
}
|
|
|
|
return pStripList->begin();
|
|
}
|
|
|
|
|
|
//--------------------------------------------------------------------------------------
|
|
// Name: CreateManyStrips()
|
|
// Desc: Don't merge the strips - just blast em into the stripbuffer one by one
|
|
// (useful for debugging)
|
|
//--------------------------------------------------------------------------------------
|
|
int CStripper::CreateManyStrips( CStripList* pStripList, WORD** ppStripIndices )
|
|
{
|
|
// Count the number of indices. Allow room for each of the strips size
|
|
// plus the final 0
|
|
DWORD dwIndexCount = pStripList->m_dwNumStrips + 1;
|
|
|
|
// We're storing the strips in [size1 i1 i2 i3][size2 i4 i5 i6][0] format
|
|
for( DWORD i = 0; i < pStripList->m_dwNumStrips; i++ )
|
|
{
|
|
// Add striplength plus potential degenerate to swap ccw --> cw
|
|
dwIndexCount += pStripList->m_pStrips[i]->m_dwNumIndices + 1;
|
|
}
|
|
|
|
// Alloc the space for all this stuff
|
|
WORD* pStripIndices = new WORD[dwIndexCount];
|
|
DWORD dwNumStripIndices = 0;
|
|
CVertCache VertexCache;
|
|
|
|
// Loop through all strips
|
|
CStrip** ppStrip = pStripList->begin();
|
|
|
|
while( pStripList->m_dwNumStrips > 0 )
|
|
{
|
|
CStrip* pStrip = *ppStrip;
|
|
|
|
if( !pStrip->m_bIsStripCW )
|
|
{
|
|
// Add an extra index if it's ccw
|
|
pStripIndices[dwNumStripIndices++] = (WORD)pStrip->m_dwNumIndices + 1;
|
|
pStripIndices[dwNumStripIndices++] = pStrip->m_pIndices[0];
|
|
}
|
|
else
|
|
{
|
|
// Add the strip length
|
|
pStripIndices[dwNumStripIndices++] = (WORD)pStrip->m_dwNumIndices;
|
|
}
|
|
|
|
// Add all the strip indices
|
|
for( DWORD i = 0; i < pStrip->m_dwNumIndices; i++)
|
|
{
|
|
pStripIndices[dwNumStripIndices++] = pStrip->m_pIndices[i];
|
|
VertexCache.Add( 1, pStrip->m_pIndices[i] );
|
|
}
|
|
|
|
// Free this guy and pop him off the list
|
|
pStripList->RemoveFirst();
|
|
|
|
// Get the next best strip
|
|
ppStrip = FindBestStrip( pStripList, VertexCache );
|
|
}
|
|
|
|
// Add terminating zero
|
|
pStripIndices[dwNumStripIndices++] = 0;
|
|
(*ppStripIndices) = pStripIndices;
|
|
|
|
return dwNumStripIndices;
|
|
}
|
|
|
|
|
|
//--------------------------------------------------------------------------------------
|
|
// Name: CreateLongStrip()
|
|
// Desc: Merge striplist into one big uberlist with (hopefully) optimal caching
|
|
//--------------------------------------------------------------------------------------
|
|
int CStripper::CreateLongStrip( CStripList* pStripList, WORD** ppwStripIndices )
|
|
{
|
|
// Allow room for one strip length plus a possible 3 extra indices per
|
|
// concatenated strip list plus the final 0
|
|
int dwIndexCount = (pStripList->m_dwNumStrips * 3) + 2;
|
|
|
|
// We're storing the strips in [size1 i1 i2 i3][size2 i4 i5 i6][0] format
|
|
for( DWORD i=0; i < pStripList->m_dwNumStrips; i ++ )
|
|
{
|
|
dwIndexCount += pStripList->m_pStrips[i]->m_dwNumIndices;
|
|
}
|
|
|
|
// Alloc the space for all this stuff
|
|
WORD* pStripIndices = new WORD[dwIndexCount];
|
|
int dwNumStripIndices = 0;
|
|
CVertCache VertexCache;
|
|
|
|
// Add first strip
|
|
CStrip** ppStrip = pStripList->begin();
|
|
CStrip* pStrip = *ppStrip;
|
|
|
|
// Note: first strip should be clock-wise
|
|
|
|
for( DWORD ivert = 0; ivert < pStrip->m_dwNumIndices; ivert++ )
|
|
{
|
|
pStripIndices[dwNumStripIndices++] = pStrip->m_pIndices[ivert];
|
|
VertexCache.Add( 1, pStrip->m_pIndices[ivert] );
|
|
}
|
|
|
|
// Kill first dude
|
|
pStripList->RemoveStripFromList( ppStrip );
|
|
|
|
// Add all the others
|
|
while( pStripList->m_dwNumStrips )
|
|
{
|
|
ppStrip = FindBestStrip( pStripList, VertexCache );
|
|
pStrip = *ppStrip;
|
|
WORD wLastVertex = pStripIndices[dwNumStripIndices - 1];
|
|
WORD wFirstVertex = pStrip->m_pIndices[0];
|
|
|
|
if( wFirstVertex != wLastVertex )
|
|
{
|
|
// Add degenerate from last strip
|
|
pStripIndices[dwNumStripIndices++] = wLastVertex;
|
|
|
|
// Add degenerate from our strip
|
|
pStripIndices[dwNumStripIndices++] = wFirstVertex;
|
|
}
|
|
|
|
// If we're not orientated correctly, we need to add a degenerate
|
|
if( pStrip->m_bIsStripCW != !(dwNumStripIndices & 0x1) )
|
|
{
|
|
// This shouldn't happen - we're currently trying very hard
|
|
// to keep everything oriented correctly.
|
|
pStripIndices[dwNumStripIndices++] = wFirstVertex;
|
|
}
|
|
|
|
// Add these verts
|
|
for( DWORD ivert = 0; ivert < pStrip->m_dwNumIndices; ivert++ )
|
|
{
|
|
pStripIndices[dwNumStripIndices++] = pStrip->m_pIndices[ivert];
|
|
VertexCache.Add( 1, pStrip->m_pIndices[ivert] );
|
|
}
|
|
|
|
// Free these guys
|
|
pStripList->RemoveStripFromList( ppStrip );
|
|
}
|
|
|
|
(*ppwStripIndices) = pStripIndices;
|
|
return dwNumStripIndices;
|
|
}
|
|
|
|
|
|
//--------------------------------------------------------------------------------------
|
|
// Name: CreateCachedStrip()
|
|
// Desc: Merge striplist into one big uberlist with (hopefully) optimal caching
|
|
//--------------------------------------------------------------------------------------
|
|
int CStripper::CreateCachedStrip( CStripList* pStripList, WORD** ppwStripIndices )
|
|
{
|
|
DWORD i;
|
|
WORD pTempVerts[CACHE_SIZE*4];
|
|
|
|
// Split up the strips into cache friendly pieces.
|
|
CStripList* pNewList = new CStripList(m_dwNumTris);
|
|
|
|
while( pStripList->m_dwNumStrips )
|
|
{
|
|
CStrip** ppStrip = pStripList->begin();
|
|
CStrip* pStrip = *ppStrip;
|
|
|
|
int start = 0;
|
|
int ssize = pStrip->m_dwNumTriangles;
|
|
|
|
do
|
|
{
|
|
int dsize = ssize;
|
|
|
|
if( dsize > CACHE_SIZE )
|
|
dsize = CACHE_SIZE;
|
|
|
|
int j = pNewList->m_dwNumStrips++;
|
|
|
|
// Create temp triangle list/index list.
|
|
int num_indices = CreateIndices( pStrip->m_bIsStripCW, dsize,
|
|
pStrip->m_pTriangles + start,
|
|
pTempVerts );
|
|
|
|
// Make new strip.
|
|
pNewList->m_pStrips[j] = new CStrip( dsize, num_indices );
|
|
|
|
pNewList->m_pStrips[j]->m_bIsStripCW = pStrip->m_bIsStripCW;
|
|
|
|
// Copy triangles.
|
|
memcpy( pNewList->m_pStrips[j]->m_pTriangles,
|
|
pStrip->m_pTriangles + start, dsize * sizeof(int) );
|
|
|
|
// Copy indices.
|
|
memcpy( pNewList->m_pStrips[j]->m_pIndices,
|
|
pTempVerts, num_indices * sizeof(WORD) );
|
|
|
|
start += dsize;
|
|
ssize -= dsize;
|
|
}
|
|
while( ssize > 0 );
|
|
|
|
pStripList->RemoveStripFromList( ppStrip );
|
|
}
|
|
|
|
// Count the number of adjacent triangles to each strip.
|
|
// an edge of the mesh.
|
|
for( i = 0; i < pNewList->m_dwNumStrips; i++ )
|
|
{
|
|
CStrip* pStrip = pNewList->m_pStrips[i];
|
|
|
|
DWORD count = 0;
|
|
|
|
for( DWORD j = 0; j < pStrip->m_dwNumTriangles; j++ )
|
|
{
|
|
// Count the number of neighbors.
|
|
for( int vert = 0; vert < 3; vert++ )
|
|
{
|
|
if (m_pTriInfo[pStrip->m_pTriangles[j]].neighbortri[vert] != -1)
|
|
count++;
|
|
}
|
|
}
|
|
|
|
pStrip->m_dwNumNeighbors = count;
|
|
}
|
|
|
|
// Should we remove/ignore very small strips?
|
|
|
|
// Allow room for one strip length plus a possible 3 extra indices per
|
|
// concatenated strip list plus the final 0
|
|
int dwIndexCount = (pNewList->m_dwNumStrips * 3) + 2;
|
|
|
|
// We're storing the strips in [size1 i1 i2 i3][size2 i4 i5 i6][0] format
|
|
for( i = 0; i < pNewList->m_dwNumStrips; i++ )
|
|
{
|
|
dwIndexCount += pNewList->m_pStrips[i]->m_dwNumIndices;
|
|
}
|
|
|
|
// Alloc the space for all this stuff
|
|
WORD* pStripIndices = new WORD[dwIndexCount];
|
|
DWORD dwNumStripIndices = 0;
|
|
CVertCache VertexCache;
|
|
|
|
// Add the strips
|
|
while( pNewList->m_dwNumStrips )
|
|
{
|
|
CStrip** ppStrip = FindBestCachedStrip( pNewList, VertexCache );
|
|
CStrip* pStrip = *ppStrip;
|
|
|
|
WORD wFirstVertex = pStrip->m_pIndices[0];
|
|
|
|
DWORD ivert = 0;
|
|
|
|
if (dwNumStripIndices > 0)
|
|
{
|
|
WORD wLastVertex = pStripIndices[dwNumStripIndices - 1];
|
|
|
|
assert( dwNumStripIndices > 2 );
|
|
|
|
if( wLastVertex == pStrip->m_pIndices[1] &&
|
|
pStripIndices[dwNumStripIndices - 2] == wFirstVertex &&
|
|
pStrip->m_bIsStripCW == !(dwNumStripIndices & 0x1) )
|
|
{
|
|
// We are re-stitching strips together, so skip the first two
|
|
// verts of this strip.
|
|
ivert = 2;
|
|
}
|
|
else if( wFirstVertex != wLastVertex )
|
|
{
|
|
// Add degenerate from last strip
|
|
pStripIndices[dwNumStripIndices++] = wLastVertex;
|
|
|
|
// Add degenerate from our strip
|
|
pStripIndices[dwNumStripIndices++] = wFirstVertex;
|
|
}
|
|
}
|
|
|
|
// If we're not orientated correctly, we need to add a degenerate
|
|
if( pStrip->m_bIsStripCW != !(dwNumStripIndices & 0x1) )
|
|
{
|
|
pStripIndices[dwNumStripIndices++] = wFirstVertex;
|
|
}
|
|
|
|
// Add these verts and update cache.
|
|
while( ivert < pStrip->m_dwNumIndices )
|
|
{
|
|
pStripIndices[dwNumStripIndices] = pStrip->m_pIndices[ivert];
|
|
VertexCache.Add( 1, pStrip->m_pIndices[ivert] );
|
|
dwNumStripIndices++;
|
|
ivert++;
|
|
}
|
|
|
|
// Free these guys
|
|
pNewList->RemoveStripFromList( ppStrip );
|
|
}
|
|
|
|
delete pNewList;
|
|
|
|
(*ppwStripIndices) = pStripIndices;
|
|
return dwNumStripIndices;
|
|
}
|
|
|
|
|
|
//--------------------------------------------------------------------------------------
|
|
// Name: BuildStrips()
|
|
// Desc: Build a (hopefully) optimal set of strips from a trilist
|
|
//--------------------------------------------------------------------------------------
|
|
void CStripper::BuildStrips( CStripList* pStripList, int maxlen, BOOL bLookAhead,
|
|
BOOL bNonSequential, BOOL bSwapOrientation )
|
|
{
|
|
// temp indices storage
|
|
const int cNumTmpVerts = 1024;
|
|
WORD pStripVerts[cNumTmpVerts + 1];
|
|
int pStripTris[cNumTmpVerts + 1];
|
|
|
|
// clear all the used flags for the tris
|
|
ZeroMemory( m_pUsed, m_dwNumTris * sizeof(m_pUsed[0]) );
|
|
|
|
BOOL bStartCW = TRUE;
|
|
|
|
for( ;; )
|
|
{
|
|
int besttri = 0;
|
|
int bestvert = 0;
|
|
float bestratio = 2.0f;
|
|
int bestneighborcount = INT_MAX;
|
|
|
|
for( int tri = 0; tri < m_dwNumTris; tri++)
|
|
{
|
|
// if used the continue
|
|
if(m_pUsed[tri])
|
|
continue;
|
|
|
|
// get the neighbor count
|
|
int curneighborcount = GetNeighborCount(tri);
|
|
|
|
// push all the singletons to the very end
|
|
if( !curneighborcount )
|
|
curneighborcount = 4;
|
|
|
|
// if this guy has more neighbors than the current best - bail
|
|
if( curneighborcount > bestneighborcount )
|
|
continue;
|
|
|
|
// try starting the strip with each of this tris verts
|
|
for( int vert = 0; vert < 3; vert++ )
|
|
{
|
|
int swaps;
|
|
int num_tris = CreateStrip( tri, vert, maxlen, &swaps, bLookAhead,
|
|
bNonSequential, bStartCW, pStripTris );
|
|
|
|
int len = 2 + num_tris + swaps;
|
|
float ratio = (len == 3) ? 1.0f : (float)swaps / len;
|
|
|
|
// check if this ratio is better than what we've already got for
|
|
// this neighborcount
|
|
if( (curneighborcount < bestneighborcount) ||
|
|
(curneighborcount == bestneighborcount && ratio < bestratio) )
|
|
{
|
|
bestneighborcount = curneighborcount;
|
|
besttri = tri;
|
|
bestvert = vert;
|
|
bestratio = ratio;
|
|
}
|
|
}
|
|
}
|
|
|
|
// no strips found?
|
|
if( bestneighborcount == INT_MAX )
|
|
break;
|
|
|
|
// recreate this strip
|
|
int swaps;
|
|
int num_tris = CreateStrip( besttri, bestvert, maxlen, &swaps, bLookAhead,
|
|
bNonSequential, bStartCW, pStripTris );
|
|
|
|
// Mark the tris on the best strip as used
|
|
for( int tri = 0; tri < num_tris; tri++ )
|
|
m_pUsed[pStripTris[tri]] = 1;
|
|
|
|
// Make the indices from the triangle verts.
|
|
int num_indices = CreateIndices( bStartCW, num_tris, pStripTris, pStripVerts );
|
|
|
|
// Create a new CStrip and stuff in the list.
|
|
CStrip* pStrip = new CStrip( num_tris, num_indices );
|
|
|
|
pStrip->m_bIsStripCW = bStartCW;
|
|
|
|
for( int j = 0; j < num_tris; j++ )
|
|
pStrip->m_pTriangles[j] = pStripTris[j];
|
|
|
|
for( int k = 0; k < num_indices; k++ )
|
|
pStrip->m_pIndices[k] = pStripVerts[k];
|
|
|
|
// Store the CStrip
|
|
pStripList->AddStripToList( pStrip );
|
|
|
|
if( bSwapOrientation )
|
|
{
|
|
// if strip was odd - swap orientation
|
|
if( (num_indices & 0x1) )
|
|
bStartCW = !bStartCW;
|
|
}
|
|
}
|
|
}
|
|
|
|
|
|
//--------------------------------------------------------------------------------------
|
|
// Name: InitTriangleInfo()
|
|
// Desc: Initialize triangle information (edges, #neighbors, etc.)
|
|
//--------------------------------------------------------------------------------------
|
|
void CStripper::InitTriangleInfo(int tri, int vert)
|
|
{
|
|
WORD* ptriverts = &m_pTriangles[tri + 1][0];
|
|
int vert1 = m_pTriangles[tri][(vert + 1) % 3];
|
|
int vert2 = m_pTriangles[tri][vert];
|
|
|
|
for( int itri = tri + 1; itri < m_dwNumTris; itri++, ptriverts += 3 )
|
|
{
|
|
if( m_pUsed[itri] != 0x7 )
|
|
{
|
|
for( int ivert = 0; ivert < 3; ivert++ )
|
|
{
|
|
if( ( ptriverts[ivert] == vert1) &&
|
|
( ptriverts[(ivert + 1) % 3] == vert2 ) )
|
|
{
|
|
// add the triangle info
|
|
m_pTriInfo[tri].neighbortri[vert] = itri;
|
|
m_pTriInfo[tri].neighboredge[vert] = ivert;
|
|
m_pUsed[tri] |= (1 << vert);
|
|
|
|
m_pTriInfo[itri].neighbortri[ivert] = tri;
|
|
m_pTriInfo[itri].neighboredge[ivert] = vert;
|
|
m_pUsed[itri] |= (1 << ivert);
|
|
return;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
|
|
//--------------------------------------------------------------------------------------
|
|
// Name: CStripper()
|
|
// Desc: Constructor
|
|
//--------------------------------------------------------------------------------------
|
|
CStripper::CStripper( int dwNumTris, TRIANGLELIST pTriangles )
|
|
{
|
|
// Store trilist info
|
|
m_dwNumTris = dwNumTris;
|
|
m_pTriangles = pTriangles;
|
|
m_pUsed = new int[dwNumTris];
|
|
m_pTriInfo = new TRIANGLEINFO[dwNumTris];
|
|
|
|
// Init triinfo
|
|
for( int itri = 0; itri < dwNumTris; itri++ )
|
|
{
|
|
m_pTriInfo[itri].neighbortri[0] = -1;
|
|
m_pTriInfo[itri].neighbortri[1] = -1;
|
|
m_pTriInfo[itri].neighbortri[2] = -1;
|
|
}
|
|
|
|
// Clear the used flag
|
|
ZeroMemory( m_pUsed, m_dwNumTris * sizeof(m_pUsed[0]) );
|
|
|
|
// Go through all the triangles and find edges, neighbor counts
|
|
for( int itri = 0; itri < dwNumTris; itri++ )
|
|
{
|
|
for( int ivert = 0; ivert < 3; ivert++ )
|
|
{
|
|
if( !(m_pUsed[itri] & (1 << ivert)) )
|
|
InitTriangleInfo( itri, ivert );
|
|
}
|
|
}
|
|
|
|
// Clear the used flags from InitTriangleInfo
|
|
ZeroMemory( m_pUsed, m_dwNumTris * sizeof(m_pUsed[0]) );
|
|
}
|
|
|
|
|
|
//--------------------------------------------------------------------------------------
|
|
// Name: ~CStripper()
|
|
// Desc: Destructor
|
|
//--------------------------------------------------------------------------------------
|
|
CStripper::~CStripper()
|
|
{
|
|
delete[] m_pUsed;
|
|
delete[] m_pTriInfo;
|
|
}
|
|
|
|
|
|
//--------------------------------------------------------------------------------------
|
|
// Name: Add()
|
|
// Desc: Add an index to the cache - returns true if it was added, false otherwise
|
|
//--------------------------------------------------------------------------------------
|
|
int CVertCache::Add( int strip, int vertindex )
|
|
{
|
|
// Find index in cache
|
|
for( int iCache = 0; iCache < CACHE_SIZE; iCache++ )
|
|
{
|
|
if( vertindex == m_rgCache[iCache] )
|
|
{
|
|
// If it's in the cache and it's from a different strip
|
|
// change the strip to the new one and count the cache hit
|
|
if( strip != m_rgCacheStrip[iCache] )
|
|
{
|
|
m_cachehits++;
|
|
m_rgCacheStrip[iCache] = strip;
|
|
m_bReUsed[iCache] = true;
|
|
}
|
|
|
|
// Item is already in the cache, so no need to add it
|
|
return 0;
|
|
}
|
|
}
|
|
|
|
int retval = 1;
|
|
|
|
// If we are push one of the verts add by our strip out of the cache, return two.
|
|
if ( m_rgCache[m_iCachePtr] != -1 && m_rgCacheStrip[m_iCachePtr] == strip &&
|
|
!m_bReUsed[m_iCachePtr] )
|
|
retval = 2;
|
|
|
|
// Not in cache, add vert and strip
|
|
m_rgCache[m_iCachePtr] = (WORD)vertindex;
|
|
m_rgCacheStrip[m_iCachePtr] = strip;
|
|
m_bReUsed[m_iCachePtr] = false;
|
|
m_iCachePtr = (m_iCachePtr + 1) % CACHE_SIZE;
|
|
|
|
return retval;
|
|
}
|
|
|
|
|
|
//--------------------------------------------------------------------------------------
|
|
// Name: CountCacheMisses()
|
|
// Desc: Count the number of cache misses for a given strip.
|
|
//--------------------------------------------------------------------------------------
|
|
DWORD CountCacheMisses( DWORD dwIndexCount, WORD *pStripIndices )
|
|
{
|
|
CVertCache VertexCache;
|
|
|
|
DWORD dwMisses = 0;
|
|
|
|
for ( DWORD i = 0; i < dwIndexCount; i++ )
|
|
dwMisses += (VertexCache.Add( 1, pStripIndices[i] ) != 0);
|
|
|
|
return dwMisses;
|
|
}
|
|
|
|
|
|
//--------------------------------------------------------------------------------------
|
|
// Name: TriStripToTriList()
|
|
// Desc: Convert a tri-strip to a tri-list.
|
|
//--------------------------------------------------------------------------------------
|
|
DWORD TriStripToTriList( DWORD dwNumStripIndices, const WORD *pStripIndices,
|
|
WORD *pTriangleIndices )
|
|
{
|
|
DWORD dwNumTriangleIndices = 0;
|
|
|
|
// Unstrip the indices.
|
|
WORD ind0 = 0;
|
|
WORD ind1 = pStripIndices[0];
|
|
WORD ind2 = pStripIndices[1];
|
|
|
|
for( DWORD src = 2; src < dwNumStripIndices; src++ )
|
|
{
|
|
ind0 = ind1;
|
|
ind1 = ind2;
|
|
ind2 = pStripIndices[src];
|
|
|
|
// Check for null-triangles.
|
|
if( ind0 != ind1 && ind1 != ind2 && ind2 != ind0 )
|
|
{
|
|
if( src & 1 )
|
|
{
|
|
pTriangleIndices[dwNumTriangleIndices] = ind1;
|
|
dwNumTriangleIndices++;
|
|
|
|
pTriangleIndices[dwNumTriangleIndices] = ind0;
|
|
dwNumTriangleIndices++;
|
|
|
|
// always put the new index last
|
|
pTriangleIndices[dwNumTriangleIndices] = ind2;
|
|
dwNumTriangleIndices++;
|
|
}
|
|
else
|
|
{
|
|
pTriangleIndices[dwNumTriangleIndices] = ind0;
|
|
dwNumTriangleIndices++;
|
|
|
|
pTriangleIndices[dwNumTriangleIndices] = ind1;
|
|
dwNumTriangleIndices++;
|
|
|
|
// always put the new index last
|
|
pTriangleIndices[dwNumTriangleIndices] = ind2;
|
|
dwNumTriangleIndices++;
|
|
}
|
|
}
|
|
}
|
|
|
|
return dwNumTriangleIndices;
|
|
}
|
|
|
|
|
|
//--------------------------------------------------------------------------------------
|
|
// Name: MakeStrips()
|
|
// Desc: Stripify routine
|
|
//--------------------------------------------------------------------------------------
|
|
DWORD TriStripper::MakeStrips( DWORD dwNumTriangles, WORD* pTriangles,
|
|
DWORD* pdwNumIndices, WORD** ppStripIndices,
|
|
DWORD dwFlags )
|
|
{
|
|
if( 0 == dwNumTriangles || NULL == pTriangles )
|
|
return 0;
|
|
|
|
*ppStripIndices = 0;
|
|
|
|
// The stripper, and storage for it's best results
|
|
CStripper stripper( dwNumTriangles, (TRIANGLELIST)pTriangles );
|
|
|
|
DWORD dwBestCost = 0xffffffff;
|
|
DWORD dwBestIndexCount = 0;
|
|
WORD* pTempStripIndices;
|
|
|
|
// Map of various args to try stripifying mesh with
|
|
struct ARGMAP
|
|
{
|
|
DWORD dwMaxLength; // Maximum length of strips
|
|
BOOL bLookAhead; // Whether to use sgi greedy lookahead
|
|
BOOL bNonSequential; // Take non-sequential exits to lengthen strips.
|
|
};
|
|
|
|
ARGMAP argmap[] =
|
|
{
|
|
{ 1024, TRUE, TRUE },
|
|
{ 1024, FALSE, TRUE },
|
|
{ 1024, FALSE, FALSE },
|
|
};
|
|
const int dwNumArgMaps = sizeof(argmap)/sizeof(ARGMAP);
|
|
|
|
// Build strips with the various maxlength and lookahead arguments, and
|
|
// pick the one with the least result index count.
|
|
for( int map = 0; map < dwNumArgMaps; map++ )
|
|
{
|
|
// Build the strip with the various maxlength and lookahead arguments
|
|
CStripList* pStripList = new CStripList(dwNumTriangles);
|
|
|
|
stripper.BuildStrips( pStripList, argmap[map].dwMaxLength,
|
|
argmap[map].bLookAhead, argmap[map].bNonSequential,
|
|
(dwFlags & ATGTRISTRIPPER_OPTIMIZE_FOR_INDICES) != 0 );
|
|
|
|
DWORD dwIndexCount;
|
|
DWORD dwCost;
|
|
|
|
// Build strip (freeing the strip list).
|
|
if( dwFlags & ATGTRISTRIPPER_OPTIMIZE_FOR_INDICES )
|
|
{
|
|
dwIndexCount = stripper.CreateLongStrip( pStripList, &pTempStripIndices );
|
|
|
|
// Cost is just the number of indices.
|
|
dwCost = dwIndexCount;
|
|
}
|
|
else
|
|
{
|
|
dwIndexCount = stripper.CreateCachedStrip( pStripList, &pTempStripIndices );
|
|
|
|
// Count number of cache misses.
|
|
DWORD dwMisses = CountCacheMisses( dwIndexCount, pTempStripIndices );
|
|
|
|
if( dwFlags & ATGTRISTRIPPER_OUTPUT_TRILIST )
|
|
{
|
|
// Nulls don't matter for tri-lists.
|
|
dwCost = dwMisses;
|
|
}
|
|
else
|
|
{
|
|
// Cost is the (shader length) / 2 + (# null tris) * 2
|
|
dwCost = dwMisses * (SHADER_CYCLES/2) +
|
|
(dwIndexCount - (dwNumTriangles + 2)) * 2;
|
|
}
|
|
}
|
|
|
|
if ( dwCost < dwBestCost )
|
|
{
|
|
// Free the old best list
|
|
if( *ppStripIndices )
|
|
delete[] *ppStripIndices;
|
|
|
|
// store the new best list
|
|
*ppStripIndices = pTempStripIndices;
|
|
dwBestCost = dwCost;
|
|
dwBestIndexCount = dwIndexCount;
|
|
}
|
|
else
|
|
{
|
|
delete[] pTempStripIndices;
|
|
}
|
|
|
|
delete pStripList;
|
|
}
|
|
|
|
if( dwFlags & ATGTRISTRIPPER_OUTPUT_TRILIST )
|
|
{
|
|
// Convert to triangle list.
|
|
WORD* pTempIndices = new WORD[dwNumTriangles*3];
|
|
|
|
dwBestIndexCount = TriStripToTriList( dwBestIndexCount, *ppStripIndices,
|
|
pTempIndices );
|
|
|
|
assert( dwBestIndexCount <= dwNumTriangles*3 );
|
|
|
|
delete[] *ppStripIndices;
|
|
*ppStripIndices = pTempIndices;
|
|
}
|
|
|
|
if( pdwNumIndices )
|
|
(*pdwNumIndices) = dwBestIndexCount;
|
|
|
|
return dwBestIndexCount;
|
|
}
|
|
|
|
|
|
//--------------------------------------------------------------------------------------
|
|
// Name: ComputeVertexPermutation()
|
|
// Desc: Reorder the vertices
|
|
//--------------------------------------------------------------------------------------
|
|
VOID TriStripper::ComputeVertexPermutation( DWORD dwNumStripIndices, WORD* pStripIndices,
|
|
DWORD dwNumVertices, WORD** ppVertexPermutation )
|
|
{
|
|
// Sort verts to maximize locality.
|
|
SortEntry* pSortTable = new SortEntry[dwNumVertices];
|
|
|
|
// Fill in original index.
|
|
for( DWORD i = 0; i < dwNumVertices; i++ )
|
|
{
|
|
pSortTable[i].iOrigIndex = i;
|
|
pSortTable[i].iFirstUsed = -1;
|
|
}
|
|
|
|
// Fill in first used flag.
|
|
for( DWORD i = 0; i < dwNumStripIndices; i++ )
|
|
{
|
|
int index = pStripIndices[i];
|
|
|
|
if( pSortTable[index].iFirstUsed == -1 )
|
|
pSortTable[index].iFirstUsed = i;
|
|
}
|
|
|
|
// Sort the table, using the STL sort() routine.
|
|
std::sort( pSortTable, pSortTable + dwNumVertices );
|
|
|
|
// Copy re-mapped to original vertex permutation into output array.
|
|
(*ppVertexPermutation) = new WORD[dwNumVertices];
|
|
|
|
for( DWORD i = 0; i < dwNumVertices; i++ )
|
|
{
|
|
(*ppVertexPermutation)[i] = (WORD)pSortTable[i].iOrigIndex;
|
|
}
|
|
|
|
// Build original to re-mapped permutation.
|
|
WORD* pInversePermutation = new WORD[dwNumVertices];
|
|
|
|
for( DWORD i = 0; i < dwNumVertices; i++ )
|
|
{
|
|
pInversePermutation[pSortTable[i].iOrigIndex] = (WORD)i;
|
|
}
|
|
|
|
// We need to remap indices as well.
|
|
for( DWORD i = 0; i < dwNumStripIndices; i++ )
|
|
{
|
|
pStripIndices[i] = pInversePermutation[ pStripIndices[i] ];
|
|
}
|
|
|
|
delete[] pSortTable;
|
|
delete[] pInversePermutation;
|
|
}
|
|
|
|
|
|
//--------------------------------------------------------------------------------------
|
|
// Name: CalcCacheHits()
|
|
// Desc: Calculate the number of cache hits and degenerate triangles
|
|
//--------------------------------------------------------------------------------------
|
|
HRESULT TriStripper::CalcCacheHits( D3DPRIMITIVETYPE dwPrimType, DWORD dwVertexSize,
|
|
WORD* pIndices, DWORD dwNumIndices,
|
|
DWORD* pdwNumDegenerateTris,
|
|
DWORD* pdwNumCacheHits,
|
|
DWORD* pdwNumPagesCrossed )
|
|
{
|
|
// Check arguments
|
|
if( NULL == pdwNumDegenerateTris || NULL == pdwNumCacheHits ||
|
|
NULL == pdwNumPagesCrossed )
|
|
return E_INVALIDARG;
|
|
|
|
// Initialize results
|
|
(*pdwNumDegenerateTris) = 0;
|
|
(*pdwNumCacheHits) = 0;
|
|
(*pdwNumPagesCrossed) = 1;
|
|
|
|
// Simulate a vertex cache
|
|
static const int CACHE_SIZE = 12;
|
|
static const int PAGE_SIZE = 4096;
|
|
DWORD rgdwCache[CACHE_SIZE];
|
|
INT iCachePtr = 0;
|
|
BOOL bIsTriStrip = (dwPrimType == D3DPT_TRIANGLESTRIP);
|
|
DWORD dwLastPageAddr = 0;
|
|
memset( rgdwCache, 0xff, sizeof(rgdwCache) );
|
|
|
|
// Run all vertices through the simulated vertex cache, tallying cache hits,
|
|
// degenerate triangles, and pages crossed.
|
|
for( DWORD i = 0; i < dwNumIndices; i++ )
|
|
{
|
|
// This makes all kinds of assumptions such as page size is 4k,
|
|
// page across then back is ok, etc etc. Seems to be an ok
|
|
// estimate on data locality though.
|
|
DWORD dwPage = dwVertexSize * pIndices[i] / PAGE_SIZE;
|
|
|
|
if( ( dwPage > dwLastPageAddr ) || ( dwPage+1 < dwLastPageAddr ) )
|
|
{
|
|
(*pdwNumPagesCrossed)++;
|
|
dwLastPageAddr = dwVertexSize * pIndices[i] / PAGE_SIZE;
|
|
}
|
|
|
|
// Update our count of degenerate tris
|
|
if( bIsTriStrip && (i > 1) )
|
|
if( ( pIndices[i-0] == pIndices[i-1] ) ||
|
|
( pIndices[i-0] == pIndices[i-2] ) ||
|
|
( pIndices[i-1] == pIndices[i-2] ) )
|
|
(*pdwNumDegenerateTris)++;
|
|
|
|
// Check to see if the vertex would be in the cache
|
|
BOOL bVertexInCache = FALSE;
|
|
for( int cache_index = 0; cache_index < CACHE_SIZE; cache_index++ )
|
|
{
|
|
if( pIndices[i] == rgdwCache[cache_index] )
|
|
{
|
|
bVertexInCache = TRUE;
|
|
break;
|
|
}
|
|
}
|
|
|
|
if( bVertexInCache )
|
|
{
|
|
// Keep track of cache hits
|
|
(*pdwNumCacheHits)++;
|
|
}
|
|
else
|
|
{
|
|
// Add vertex to simulated cache
|
|
rgdwCache[iCachePtr] = pIndices[i];
|
|
iCachePtr = (iCachePtr + 1) % CACHE_SIZE;
|
|
}
|
|
}
|
|
|
|
return S_OK;
|
|
}
|