Exercises Computer Graphics

Session 4 - IFS Fractals



Useful Links:


In this session, we will study iterated function system fractals. Iterated function systems (IFS) are defined as a set of 'contraction mappings' (functions that map a set of points 'closer' to one another). A fractal can be generated from an IFS by applying its set of functions to an initial image (a set of points in 2d space) recursively. Fractals are figures that exhibit the same pattern no matter how much you zoom in or out on the figure.

Take a fixed coordinate system. A point in the real plane (RxR) can be written as p = (x,y) relative to this coordinate system. Points can be added or subtracted and multiplied by a scalar constant.

A linear function is a transformation that associates each point p in the plane with a point f(p) such that:f(p1+p2) = f(p1) + f(p2) And such that:
f(a * p) = a * f(p) for each real number a and all points p, p1, p2.

A linear transformation can be represented as a matrix:

where if p = (x, y) and f(p) = (u, v), then:

I.e. the matrix is multiplied with the vector [x y]T . An affine linear transform can be followed by a translation. If f is a linear transformation and q = (e,f) is a point then a translation is expressed as:

w(p) = f(p) + q

If p=(x,y) and w(p) = (u,v) then we can represent the transformation as:

An iterated function system (IFS) is a set of such affine transformations w1, w2, w3, ... wn. A given initial image A is transformed by creating small copies of it, by applying each transformation to it: w1(A), w2(A), w3(A), ..., wn(A). The original image A is then replaced by the union of these small copies:

w is called the Hutchinson operator. A fractal can be created from an IFS by repetitively applying w to an initial image A0. Thus we acquire A1=w(A0), A2=w(A1), etc. If the initial image consists of only a single point p and the IFS consists of 3 transformations (n = 3), each application of the Hutchinson operator multiplies the number of points (pixels) in the image by 3. An IFS generates a sequence of images and converges to an image A, called the attractor of the IFS. It is an interesting fact that the attractor is independent of the initial drawing used to generate it.

The algorithm described above to generate a fractal from an IFS is deterministic: at each iteration, all transformations are applied to the image. There also exists a non-deterministic variant that assigns a probability p (between 0 and 1) to each transformation in the IFS. At each iteration, instead of applying all transformations, one transformation is chosen at random, where the probability that a certain function is chosen is determined by its probability p.

You can make use of the following skeleton code.


Exercise 1: implement an IFS

Write a program that, given a number of affine transforms and a point to serve as initial image, draws the attractor A on the screen. Test your algorithm on the following IFSes. Each row in the table below is an affine transformation.

Exercise 2: Sierpinsky

Determine the number and kind of affine transforms that generate the sierpinsky triangle. Its attractor looks like this:

Exercise 3: Koch's Snowflake

Implement Koch's Snowflake. The idea behind Koch's Snowflake is the following transformation:

where each line segment is transformed into 4 new segments of equal length |ab|/3. Keep on repeating this transformation recursively on the 4 new segments. If you choose an equilateral triangle (represented by 3 line segments) as an initial image, you will end up with Koch's snowflake.

Valid HTML 4.01 Transitional ©2008-2009 Tom Van Cutsem