# Theoretical and Empirical Analysis of a Fast Algorithm for Extracting Polygons from Signed Distance Bounds

arXiv: https://arxiv.org/abs/2111.05778 · HTML: https://mlsanity.com/paper/2111.05778/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 12 of its 29 references that are in the map.
- First posted on arXiv 10 Nov 2021.

## Builds on (most cited first, 12 of 12)

- [Denoising Diffusion Probabilistic Models](https://mlsanity.com/paper/2006.11239/) (2020)
- [Deep Unsupervised Learning using Nonequilibrium Thermodynamics](https://mlsanity.com/paper/1503.03585/) (2015)
- [DeepSDF: Learning Continuous Signed Distance Functions for Shape Representation](https://mlsanity.com/paper/1901.05103/) (2019)
- [Learning Implicit Fields for Generative Shape Modeling](https://mlsanity.com/paper/1812.02822/) (2018)
- [Neural Geometric Level of Detail: Real-time Rendering with Implicit 3D Shapes](https://mlsanity.com/paper/2101.10994/) (2021)
- [Thingi10K: A Dataset of 10,000 3D-Printing Models](https://mlsanity.com/paper/1605.04797/) (2016)
- [A-SDF: Learning Disentangled Signed Distance Functions for Articulated Shape Representation](https://mlsanity.com/paper/2104.07645/) (2021)
- [Supervised Fitting of Geometric Primitives to 3D Point Clouds](https://mlsanity.com/paper/1811.08988/) (2018)
- [DualSDF: Semantic Shape Manipulation using a Two-Level Representation](https://mlsanity.com/paper/2004.02869/) (2020)
- [Geometry-Consistent Neural Shape Representation with Implicit Displacement Fields](https://mlsanity.com/paper/2106.05187/) (2021)
- [On the Effectiveness of Weight-Encoded Neural Implicit 3D Shapes](https://mlsanity.com/paper/2009.09808/) (2020)
- [3D Shapes Local Geometry Codes Learning with SDF](https://mlsanity.com/paper/2108.08593/) (2021)

## Abstract (arXiv)

Recently there has been renewed interest in signed distance bound representations due to their unique properties for 3D shape modelling. This is especially the case for deep learning-based bounds. However, it is beneficial to work with polygons in most computer-graphics applications. Thus, in this paper we introduce and investigate an asymptotically fast method for transforming signed distance bounds into polygon meshes. This is achieved by combining the principles of sphere tracing (or ray marching) with traditional polygonization techniques, such as Marching Cubes. We provide theoretical and experimental evidence that this approach is of the O(N2log N) computational complexity for a polygonization grid with N3 cells. The algorithm is tested on both a set of primitive shapes as well as signed distance bounds generated from point clouds by machine learning (and represented as neural networks). Given its speed, implementation simplicity and portability, we argue that it could prove useful during the modelling stage as well as in shape compression for storage. The code is available here: https://github.com/nenadmarkus/gridhopping