Surface Meshing by Transforming the Medial Scaffold

Ming-Ching Chang, Frederic F. Leymarie, and Benjamin B. Kimia
3DIM, 2007
mobius5k_seg_surf.png sapho_seg_surf_cb.png davidhead.png asian_dragon_bkt.png
hypersheet_seg_surf.png asian_dragon_bkt2.png
Click on the images to enlarge.
See the surface reconstruction process in video (AVI) for the hypersheet and mobius strip example.
Dataset are certesy of H. Hoppe, Stony Brook Geometric Surface Archieve, Stanford 3D Scanning Repository.

We propose an algorithm for surface reconstruction from unorganized points based on a view of the sampling process as a deformation from the original surface. In the course of this deformation the Medial Scaffold (MS) -- a graph representation of the 3D Medial Axis (MA) -- of the original surface undergoes abrupt topological changes (transitions) such that the MS of the unorganized point set is significantly different from that of the original surface. The algorithm seeks a sequence of transformations of the MS to invert this process. Specifically, some MS curves (junctions of 3 MA sheets) correspond to triplets of points on the surface and represent candidates for generating a (Delaunay) triangle to mesh that portion of the surface. We devise a greedy algorithm that iteratively transforms the MS by “removing” suitable candidate MS curves (gap transform) from a rank-ordered list sorted by a combination of properties of the MS curve and its neighborhood context. This approach is general and applicable to surfaces which are: non-closed (with boundaries), non-orientable, non-uniformly sampled, non-manifold (with self-intersections), non-smooth (with sharp features: seams, ridges). In addition, the method is comparable in speed and complexity to current popular Voronoi/Delaunay-based algorithms, and is applicable to very large datasets.

chang_mesh_cviu_draft
M.-C. Chang, F. F. Leymarie, and B. B. Kimia, “Surface Reconstruction from Point Clouds by Transforming the Medial Scaffold”, submitted to Computer Vision and Image Understanding (CVIU), Elsevier, April, 2008.
Paper (PDF), BibTex.
chang_mesh_3dim07 Ming-Ching Chang, Frederic F. Leymarie, and Benjamin B. Kimia, “Surface Reconstruction from Point Clouds by Transforming the Medial Scaffold”, the first oral presentation after the key note in IEEE 3-D Digital Imaging and Modeling (3DIM), Montreal, Canada, pp. 13-20, August 2007.
 Paper (PDF), Presentation (PPT), Poster (PPT), BibTex, Code.
Also download the Videos (hypersheet, mobius, rockerarm, bunny, sapho, david) and put into the same directory.