Logo by Pauldelbrot - Contribute your own Logo!
News: Visit the official fractalforums.com Youtube Channel
 
*
Welcome, Guest. Please login or register. September 23, 2017, 06:12:48 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] 2 3   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: A new? Simple way to compute DE for any trig. Mandelbulb  (Read 7061 times)
0 Members and 1 Guest are viewing this topic.
mrrgu
Guest
« on: January 04, 2010, 02:13:11 PM »

Hello

Found a simple way to compute DE for trig. mandelbulbs.
I think it is new since I have not seen it on the forums?
I mention it anyway.

It is based on:

Dist = 0.5*|Zn|*log(|Zn|)/|DZn|

and

Zn+1 = Zn^P +C

DZn+1 = P*Zn^(P-1)*DZn +1

Thus nothing new so far!!

What is new (i think?) is the way to compute the product P*Zn^(P-1)*DZn

With Zn+1 defined as follows (wikipedia like def. of spherical coordinates, works with usual def. to.)
-----------------------------------------------------------------------------------------------
r=length(Zn)
t=acosf(Zn.z/r)
p=atan2f(Zn.y,Zn.x)

st = (r^P)*sin(P*t)

Zn+1.x = st*cos(P*p)+C.x
Zn+1.y = st*sin(P*p)+C.y
Zn+1.z = cos(P*t)*r^P+C.z

Now the derivative DZn+1 is:

l = length(DZn)

t = t *(P-1) + acos(DZn.z/l)
p = p*(P-1) + atan2(DZn.y,DZn.x)

rd = l*P*r^(P-1)

st = rd*sin(t)

DZn+1.x = st*cos(p)+1
DZn+1.y = st*sin(p)
DZn+1.z = cos(t)*rd


Thus I add the angles of Zn-1^P and DZn together and multiply their lengths..
to create the product vector. Exactly the  same way you can do for complex vectors.

I have tested it for the Z^2 mandel bulb and it works  grin

I had to set:

DZ0 = (0,0,1)

To  get correct results.. if you use different def. of spherical coords you might need to try (1,0,0) and (0,1,0).

Also I set Z0 = C.

Can not show results yet, cause I am on a 44kbit modem  sad at the moment.





« Last Edit: January 04, 2010, 02:35:30 PM by mrrgu » Logged
David Makin
Global Moderator
Fractal Senior
******
Posts: 2286



Makin' Magic Fractals
WWW
« Reply #1 on: January 04, 2010, 02:33:55 PM »

That's essentialy what's being used wink

You should also note that because there is no "+1" involved in the derivative for Julia Sets of the form a*z^p+c then all you actually need is the running product of the magnitude i.e. you just do:

Dr = Dr*length(Zn)

where initial Dr is 1.0

Of course that optimisation won't adapt for exp(z)+c or z^p+z^p1+c etc.
Logged

The meaning and purpose of life is to give life purpose and meaning.

http://www.fractalgallery.co.uk/
"Makin' Magic Music" on Jango
mrrgu
Guest
« Reply #2 on: January 04, 2010, 02:39:23 PM »

Ok..so it was not new  sad Took me a week to figure it out..  smiley
You say essentially..what is done different?
« Last Edit: January 04, 2010, 02:42:32 PM by mrrgu » Logged
David Makin
Global Moderator
Fractal Senior
******
Posts: 2286



Makin' Magic Fractals
WWW
« Reply #3 on: January 04, 2010, 02:52:37 PM »

Well I'm pretty sure I'm using a start for the running derivative of (1,0,0) in all cases and assuming you're starting with initial z as (0,0,0) then that's correct since on the first iteration for the Mandelbrot you get 0 + 1 for the running derivative anyway.

« Last Edit: January 04, 2010, 02:55:45 PM by David Makin » Logged

The meaning and purpose of life is to give life purpose and meaning.

http://www.fractalgallery.co.uk/
"Makin' Magic Music" on Jango
mrrgu
Guest
« Reply #4 on: January 04, 2010, 03:23:13 PM »

I see.
Im not sure why I need different start values..but it looks alright in the end.

Why did you make that binary search algorithm for DE when you can use this method?
Is binary search better ?
Logged
David Makin
Global Moderator
Fractal Senior
******
Posts: 2286



Makin' Magic Fractals
WWW
« Reply #5 on: January 04, 2010, 06:16:26 PM »

I see.
Im not sure why I need different start values..but it looks alright in the end.

Why did you make that binary search algorithm for DE when you can use this method?
Is binary search better ?

I think you're confusing my delta DE method and using a binary search when solid is hit ?

I created the delta DE method for formulas other than the Mandelbulb before Paul Nylander extended Daniel White's original formula to higher powers finding the Mandelbulb - the other formulas concerned, although simple, are not so easy to get the analytical derivatives for - in fact for the Mandelbrot version they really need the full Jacobian which is both complicated and slow to calculate.
I used the delta DE method for my earlier renders of the Mandelbulb because it worked and because I'm a little lazy when it comes to maths (rather than programming) and I waited for someone else to come up with an analytical DE for the Mandelbulb using the derivative (I'm not sure who came up with that first but Jos Leys described it to me).

As for the binary search - that's a separate subject, when you use DE (delta or derivative) but you set the solid threshold to a high value, i.e. for a low resolution render, then without using a binary search (by initially stepping backwards 1/2 the last step when solid is hit) you get "stepping" in the render.

I should add that for some renders of the Mandelbulb using the latest optimised version of my Ultra Fractal formula (not released yet) then in some cases using delta DE is actually faster than using derivative DE - but not when using the magnitude only method for the derivative.

I should add that the delta DE method will work with *any* formula that you can get accurate smooth iteration values for.

« Last Edit: January 04, 2010, 06:20:00 PM by David Makin » Logged

The meaning and purpose of life is to give life purpose and meaning.

http://www.fractalgallery.co.uk/
"Makin' Magic Music" on Jango
Buddhi
Fractal Iambus
***
Posts: 885



WWW
« Reply #6 on: January 04, 2010, 08:56:32 PM »

Hi

Because analytic DE method is limited to fractals where we can find analytic derivatives, yesterday I tried to fight with delta DE methods. David, I tried to analyse your delta DE method but I can't understand some issues (for example I don't know how to calculate smooth iteration value). I decided to find method by myself.
In my method I calculate central difference instead of analytic derivative of z value, using z value for two point in very close distance (1e-10). I will describe my method in following pseudo-code:

delta = 1e-10
z1 = CalculateIterations(a,b,c)            //z1, z2 last values of z (after last iteration)
z2 = CalculateIterations(a+delta,b,c)   // I tried also (a+delta, b+delta, c+delta)
r = |(z1+z2)/2|
dr = |z2 - z1| / delta
distance = r * log(r) / dr

I tried this method in my 3D rendered. It works but there was lots of artifacts. I attached result ("delta DE test.jpg")

I made some investigations and tests on 2D slices. This method works very fine only for plane z = 0. When I tried to render another slices, for example z = 0.1 there was artifacts. I fought that I made some mistake in program but I tested it on quaternionic formula. For quaternions it works fine in full range of z.
I attached results of tests. On left side there are slices for z = 0 and on right side for z = 0.1.

David, you have very big experience with delta DE method. Do you know what I'm doing wrong?


* delta DE test.jpg (441.27 KB, 640x640 - viewed 308 times.)

* DE compare.png (232 KB, 640x1280 - viewed 324 times.)

* DE compare 2.png (133.96 KB, 800x800 - viewed 331 times.)
Logged

David Makin
Global Moderator
Fractal Senior
******
Posts: 2286



Makin' Magic Fractals
WWW
« Reply #7 on: January 04, 2010, 09:21:45 PM »


David, you have very big experience with delta DE method. Do you know what I'm doing wrong?


I think so, you need to use 2 points *on the ray* i.e. at vp + alpha*d (the current step position) and vp + (alpha+1e-10)*d because the method you're using (like mine) is directional unlike the analytical method which gives the minimum distance in any direction.

(vp = viewpoint (ray start), alpha = step, d = ray's unit direction vector)

As to the smooth iteration value, use:

smooth = final iter + 1 + (log(log(bailout))-log(log(final magnitude)))/log(power)

Or (for much more accurate results) instead of log(power) use log(log(|z|)/log(|zold|)) when final iter is >1 (where zold is the penultimate value of z i.e. z from the iteration prior to bailout).

Actually for delta DE purposes because the difference of the 2 smooth iteration values is actually used then when using /log(power) then both the +1 term and the log(log(bailout)) term can be omitted - if using the log(log(|z|)/log(|zold|)) method then the +1 can be omitted but not the bailout term. I don't omit anything in my code because the overhead is small anyway and often the full correct iteration value will be needed for colouring.
Note that the +1 term is only required anyway if bailout on the first iteration results in a final iter of zero rather than 1.


Logged

The meaning and purpose of life is to give life purpose and meaning.

http://www.fractalgallery.co.uk/
"Makin' Magic Music" on Jango
mrrgu
Guest
« Reply #8 on: January 04, 2010, 09:41:42 PM »

I begin to understand the history..

Why can you just not step back a half step and set the threshold to a lower value.. ?
I guess I dont understand fully..that would be the same as having a low thresold to begin with or..



I see.
Im not sure why I need different start values..but it looks alright in the end.

Why did you make that binary search algorithm for DE when you can use this method?
Is binary search better ?

I think you're confusing my delta DE method and using a binary search when solid is hit ?

I created the delta DE method for formulas other than the Mandelbulb before Paul Nylander extended Daniel White's original formula to higher powers finding the Mandelbulb - the other formulas concerned, although simple, are not so easy to get the analytical derivatives for - in fact for the Mandelbrot version they really need the full Jacobian which is both complicated and slow to calculate.
I used the delta DE method for my earlier renders of the Mandelbulb because it worked and because I'm a little lazy when it comes to maths (rather than programming) and I waited for someone else to come up with an analytical DE for the Mandelbulb using the derivative (I'm not sure who came up with that first but Jos Leys described it to me).

As for the binary search - that's a separate subject, when you use DE (delta or derivative) but you set the solid threshold to a high value, i.e. for a low resolution render, then without using a binary search (by initially stepping backwards 1/2 the last step when solid is hit) you get "stepping" in the render.

I should add that for some renders of the Mandelbulb using the latest optimised version of my Ultra Fractal formula (not released yet) then in some cases using delta DE is actually faster than using derivative DE - but not when using the magnitude only method for the derivative.

I should add that the delta DE method will work with *any* formula that you can get accurate smooth iteration values for.


Logged
Buddhi
Fractal Iambus
***
Posts: 885



WWW
« Reply #9 on: January 04, 2010, 10:01:55 PM »

Binary search is for finding exact place where distance equals to DE threshold. Last DE step is always little too close (distance is less than DE threshold) and you have to cancel last step and go half step forward and check distance. When distance is to high you have to go forward or when distance is too small you have to go back again. In my programs I'm ending searching when distance is in range 90% - 100% of DE threshold. It is completely enough for all shading algorithms.
Logged

Buddhi
Fractal Iambus
***
Posts: 885



WWW
« Reply #10 on: January 04, 2010, 10:12:13 PM »

I think so, you need to use 2 points *on the ray* i.e. at vp + alpha*d (the current step position) and vp + (alpha+1e-10)*d because the method you're using (like mine) is directional unlike the analytical method which gives the minimum distance in any direction.

Thanks David for reply.
In my 3D renderer I used direction vector for delta. I also tested different directions of delta vector on slices but it always looks nearly the same. Very interesting for me is that it works properly for z = 0 and quaternions. I think our 3D/4D number systems don't have authentic derivatives and this a reason of artefacts.  Only complex numbers and quaternions has derivatives - analytical and accurate numerical.

I will try with smooth iteration values according to your description.
Logged

David Makin
Global Moderator
Fractal Senior
******
Posts: 2286



Makin' Magic Fractals
WWW
« Reply #11 on: January 04, 2010, 10:24:47 PM »

I begin to understand the history..

Why can you just not step back a half step and set the threshold to a lower value.. ?
I guess I dont understand fully..that would be the same as having a low thresold to begin with or..


Yes, that would be the same as having a low threshold to begin with smiley

Sometimes setting the DE large enough to avoid aliasing causes the stepping i.e. setting the DE threshold too small on a lower resolution image can cause aliasing but if you set it too high then you can get stepping.

Here's a gross example of the difference on a DE threshold animated quaternion (note that with my latest code the jagged artifacts on the version using the binary search have gone altogether):

http://makinmagic.deviantart.com/art/Plain-DE-animation-127361800

http://makinmagic.deviantart.com/art/Using-DE-Binary-Search-127362040
« Last Edit: January 04, 2010, 10:27:02 PM by David Makin » Logged

The meaning and purpose of life is to give life purpose and meaning.

http://www.fractalgallery.co.uk/
"Makin' Magic Music" on Jango
David Makin
Global Moderator
Fractal Senior
******
Posts: 2286



Makin' Magic Fractals
WWW
« Reply #12 on: January 04, 2010, 10:34:07 PM »

Thanks David for reply.
In my 3D renderer I used direction vector for delta. I also tested different directions of delta vector on slices but it always looks nearly the same. Very interesting for me is that it works properly for z = 0 and quaternions. I think our 3D/4D number systems don't have authentic derivatives and this a reason of artefacts.  Only complex numbers and quaternions has derivatives - analytical and accurate numerical.

I will try with smooth iteration values according to your description.

Have you implimented the array to check that the new step distance is not greater than the current minimum for that iteration count on the ray ?
Without that you'll always get gross overstepping in some places when using the delta method.
Logged

The meaning and purpose of life is to give life purpose and meaning.

http://www.fractalgallery.co.uk/
"Makin' Magic Music" on Jango
Buddhi
Fractal Iambus
***
Posts: 885



WWW
« Reply #13 on: January 04, 2010, 11:11:20 PM »

Have you implimented the array to check that the new step distance is not greater than the current minimum for that iteration count on the ray ?
Without that you'll always get gross overstepping in some places when using the delta method.

No, I didn't implemented it. But I think for it I have to change final condition if I implement it. Now I'm searching fractal boundary until I achieve proper distance. Maybe will it be better when I finish searching when I find required value of iteration count? Now when my program meets some place where there is wrong value of distance (for example iteration count in this place is very low) and this is unfortunately lees than distance threshold, it finishes searching. When DE values are accurate everything is very simple but for power 2 fractals unfortunately are very inaccurate, also analytical.
Tomorrow I will try also with smooth iteration value instead of last value of z.
Logged

mrrgu
Guest
« Reply #14 on: January 05, 2010, 02:57:49 PM »

I see.
What about setting a scale factor for DE that underestimates the distance more?
Or will it still overestimate the last step if you scale ?

Binary search is for finding exact place where distance equals to DE threshold. Last DE step is always little too close (distance is less than DE threshold) and you have to cancel last step and go half step forward and check distance. When distance is to high you have to go forward or when distance is too small you have to go back again. In my programs I'm ending searching when distance is in range 90% - 100% of DE threshold. It is completely enough for all shading algorithms.

Logged
Pages: [1] 2 3   Go Down
  Print  
 
Jump to:  

Related Topics
Subject Started by Replies Views Last post
Simple 2D IFS animation Movies Showcase (Rate My Movie) David Makin 0 805 Last post December 09, 2006, 11:41:48 PM
by David Makin
Plain and Simple Mandelbulb3D Gallery lenord 0 331 Last post February 27, 2011, 07:14:47 PM
by lenord
Non-trig expansion for RuckerBrot? Help & Support DarkBeam 1 831 Last post March 16, 2011, 01:41:42 PM
by DarkBeam
Does anyone know a trick to compute the derivative of Mandelbrot ? General Discussion tit_toinou 9 1788 Last post April 02, 2012, 03:53:12 AM
by David Makin
VTune Results; Compute vs. CVector3::IsNotANumber. Mandelbulber mancoast 0 433 Last post August 03, 2016, 03:42:16 AM
by mancoast

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.361 seconds with 29 queries. (Pretty URLs adds 0.017s, 2q)