Difference between revisions of "Approaches"

Revision as of 16:01, 20 April 2014

Scanline and direct

When creating an image there are two main methods:

• scanline methods: all pixels in the image will be scanned. For each pixel, the color has to be determined. The coordinates of the pixel are converted into mathematical parameters. Then an algorithm is run on that parameter. For instance we may have a dynamical system, the point may represent a point in phase space, whose orbit we simulate/iterate, and the color of the pixel will be chosen according to the behaviour of the orbit.

• direct drawing: points, lines or areas, are determined by their mathematical coordinates, converted into pixel coordinates, and drawn

A vast majority of my images use scanline algorithms.

Backward and forward iteration

This concerns discrete dynamical systems.

Forward iteration means that we compute z₁, z₂=f(z₁), z₃=f(z₂), etc... Backward iteration means that $z_2=f^{-1}(z_1)$, $z_3=f^{-1}(z_2)$, etc... The solution may be non-unique.

Most of my scanline programs use forward iteration.

Example of scanline algorithm with forward iteration

A famous example is the following, one of the first methods used by people to draw Mandelbrot's set:

• Choose a maximal number of iterations N (integer), a scaling factor a (real or complex) and an offset b (complex number)
• For all pixel in the image, whose coordinate we call (i,j):
  • Compute the complex number c from (i,j)
    typically set c=a×(i-j×√-1)+b (there are nicer formulas)
  • Set the complex number z=0
  • Do the following at most N times:
    • if the module of z is bigger that 4:
      • color the pixel (i,j) white
      • exit the loop and pass to the next pixel
    • (otherwise) compute z²+c and let z be this quantity
    • carry on the loop
  • If the loop ends without having given a white pixel, set it to black
  • pass to the next pixel

The bigger N, the better image, but the computation time increases with N.

There are better algorithms, see the special page Mandelbrot set on this wiki.

Example of an inverse iteration method

The IIM to draw Julia sets:

Choose a rational map F, call J its Julia set

• find one point in J (for instance there must be at least one repelling fixed point, it must be in J)
  call it z
• for as long as you can wait do the following:
  • choose randomly a preimage w of z by F
  • color the pixel corresponding to w, if it is within the bounds of the frame
  • let z have the value w and repeat the process

It has defects: it draws the same pixels many times and takes a lot of time to find some other pixels. This is well explained in the book The beauty of Fractals^[1].

Image/preimage of a set

Suppose it is easier to compute F than F^-1.

Using the n-th iterate of F:

• In scanline methods, one computes the n-th inverse image of a set
• In direct methods, one computes the n-th image of a set

1. ↑ Heinz-Otto Peitgen, Peter Richter, The beauty of fractals, Springer-Verlag, Heidelberg, 1986, 0-387-15851-0