Ray Tracing Harmonic Functions
ACM Transactions on Graphics (SIGGRAPH 2024)
The sphere tracing algorithm provides a fast and high-quality strategy for visualizing surfaces encoded by signed distance functions (SDFs), which have become a centerpiece in a wide range of visual computing algorithms. In this paper we introduce a sphere tracing algorithm for a completely different class of functions, harmonic functions, opening up a whole new set of possibilities. Harmonic functions are found throughout geometric and visual computing, where they arise naturally as the solution to interpolation problems, and in the physical sciences, where they appear as solutions to the Laplace equation. Our algorithm for harmonic functions is similar in spirit to the sphere tracing algorithm for SDFs: by using a conservative lower bound on the distance to the level set, we can take much larger steps than with naïve ray marching. Our key observation is that for harmonic functions such a bound is given by Harnack's inequality. Unlike Lipschitz bounds used in traditional sphere tracing, this Harnack bound requires only the value of the function at a point—we use this bound to develop a sphere tracing algorithm that can also handle jump discontinuities arising in angle-based harmonic functions. We show how this algorithm can be used to directly visualize smooth surfaces reconstructed from point clouds (via Poisson surface reconstruction) or polygon soup (via generalized winding numbers) without performing linear solves or mesh extraction. We also show how it can be used to render nonplanar polygons (including those with holes), and to visualize key objects from mathematics, including knots, links, spherical harmonics, and Riemann surfaces.
Paper
Supplement
GLSL Examples
Several examples in the paper were implemented as GLSL shaders in ShaderToy:
Riemann surfaces are central objects of study in complex analysis. Much of their interesting behavior occurs at singular points, which pose problems for standard techniques, but are accurately resolved by Harnack tracing
A perennial question in computer graphics is how to interpret polygons whose vertices do not sit in a common plane. The ability to ray trace harmonic functions provides an elegant answer: we can visualize a nonplanar polygon as a level set of a harmonic function naturally associated to the polygon, namely, its (signed) solid angle
Given an oriented point cloud (left), we can directly visualize an interpolating surface (right). This procedure effectively shows the result of running the Poisson surface reconstruction algorithm of Kazhdan et al. [2006], without requiring any volumetric meshing or linear solves.
The gyroid is described by the zero level set of the function f(x, y, z) = sin(x) cos(y) + sin(y) cos(z) + sin(z) cos(x). Although this function is not harmonic, we can still ray trace its level sets by constructing a harmonic extension in four dimensions.
We can also visualize “hyperspherical” harmonics: 4D harmonic polynomials restricted to the 3-sphere and mapped into R³ via stereographic projection.
Riemann Surfaces
https://www.shadertoy.com/view/DlSfWdRiemann surfaces are central objects of study in complex analysis. Much of their interesting behavior occurs at singular points, which pose problems for standard techniques, but are accurately resolved by Harnack tracing
Nonplanar Polygons
https://www.shadertoy.com/view/DlSfWdA perennial question in computer graphics is how to interpret polygons whose vertices do not sit in a common plane. The ability to ray trace harmonic functions provides an elegant answer: we can visualize a nonplanar polygon as a level set of a harmonic function naturally associated to the polygon, namely, its (signed) solid angle
Point Cloud Reconstruction
https://www.shadertoy.com/view/DlSfWdGiven an oriented point cloud (left), we can directly visualize an interpolating surface (right). This procedure effectively shows the result of running the Poisson surface reconstruction algorithm of Kazhdan et al. [2006], without requiring any volumetric meshing or linear solves.
Gyroid
https://www.shadertoy.com/view/DlSfWdThe gyroid is described by the zero level set of the function f(x, y, z) = sin(x) cos(y) + sin(y) cos(z) + sin(z) cos(x). Although this function is not harmonic, we can still ray trace its level sets by constructing a harmonic extension in four dimensions.
Hyperspherical Harmonics
https://www.shadertoy.com/view/DlSfWdWe can also visualize “hyperspherical” harmonics: 4D harmonic polynomials restricted to the 3-sphere and mapped into R³ via stereographic projection.
Bibtex
@article{Gillespie:2024:RTH,
author = {Gillespie, Mark and Yang, Denise and Botsch, Mario and Crane, Keenan},
title = {Ray Tracing Harmonic Functions},
journal = {ACM Trans. Graph.},
volume = {43},
number = {4},
year = {2024},
publisher = {ACM},
address = {New York, NY, USA},
doi = {10.1145/3658201},
month = jul,
articleno = {99},
pages = {1--18}
}
Acknowledgements
Thanks to Nicole Feng for help with Biot-Savart-based expressions for our surface normals, to Albert Chern for helpful discussion of the Biot-Savart law and random projections of curves, and to Andrea Tagliasacchi and Google Brain for supporting this work. Figure 2 is based on an illustration by the last author. This work was funded by an NSF CAREER Award (IIS 1943123), NSF Award IIS 2212290, a Packard Fellowship and a gift from Google Brain.
Selected Figures
Our nonplanar polygon definition automatically applies to difficult cases like polygons with holes (left), or knotted boundaries (right)
Given a sparse "exoskeleton" approximating a surface (top left) we can directly ray trace an interpolating surface (top right). The resulting image is both higher-quality than the simple triangulation used by most mesh viewers (bottom left), and much simpler to compute than optimizing a mesh-based minimal surface, as originally proposed by de Goes et al. [2011].
Given a surface mesh with imperfections such as holes (left), we can directly visualize the repaired surface defined via the generalized winding number (right), reproducing the example from Jacobson et al. [2013, Figure 1].
Here we use Harnack tracing to directly visualize a special class of grid shells used in architecture, reproducing examples from Adiels [2022] figures 11, 12, and 22 (resp.). To do so, we extend our algorithm to handle circular holes in addition to polygons.