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

Both the random and growth methods assume that just one pixel is painted and calculate what other pixels must be set because of it. Death takes the exact opposite approach, assuming all visible pixels are painted and gradually removing those that it calculates cannot be set. Death also operates on a frame by frame basis, rather than pixel by pixel.

For the death algorithm, we require some extra information; we need the size and position of a rectangular area that completely contains all the painted pixels. For the simple images we use here, finding this rectangle is no problem - it's simply the size of the window we painted the original image in!

Note that if a pixel is painted in a sub-image, then there must exist some painted in one of it's parent images that transforms to that painted pixel. This is the crux of the death algorithm. Again, every painted pixel must be transformed to by some other painted pixel in the original image. In mathematical terms, the pixels perform a self-sustaining cycle under the relevant IFS transformations.

To start with, we assume that every pixel is painted within this rectangle. Because the rectangular area contains every painted pixel, we know that every painted pixel in the original image will be transformed to by some painted pixel in this (quite bad) approximation. So, to gain a better approximation, we calculate the destination of every pixel under every available transformation. Only those pixels mapped to by some other pixel remain set.

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 death method 2nd step in a sequence showing progressive execution of the death method 3rd step in a sequence showing progressive execution of the death method 4th step in a sequence showing progressive execution of the death method 5th step in a sequence showing progressive execution of the death method 6th step in a sequence showing progressive execution of the death method 7th step in a sequence showing progressive execution of the death method 8th step in a sequence showing progressive execution of the death method

It should be fairly obvious how we know we can unpaint the pixels that aren't mapped to; every painted pixel must be mapped to by some painted pixel in the original image. If we initially estimate the image as a large painted square containing the original image, then we know we have painted at least every rightfully painted pixel. Therefore, every pixel that should be mapped to is mapped to, since we have covered all possibilities. Hence, we can unpaint pixels that aren't mapped to

We can keep repeating this idea to gain further better and better approximations to the original image. Again, for every painted pixel, we calculate the destination of every transformation and leave only the transformed to pixels painted.

By the same ideas as above, no pixel that should be painted will not be painted by the first iteration. Hence, every pixel that should be painted will be mapped to by the second algorithm too (and some that shouldn't). By repeating this algorithm, we gradually unpaint pixels until we leave only those that should be painted.