Logo by teamfresh - 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. January 30, 2023, 07:56:23 PM


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: Improved delta-DE algorithm  (Read 2446 times)
0 Members and 1 Guest are viewing this topic.
Buddhi
Fractal Iambus
***
Posts: 895



WWW
« on: August 15, 2013, 03:38:02 PM »

Hi
Because rendering on GPU has limitation for calculation accuracy (mostly possible to use only floats), I had to redesign a little delta-DE algorithm. Standard 4-point delta-DE needs delta lower about 1000 times than distance threshold. With single rescission floating point numbers the lowest acceptable delta is anout 1e-6. Lower value produces big numeric errors. Higher gives artifacts in areas where DE is not continuous function. With this limitation there was not possible to get images with magnification higher than 1e3.
To improve delta-DE algorithm I decided to use additional 3 points. It's better to calculate deltas in positive and negative direction and use lower value of them. Then non-continuous areas of DE are eliminated.

Below there is a code which I use actually in Mandelbulber-OpenCL
 
Code:
formulaOut CalculateDistance(__constant sClInConstants *consts, float3 point, sClCalcParams *calcParam)
{
float distance;
float delta = 1e-6;
float3 dr = 0.0;
formulaOut out = Fractal(consts, point, calcParam);

if (out.iters == calcParam->N)
{
distance = 0.0f;
}
else
{
float r = out.distance;
float r11 = Fractal(consts, point + (float3) { delta, 0.0, 0.0}, calcParam).distance;
float r12 = Fractal(consts, point + (float3) { -delta, 0.0, 0.0}, calcParam).distance;
dr.x = min(fabs(r11 - r), fabs(r12 - r)) / delta;
float r21 = Fractal(consts, point + (float3) { 0.0, delta, 0.0}, calcParam).distance;
float r22 = Fractal(consts, point + (float3) { 0.0, -delta, 0.0}, calcParam).distance;
dr.y = min(fabs(r21 - r), fabs(r22 - r)) / delta;
float r31 = Fractal(consts, point + (float3) { 0.0, 0.0, delta}, calcParam).distance;
float r32 = Fractal(consts, point + (float3) { 0.0, 0.0, -delta}, calcParam).distance;
dr.z = min(fabs(r31 - r), fabs(r32 - r)) / delta;
float d = length(dr);
}
out.distance = distance;
return out;
}

where Fractal().distance returns last z value from fractal formula iterations.


* old.jpg (81.39 KB, 400x300 - viewed 679 times.)

* inproved.jpg (50.42 KB, 400x300 - viewed 711 times.)
Logged

Roquen
Iterator
*
Posts: 180


« Reply #1 on: August 15, 2013, 05:19:30 PM »

It would seem desirable to have the delta be a value with no significant bits (a power of two) so you can convert the divide into a multiple and remove one rounding error from the process.  Simple to implement since CL support hex constants.  The closest to the current would be: 0x1.0-20f
Logged

All code submitted by me is in the public domain. (http://unlicense.org/)
eiffie
Guest
« Reply #2 on: August 15, 2013, 05:41:10 PM »

Thanks for this improvement!
Logged
lycium
Fractal Supremo
*****
Posts: 1158



WWW
« Reply #3 on: August 15, 2013, 08:15:04 PM »

Using central-differences as you do turns the error in Taylor series from O(h) to O(h^2). Roquen's suggestion suggests he's pretty experienced in numerical methods, right on the money! smiley

More info here: http://en.wikipedia.org/wiki/Finite_difference
Logged

Roquen
Iterator
*
Posts: 180


« Reply #4 on: August 15, 2013, 08:40:17 PM »

Another random though is to make the delta adaptive.  So:  norm = dot(p,p); delta = nextAfter(norm)-norm;  then multiple delta some small power of two to allow for compounding errors in the computation of the function.
Logged

All code submitted by me is in the public domain. (http://unlicense.org/)
Syntopia
Fractal Molossus
**
Posts: 681



syntopiadk
WWW
« Reply #5 on: August 15, 2013, 10:13:46 PM »

Using central-differences as you do turns the error in Taylor series from O(h) to O(h^2). Roquen's suggestion suggests he's pretty experienced in numerical methods, right on the money! smiley

More info here: http://en.wikipedia.org/wiki/Finite_difference

I don't think it is a central-difference. Buddhi calculates both a forward and a backwards difference, and chooses the minimum of these two.

Buddhi, could you make a central-differences image for comparison? I think that would be just:
Code:
dr.x = (r11 - r12) / (2.0*delta); // sign doesn't matter
Logged
Roquen
Iterator
*
Posts: 180


« Reply #6 on: August 15, 2013, 10:22:06 PM »

My concrete mathematics is weak, but isn't the error analysis similar?  BTW: My thinking about the adaptive delta is if that were to work, I'd be curious if an intermediate difference might be sufficient...and thus drastically increase performance.
Logged

All code submitted by me is in the public domain. (http://unlicense.org/)
Buddhi
Fractal Iambus
***
Posts: 895



WWW
« Reply #7 on: August 16, 2013, 06:59:50 PM »

Central-difference doesn't help at all. I have changed delta-DE algorithm not to reduce numeric errors but to eliminate artifacts caused by steps of z value. In places where z (in function of fractal coordinates) is not continuous the length(dz) is quite high. Then in those places calculated estimated distance is very low. Ray-marching algorithm sees in those places fake objects (lower distance than threshold) so we have artifacts. When I use minimum value of two directions then the algorithm uses more proper value of delta. Even if there is a step of z value, one of deltas has to be not in the place where is this step (will be just behind or just in front of it).
In attached file there is a result with central-difference


* central-difference.jpg (118.9 KB, 400x300 - viewed 616 times.)
Logged

lycium
Fractal Supremo
*****
Posts: 1158



WWW
« Reply #8 on: August 16, 2013, 07:33:33 PM »

That's very interesting, thanks for the render Buddhi! And good catch Syntopia, I didn't look closely enough at the not-central-differences smiley
Logged

Roquen
Iterator
*
Posts: 180


« Reply #9 on: August 16, 2013, 08:25:40 PM »

My thoughts are always worth about what you paid for the them...and I have very little (read none) experience at the real topic at hand.  My thinking wasn't really about precision for precision sake, but as a potential means to increase robustness of the computation and if by chance computational complexity could be reduced...that would be added bonus.

An example to be slightly clearer to a wider audience.  If you have delta = 1e-6f, then any value X with |X|>= 16, X + delta = X.  And conversely if X is small, then delta becomes quite large.  If |X| is on [8,16) then the lowest bit will be changed, [4,8) the second to lowest, etc.  Now it's very easy to formula simple equations which burn through valid bits, so just because the input has been effected by the sum (or difference) doesn't imply that the returned result isn't more noise than signal.
Logged

All code submitted by me is in the public domain. (http://unlicense.org/)
Pages: [1]   Go Down
  Print  
 
Jump to:  

Related Topics
Subject Started by Replies Views Last post
Delta DE limits 3D Fractal Generation David Makin 5 2416 Last post October 24, 2009, 05:35:30 PM
by David Makin
Delta Sunset Mandelbulb3D Gallery lenord 0 835 Last post December 17, 2010, 01:12:15 AM
by lenord
Delta Images Showcase (Rate My Fractal) Kali 6 1047 Last post June 27, 2012, 06:28:37 AM
by Kali
Hybri-Station on Delta 4 Images Showcase (Rate My Fractal) JoeFRAQ 1 723 Last post October 31, 2014, 02:09:53 AM
by JohnVV
Orange Delta Images Showcase (Rate My Fractal) C.K. 4 680 Last post January 11, 2015, 06:46:21 PM
by C.K.

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.191 seconds with 24 queries. (Pretty URLs adds 0.014s, 2q)