OptimizeFacesLRU

DirectXMesh

Reorders faces to improve post-transform vertex cache reuse using the Forsyth algorithm.

HRESULT OptimizeFacesLRU(
   const uint16_t* indices, size_t nFaces,
   uint32_t* faceRemap,
   uint32_t lruCacheSize = OPTFACES_LRU_DEFAULT );

HRESULT OptimizeFacesLRUEx(
   const uint16_t* indices, size_t nFaces,
   const uint32_t* attributes,
   uint32_t* faceRemap,
   uint32_t lruCacheSize = OPTFACES_LRU_DEFAULT );

HRESULT OptimizeFacesLRU(
   const uint32_t* indices, size_t nFaces,
   uint32_t* faceRemap,
   uint32_t lruCacheSize = OPTFACES_LRU_DEFAULT );

HRESULT OptimizeFacesEx(
   const uint32_t* indices, size_t nFaces,
   const uint32_t* attributes,
   uint32_t* faceRemap,
   uint32_t lruCacheSize = OPTFACES_LRU_DEFAULT );

See also OptimizeFaces

Parameters

faceRemap is an array describing the reordering, and must have nFaces entries: oldLoc = faceRemap[newLoc]. See ReorderIB 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 simulate for the optimization. This number should range from 1 to 64, and defaults to 32.

Remarks

The primary benefits of using Forsyth's algorithm are:

1. Adjacency is not required
2. If the simulated cache size is too large for the target hardware, performance drop-off tends to be more graceful than the Hoppe algorithm. Therefore a less conservative simulated cache size is required in practice.

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

There are models where the optimization fails to produce a faster ordering. For this reason, you should evaluate the original and optimized models with ComputeVertexCacheMissRate. If the new model is worse, use the original.

Example

auto mesh = std::make_unique<WaveFrontReader<uint16_t>>();

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

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

auto faceRemap = std::make_unique<uint32_t[]>(nFaces);
if ( FAILED( OptimizeFacesLRU( mesh->indices.data(), nFaces,
   faceRemap.get() ) ) )
   // Error

auto newIndices = std::make_unique<uint16_t[]>(nFaces * 3);
if ( FAILED( ReorderIB( mesh->indices.data(), nFaces, faceRemap.get(),
   newIndices.get() ) ) )
   // Error

Further Reading

Post Transform Cache

Forsyth, T.; "Linear-Speed Vertex Cache Optimisation" link