# Iterated Function Systems

CS 481/681 2007 Lecture, Dr. Lawlor

An Iterated Function System (IFS) is a really simple object.  It's just a small set of matrices, or other space-to-space functions (hence usually called "maps").  It's really easy to describe lots of interesting fractal shapes using IFSs, where the shape consists of nothing but a set of scaled copies of itself.  That is, an IFS is a definition for a sort of "recursive object", where you define the object in terms of smaller copies of itself.

For example, a Sierpinski Triangle consists of three smaller Sierpinski Triangles.  Hence you can represent a Sierpinski Triangle using an IFS with 3 matrices that map the unit square down onto the three pieces.  You can draw an IFS by recursively applying the IFS matrices, like this.  Eventually you do need a recursive base case, where you draw a point or dot or... anything, really!
`void drawSierpinski(Matrix cur) {	if (coordinates_are_really_small(cur)) 	{ /* Recursion base case: draw a little dot at this coordinate origin */		draw_a_point(cur);	} else { /* Recursion case */		drawSierpinski(cur*top_and_center);		drawSierpinski(cur*down_and_left);		drawSierpinski(cur*down_and_right);	 }}`
Or if you've got a list of matrices, the same recursion looks like this:
`void drawIFS(Matrix cur,int level,const std::vector<Matrix> &matrices) {	if (level>10) 	{ /* Recursion base case: draw a little dot at this coordinate origin */		draw_a_point(cur);	} else { /* Recursion case */		for (int m=0;m<matrices.size();m++)			drawSierpinski(cur*matrices[m], level+1, matrices);	}}`
What's really weird about IFSs is that *there is no geometry there*.  It's all just points, defined by a small set of matrices.

Curiously, you can also draw an IFS without recursion by applying a randomly chosen IFS matrix to a randomly-chosen point:
`void diceIFS(const std::vector<Matrix> &matrices) {	Point p=Point(0,0);	for (int i=0;i<1000000;i++) {		p=matrices[rand()%matrices.size()] * p;		draw_a_point(p);	}}`
You can define IFSs in any number of dimensions; see some 3D examples in an online Java Applet.

I wrote a paper in late 2002 describing how to find bounding volumes for 2D and 3D IFS.  The same page has presentations, a much nicer 2D IFS editor than my 3D version on the course homepage, and a whole set of cool 2D IFSs.