Fast Mesh Decimation by Multiple-Choice Techniques

We present a new mesh decimation framework which is based on the probabilistic optimization technique of Multiple-Choice algorithms. While producing the same expected quality of the output meshes, the Multiple-Choice approach leads to a significant speed-up compared to the well-established standard framework for mesh decimation as a greedy optimization scheme. Moreover, Multiple-Choice decimation does not require a global priority queue data structure which reduces the memory overhead and simplifies the algorithmic structure. We explain why and how the Multiple- Choice optimization works well for the mesh decimation problem and give a detailed CPU profile analysis to explain where the speed-up comes from.