Function Representation of Solids Reconstructed from Scattered Surface Points and Contours

Vladimir V. Savchenko, Alexander A. Pasko, Oleg G. Okunev, Tosiyasu L. KuniiComputer Graphics Forum 1995 · DOI

TL;DR

This paper introduces a robust method for reconstructing 3D solids from scattered point clouds or cross-sections using "volume splines" based on Green’s functions. By defining the object as an implicit function inequality ($f(x,y,z) \ge 0$), the approach automatically handles complex topologies like branching and deep concavities without needing pre-defined connectivity or manual point-matching.

What Problem Does This Paper Address?

Reconstructing a smooth 3D surface from a "cloud" of unorganized points—often obtained from physical scans or mathematical simulations—is a classic challenge in computer graphics. Traditional methods often rely on polyhedral meshes, which struggle with complex topologies (like a tree branch or a hollowed-out shape) and require difficult combinatorial logic to "stitch" points together.

Furthermore, when reconstructing from 2D cross-sections (like medical MRI slices), researchers often face the "branching problem," where one contour in one slice splits into two in the next. The authors aim to provide a unified, global analytic description—a Function Representation (F-Rep)—that treats the solid as a continuous field rather than just a collection of triangles.

Methods

The core of the paper is a two-step "carrier solid" approach:

  1. The Carrier Solid: The authors start with a simple, known object called a "carrier," such as a sphere, defined by a function $f_c$. They calculate the values of this function at every scattered data point.
  2. Volume Spline Interpolation: They then construct a volume spline $U$ that interpolates these values. The spline is derived using Green’s functions, which are mathematical tools used to solve differential equations.
  3. The Final Solid: The reconstructed solid is defined by the algebraic difference between the spline and the carrier: $f(x,y,z) = U(x,y,z) - f_c(x,y,z)$. The surface of the object is simply where this function equals zero.

For cross-sectional data, the authors extend this by interpolating between 2D slices. They even propose a method for non-parallel sections using orientational matrices and quaternions to handle twisted or bent objects.

Because solving the resulting system of linear equations is computationally expensive ($O(N^3)$ complexity), the authors implemented a parallel version of the algorithm on a network of INMOS T800 transputers to maintain practical performance.

Datasets

The authors evaluated their method using several datasets:

  • Fobos Surface: 942 random points representing the surface of the Martian moon, Fobos.
  • Concave Contours: 2D point sets (59 and 67 points) used to test the reconstruction of "c-shaped" and multi-contour objects.
  • Synthetic Cube: 90 points used to demonstrate how deforming the underlying carrier solid affects the final reconstruction.
  • Medical-style Slices: 50 non-parallel planar sections used to reconstruct a twisted block.

Key Insights and Ideas

  • Implicit Topology: Unlike mesh-based methods, this approach doesn't care about the object's genus (number of holes) or branching. The math naturally produces the correct topology based on the point density.
  • The Carrier Trick: By using a carrier solid, the algorithm has a "global hint" of what the object should look like. Interestingly, the authors found that the accuracy of the final restoration didn't heavily depend on which carrier was chosen.
  • F-Rep Utility: The resulting function isn't just for visualization. Because it's a continuous field, it's trivial to perform set-theoretic operations (union, intersection), offsetting, and blending, which are essential for CAD and animation.
Figure 3: A branching structure reconstructed automatically from cross-sections.

Key Results

  • Accuracy: For the Fobos reconstruction (Figure 1), the error was kept under 3%. In a numerical test against a known function, the Root Mean Square (RMS) error was 0.02, which is comparable to more complex methods like triangular Gregory patches.
  • Parallel Efficiency: The parallel implementation showed excellent scaling. Solving a 400x400 system took 180 seconds on a single processor but dropped to just 32.7 seconds on six processors (approx. 92% efficiency).
  • Complex Geometry: The method successfully reconstructed highly concave 2D shapes (Figure 2) and complex 3D branching structures (Figure 3) that would typically require significant manual intervention in other frameworks.
Figure 4: Example of restoration from nonparallel cross sections

Limitations and Future Work

The primary drawback is the computational cost. The $O(N^3)$ scaling for solving the linear system limits the method to "moderate size" datasets (roughly a few thousand points). While parallelization helps, it doesn't solve the underlying scaling issue for massive point clouds.

The authors suggest that future work will focus on deforming the carrier solid to simulate plastic or elastic structures, such as human faces, by locally changing the carrier function. They also see potential in using this for tomographic data rendering and advanced CAD modifications.

Summary updated

Abstract

Abstract This paper presents a novel approach to the reconstruction of geometric models and surfaces from given sets of points using volume splines. It results in the representation of a solid by the inequality f(x,y,z) ≥ 0. The volume spline is based on use of the Green's function for interpolation of scalar function values of a chosen “carrier” solid. Our algorithm is capable of generating highly concave and branching objects automatically. The particular case where the surface is reconstructed from cross‐sections is discussed too. Potential applications of this algorithm are in tomography, image processing, animation and CAD for bodies with complex surfaces.
BibTeX
@article{savchenko1995function,
  author = {Vladimir V. Savchenko and Alexander A. Pasko and Oleg G. Okunev and Tosiyasu L. Kunii},
  title = {{Function Representation of Solids Reconstructed from Scattered Surface Points and Contours}},
  journal = {Computer Graphics Forum},
  year = {1995},
  doi = {10.1111/1467-8659.1440181},
}
Figure