# pouët.net

Go to bottom

## 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 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.
added on the 2008-09-07 21:50:58 by ryg
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.
added on the 2008-09-07 22:22:57 by Hyde
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.
added on the 2008-09-07 22:40:34 by Hyde
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.
added on the 2008-09-07 22:47:05 by ryg
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. :)
added on the 2008-09-09 09:52:52 by Blueberry
go for a rotozoomer
added on the 2008-09-09 10:24:12 by tobé
Yeah, rotozoomers are nice and straight forward to implement, screw that awful math!
added on the 2008-09-09 10:25:11 by kusma
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.
added on the 2008-09-09 10:28:19 by doomdoom
will Maple fit in a 4k intro? :)
added on the 2008-09-09 10:34:01 by iq
Hehe. It's not middleware ;). But it does have an API. Been meaning to look into that, it might be really useful.
added on the 2008-09-09 11:00:40 by doomdoom
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 :)
added on the 2008-09-09 11:04:50 by ryg
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 ;).
added on the 2008-09-09 11:53:08 by doomdoom
"iqs accelerated ray marching" what is it? url?
added on the 2008-09-09 12:05:47 by rale
the presentation he gave at nvscene - slides here: http://rgba.scenesp.org/iq/divulgation/nvscene2008/nvscene2008.htm
added on the 2008-09-09 12:16:10 by ryg
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
Could not initialize slide 8
added on the 2008-09-09 13:49:03 by kusma
same result here, same processor, same OS, but GeForce 7600GT. but I just figured needs an 8xxx gfxcard, so I watched the PDF instead..
added on the 2008-09-09 13:50:46 by bartman
same problem here as well.
added on the 2008-09-09 13:57:38 by ryg
"Karma Police, arrest these men, they talk in maths, they buzz like a fridge, it's like a detuned radiiioo" -Radiohead
:D
added on the 2008-09-09 14:30:28 by oxb
:)
added on the 2008-09-09 14:45:00 by raer
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).
added on the 2008-09-09 16:52:25 by iq
===================================================
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