Progressive Meshes in an Operational Rate-Distortion Sense with Application to Terrain Data

This paper presents an efficient simplification method for regular meshes obtained with a binary subdivision scheme. Our mesh connectivity is constrained with a quadtree data structure. We propose a quadtree built especially for this class of meshes having a constant-time traversal property. We introduce a rate-distortion (RD) framework to decimate the mesh and build a progressive representation for the model. We propose to achieve the RD-optimal solutions for our quadtree-restricted setting: to obtain the optimal solutions, we show how to find the vertex in the quadtree yielding the best RD trade-off and then perform optimizations at variable rate, where the rate is given by a cost function (for example the number of triangles). All previous methods are restricted to constant rate optimization only. We compare the optimal approach to its greedy counterpart. We give computationally optimal formulations for all our algorithms on the quadtree. We apply our technique to a large dataset of terrains and give extensive experimental results.