The "Growth" Algorithm
  Home    /    IFS    :    Prev Page       Next Page  

The growth algorithm is based very heavily on the random method. We start with a clear image and find the first pixel to set in exactly the same way as the random drawing method.

However, for each new pixel we generate we apply every single available transformation. We paint each resultant pixel and store them all for future reference (a linked list is common). For the next iteration, we simply grab any pixel from our reference pool and perform the same operation.

If we find we have reached a pixel that is already painted, we ignore it and do not add it to the reference pool. This idea behind this is that if the pixel is already plotted, then it must already have had all transformations applied to it, so there is no point duplicating the work (or it must at least already be in the reference pool waiting to be processed). This stops the decoder going into an infinite loop.

When the reference pool is finally empty, the algorithm is complete. Again, pseudo-code for the algorithm is given below.

            co-ordinates=0,0
            for counter=1 to 100
              pick a random transform
              apply it to the co-ordinates
            end
            paint pixel corresponding to the co-ordinates
            empty co-ordinate pool
            put co-ordinates into pool
            while co-ordinate pool not empty
              take co-ordinates from co-ordinate pool
              for every transform
                apply transform to unmodified co-ordinates from pool
                if transformed pixel not already painted
                  paint transformed pixel
                  add transformed co-ordinates to pool
                end
              end
            end
            

An example of an IFS image being drawn by this method is shown below in various stages of development:

1st step in a sequence showing progressive execution of the growth method 2nd step in a sequence showing progressive execution of the growth method 3rd step in a sequence showing progressive execution of the growth method 4th step in a sequence showing progressive execution of the growth method 5th step in a sequence showing progressive execution of the growth method 6th step in a sequence showing progressive execution of the growth method

Notice how the pixels furthest along the 'tail' of the image are painted far more quickly than the rest. This is because we always apply every tranformation to every pixel; All pixels in the main image map into the very small sub-image at the tail under the second transformation, whilst the first transformation scatters points around the rest of the image.

Also note that in the final image the centre is much lighter. This is due to the way the errors accumulate; many different co-ordinates are associated with a singel pixel.

Whilst using the random IFS method, any pixel may be painted any number of times due to the chain of co-ordinates passing through a pixel many times, albeit at very slightly different points within that pixel.

However, whilst using the growth method, any co-ordinate falls into a pixel is treated as being equal to any other co-ordinate. Hence, re-visiting a pixel, even with different co-ordiantes, causes the co-ordinate chain to be discarded. This reduces the number of different co-ordinates that the transformations are applied to and hence makes the image lighter.