posted on 1997-04-01, 00:00authored byAndrew E. Johnson, Martial Hebert
A common representation in 3-D computer vision is the polygonal surface mesh because meshes
can model objects of arbitrary shape and are easily constructed from sensed 3-D data. The resolution
of a surface mesh is the overall spacing between vertices that comprise the mesh. Because
sensed 3-D points are often unevenly distributed, the resolution of a surface mesh is often poorly
defined. We present an algorithm that transforms a mesh with an uneven spacing between vertices
into a mesh with a more even spacing between vertices, thus improving its definition of resolution.
In addition, we show how the algorithm can be used to control the resolution of surface meshes,
making them amenable to multi-resolution approaches in computer vision.
The structure of our algorithm is modeled on iterative mesh simplification algorithms common in
computer graphics; however, the individual steps in our algorithm are designed specifically to
control mesh resolution. An even spacing between vertices is generated by applying a sequence of
local edge operations that promote uniform edge lengths while preserving mesh shape. To account
for polyhedral objects, we introduce an accurate shape change measure that permits edge operations
along sharp creases. By locally bounding the total change in mesh shape, drastic changes in
global shape are prevented. The generality of our algorithm is demonstrated by its ability to control
the resolution of meshes with holes, boundaries, and both curved and polyhedral surfaces. We
show results from many 3-D sensing domains including computed tomography, range imaging,
and digital elevation map construction.