Control of polygonal mesh resolution for 3-D computer vision

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 multiresolution 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. We show results from many 3-D sensing domains including computed tomography, range imaging, and digital elevation map construction. (C) 1998 Academic Press.