## Implicit function to distance function

**category:**general [glöplog]

Okay, doing this on the oneliner is silly.

Parapete has some implicit function f(x,y,z) in 3D and wants to get a reasonable signed distance function for use with iqs accelerated ray marching. iq suggested using f(x,y,z) / |grad f(x,y,z)| and noted that "It only works as get closer to it." [sic :)].

Now, what you need is basically to find the roots of your distance function, and for a smooth function, a lower bound for the minimum distance to the next root is f(x,y,z) / sup { |grad f(x',y',z')| | (x',y',z') in R^3 } (or some other domain). The sup (or max if that's well defined) is critical here; if your function has unbounded derivatives you're pretty much screwed no matter what, even though |f'(x,y,z)| may be completely reasonable. And if your function has local minima (or near-minima) somewhere, i.e. |f'(x,y,z)| gets close to zero, you'll end up taking very distant steps, probably too far. That's why the f(x,y,z)/|grad f(x,y,z)| only properly works as you get close to the solution.

In fact, if you use that trick, what you're doing boils down to a Newton-style root finder. You get all the advantages (quadratic converge near roots if the function is smooth), but you also get all the disadvantages (notably, Newton's is pretty crappy if you're not fairly close to a root already, and it

Using the "max |grad f|" instead avoids these problems (it guarantees that you can't miss a root), but it's also a pretty conservative approximation that will, in doubt, tend to take relatively small steps.

Your best guess is probably to take the "safe" scheme to get reasonably close to a root, then do two or three more Newton-style iterations to refine the accuracy of your hit points.

Parapete has some implicit function f(x,y,z) in 3D and wants to get a reasonable signed distance function for use with iqs accelerated ray marching. iq suggested using f(x,y,z) / |grad f(x,y,z)| and noted that "It only works as get closer to it." [sic :)].

Now, what you need is basically to find the roots of your distance function, and for a smooth function, a lower bound for the minimum distance to the next root is f(x,y,z) / sup { |grad f(x',y',z')| | (x',y',z') in R^3 } (or some other domain). The sup (or max if that's well defined) is critical here; if your function has unbounded derivatives you're pretty much screwed no matter what, even though |f'(x,y,z)| may be completely reasonable. And if your function has local minima (or near-minima) somewhere, i.e. |f'(x,y,z)| gets close to zero, you'll end up taking very distant steps, probably too far. That's why the f(x,y,z)/|grad f(x,y,z)| only properly works as you get close to the solution.

In fact, if you use that trick, what you're doing boils down to a Newton-style root finder. You get all the advantages (quadratic converge near roots if the function is smooth), but you also get all the disadvantages (notably, Newton's is pretty crappy if you're not fairly close to a root already, and it

**will**take too small or too large steps and miss an intersection sometimes).Using the "max |grad f|" instead avoids these problems (it guarantees that you can't miss a root), but it's also a pretty conservative approximation that will, in doubt, tend to take relatively small steps.

Your best guess is probably to take the "safe" scheme to get reasonably close to a root, then do two or three more Newton-style iterations to refine the accuracy of your hit points.

parapete didnt ask a general question though, he had a particular function in mind, or did you pete? I case you meant that cos-thing, I am curious to see what interesting effect comes out of it.

Thanks for writing this, ryg. I appear to have underestimated the problem though (I'm looking for something quick to hack in a 1k this weekend) and this calculus is slightly over my head. Oh well... :)

Hyde, it's the function from the raytracer part in Aura for Laura and Fallty (among others), but I was asking in a general sense.

parapete: sure, i'm just saying that, in many cases, general statements can be confusing and it is often good to sit down and look at the particular function you have in mind.

In your case, the generic surface is more or less a bunch of spheres.

In your case, the generic surface is more or less a bunch of spheres.

Hyde, oops sorry! Misunderstood what you were asking. I'm sat with a pen and paper now trying to find a solution for this specific case right now, as it happens... :)

Make sure you don't forget to subtract a constant first - otherwise you're going to get nowhere.

For very smooth and well-behaved functions like this, you could precalculate the relationship between the function value and the distance and store it in a table, i.e. for each possible function value, store the minimum distance that can occur at any point with that function value. It will be quite an expensive brute-force calculation, but you only need to do it once.

For even better results, make the table two-dimensional and look up using both f and |grad(f)|.

Now, for a 1k, storing a table is probably not an option, but even then, it might be possible to find a simple function that conservatively approximates the relationship for your particular implicit surface function. You will have to look at the distances the precalculation collects and see if you can match the shape. :)

For even better results, make the table two-dimensional and look up using both f and |grad(f)|.

Now, for a 1k, storing a table is probably not an option, but even then, it might be possible to find a simple function that conservatively approximates the relationship for your particular implicit surface function. You will have to look at the distances the precalculation collects and see if you can match the shape. :)

go for a rotozoomer

Yeah, rotozoomers are nice and straight forward to implement, screw that awful math!

parapete: If you do this sort of thing a lot, it's not a bad idea to get a maths package like Maple (runs in Linux, too, ZOMG). That'll make the whole thing a lot less tedious and you'll make fewer mistakes along the way.

will Maple fit in a 4k intro? :)

Hehe. It's not middleware ;). But it does have an API. Been meaning to look into that, it might be really useful.

computer algebra packages are really powerful tools, but in my experience they're a total bitch to work with (unless you try toy problems). worth it if you have a tough nut to crack, but don't underestimate the time you'll spend rephrasing the problem again and again until you get somewhere, and the time you'll spend on cleaning up the solution afterwards :)

Yeah all it does is automate parts of the process for you, you still need to know what you want it to do. Every now and again, some expression will simplify in a way you hadn't thought of, but just as often it'll overlook solutions because it's not aware of all the assumptions you might be making (like a distance measure >= 0, etc.). I find that overall, though, it saves you a lot of time, and that lets you experiment more. Plus, despite the clumsy line-based input, you can quickly render things like basic function graphs, implicit surfaces from any function, etc.

For a tool that sells for like £15, that's pretty neat. (I paid £2.50 for mine back when I were an student, dunno if I'm still allowed to use it but whatever ;).

For a tool that sells for like £15, that's pretty neat. (I paid £2.50 for mine back when I were an student, dunno if I'm still allowed to use it but whatever ;).

"iqs accelerated ray marching" what is it? url?

the presentation he gave at nvscene - slides here: http://rgba.scenesp.org/iq/divulgation/nvscene2008/nvscene2008.htm

Hm, the executable version doesn't work here, it crashes (instruction at 0x69774819 tries to write to 0x0263004c). And, no IQ, I don't have a particularly old computer (core 2 duo @ 2.4, 2 gb ram, gf 8600 gt)...

here's the debug.txt log:

===================================================

date : 11:44:27 of Wen 9/9/2008

Memory: 1000 / 2038 Megabytes

CPU : Intel(R) Core(TM)2 CPU 6600 @ 2.40GHz

Units : 2

Speed : 2392 Mhz

OS : Microsoft Windows XP

GPU : Unkown, NVIDIA GeForce 8600 GT

VRam : 0 Megabytes

===================================================

sketches\\skChocolux.dll

failed

sketches\\skDeform2.dll

failed

sketches\\skKindernoiser.dll

failed

sketches\\skKinderpainter.dll

failed

sketches\\skMandel.dll

failed

sketches\\skRasterizer.dll

failed

[-2] .\src\iqSlide.cpp::iqSlide0::Initialize (93) :could not found sketch "Mandel"

Could not initialize slide 8

here's the debug.txt log:

===================================================

date : 11:44:27 of Wen 9/9/2008

Memory: 1000 / 2038 Megabytes

CPU : Intel(R) Core(TM)2 CPU 6600 @ 2.40GHz

Units : 2

Speed : 2392 Mhz

OS : Microsoft Windows XP

GPU : Unkown, NVIDIA GeForce 8600 GT

VRam : 0 Megabytes

===================================================

sketches\\skChocolux.dll

failed

sketches\\skDeform2.dll

failed

sketches\\skKindernoiser.dll

failed

sketches\\skKinderpainter.dll

failed

sketches\\skMandel.dll

failed

sketches\\skRasterizer.dll

failed

[-2] .\src\iqSlide.cpp::iqSlide0::Initialize (93) :could not found sketch "Mandel"

Could not initialize slide 8

same result here, same processor, same OS, but GeForce 7600GT. but I just figured needs an 8xxx gfxcard, so I watched the PDF instead..

same problem here as well.

"Karma Police, arrest these men, they talk in maths, they buzz like a fridge, it's like a detuned radiiioo" -Radiohead

:D

:D

:)

Kusma, that error I see on the log file has nothing to do with shaders, apparently the plugin dlls are corrupted or something (basically that error means GetProcAddress() is failing! Interesting... Does depends.exe show any export symbol on the dlls?? Thx!

For the others, any gfx card with shaders 3 should do it (it works fine in my Radeon 1800 for example, also in my GeForce 8600 GT too of course).

For the others, any gfx card with shaders 3 should do it (it works fine in my Radeon 1800 for example, also in my GeForce 8600 GT too of course).

===================================================

date : 15:43:37 of Wen 9/9/2008

Memory: 2047 / 2047 Megabytes

CPU : Intel(R) Core(TM)2 Duo CPU E8200 @ 2.66GHz

Units : 2

Speed : 2666 Mhz

OS : Microsoft Windows XP

GPU : ATI, Radeon X1650 Series

VRam : 0 Megabytes

===================================================

sketches\\skChocolux.dll

failed

sketches\\skDeform2.dll

failed

sketches\\skKindernoiser.dll

failed

sketches\\skKinderpainter.dll

failed

sketches\\skMandel.dll

failed

sketches\\skRasterizer.dll

failed

[-2] .\src\iqSlide.cpp::iqSlide0::Initialize (93) :could not found sketch "Mandel"

Could not initialize slide 8

date : 15:43:37 of Wen 9/9/2008

Memory: 2047 / 2047 Megabytes

CPU : Intel(R) Core(TM)2 Duo CPU E8200 @ 2.66GHz

Units : 2

Speed : 2666 Mhz

OS : Microsoft Windows XP

GPU : ATI, Radeon X1650 Series

VRam : 0 Megabytes

===================================================

sketches\\skChocolux.dll

failed

sketches\\skDeform2.dll

failed

sketches\\skKindernoiser.dll

failed

sketches\\skKinderpainter.dll

failed

sketches\\skMandel.dll

failed

sketches\\skRasterizer.dll

failed

[-2] .\src\iqSlide.cpp::iqSlide0::Initialize (93) :could not found sketch "Mandel"

Could not initialize slide 8

Also the full screen mode makes all my Windows jump to the other monitor. Grr! Is it too much to ask that coders not change resolution all the time? Just render to a texture and stretch that to fill the desktop. KTHX