I’m writing another vertex cache optimization tool. Why on earth would I do that? The main reason is because most of the tools out there are designed exclusively for triangles, and in my case I need to handle arbitrary primitives. Not just lines, triangles or quads, but sets of indices with arbitrary number of elements: one-rings, winged-triangles, facets with all the neighboring vertices, etc.
The algorithm that I’m using has some similarities with Tom Forsyth’s Linear-Speed Vertex Cache Optimization. It’s a greedy algorithm, but it does not model the cache as a generic LRU, but instead uses the “real hardware cache”, and the scoring system that I use is quite different.
In order to support arbitrary primitives I use a complex connectivity structure in which there are multiple levels of connectivity. In level 0 there are primitives that share all its vertices. In level 1 there are primitives that share all its vertices minus one, and so on. So, for example, triangles have 3 connectivity levels: triangles that overlap, triangles that share an edge, and triangles that share only one vertex.
Each primitive is assigned a score according to how connected it is. That is, the more connections the higher the score. The connectivity structure and the scores are updated dynamically as triangles are processed. To select a triangle I take into account two things: how connected is the triangle to triangles in the cache, and its overall connectivity score.
I still haven’t done any comparisons. So, I don’t know how well it works, but I’m sure I’ll have to tweak the scores in order to obtain something that works well in all cases.
4 Comments
When I made a stripper long ago I found a pretty huge win from doing non-greedy lookaheads.
I was hoping that would not be necessary… updating my connectivity structure is not trivial. I build it o(n^2), so adding faces is o(n), but removing faces is a constant operation. Maybe I should do something smarter. Or maybe it doesn’t matter, I’m not really targeting high res meshes.
It’s not obvious to me when should I backtrack and how much. To be honest I haven’t read the literature in detail. Maybe I should start doing that before trying anything fancy.
Is that code in galaxy? I’ll have a look.
Yeah it’s in the Stripper, it does experimenting restarts.
With something like Tom’s linear thing you’d want to try adding not just the lowest-cost face but also some of the slightly higher cost faces.
You don’t need to update connectivity, you can just flag the faces, or even better use a time-counter type of flag.
May not be necessary unless you want to be the best ;)
That’s right. I’ve now decoupled the state from the connectivity structure. So, it should now be easy to try multiple experiments and pick the best.