3D Barnsley ferns and firs

[Alef]

Is it possible to have a solid 3D barnsley fern?

There are one 2D fractal, who fascinated me when I discovered fractals, the Barnsley Fern. It have certain interesting properties. The most important is that Barnsley Fern looks perfectly as real life ferns, mysterious plants, who were stamped by the feets of dinosaurs. There are ru folk stories, that those, who would find ferns flowers ( golden shining and seen only in midsummer night) would find enermous riches and glory somewhat like of Holy Grail.




It's not so suprising that PC can generate some mathematical figure, its more surpising when mathematical formula generates natural things. Broccollis is nice, but IMHO ferns are more complex and fascinating. A modification of Barnsley Fern that looks just like Christmas tree,  important thing in modern western culture.

Code:

Tannenbaum { ; Created from older IFS of unknown author
  ; by Edgar Malinovsky
  0.024000  0.000000  0.000000  0.432000 -0.011000 -1.148000  0.0114
  0.767883  0.014660  -0.013403  0.839872  -0.045542  1.678451  0.7083
 -0.058172  0.359455  0.429910 -0.136618  0.653422  0.152845  0.1343
  0.103733 -0.370260  0.441029 -0.214518 -0.602863  0.404158  0.146
  }

by Apophysis


Is it possible to have some modified KIFS forest of 3D Barnsley ferns and tannenbaums?

IMHO, it would be more revarding than 3D mandelbrot. If you zoom into mandelbrot set you see more and more spirals. In 3D there are no such easy spirals, but there are number of coresponding curves, who wount be so easily observable.


p.s.
In searching for pictures I just found, that 'm not alone with this idea, and that it is pretty possible. So no new grail.

Chaos and Graphics
Realistic rendering 3D IFS fractals in real-time with graphics accelerators
Tomasz Martyn,
Institute of Computer Science, Warsaw University of Technology, ul Nowowiejska 15/19, 00-665 Warsaw, Poland

http://www.sciencedirect.com/science/article/pii/S0097849309001150

[Alef]

Integration of iterated function systems and vector graphics for aesthetics
Slawomir Nikiel
Department of Control and Computation Engineering, University of Zielona Góra,
http://www.sciencedirect.com/science/article/pii/S0097849306000033

Tight bounding ball for affine IFS attractor
Tomek Martyn,
Computer Graphics Laboratory, Institute of Computer Science, Warsaw University of Technology
http://www.sciencedirect.com/science/article/pii/S009784930300089X

[blob]

This is perhaps of interest: IFS Builder 3d at http://fractals.nsu.ru/builder3d_en.htm

[David Makin]

Of course potentially all L-Systems are convertible to some form of IFS, so really the target should be results like the L-Systems featured here:

http://algorithmicbotany.org/papers/

[Alef]

I was thinking about escape time barnsley fern integrated into major raytracers.

Tomasz Martyn in links above did IFS barnsley fern from raytracer friendly solid 3D primitives. Maybe this could be implemented in fragmentarium, too (but definetely not by me).

Well, but spruce is more interesting, as it is more culturaly important object.

[laser blaster]

A chaos game style implementation of the 3D Barnsley would be really easy to pull off. For each location the point lands at, you would add a sphere. Then, you wold raytrace the sphere data. The only issue is finding a program that lets generate structures with a 3D chaos game. I've never tried it, but structure synth seems like the perfect tool for the job: http://structuresynth.sourceforge.net/

On the other hand, writing a distance estimation formula for a 3D barnsley (for direct raytracing) would be far more difficult. IFS distance estimation is generally straightforward(at least conceptually) - just apply a series of conditional transformations to map sub-parts of the fractal onto the whole, in recursive way, then estimate the distance to the base shape after you're done iterating. However, the problem with the Barnsley Fern is that its fronds overlap, which is something the above method can't handle...

I actually have an idea for how to go about writing a perfect Barnsley distance estimator... but I'll try to write a 2D version first, in Fragmentarium. I have a good feeling I'll be able to pull it off. 

[David Makin]

For affine 3D IFS there's also a way to implement Hart's method (intersecting viewing rays with attractor) on the GPU - for each point you need to traverse the entire IFS tree but only down to a given depth (based on detail/distance from viewpoint) and culling is quick based on bailout (distance of closest approach of viewing ray to bounding volume) - however the method I've used in my 3D IFS formula for UF is not suitable as that goes down the tree branches then back up and across (massive variations in code path from point to point), for efficient GPU you'd have to use an algorithm that goes across each row of the IFS tree instead, I've got it in my head such that no matter which branches get culled the code path will be unchanged but at the moment I've lost my programming mojo - haven't done a line for several weeks

Of course this method is not as general as DE as it's useless for non-affine IFS but it is considerably more optimum than using DE for complete IFS and slightly faster than using DE for KIFS when both are fully optimised.

[cKleinhuis]

lol, i never understood that david, do you have a paper at hand describing the hart's method

[David Makin]

lol, i never understood that david, do you have a paper at hand describing the hart's method

Here's a simplified version I just found - see section 3.41 onwards - it's not as detailed as the paper I've got somewhere here (on my PC from around 7 years ago) but I think you'll get the algorithm:

http://www.cg.tuwien.ac.at/courses/Fraktale/PDF/fractals3.pdf


In my 3D IFS formula a lot of the initialisation code is setting the order in which the transforms appear in the IFS tree - this is because it goes down the tree first therefore the algorithm gives the closest transforms to the viewer/ray priority i.e. they come frst - that way any point found "on" the surface will be found as quickly as possible.

[cKleinhuis]

most excellent, thank you, arrh, although i do not have time for it i will set this post sticky!

[phtolo]

Animated
http://www.phtolo.se/fractals/anim/fern2.avi

[claude]

http://mathr.co.uk/misc/2013-06-30_fern.jpg

I actually have an idea for how to go about writing a perfect Barnsley distance estimator... but I'll try to write a 2D version first, in Fragmentarium. I have a good feeling I'll be able to pull it off. 

I tried to work out some of the maths in 2D today:

http://mathr.co.uk/blog/2013-06-30_distance_estimation_for_ifs_fractals.html

The older post I linked from there has a method for reducing time complexity from O(number of functions ^ number of iterations) to O(number of functions * number of iterations) but it does that by memoizing values in a texture (which isn't scalable to really huge images, nor 3D).

[laser blaster]

Well, all these months later, I finally did write a 2D Barnsley distance estimator in Fragmentarium. Actually, it works far any affine IFS you plug into it. I've only bothered to code in support for 3 transformations, so I had to leave the stem out of my fern.

Not surprisingly, adding support for overlapping parts slows the program down drastically, even when there are few overlaps. But that's partly because my implementation is boneheaded. I used a while loop to traverse down the IFS tree (using a for loop nested inside the while loop) over and over again, taking a slightly different path each time, until I can prove that a pixel is either inside or outside of the fractal. If it's outside the fractal, then I go several steps further down the tree, each time picking the path who's bounding rhombus is estimated to be the closet to the pixel, and calculate the resulting distance estimate (which still isn't completely accurate- there are small discontinuities in the result). So, it needs a lot more work!

Instead of starting from the top of the IFS tree each time I hit a dead end, I could trace back up it to the nearest un-traveled branch by applying the inverse of the transformations, though I would need to restart from the top periodically to avoid losing too much precision. Or, I could even cache the last several positions of the iterated point.

@David Makin: You're right, it would be far simpler and faster to intersect rays directly with a 3D IFS, rather than ray stepping with a distance estimator.

[Alef]

Animated
http://web.comhem.se/phtolol/fern2.avi

Animation looks kind of magic. I like it.

EDIT:

I didn't tell the whole story about ferns. In lavian there are story about ferns having flowers shining of gold but just in single middsummer night, (a day of Johan the Babtist). And anyone who 'll found them will recieve magic luck or something like that. But outside of folklore seeking of fern flower are euphemism having s@x in day of John;)

[cKleinhuis]

that animation is really funny and nice just too short