A Parallel Meshless Voronoi Method for Generalized SurfaceNets
- 1 July 2026
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Visualization and Computer Graphics
- Vol. 32 (7) , 7118-7130
Abstract
SurfaceNets is a powerful visualization technique typically used to contour non-continuous, discrete, volumetric scalar fields such as segmentation label maps. Label maps are ubiquitous to medical computing, biological studies, and materials characterization, used in applications ranging from anatomical atlas creation to nanotechnology analysis. Due to the uniform spacing of volume data, however, representing data with highly variable resolution is challenging. Consequently we have developed a generalized high-performance, parallel SurfaceNets algorithm that processes unorganized, labeled point clouds. Based on a scalable, meshless Voronoi approach, the algorithm independently processes each Voronoi hull in parallel using a hierarchical neighborhood point search metric. By employing novel topological constructs, the resulting meshless tessellation can be readily transformed into a connected conformal mesh, from which multiple, valid contour surfaces can be simultaneously extracted and smoothed. Additional contributions include a general API for locating points proximal to Voronoi hulls; the definition of topological coordinates used to detect and eliminate numerical degeneracies, merge coincident points, rapidly produce the dual Delaunay triangulation, and build smoothing stencils; and the construction of a Voronoi adjacency graph along with associated necessary conditions to ensure the generation of valid tessellations. Characterization of parallel performance is also quantified, including producing Voronoi and Delaunay tessellations of 128 million hulls and more than 750 million tetrahedra. A software implementation is available from the open source the Visualization Toolkit (VTK) system at vtk.org.Keywords
This publication has 31 references indexed in Scilit:
- An extension to Voro++ for multithreaded computation of Voronoi cellsComputer Physics Communications, 2023
- Spatial Tessellations2017
- PARAVT: Parallel Voronoi tessellation codeAstronomy and Computing, 2016
- A new parallel algorithm for constructing Voronoi tessellations from distributed input dataComputer Physics Communications, 2014
- Variational Anisotropic Surface Meshing with Voronoi Parallel Linear Enumeration2013
- Spatial Tessellations2000
- Improving Triangle Mesh Quality with SurfaceNets2000
- A nearly optimal deterministic parallel Voronoi diagram algorithmAlgorithmica, 1996
- Triangle: Engineering a 2D quality mesh generator and Delaunay triangulator1996
- Computational Geometry1985