News: Did you know ? you can use LaTex inside Postings on fractalforums.com!  ## The All New FractalForums is now in Public Beta Testing! Visit FractalForums.org and check it out!

 Pages:    Go Down       Author Topic: What is a distance field ?  (Read 1983 times) Description: How can I know if a given f(x,y,z) function can be used as a distance field ? 0 Members and 1 Guest are viewing this topic.
Chanur
Forums Newbie Posts: 2 « on: August 20, 2012, 07:08:06 AM »

What is a distance field ?

this is not a naive question : I know what a distance field is. (for those who don't, its a mathematic function which gives, for each point M of the space, the distance between M and the nearest point of the object you're drawing. It makes the calculation much faster an precise than progressing along a ray with a constant step.)

If you have a way to calculate an exact distance field, you don't need to use the actual equation of the fractal : the distance field suffices.

And so it would be interesting to invent distance fields to draw new 3D fractals, exactly as you can invent several functions to drow flat fractals (I fancy, for example z(n+1) = sin (z) / z + c where c is the point on the screen).

So the question is : on wich condition is the function f(M) a distance field ? (M being a point x, y, z)

These two are evident :
f(A) must always be positive (it's a distance).
It's clear that if f(A) = a, then for B being at a distance d<a from A, f(B) must be lesser than a+d and greater than a-d

Is that sufficient ?
How can I know for a given function f(M) if it is true ?
 « Last Edit: August 20, 2012, 07:10:29 AM by Chanur » Logged

willvarfar
Explorer    Posts: 57 « Reply #1 on: August 20, 2012, 09:18:10 AM »

Isn't it fairly usual (outside the fractal DEs) for distance estimators to be signed, the sign indicating if you are inside or outside the object? Logged
Syntopia
Fractal Molossus  Posts: 681    « Reply #2 on: August 20, 2012, 02:19:00 PM »

If you have a way to calculate an exact distance field, you don't need to use the actual equation of the fractal : the distance field suffices.

Well, that is the way it works: most fractal software just use the DE-formula and stop at a certain proximity - there is no need to actually check whether your inside with a different formula.

Quote
So the question is : on wich condition is the function f(M) a distance field ? (M being a point x, y, z)

These two are evident :
f(A) must always be positive (it's a distance).
It's clear that if f(A) = a, then for B being at a distance d<a from A, f(B) must be lesser than a+d and greater than a-d

You are right, a distance field needs to have some contraints on how fast it can change. A fancier way of saying the same, is that it needs to be Lipschitz continuous with a Lipschitz constant of one (http://en.wikipedia.org/wiki/Lipschitz_continuity). If you want to prove this property, you need to look at the derivative (the gradient norm). In general this can be pretty hard: I look at the norm of the derivative of the Mandelbox in a blog post here: http://blog.hvidtfeldts.net/index.php/2011/11/distance-estimated-3d-fractals-vi-the-mandelbox/

And as Willvarfar said Distance Fields may be signed (this is always preferable).

Quote
Is that sufficient ?
How can I know for a given function f(M) if it is true ?

Well, it is certainly not sufficient: a constant function such as DE(vec3 p) = 0.5, is Lipschitz, yet cannot be used for ray marching. However, if you also required that is was zero *somewhere*, it probably is sufficient. It need not be exact, though - this only guarantees a lower bound of the distance (if you divide any DE by a number >1, you still get a DE). Logged
hobold
Fractal Bachius Posts: 573 « Reply #3 on: August 20, 2012, 07:47:46 PM »

There's another bit of non-obvious freedom: "distance" does not need to be Euclidian distance. As long as the ray marcher and the distance field are consistent with each other, other metrics will too, too. For example sum of absolute differences, or the maximum norm. Logged
Chanur
Forums Newbie Posts: 2 « Reply #4 on: August 21, 2012, 03:52:33 AM »

Oh yes of course the DE can be signed. I DID know it ! (in the mandelbulb, the DE I use is negative inside the set and it's very convenient)

@ Syntopia :
Very interesting ! Even if it's impossible to prove that a given formula is Lipschitz continuous, it may be easy in many cases to prove that it's NOT (by testing the gradient in random points) , and then eliminate rapidly some non adequate ones. And even, if I'm lucky, to understand why they aren't.

But I think the DE only have to be locally Lipschitz continuous, doesn't it ? Because for a fractal it's obvious that its's not globally. At least if I understand what Lipschitz continuity means.

And it makes me thing of a lighter test : the DE must first be continuous.

So if I summarize :
A distance field must be continuous, and more, it must be locally Lipschitz continuous with a Lipschitz constant of one.
It must have at least one point with zero value.

I dont care about mathematical rigor (may the purists forgive me ) : I'm only a programming handyman ... What I'm looking for is a way to know as quickly as possible if a given formula is an adequate DE. It can easily be done by launching a raytracer, but its slow... so if I can eliminate rapidly bad ones ...

The continuity and the Lipschitz continuity may be tested by looking at random points.
And the derivative doesn't afraid me : I already read the blog about the running derivative of mandelbulb and mandelbox, but I don't think it can easily be translated to other DE (short of these constructed by folds and scales). At first I intend to calculate the gradient by rough approximation : dx = finite epsilon

Any other idea of conditions a DE must meet ?

@ hobold :
Strange idea, indeed ... Interesting. I'll think about it, but I don't clearly see how to use it ...  Thanks a lot for your replies.
 « Last Edit: August 21, 2012, 04:00:16 AM by Chanur » Logged

willvarfar
Explorer    Posts: 57 « Reply #5 on: August 21, 2012, 07:59:58 AM »

You are imagining some genetic programming approach?

Leave your machine overnight 'breeding' random DEs?

(I used to evolve warriors for the corewars game; fun memories) Logged
Syntopia
Fractal Molossus  Posts: 681    « Reply #6 on: August 21, 2012, 10:54:12 AM »

After I gave it another thought, I don't think continuity (Lipschitz or not) is necessary. I guess that depends on whether you distance field returns the true distance to an object (in which case it must be Lipschitz), or is just a number less than or equal to the true distance (a lower bound) - which is all that is needed for ray marching.

For instance given a true (exact) distance field, you could create another distance field, which was equal for distances less than 2 units, and just returned 1 elsewhere. This would be discontinuous, but still perfectly acceptable for ray marching (though not optimal).

Even if you required continuity, you could still create distance fields with arbitrary steepness, as long as they are bounded by the true (Lipschitz continous) distance.

This will be much more difficult to test. Logged
 Pages:    Go Down
 Related Topics Subject Started by Replies Views Last post  Depth of Field Mandelbulb 3d mehrdadart 1 2969 February 09, 2011, 11:22:45 PM by Jesse  Field of balls Mandelbulb3D Gallery miguelnpg 0 465 May 15, 2011, 07:38:12 AM by miguelnpg  Quanta field Mandelbulb3D Gallery bib 0 579 July 12, 2011, 10:38:00 PM by bib  Distance field blending Programming Kali 2 1200 November 15, 2012, 08:17:56 PM by Kali  Is there a way to maintain a real distance field when modifying this fragment? Programming tryptophan 9 1209 April 04, 2013, 11:14:50 PM by Syntopia