Fractals/Computer graphic techniques/2D

From Wikibooks, open books for an open world
Jump to navigation Jump to search

Software[edit | edit source]

All tasks (image processing[1]) can be done using:

One can use free graphic libraries:

Hardware[edit | edit source]

graphic workstation: graphic card, monitor, memory, disk

2D graphics pipeline[edit | edit source]


  • clipping : covert object in world coordinate to object subset = = applaying world window to object
  • window to vieport mapping
  • rasterisation = (scan conversion) – Convert high level object descriptions to pixel colors in the frame buffer
  • display/ save

Creating graphic[edit | edit source]

Here are 3 targets / tasks:

  • graphic file (saving/ loading image)
  • memory array (processing image)
  • screen pixels (displaying image)

Memory array[edit | edit source]

Image in memory is a matrix:

  • A 24-bit color image is an (Width x Height x 3) matrix.
  • Gray-level and black-and-white images are of size (Width x Height).

The color depth of the image:

  • 8-bit for gray
  • 24 or 32-bit for color,
  • 1-bit for black and white.

Screen pixels[edit | edit source]

glxinfo | grep OpenGL
glxinfo | grep "direct rendering"

DRI[edit | edit source]

Direct Rendering Infrastructure (DRI2)[12]

Color[edit | edit source]

Example of interesting color gradient
Palette graphics, palette replacement mechanism

Curve[edit | edit source]

Field lines[edit | edit source]

Field line[13]

Tracing[edit | edit source]

Tracing a curve on a triangular grid

Tracing curve[14]


  • general, (analytic or systematic) = curve sketching[15]
  • local method

Three Curve Tracing Models[16]

  • Pixel-by-Pixel tracing
  • The bipartite receptive field operator
  • The zoom lens operator




Curve rasterisation[edit | edit source]

Ray[edit | edit source]

Ray can be parametrised with radius (r)

Closed curve[edit | edit source]

Simple closed curve ("a connected curve that does not cross itself and ends at the same point where it begins"[18] = having no endpoints) can be parametrized with angle (t).

Edge detection[edit | edit source]

Sobel filter[edit | edit source]

Short introduction[edit | edit source]

Sobel filter G consist of 2 kernels (masks):

  • Gh for horizontal changes.
  • Gv for vertical changes.
Sobel kernels[edit | edit source]
8-point neighborhood on a 2D grid
2D Convolution Animation

The Sobel kernel contains weights for each pixel from the 8-point neighbourhood of a tested pixel. These are 3x3 kernels.

There are 2 Sobel kernels, one for computing horizontal changes and other for computing vertical changes. Notice that a large horizontal change may indicate a vertical border, and a large vertical change may indicate a horizontal border. The x-coordinate is here defined as increasing in the "right"-direction, and the y-coordinate is defined as increasing in the "down"-direction.

The Sobel kernel for computing horizontal changes is:

The Sobel kernel for computing vertical changes is:

Note that:

  • sum of weights of kernels are zero

  • One kernel is simply the other rotated by 90 degrees.[20]
  • 3 weights in each kernal are zero.
Pixel kernel[edit | edit source]

Pixel kernel A containing central pixel with its 3x3 neighbourhood:

Other notations for pixel kernel:


unsigned char ul, // upper left
unsigned char um, // upper middle
unsigned char ur, // upper right
unsigned char ml, // middle left
unsigned char mm, // middle = central pixel
unsigned char mr, // middle right
unsigned char ll, // lower left
unsigned char lm, // lower middle
unsigned char lr, // lower right
Pixel 3x3 neighbourhood (with Y axis directed down)

In array notation it is:[22]

In geographic notation usede in cellular aotomats[check spelling] it is central pixel of Moore neighbourhood.

So central (tested) pixel is:

Sobel filters[edit | edit source]

Compute Sobel filters (where here denotes the 2-dimensional convolution operation not matrix multiplication). It is a sum of products of pixel and its weights:

Because 3 weights in each kernal are zero so there are only 6 products.[23]

short Gh = ur + 2*mr + lr - ul - 2*ml - ll;
short Gv = ul + 2*um + ur - ll - 2*lm - lr;
Result[edit | edit source]

Result is computed (magnitude of gradient):

It is a color of tested pixel.

One can also approximate result by sum of 2 magnitudes:

which is much faster to compute.[24]

Algorithm[edit | edit source]

  • choose pixel and its 3x3 neighberhood A
  • compute Sobel filter for horizontal Gh and vertical lines Gv
  • compute Sobel filter G
  • compute color of pixel

Programming[edit | edit source]

Sobel filters (2 filters 3x3): image and full c code
Skipped pixel - some points from its neighbourhood are out of the image

Lets take array of 8-bit colors (image) called data. To find borders in this image simply do:

     Gv= - data[iY-1][iX-1] - 2*data[iY-1][iX] - data[iY-1][iX+1] + data[iY+1][iX-1] + 2*data[iY+1][iX] + data[iY+1][iX+1];
     Gh= - data[iY+1][iX-1] + data[iY-1][iX+1] - 2*data[iY][iX-1] + 2*data[iY][iX+1] - data[iY-1][iX-1] + data[iY+1][iX+1];
     G = sqrt(Gh*Gh + Gv*Gv);
     if (G==0) {edge[iY][iX]=255;} /* background */
         else {edge[iY][iX]=0;}  /* boundary */

Note that here points on borders of array (iY= 0, iY = iYmax, iX=0, iX=iXmax) are skipped

Result is saved to another array called edge (with the same size).

One can save edge array to file showing only borders, or merge 2 arrays:

    for(iX=1;iX<iXmax-1;++iX){ if (edge[iY][iX]==0) data[iY][iX]=0;}}

to have new image with marked borders.

Above example is for 8-bit or indexed color. For higher bit colors "the formula is applied to all three color channels separately" (from RoboRealm doc).

Other implementations:

Problems[edit | edit source]

Bad edge position seen in the middle of image. Lines are not meeting in good points, like z = 0

Edge position:

In ImageMagick as "you can see, the edge is added only to areas with a color gradient that is more than 50% white! I don't know if this is a bug or intentional, but it means that the edge in the above is located almost completely in the white parts of the original mask image. This fact can be extremely important when making use of the results of the "-edge" operator."[25]

The result is:

  • doubling edges; "if you are edge detecting an image containing an black outline, the "-edge" operator will 'twin' the black lines, producing a weird result."[26]
  • lines are not meeting in good points.

See also new operators from 6 version of ImageMagick: EdgeIn and EdgeOut from Morphology[27]

Edge thickening[edit | edit source]


convert $tmp0 -convolve "1,1,1,1,1,1,1,1,1" -threshold 0 $outfile

Filling contour[edit | edit source]

Filling contour - simple procedure in c

Quality of image[edit | edit source]

  • " using 100 samples per pixel, so rendered the full image 100 times with small random jitter (movement at sub pixel size) and accumulate the result, gives really nice antialiasing." 3DickUlus
  • Tips for making better images by Paul Bourke
    • do the fractal creation not in 8 bit, but use 16 bit or floating point for each pixel ( pfm file, kfb and exr ( OpenEXR) from Kalles Fraktaler or array with floating point values )
    • apply antialiasing by supersampling each final pixel ( render a 30,000 pixel version of the image )
    • do all colour external to the fractal creation using gradient maps...allows you to make appearance decisions independent to the creation

Interval arithmetic[edit | edit source]

Antialiasing[edit | edit source]

Aliased chessboard - image and c src code

Supersampling[edit | edit source]

example of supersampled image
Cpp code of supersampling

Other names:

  • antigrain geometry
  • Supersampling (downsampling)[39][40]
  • downsizing
  • downscaling[41]
  • subpixel accuracy


 // subpixels finished -> make arithmetic mean
 char pixel[3];
 for (int c = 0; c < 3; c++)
   pixel[c] = (int)(255.0 * sum[c] / (subpix * subpix)  + 0.5);
 fwrite(pixel, 1, 3, image_file);
 //pixel finished
  • command line version of Aptus (python and c code) by Ned Batchelder[42] (see is using a high-quality downsampling filter thru PIL function resize[43]
  • Java code by Josef Jelinek:[44] supersampling with grid algorithm, computes 4 new points (corners), resulting color is an average of each color component:
 //Created by Josef Jelinek
 Color c0 = color(dx, dy); // color of central point
 // computation of 4 new points for antialiasing
 if (antialias) { // computes 4 new points (corners)
   Color c1 = color(dx - 0.25 * r, dy - 0.25 * r);
   Color c2 = color(dx + 0.25 * r, dy - 0.25 * r);
   Color c3 = color(dx + 0.25 * r, dy + 0.25 * r);
   Color c4 = color(dx - 0.25 * r, dy + 0.25 * r);
  // resulting color; each component of color is an avarage of 5 values (central point and 4 corners)
   int red = (c0.getRed() + c1.getRed() + c2.getRed() + c3.getRed() + c4.getRed()) / 5;
   int green = (c0.getGreen() + c1.getGreen() + c2.getGreen() + c3.getGreen() + c4.getGreen()) / 5;
   int blue = (c0.getBlue() + c1.getBlue() + c2.getBlue() + c3.getBlue() + c4.getBlue()) / 5;
   color = new Color(red, green, blue);
  • one can make big image (like 10 000 x 10 000) and convert/resize it (downsize). For example using ImageMagick:
convert big.ppm -resize 2000x2000 m.png

See also:

realistic 2D static images[edit | edit source]

realistic 2D static images [47]

  • Higher pixel resolution ("4k" and "8k").
  • Wider color gamut (WCG) : express a wider range of colors than today ( BT.2020 color gamut )
  • High Dynamic Range (HDR): express a wider range of luminance than today.

Check if you are ready:

Plane[edit | edit source]

Description is here.

Optimization[edit | edit source]

Optimisation is described here

References[edit | edit source]

  1. IPOL Journal · Image Processing On Line
  2. ImageMagick image processing libraries
  3. GEGL (Generic Graphics Library)
  6. GD Graphics Library
  7. GraphicsMagick
  8. OpenCv
  9. OpenImageIO
  10. educativesite : 2 d-graphics-pipeline-block-diagram
  11. MIT 6.837 Fall 2012 Undergraduate Computer Graphics Lecture notes
  12. w:Direct Rendering Infrastructure (DRI)
  13. wikipedia: Field line
  14. Curve sketching in wikipedia
  16. Predicting the shape of distance functions in curve tracing: Evidence for a zoom lens operator by PETER A. McCORMICK and PIERRE JOLICOEUR
  17. stackoverflow question: line-tracking-with-matlab
  18. mathwords: simple_closed_curve
  19. matrixlab - line-detection
  20. Sobel Edge Detector by R. Fisher, S. Perkins, A. Walker and E. Wolfart.
  21. NVIDIA Forums, CUDA GPU Computing discussion by kr1_karin
  22. Sobel Edge by RoboRealm
  23. nvidia forum: Sobel Filter Don't understand a little thing in the SDK example
  24. Sobel Edge Detector by R. Fisher, S. Perkins, A. Walker and E. Wolfart.
  25. ImageMagick doc
  26. Edge operator from ImageMagick docs
  27. ImageMagick doc: morphology / EdgeIn
  28. dilation at HIPR2 by Robert Fisher, Simon Perkins, Ashley Walker, Erik Wolfart
  29. ImageMagick doc: morphology, dilate
  30. Fred's ImageMagick Scripts
  31. Images of Julia sets that you can trust Luiz Henrique de Figueiredo
  33. "Images of Julia sets that you can trust" by Luiz Henrique de Figueiredo and Joao Batista Oliveira
  34. adaptive algorithms for generating guaranteed images of Julia sets by Luiz Henrique de Figueiredo
  35. Drawing Fractals With Interval Arithmetic - Part 1 by Dr Rupert Rawnsley
  36. Drawing Fractals With Interval Arithmetic - Part 2 by Dr Rupert Rawnsley
  37. Spatial anti aliasing at wikipedia
  38. fractalforums discussion: Antialiasing fractals - how best to do it?
  39. Supersampling at wikipedia
  40. ImageMagick v6 Examples -- Resampling Filters
  41. What is the best image downscaling algorithm (quality-wise)?
  42. Aptus (python and c code) by Ned Batchelder
  43. Pil function resize
  44. Java code by Josef Jelinek
  45. ImageMagick: resize_gamma
  46. A Cheritat wiki: see image showing gamma-correct downscale of dense part of Mandelbrot set
  47. Linux and High Dynamic Range (HDR) Display by Andy Ritger ( 2016)