Locally toleranced surface simplification

We present a technique for simplifying a triangulated surface. Simplifying consists of approximating the surface with another surface of lower triangle count. Our algorithm can preserve the volume of a solid to within machine accuracy; it favors the creation of near-equilateral triangles. We develop novel methods for reporting and representing a bound to the approximation error between a simplified surface and the original, and respecting a variable tolerance across the surface. A different positive error value is reported at each vertex. By linearly blending the error values in between vertices, we define a volume of space, called the error volume, as the union of balls of linearly varying radii. The error volume is built dynamically as the simplification progresses, on top of preexisting error volumes that it contains. We also build a tolerance volume to forbid simplification errors exceeding a local tolerance. The information necessary to compute error values is local to the star of a vertex; accordingly, the complexity of the algorithm is either linear or in O(n log n) in the original number of surface edges, depending on the variant. We extend the mechanisms of error and tolerance volumes to preserve during simplification scalar and vector attributes associated with surface vertices. Assuming a linear variation across triangles, error and tolerance volumes are defined in the same fashion as for positional error. For normals, a corrective term is applied to the error measured at the vertices to compensate for nonlinearities.