Difference between revisions of "Approaches"
m (→Backward and forward iteration) |
(→Backward and forward iteration) |
||
| (9 intermediate revisions by the same user not shown) | |||
| Line 3: | Line 3: | ||
When creating an image there are two main methods: | 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. | + | * 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: 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. | + | 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 == | == Backward and forward iteration == | ||
| Line 14: | Line 17: | ||
Forward iteration means that we compute z<sub>1</sub>, z<sub>2</sub>=f(z<sub>1</sub>), z<sub>3</sub>=f(z<sub>2</sub>), etc... | Forward iteration means that we compute z<sub>1</sub>, z<sub>2</sub>=f(z<sub>1</sub>), z<sub>3</sub>=f(z<sub>2</sub>), etc... | ||
| − | Backward iteration means that $z_2=f^{-1}(z_1)$, $z_3=f^{-1}(z_2)$, etc... The solution may be non-unique. | + | 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 === | === Example of scanline algorithm with forward iteration === | ||
| Line 27: | Line 30: | ||
** Set the complex number z=0 | ** Set the complex number z=0 | ||
** Do the following at most N times: | ** Do the following at most N times: | ||
| − | *** if the | + | *** if the modulus of z is bigger that 2: |
**** color the pixel (i,j) white | **** color the pixel (i,j) white | ||
**** exit the loop and pass to the next pixel | **** exit the loop and pass to the next pixel | ||
| Line 38: | Line 41: | ||
There are better algorithms, see the special page [[Mandelbrot set]] on this wiki. | 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)<br/>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''<ref>Heinz-Otto Peitgen, Peter Richter, ''The beauty of fractals'', Springer-Verlag, Heidelberg, 1986, ISBN 0-387-15851-0</ref>. | ||
| + | |||
| + | == Image/preimage of a set == | ||
| + | |||
| + | Suppose it is easier to compute F than F<sup>-1</sup>. | ||
| + | |||
| + | 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<sup>n</sup>(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<sup>n</sup>(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. | ||
{{expand}} | {{expand}} | ||
| + | |||
| + | == References == | ||
| + | |||
| + | <references> | ||
Latest revision as of 08:58, 28 July 2016
Contents
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 z1, z2=f(z1), z3=f(z2), 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 z2+c and let z be this quantity
- carry on the loop
- if the modulus of z is bigger that 2:
- If the loop ends without having given a white pixel, set it to black
- pass to the next pixel
- Compute the complex number c from (i,j)
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
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 fn(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 fn(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.
References
- ↑ Heinz-Otto Peitgen, Peter Richter, The beauty of fractals, Springer-Verlag, Heidelberg, 1986, ISBN 0-387-15851-0
