Fast approximation of range images by triangular meshes generated through adaptive randomized sampling

This paper describes and evaluates an efficient technique that allows the fast generation of 3D triangular meshes from range images avoiding optimization procedures. Such a tool is advantageous in order to integrate range imagery into world models based on scattered representations. Furthermore, this technique can also be used as a fast preprocessing stage of registration, segmentation or recognition algorithms, owing to its abstraction capabilities that tend to eliminate redundant information. The proposed method has two stages: 1) the vertices of the mesh are computed through adaptive randomized sampling of the range image based on curvature estimations; and 2) the mesh is generated by triangulating the sampled vertices through an efficient 2½D Delaunay algorithm. The sampling process concentrates points in areas of large curvature and tends to preserve surface and orientation discontinuities. Multiresolution representations are supported in a natural way. The proposed technique is evaluated with several real range images that include both free-form and polyhedral surfaces