Multi-level partition of unity implicits

Yutaka Ohtake, Alexander G. Belyaev, Marc Alexa, Greg Turk, Hans-Peter Seidel

TL;DR

This paper introduces Multi-level Partition of Unity Implicits (MPU), a novel shape representation that efficiently reconstructs complex 3D models from massive point clouds. By combining local quadratic shape functions with a hierarchical octree subdivision and a partition of unity blending scheme, MPU achieves accurate and adaptive surface modeling, even for objects with sharp features, outperforming existing methods in speed and memory efficiency.

What Problem Does This Paper Address?

Modern 3D scanning techniques can generate millions of points, posing a significant challenge for traditional surface reconstruction methods. Building accurate, faithful, and efficient 3D models from such large datasets is difficult. Existing implicit surface representations often struggle with sharp features, require global computations that don't scale well with data size, or are computationally expensive. The authors aim to develop a method that is fast, memory-efficient, handles large point sets, accurately represents sharp features, and allows for easy manipulation of the resulting models.

Methods

The core of the MPU approach lies in three key components:

  • Piecewise Quadratic Local Shape Functions: Instead of a single global function, MPU uses local quadratic functions to approximate the surface shape within small regions of space. This allows for flexibility in capturing local geometry.
  • Partition of Unity Blending: These local shape functions are blended together using a set of "partition of unity" weighting functions. These weights sum to one everywhere, ensuring a smooth global implicit function. This technique is borrowed from finite element methods.
  • Octree Subdivision: An adaptive octree structure is used to subdivide the bounding box of the point cloud. This subdivision is driven by an error metric, meaning cells are refined only where necessary to meet a desired accuracy, making the representation adaptive to the complexity of the shape.

The method also incorporates strategies for estimating these local shape functions, including fitting general 3D quadrics, bivariate quadratic polynomials, and specialized functions for edges and corners to accurately represent sharp features.

Datasets

The paper uses several publicly available datasets for evaluation:

  • Stanford Michelangelo's David (3D Model Repository)
  • Stanford 3D Scanning Repository (Lucy, bunny, dragon, Buddha)
  • Cyberware (Igea, fandisk, vase)
  • Max-Planck-Institut für Informatik (Head of Max Planck)
  • University of British Columbia (knot)

The authors do not introduce new benchmarks but demonstrate their method's performance on these existing, challenging datasets.

Key Insights and Ideas

  • Local Control for Global Representation: The combination of local shape functions and global blending via partition of unity is a powerful paradigm for handling large, complex datasets. It allows for detailed local modeling without the computational burden of global methods.
  • Adaptive Octree for Efficiency: The adaptive octree subdivision is crucial for efficiency. It ensures that computational resources are focused only on areas requiring high detail, leading to significant speedups and memory savings compared to uniform grids.
  • Explicit Sharp Feature Handling: The dedicated strategies for fitting edges and corners, rather than relying solely on general quadrics, are key to MPU's ability to accurately represent sharp geometric features, a common weakness in other implicit methods.
  • Implicit Function Advantages: By representing surfaces as implicit functions, MPU naturally supports operations like shape blending, offsetting, and CSG (Constructive Solid Geometry), which are difficult or impossible with explicit mesh representations.

Key Results

  • Speed and Memory Efficiency: The paper demonstrates that MPU is significantly faster (20-30 times) and more memory-efficient than state-of-the-art RBF-based methods for reconstructing large point clouds. For example, reconstructing the David model (4 million points) took approximately 10 minutes and 810 MB of RAM.
  • Accurate Sharp Feature Reconstruction: Visualizations show that MPU successfully reconstructs and renders sharp features like edges and corners, as seen in the eye reconstruction (Figure 6) and the fandisk model (Figure 7).
  • Robustness to Incomplete Data: The method shows robustness in reconstructing models from incomplete range scans (Figure 10), demonstrating its ability to "repair" missing data.
  • Flexibility: MPU supports both approximation and interpolation of point data, with the ability to adapt the approximation accuracy dynamically.

Limitations and Future Work

  • Sensitivity to Normals: The authors acknowledge that MPU, due to its local nature, is more sensitive to the quality of input normals compared to global RBF methods.
  • Approximation of Distance Function: While quadratic functions are used, the authors note that they are not optimal for approximating the distance function, which is a ruled surface with singularities.
  • Surfaces with Boundaries: Similar to other implicit function representations, MPU is not capable of representing surfaces with boundaries.

Future work suggested includes exploring richer libraries of local shape approximations for more complex sharp features, improving the distance function estimation, and developing out-of-core implementations to handle even larger datasets that exceed available RAM.

Summary updated

Abstract

We present a new 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.
BibTeX
@article{ohtake2003multi,
  author = {Yutaka Ohtake and Alexander G. Belyaev and Marc Alexa and Greg Turk and Hans-Peter Seidel},
  title = {{Multi-level partition of unity implicits}},
  journal = {ACM Trans. Graphics},
  year = {2003},
  doi = {10.1145/882262.882293},
}
Figure