Reorders faces to improve post-transform vertex cache reuse.

HRESULT OptimizeFaces(
   _In_reads_(nFaces*3) const uint16_t* indices, _In_ size_t nFaces,
   _In_reads_(nFaces*3) const uint32_t* adjacency,
   _Out_writes_(nFaces) uint32_t* faceRemap,
   _In_ uint32_t vertexCache = OPTFACES_V_DEFAULT,
   _In_ uint32_t restart = OPTFACES_R_DEFAULT );

HRESULT OptimizeFaces(
   _In_reads_(nFaces*3) const uint32_t* indices, _In_ size_t nFaces,
   _In_reads_(nFaces*3) const uint32_t* adjacency,
   _Out_writes_(nFaces) uint32_t* faceRemap,
   _In_ uint32_t vertexCache = OPTFACES_V_DEFAULT,
   _In_ uint32_t restart = OPTFACES_R_DEFAULT );

HRESULT OptimizeFacesEx(
   _In_reads_(nFaces*3) const uint16_t* indices, _In_ size_t nFaces,
   _In_reads_(nFaces*3) const uint32_t* adjacency,
   _In_reads_(nFaces) const uint32_t* attributes,
   _Out_writes_(nFaces) uint32_t* faceRemap,
   _In_ uint32_t vertexCache = OPTFACES_V_DEFAULT,
   _In_ uint32_t restart = OPTFACES_R_DEFAULT );

HRESULT OptimizeFacesEx(
   _In_reads_(nFaces*3) const uint32_t* indices, _In_ size_t nFaces,
   _In_reads_(nFaces*3) const uint32_t* adjacency,
   _In_reads_(nFaces) const uint32_t* attributes,
   _Out_writes_(nFaces) uint32_t* faceRemap,
   _In_ uint32_t vertexCache = OPTFACES_V_DEFAULT,
   _In_ uint32_t restart = OPTFACES_R_DEFAULT );

Parameters

faceRemap is an array describing the reordering. See ReorderIB and ReorderIBAndAdjacency for details.

Note this matches the D3DXMesh::Optimize method and D3DXOptimizeFaces function definitions of the face remap array.

vertexCache is the size of the vertex cache to assume for the optimization. If OPTFACES_STRIPORDER is provided, then the vertex cache simulation is not used and the faces are put in "strip order". This number should typically range from 0 to 32.

restart is a threshold used to control when strips are restarted based. This number must be less than or equal to vertexCache, and is ignored for OPTFACES_STRIPORDER.

Remarks

This implements the same algorithm as D3DX with explicit control over the simulated vertex cache size. OPTFACES_V_DEFAULT / OPTFACES_R_DEFAULT is the same value that D3DXOptimizeFaces used (.e. D3DXMESHOPT_DEVICEINDEPENDENT).

Some vendors support a Direct3D 9 query D3DQUERYTYPE_VCACHE that reports the vertex cache optimization settings that are device specific. If OptMethod is 0, use OPTFACES_STRIPORDER, otherwise pass CacheSize as vertexCache and MagicNumber as restart. For some example code for checking this query, see vcache.cpp

Note that optimizing for a vertexCache larger than is present on the hardware can result in poorer performance than the original mesh, so this value should be picked either for a known fixed device or conservatively.

Degenerate and 'unused' faces are skipped by the optimization, so they do not appear in the remap order.

Example

std::unique_ptr<WaveFrontReader<uint16_t>> mesh( new WaveFrontReader<uint16_t>() );

if ( FAILED( mesh->Load( L"test.obj" ) ) )
   // Error

size_t nFaces = mesh->indices.size() / 3;
size_t nVerts = mesh->vertices.size();

std::unique_ptr<XMFLOAT3[]> pos( new XMFLOAT3[ nVerts ] );
for( size_t j = 0; j < nVerts; ++j )
   pos[ j ] = mesh->vertices[ j ].position;

std::unique_ptr<uint32_t[]> adj( new uint32_t[ mesh->indices.size() ] );
if ( FAILED( GenerateAdjacencyAndPointReps( &mesh->indices.front(), nFaces,
   pos.get(), nVerts, 0.f, nullptr, adj.get() ) ) )
   // Error

std::unique_ptr<uint32_t[]> faceRemap( new uint32_t[ nFaces ] );
if ( FAILED( OptimizeFaces( &mesh->indices.front(), nFaces, adj.get(),
   faceRemap.get() ) ) )
   // Error

std::unique_ptr<uint16_t[]> newIndices( new uint16_t[ nFaces * 3 ] );
if ( FAILED( ReorderIB( &mesh->indices.front(), nFaces, faceRemap.get(),
   newIndices.get() ) ) )
   // Error

Further Reading

http://www.opengl.org/wiki/Post_Transform_Cache

Hoppe, H.; "Optimization of mesh locality for transparent vertex caching", ACM SIGGRAPH 1999 Proceedings
http://research.microsoft.com/en-us/um/people/hoppe/proj/tvc/

Last edited Nov 20, 2014 at 6:56 PM by walbourn, version 27