Logo by S Nelson - 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: Visit us on facebook
 
*
Welcome, Guest. Please login or register. March 29, 2024, 12:29:42 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: DE accuracy for IFS fractals  (Read 6308 times)
Description: Do distance estimators get less accurate with more iterations?
0 Members and 1 Guest are viewing this topic.
dom767
Explorer
****
Posts: 40


dom767
WWW
« on: April 15, 2015, 01:48:26 PM »

Hi folks,

I've been playing with kaleidoscopic IFS fractals for a while, and I'm just about to write up my findings. One of the more surprising things I've discovered is that as I increase the iteration count for the sierpinski pyramid, I have to multiply the distance estimate by an increasingly small factor to get a good render of the fractal. If I leave the distance estimate as is I end up skipping lots of detail in the fractal. The DE I'm using is based on the original code posted on the KIFS thread (http://www.fractalforums.com/ifs-iterated-function-systems/kaleidoscopic-%28escape-time-ifs%29/), my version being...

float bailout = 1000;
float r=pos.MagnitudeSquared();
int i;
for(i=0;i<iterations && r<bailout;i++){
   float tmp;

   if(pos[0]+pos[1]<0){tmp=-pos[1];pos[1]=-pos[0];pos[0]=tmp;}
   if(pos[0]+pos[2]<0){tmp=-pos[2];pos[2]=-pos[0];pos[0]=tmp;}
   if(pos[1]+pos[2]<0){tmp=-pos[2];pos[2]=-pos[1];pos[1]=tmp;}
      
   pos[0]=scale*pos[0]-offset[0]*(scale-1);
   pos[1]=scale*pos[1]-offset[1]*(scale-1);
   pos[2]=scale*pos[2]-offset[2]*(scale-1);
   r=pos.MagnitudeSquared();
}   

return (sqrtf(r)-2)*powf(scale,-float(i));//the estimated distance


With 20 iterations I typically have to multiply the return result by 0.2 to capture the bulk of the detail in the fractal. I've seen this with other recursive folding structures before so I'm not terribly surprised, but I did want to confirm that this is expected behaviour?

Regards,
Dom
Logged
eiffie
Guest
« Reply #1 on: April 15, 2015, 05:38:15 PM »

Your formula looks good and should not need any "fudgefactor". I suppose after 20 iterations you build up a loss of precision with floats??
Logged
youhn
Fractal Molossus
**
Posts: 696


Shapes only exists in our heads.


« Reply #2 on: April 15, 2015, 08:41:29 PM »

Yes, increasing the iteration count makes the whole thing more and more like cantor dust, but in 3D. Details increase, but volume could shrink till zero. So when the detail size drops below the pixel size, then you need more pixels (or less iterations).

Indeed you could change the some parameter (which I think is called "Detail level" in Mandelbulber, and "DE Stop" in Mandelbulb 3D). Increase for longer render times, finer details but less volume. Decreasing gives shorter render times, blown up details (which of course have more volume). I always think the DE calculation draws a virtual sheet over the "real" fractal shape. Detail param is like the thickness and flexibility of the sheet, either pulling it tighter around the fractal or blowing it up like a balloon (try huge multiply value, with high resolution and high iteration). This is NOT the same parameter as the multiplier (which

Example A on the Burning Ship fractal
Detail level = 10


Example A on the Burning Ship fractal
Detail level = 0.1


Both rendered with:
Iteration = 499
Ray step multiplier = 0.6
Smoothness = 1
Resolution = 2400 x 2400 px
Logged
youhn
Fractal Molossus
**
Posts: 696


Shapes only exists in our heads.


« Reply #3 on: April 15, 2015, 08:43:13 PM »

What resolution do you render? Can you show an example of what you want, and another example on what you got?
Logged
dom767
Explorer
****
Posts: 40


dom767
WWW
« Reply #4 on: April 16, 2015, 09:14:45 AM »

Hi all,

Thanks for the replies. I spent some time last night trying to get a few screenshots of the problem i was seeing yesterday but frustratingly i can't reproduce it any more. I did do some refactoring of the code last night so perhaps i unbroke it on the final pass...

Apologies!

The only issue that is now evident is that the fudge factor is important for getting nice precise renderings close to the fractal but that's just down to how my raymarcher works. Basically it bails out as soon as the distance estimate is less than 0.001. With a fudge factor of 1.0 that means that separate rays will show some noise near the surface or the fractal. With overshoots (de <0 I march back to find the surface, but if the distance estimate is very close to the surface I just return that point as the collision point.

Youhn, I'm not sure what detail level corresponds to in my code. Is that the minimum value the raymarcher is looking for?
Logged
David Makin
Global Moderator
Fractal Senior
******
Posts: 2286



Makin' Magic Fractals
WWW
« Reply #5 on: April 16, 2015, 01:59:53 PM »

The threshold for solid found needs to be related to the pixel size and in the case of perspective 3D this means that it needs to change based on distance from viewpoint - i.e. you can't just use a single fixed value for the threshold and expect to get correct detail scaling throughout.
The closer to viewpoint the smaller the threshold required and vice-versa - ideally the value should be calculated so that at all distances the threshold is somewhere between 0.5 and 1.5 pixels with respect to the image.
Logged

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

http://www.fractalgallery.co.uk/
"Makin' Magic Music" on Jango
dom767
Explorer
****
Posts: 40


dom767
WWW
« Reply #6 on: April 16, 2015, 03:50:57 PM »

That's interesting, I hadn't thought of doing that before.

Isn't there a danger that distant parts of fractal objects will appear to be more solid? Are any of the existing DE apps out there using this type of algo?
Logged
David Makin
Global Moderator
Fractal Senior
******
Posts: 2286



Makin' Magic Fractals
WWW
« Reply #7 on: April 16, 2015, 03:56:09 PM »

That's interesting, I hadn't thought of doing that before.

Isn't there a danger that distant parts of fractal objects will appear to be more solid? Are any of the existing DE apps out there using this type of algo?

No, not provided you get the relative pixel size calculation correct and yes, at least my formulas for UF do this -  not sure about anyone else's software (except I think Xenodream does it).
Logged

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

http://www.fractalgallery.co.uk/
"Makin' Magic Music" on Jango
youhn
Fractal Molossus
**
Posts: 696


Shapes only exists in our heads.


« Reply #8 on: April 16, 2015, 05:30:09 PM »

Youhn, I'm not sure what detail level corresponds to in my code. Is that the minimum value the raymarcher is looking for?

I'm no programmer. My coding skills somewhere between hacking and writing. Did managed to get some formulas into Mandelbulber (not MB3D), but never really dove into the DE calculation enough. Let' see were the variable is being used;

Code:
//calculation of distance where ray-marching stops
double cRenderWorker::CalcDistThresh(CVector3 point)
{
double distThresh;
if (params->constantDEThreshold)
distThresh = params->DEThresh;
else
distThresh = (params->camera - point).Length() * params->resolution * params->fov / params->detailLevel;
if(params->perspectiveType == params::perspEquirectangular || params->perspectiveType == params::perspFishEye || params->perspectiveType == params::perspFishEyeCut) distThresh *= M_PI;
distThresh /= data->reduceDetail;
return distThresh;
}

and another piece in the same source file:

Code:
//Ray-Marching
CVector3 cRenderWorker::RayMarching(sRayMarchingIn &in, sRayMarchingInOut *inOut, sRayMarchingOut *out)
{
CVector3 point;
bool found = false;
double scan = in.minScan;
double dist = 0;
double search_accuracy = 0.01 * params->detailLevel;
double search_limit = 1.0 - search_accuracy;
int counter = 0;
double step = 0.0;
(*inOut->buffCount) = 0;
double distThresh;
//qDebug() << "Start ************************";
for (int i = 0; i < 10000; i++)
{

(too long, so removed the rest. See link to source here below)

Source: https://github.com/buddhi1980/mandelbulber2/blob/master/mandelbulber2/src/render_worker.cpp

I'm not sure what's going on, but hopefully this will be of help for you.
Logged
dom767
Explorer
****
Posts: 40


dom767
WWW
« Reply #9 on: April 17, 2015, 09:01:13 AM »

Hi youhn,

Thanks for digging into it. I think this is related to the algorithm that David mentioned so yes, it's the equivalent of changing the minimum distance on my raymarcher.
Logged
Imagyx
Navigator
*****
Posts: 72


Finally 3D and more... Thank you !! ;-)


« Reply #10 on: May 15, 2016, 04:23:09 PM »

I found this very useful in my mind and hope to optimize my own code with the idea of a adjusted threshold.
If anyone here uses such an adjusted threshold, could you please tell me, what is missing in the line with huh? in my code?
The problem is, that a menger sponge or mandelbox gets ugly far from the camera, where the front parts are ok.
Like the picture below.

Or with a really small threshold it turns into dust.

Code:
public void intersect(Ray r, double ncp, double fcp, RaymarcherCore core) {//Ray, near and far clipping planes, multicore functionality

double t0 = 0.0;//sum over stepping distances along the ray
int k = 0;//numSteps
for(; k < maxRaySteps ; k++){
V3D next = r.orig.getAdd(r.dir.mult(t0));//calculate next position along the ray
double dist = DE(next);//call distance estimation function
if(dist < epsDE){// WHAT TO TO HERE ??? epsDE is a predefined threshold, for example 0.001
break;
}
t0 += dist;
}
r.numSteps += k;
if(k >= maxRaySteps || t0 <= ncp){
t0 = Double.POSITIVE_INFINITY;
}else if(r.tNear > t0){
                     //found an object
}
}

I hope my intersection code is explained enough.
Otherwise please ask.
Thank you.


* Raymarcher_2016.05.15_16.18.36.jpg (110.89 KB, 600x400 - viewed 153 times.)
Logged

During difficult times, keep steady and play the match.
eiffie
Guest
« Reply #11 on: May 16, 2016, 02:56:10 AM »

There are a number of things you can do to "fill in" the black areas if that is what you are talking about.
1) obviously more steps
2) let epsDE increase with distance. Something like ps=pixelsize,  epsDE=ps*t0; //pixelsize can be 1.0/imageWidth or Height or whatever looks good
3) just because k>maxRaySteps doesn't mean you have to treat it as missing everything, you can fudge and accept anything that came close to the surface - you will have the opposite problem of the menger being somewhat rounded at the corners. This brings you back to 1. (use more steps)

If this is CPU code you might want to take samples whenever dist < epsDE but continue marching! keeping track of an alpha (like you were marching thru a density). It will give you a nice AA look.
Logged
Imagyx
Navigator
*****
Posts: 72


Finally 3D and more... Thank you !! ;-)


« Reply #12 on: May 17, 2016, 08:56:04 AM »

First thank you very much for your effort eiffie.
Increasing epsDE with distance actually fills the black holes in the back.
About the number of steps I'm not so sure, what a default value is, that you or any other expert here use.
I used 100 steps in the picture I posted and now 200 in the current image with your suggestions already used in the code.
It looks a lot better. Also I use a four/eight star adapted AA, especially for noisy images like fractals.
It depends on the number of steps used. For example with a value between 0.1 and 0.4 only
parts of the image where 10 to 40 % of the maxSteps are necessary, AA is activated.
(4star / 8star meaning:
-*-
*+*
-*-

and

***
*+*
***

where * are AA samples, + is the actual pixel and - not used. )
As you assumed it is CPU code, I wrote my own raytracer in Java which gives me all the possibilities to change
whatever I want in the process. And I like to learn a lot about CG, fractals and optimization.
I created a lot of new parameters from your suggestions, e.g. the pixelsizefactor, a fugdefactor for nearly missed surfaces.
All that's left for me to do is playing around with these new parameters to find the best combination for  a good image with reasonable rendertimes.
And I'm not sure how to understand the last part of your answer.
By going a bit further after dist<epsDE,  what do I do there ?

Pictures:
1) Default render
2) number of steps used, dark=few, white=many
3) AO


* P3D_2016.05.17_08.50.47.jpg (82.37 KB, 450x300 - viewed 534 times.)

* P3D_2016.05.17_08.51.16.jpg (52.69 KB, 450x300 - viewed 516 times.)

* P3D_2016.05.17_08.51.50.jpg (75.49 KB, 450x300 - viewed 558 times.)
Logged

During difficult times, keep steady and play the match.
eiffie
Guest
« Reply #13 on: May 17, 2016, 12:13:16 PM »

I will try to explain the multi-sampling I'm talking about. When you do traditional AA (your 4/8 star) you have to start marching all over again so 4/8 times slower. Instead every time the surface comes within a pixel you calculate the pixel coverage. It the surface does not cover the pixel completely you continue marching and blend the surface colors together (like marching thru a density if you have every seen code for clouds).
Here is some simple untested code...
Code:
double t0 = 0.0, eps=1.0/width, opacity=0.0;//when opacity hits 1.0 then the surface is opaque. (also called alpha)
int k = 0;//numSteps
V3D color=V3D(0.0, 0.0, 0.0);//assuming you can initialize
for(; k < maxRaySteps ; k++){
V3D next = r.orig.getAdd(r.dir.mult(t0));//calculate next position along the ray
double dist = DE(next);//call distance estimation function
if(dist < eps*t0){
V3D newColor=GetMaterialAndLighting(r,next);//whatever code you have to light the scene will be run multiple times
double alpha=(1.0-opacity)*clamp(1.0-dist/(eps*t0),0.0,1.0); //I am using some glsl functions, clamp means min(max(x,0.0),1.0)
color+=newColor*alpha;
opacity+=alpha;
if(opacity>0.95)break;//close enough to opaque
}
t0 += dist;
}
Again this isn't tested and I tend to make typos, hopefully you get the idea of keeping track of the pixel's alpha value.
This should really help in those distance areas as in the center of your last pic.
Logged
Imagyx
Navigator
*****
Posts: 72


Finally 3D and more... Thank you !! ;-)


« Reply #14 on: May 17, 2016, 05:48:35 PM »

Awesome !!!

Your code explains all I need to understand your approach.
I had to move some parts of my code around and change a few things to fit
in the GetMaterialAndLighting() method with all object oriented stuff around it
but I think I'll write a new raytracer some day anyway which combines all I've learned so far.
The new code also reduces rendering time  a lot, as you mentioned  smiley
Much of the noise in my previous pictures seems to come from lighting calculations because
the AO alone looks way better than a lit scene.
The best result for now is this:

Thanks a lot for the trouble.
I'll see what else I can optimize.


* P3D_2016.05.17_17.23.19.jpg (152.66 KB, 600x400 - viewed 207 times.)
Logged

During difficult times, keep steady and play the match.
Pages: [1]   Go Down
  Print  
 
Jump to:  

Related Topics
Subject Started by Replies Views Last post
fractals r us Meet & Greet woodlands 3 6366 Last post October 09, 2006, 03:53:14 PM
by alan2here
two b&w 3d fractals 3D Fractal Generation lycium 0 5411 Last post August 25, 2007, 12:16:05 AM
by lycium
Relationship between bailout and accuracy of analytical DE Programming David Makin 1 6602 Last post April 08, 2010, 02:56:03 AM
by reesej2
Area of fractals - Area of quasifuchsian grandma fractals (new) Theories & Research hgjf2 7 1315 Last post July 26, 2014, 02:14:22 PM
by hgjf2
accuracy of glitch detection? Kalles Fraktaler claude 2 9821 Last post May 09, 2017, 05:00:10 PM
by claude

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