PaperlayerView exact revision on arXiv

Source-linked AI summary

VoroDuce: Massively Parallel 3D Voronoi Simplification with Volume-Aware Edge Collapse

Felix Windisch, Lukas Radl, Thomas Köhler, Shrisudhan Govindarajan, Marcel Pur, Andrea Tagliasacchi, Markus Steinberger

arXiv:2610.21811v1cs.CG

TL;DR

Fine volumetric structures can require millions of Voronoi cells, while common simplification methods ignore their neighborhood structure. VoroDuce formalizes Voronoi reduction and uses Delaunay edge collapse with an approximate intersection-volume cost; its benchmarks report better preservation of structure and detail than baseline approaches.

  • Problem

    High-quality Voronoi models may require millions of primitives, and standard mesh or point-cloud simplification does not account for the neighboring-cell effects of Voronoi representations.

    Source: §1 · pp. 1–2

  • Method

    VoroDuce formalizes reduction using integrated squared error and greedily collapses edges in the dual Delaunay triangulation with a volume-aware cost, approximating intersections as truncated prismatoids for GPU parallelization.

    Source: §1 · p. 2, §4.2.1 · p. 5, §6 · p. 9

  • Results

    The benchmark reports that VoroDuce preserves overall structure and details more faithfully than baseline approaches.

    Source: §1 · p. 2

  • Takeaways & Limitations

    VoroDuce provides a GPU-accelerated reduction algorithm designed for 3D Voronoi geometry representations.

    Source: §6 · p. 9

    VoroDuce places each merged site at the collapsed edge's midpoint and does not optimize its position; tested position optimization did not significantly improve quality.

    Source: §6 · p. 9

Abstract

from arXiv · show

3D Voronoi diagrams provide a powerful mathematical framework for representing volumetric functions and geometry with applications to Materials Science, Biology, Simulation and Astrophysics. However, accurately resolving fine structures often requires millions of cells, imposing severe computational and memory constraints. Traditional mesh decimation or point cloud simplification techniques fail to account for the effects re-meshing has on neighbouring cells. In this work, we formalize the Voronoi reduction problem and propose a greedy edge-collapsing algorithm on the dual Delaunay tetrahedralisation that accounts for changes in the local geometry. Further, we demonstrate a novel volumetric error approximation technique that models convex cell intersections as truncated prismatoids, circumventing computationally prohibitive exact volume calculations and enabling massive GPU parallelization. Evaluations across Synthetic, Medicine and Material Science data demonstrate that VoroDuce decimates models with up to a million primitives, successfully compressing the representation while preserving the underlying data better than naive decimation approaches.

1. Introduction

Voronoi diagrams represent volumetric functions and geometry, but resolving fine structures can require millions of primitives. VoroDuce reduces Voronoi sites using a Delaunay-edge-collapse method and benchmarks its preservation of structure against baseline approaches.

1. Introduction

  • High-quality Voronoi models can require millions of primitives to resolve fine internal structures, limiting real-time rendering, interactive design, and memory-constrained use.Source: §1 · p. 1
  • Mesh decimation and point-cloud downsampling do not account for the neighborhood structure that defines 3D Voronoi representations.Mesh decimation relies on surface connectivity, which is usually absent or prohibitively complex for these models.Source: §1 · pp. 1–2
  • VoroDuce greedily collapses edges on the dual Delaunay triangulation, accounting for how site removal affects neighboring cells and topology while minimizing integrated squared error.The algorithm is designed to scale in time and memory to millions of input sites.Source: §1 · p. 2
  • The benchmark shows the algorithm preserves overall structure and details more faithfully than baseline approaches.The paper reports synthetic and real-world volumetric functions in its benchmark.Source: §1 · p. 2
  • The paper formalizes Voronoi reduction using integrated squared error and provides a GPU-accelerated implementation that scales to millions of primitives.Source: §1 · p. 2

2. Related Work

Prior geometry-reduction approaches target surface-sampling points or tetrahedral meshes, while Voronoi sites represent volumetric cells with neighborhood structure. Convex-cell intersection methods also face obstacles to GPU parallelization, motivating a scalable approximation.

2.1. Geometry Reduction

  • Point-cloud methods target surface samples or uniform density and ignore Voronoi neighborhoods; Gaussian Mixture reduction lacks the diagram's topology.Source: §2.1 · p. 2
  • Tetrahedral-mesh collapse can lose the Delaunay property, while adaptive thinning targets piecewise-linear interpolation and was developed primarily for bivariate data.Source: §2.1 · p. 2

2.2. Convex Cell Intersection

  • Exact convex-cell intersection methods use sequential operations that hinder GPU parallelization, while Monte Carlo offers little performance benefit for 3D cells and struggles with thin intersections.Source: §2.2 · p. 2

3. Preliminaries

The paper describes Voronoi cells and their Delaunay dual, then formalizes reduction as constructing a smaller sample set that minimizes integrated squared error over a domain.

3.1. Voronoi Diagrams and Delaunay Triangulations

  • A Voronoi diagram partitions space into cells around seed points; each cell contains points at least as close to its seed as to any other.Source: §3.1 · p. 2
  • Voronoi cells are convex polyhedra, and their Delaunay dual connects two sites when their cells share a face.Source: §3.1 · p. 2
  • The analysis assumes general position—no four sites coplanar and no five co-spherical—so cells intersect exactly when their sites share a Delaunay edge.Source: §3.1 · p. 3

3.2. The Voronoi Reduction Problem

  • Voronoi reduction is formalized as choosing fewer than N samples to minimize integrated squared error between the original and reduced piecewise-constant nearest-neighbor functions.The error sums squared value differences over intersections of original and reduced cells, weighted by overlap volume.Source: §3.2 · p. 3
  • The reduction objective is illustrated in 2D as reducing the number of sites representing an image while minimizing mean squared error.Source: Figure 2 · p. 3

4. Method

The method reduces Voronoi sites through greedy edge collapses in the dual Delaunay triangulation, selecting merges by their integrated squared error. Its cost computation tracks local cell-volume changes and approximates intersection volumes with truncated prismatoids.

4.1. Iterative Cell Merging

  • Greedy edge collapses merge neighboring Voronoi cells, with candidate pairs ranked by the integrated squared error their merge would introduce.The algorithm batches ⌊β · |S|⌋ collapses before recomputing Delaunay edges and costs, then updates costs for affected edges.Source: §4.1 · pp. 3–4

4.2. Computing the cost

  • A collapse changes only the function over the union of the merged and original cells, so its cost accounts for gained and lost neighbor volumes as well as changes to the merged cells.Cases where the merged cell intersects a non-neighbor are treated as zero because they are infrequent, have negligible error effect, and are expensive to handle.Source: §4.2 · p. 4

4.2.1. Computing Intersection Volumes

  • Convex-cell intersections dominate runtime, reaching 92% and around 2,000 amortized volume intersections per edge collapse, motivating approximate volume computation.Source: §4.2.1 · p. 5
  • A truncated prismatoid is the convex hull of two convex polygons with nonintersecting interiors, whose volume can be computed efficiently by tetrahedral decomposition.The polygons need not be parallel; the definition also includes wedges and pyramids.Source: §4.2.1 · p. 5

Merges with flips

Delaunay flips can change the topology around a neighboring cell during a merge, creating several intersection-volume cases. The method approximates these cases with different geometric constructions and biases.

Merges with flips

  • When a flip pinches off a vertex, the implementation approximates the resulting polytope with a truncated prismatoid, underestimating its volume by omitting small caps.Source: Merges with flips · p. 6
  • For new-neighbor walls, the method ignores those walls and computes the new face from the tunnel alone, overestimating gained volume; this bias opposes vertex loss.Source: Merges with flips · p. 6
  • When the tunnel closes before reaching the new bisector, the method approximates the closed region with a pyramid whose volume may over- or underestimate the true intersection.Its base is the original face, and its apex lies along the inward normal at the distance where the ray first exits the tunnel.Source: Merges with flips · p. 6

Neighbours of both merged cells

The method handles cells neighboring both merged cells by splitting them along the sites’ bisector, and estimates intersection volumes with special cases for Delaunay flips. Rest volumes avoid directly computing the difficult intersection involving the merged cell.

Neighbours of both merged cells

  • Shared neighbors are split along the bisector between the merged sites, producing two disjoint cells whose intersections use the standard approximation procedure.This handles the case where a neighbor belongs to both merged cells.Source: Neighbours of both merged cells · p. 6

4.3. Merged Cell Intersections

  • The polygon-based approximation poorly captures the merged cell, so its intersection volume is recovered by subtracting neighboring intersections from the original cell volume.This rest-volume approach bypasses direct computation of the more complex merged-cell intersection.Source: §4.3 · pp. 6–7
  • A pinch vertex makes the truncated-prismatoid approximation underestimate intersection volume, while an empty Fnew after an edge flip is approximated with a pyramid.The pyramid may over- or underestimate the true volume, depending on the bounding bisectors.Source: §4.3 · p. 7
  • GPU work is batched across independent neighbor cells and face pairs, with tunnels padded to the tested maximum degree of 11 to reduce divergence.Sorting face pairs by degree allows volume calculations to be batched by equal degree.Source: §4.3 · p. 7

5. Evaluation

The evaluation compares VoroDuce with point-cloud, mesh, clustering, and heuristic baselines across synthetic, scan, and materials datasets. Results favor or match VoroDuce in nearly all cases, and the fast computation improves scalability.

5.1. Compared methods

  • Baselines span volume and neighbor rankings, FPS, grid sampling, Cignoni et al.’s QN mesh method, Ward edge collapse, and fast and exact VoroDuce.The comparisons are intended to test point-cloud, volumetric-mesh, clustering, and general-heuristic alternatives.Source: §5.1 · pp. 7–8

5.2. Data

  • The evaluation combines 17 synthetic datasets with 100,000 sites each, volumetric scans downsampled to 250,000 sites, and five simulated polycrystal datasets.Scan sampling strategies include uniform, importance, gradient, and jittered-grid sampling; polycrystal cell values represent stress.Source: §5.2 · p. 8

5.3. Monte Carlo ISE

  • Monte Carlo estimates the reduced set’s ISE without bias using 5·10^6 uniform samples, reports normalized MSE, and interpolates AUC from measurements every 5%.The exact ISE is computationally infeasible for scenes with hundreds of thousands of cells.Source: §5.3 · pp. 8–9

5.4. Results

  • VoroDuce matches or outperforms baselines in almost all cases; its slices preserve fine details and overall structure more faithfully.Exact volume computation improves average results only slightly over the fast approximation, with its largest impact on Microstructure.Source: §5.4 · p. 9, Figure 9 · p. 9

5.5. Scalability

  • On MRBrain, fast cost computation is roughly 10× faster than exact computation and enables up to 5× faster overall reduction, with a minor error increase.Runtimes scale roughly linearly with input cell size; higher β can accelerate both variants by up to 5× with minor quality impact.Source: §5.5 · p. 9

6. Discussion and Outlook

VoroDuce combines GPU-accelerated, volume-aware reduction with approximations that trade exact geometric precision for scalability. The discussion reports strong structural fidelity while noting limits in site placement and input assumptions.

6. Discussion and Outlook

  • VoroDuce is a GPU-accelerated, volume-aware reduction algorithm that preserves model structures and details more faithfully than traditional mesh or point-cloud downsampling.The method treats decimation as a spatially aware optimization problem.Source: §6 · p. 9
  • Truncated-prismatoid intersection approximations introduce localized errors in edge cases but enable GPU parallelization without observed macroscopic structural failures.The discussion identifies faces with disparate vertex counts and pyramid approximations as examples of edge cases.Source: §6 · p. 9
  • The merged site is always placed at the collapsed edge’s midpoint; experiments optimizing its position found no statistically significant quality improvement.The method does not optimize the new site position as quadric-based surface simplification does.Source: §6 · p. 9
  • The benchmark table covers scans reduced from 250,000 to 37,500 cells, synthetic data from 100,000 to 10,000, and polycrystals from 100,000 to 15,000.It reports Final MSE and Trajectory AUC Mean MSE for each method.Source: Table 2 · p. 10
  • The algorithm assumes sites are in general position; near-degenerate inputs can destabilize triangulations, and the greedy method has no optimality guarantee.Jittered regular lattices are given as an example of near-degenerate inputs.Source: §6 · p. 10
  • Future directions include other distance metrics, further GPU kernel and memory optimization, and applying Voronoi reduction to finite-volume simulations.The cited application areas include astronomy and fluid dynamics.Source: §6 · p. 10

A. Example Illustrations

  • A single Delaunay edge collapse can cause several edge flips, which introduce special cases into the volume approximation.The appendix illustrates flips and their approximation effects with an example merge.Source: Figure 10 · p. 13, A. Example Illustrations · p. 13

B.1. Synthetic Dataset

  • The synthetic benchmark generates seed coordinates from spatial distributions, then assigns cell values by analytically evaluating scalar fields at those seeds.The dataset details describe five spatial patterns and eight functional categories.Source: §B.1 · p. 13

B.2. Material Science Dataset

The materials-science data comprise simulated Voronoi polycrystals with stress assigned to cells. The benchmark includes multiple crystal structures and evaluates stress across specified slip systems.

B.2. Material Science Dataset

  • Each cell’s value is the maximum resolved shear stress across its active slip systems.Source: §B.2 · p. 13
  • Three datasets represent equiaxed FCC, cold-rolled sheet, and additive columnar polycrystals, with shear stress evaluated across 12 primary octahedral slip systems.The models are generated as Voronoi structures.Source: §B.2 · pp. 13–14
  • The dual-phase steel dataset evaluates shear stress across three basal and three prismatic slip systems.The supplied generation command specifies a 100,000-cell model.Source: §B.2 · p. 14
  • The hexagonal close-packed α-titanium dataset applies Hall–Petch grain-size scaling: ×1.35 for fine grains below median volume and ×0.85 for coarse grains.The dataset is generated as a 100,000-cell Voronoi model.Source: §B.2 · p. 14

C. Ablation of collapse batch size β

The collapse batch size β trades reduction speed against quality, with performance generally robust through β = 1 but degrading above 1. Moderate batches can regularize merges, and larger batches especially benefit the fast variant.

C. Ablation of collapse batch size β

  • Up to β = 1, quality is generally insensitive, while β > 1 degrades it quickly; β = 0.1–0.5 gives the best quality and up to 5× speedup over β = 0.01 with minimal quality change.Because each cell can merge only once per block, moderate β prevents overly aggressive merging of a small set of cells; excessive β can leave good candidates unmerged.Source: C. Ablation of collapse batch size β · p. 14
  • The batch-size effect is not simply a quality–performance trade-off: moderate β acts as a regularizer, whereas excessive β can prevent good candidates from being merged often enough.Source: C. Ablation of collapse batch size β · p. 14
  • Larger batch sizes speed both cost variants, with the fast variant reaching up to 8× overall speedup over exact costs.Source: C. Ablation of collapse batch size β · p. 14

D. Implementation Details

The implementation uses GPU-oriented procedures for merging cells and computing volumes. Across evaluated datasets, the fast variant tracks the exact variant closely, and VoroDuce usually achieves the best accuracy.

D. Implementation Details

  • CUDA kernels run in Warp, GPU Delaunay triangulation uses local retriangulation with full-rebuild fallback, and infinite hull cells are excluded from cost computation.Source: D. Implementation Details · p. 15

D.1. Merging Cells

  • The merged site is placed at the collapsed-edge midpoint, and its function value is the mean over the merged cell; optimizing site position brought no significant quality gain and sometimes regressed.Source: §D.1 · p. 15

D.2. Computing Cell Volumes From Delaunay Tetrahedra

  • Cell volumes are computed by summing Delaunay tetrahedron volumes and redistributing each tetrahedron’s volume to its four vertex cells.Source: §D.2 · p. 16

D.3. Computing Prismatoid Volume

  • Truncated prismatoids are padded to equal face sizes, triangulated into tetrahedra, and summed in parallel; shared patterns eliminate warp divergence.Source: §D.3 · p. 16, Figure 13 · p. 16

E. ISE Curves

  • Across the plotted reductions, Ours (Fast) closely matches Ours (Exact), and VoroDuce has the best accuracy with few exceptions.Source: E. ISE Curves · p. 16

F. Empirical Frequency of Delaunay flips

The flip analysis measures how often approximation cases arise and how much volume they involve. The accompanying proofs characterize the relevant regions and state conditions for exactness without flips.

F. Empirical Frequency of Delaunay flips

F.1. Proofs

  • The stated exactness result without flips assumes general position and bounded original and merged cells.Source: §F.1 · p. 16
  • When the original and new Voronoi faces intersect, the proof identifies the gained and lost regions as truncated prismatoids.Source: §F.1 · p. 18
Loading 2610.21811v1…