Amal Dev Parakkat, Stefan OhrhallingerORCID iD, Elmar Eisemann, Pooran Memari
BallMerge: High‐quality Fast Surface Reconstruction via Voronoi Balls
Computer Graphics Forum, 43(2), 2024. [paper]

Information

Abstract

We introduce a Delaunay-based algorithm for reconstructing the underlying surface of a given set of unstructured points in 3D. The implementation is very simple, and it is designed to work in a parameter-free manner. The solution builds upon the fact that in the continuous case, a closed surface separates the set of maximal empty balls (medial balls) into an interior and exterior. Based on discrete input samples, our reconstructed surface consists of the interface between Voronoi balls, which approximate the interior and exterior medial balls. An initial set of Voronoi balls is iteratively processed, merging Voronoi-ball pairs if they fulfil an overlapping error criterion. Our complete open-source reconstruction pipeline performs up to two quick linear-time passes on the Delaunay complex to output the surface, making it an order of magnitude faster than the state of the art while being competitive in memory usage and often superior in quality. We propose two variants (local and global), which are carefully designed to target two different reconstruction scenarios for watertight surfaces from accurate or noisy samples, as well as real-world scanned data sets, exhibiting noise, outliers, and large areas of missing data. The results of the global variant are, by definition, watertight, suitable for numerical analysis and various applications (e.g., 3D printing). Compared to classical Delaunay-based reconstruction techniques, our method is highly stable and robust to noise and outliers, evidenced via various experiments, including on real-world data with challenges such as scan shadows, outliers, and noise, even without additional preprocessing.

Additional Files and Images

Additional images and videos

image
image

Additional files

paper
paper

Weblinks

BibTeX

@article{parakkat-2024-ballmerge,
  title =      "BallMerge: High‐quality Fast Surface Reconstruction via
               Voronoi Balls",
  author =     "Amal Dev Parakkat and Stefan Ohrhallinger and Elmar Eisemann
               and Pooran Memari",
  year =       "2024",
  abstract =   "We introduce a Delaunay-based algorithm for reconstructing
               the underlying surface of a given set of unstructured points
               in 3D. The implementation is very simple, and it is designed
               to work in a parameter-free manner. The solution builds upon
               the fact that in the continuous case, a closed surface
               separates the set of maximal empty balls (medial balls) into
               an interior and exterior. Based on discrete input samples,
               our reconstructed surface consists of the interface between
               Voronoi balls, which approximate the interior and exterior
               medial balls. An initial set of Voronoi balls is iteratively
               processed, merging Voronoi-ball pairs if they fulfil an
               overlapping error criterion. Our complete open-source
               reconstruction pipeline performs up to two quick linear-time
               passes on the Delaunay complex to output the surface, making
               it an order of magnitude faster than the state of the art
               while being competitive in memory usage and often superior
               in quality. We propose two variants (local and global),
               which are carefully designed to target two different
               reconstruction scenarios for watertight surfaces from
               accurate or noisy samples, as well as real-world scanned
               data sets, exhibiting noise, outliers, and large areas of
               missing data. The results of the global variant are, by
               definition, watertight, suitable for numerical analysis and
               various applications (e.g., 3D printing). Compared to
               classical Delaunay-based reconstruction techniques, our
               method is highly stable and robust to noise and outliers,
               evidenced via various experiments, including on real-world
               data with challenges such as scan shadows, outliers, and
               noise, even without additional preprocessing.",
  journal =    "Computer Graphics Forum",
  volume =     "43",
  number =     "2",
  issn =       "1467-8659",
  doi =        "10.1111/cgf.15019",
  pages =      "13",
  publisher =  "WILEY",
  keywords =   "surface reconstruction, voronoi, point clouds",
  URL =        "https://www.cg.tuwien.ac.at/research/publications/2024/parakkat-2024-ballmerge/",
}