DragonKIFS - promising formula but help needed

[Kali]

Some time ago I made this to test the possibility of making image-based IFS using flash:  (move the mouse over it to change fractal shape)

<a href="https://dl.dropbox.com/s/7h98zkj3pj3zlvm/ifs2.swf" target="_blank">https://dl.dropbox.com/s/7h98zkj3pj3zlvm/ifs2.swf</a>

I made it by using an array of movieclips and a recursive routine that makes two smaller copies of the previous generation of images, placed at 180º from each other (taking the base image as the center and the copies orbiting around it). Then the fractal is made easy, by simply changing the position angle of the copies after each iteration.

I wanted to see if I could make a 3D version of this fractal in Fragmentarium using baseshapes (i.e. spheres), but I encountered a problem as the GPU can't handle big arrays. Anyway, with the method I used in flash, anything beyond a few iterations gets really slower and memory consuming (you have to treat each of the parts that are duplicated as a variable and establish their scale and positions individually).

I moved to the idea of finding a folding for this kind of fractal, so I can make an escapetime version. And I found a way, but there's a problem...


I started from the simpler version of abs folding, that works this way:





(The example shows the first iteration of a fractal made of spheres that are drawn using min.DEcombinate method evaluated at each iteration, and I only take x-axis folding and 2D transforms to make the things simpler...)


So a fractal made with this folding iterates the following procedure:

- Fold X (abs)
- Scale
- Translate (constant C, as shown in the image, often called "Julia values")



After some iterations the result is:





And adding some rotation at each iteration:





With this method, the spheres from each side sometimes will overlap at the line of symmetry (as you can see in the example at the right), making a discontinuity in the baseshape used, but not in the fractal itself as each side always meets exactly the opposite (something you may always expect in a reflection transform ). So there are no shape/empty-space discontinuity.

Let's see what happens in the solution I found for the DragonKIFS folding:





So the iteration procedure is:

- If X>0, invert Y (Y=-Y)
- ABS(X)  (the reflected copy will be placed at 180º degrees because of the inversion of the other half of the fractal)
- Scale
- Translate (by C constant)
- Rotate
- Invert X (this gives the next copy the right orientation)


The result using some rotation angle is:






Seems to be working right, but...

If the iterated parts trespass the "abs barrier" formed by the axis of symmetry, this is what happens:





So you can see the fractal shape is truncated, also disturbing the distance estimator because of this discontinuity (I didn't made an image of the DE problem, but believe me )
Off course, as you can see, this also happens with all the child shapes at it's own abs fold axis.

Damn... never see it coming, even when it's obvious this was going to happen

However, using the pure escapetime version of the fractal, I managed to get some decent renderings... using "fudge factor" option of Fragmentarium and progressive rendering helped a lot with the DE trouble... and even I think the discontinuity contributes aesthetically sometimes...

But I still want to make the fractal right, in the way I was looking for. Also I want to make a proper baseshape version to be included in my KDIFS script, and it's when the DE issue is really a problem, because even when the fractal "arms" don't trespass the abs fold line, the DE fails when looking from certain angles... I guess this is caused by the discontinuity even in the empty space, because of the change of sign.


So, if someone has an idea on how to make it right, I'll appreciate your help. Keep in mind that I want only an escapetime version of it.

Thank you in advance!


In the posts below there are some quick renders I made to show the formula's potential, and there is another one in the gallery:

http://www.fractalforums.com/index.php?action=gallery;sa=view;id=12561

[Kali]

DragonKIFS - X version:






DragonKIFS - XY version:

[DarkBeam]

  Congrats, you found the good old 3D Barnsley. It is an old problem...

[Kali]

Congrats, you found the good old 3D Barnsley. It is an old problem...

Yep, it seems like I ended up with something similar to Mr. Barnsley's conditional formula, but I didn't think of it, I just made it as I show in the post.
Anyway I did a search and I didn't found any "3D Barnsley" image that looks remotely similar to the renderings I've done, and you call it the "good old 3D Barnsley", did I miss something?

[Kali]

I did a 3D version of the original Barnsley formula, and it does give some similar results indeed:





Original Barnsley multiplies by complex number which is the same as scaling+rotate so the simplified formula I used here is:

p.x=p.x-sign(p.x); // the same as (if x>0 x=x-1 else x=x+1) but more elegant
p*=Scale;
p*=Rotation;

Where "Rotation" is the 3D rotation matrix defined with rotationMatrix3 function in Fragmentarium


The discontinuities are somehow more noticeable with most params using this formula, not the same shapes can be achieved, and all in all I think my formula works better...
But yes, I have to admit that mine is a kind of 3D Barnsley, even when is not the same at all...

I insist, what I don't understand is, if it's a well-known 3D fractal, why I can't find other 3D Barnsley renders like this, or some references to this 3D version?

[DarkBeam]

My implements are not as sharp as yours, and it's hard to manage it. Your rensers are much more detailed.

[eiffie]

Kali could you try rotating the fold with each iteration instead? This may be a dumb idea but I will try it out.

[Kali]

Ok, I totally misunderstood what Darkbeam wrote, I thought he was being sarcastic, sorry Luca!
When he said the "good old 3D Barnsley" I interpreted that the results of my formula were something already known, but he meant it's an old problem to get a good 3D result of something like Barnsley conditional formula does in 2D. However Luca was pretty close with his 4D Barnsley in Mandelbulb3D.

Kali could you try rotating the fold with each iteration instead? This may be a dumb idea but I will try it out.

Yes, is one of the things I tried, but don't know if I did it right... maybe rotate, fold, and then rotateback?

[DarkBeam]

I report here my concept of what Barnsley formula does. Don't know it's really correct.

- A complex number can be thinked as an affine transform, simplified as rotation and scale (when we multiply), translation (when we add).
- In Julia mode, Barnsley formula is a pure IFS fractal;

  IF real(z) >= 0 // real(z) = x coordinate
    z = (z - 1) * pixel
  ELSE
    z = (z + 1) * pixel
  ENDIF

As pixel stays constant in J-mode this is a conditional translation, and an unconditional fixed rotation

  IF x >= 0
    z = z - 1 // translation
  ELSE
    z = z + 1 // translation
  ENDIF
    z = z * pixel // rotation

Hope this helps. In 3D we need a triple angle, and a 3D translation- easier said than done btw.

[DarkBeam]

uH! Just readed of your issue - it is (too) an old issue. The issue! The only way to solve it is to use a probabilistic approach; in other words, the fractal would be rendered as a cloud of pixels like in Incendia.

The method you are using is called "brute force", it does not work well for all kinds of transforms.

ps; there is also a way to work this around *but* it seems to be absolutely complicated. Dave Makin made a very accurate 2d formula but I simply can not understand it at all!

[Kali]

This are Fragmentarium .frag files for DragonKIFS and Barnsley3D formulas, including some presets.
Use with latest version: https://github.com/downloads/Syntopia/Fragmentarium/Fragmentarium%20Windows%20Binary%20v0.9.12b2.zip

[eiffie]

OK I finally found a "solution". But I doubt anyone will like it When we have a discontinuous cut plane (where the fractal follows different orders on either side) we can correct our DE by limiting the return value so we never jump to the other side of the plane but instead step nicely over the boundary a small amount then perform the next DE from that side.

The problem is that means making the formula linear and doing a strange combination of ray-marching/tracing. Here are examples:

Code:

float DistanceToPlane(vec3 p, vec3 nrm, vec3 rd)
{//exact distance to plane (from either side)
float t=-(dot(nrm,p))/dot(nrm,rd); //needs the ray direction!!!
if(t<0.0)return 1000.0;
return t;
}
float DDE(vec3 p, vec3 rd, out bool bHit) //the point to test, ray direction, did we hit the object or just a plane
{//directional distance estimate?!? (best or worst of two worlds?)
float dP=1000.0;
for (int i = 0; i < iters; i++) {
dP=min(dP,DistanceToPlane(p,normalize(c[i]),rd));
p-=c[i]*sign(dot(p,c[i]));//c is a precalculated array of offsets
}
float dS=max(0.0005,length(p)-radius);//leaving room for the calculation of a normal
bHit=(dS<0.001);//bHit tells if we hit the surface or we are just close to a cut plane
return min(dS,dP+0.00001);//step over the plane
}

There are some nice things about this - precalculated offsets so you do the math once, works with any discontinuous cut.
But also many bad things - need to make the formula linear (don't scale/rotate p just c), at high iterations the march becomes too slow (too many planes limiting movement).  
You could also scale and rotate the ray direction along with p. That would make calculating the distance to the plane simpler.
Whatever just wanted to show it can be done - the question is do we really want to?

[Kali]

Nice work, eiffie, all in all is a nice workaround, thanks for sharing!

[Kali]

I finally found a way to properly render a 3D dragon fractal made of base shapes in Fragmentarium.

I made this test image using spheres:



I used a section of the screen and the buffer to pre-calculate the positions of each generation of spheres. The colorful garbage you can see on the lower part of the image is the pre-generated data. It was kinda tricky to properly write and access the right pixels of each generation of spheres, but I think it's working fine.

Rendering times begin to really slow down at more than 9 iterations, as I expected,  but it's the only solution I found since I only know how to render using distance estimation.
Also the only optimization I found so far, was to check DE for the spheres on either side of the fractal at the same time, taking advantage of the symmetry so I only have to track positions of half of the spheres. The test image was 12 iterations, so it scans of the positions of 8000+ spheres but does a DE combination of 16000+ that are finally shown (thanks to the optimization).

I attached the .frag, it's a modification of "DE-Raytracer-v0.9.1.frag", and my code is mostly on the "main()" section, and in the included DE function, off course.
I added some comments to the code, but it's a mess and I barely understand it myself 

Be sure to run it in continuous mode to make it work, and use preview modes if it's running too slow. I recommend lowering the value of OpenGL refresh rate on edit->preferences for faster pre-calculation.

Any other suggestions are welcome.

[David Makin]

<snip?
ps; there is also a way to work this around *but* it seems to be absolutely complicated. Dave Makin made a very accurate 2d formula but I simply can not understand it at all!

The key with "my" method is that it is not KIFS, it's truly IFS - *the entire IFS tree* is traversed *per pixel* (and per ray position if in 3D to get DE values) so the entire tree is calculated only stopping going deeper on each path down the tree when a threshold scale factor is reached (for that path). I haven't actually written a 3D version using DE yet because I still haven't found a satisfactory "formula" for the DE when the transforms in the IFS are very different in scale (it's OK for 2D but so far from optimum I haven't even tried it for 3D yet).

For affine 3D IFS Hart's method is waaay better - DE is only needed for non-affine IFS - Hart's method again also does the entire tree per pixel but directly returns an intersectiion with the attractor or not - so no DE stepping required.