Source-linked AI summary
CVTSplat: Multi-view Reconstruction Using an Adaptive Centroidal Voronoi Tessellation
Briac Toussaint, Diego Thomas, Jean-Sébastien Franco, Edmond Boyer, Christian Theobalt
TL;DR
Adaptive Voronoi representations focus capacity near surfaces, but irregular cells make repeated tessellation reconstruction costly. CVTSplat uses surface-adaptive centroidal Voronoi cells and specializes construction and rendering around their regularity. It achieves geometric accuracy competitive with the state of the art on two object-level benchmarks, with training taking approximately 2.5 minutes on a single RTX 5090.
Problem
Adaptive representations concentrate capacity in relevant regions, but irregular spatial configurations can make neighborhood queries, geometric operations, and rendering more expensive.
Source: §1 · p. 1Method
CVTSplat modulates Voronoi cell size using the implicit surface, concentrating sites near the zero level set while keeping cells near-centroidal.
Source: §1 · p. 2Results
Geometric accuracy is competitive with the state of the art on two object-level benchmarks; training takes approximately 2.5 minutes on a single RTX 5090 using 4 GB of VRAM.
Source: §1 · p. 2, §8 · p. 13Takeaways & Limitations
Centroidal regularization enables specialized diagram construction, neighbor queries, centroid computation, rasterization, and mesh extraction in an efficient reconstruction pipeline.
Source: §8 · p. 13The approximate Voronoi construction is unsuitable for applications requiring exact adjacencies.
Source: §7 · p. 13
Abstract
from arXiv · showhide
Voronoi tessellations have recently emerged as an adaptive, space-partitioning discretization for shape and appearance reconstruction from multi-view images. However, the irregular cells they produce make the repeated reconstruction of the tessellation during optimization costly. We therefore explore adaptive centroidal Voronoi tessellations (CVTs), which extend standard CVTs with non-uniform cell sizes while preserving the regular, well-shaped cells that make them efficient to compute. In CVTSplat, cell size is modulated by the evolving signed distance field, concentrating sites near the zero level set while keeping cells nearly centroidal. This regularity lets us specialize the whole pipeline, with GPU algorithms for nearest-neighbor queries and approximate Voronoi construction, and a rasterizer tailored to small, nearly isotropic cells. Our Voronoi construction is 5 to 10 times faster than general-purpose alternatives in this regime. On DTU and BlendedMVS, CVTSplat reaches geometric accuracy competitive with the best Gaussian-splatting surface methods while training in about 2.5 minutes on a single GPU.
1 Introduction
CVTSplat uses an adaptive centroidal Voronoi representation to combine surface-focused capacity with regular cells, then specializes reconstruction operations around that structure.
1 Introduction
- Adaptive representations concentrate capacity in relevant regions, but irregular spatial configurations can make neighborhood queries, geometric operations, and rendering more expensive; standard CVTs tend toward uniform site distributions.Uniform discretizations allocate the same capacity throughout space even though accurate geometry and appearance are primarily required near the surface.Source: §1 · pp. 1–2
- CVTSplat modulates Voronoi cell size using the implicit surface, increasing site density near the zero level set while retaining a near-centroidal tessellation.This uses a standard Voronoi diagram rather than a power diagram, which would require an additional weight per site and incur higher construction cost.Source: §1 · p. 2
- Approximately 2.5 minutes on a single RTX 5090 with 4 GB of VRAM; geometric accuracy is competitive with state-of-the-art 3DGS-based methods on DTU [13] [63].The conclusion reports competitive geometric accuracy on two object-level reconstruction benchmarks.Source: §1 · p. 2
- Specialized GPU algorithms target approximate Voronoi construction, repeated K-nearest-neighbor queries, and Delaunay triangulation.The introduction reports substantial acceleration over general-purpose approaches [49].Source: §1 · p. 2
- The framework also introduces a rasterizer optimized for small, isotropic primitives.The paper describes directly rasterizing cells and exploiting their small, nearly isotropic shape.Source: §1 · p. 2
2 Related Work
The related work reviews adaptive spatial discretizations, explicit primitive-based representations, and GPU construction of Voronoi and Delaunay diagrams.
2 Related Work
- The review covers adaptive spatial discretizations, explicit primitive-based representations, and efficient GPU construction of 3D Voronoi and Delaunay diagrams.Source: §2 · p. 2
2.1 Adaptive Spatial Discretizations
- Grid-based encodings allocate computation sparsely around surfaces but follow predefined spatial structures, whereas unstructured discretizations allow element count and extent to adapt.The cited approaches include Voronoi or power cells and tetrahedral representations.Source: §2.1 · p. 2
2.2 Explicit Splatting Representations
- 3D Gaussian Splatting offers adaptive primitives and efficient rasterization, but coherent geometry recovery remains challenging [13] [63].Space-partitioning primitives such as tetrahedra and Voronoi cells provide a coherent decomposition, but maintaining it as sites move can add computational overhead.Source: §2.2 · p. 2
2.3 GPU Voronoi & Delaunay Diagrams Construction
- GPU Delaunay methods require repeated insertion, splitting, flipping, and repair; direct Voronoi clipping is sequential per cell and costlier for irregular cells.The cited passage notes that leaving cells unregularized can increase total construction cost.Source: §2.3 · pp. 2–3
3 Fast and Adaptive Spatial Data Structure
CVTSplat uses a near-centroidal Voronoi representation whose cell sizes adapt to the implicit surface. It combines this structure with approximate GPU methods for computing centroids, Voronoi cells, Delaunay connectivity, and nearest neighbors.
3 Fast and Adaptive Spatial Data Structure
- Voronoi cells serve as volumetric rendering primitives, while dual Delaunay connectivity supplies local neighborhoods for mesh extraction.Sites store signed-distance and appearance attributes and remain close to a centroidal configuration, supporting compact cells with few nearby neighbors.Source: §3 · p. 3
3.1 Adaptive Centroidal Voronoi Tessellation
- Shifting centroids along the SDF gradient yields smaller cells near the zero level set and larger cells farther away.With a=0.1 and b=0.001, the centroid shift is 10% of the cell radius; cell size is not explicitly imposed.Source: §3.1 · p. 4
3.2 Computation of the Centroids
- Casting 64 approximately uniform rays from each site estimates cell volume and centroid from distances to the nearest bisector planes.The volume and centroid are reevaluated every training iteration; the authors describe the quadrature as approximate and allow more direct computation when greater precision is needed.Source: §3.2 · p. 4
3.3 Voronoi Diagram Construction
- Voronoi cells are defined by active neighboring bisector planes, identified through ordered feasibility tests on candidate planes.The GPU tests the 32 nearest neighbors; missed neighbors can enlarge cells or create false adjacency, with errors confined to cells near the affected sites.Source: §3.3 · pp. 4–5
3.4 Delaunay Triangulation
- A binary neighbor-adjacency matrix supports enumeration of candidate Delaunay quadruplets, which are filtered by testing circumspheres against neighboring sites.The triangulation is not guaranteed exact when cells have missing clipping planes or the circumsphere check is numerically ambiguous; resulting mesh defects can include holes or non-manifold edges.Source: §3.4 · p. 5
3.5 Fast GPU KNN Search
- The repeated K=32 nearest-neighbor search uses a bounding-volume hierarchy and radius-based ball queries, then sorts gathered points by distance.Saved per-query radii can reduce repeated traversals as sites move slowly; warp-level traversal shares a stack and compacts points to shared memory for parallel sorting.Source: §3.5 · pp. 5–6
4 Differentiable Volume Rendering
The rendering pipeline combines smoothed, piecewise-linear SDFs with compact view-dependent appearance and a cell-based volume integral. Its rasterizer processes small cells in parallel while skipping occluded work.
4 Differentiable Volume Rendering
- Piecewise-linear SDFs and constant cell colors yield a closed-form volume-rendering solution over ray-cell segments, unlike neighborhood interpolation or tetrahedral-mesh alternatives.The SDF-to-density conversion is nonlinear, while the integral remains closed-form.Source: §4 · p. 6, §4.3 · p. 7
4.1 Attributes Smoothing
- SPH-inspired differentiable Gaussian smoothing stabilizes site attributes and supplies the SDF gradient; the resulting piecewise-linear field permits small inter-cell discontinuities.The SDF and its smoothed version are regularized alongside gradient smoothness and eikonal terms; site positions are controlled by the CVT loss.Source: §4.1 · pp. 6–7
4.2 Appearance Representation
- View-dependent cell color is decoded from per-site spatial features and angular features sampled from light-probe grids using incident and reflected directions.This separates view-independent and view-dependent appearance and uses fewer parameters than a distinct spherical-harmonic basis per primitive.Source: §4.2 · p. 7, Figure 7 · p. 7
4.3 Real-Time Rasterization
- Chunks of 32 cells are rasterized in parallel, while per-pixel flags let chunks skip work when accumulated transmittance bounds show they cannot contribute.Chunk outputs are blended front-to-back in a later pass; the method targets small primitives and mitigates poor utilization from rays intersecting different numbers of cells.Source: §4.3.1 · p. 8, Figure 9 · p. 8, Figure 8 · p. 8
- Threads test cell bounding spheres before more costly ray-cell intersections, reducing divergent work because rays usually intersect fewer than all 32 cells in a chunk.The passage notes this optimization is less beneficial for larger primitives, which more rays intersect at once.Source: §4.3.1 · p. 8
5 Optimization and Implementation
The optimization combines image, depth, and regularization losses with coarse-to-fine supervision. Training begins with a small site set, adds sites progressively, and includes color remapping for rendered images.
5.1 Color remapping
- Rendered colors are composited with a trainable environment map, tone-mapped to [0, 1], then adjusted by a trainable per-camera, per-channel color curve.The environment map uses an octahedral parameterization at resolution 1024^2.Source: §5.1 · pp. 8–9
5.2 Image Losses
- The image objective combines normalized L2, mask, structural, and multi-view losses, plus L1 smoothing on depth from the first implicit-surface intersection.Supervision uses four levels of detail, and per-primitive image-loss gradients are reweighted by projected size when image resolution changes.Source: §5.2 · p. 9
5.3 Initialization and Densification
- Training initializes 200K sites and progressively adds sites to reach 4M, placing new sites using rendered depth and spatial-feature maps.The Voronoi diagram is recomputed every iteration initially and every five iterations toward the end; training runs for 10K iterations.Source: §5.3 · p. 9
6 Experimental validation
CVTSplat achieves competitive geometric accuracy on DTU and BlendedMVS, with a roughly 2.5-minute DTU training time. Experiments also examine runtime trade-offs, component ablations, and the efficiency of its neighbor-query and Voronoi construction algorithms.
6.1 Multi-view Reconstruction
- On DTU, CVTSplat ties GGGS and BlobsToSpokes in geometric accuracy while training in approximately 2.5 minutes; on BlendedMVS, GGGS is slightly ahead quantitatively.PGSR fails to produce meshes in two BlendedMVS instances. Qualitatively, CVTSplat reproduces high-frequency DTU details and produces smoother BlendedMVS geometry than GGGS, though GGGS reconstructs some concavities better.Source: §6.1 · p. 9, Table 1 · p. 10, Figure 10 · p. 10
6.2 Training Speed Analysis on DTU
- 147s with the chunked rasterizer versus 280s with the single-thread-per-pixel baseline yields almost 2× end-to-end speedup with nearly the same Chamfer distance.Reducing site count or training steps lowers runtime with a small accuracy decrease; the model converges after 10K steps, with marginal improvement beyond 7.5K.Source: §6.2 · pp. 9–11, Table 3 · p. 11, Figure 12 · p. 11
6.3 Ablations on DTU
- Removing the multi-view or depth-smoothing loss strongly harms accuracy, while reflection probes aid smooth geometry in specular regions and the environment map helps compensate for mask inaccuracies.Linear radiance avoids a saturated-pixel failure on scan 65; reducing the biased-CVT parameter from 0.10 to 0.05 prevents sufficient cell shrinking and reduces accuracy. Other ablations include changes to planar versus nonplanar ZNCC, normal smoothing, and gradient modulation.Source: §6.3 · p. 11, Figure 13 · p. 12, Table 4 · p. 12
6.4 KNN Efficiency
- The KNN evaluation uses 32 neighbors on 4M-point DTU clouds; the search takes approximately 3× longer when its radius is unknown, though most sites can reuse the previous iteration’s radius.The gather-then-sort approach is reported as more efficient than heap-based approaches, especially when temporal consistency is leveraged.Source: §6.4 · p. 12, Table 5 · p. 12
6.5 Voronoi and Delaunay Efficiency
- On 4M-point DTU checkpoints, Voronoi construction is consistently 5× faster than MeshlessVoronoi and 10× faster than Paragram [49], and scales linearly.The reported comparison assumes the KNN search radius is known; RestrictedVoronoi retries for incomplete cells increase its runtime by about 1.5×.Source: §6.5 · p. 12, Table 6 · p. 12, Figure 14 · p. 12
- Generating only tetrahedra that cross the zero level set divides total mesh-extraction time by 3×.The zero-level-set surface is extracted as a triangle soup for real-time visualization during training, and duplicate vertices are merged on the CPU before outputting the final mesh.Source: §6.5 · p. 13, Table 7 · p. 13
7 Limitations and Future Work
The Voronoi construction is approximate and does not suit applications requiring exact adjacencies. The authors identify open-scene reconstruction as future work, with initialization and scalability obstacles.
Limitations
- Approximate Voronoi construction is unsuitable when exact adjacencies are required; larger-neighbor retries or double precision could improve completeness or robustness.The authors report a low proportion of incomplete cells for their chosen hyperparameters, while more aggressive adaptivity may require more neighbors at increased cost.Source: §7 · p. 13
Future Work
- Open-scene extension remains future work because naive sphere initialization and representing detail across large spatial extents may not scale well.The authors suggest monocular priors for initialization and image-content-based densification or more expressive primitives for scalability.Source: §7 · p. 13
8 Conclusion
CVTSplat combines adaptive Voronoi tessellations with differentiable implicit surface modeling. The conclusion attributes its efficiency to centroidal regularity, which enables specialized pipeline components, alongside competitive geometric accuracy on two object-level benchmarks.
8 Conclusion
- Centroidal regularity produces well-shaped cells and enables specialized pipeline components, supporting an efficient reconstruction pipeline with competitive accuracy on two object-level benchmarks.The conclusion names Voronoi construction, neighbor queries, centroid computation, rasterization, and mesh extraction as tailored components.Source: §8 · p. 13
A Overview; B Hyperparameters Scheduling
- The supplementary overview lists an optimization schedule and additional evaluations, derivations, and proofs; the schedule is detailed in Table 8, whose values are linearly interpolated during training.The listed supplementary evaluations include rendering speed, photometric accuracy, model size, mesh defects, cell moments, and incomplete-cell frequency.Source: A Overview · p. 15, B Hyperparameters Scheduling · p. 15, Table 8 · p. 15
C Mesh Defects Analysis
Extracted-mesh topological defects are infrequent relative to the number of triangles, and may potentially be addressed with topological post-processing.
C Mesh Defects Analysis
- Topological defects are infrequent relative to mesh triangles and could potentially be addressed by post-processing; missing adjacencies can produce small holes, while inconsistent tetrahedron selection or incomplete neighbor lists may cause non-manifold edges.Boundary edges are counted only within 95% of the bounding box because surfaces touching its walls can create legitimate boundaries.Source: C Mesh Defects Analysis · p. 15
D Cell Moments Estimation
The section evaluates ray-sampling approximations for cell moments and radius. With 64 rays, volume and centroid errors are below 1%, while radius error is larger.
D Cell Moments Estimation
- Table 9 reports average mesh-extraction defects by dataset.The supplied passage identifies the table's scope but gives no defect values.Source: Table 9 · p. 15
- Volume and centroid errors decrease as 1/N and have nearly overlapping curves; radius error decreases more slowly, approximately as 1/√N.Errors are measured relative to an 8192-ray reference; centroid error is normalized by the reference cell radius.Source: D Cell Moments Estimation · p. 15, Figure 15 · p. 15
- 0.79% volume error, 0.77% centroid error, and 5.65% radius error are obtained with 64 rays.The radius mainly defines an approximate rasterization bounding sphere; the authors note that its errors clip only the furthest cell corners.Source: D Cell Moments Estimation · p. 15
E Distribution of cells
The adaptive CVT concentrates smaller cells near the implicit surface, while the neighbor statistics support efficient approximate cell construction. The section also reports projected cell size and rendering speed.
E Distribution of cells
- The offset KNN strategy reduces the incomplete-cell rate from ≈0.1% to ≈0.0006% at no additional cost.Incomplete cells are typically away from the implicit surface and do not participate in volume rendering or mesh extraction.Source: E Distribution of cells · pp. 15–16
- ≈14.2 Voronoi neighbors occur per site on average, and ≈60% of sites have all neighbors among their first 16 nearest neighbors.About 0.1% of cells miss a Voronoi neighbor in the 32-KNN list with the base strategy; shifted ball queries reduce incomplete cells by a factor of 170, to ≈600 of 92M.Source: E Distribution of cells · p. 15, Figure 16 · p. 16
- Cell radius grows approximately affinely with SDF distance, with most cells located close to the implicit surface.At equal distances inside and outside the surface, the figure indicates comparable cell sizes.Source: E Distribution of cells · p. 16, Figure 17 · p. 16
F Rendering speed
- Table 10 reports average projected cell radius and rendering speed across scenes; the timings are measured on an RTX 5090.Images are rendered to an offscreen buffer, so displaying results would add a small overhead.Source: Table 10 · p. 16, F Rendering speed · pp. 16–17
E Distribution of cells
- Increasing CVT-loss parameter a improves zero-level-set mesh accuracy, but missing bisector planes rise sharply above a=0.1 with 32 Euclidean neighbors.At a=0.2, missing planes can cause cells to overlap visibly.Source: E Distribution of cells · p. 16, Figure 18 · p. 17
G Photometric Evaluation
Photometric evaluation finds image quality comparable to PGSR but slightly below GGGS, with a larger gap on BlendedMVS. The remaining sections describe model size and the multi-view loss pipeline, including its planar and nonplanar ZNCC variants.
G Photometric Evaluation
- Image quality is comparable to PGSR but slightly below GGGS, with a larger gap on BlendedMVS.The comparison measures fitting error on training views, not novel-view synthesis fidelity; qualitative renderings show high-frequency texture but miss some specularities compared with GGGS and PGSR.Source: G Photometric Evaluation · p. 17, Table 11 · p. 17, Figure 19 · p. 18
H Model size
- Despite using more primitives than GGGS, CVTSplat has a similar total parameter count on DTU and a lower count on BlendedMVS.Tables 12 and 13 report model size and the parameter-count breakdown, respectively.Source: H Model size · p. 17, Table 12 · p. 17, Table 13 · p. 17
I Details on the Multiview Loss
- Training pairs randomly selected nearby views in mini-batches of four, recording each ray's first SDF zero-crossing depth during rendering.The multi-view loss is inspired by PGSR.Source: I Details on the Multiview Loss · p. 18
I.1 Depth Computation
- For each cell, the method approximates an SDF zero-crossing along a ray, discards crossings outside the cell, and selects the minimum valid depth across intersected cells.If no crossing is found, the depth is set to +∞.Source: §I.1 · p. 18
I.2 Planar ZNCC
- Planar ZNCC checks mutual visibility and computes grayscale correlation over a 5 × 5 patch mapped between views using a local plane.The method skips invalid or occluded pixels and rejects normals more than 85° from the viewing ray.Source: §I.2 · p. 19
I.3 Nonplanar ZNCC
- Nonplanar ZNCC replaces plane-intersection depth with neighboring pixels' actual depths, avoiding a local-planarity assumption that can erase fine geometric detail.The implementation can share sampled neighboring-view pixel values across adjacent pixels.Source: §I.3 · p. 19
I.4 Loss
- The multi-view loss sums 1−ZNCC over valid pixels, using planar ZNCC for most training and switching to nonplanar ZNCC near the end to recover finer details.Depth maps and grayscale images follow the same coarse-to-fine schedule as the color losses.Source: §I.4 · p. 19
I.5 Backward Pass
- A CUDA kernel computes ZNCC forward and backward passes, producing the multi-view loss and depth gradients that propagate to SDF values through volume-rendering backpropagation.Source: §I.5 · pp. 19–20
J Derivations and Proofs
The derivations cover SDF-gradient computation, a closed-form volume-rendering integral, and a criterion for identifying Delaunay tetrahedra from Voronoi neighbors.
J.1 SDF Gradient Computation
- The SDF-gradient derivation treats each site's neighborhood, neighboring cell volumes, and kernel radius as constants during computation.The section also defines an intermediate weight sum and treats weights on neighboring smoothed SDF values as constants during backpropagation.Source: §J.1 · p. 20
J.2 Closed-form Volume Integral
- Assuming cells do not overlap, the ray's volume integral is split into per-cell integrals and blended into color using a closed-form transparency expression.The derivation uses the linear SDF approximation and the fact that each cell's color is constant within that cell.Source: §J.2 · p. 20
J.3 Delaunay Triangulation
- For sites in general position, a tetrahedron is Delaunay if any vertex has no Voronoi neighbor inside its circumsphere.The proof establishes that every vertex of a non-Delaunay tetrahedron has a Voronoi neighbor inside the circumsphere.Source: §J.3 · p. 21