Logo by Trifox - Contribute your own Logo!

END OF AN ERA, FRACTALFORUMS.COM IS CONTINUED ON FRACTALFORUMS.ORG

it was a great time but no longer maintainable by c.Kleinhuis contact him for any data retrieval,
thanks and see you perhaps in 10 years again

this forum will stay online for reference
News: Check out the originating "3d Mandelbulb" thread here
 
*
Welcome, Guest. Please login or register. March 29, 2024, 03:17:14 AM


Login with username, password and session length


The All New FractalForums is now in Public Beta Testing! Visit FractalForums.org and check it out!


Pages: [1]   Go Down
  Print  
Share this topic on DiggShare this topic on FacebookShare this topic on GoogleShare this topic on RedditShare this topic on StumbleUponShare this topic on Twitter
Author Topic: What is a distance field ?  (Read 3364 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  wink : 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



syntopiadk
WWW
« 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 ! 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 ...  wink
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 ... huh? huh?

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



syntopiadk
WWW
« 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: [1]   Go Down
  Print  
 
Jump to:  

Related Topics
Subject Started by Replies Views Last post
Depth of Field Mandelbulb 3d mehrdadart 1 3475 Last post February 09, 2011, 11:22:45 PM
by Jesse
Field of balls Mandelbulb3D Gallery miguelnpg 0 674 Last post May 15, 2011, 07:38:12 AM
by miguelnpg
Quanta field Mandelbulb3D Gallery bib 0 782 Last post July 12, 2011, 10:38:00 PM
by bib
Distance field blending Programming Kali 2 1433 Last post 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 1521 Last post April 04, 2013, 11:14:50 PM
by Syntopia

Powered by MySQL Powered by PHP Powered by SMF 1.1.21 | SMF © 2015, Simple Machines

Valid XHTML 1.0! Valid CSS! Dilber MC Theme by HarzeM
Page created in 0.127 seconds with 27 queries. (Pretty URLs adds 0.006s, 2q)