LRIFS Paper

[Aexion]

Just a curiosity,
Does anyone has tried the method presented here in this article from Przemyslaw Prusinkiewicz and Mark Hammel ?:
http://algorithmicbotany.org/papers/escape.gi92.html

The images at the end of the article looks interesting..
By the way, the Algorithmic Botany publications page is a real treasure for anyone who want to play with l-systems..
http://algorithmicbotany.org/papers/

[David Makin]

My IFS formulas for UF are essentially based on that paper but I didn't spare the time to fully digest their implementation, I just took the idea of "language restriction" and implemented it in my own slightly more limited (and considerably simpler) way so I have referred to them as LRIFS on occasion  - i.e. they have optional restrictions on paths in the IFS tree e.g. if we have transform A last then AoB is not allowed but AoC is, or restrictions such that certain transforms are not allowed at certain depths in the tree, or some are restricted to only n repeats e.g. AoAoA is OK but in AoAoAoX the X cannot be A (extremely useful and prompted by Garth Thornton) - I extended this idea to restricting any path through the tree such that a given transform is only allowed n times within the entire path (that's not quite as useful except if you want "broken-looking" results).
Of course there are a myriad of other possibilities, especially if you start mixing in non-affine transforms and rendering using DE instead of Hart's direct ray/convex hull intersection method.
The formulas are in mmf4.ufm as "3D IFS" and "Escape-time IFS"
This method if extended a little could be used to combine standard convex hull based hierarchies of conventional models (polygons, primitives or even local voxels) with multiple fractal objects and if done properly then in such a way that all movement (including say changes in convex hull information at multiple levels) is possible for an entire world in a single data structure.

[Aexion]

Hmm,

Let me try to understand the RIFS algorithm (the equations aren't a problem, since I already have used them).
For every iteration, you have (for example) four possible transformations.
Then you select one transformation that meets some criteria.
and continue the process until the iteration bails out.

The criteria can be:
A rule: Iterate all of transformation and take the solution that has the shortest distance from the previous value.
A automaton: If the previous transformation is X, then select the transformation Y.
A geometrical rule: If the actual iteration value is negative, then select the transformation X, else select the transformation Y

Of those criteria's, the article are using the automaton, if I have guessed well?(or I'm missing something?).


I have seen only one full implementation of the RIFS (besides yours!), that actually renders the set. Its a program called FractalBuilder,
that effectively inverts every IFS, and even goes beyond, inverting apollonian nets. Take a look at their galleries:
http://fractals.chat.ru/gallery2.htm

The program itself can be downloaded here (the webpage is in Russian, but the program is in plain English, and you need to expand the program left panel if you want to add your transformations):
http://fractals.chat.ru/builder.htm

[David Makin]

Ermmm no, that doesn't really match my code - here's the 2D version:

1. Convert all transforms to the divergent equivalents
2. Using some method ascertain a reasonable centre + bailout automatically but have a user scale factor to adjust this - or a plain override for direct user specification of centre + bailout.

then

By default per pixel my code (without special rules) traverses the entire IFS tree for all transforms traveling down each branch to either a limit depth or until bailout occurs - if bailout occurs carry on tree traversal otherwise use the first path that doesn't bailout as the correct one (i.e. sequence/genetic code for that pixel). The limit depth ideally has an absolute depth parameter plus an overall scale factor that's tested as the tree is descended on each path. In cases of overlap i.e. 2 or more codes potentially for the same pixel this method will always choose the same one based on the order of traversal of the IFS tree - so the user can specify priorities on the transforms to control this.

the LRIFS part comes from modifying the tree traversal so that certain paths are blocked at whatever depth based on whatever criteria you can think up - as I suggested in my previous post, e.g. if down the tree the last transform was A then a rule could specify that A can never be followed by B in which case all the B branches from every occurance of A are pruned - similarly you could specify that at depth 5 B is allowed but A isn't so XoXoXoXoB is OK but XoXoXoXoA is not but any transform is allowed at depths 6 and above. Also as I said you could restrict the consecutive uses of a given transform such that XoCoCoCoX is OK but XoCoCoCoC is not and obviously combinations and extensions of these rules.

In the 3D version the tree traversal the algorithm is very similar except here we keep a record of a valid line segment on the viewing ray for each pixel that passes through the bounding volumes - if it misses the bounding volume then that path ends etc.

Note that you can't just use the smallest magnitude/distance to keep the IFS tree to a single path unless there is absolutely no overlap of two or more genetic areas within a given bounding volume at any stage (Edit: in fact doing that you basically drop back to Mandelbox/KIFS which of course can render say a menger sponge or siierpinski or in fact any other IFS or even LRIFS that does not have overlapping bounding volumes but otherwise will tend to miss areas of the "complete" attractor)

[Aexion]

You mean that you iterate the entire transformation tree for every pixel(voxel)!?
Now I understand why this is on the L-System section. Basically, an L-System string is build in order to scan the whole tree..
Now the automaton part is more clear, its a set of rules for cutting the tree branches, being one of them the rule that you have explained.
My method don't works in that way and actually fails on overlapping transformations, but perhaps an hybrid  can give a good result.
Need to think more about that, since not only classic IFS transformations can be used, but a lot of interesting ones (as you already pointed).
Did you remember the old Lyapunov fractal, and its transformation sequences.. perhaps something like that (I actually ported the lyap to 3d by adding a third transformation.. interesting results.. )..
Here is a little example of a fern rendered by my distance selection method. While the overall shape is clearly visible, it fails when the leaves overlaps.

[DarkBeam]

It would be helpful if somebody figures out how to write this formula, a more simplified version of David's 3d ifs formula.
Only input needed, a bool array that tells if transforms are on or off. Transforms are placed on a cube, possible coords are -1, 0, 1... total 9x3 ... 27 transforms.
other input, x y z.

scale is 3 for all transforms (like menger)
also suppose to not use any rotation, or a rot equal for all transforms (if liked)

The output is the new x y z, but the function f(x,y,z) must be continue to give a good de for raytrace and normals

Possible and easy?

[David Makin]

You mean that you iterate the entire transformation tree for every pixel(voxel)!?
Now I understand why this is on the L-System section. Basically, an L-System string is build in order to scan the whole tree..
Now the automaton part is more clear, its a set of rules for cutting the tree branches, being one of them the rule that you have explained.
My method don't works in that way and actually fails on overlapping transformations, but perhaps an hybrid  can give a good result.
Need to think more about that, since not only classic IFS transformations can be used, but a lot of interesting ones (as you already pointed).
Did you remember the old Lyapunov fractal, and its transformation sequences.. perhaps something like that (I actually ported the lyap to 3d by adding a third transformation.. interesting results.. )..
Here is a little example of a fern rendered by my distance selection method. While the overall shape is clearly visible, it fails when the leaves overlaps.

Exactly - a single path "standard escape-time" (2D) version for IFS has been in the UF database since around 2003 though I forget who wrote it - that has the same issue with ferns etc.
I don't really know the Lyap that well - I've only really used Lyapunov exponents - in a couple of formulas for orbital attractors to help give users information on where strange attractors may be found and in an attempt to estimate the dimension of them very rapidly.
The problem goes further than just overlaps in the attractor itself, mistakes (missed attractor) also occur if the bailout areas/volumes of two or more paths in the tree overlap if using the simple single chosen path method - this can be avoided in some cases by customising the bailout testing to ensure no overlap of bailout areas/volumes for any of the paths to a given depth in the tree but of course with rotation, shearing, skewing and especially anything non-linear that's very difficult to say the least and in the case of actual overlap of the attractor (such as overlapping fern leaves) then it's not possible to fix the issue if using a single path without checking for others and even then you have to either colour using "hits" in the flame type manner in some way or have some system of choosing which of the alternative genetic paths to use with respect to the colouring.

If tree traversal is done in a width-first rather than depth-first method one could restrict the paths continued at each depth to the x best (i.e. the x ones having minimum bailout test magnitude) though as the complexity of the IFS increases (more trasforms or very non-linear including rotations, skews,shears and powers etc.) then x would also have to increase That method (like using the complete tree per pixel) may also work quite well even if using non-affine transforms but you'd still need to use DE rather than Hart's intersection when using any non-affine transforms.

For more comments and images relating to the bailout area/volume overlap issues (including DE estimation problems) see here (the various renders of the Heighway Dragon), oldest first:

http://www.fractalforums.com/index.php?action=gallery;su=user;cat=82;u=141

And here's an old post of mine on LRIFS - at least my way:

http://www.fractalforums.com/programming/escape-time-lrifs/

[Aexion]

Did you remember the old Lyapunov fractal, and its transformation sequences.. perhaps something like that (I actually ported the lyap to 3d by adding a third transformation.. interesting results.. )..
Here is a little example of a fern rendered by my distance selection method. While the overall shape is clearly visible, it fails when the leaves overlaps.

Exactly - a single path "standard escape-time" (2D) version for IFS has been in the UF database since around 2003 though I forget who wrote it - that has the same issue with ferns etc.

I don't really know the Lyap that well - I've only really used Lyapunov exponents - in a couple of formulas for orbital attractors to help give users information on where strange attractors may be found and in an attempt to estimate the dimension of them very rapidly.

Yes, someone ported the formulas that are the output of my 1997 IFSINV program
http://user.xmission.com/pub/lists/fractint/archive/v01.n025   
(search for Ramiro Perez)
That in turn comes from my 1993 post about escapetime ifs formulas:
http://groups.google.com/group/bit.listserv.frac-l/browse_thread/thread/c4b8f0dc58a8965d/41c9cae07feec4c2
The first formula, translated to fractint 20.0 format is (in 1993 fractint didn't supported conditionals, so I have solved it in my own way):
zpj(YAXIS){
z=pixel:
k=real(z)
IF (k<0)
z=z*p1-1
ELSE
z=z*conj(p1)+1
ENDIF,
|z|<=100
}
solve it for c=0.9-0.87i ...

I don't really know the Lyap that well - I've only really used Lyapunov exponents - in a couple of formulas for orbital attractors to help give users information on where strange attractors may be found and in an attempt to estimate the dimension of them very rapidly.

You most probably have seen this one:
http://en.wikipedia.org/wiki/Lyapunov_fractal
Back in 1993, I also was investigating the 3D version:
http://groups.google.com/group/bit.listserv.frac-l/browse_thread/thread/9122874e4a0498ad/28157de62f77d1b3
(Elder times.. I miss them.. with those full 16 colors EGA cards.. )

The problem goes further than just overlaps in the attractor itself, mistakes (missed attractor) also occur if the bailout areas/volumes of two or more paths in the tree overlap if using the simple single chosen path method - this can be avoided in some cases by customising the bailout testing to ensure no overlap of bailout areas/volumes for any of the paths to a given depth in the tree but of course with rotation, shearing, skewing and especially anything non-linear that's very difficult to say the least and in the case of actual overlap of the attractor (such as overlapping fern leaves) then it's not possible to fix the issue if using a single path without checking for others and even then you have to either colour using "hits" in the flame type manner in some way or have some system of choosing which of the alternative genetic paths to use with respect to the colouring.

If tree traversal is done in a width-first rather than depth-first method one could restrict the paths continued at each depth to the x best (i.e. the x ones having minimum bailout test magnitude) though as the complexity of the IFS increases (more trasforms or very non-linear including rotations, skews,shears and powers etc.) then x would also have to increase That method (like using the complete tree per pixel) may also work quite well even if using non-affine transforms but you'd still need to use DE rather than Hart's intersection when using any non-affine transforms.

For more comments and images relating to the bailout area/volume overlap issues (including DE estimation problems) see here (the various renders of the Heighway Dragon), oldest first:

http://www.fractalforums.com/index.php?action=gallery;su=user;cat=82;u=141

And here's an old post of mine on LRIFS - at least my way:

http://www.fractalforums.com/programming/escape-time-lrifs/

I saw those dragons..A very good work!
As for my method, I just don't use a single path, but select the smallest distance between the transformation solution and a fixed point (usually the fractal central point).
But also I have added an scaling factor to these distances, something that helps the right transformation selection. Sadly the method only works for non-touching IFS, and its not a general solution..
Anyways, I will investigate your method, since it's the one that more closely renders the attractor (the automaton section of the article also appears to be very interesting).

[David Makin]

Of course one can obviously always use quick location testing to help decide on the next transform i.e. if you have an overlap area as in the Heighway Dragon example then use quick location testing to eliminate some transforms (i.e. a check for locations where they are not on the attractor) and only have multiple paths for the remainder - giving an optimised combination of the single path and full tree methods.

[Aexion]

Of course one can obviously always use quick location testing to help decide on the next transform i.e. if you have an overlap area as in the Heighway Dragon example then use quick location testing to eliminate some transforms (i.e. a check for locations where they are not on the attractor) and only have multiple paths for the remainder - giving an optimised combination of the single path and full tree methods.

Something like a "majority vote" testing sphere.. whose testing radius is proportional to the minimum contraction ratio of the transformations (or it can be user defined, or just proportional to the zoom factor). Testing points can be distributed by a platonic solid on the sphere surface.
Its a good idea.   Also, such test can be computed in a gpu, for example..

[David Makin]

It would be helpful if somebody figures out how to write this formula, a more simplified version of David's 3d ifs formula.
Only input needed, a bool array that tells if transforms are on or off. Transforms are placed on a cube, possible coords are -1, 0, 1... total 9x3 ... 27 transforms.
other input, x y z.

scale is 3 for all transforms (like menger)
also suppose to not use any rotation, or a rot equal for all transforms (if liked)

The output is the new x y z, but the function f(x,y,z) must be continue to give a good de for raytrace and normals

Possible and easy?

Not quite that simple I think, if you only use 27 flags per depth then you only get uniformity within each depth - using the standard method of a fixed set of n transforms you'd really need n flags at depth 1, x*n flags at depth 2 where x is the number of "on" flags at depth 1, y*x*n flags at depth 3 where y is the number of "on" flags at depth 2 ......
Of course that would be the ultimate in flexibility because (for example) level 1 holes in a Menger need not necessarily be passed on to all other levels as smaller holes if appropriate transforms are applied down the tree - hmmm I need to think about it a little more......

Edit: For instance let's say you have all 27 transforms defined for a cube but only the normal "sponge" 20 are allowed at all depths *except* (for example) at one corner for which after depth 1 all 27 are allowed at all deeper levels.....
Of course Huffman encoding the bits for each depth could be very useful

[DarkBeam]

Oh dear ...

but kifs menger is a very simple formula, ten lines in total the problem is that is not general but fixed

Anyway the fractal community would be grateful if you manage to write it

[DarkBeam]

The base should be:

x1=3(x-1) y1=3(y-1) z1=3(z-1)
...
x27=3(x+1) y27=3(y+1) z27=3(z+1)

Then do some mangling to get continuity ...

[David Makin]

It would be helpful if somebody figures out how to write this formula, a more simplified version of David's 3d ifs formula.
Only input needed, a bool array that tells if transforms are on or off. Transforms are placed on a cube, possible coords are -1, 0, 1... total 9x3 ... 27 transforms.
other input, x y z.

scale is 3 for all transforms (like menger)
also suppose to not use any rotation, or a rot equal for all transforms (if liked)

The output is the new x y z, but the function f(x,y,z) must be continue to give a good de for raytrace and normals

Possible and easy?

Not quite that simple I think, if you only use 27 flags per depth then you only get uniformity within each depth - using the standard method of a fixed set of n transforms you'd really need n flags at depth 1, x*n flags at depth 2 where x is the number of "on" flags at depth 1, y*x*n flags at depth 3 where y is the number of "on" flags at depth 2 ......
Of course that would be the ultimate in flexibility because (for example) level 1 holes in a Menger need not necessarily be passed on to all other levels as smaller holes if appropriate transforms are applied down the tree - hmmm I need to think about it a little more......

Edit: For instance let's say you have all 27 transforms defined for a cube but only the normal "sponge" 20 are allowed at all depths *except* (for example) at one corner for which after depth 1 all 27 are allowed at all deeper levels.....
Of course Huffman encoding the bits for each depth could be very useful

For example in terms of bit storage than a complete platonic cube would require all "on" bits at every depth which will probably huffman encode quite well

[DarkBeam]

Yes, but I don't care because I use assembly that ignore such types