Many 3D datasets, especially scanned meshes, have far more points, edges and
triangles than are needed to represent their geometry. A central problem in
computational geometry is to be able to simplify excessively large
meshes: find a concise but geometrically accurate representation of such
meshes. The problem has numerous applications ranging from geometry
compression to reverse engineering.
The authors wish to answer the following questions:
Given a 3D surface, a target number of face elements, and an error
metric, what is the best geometric approximation of the object that one can
find with this face budget?
Given a distortion tolerance, what is the smallest polygonal mesh
approximant with a distortion less than the tolerance?
This problem is NP-hard so researchers shy away from it.
This paper casts the shape approximation problem as a variational geometric
partitioning problem (i.e. as the problem of finding a partition that
minimizes a given error metric). Using the concept of geometric proxies, the
algorithm
drives down the distortion error by repeatedly clustering faces into
best-fitting regions. This paper also presents a new metric based on normal
deviation.
Advantages of the presented shape approximation approach include:
Symmetries are quickly found
Anisotropy is automatically detected and exploited
Regions line up with the features
Although the simplified meshes do not have nicely shaped triangles with
smooth sampling gradation, efficiency is gained by respecting features and
symmetries
Disadvantages of the approach include:
Algorithm is slower than greedy methods
Algorithm only handles piecewise linear 2-manifolds, although extension
to point clouds is feasible
Qslim (cite garlandAndHeckbert98) outperforms algorithm if a given
number of triangles is sought, since algorithm is not error-driven and is
designed for polygonal outputs
Mesh not allowed to be non-manifold
Possible improvements to the algorithm include allowing the output mesh to be
non-manifold and locally extracting a dual mesh so that the output mesh will
have nicely shaped triangles in round regions and elongated triangles in
anisotropic regions. Other future work includes trying a Sobolev metric,
simplifying large scientific sequences using variatonal motion approximation
with a 4D (space + time) metric, geometry compression, higher-order proxies,
and the notion of shape shape complexity and how it relates to the choice of a
metric towards a sampling theory for shapes.