Vertex cache ordering

since 0.7.0 Scene and geometry

Open the live demo · Read the source · View on GitHub

A GPU keeps a small window of recently transformed vertices. A triangle order that reuses them costs less than one that keeps reaching for a vertex the cache has already dropped. This page shuffles a mesh's triangles and puts them back in a cache-friendly order.

Step 1: Scramble a sphere's triangles #

SphereShape already produces a fairly local order, so the page shuffles it first with a fixed seed, to have something worth reordering. The vertices are untouched; only which triangle is drawn when changes.

final MeshData sphere = const SphereShape(
  radius: 1.1,
  segments: 32,
  rings: 16,
).build();
final int triangleCount = sphere.triangleCount;
final List<int> order = List<int>.generate(triangleCount, (int i) => i)
  ..shuffle(math.Random(7));
final Uint32List scrambled = Uint32List(sphere.indices.length);
for (var t = 0; t < triangleCount; t++) {
  final int from = order[t] * 3;
  scrambled[t * 3] = sphere.indices[from];
  scrambled[t * 3 + 1] = sphere.indices[from + 1];
  scrambled[t * 3 + 2] = sphere.indices[from + 2];
}

Step 2: Reorder for the cache, then renumber vertices #

optimizeTriangleOrder scores each triangle by how much of it a simulated cache still holds and emits the best one first. optimizeVertexFetch then renumbers vertices by the order they are first referenced, so nearby triangles also read nearby memory. averageCacheMissRatio scores an index list before and after: lower is better, and 3.0 is the worst a random order gets.

_beforeRatio = averageCacheMissRatio(scrambled);
final Uint32List cacheOrdered = optimizeTriangleOrder(
  scrambled,
  sphere.vertexCount,
);
final ({Uint32List indices, Uint32List oldToNew}) fetch =
    optimizeVertexFetch(cacheOrdered, sphere.vertexCount);
_afterRatio = averageCacheMissRatio(cacheOrdered);

Step 3: Apply the new vertex numbering #

The index buffer already changed inside optimizeVertexFetch. What is left is moving each vertex's own floats to its new slot, which is the same permutation oldToNew describes.

final int stride = sphere.layout.floatsPerVertex;
final Float32List vertices = Float32List(sphere.vertices.length);
for (var oldV = 0; oldV < sphere.vertexCount; oldV++) {
  final int newV = fetch.oldToNew[oldV];
  vertices.setRange(
    newV * stride,
    newV * stride + stride,
    sphere.vertices,
    oldV * stride,
  );
}
final MeshData reordered = MeshData(
  layout: sphere.layout,
  vertices: vertices,
  indices: fetch.indices,
);
_originalVertexCount = sphere.vertexCount;
_reorderedIndexCount = reordered.indexCount;

Step 4: Check the ratio improved #

The picture looks identical either way; only the memory access pattern behind it changed. The page checks that the miss ratio after reordering is no higher than before.

if (_reorderedIndexCount == 0 ||
    _originalVertexCount == 0 ||
    _afterRatio > _beforeRatio ||
    frame.drawCalls < 1) {
  throw StateError('reordering the mesh did not improve cache locality');
}