Quineloop

['Gautam Chekuri', 'gautam.chekuri@gmail.com', 'http://github.com/gautamc']
[Observe ∿ deconstruct ∿ Generalize ∿ Reflect ∿ Repeat]

« Back to /index

------------

Rendering Mandelbrot Set using canvas and d3.js

Initially drafted in Aug 2013; updated April 2016

Rendering Mandelbrot set – this is computationally intensive and will take time to render.
Actual runtime depends on your screen resolution & processor.

Describing the Mandelbrot:

1.
1. A “Mandelbrot set” is a set that contains complex numbers.

To check if a given complex number is in the “Mandelbrot set”, we have to perform a certain mathematical operation on the complex number over and over and identify if the result has a certain property.
Meaning:
Given complex number: This refers to any complex number that we can choose at will – to check if it is in the “Mandelbrot set”

The repetitive mathematical operation:
A simplified but not accurate description of the mathematical operation can say that we square the given complex number and add it to itself.
We repeat this operation over and over until we can determine if the result will always stay less than some value.
This property of always staying less then some value is called being “bounded”.
If the result of a repetitive operation is not bounded then it means that it will be -
Ever increasing – if it moves toward positive Infinity
or
Ever decreasing – if it moves toward negative Infinity
This behavior is called “escaping to Infinity”.

The operation can be accurately described as the following function:
fc z = z2 + c
Where c is the Given complex number
and z – the parameter passed to this function – is the result we got from the previous call to this function.
When we call the function for the first time we use Zero as the value of z.
One must note that the “Given complex number” c is a constant in the function.
The subscript c in fc is simply a convention which remainds us that the “Given complex number” plays a part in defining the behavior of this function.

Property of the mathematical operation’s result:
If, for a given complex number, the result of this repeated operation will remain within some bounds than we conclude that the complex number is in the “Mandelbrot set”.
If the result of this repeated operation does not stay within any bounds and keeps moving towards Infinity with each repetition – then the complex number is not a member of the “Mandelbrot set”.

In the popular “Mandelbrot set” visualization, each pixel on the screen represents a complex number.
A pixel is colored black if the complex number it represents is part of “Mandelbrot set”.
If the complex number representing a pixel is not in the “Mandelbrot set” then we assign it a color based on how quickly we were able to determine that it is not a member of the “Mandelbrot set”.

How do we implement this as a program?

2.
2. Loop over all complex numbers in the complex plane:
Every complex number in the complex plane is either in the Mandelbrot set or it is not.
Therefore, to build the Mandelbrot set we have to take each complex number in the complex plane and check if it is in the Mandelbrot set.

For example, the following block of code uses two loops, one nested inside the other, to print complex numbers between -1 + -1i and 1 + 1i ; in steps of 0.5:
for(
  var real_part = -1.0;
      real_part <= 1.0;
      real_part += 0.5
) {
  for(
    var imaginary_part = -1.0;
        imaginary_part <= 1.0;
        imaginary_part += 0.5
  ) {
    var given_complex_number = {
      real: real_part,
      imaginary: imaginary_part
    }
    console.log(
      given_complex_number.real +
      ' + ' +
      given_complex_number.imaginary +
      'i'
    )
  }
}

But, to create the visualization we need more than just a simple nested loop that can give us complex numbers.

(a) We should be able to transform a screen area of some pixel height & width into a complex plane containing Real and Imaginary axes.
We can use a D3.js scale to transform a screen pixel’s location into a point on the complex plane.

If the Real axis is positioned across the width of the canvas element then we have to map the X coordinate of each pixel along the width to a Real number.
The following example creates a function named real_scale that maps values from 0 to 300 to a number between -2.0 and 1:
> var real_scale = d3.scale.linear()
    .domain([0,300])
    .range([-2.0, 1])
> real_scale(0)
  -2
> real_scale(150)
  -0.5
> real_scale(200)
  0
> real_scale(300)
  1

Similarly, for the imaginary axis along the height of the canvas element, we need to map the Y coordinate of each pixel to a Imaginary number.
The following example creates a function named imaginary_scale. It takes as input a pixel’s Y coordinate and return the imaginary part of a complex number:
> var imaginary_scale = d3.scale.linear()
    .domain([0,300])
    .range([1, -1])
> imaginary_scale(0)
  1
> imaginary_scale(150)
  0
> imaginary_scale(200)
  0
> imaginary_scale(300)
  -1

(b) We should be able to access each pixel so that it can be associated with a complex number.
For efficiently reading & writing indiviual pixels we can use the ImageData object that is part of the canvas element.
The ImageData object can represent the underlying pixel data of an area in a canvas element.

The following block of code creates a 100px by 100px canvas element and uses createImageData to create a ImageData object that can represent 1 pixel.
The ImageData object has a property named data – this an array which stores the RGB & Alpha values for pixels that the object represents.
We can use putImageData() method to write the pixel at certain coordinate on the canvas
// 1. Create a canvas element
var canvas = document.body.appendChild(
  document.createElement('canvas')
)
canvas.setAttribute("height", 100)
canvas.setAttribute("width", 100)
canvas.setAttribute("style", "border: 1px solid black;")

// ctx points to a object that belongs to the canvas.
// It provides functions we use to draw things on the canvas.
ctx = canvas.getContext('2d')

// 2. Create ImageObject to represent 1 pixel
var img_data = ctx.createImageData(1, 1)

// 3. Use the data property to set RGBA values for 1 pixel
img_data.data[0] = 0   // R
img_data.data[1] = 0   // G
img_data.data[2] = 0   // B
img_data.data[3] = 255 // A

// 4. Write to the pixel at canvas location 50, 50
ctx.putImageData(img_data, 50, 50)
// Write to the pixel at canvas location 50, 51
ctx.putImageData(img_data, 50, 51)
// Write to the pixel at canvas location 51, 50
ctx.putImageData(img_data, 51, 50)
// Write to the pixel at canvas location 49, 50
ctx.putImageData(img_data, 49, 50)
// Write to the pixel at canvas location 50, 49
ctx.putImageData(img_data, 50, 49)

Therefore, the block of code that will loop over all complex numers in the complex plane that is bounded in the real axis by [-2.0, 1.0] and in the imaginary_scale by [1, -1]:
var width = 200, height = 200, canvas, ctx, one_pixel, real_scale, imaginary_scale

canvas = document.body.appendChild(
  document.createElement('canvas')
)
canvas.setAttribute("height", height)
canvas.setAttribute("width", width)
ctx = canvas.getContext('2d')
one_pixel = ctx.createImageData(1, 1)

real_scale = d3.scale.linear()
  .domain([0, width])
  .range([-2.0, 1])

imaginary_scale = d3.scale.linear()
  .domain([0, height])
  .range([1, -1])

for(var r = 0; r < width; r++) {
  for(var i = 0; i < height; i++) {

    // c => The given complex number
    var c = { r: real_scale(r), i: imaginary_scale(i) }
    var z = { r: 0, i: 0 }

    // perform the mathematical operation over and over
    // and figure out of the complex number c is in the 
    // Mandelbrot set.

  }
}
3.
3. Repetitive squaring of a complex number and then adding another complex number to it:
Multiplying two complex numbers results in a complex number – in our case, we are multiplying a complex number to itself.
How do we figure out what the real and imaginary parts of this resultant complex number is?
a+bi × a+bi = ?+?i

When multiplying, the real part of the first number is multiplied with the real and imaginary parts of the second number: a×a + a×bi
Similarly, the imaginary part of first number is also multiplied with the real and imaginary parts of the second number: bi×a + bi×bi
Therefore:
a+bi × a+bi = a×a + a×bi + bi×a + bi×bi

Since i2=-1, we can conclude that bi×bi = - b2
Therefore, the Real part of the result for our squaring operation is: a2 - b2

The Imaginary part of the result is: a×bi + bi×a = 2 × a×bi
This multiplication of a imaginary number with a real number results in a imaginary number
- to understand why that should be the case, it helps to realize that i is the multiplicative identity of imaginary numbers.

Implemented in our javascript this multiplication will look like this:
> var z = { r: 1.5, i: 1.5 }
  var square_of_z = { r: null, i: null }

  // Wrong implementation - z.r is already changed in the first statement
  // before it was used in the second statement
  // z.r = (z.r * z.r) - (z.i * z.i)
  // z.i = (2 * z.r * z.i)  // z.r was updated above! this is not the correct!

  // Correct implementation - z.r & z.i remain unchanged
  // when the next two statements are executed
  square_of_z.r = (z.r * z.r) - (z.i * z.i)
  square_of_z.i = (2 * z.r * z.i)

> square_of_z
  Object { r: 0, i: 4.5 }
To correctly calculate the two components of the resultant squared complex number, we should make sure that the original complex number is not updated when the product is still being calculated.
The two statements which calculate the Real and Imaginary components of the product should execute as if they were a single statement.

Adding two complex numbers, simply adds the two Real parts and the two Imaginary parts respectively.
> square_of_z = { r: 0, i: 4.5 } 
  c = { r: 1.5, i: 1.5 }
  new_z = { r: square_of_z.r + c.r, i: square_of_z.i + c.i }
> new_z
  Object { r: 1.5, i: 6 }
Therefore, the javascript code to loop over all complex numbers and then perform the repetitive mathematical operation will look something like this:
var width = 200, height = 200, real_scale, imaginary_scale

real_scale = d3.scale.linear()
  .domain([0, width])
  .range([-2.0, 1])

imaginary_scale = d3.scale.linear()
  .domain([0, height])
  .range([1, -1])

for(var r = 0; r < width; r++) {
  for(var i = 0; i < height; i++) {

    // c => The given complex number
    var c = { r: real_scale(r), i: imaginary_scale(i) }
    var z = { r: 0, i: 0 }
    var math_op_loop_count = 0

    var what_should_this_condition_be = false
    while( what_should_this_condition_be ) {

      // square z - remember that z.r and z.i must both be
      // updated at the same time; hence we use new_z to
      // temporarily store the partially calculated result
      var new_z = {}
      new_z.r = (z.r * z.r) - (z.i * z.i)
      new_z.i = (2 * z.r * z.i)

      // add c to new_z
      new_z.r = new_z.r + c.r
      new_z.i = new_z.i + c.i

      z = new_z

      math_op_loop_count = math_op_loop_count + 1
    }
  }
}
4.
4. Checking if the resulting complex number has been staying bounded:
Now that we have implemented the repetitive mathematical operation, we need to figure out:
(a) The logic to stop the while loop’s execution
(b) The logic for assigning a color to each pixel

(a) To stop the while loop we have to detect if the value of z has remained bounded or if it is escaping to Infinity.

According to the Wikipedia entry for Mandelbrot_set, if the absolute value of z exceeds 2 then we can conclude that z will escaping to Infinity – I still need to figure out the reasoning behind this.
Therefore, we use the absolute value of z as a condition to stop the while loop.

Additionally, complex numbers that are part of the Mandelbrot set, will never escape – i.e their absolute value will never exceed 2. For such values of z, we have to use a second condition to stop the while loop.
This second condition simply counts the number of times the while loop is executed and uses it to stop execution, if the loop has executed more than a 1000 times – again, 1000 is a number that is mentioned in the Wikipedia page.

(b) For assigning a color to each pixel, we can use a D3.js scale that maps the number of times the while loop executed to RGB value or a Alpha value.
In the following block of code we use a linear scale to assign a shade of blue color to each pixel that is not in the Mandelbrot set:
var width = 200, height = 200, canvas, ctx, one_pixel, real_scale, imaginary_scale

canvas = document.getElementById("demo").appendChild(
  document.createElement('canvas')
)
canvas.setAttribute("height", height)
canvas.setAttribute("width", width)
ctx = canvas.getContext('2d')
one_pixel = ctx.createImageData(1, 1)

real_scale = d3.scale.linear()
  .domain([0, width])
  .range([-2.0, 1])

imaginary_scale = d3.scale.linear()
  .domain([0, height])
  .range([1, -1])

var blue_scale = d3.scale.pow()
      .domain([1,20])
      .range([50, 255])

for(var r = 0; r < width; r++) {
  for(var i = 0; i < height; i++) {

    // c => The given complex number
    var c = { r: real_scale(r), i: imaginary_scale(i) }
    var z = { r: 0, i: 0 }
    var math_op_loop_count = 0
    var max_op_loop_count = 1000

    // (z.r * z.r) + (z.i * z.i) => Absolute value of the complex number z 
    while( ((z.r * z.r) + (z.i * z.i) < 2) && (math_op_loop_count < max_op_loop_count) ) {

      // square z - remember that z.r and z.i must both be
      // updated at the same time; hence we use new_z to
      // temporarily store the partially calculated result
      var new_z = {}
      new_z.r = (z.r * z.r) - (z.i * z.i)
      new_z.i = (2 * z.r * z.i)

      // add c to new_z
      new_z.r = new_z.r + c.r
      new_z.i = new_z.i + c.i

      z = new_z

      math_op_loop_count = math_op_loop_count + 1
    }

    if( math_op_loop_count == max_op_loop_count ) {
      one_pixel.data[0] = 0
      one_pixel.data[1] = 0
      one_pixel.data[2] = 0
      one_pixel.data[3] = 255
      ctx.putImageData(one_pixel, r, i)
    } else {
      one_pixel.data[0] = 0
      one_pixel.data[1] = 0
      one_pixel.data[2] = blue_scale(math_op_loop_count)
      one_pixel.data[3] = 255
      ctx.putImageData(one_pixel, r, i)
    }
  }
}
Run this code to see the output.
5.
5. Knowing about the Mandelbrot set and understanding the basic algorithm for visualizing it is indeed very useful.
The algorithm can be used to implement computationally intensive code.
The CUDA GPU programming SDK includes the Mandelbrot set as one of the examples.
-----------

« Back to /index