Abstract:
The FanGrower algorithm proposed here segments a manifold triangle mesh into regions (called caps), which may each be closely approximated by a triangle-fan. Once the caps are formed, their rims, which form the inter-cap boundaries, are simplified, replacing each fan by its framea fan with the same apex but fewer triangles. The resulting collection of frames is an approximation of the original mesh with a guaranteed maximum error bound. As such, it may be viewed as a powerful extension of Kalvin and Taylors super-faces, which were restricted to nearly planar configurations and approximated by nearly planar fans. In contrast, our caps simplify to frames that need not be planar, but may contain convex or concave corners or saddle points. We propose a new and efficient solution for evaluating a tight bound on the deviation between a cap and its approximating fan and frame. We also introduce a new solution for computing the location of the apex of a fan as the point minimizing Garland and Heckberts quadric error for a set of planes defined by the vertices of the cap and their normals. We discuss several cap-growing approaches. Finally, we propose a compact representation of a triangle mesh from which one can easily extract the frames and execute selective refinements needed to reconstruct the original caps in portions of the mesh that are closer to the viewer, to a silhouette, or in an area of interest. Some frames are automatically upgraded to partly simplified fans to ensure a water-tight transition between frames and application-selected caps.

Keywords: Triangle-meshes, Simplification, Error-estimation, Multi-Resolution Modeling

You can access this technical report via: PDF, Postscript