Ray Tracing Harmonic Functions

ACM Transactions on Graphics (SIGGRAPH 2024)

pdf (11.2 mb)
supplement (350 kb)
video (2 min)
video (10 min)
code (ShaderToy)
code (C++)
doi
bibtex

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

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