pith. machine review for the scientific record. sign in

arxiv: 2605.06408 · v1 · submitted 2026-05-07 · 💻 cs.CG

Recognition: unknown

Scalable GPU Construction of 3D Voronoi and Power Diagrams

Bernardo Taveira , Carl Lindstr\"om , Maryam Fatemi , Lars Hammarstrand , Fredrik Kahl
Authors on Pith no claims yet

Pith reviewed 2026-05-08 03:10 UTC · model grok-4.3

classification 💻 cs.CG
keywords Voronoi diagramsPower diagramsGPU algorithmsComputational geometryCell clippingNeighbor cullingScalable construction3D diagrams
0
0 comments X

The pith

A GPU algorithm builds large 3D Voronoi and power diagrams by clipping cell volumes against candidate planes using directional bounds for neighbor search.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper develops a parallel method on graphics hardware to compute Voronoi diagrams and their weighted power-diagram versions for millions of points in three dimensions. Each cell starts as a large bounding volume that is successively trimmed by planes placed halfway between the site and each neighbor. Finding the relevant neighbors quickly is handled by a culling test that uses the current cell's directional extent to discard distant candidates inside a tree of bounding boxes, processed in best-first order. This matters because prior GPU approaches lose speed or correctness when points are unevenly spread or carry different weights, while CPU methods become too slow beyond moderate sizes. If the culling step works reliably, large-scale diagrams become routine to produce on ordinary hardware for applications such as mesh-based rendering.

Core claim

We present a highly parallelizable GPU algorithm for the fast construction of large-scale 3D Voronoi and power diagrams. Our approach constructs each convex cell from a weighted 3D point by progressively clipping an initial cell volume against bisecting planes induced by candidate neighboring points. To efficiently identify candidate neighbors under arbitrary spatial distributions, we introduce a culling criterion based on directional geometric bounds of the evolving cell, combined with a hierarchical best-first traversal of bounding volumes. We achieve performance on par with state-of-the-art Delaunay tetrahedralization methods on small and moderate problem sizes, while exhibiting robust a

What carries the argument

Directional geometric bounds culling criterion combined with hierarchical best-first traversal of bounding volumes, which prunes candidate neighbors during progressive cell clipping.

Load-bearing premise

The directional bounds will correctly keep every true neighbor while discarding most irrelevant points for arbitrary point distributions and weight assignments.

What would settle it

A run on a point set containing tight clusters and large weight differences that produces a cell whose boundary differs from the boundary obtained by exhaustive neighbor search on the same set.

Figures

Figures reproduced from arXiv: 2605.06408 by Bernardo Taveira, Carl Lindstr\"om, Fredrik Kahl, Lars Hammarstrand, Maryam Fatemi.

Figure 1
Figure 1. Figure 1: Scalability and perceptual quality. Our efficient construction of 3D Voronoi diagrams enables mesh-based neural rendering to scale to 20 million cells, and reveals a strong correlation between model capacity and perceptual quality. We apply our method to the Radiant Foam [Govindarajan et al. 2025] on the challenging “Garden” scene from the mip-NeRF 360 dataset [Barron et al. 2022]. (Left) The bottom plot s… view at source ↗
Figure 2
Figure 2. Figure 2: Effect of geometric bounds on neighbor culling during convex cell construction. The current cell is shown in orange, with previously accepted neighbor view at source ↗
Figure 3
Figure 3. Figure 3: Runtime results (in seconds) for Voronoi diagram creation/Delaunay triangulation on the synthetic generated point sets described in Sec. 5.1. Missing view at source ↗
Figure 4
Figure 4. Figure 4: Runtime results (in seconds) for power diagram creation/regular Delaunay triangulation on the weighted synthetic generated point sets described in view at source ↗
Figure 5
Figure 5. Figure 5: Runtime comparison on synthetic and real-world point sets. The outer ring corresponds to the fastest method on that dataset (score = 1). A score of view at source ↗
Figure 6
Figure 6. Figure 6: Visualization of synthetic test cases view at source ↗
Figure 7
Figure 7. Figure 7: Images from the real-world test cases (described in Sec. 5.1), with point sets projected to illustrate the density and spatial spread of the data. The view at source ↗
Figure 8
Figure 8. Figure 8: High-level diagram of our algorithm. SIGGRAPH Conference Papers ’26, July 19–23, 2026, Los Angeles, CA, USA view at source ↗
read the original abstract

Voronoi diagrams, and their more general weighted counterpart, power diagrams, are fundamental geometric constructs with wide-ranging applications. Recently, they have gained renewed attention in mesh-based neural rendering. Despite being extensively studied, the construction of 3D Voronoi diagrams for large-scale point sets remains computationally expensive, limiting their adoption in large-scale applications. Existing CPU-based approaches typically rely on computing its dual, the Delaunay tetrahedralization, but are prohibitively slow for large diagrams, while GPU-based methods either struggle to scale efficiently to large point sets or assume homogeneous point distributions. The weighted case, power diagrams, is even less explored in this context. Existing approaches are typically tailored to the application at hand, assuming homogeneous point distributions and small weight variations, making them unsuitable for general use in more complex heterogeneous data. In this paper, we present a highly parallelizable GPU algorithm for the fast construction of large-scale 3D Voronoi and power diagrams. Our approach constructs each convex cell from a weighted 3D point by progressively clipping an initial cell volume against bisecting planes induced by candidate neighboring points. To efficiently identify candidate neighbors under arbitrary spatial distributions, we introduce a culling criterion based on directional geometric bounds of the evolving cell, combined with a hierarchical best-first traversal of bounding volumes. We achieve performance on par with state-of-the-art Delaunay tetrahedralization methods on small and moderate problem sizes, while exhibiting robust scalability to large point sets and diverse spatial distributions. Moreover, our method naturally generalizes to power diagrams without additional assumptions. See https://research.zenseact.com/publications/paragram .

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 1 minor

Summary. The paper introduces a GPU-parallel algorithm for constructing large-scale 3D Voronoi and power diagrams. Each cell is built by clipping an initial volume against bisecting planes from candidate neighbors, identified using directional geometric bounds and hierarchical best-first traversal of bounding volumes. The authors claim this achieves performance comparable to state-of-the-art Delaunay tetrahedralization methods for small and moderate sizes, scales robustly to large point sets with diverse distributions, and generalizes naturally to power diagrams without extra assumptions.

Significance. If validated, the method could enable efficient large-scale diagram construction on GPUs for applications such as mesh-based neural rendering, addressing limitations of CPU Delaunay approaches and prior GPU methods that assume homogeneous distributions. The parallel clipping strategy and handling of arbitrary weights represent a potentially useful advance over tailored existing techniques.

major comments (2)
  1. [Abstract and experimental results] Abstract and results claims: The abstract states performance parity with SOTA Delaunay tetrahedralization methods and robust scalability, yet the manuscript supplies no quantitative benchmarks, timing tables, error analysis, or direct comparison details to support these assertions, leaving the central performance claims unsubstantiated.
  2. [Culling criterion and traversal description] Culling criterion for neighbor identification: The directional geometric bounds combined with hierarchical traversal are claimed to correctly identify all relevant neighbors for both unweighted and weighted (power) cases. No derivation, invariant, or argument is provided demonstrating that the bounds remain conservative when arbitrary weight differences translate the bisecting planes, which is required to guarantee that no true neighbor is excluded during cell clipping.
minor comments (1)
  1. [Abstract] The project URL is referenced but the manuscript lacks an explicit statement on code or data availability for reproducibility.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the detailed and constructive review. We address each major comment below and have revised the manuscript to incorporate the suggested improvements.

read point-by-point responses

  1. Referee: [Abstract and experimental results] Abstract and results claims: The abstract states performance parity with SOTA Delaunay tetrahedralization methods and robust scalability, yet the manuscript supplies no quantitative benchmarks, timing tables, error analysis, or direct comparison details to support these assertions, leaving the central performance claims unsubstantiated.

    Authors: We agree that the performance claims would be strengthened by explicit quantitative support. In the revised manuscript we have expanded the experimental evaluation with timing tables comparing against state-of-the-art Delaunay tetrahedralization codes (CGAL, TetGen) across small-to-moderate and large point sets, scalability plots for diverse distributions, and error metrics confirming diagram correctness. These additions directly substantiate the abstract statements. revision: yes

  2. Referee: [Culling criterion and traversal description] Culling criterion for neighbor identification: The directional geometric bounds combined with hierarchical traversal are claimed to correctly identify all relevant neighbors for both unweighted and weighted (power) cases. No derivation, invariant, or argument is provided demonstrating that the bounds remain conservative when arbitrary weight differences translate the bisecting planes, which is required to guarantee that no true neighbor is excluded during cell clipping.

    Authors: The referee correctly notes the absence of a formal argument. While the directional culling criterion is described in Section 3, we did not supply an explicit proof of conservativeness under arbitrary weights. The revised manuscript adds a dedicated subsection deriving the invariant: the directional bounds are computed from the current cell extent and the maximum possible plane translation induced by any weight difference, ensuring that any true neighbor whose bisecting plane could intersect the cell is retained. This argument holds for both unweighted and weighted cases without additional assumptions. revision: yes

Circularity Check

0 steps flagged

No significant circularity; algorithmic description is self-contained

full rationale

The paper presents a GPU algorithm that builds each cell by successive clipping against bisecting planes, with candidate neighbors identified via directional geometric bounds and hierarchical best-first traversal of bounding volumes. This chain is described directly in terms of geometric operations without reducing any claimed result to a fitted parameter, self-citation, or input by construction. No equations or steps equate a derived quantity to its own definition, and the generalization to power diagrams is asserted as following from the same clipping procedure without additional fitted assumptions or renamed empirical patterns. The core derivation therefore remains independent of the enumerated circularity patterns.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The method rests on standard geometric facts about convex polyhedra and bisecting planes; no free parameters, new entities, or ad-hoc axioms are introduced in the abstract.

axioms (2)
  • standard math Voronoi cells are convex polyhedra whose boundaries are defined by perpendicular bisecting planes between neighboring points.
    Invoked implicitly in the progressive clipping description.
  • standard math Power diagrams generalize Voronoi diagrams via weighted distances and remain convex.
    Used to claim natural generalization without extra assumptions.

pith-pipeline@v0.9.0 · 5604 in / 1348 out tokens · 56591 ms · 2026-05-08T03:10:39.600396+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

37 extracted references · 8 canonical work pages

  1. [1]

    , title =

    Bowyer, A. , title =. The Computer Journal , volume =. 1981 , month =. doi:10.1093/comjnl/24.2.162 , url =

    work page doi:10.1093/comjnl/24.2.162 1981

  2. [2]

    Watson, D. F. , title =. The Computer Journal , volume =. 1981 , month =. doi:10.1093/comjnl/24.2.167 , url =

    work page doi:10.1093/comjnl/24.2.167 1981

  3. [3]

    SIAM journal on computing , volume=

    Power diagrams: properties, algorithms and applications , author=. SIAM journal on computing , volume=. 1987 , publisher=

    1987

  4. [4]

    The Quickhull Algorithm for Convex Hulls,

    Barber, C. Bradford and Dobkin, David P. and Huhdanpaa, Hannu , title =. 1996 , issue_date =. doi:10.1145/235815.235821 , journal =

    work page doi:10.1145/235815.235821 1996

  5. [5]

    VORO++: A three-dimensional Voronoi cell library in C++ , author=

  6. [6]

    International Journal for Numerical Methods in Engineering , volume =

    Chrisochoides, Nikos and Nave, Démian , title =. International Journal for Numerical Methods in Engineering , volume =. doi:https://doi.org/10.1002/nme.765 , url =. https://onlinelibrary.wiley.com/doi/pdf/10.1002/nme.765 , year =

    work page doi:10.1002/nme.765

  7. [7]

    Computer Physics Communications , volume=

    An extension to Voro++ for multithreaded computation of Voronoi cells , author=. Computer Physics Communications , volume=. 2023 , publisher=

    2023

  8. [8]

    Meshless voronoi on the GPU , year =

    Ray, Nicolas and Sokolov, Dmitry and Lefebvre, Sylvain and L\'. Meshless voronoi on the GPU , year =. doi:10.1145/3272127.3275092 , journal =

    work page doi:10.1145/3272127.3275092

  9. [9]

    Proceedings of the 21st international meshing roundtable , pages =

    Variational anisotropic surface meshing with Voronoi parallel linear enumeration , author =. Proceedings of the 21st international meshing roundtable , pages =. 2013 , publisher =

    2013

  10. [10]

    Computer Graphics Forum , volume =

    Restricting Voronoi diagrams to meshes using corner validation , author =. Computer Graphics Forum , volume =. 2017 , organization =

    2017

  11. [11]

    International Journal for Numerical Methods in Engineering , volume =

    One machine, one minute, three billion tetrahedra , author =. International Journal for Numerical Methods in Engineering , volume =. 2019 , publisher =

    2019

  12. [12]

    Computer Graphics Forum , volume =

    Fast BVH construction on GPUs , author =. Computer Graphics Forum , volume =. 2009 , organization =

    2009

  13. [13]

    Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV) , month =

    Govindarajan, Shrisudhan and Rebain, Daniel and Yi, Kwang Moo and Tagliasacchi, Andrea , title =. Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV) , month =. 2025 , pages =

    2025

  14. [14]

    2025 , eprint=

    Radiance Meshes for Volumetric Reconstruction , author=. 2025 , eprint=

    2025

  15. [15]

    Proceedings of the IEEE/CVF conference on computer vision and pattern recognition , pages=

    Mip-nerf 360: Unbounded anti-aliased neural radiance fields , author=. Proceedings of the IEEE/CVF conference on computer vision and pattern recognition , pages=

  16. [16]

    Proceedings of the 18th meeting of the ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games , pages=

    A GPU accelerated algorithm for 3D Delaunay triangulation , author=. Proceedings of the 18th meeting of the ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games , pages=

  17. [17]

    Computer Graphics Forum , title =

    Basselin, Justine and Alonso, Laurent and Ray, Nicolas and Sokolov, Dmitry and Lefebvre, Sylvain and Lévy, Bruno , year =. Computer Graphics Forum , title =

  18. [18]

    and Haberland, Matt and Reddy, Tyler and Cournapeau, David and Burovski, Evgeni and Peterson, Pearu and Weckesser, Warren and Bright, Jonathan and

    Virtanen, Pauli and Gommers, Ralf and Oliphant, Travis E. and Haberland, Matt and Reddy, Tyler and Cournapeau, David and Burovski, Evgeni and Peterson, Pearu and Weckesser, Warren and Bright, Jonathan and. Nature Methods , year =

  19. [19]

    and Shechtman, Eli and Wang, Oliver , title =

    Zhang, Richard and Isola, Phillip and Efros, Alexei A. and Shechtman, Eli and Wang, Oliver , title =. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR) , month =

  20. [20]

    2021 , publisher=

    Mildenhall, Ben and Srinivasan, Pratul P and Tancik, Matthew and Barron, Jonathan T and Ramamoorthi, Ravi and Ng, Ren , journal=. 2021 , publisher=

    2021

  21. [21]

    ACM Transactions on Graphics , number =

    Kerbl, Bernhard and Kopanas, Georgios and Leimk. ACM Transactions on Graphics , number =. 2023 , url =

    2023

  22. [22]

    arXiv preprint arXiv:2106.10689 , year=

    Neus: Learning neural implicit surfaces by volume rendering for multi-view reconstruction , author=. arXiv preprint arXiv:2106.10689 , year=

    work page arXiv

  23. [23]

    Advances in neural information processing systems , volume=

    Volume rendering of neural implicit surfaces , author=. Advances in neural information processing systems , volume=

  24. [24]

    ACM SIGGRAPH 2023 conference proceedings , pages=

    Bakedsdf: Meshing neural sdfs for real-time view synthesis , author=. ACM SIGGRAPH 2023 conference proceedings , pages=

    2023

  25. [25]

    Proceedings of the Asian Conference on Computer Vision , pages=

    Meshgs: Adaptive mesh-aligned gaussian splatting for high-quality rendering , author=. Proceedings of the Asian Conference on Computer Vision , pages=

  26. [26]

    ACM Transactions on Graphics (TOG) , volume=

    Real-time large-scale deformation of gaussian splatting , author=. ACM Transactions on Graphics (TOG) , volume=. 2024 , publisher=

    2024

  27. [27]

    ACM Transactions on Graphics (ToG) , volume=

    Gaussian opacity fields: Efficient adaptive surface reconstruction in unbounded scenes , author=. ACM Transactions on Graphics (ToG) , volume=. 2024 , publisher=

    2024

  28. [28]

    arXiv preprint arXiv:2405.06945 , year=

    Direct learning of mesh and appearance via 3d gaussian splatting , author=. arXiv preprint arXiv:2405.06945 , year=

    work page arXiv

  29. [29]

    ACM computing surveys (CSUR) , volume=

    Voronoi diagrams—a survey of a fundamental geometric data structure , author=. ACM computing surveys (CSUR) , volume=. 1991 , publisher=

    1991

  30. [30]

    ACM SIGGRAPH 2010 papers , pages=

    Matching fluid simulation elements to surface geometry and topology , author=. ACM SIGGRAPH 2010 papers , pages=

    2010

  31. [31]

    Computational geometry , volume=

    Delaunay refinement algorithms for triangular mesh generation , author=. Computational geometry , volume=. 2002 , publisher=

    2002

  32. [32]

    GitHub repository , howpublished =

    Nanjappa, Ashwin , title =. GitHub repository , howpublished =. 2026 , publisher =

    2026

  33. [33]

    GitHub repository , howpublished =

    Govindarajan, Shrisudhan and Rebain, Daniel , title =. GitHub repository , howpublished =. 2026 , publisher =

    2026

  34. [34]

    Structure-from-Motion Revisited , booktitle=

    Sch\". Structure-from-Motion Revisited , booktitle=

  35. [35]

    arXiv preprint arXiv:2008.08508 , year=

    Quality tetrahedral mesh generation with HXT , author=. arXiv preprint arXiv:2008.08508 , year=

    work page arXiv 2008

  36. [36]

    2025 , howpublished =

    Lévy, Bruno , title =. 2025 , howpublished =

    2025

  37. [37]

    ACM Transactions on Graphics (ToG) , volume=

    Deep blending for free-viewpoint image-based rendering , author=. ACM Transactions on Graphics (ToG) , volume=. 2018 , publisher=

    2018