Abstract  An adaptive surface triangulation algorithm for binary 3D image data is presented. The proposed method is robust and efficient and yields a high-quality surface-mesh description. The main idea of the algorithm is based on selecting a subset of the object voxel surface elements as the vertices of the triangulation and to obtain a discrete approximation of the Voronoi graph on the object surface to generate its dual, the surface Delaunay triangulation. The presented approach incorporates local object shape into the early stages of the algorithm, yielding an elegant method for obtaining shape-adaptive triangular meshes. One of the main advantages of the presented method over previous approaches is that no intermediate surface representation other than the trivial voxel representation provided by the input data is necessary. The method is presented in detail and tested on synthetic as well as real images.