Filling holes in complex surfaces using volumetric diffusion

James Davis, Stephen R. Marschner, Matt Garr, and Marc Levoy

Technical Report TR-2001-08
Computer Science Department
Stanford University

December, 2001

At left is a photograph of the head of Michelangelo's David. At right is a rendered 3D model of a section of his hair (corresponding to the square in the photograph). The section is 75mm wide on the statue, and the spacing between triangle vertices is 1.0mm. Although this surface was scanned dozens of times (from many different angles), occlusions prevented access to the deepest crevices. The hole highlighted in this rendering has a complex shape and multiple boundary components, i.e. islands floating in the hole. The largest boundary component contains 905 edges. (Hidden portions of this boundary are indicated with broken lines.)

Abstract

We address the problem of building watertight 3D models from surfaces that contain holes - for example, sets of range scans that observe most but not all of a surface. We specifically address situations in which the holes are too geometrically and topologically complex to fill using triangulation algorithms. Our solution begins by constructing a signed distance function, the zero set of which defines the surface. Initially, this function is defined only in the vicinity of observed surfaces. We then apply a diffusion process to extend this function through the volume until its zero set bridges whatever holes may be present. If additional information is available, such as known-empty regions of space inferred from the lines of sight to a 3D scanner, it can be incorporated into the diffusion process. Our algorithm is simple to implement, is guaranteed to produce manifold non-interpenetrating surfaces, and is efficient to run on large datasets because computation is limited to areas near holes.

Paper

Postscript with color figures	[PDF 2.8MB]
	Note: The is apparently a bug in some Acrobat Reader plug-ins for Netscape and Explorer that causes them to hang after page 3 while reading this PDF. To avoid this bug, download the PDF to your hard drive (by right-clicking on the link in Netscape or Explorer), then open it in Acrobat Reader. This seems to work reliably.
Accompanying video	[RealVideo (320 x 240, 100kbs) 2MB]
	[MPEG (320 x 240, 450kbs) 12MB]
	[MPEG (640 x 480, 1800kbs) 44MB]

Note: This paper is a revision of TR-2001-07. A further (and final) revision has been accepted for publication in the First International Symposium on 3D Data Processing, Visualization, and Transmission.