## 2 Basic Definitions and Related Work  
In our case, the polygonization volume is an axis-aligned cube centered at the origin. The shape represented by its SDB is withing this cube. This cube is partitioned into a rectangular grid with \(N^{3}\) cells by subdividing each of its sides into \(N\) intervals of equal size. If we assume we are not dealing with fractals, only \(O(N^{2})\) cells asymptotically contain the surface of our shape. Thus, the only triangles that need to be computed are passing through these cells. This puts the lower bound on the complexity of the triangularization algorithm. However, the challenge is to isolate just these \(O(N^{2})\) cells. The simplest solution, which leads to \(O(N^{3})\) complexity, is to check each of the \(N^{3}\) cells. This process is called **enumeration**[11] (Section 4.2.2 in the book), and for some purposes it is too slow. The original applications of the marching cubes algorithm [10] applied this slow approach. However, these applications usually dealt with real-world data obtained through measurements (e.g., CT scans), not well defined mathematical objects. An improvement to this basic enumeration scheme is known as **continuation**[11] (Section 4.2.3 in the book). The idea of this approach is quite simple. Starting from a single \"seed\" cell that intersects the surface of the shape, new cells are propagated across the surface until the entire surface is enclosed. The complexity of this algorithm is \(O(N^{2})\) because only the surface cells are analyzed. Thus, we also call it surface tracing/crawling. Its main disadvantage is that it produces a single mesh component for each seed cell, i.e., we need a separate seed cell to polygonize all disjoint shape components. This can be problematic in practice. Another issue with this approach is caused by the limited numerical precision of digital computers when representing seed cell parameters (e.g., their center point coordinates)--this complicates the positioning of the seed cell. Of course, these problems only show up for high grid resolutions, i.e., large values of \(N\). We also mention the unpublished work of [PERSON] [12; 13]. This method aims at similar goals (transform an SDB into a triangle mesh) but uses a different subdivision strategy over the grid (recursive partitioning instead of sphere tracing), and no detailed complexity analysis was performed. It is not a formal academic work but an implementation. Besides the mentioned work that warrants a direct experimental comparison (enumeration and continuation [11], marching cubes [10]) to our method, we also mention more broad work for additional context. There are a number of algorithms for speeding up isosurface extraction (as polygon meshes) from real-world data such as MRI and CT scans, e.g., based on octrees [14] or other, more exotic data structures [15; 16]. However, these methods assume that data points on the grid are already known (sampled). Thus, direct application of these algorithms to polygonizing SDBs is not possible. There is also a large body of work on generative models for geometry. In this context, we mention those that directly output polygons. [PERSON] et al. (2017) represent geometry as a signed distance field defined on a deformable tetrahedral grid and incorporate this into a learning framework. Their end result is a neural representation that can directly generate polygonal models from the training data distribution. In the PolyDiff paper ([PERSON] et al., 2018), the authors introduce a mesh generator based on a denoising diffusion process ([PERSON] et al., 2018; [PERSON] et al., 2018). In the MeshGPT paper ([PERSON] et al., 2018), the authors use a decoder-only transformer neural network to directly output the polygons of a mesh. All these works are learning-based, i.e., require a large dataset in order to be effective, are not easy to implement/use in a production system like a game engine, and require significant computational resources.