Welcome to Fractal Forums

What is a distance field ?

this is not a naive question  :dink: : 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 ?

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?

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.



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).


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).

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.

Oh yes of course the DE can be signed. I DID know it ! :embarrass: (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  :fiery:) : I'm only a programming handyman ...  :dink:
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 ... :hmh: :hmh:

Thanks a lot for your replies.

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)

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.