Talk:Iterated function system

Equivalent constructions

There might be something unclear in the construction paragraph:

The most common algorithm to compute IFS fractals is called the chaos game. It consists of picking a random point in the plane, then iteratively applying one of the functions chosen at random from the function system and drawing the point. An alternative algorithm is to generate each possible sequence of functions up to a given maximum length, and then to plot the results of applying each of these sequences of functions to an initial point or shape.

Is this a correct rendition of the two methods? Method 1 as described here takes an initial point, applies a randomly chosen transformation, plots the resulting point and applies a randomly chosen transformation on that point again. Method 2 as described here do effectively the same sequence of transformations but only plots the last point. Method 2 is then just Method 1 throwing away most of the plot.

I might be showcasing my ignorance here, but in the chaos game (method 1), we have, intuitively, a point that is jumping around and never settles. Perhaps, we're trying to say that method 2 relies on function sequences such as f1(f2(f1(f3(f2(...(X)....))) where f1,f2,f3 are contractive mappings and that each such sequence have any point X converging on a specific fixed point. This sounds like it would rely on the Banach fixed point theorem but the chaos game seems to show that even though contractive mappings converge to a point, iterative application of different contractive mappings does not necessarily do the same.

So in short, I'm not sure what method 2 is supposed to be :-) EverGreg (talk) 13:54, 23 October 2009 (UTC)

The paper "fractals, graphs and fields" by Franklin Mendivil [1] explained the two methods and their equivalence very well. Recommended if there's others out there getting confused. :-) The construction paragraph seems correct, though it leaves out a lot of detail. EverGreg (talk) 19:40, 26 December 2009 (UTC)

to EverGreg: "Method 2 as described here do effectively the same sequence of transformations but only plots the last point."

There's a subtlety in method 2. Note that it doesn't say "generate a sequence of transformations". It says "generate EACH POSSIBLE sequence of transformations" (implication: from a known starting point in space.)

If you have 3 transformations and you want sequences of length 10, you have 3^10 possible sequences of transformations. Given a common (arbitrary) starting point, this will yield 3^10 end points. Those 3^10 end points are plotted and make your fractal. 46.64.181.38 (talk) 14:11, 19 April 2014 (UTC)

Right. Another way of looking at it is that the chaos-game algorithm is a random depth-first "search" that never backtracks, while Method 2 is an exhaustive search up to a given depth. But yes, this paragraph is super unclear. I just improved it slightly, but a lot more work is needed. Kragen Javier Sitaker (talk) 05:49, 19 July 2014 (UTC)

Example

Just not an encyclopedic, throught with ferns and triangles IFS animation 1 and IFS animation 2 —Preceding unsigned comment added by Edo 555 (talk • contribs) 14:05, 8 July 2010 (UTC)

Major missing topics

Although a few are mentioned as links, this page currently doesn't talk about any of these IFS topics, which I think are interesting and important:

• fractal image compression using IFSs;
• escape-time rendering of IFSs by inverting the functions;
• ray-traced rendering of 3-D IFSs;
• the relationship between IFSs and L-Systems, at any rate the commonly-studied L-Systems (it's easy to come up with a pathological L-System that doesn't obviously correspond to any IFS);
• Barnsley's deterministic iteration algorithm, which I guess is "Method 2"?
• the various other rendering methods presented by Hepting et al. 1991;
• the "collage theorem";
• Bell's "tesseral synecdoche algorithm";
• the "grayscale photo-copy algorithm" and its connection to the invariant measure of the IFS;
• the problem of computing the IFS's bounding box;
• the need to balance transform probabilities for stochastic ("chaos game") rendering (and the difficulty of doing so);
• computing sound upper and lower conservative bounds on the IFS's attractor;
• the phase transitions observed during continuous parameter variation.

Some random set of slides I ran across mentioned that you can get good ray-tracing results by approximating your surface normal as a weighted sum of the surface normals of the bounding spheres of the different subunits, which was part of what I was trying to figure out. I was disappointed to find that we haven't written a better article on this topic yet.

Thoughts on which of these are most important to cover? How to organize them?

Kragen Javier Sitaker (talk) 06:19, 19 July 2014 (UTC)

Zooming

The article says that zooming in on an IFS fractal using the deterministic and random iteration algorithms is impractical.

This may not be the case, depending on how broadly you conceive each algorithm. I've been investigating producing high depth zooms, using a modification of the (depth first) deterministic iteration algorithm and reached a zoom of 5 × 10¹⁵⁰, using native 64 bit floating point arithmetic, without any noticeable deterioration in image quality, at little cost in extra computation time. At this point I hit an arithmetic overflow in the calculation of how deep the iterations should be, but this code can be refactored to avoid this. The modified code is ticking away and has reached a zoom 7 × 10¹⁹⁰. It may be possible to get to over 10⁶⁰⁰.

The modification is to combine a shallow depth first deterministic algorithm with a pruned breadth first deterministic algorithm (i.e. selecting only those branches in the deeper parts of the tree which lie within the zoom).

I haven't tried it yet, but combining a random iteration algorithm with the same pruned breadth first deterministic algorithm, should also work. Lavateraguy (talk) 16:48, 3 November 2016 (UTC)