Recent progress in acquiring shape from range data permits the acquisition of seamless million-polygon meshes from physical models. While dense polygon meshes are an ade-quate representation for some applications, many users prefer smooth surface representa-tions for reasons of compactness, control, manufacturability, or appearance. In this thesis, we present algorithms and an end-to-end software system for converting dense irregular polygon meshes of arbitrary topology into tensor product B-spline surface patches with ac-companying displacement maps. This choice of representation yields a coarse but efficient model suitable for interactive modification and animation and a fine but more expensive model suitable for rendering.
The first step in our process consists of interactively painting patch boundaries onto the polygonal surface. In many applications, the placement of patch boundaries is considered part of the creative process and is not amenable to automation. We present efficient tech-niques for representing, creating and editing surface curves on dense polygonal surfaces.
The second step in our process consists of finding a 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 pa-rameterization for the mesh section, which is initially unparameterized. Our parameteriza-tion algorithm is automatic, efficient, and robust, even for very complex polygonal surfaces. Prior algorithms have lacked one or more of these properties, making them unusable for dense meshes. Our parameterization strategy also provides the user a flexible method to design parameterizations - an ability that previous literature in surface approximation does not address.
The third and final step of our process consists of fitting a hybrid of B-spline surfaces and displacement maps to our gridded re-sampling. This fitting method reproduces with high fidelity the geometry of the original polygon mesh. The displacement map is an image representation of the error between the fitted B-spline surfaces and our spring grid. Since displacement maps are just images our hybrid 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. The resampling and fitting steps of our process are fast enough to surface a million polygon mesh in under 10 minutes - important for an interactive system.