## 4 Theoretical Analysis of Computational Complexity
### Polygonizing Planes  
A plane is a flat, two-dimensional surface that extends infinitely far. Of course, we are interested in polygonizing only the part that intersects with the polygonization volume. The exact signed distance from a point \(\mathbf{r}\) to a plane \(P\) is given by the following Equation [22]:  
\[D_{P}(\mathbf{r})=\mathbf{n}_{P}^{T}\cdot(\mathbf{r}-\mathbf{r}_{P}), \tag{5}\]  
where \(\mathbf{r}_{P}\) is some point lying on \(P\) and \(\mathbf{n}_{P}\) is \(P\)'s normal vector such that \(\mathbf{n}_{P}^{T}\cdot\mathbf{n}_{P}=||\mathbf{n}_{P}||_{2}^{2}=1\). We analyze three different cases: two cases of axis-aligned planes and one case for a plane in a general position. The first case is when the plane and the rays are perpendicular. In our case, since the rays are cast in the \(+z\) direction, this corresponds to the plane \(z=C\) for some constant \(C\). The second case is when the plane and the rays are parallel (plane specified by \(x=C\) or \(y=C\)). The third case is the plane in a general position. **Case #1: plane \(P\) and rays are perpendicular**. First, notice that the orientation of the plane does not matter since the ray marching always uses the absolute value of the computed distance bound. Thus, we have two subcases: approaching the plane and escaping the vicinity of its surface. The approaching phase is performed in a single step for each ray since \(D_{P}\) provides the exact distance estimate. Hence, its complexity is \(O(1)\), independent of \(N\), the position of the plane along the \(z\) axis, and the starting point. Since there are \(N^{2}\) rays, the complexity of the approaching phase is \(O(N^{2})\). Escaping the plane's  
Figure 1: A 2D illustration of the gridhopping method: grid cells are dashed gray squares, the shape with an SDF is in red, and the \(z\) axis and the \(xy\) plane are in black. The dashed green line (parallel to the \(z\) axis) represents one of the rays along which sphere tracing is applied. Since the SDF of the red shape is known, we can compute the maximum step size along the ray (green circles). The green dots are locations obtained from these calculations. The marching cubes polygonization is first applied to the light-blue cell since it is the first one along the ray that satisfies the condition related to Equation (4). surface requires more work, and the following analysis holds for each of the \(N^{2}\) rays that need to be cast. Let \(\mathbf{r}_{0}\) denote the starting point in the vicinity of \(P\)'s surface. Note that \(D_{P}(\mathbf{r}_{0})\) is about \(\frac{1}{N}\) in size immediately after the polygonization routines for \(P\)'s cells have been invoked (at most two in this case, only one containing polygons). Analyzing the iteration (3), it is easy to see that \(D_{P}(\mathbf{r}_{1})=2\cdot D_{P}(\mathbf{r}_{0})\), and in general, the following holds:  
\[D_{P}(\mathbf{r}_{n})=2^{n}\cdot D_{P}(\mathbf{r}_{0}), \tag{6}\]  
i.e., the method escapes the surface in steps of exponentially increasing size. If \(D_{P}(\mathbf{r}_{0})\) is about \(\frac{1}{N}\), then the number of steps required to exit the polygonization volume is \(O(\log N)\). Given that there are \(N^{2}\) such rays, the complexity of the escaping phase is \(O(N^{2}\log N)\). The approaching and escaping phase are performed sequentially. Thus, the complexity of polygonizing a plane in this scenario is \(O(N^{2}\log N)\). **Case #2: plane \(P\) and rays are parallel**. First, notice that if the distance between a ray and \(P\) is equal to \(\frac{k}{N}\) in this case, then the method exits the polygonization volume in approximately \(\frac{N}{k}\) steps. There are \(N\) rays marching through cells that contain \(P\). The algorithm takes approximately \(N\) steps along each of these rays before terminating. Next, notice that there are \(N\) rays above and \(N\) rays below \(P\), parallel to \(P\), and of distance approximately \(\frac{k}{N}\) to \(P\) for some integer \(k<N\). These rays require about \(N/k\) steps before exiting the polygonization volume.