Fitting Smooth Surfaces to Dense Polygon Meshes

Venkat Krishnamurthy and Marc Levoy,
Proc. SIGGRAPH '96.


Recent progress in acquiring shape from range data permits the acquisition of seamless million-polygon meshes from physical models. In this paper, we present an algorithm and system for converting dense irregular polygon meshes of arbitrary topology into tensor product B-spline surface patches with accompanying displacement maps. This choice of representation yields a coarse but efficient model suitable for animation and a fine but more expensive model suitable for rendering.

The first step in our process consists of interactively painting patch boundaries over a rendering of the mesh. In many applications, interactive placement of patch boundaries is considered part of the creative process and is not amenable to automation. The next step is gridded resampling of each bounded section of the mesh. Our resampling algorithm lays a grid of springs across the polygon mesh, then iterates between relaxing this grid and subdividing it. This grid provides a parameterization for the mesh section, which is initially unparameterized. Finally, we fit a tensor product B-spline surface to the grid. We also output a displacement map for each mesh section, which represents the error between our fitted surface and the spring grid. These displacement maps are images; hence this representation facilitates the use of image processing operators for manipulating the geometric detail of an object. They are also compatible with modern photo-realistic rendering systems.

Our resampling and fitting steps are fast enough to surface a million polygon mesh in under 10 minutes - important for an interactive system.

Explanation of the figure above
The figure at the top of this page summarizes the paper. Moving from left to right in the image, we start with the raw, dense polygonal model (leftmost) which in this case came from 75 scans of an action figure. It has over 350,000 polygons. We first paint boundary lines on this model. This is shown in the figure that is second from the left. We use this information to automatically grid (see paper) each patch. Here is a close-up shot of an intermediate stage of this gridding. The third figure from the left shows a split view. The left half is a set of spline approximations for the relevant patches and some associated displacement maps. The right half shows the polygonal model. The rightmost figure shows a split view with the left half being the displacement mapped spline patches, the right half once again being the polygonal model.

Additional information:

Paper in acrobat format with medium resolution color figures
(3 MB uncompressed)

Paper in postscript with low resolution color figures
(679 KB compressed)

Paper in postscript with medium resolution color figures
(1.227 MB compressed)

Figures from the paper:

JPEG image of figure 5

JPEG image of figure 8

JPEG image of figure 11

JPEG image of figure 12

JPEG image of figure 13

The captions for these figures can be found in the paper. You can also read the captions here.

And finally, a more distinct image corresponding to Figure 11d.

The Technical Academy Award

After leaving Stanford, Venkat Krishnamurthy co-founded Paraform Technologies with Brian Kissel to commercial the ideas in his dissertation. In 2001, Paraform was awarded a Technical Achievement Award by the Academy of Motion Picture Arts and Sciences for developement of the "Paraform Digital Form Development Software". By then, his software had been used on a number of movies, including "Lake Placid", "The Haunting", "HollowMan", "End of Days", and "Minority Report". As of this writing (2003), Paraform has been bought by Metris International, and his software continues to be sold and used in the entertainment and manufacturing industries.

(This historical note written by Marc Levoy.)

This page © Copyright 1996 by Venkat Krishnamurthy
The paper © Copyright 1996 by ACM