Torus

[koiava]

Torus Intersection seams to have some serious precision issues.

[erichlof]

Hi @koiava Yes that is the one analytical intersection routine in my library of collected functions that has the most precision problems. I actually got that routine from iq (Inigo Quilez) on Shadertoy iq Ray-Torus , which he got in turn from Original Ray-Torus

I don't quite understand how the intersection routine does its magic. I only have studied and generally understand ray-plane and ray-sphere, the 2 most common intersection routines. For the other analytical shapes I have borrowed from various sources like the Ray Tracing From the Ground Up textbook, the PBRT textbook, and Shadertoy. I might try porting the original routine (link above) and seeing if the precision problems go away. Although the original is much longer and involved than iq's boiled down version, it might be still fast enough to be used in the real time scenes and have less artifacts.

Thanks! -Erich

[capagot]

Hi guys

I haven't actually seen the ray-torus intersection code that you are

using. However, I've already, in the past, successfully computed intersections between rays and implicit surfaces (polynomials in this case) through the use of interval arithmetic. More specifically, I've used affine arithmetic in a reduced form because the original interval arithmetic formulation was too conservative. If you do not know about interval/affine arithmetic, you might get an idea from the following paper:

https://pdfs.semanticscholar.org/b31d/7169c6aa63fbcab693d76ffab20d3621fd99.pdf

Although the evaluation of polynomials rewritten in the affine form is

a little bit more expensive, the root finding procedure is extremely fast, does not depend on an initial seed and is robust (robust in the sense that only regions that do not contain the root will be discarded by the root-finding procedure). Obviously, there are some degenerate cases where even the affine arithmetic becomes too conservative... but in the general case, it works quite well. Th ​e paper below (which is quite old... 2009) presents a realtime-GPU-based approach for the rendering (ray tracing in this case) of implicit surfaces through the use of reduced affine arithmetic:

http://onlinelibrary.wiley.com/doi/10.1111/j.1467-8659.2008.01189.x/full

Certainly, with current hardware much faster results could be obtained.

On the other hand, the paper presents a ray-tracing-based method, where just a few rays per pixel are needed. It would be interesting to see how this would work in a path tracing setting, where more -- and incoherent -- rays are needed.

And congratulations Erich for this awesome project!!!

Cheers,
Christian

​ ​

On Fri, Dec 8, 2017 at 6:34 PM, Erich Loftis notifications@github.com wrote:

Hi @koiava https://github.com/koiava Yes that is the one analytical intersection routine in my library of collected functions that has the most precision problems. I actually got that routine from iq (Inigo Quilez) on Shadertoy. Link https://www.shadertoy.com/view/4sBGDy

I don't quite understand how the intersection routine does its magic. I only have studied and generally understand ray-plane and ray-sphere, the 2 most common intersection routines. For the other analytical shapes I have borrowed from various sources like the Ray Tracing From the Ground Up textbook, the PBRT textbook, and Shadertoy.

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/erichlof/THREE.js-PathTracing-Renderer/issues/10#issuecomment-350377725, or mute the thread https://github.com/notifications/unsubscribe-auth/APDnnl6oo8Br8Xev3qq2RXmXAwosDCyiks5s-atUgaJpZM4Q7HjD .

[capagot]

In time...

 Affine arithmetic-based root finding is based on binary search, which

implies recursion. Obviously, GPUs do not support recursion and, in this case (as the paper I mention in the previous email), some kind of explicit stack might be needed. As far as I remember, the paper I mention proposes an additional stackless approach. All in all, it is fast and robust... but with a tricky implementation that would eventually consume a substantial portion of your time budget...

Cheers,
Christian

On Fri, Dec 8, 2017 at 11:15 PM, Christian Pagot < christian.azambuja@gmail.com> wrote:

Hi guys

I haven't actually seen the ray-torus intersection code that you are

using. However, I've already, in the past, successfully computed intersections between rays and implicit surfaces (polynomials in this case) through the use of interval arithmetic. More specifically, I've used affine arithmetic in a reduced form because the original interval arithmetic formulation was too conservative. If you do not know about interval/affine arithmetic, you might get an idea from the following paper:

https://pdfs.semanticscholar.org/b31d/7169c6aa63fbcab693d76ffab20d36

21fd99.pdf

Although the evaluation of polynomials rewritten in the affine form is

a little bit more expensive, the root finding procedure is extremely fast, does not depend on an initial seed and is robust (robust in the sense that only regions that do not contain the root will be discarded by the root-finding procedure). Obviously, there are some degenerate cases where even the affine arithmetic becomes too conservative... but in the general case, it works quite well. Th ​e paper below (which is quite old... 2009) presents a realtime-GPU-based approach for the rendering (ray tracing in this case) of implicit surfaces through the use of reduced affine arithmetic:

http://onlinelibrary.wiley.com/doi/10.1111/j.1467-8659.

2008.01189.x/full

Certainly, with current hardware much faster results could be

obtained. On the other hand, the paper presents a ray-tracing-based method, where just a few rays per pixel are needed. It would be interesting to see how this would work in a path tracing setting, where more -- and incoherent -- rays are needed.

And congratulations Erich for this awesome project!!!

Cheers,
Christian

​ ​

On Fri, Dec 8, 2017 at 6:34 PM, Erich Loftis notifications@github.com wrote:

Hi @koiava https://github.com/koiava Yes that is the one analytical intersection routine in my library of collected functions that has the most precision problems. I actually got that routine from iq (Inigo Quilez) on Shadertoy. Link https://www.shadertoy.com/view/4sBGDy

I don't quite understand how the intersection routine does its magic. I only have studied and generally understand ray-plane and ray-sphere, the 2 most common intersection routines. For the other analytical shapes I have borrowed from various sources like the Ray Tracing From the Ground Up textbook, the PBRT textbook, and Shadertoy.

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/erichlof/THREE.js-PathTracing-Renderer/issues/10#issuecomment-350377725, or mute the thread https://github.com/notifications/unsubscribe-auth/APDnnl6oo8Br8Xev3qq2RXmXAwosDCyiks5s-atUgaJpZM4Q7HjD .

[erichlof]

Hello @capagot Wow, thank you for the references - I didn't even know about these techniques. I must say that I don't quite understand the mathematics of the first paper. I'm trying to understand the general summation of the technique though. If I understand correctly, I.A. attempts to find a solution to a curve function by first defining some kind of conservative range that the answer would be in, and then breaking it up into smaller chunks or intervals, and then solving each of those more manageable pieces with their smaller ranges, and then somehow fitting them back together at the end? I may be totally off, but that's what I could gather from the diagrams (I am a visual learner, ha!). How does reduced A.A. do this more efficiently? - (in layman terms)

The second reference has some snippets of GPU code, which I understand a little more easily. But the issue is that they are just snippets of the whole author's solution. I guess they couldn't give away everything, but it would have been nice to see. I really like some of the mathematical shapes that they are able to render in real time. It reminds me of MAGI back in the early 1980's, when they were developing the tracing routines for the movie TRON - I love the lightcycles and tanks and such - apparently those are all mathematical shapes combined together and ray traced.

You should check out Shadertoy.com , there are a couple of more mathematical-minded coders over there who regularly post, i.e. the member 'paniq' with his examples like quadric frustrum tracing, affine arithmetic and Interval Arithmetic . I will study this shader, as it references the same paper you mentioned. I guess I would be more in the visual camp: I tend to visualize everything, even most of my code here. I imagine firing physical light rays from a camera, intersecting objects, getting their material properties, and bouncing off accordingly, collecting light as they go. I have to see a movie of all this in my mind when I am coding, otherwise I can't get it started. I barely understand the mathematical solutions for ray-plane and ray-sphere because you tend to see them everywhere. But still, I couldn't write one from scratch, I only know how to use them appropriately like tools in a tool case.

Thanks again for the references!

[koiava]

I believe if you want to have successful project first obvious step is to add CI. Then cover those low level functions with Unit Tests. That way you also can measure precision and ensure that no one will make it worth in the future.

In this particular example artifacts are visible in 'Geometry primitives Demo' There might be two separate problems:

1. Intersection code.
2. normal calculation code.

Right now they are very much separated from each other. Normal calculation is done based on intersection point but I believe that's not optimal, It should be possible to return normal directly from intersection function because there you have enough information to build the normal.

[erichlof]

@koiava Ok I will take a look at the intersection function and normal calculation again. I must admit I borrowed the Torus code from Shadertoy without understanding the complex math/algo behind it. I will investigate it further and see if there is a better solution for the intersection as well as the normal. What does CI stand for, when you said I should add that?

By the way, do you know of any resources online for this particular object? I looked through PBRT, but that is the only shape they don't have! It appears that this is the most problematic regular mathematical shape to calculate, and maybe they assume that the object will be triangulated anyway and that we can just call a bunch of ray triangle intersections to build up the shape and get the correct normal.

Thanks

[koiava]

Continuous integration CI.

I guess main reason why pbrt has shapes is to represent area light sources and not a actual geometry and reason why renderer wants to have lights with simple and well known shapes is that in that case renderer can define specific optimized sampling function for those. Torus is little more complex and it's not simple to write sampling function which will give Torus benefit compared to other shapes(like triangle mesh).

[erichlof]

@koiava

Ah thank you for clarifying. Yes that makes sense about why they have most analytical shapes covered - for area light sampling. Btw, I have just located a general ray-torus algorithm in C++ Here. As you can see, it is pretty hefty, but fortunately the author has a .zip file of the corresponding source code. I just have to see if I can port the C++ to GLSL and get all the loops and if statement branching to comply with the GPU.

Thanks again

[erichlof]

@koiava

Hi, I updated the intersection code for Ray-Torus in pathTracingCommon.js located inside the 'js' folder of this repo. After hours spent looking online and in my old ray tracing books, and converting 2 old C++ routines to GLSL, unfortunately I have not found a usable Ray-Torus routine that is suitable for the GPU. The algo I linked to in my previous post contained C++ Complex number manipulation library calls c(float real, float imaginary), which I couldn't quite convert efficiently over to GLSL. I also tried one of my old Ray Tracing from the Ground Up textbook's Torus routine, but I couldn't get past the part where he uses dynamic array indexing while looping through the roots, which is forbidden in GLES 2.0 / WebGL 1.0 . I even tried the original Antonalog routine from Shadertoy (where iq got his algo from), but not only did it fail to remove the artifacts even after tweaking precision parameters, it ran twice as slow without iq's crafty optimizations/reductions in place.

I ended up tweaking iq's Shadertoy torus routine (the one I've been using since the start) to account for reduced machine precision. Try the quadratic geometry demo and notice that the holes on the sides of the copper torus are gone (at least on my machine). Demo.

If you make the Torus huge, like as big as that large spherical room, the artifacts will return. Luckily, the Torus is not very commonly used or seen in real life scenes, and if it is (like a donut or a bagel), we can triangulate it in the future and feed it to the BVH for breakfast! ;-)

[koiava]

I think distance field based sphere tracing will work just fine for GPU. You can speed up this by adding bounding volume(cylinders for example) to minimize marching range.

[erichlof]

That's a good idea. I will experiment with that approach. Thread divergence might be an issue, because some rays will hit the bounding cylinder of the torus, then have to march in a tight loop 20-30 times to hone in on the torus shape to an agreeable tolerance, while other rays will miss the bounding cylinder of the torus completely, and quickly return with the background hit-info, and then have to sit around and wait for the torus marching rays to finish with their work. But maybe it won't be that big of a deal, we'll see. I'll let you know what I find, thanks!

[koiava]

Agree but that's always the case. Than you have to switch to stream tracing to maximize GPU utilization. Here I'm using ray marching inside AABB localy and it works surprisingly well.

[erichlof]

Wow, that's beautiful! I will study your shader code and try to learn from it. Thanks for the tips!

[erichlof]

Hi @koiava , I successfully implemented the distance field sphere tracing algo for the Ray-Torus intersection. It works perfectly, thanks for the suggestion! New Torus Intersection

I gave you credit in the pathTracingCommon.js file Link that contains the new set of routines under the 'pathtracing_torus_instersect' include portion.

Thanks again for your guidance and expertise!

[koiava]

If you move closer you might notice that it has very noticeable holes when viewing from the side: I would increase iteration count and replace bounding sphere with two clipped cylinder as I sujested above.

[erichlof]

Uh oh, thanks for catching those holes, I somehow missed that. I will work on it some more.

[erichlof]

Hi again, I used your suggestions in the updated Torus intersection algorithm. Could you please try it out and let me know if that resolves the holes issue? Thanks!