Amazing Work! & Question about three.js-pathtracing-renderer

[erichlof]

Hi @ZevanRosser
Thank you for the kind words! Regarding the CSG algorithms, I'll try to be as specific as I can - but it's been a while since I worked on those. :)

I can't remember how I got inspired to try CSG, it might have been from a random AutoCAD YouTube video, where one can do those operations easily with that software. Back then when I was starting out with this stuff, I literally Googled around for CSG algo's and I came across 2 different sources that were/are helpful in outlining all the possibilities (there were much more than I had thought of). Here are a couple of links to check out.
Ray Tracing CSG paper and Blog post about CSG .

These were very helpful because they made tables for all the possibilities of each CSG operation. There are basically 9 possibilities for each operation, 3 for each of the 2 shapes (3 * 3 = 9). They are EnterA ExitA, MissA, and EnterB, ExitB, and MissB. Once I understood what the choices were I set about adding one situation at a time, starting with the easiest, the ADD or Union operation. the SUB or Difference operation and Overlap operation took a whole lot of trial and error. I think I spent a good month trying to get those different possibilities to work!

That said, there are positives and negatives about Ray/Path tracing CSG. The positives are that if you stick with simple primitive shapes like spheres, ellipsoids, cylinders, etc. the classic ray/shape intersection routines for each of those have long been studied and optimized. Especially on the GPU, it does really well with those shapes. One more positive is that you can make both objects be glass or clear plastic and get some really cool results as the rays enter and exit the shapes. Since the intersections are mathematical, you get pixel perfect smooth edges and curves - something that would be very hard to do with a more traditional high triangulated mesh.

Now for the negatives: As you can see from the papers I linked to and my own source code for those CSG possibilities, there must be a LOT of 'if' branching statements. And traditionally, we're not supposed to throw a lot of 'if' statements at the GPU. It doesn't like divergent code, it prefers to work on the same branch of code in parallel. And if you have too many 'if'statements, the shader will just crash. That is why I have 4 separate CSG demos. I originally tried to add all 12 objects along the 4 walls of the museum room, but my browser kept crashing, or the shader code wouldn't even compile. Thus I ran into the limit of the amount of 'if's I could have in one sequence. Now, on an old CPU renderer that is not real-time, it would have no problem with thousands of those shapes and possibilities, it seems that CPUs just love 'if' statements. ;-)

Regarding path vs. ray tracing, the only material the 2 algos differ on is with a Diffuse surface. Both path and ray tracing handle Specular objects the same, like Mirrors, Metals, Glass objects, Water, etc. But if you make the materials Diffuse, the ray tracer might just pick an average color for the entire surface and light it accordingly using the usual 'Normal.dot(LightDirection) as a falloff. However the path tracer will do this on the first bounce, but then pick a random direction in the hemisphere right above the hit location where the ray pierced the surface, and then continue onward in that random direction, repeating for however many 'depth' bounces you ask for. This randomness is what gives path tracing its photo-realistic look, but also introduces noise when there aren't enough samples yet. This also wreaks havoc on the GPU CSG routine because with each iteration, different rays on the screen are bouncing all which ways, requiring that ALL of those 'if' statements be tested eventually - again we're back to divergence which the GPU does not care for.

I hope this helps get you started on your path to understanding ray/path tracing CSG objects. Best of luck!
-Erich

[ZevanRosser]

Awesome! Thanks so much for that detailed response. That's very helpful. Too bad about the if statements, I'll have to play around with it a bit more. Luckily, even with just a few boolean operations I can get some pretty interesting stuff.

Back when I was a kid I spent an entire summer in KPT Bryce - waiting 15hrs for straight up raytracing of 640x480 images.... amazing how far things have come. For nostalgia I still use Bryce from time to time... often using boolean operations to create complex objects... (see pic, cylinder with cubes subtracted)

thanks again,
z

[ZevanRosser]

I made those two hacked ones as I was learning about pathtracing stuff - and used some of your code there to make ellipse and cylinders :D

[erichlof]

@ZevanRosser
Thanks for the pic - that's cool! Yes things have come a long way since the days of waiting hours (or days) for rendering a single frame. Speaking of unfortunate 'if' statements and how to circumvent them, something just came to mind as an alternative rendering solution that could still be real-time: CSG with sphere tracing and distance fields.

On this repo I use the classic ray/shape intersection algos which produce fast and accurate results suitable for final rendering. However there is a different approach from this classic ray tracing; sphere tracing (also known as ray marching). It is used on my outdoor demos. Instead of shooting rays out into the scene and finding closed-form solutions for the ray t-value, you cast a sphere (large at first, getting smaller and smaller as it advances each step) and get the distance from the center of that sphere to all of the scene geometry. When the sphere first launches out into the scene, it is a gross approximation. But when the first distance to any object(s) is returned, the sphere is advanced either that whole distance, or half that distance (if scene accuracy is required, like a mountain side with rocks). It might require 200 or 300 advancing steps (which is why it is sometimes called 'marching'), but as it gets closer and closer, the distance from the sphere to the surface gets more accurate until an epsilon is reached, say 0.001 units.

There are positives and negatives to this alternate approach to ray tracing. The negatives are that is slower than casting one ray and being done with it. The shader has to loop 200 or 300 times for every pixel, some pixels will hit early and break out of the loop, while others might skim the horizon and never hit, thus diverging from their neighbor pixels, which as we discussed, GPU's do not care for. One more minor negative is that it IS an approximation, rather than a closed-form solution, so edges of mathematical shapes are sometimes not as crisp as they would be with traditional ray casting.

But the positives might outweigh the negatives because since we are only getting the distance from the sphere center to the scene, we don't need a complex closed form solution (like for a ray/cone). Rather, a 'distance-field' is used. This distance field can take any shape, from terrain, to abstract fractal, to cloud-like, to water waves, to boolean CSG geometry. If the surface(s) can be defined as a simple math formula to get the distance to itself from the sphere center, then you can render it. And with CSG, you can avoid if statements that are needed in traditional ray-casting, because you can do intrinsic functions like min(d1,d2) and max(d1,d2), where d1 and d2 are distances to the two mathematical shapes you are performing CSG operations with. GPU's have no problem with a bunch of native min and max statements, they eat those for breakfast.

It might be worth looking into if you want to get more complex with your CSG adventures and keep it real-time. Here are a couple of resources: iq's distance function encyclopedia and a fun, interactive full-blown CSG editor on ShaderToy.

Enjoy and best of luck!

[ZevanRosser]

very cool - thanks again for all the info :D I'm familiar with that great link from iq... hadn't seen that editor though. I know I saw someone try to fork iq's marching stuff and turn it into a pathtracer but it looked really weird... I can't seem to find the link again.

I've done lots of 2D implicit boolean stuff like this (fun and simple stuff):
http://zevanrosser.com/vents/tooth-curve.html
http://zevanrosser.com/vents/implicit-moon.html

I've been thinking about forking and playing with iq's primatives shader (the one at the bottom of the distance function article): https://www.shadertoy.com/view/Xds3zN

... seems he just recently added a rounded cone.

thanks again,

z

[ZevanRosser]

P.S here are your ellipse and cylinder functions inside a modified version Evan Wallace's pathtracer:

http://mtcanvas.com/hack/pathtracer/demo-2-512/index.html

and another weirder one:
http://mtcanvas.com/hack/pathtracer/demo-3-512/index.html

code is a total mess - as I was just using it to learn how this stuff works ;)

[erichlof]

@ZevanRosser
Thanks for the links - those path tracers are pretty cool! Are those made by you, or are they something you found while searching the internet for path tracers? I've seen Evan Wallace's original path tracer project but I haven't seen the hacked ones before.

Yes you should fork iq's primitives ShaderToy example - a lot can be learned from just that one shader. Maybe it'll lead to other things that he hasn't thought of! ;-)