Approaches

Scanline and direct

When creating an image there are two main methods:

• scanline methods: (a.k.a. raster scan) 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.

Direct drawing is a priori much faster as, in good cases, it targets computation only at necessary pixels. Direct drawing is also the only approach compatible with vector graphics.

A vast majority of my images use scanline algorithms. When both methods are applicable, I have often noted a better quality with scanline versions.

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 $z$ of $f(z)=w$ 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 modulus of z is bigger that 2:
      • 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.

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

Example: you want to compute the n-th preimage by f of the upper half plane. You may for each pixel compute the corresponding point z, then test wether or not fⁿ(z) has positive imaginary part and color the pixel white or black according to the result.

Example: you want to compute the n-th image by f of a circle. You may discretize the circle into certain number of points z, compute fⁿ(z) for each of them, and plot a dot at each resulting value, or a straigt line between successive values. There are more clever ways to do this, though: for instance by adapting the step to the movement of the point, see section to be added. One could also use higher order approximations, like Bezier curves, but this becomes complicated.