Ray tracing harmonic functions
category: gfx [glöplog]
Hi,
I'm a graphics researcher (https://www.cs.cmu.edu/~kmcrane/) who got my start in the 1990s writing demos on the PowerPC Mac, and learned a lot from the demoscene/Pouët. I wanted to "give a little back" to this community by sharing some recent work we've done, that might fit well into some demos.
TL;DR: There are some funky new surfaces you can ray trace, using what we call "Harnack tracing." It's a lot like IQ-style sphere tracing, except that you don't have an SDF for your shape. Instead, you can use any so-called "harmonic function," including periodic functions and functions with interesting singularities.
Probably better to just check out the video, paper, and GLSL/ShaderToy examples:
https://www.youtube.com/watch?v=6j6WWzPV6aY
https://markjgillespie.com/Research/harnack-tracing/index.html
My student Mark also gives a really nice intro here:
https://www.youtube.com/watch?v=oDwedIuqh5Q
Enjoy!
I'm a graphics researcher (https://www.cs.cmu.edu/~kmcrane/) who got my start in the 1990s writing demos on the PowerPC Mac, and learned a lot from the demoscene/Pouët. I wanted to "give a little back" to this community by sharing some recent work we've done, that might fit well into some demos.
TL;DR: There are some funky new surfaces you can ray trace, using what we call "Harnack tracing." It's a lot like IQ-style sphere tracing, except that you don't have an SDF for your shape. Instead, you can use any so-called "harmonic function," including periodic functions and functions with interesting singularities.
Probably better to just check out the video, paper, and GLSL/ShaderToy examples:
https://www.youtube.com/watch?v=6j6WWzPV6aY
https://markjgillespie.com/Research/harnack-tracing/index.html
My student Mark also gives a really nice intro here:
https://www.youtube.com/watch?v=oDwedIuqh5Q
Enjoy!
Apparently I don't know how to make links:
Video: https://www.youtube.com/watch?v=6j6WWzPV6aY
Shaders & paper: https://markjgillespie.com/Research/harnack-tracing/index.html
Intro talk: https://www.youtube.com/watch?v=oDwedIuqh5Q
Video: https://www.youtube.com/watch?v=6j6WWzPV6aY
Shaders & paper: https://markjgillespie.com/Research/harnack-tracing/index.html
Intro talk: https://www.youtube.com/watch?v=oDwedIuqh5Q
really neat, thanks keenan! congrats to Mark.
badass. thanks for sharing. your example shaders look a bit like there would be a lot of work necessary to make the technique viable for 4k sizecoding :) but I imagine it could be used for showing really advanced 3D stuff in 64k intros.
Thanks for sharing and spending time to writing it so nicely in PDF form. Any improvements to find better bounding techniques for new type of functions are definitely welcomed!
Although I'm not entirely sure, you can call it a new tracing technique.
I remember segment tracing, that you also reference in your paper. In this attempt they were computing step size based on both current tracing position and direction of the ray (although indirectly, because it actually just used segment endpoints), so not just skipping empty sphere.
If I'm not missing something, the "harnack tracing" seems to be still relying only on traced position, so isn't it then just a variation of sphere tracing with more elaborate "safe" radius estimation formula (two phase) tuned for harmonic functions (plus local gradient-based stopping epsilon)?
The thing is you claim it's better than "sphere tracing", but what you actually compare it to is a sphere tracing with a restriction that "safe" radius must be obtained via Lipschitz bounds. Not to mention you state in abstract that "Sphere tracing is a fast and high-quality method for visualizing surfaces encoded by signed distance functions (SDFs).", which is yet another restriction (Lipschitz constant = 1). While, I was thinking that sphere tracing is more general concept, which is actually not restricted to the way you obtain "safe" radius of a sphere that doesn't intersect the surface.
Although I'm not entirely sure, you can call it a new tracing technique.
I remember segment tracing, that you also reference in your paper. In this attempt they were computing step size based on both current tracing position and direction of the ray (although indirectly, because it actually just used segment endpoints), so not just skipping empty sphere.
If I'm not missing something, the "harnack tracing" seems to be still relying only on traced position, so isn't it then just a variation of sphere tracing with more elaborate "safe" radius estimation formula (two phase) tuned for harmonic functions (plus local gradient-based stopping epsilon)?
The thing is you claim it's better than "sphere tracing", but what you actually compare it to is a sphere tracing with a restriction that "safe" radius must be obtained via Lipschitz bounds. Not to mention you state in abstract that "Sphere tracing is a fast and high-quality method for visualizing surfaces encoded by signed distance functions (SDFs).", which is yet another restriction (Lipschitz constant = 1). While, I was thinking that sphere tracing is more general concept, which is actually not restricted to the way you obtain "safe" radius of a sphere that doesn't intersect the surface.
>If I'm not missing something, the "harnack tracing" seems to be still relying only on traced position, so isn't it then just a variation of sphere tracing
Yep, totally. It's also based on identifying spherical regions of space that are guaranteed not to contain the surface. In the paper we just needed two different terms to discuss the differences between traditional sphere tracing, based on Lipschitz bounds, and the variant we were introducing, based on Harnack bounds. So, we could have just as easily called these "Lipschitz sphere tracing" and "Harnack sphere tracing." Sorry if that's confusing!
> you claim it's better than "sphere tracing"
I definitely don't want to claim that it's a better solution in all cases than Lipschitz sphere tracing. Instead, I just want to say that "Harnack sphere tracing" works better if your goal is specifically to ray trace surfaces defined by harmonic functions, rather than surfaces defined by SDF or SDF-like functions. That's something that is well-justified by the experiments in the paper (since if you try to apply Lipschitz sphere tracing to harmonic functions, you get all sorts of nasty artifacts).
> I remember segment tracing … not just skipping empty sphere
Right. So there are sort of two features of these conservative ray tracing algorithms you can think about:
- Geometry. What is the shape of the conservative region I'm using? (sphere, segment, etc.)
- Functions. What kind of functions can I get conservative bounds for?
Previous methods considered different geometries (spheres and segments), but only considered Lipschitz functions. In contrast, we consider a different class of functions (harmonic), but only consider spheres. It might be possible, for instance, to combine the two and do "Harnack segment tracing" rather than "Lipschitz segment tracing."
It's also fun to think about expanding this set. Are there other geometries that admit easy conservative bounds (say, cylinders or ellipsoids, rather than segments and spheres?). Are there other fundamentally different types of bounds on functions (not just Lipschitz or Harnack) that are useful for ray tracing? I'm sure the answer is "yes"—and suspect some of the folks in this community can (or have already!) come up with interesting answers. :-)
Yep, totally. It's also based on identifying spherical regions of space that are guaranteed not to contain the surface. In the paper we just needed two different terms to discuss the differences between traditional sphere tracing, based on Lipschitz bounds, and the variant we were introducing, based on Harnack bounds. So, we could have just as easily called these "Lipschitz sphere tracing" and "Harnack sphere tracing." Sorry if that's confusing!
> you claim it's better than "sphere tracing"
I definitely don't want to claim that it's a better solution in all cases than Lipschitz sphere tracing. Instead, I just want to say that "Harnack sphere tracing" works better if your goal is specifically to ray trace surfaces defined by harmonic functions, rather than surfaces defined by SDF or SDF-like functions. That's something that is well-justified by the experiments in the paper (since if you try to apply Lipschitz sphere tracing to harmonic functions, you get all sorts of nasty artifacts).
> I remember segment tracing … not just skipping empty sphere
Right. So there are sort of two features of these conservative ray tracing algorithms you can think about:
- Geometry. What is the shape of the conservative region I'm using? (sphere, segment, etc.)
- Functions. What kind of functions can I get conservative bounds for?
Previous methods considered different geometries (spheres and segments), but only considered Lipschitz functions. In contrast, we consider a different class of functions (harmonic), but only consider spheres. It might be possible, for instance, to combine the two and do "Harnack segment tracing" rather than "Lipschitz segment tracing."
It's also fun to think about expanding this set. Are there other geometries that admit easy conservative bounds (say, cylinders or ellipsoids, rather than segments and spheres?). Are there other fundamentally different types of bounds on functions (not just Lipschitz or Harnack) that are useful for ray tracing? I'm sure the answer is "yes"—and suspect some of the folks in this community can (or have already!) come up with interesting answers. :-)
>your example shaders look a bit like there would be a lot of work necessary to make the technique viable for 4k sizecoding :)
Yeah, it's an interesting challenge. Those shaders are pretty bloated, since they do a lot of stuff (and we weren't thinking about size!). Would be fun to see how small you can make a Harnack sphere tracer… :D
Yeah, it's an interesting challenge. Those shaders are pretty bloated, since they do a lot of stuff (and we weren't thinking about size!). Would be fun to see how small you can make a Harnack sphere tracer… :D
keenan: of course, you could create a new tracer for every combination of geometry, functions, or bounds. However, wouldn't that limit its potential uses?
As I checked, the radius you get from Harnack bounds is pretty good signed distance estimate, that's why you get a nice convergence. I didn't check all examples, but it's also continuous and mostly smooth, right? Intros/shadertoy shaders don't rely on exact SDFs anyway, so folks could pick it up directly to SDF-based frameworks. I think emphasizing the fact that you found a better distance estimate for harmonic functions compared to global Lipschitz bound is IMHO better selling point than a new tracer.
As I checked, the radius you get from Harnack bounds is pretty good signed distance estimate, that's why you get a nice convergence. I didn't check all examples, but it's also continuous and mostly smooth, right? Intros/shadertoy shaders don't rely on exact SDFs anyway, so folks could pick it up directly to SDF-based frameworks. I think emphasizing the fact that you found a better distance estimate for harmonic functions compared to global Lipschitz bound is IMHO better selling point than a new tracer.