Linear Time Mesh Simplification with Reliable Error-Bounds

This paper proposes an incremental mesh reduction scheme that provides fine grained control over the approximation error while being linear in time in the number of vertices. We use the well--known half--edge collapse as our atomic decimation operation but we differ from previously reported methods in that we use a sequence of oriented bounding-boxes to track the decimation error instead of retaining the complete vertex information of the original model. This reduces storage costs and computation time while still providing a reliable upper bound for the deviation from the original data. We also propose different error accumulation strategies which makes the algorithm adaptable to different application scenarios