Shape Reconstruction Using Radial-Basis Functions and Partition of Unity

Ohtake Y., Belyaev A., Seidel H.-P.,
“3D scattered data approximation with adaptive compactly supported radial basis functions”,
Shape Modeling International 2004, Genova, Italy, IEEE Computer Society, 2004, pp. 31-39.
Electronic version: PDF (623K)

In this paper, we develop an adaptive Radial-Basis Functions (RBF) fitting procedure for a high quality approximation of a set of points scattered over a piecewise smooth surface. We use compactly supported RBFs whose centers are randomly chosen from the points. The randomness is controlled by the point density and surface geometry. For each RBF, its support size is chosen adaptively according to surface geometry at a vicinity of the RBF center. All these lead to a noise-robust high quality approximation of the set. We also adapt our basic technique for for shape reconstruction from registered range scans by taking into account measurement confidences. Finally, an interesting link between our RBF fitting procedure and partition of unity approximations is established and discussed.

Ohtake Y., Belyaev A., Alexa M., Turk G., Seidel H.-P.,
“Multi-level partition of unity implicits”,
ACM Transactions on Graphics (SIGGRAPH 03 Proceedings), vol. 22, No. 3, 2003, pp. 463-470.
Electronic version: PDF (627K)

We present a shape representation, the multi-level partition of unity implicit surface, that allows us to construct surface models from very large sets of points. There are three key ingredients to our approach: 1) piecewise quadratic functions that capture the local shape of the surface, 2) weighting functions (the partitions of unity) that blend together these local shape functions, and 3) an octree subdivision method that adapts to variations in the complexity of the local shape. Our approach gives us considerable flexibility in the choice of local shape functions, and in particular we can accurately represent sharp features such as edges and corners by selecting appropriate shape functions. An error-controlled subdivision leads to an adaptive approximation whose time and memory consumption depends on the required accuracy. Due to the separation of local approximation and local blending, the representation is not global and can be created and evaluated rapidly. Because our surfaces are described using implicit functions, operations such as shape blending, offsets, deformations and CSG are simple to perform.

More detalis can be found at the Multi-level Partition of Unity Implicits page.

Ohtake Y., Belyaev A., Seidel H.-P.,
“A multi-scale approach to 3D scattered data interpolation with compactly supported basis functions”,
Shape Modeling International 2003, Seoul, Korea, IEEE Computer Society, 2003, pp. 153-161.
Electronic version: PDF (3.55 Mb)

In this paper, we propose a hierarchical approach to 3D scattered data interpolation with compactly supported basis functions. Our numerical experiments suggest that the approach integrates the best aspects of scattered data fitting with locally and globally supported basis functions. Employing locally supported functions leads to an efficient computational procedure, while a coarse-to-fine hierarchy makes our method insensitive to the density of scattered data and allows us to restore large parts of missed data. Given a point cloud distributed along a surface, we first use spatial down sampling to construct a coarse-to-fine hierarchy of point sets. Then we interpolate the sets starting from the coarsest level. We interpolate a point set of the hierarchy, as an offsetting of the interpolating function computed at the previous level. The figure above shows an original point set (the leftmost image) and its coarse-to-fine hierarchy of interpolated sets. According to our numerical experiments, the method is essentially faster than the state-of-art scattered data approximation with globally supported RBFs and much simpler to implement.

Reconstruction from Surface Points and Contours
Haniwa: Reconstruction Case Study