Go to bottom

So, what do distance field equations look like? And how do we solve them?

category: code [glöplog]
I've just rendered the scene at 1420x850:

- 11.210 with my method
- 43.330 direct rendering
added on the 2009-08-23 02:53:32 by texel texel
Hey iq, this is really interesting... connect to messenger if you are there
added on the 2009-08-23 02:54:58 by texel texel
wow, x3 speedup so far! :)
added on the 2009-08-23 02:55:44 by iq iq
go texel go! :D
added on the 2009-08-23 02:58:02 by bdk bdk
Optimized a bit more, from 3.554 seconds for 720px to 2.770
added on the 2009-08-23 07:05:16 by texel texel
Ok ok, after having a look to the discution, i think you're looking for very complicated things here texel whereas things could be much more simple... not that trying to do packet tracing for distance fields is a bad idea in itself, but..

Here is the idea,
What about using an approximation of the distance field to get an idea where the intersection is, and then refine with a few bisection steps?

where the approximation of the distance field would storing the distance field values in a 3d texture (but you only need to access a pyramid in that volume...).. though the result depends on the resolution. The values that will be the most used will simply be in the cache... Not that this also works with secondary rays and GI rays..
Furthemore, 64*64*64 < 1920*1200...

To refine your intersection, you simply need to do a few bisection steps on your actual implicit function afterwards.. 8 steps should be enough..
added on the 2009-08-23 09:52:07 by nystep nystep
nicestep, iq wrote the same some pages ago.

In any case, what I'm doing is not very complex (less than a hundred lines of code) and it is just experimenting, it is fun :P
added on the 2009-08-23 10:19:52 by texel texel
Ok, my bad :)
I was too lazy to read more than approximately the last couple of pages :D
added on the 2009-08-23 10:29:00 by nystep nystep
Still i really like the 3d texture approach, notice how elegant it is that ray coherency translates into cache coherency.. without doing anything special..
added on the 2009-08-23 10:30:06 by nystep nystep
So, I have done some tests. I did a simple modification to the original algorithm to take some of Texel's ideas into account.

Slisesix was using already a tile based rendering system (for the multithreading). So what I did was to march one ray thru the center of the tile before doing the regular raymarch for the pixels in the tile. As this central ray marches the empty spheres are stored in a local array for later use. Then the normal marching is done for the pixels as before. During the marching the local array of spheres is tested so that the ray safely steps forward as much as it can thru the sphere tunnel without doing any distance computations. The amount of code to do this is really small.

For Slisesix at 1280x720 I was getting 12.7 secs render time with the original algorithm and the dist(x,y,z) posted few pages ago. With this version of mine of Texel's idea I get 10.9 secs - a 15% time saving. This is what I expected, as the rays very quickly diverge and do not benefit from the tunnel anymore. Still disappointing compared to the 66% (x3) savings reported by Texel (I'm still very surprised with this, I didn't expect a >20%). So I either might have implemented a too naive algorithm or have done a big mistake somewhere.

Any of you have other experiences to share?
added on the 2009-08-23 16:38:28 by iq iq
not yet but I actually am also working on an implementation with a bit more salsa :). thus, soon.
added on the 2009-08-23 16:47:33 by decipher decipher
dunno, I anyway don't like the screenspace acceleration tricks,as they only work for primary rays. I'm still in favour of a volumetric acceleartion, or simply doing agressive LOD in the distance function itself (like distant objects don't need all the details and so on).
added on the 2009-08-23 16:53:33 by iq iq
iq: I favor a combination of both. sure screenspace acceleration kills the precision of the algorithm most of the time but it certainly lights a rocket under the ass of your raymarcher :).
added on the 2009-08-23 16:55:57 by decipher decipher
not sure. in my case >60% of the render time is for texturing, shading and effects anyway, so a 1000x faster raymarcher would still produce my images less that 2x faster. Also, as far as I understand Texel's algorithm is pixel perfect, it shouldn't produce any precission problem. Well, again I only believe in numbers, so let's see results.
added on the 2009-08-23 17:02:28 by iq iq
I'm wondering if there are any differences between the method "raymarching-distance fields" and the "sphere tracing" method from John C Hart (didn't know about it, thanks Ferris for the link! and iq thanks for the older article of John in 1989, wooo), at a first look, not really, but not sure, any ideas?
By the way, i found the name "sphere tracing" to be somewhat more adapted to understand this technique. iq, i don't know if you have introduced the "distance fields" terminology but what do you think? Shouldn't we call it "Sphere tracing" in order also to have a better understanding and clear link to the work of John?
added on the 2009-10-06 14:17:15 by xoofx xoofx
distance to a rounded cube:

Code: float distToCBox( in vec3 p, in vec3 box, float rad ) { return length( max( abs(p) - box + vec3(rad), 0.0 ) ) - rad; }

box is, as usual, half the length of the box's side
rad is the radious of the curvature

added on the 2010-05-10 10:09:26 by iq iq
And a side note, that would make the size of the virtual box tangent at its corners to the governing curvature equal to box. If you want the curvature itself to be governed by the size of the box, box, then you have to omit the term + vec3(rad).

End of the useless info :).
added on the 2010-05-10 10:48:12 by decipher decipher
great! thanks for sharing :)
added on the 2010-05-10 11:00:41 by xTr1m xTr1m
I must have missed this thread before, good thing it was bumped!
Before I had only the vaguest idea on what raymarching was, but after seeing the picture in IQs presentation-pdf with the spheres getting smaller and smaller and the line pointing to the nearest intersection, I got the total "Ahaaa, so easy and yet so clever" experience. :)
Now I managed to hack together a little test in Processing in half an hour that rendered a couple of spheres and a plane.
I didn't quite get how the AO thing worked though, so at the moment no shading.
Now I only need to study shaders some more, because it seems like doing it on the GPU is the cool way to do it (or at least faster, my naive Processing apporach is running single digit FPS for a 320x240, no-shading-three-objects scene...)

Btw. what was the first intro to use this technique in realtime?
added on the 2010-05-10 18:06:53 by Sdw Sdw
Indeed Sdw, to help me understand a bit more raymarching, I wrote a sample introduction to raymarching, that could be also of some interest for people looking (like me at the beginning) for an introduction about the raymarching algo : iq's article is great, full of tips, but I was not enough smart to get the right understanding of the basic raymarching algo... so writing a small article was a way for me to experience myself the logic behind it ;)

added on the 2010-05-10 22:07:52 by xoofx xoofx
Sdw: I think it was actually Receptor or the like...I'd seen some with distance fields but the adaptive length approach in sphere tracing was done in the TBC intro first I believe.

Someone confirm? :)

Also, I agree with @lx about iq's thing... I was at NVScene for that seminar and the way it was described still seemed really mysterious...but, I got the object morphing and twist concepts from it, which was cool. Perhaps we should all collaborate on an intensive raymarching page for in4k?
added on the 2010-05-11 01:44:05 by ferris ferris
Also to reiterate @lx's earlier question to iq:

iq, i don't know if you have introduced the "distance fields" terminology but what do you think? Shouldn't we call it "Sphere tracing" in order also to have a better understanding and clear link to the work of John?
added on the 2010-05-11 01:51:08 by ferris ferris
in fact I'm quite against calling it "sphere tracing", cause there is no sphere being traced. What you cast are still ordinary rays.

In the other hand I didn't introduce the term "distance fields". I thing "signed distance fields" have been in use since the prehistory of computer graphics.

If I think that "raymarching in distance fields" is the right way to call it is because what the technique does is, pretty much, marching a ray in a field that encodes distances which are signed. I mean... I don't see any spheres being marched here.

Spheres arise in a schematic picture of the algorithm, but that's specific to the algorithm, not to the technique, and could change. If I store not isotropic distances but directional distances, should we call it "potato marching" because the schematic drawing of the algorithm would show some bizarre (spherical harmonics-like) bound shapes instead of spheres? I think it should still be called "raymarching in directional distance fields", not "potato marching" or "directionally shaped sphere tracing".

I think John's name was quite unfortunate, and he should have used the name the rest of the people were using for it. For example, in 1989 (7 years before John's paper) they were already using the same algorithm and calling refering to the technique as "ray traversal assisted by distance estimation and unbounding volumes", which is a bit too long.

Anyway, I'm fine with anything that reads "raymarching/raytracing" and not "spheretracing", cause again, it's rays whay we trace/cast/march, not spheres/volumes/potatoes...

This my speech in favour of the "ray marching distance fields"... Does this make any sense or ...?
added on the 2010-05-11 05:46:28 by iq iq
besides, as far as have seen, other people using this technique in the industry call it simply "raymarching".

Btw, one of the first intros I remember using this technique is Falty by our very beloved Loonies, in 2006: http://www.pouet.net/prod.php?which=26834, although I cannot really tell if it's constant step raymarching or distance field assisted...
added on the 2010-05-11 05:56:13 by iq iq
The paper on raymarching unbounding volumes with distance, 1989: http://www.pouet.net/prod.php?which=26834

Yes man, everything was invented already by 1990, we just keep doing the same thing, only faster.
added on the 2010-05-11 05:59:14 by iq iq


Go to top