VoronoiNet: General Functional Approximators with Local Support

Francis Williams, Daniele Panozzo, Kwang Moo Yi, Andrea Tagliasacchi

Abstract

Voronoi diagrams are highly compact representations that are used in various Graphics applications. In this work, we show how to embed a differentiable version of it -- via a novel deep architecture -- into a generative deep network. By doing so, we achieve a highly compact latent embedding that is able to provide much more detailed reconstructions, both in 2D and 3D, for various shapes. In this tech report, we introduce our representation and present a set of preliminary results comparing it with recently proposed implicit occupancy networks.

Introduction

In 3D computer vision and graphics, the choice of shape representation is fundamental. Recently, "implicit" representations have gained prominence. Unlike explicit meshes or point clouds, implicit networks (such as Occupancy Networks or DeepSDF) learn a continuous scalar function where the surface is defined as a specific boundary (e.g., a zero-crossing).

However, standard implicit networks typically rely on Multi-Layer Perceptrons (MLPs), which suffer from global support. This means a change in a single network weight can unpredictably alter the entire shape. Furthermore, hybrid approaches like CvxNet, which represent shapes as intersections of convex spaces, often struggle to guarantee that these regions remain non-overlapping during inference. This lack of structural guarantee is problematic for downstream tasks like physical simulation. VoronoiNet addresses these issues by proposing a differentiable representation that ensures non-overlapping regions by design and features local support, where parameters only affect local geometry.

Methodology

The Voronoi Representation

The core of VoronoiNet is representing a shape as a piecewise constant function over a Voronoi diagram. The network's decoder outputs a set of $K$ points, known as Voronoi sites, in space. These points are partitioned: half are labeled as "inside" the shape, and the other half as "outside." The final shape is defined as the union of the Voronoi cells belonging to the "inside" points.

The VoronoiNet pipeline: An input image is encoded into a latent space, from which a decoder predicts Voronoi sites $p_k$. These sites define a Voronoi diagram that reconstructs the input shape.

Differentiability and Training

Standard Voronoi diagrams use an argmin operation to assign space to the nearest site, which is non-differentiable. To enable backpropagation, VoronoiNet utilizes a soft-argmin with a temperature parameter, creating a smooth, differentiable approximation. To guide the training of this ill-posed problem, the authors introduce three regularizers:

  1. Bounds Loss: Keeps Voronoi sites within a reasonable distance of the data.
  2. Signed Distance Loss: Pushes "inside" points into the ground-truth shape and "outside" points away from it.
  3. Centroidal Voronoi Loss: Encourages points to move toward the center of their respective cells, preventing clustering and ensuring a unique, optimal reconstruction.

Experimental Results

Parameter Efficiency

VoronoiNet demonstrates extreme parameter efficiency. When overfitting a simple 3D sphere, the model achieved reconstruction accuracy comparable to state-of-the-art implicit networks (OccNet, DeepSDF) while using three orders of magnitude fewer parameters.

In 2D auto-encoding tasks on the MNIST dataset, a Voronoi decoder with only 128 cells achieved a mean error of 57.99. This significantly outperformed an OccNet with a similar parameter count (83.80 error) and approached the performance of a much larger OccNet with 16,000 parameters (52.65 error).

Latent Space Properties

The latent space learned by VoronoiNet naturally organizes semantic classes. Because the representation is based on local support, interpolating between latent codes results in smooth topological transitions. As shown in the interpolation results, the network can seamlessly morph one digit into another by shifting the underlying Voronoi cells.

Latent space interpolation demonstrating smooth topological transitions between digits (e.g., 3 to 8 to 5) through the movement of Voronoi cells.

Conclusion and Future Work

VoronoiNet introduces a highly efficient, non-overlapping, and locally supported implicit representation. By construction, the generated convex regions cannot overlap, making the output ideal for physical simulations. While currently demonstrated on 2D digits and simple 3D shapes, future work will focus on scaling the method to complex 3D objects. This will involve developing specialized random sampling strategies to efficiently evaluate reconstruction losses in high-dimensional spaces and exploring the benefits of this representation for volumetric meshing.

Summary updated

Abstract

Voronoi diagrams are highly compact representations that are used in various Graphics applications. In this work, we show how to embed a differentiable version of it -- via a novel deep architecture -- into a generative deep network. By doing so, we achieve a highly compact latent embedding that is able to provide much more detailed reconstructions, both in 2D and 3D, for various shapes. In this tech report, we introduce our representation and present a set of preliminary results comparing it with recently proposed implicit occupancy networks.
BibTeX
@inproceedings{williams2020voronoinet,
  author = {Francis Williams and Daniele Panozzo and Kwang Moo Yi and Andrea Tagliasacchi},
  title = {{VoronoiNet: General Functional Approximators with Local Support}},
  booktitle = {Workshops @ CVPR},
  year = {2020},
  url = {https://openreview.net/forum?id=JlLQw0vWzaU},
}
Figure