Freigeben über

Simplifying zoom box implementation

  • Artikel

Building on information presented in Mapping screen coordinates to the complex plane, here we look at how to rewrite Mandelbrot 1 in order to simplify the implementation of the zoom box feature.

For performance reasons and because the coordinates of a zoom box (upper-left and lower-right corners) will always be in canvas screen coordinates, we rewrite Mandelbrot 1 as follows:

Mandelbrot 2

<!DOCTYPE html>
<html>

<head>
  <meta content="text/html; charset=utf-8" http-equiv="Content-Type">
  <title>Mandelbrot 2</title>
  <style>
    html, body {
      margin: 0;
      padding: 0;
      text-align: center;
    }
    
    canvas {
      border: 1px black solid;
    }
  </style>
</head>

<body>
  <h1>Mandelbrot 2</h1>
  <p>This example demonstrates an algorithm for drawing the Mandelbrot set using canvas screen coordinates.</p>  
  <canvas width="600" height="400">Canvas not supported - upgrade your browser</canvas>
  <script>
    var RE_MAX = 1.1; // This value will be adjusted as necessary to ensure that the rendered Mandelbrot set is never skewed (that is, true to it's actual shape).
    var RE_MIN = -2.5;
    var IM_MAX = 1.2;
    var IM_MIN = -1.2;
    var MAX_ITERATIONS = 300; // Increase to improve detection of complex c values that belong to the Mandelbrot set.

    var globals = {}; // Store all would-be-global-variables in one handy global object.
    globals.canvas = document.getElementsByTagName('canvas')[0];
    globals.canvas.ctx = globals.canvas.getContext('2d');
    globals.canvas.ctx.fillStyle = "black"
    
    drawMandelbrotSet(RE_MAX, RE_MIN, IM_MAX, IM_MIN);
    
    function drawMandelbrotSet(ReMax, ReMin, ImMax, ImMin) {   
      var canvasWidth = globals.canvas.width; // A small speed optimization.
      var canvasHeight = globals.canvas.height; // A small speed optimization.
             
      ReMax = canvasWidth * ( (ImMax - ImMin) / canvasHeight ) + ReMin; // Make the width and height of the complex plane proportional to the width and height of the canvas.                
      
      if (RE_MAX != ReMax) {
        alert("RE_MAX has been adjusted to: " + ReMax); // The user should never see this if RE_MAX is set correctly above.
      } // if

      var ctx = globals.canvas.ctx;

      var x_coefficient = (ReMax - ReMin) / canvasWidth; // Keep the Mandelbrot loop as computation-free as possible.
      var y_coefficient = (ImMin - ImMax) / canvasHeight; // Keep the Mandelbrot loop as computation-free as possible.
        
      for (var x = 0; x < canvasWidth; x++) {
        var c_Re = (x * x_coefficient) + ReMin // Convert the canvas x-coordinate to a complex plane Re-coordinate. c_Re represents the real part of a c value.

        for (var y = 0; y < canvasHeight; y++) {
          var c_Im = (y * y_coefficient) + ImMax; // Recall that c = c_Re + c_Im*i
          
          var z_Re = 0; // Recall that the first z value (Zo) must be 0.
          var z_Im = 0; // Recall that the first z value (Zo) must be 0.
          
          var c_belongsToMandelbrotSet = true;
          for (var iterationCount = 1; iterationCount <= MAX_ITERATIONS; iterationCount++) {
            var z_Re_squared = z_Re * z_Re; // A small speed optimization.
            var z_Im_squared = z_Im * z_Im; // A small speed optimization.
            
            // The next two lines perform Zn+1 = (Zn)^2 + c (note that (x + yi)^2 = x^2 - y^2 + 2xyi, thus the real part is x^2 - y^2 and the imaginary part is 2xyi).
            z_Im = (2 * z_Re * z_Im) + c_Im; // We must calculate z_Im first because it's a function of z_Re.          
            z_Re = z_Re_squared - z_Im_squared + c_Re; // The is not a function of z_Re.

            if ( z_Re_squared + z_Im_squared > 4 ) { // Checks if |z^2| is greater than 2.
              c_belongsToMandelbrotSet = false; // This complex c value is not part of the Mandelbrot set.
              break; // So we immediately check the next c value.
            } // if
          } // for          
                    
          if (c_belongsToMandelbrotSet) { 
            ctx.fillRect(x, y, 1, 1);  // This c value is probably part of the Mandelbrot set, so set the color of the associated pixel to black. Increase MAX_ITERATIONS to increase the probability.
          } // if
        } // for
      } // for
    } // drawMandelbrotSet    
  </script>
</body>

</html>

The first thing to notice is that the complex class has been replaced with more performant in-loop calculations. For example, the expensive square root operation associated with z.modulus() > 2 has been replaced with z_Re_squared + z_Im_squared > 4 in that:

A number of other small optimizations have been made in order to remove as many calculations as possible from the three (triply-nested) for loops as indicated by the comments in the previous code example.

Next, recall that our transformation equations assume proportionality (see Mapping screen coordinates to the complex plane). The line:

ReMax = canvasWidth * ( (ImMax - ImMin) / canvasHeight ) + ReMin;

ensures that the width and height of the complex plane are proportional to the width and height of the canvas. Without this check, it's possible to choose a value for RE_MAX that would break the proportionality assumption, resulting in a skewed image of the Mandelbrot set.

The major difference between Mandelbrot 1 and Mandelbrot 2, however, is the fact that each canvas pixel is now considered to be a c value:

for (var x = 0; x < canvasWidth; x++) {
  var c_Re = (x * x_coefficient) + ReMin // Convert the canvas x-coordinate to a complex plane Re-coordinate. c_Re represents the real part of a c value.
  for (var y = 0; y < canvasHeight; y++) {
    var c_Im = (y * y_coefficient) + ImMax; // Recall that c = c_Re + c_Im*i
    ...

Here we loop through each canvas pixel (x, y) and construct the associated (coincident) c point (c_Re, c_Im) in the complex plane using the coordinate transformation equations described in Mapping screen coordinates to the complex plane.

Next, we construct z₀ (which must always be 0) to determine if c is in the Mandelbrot set or not by observing the behavior of z under iteration of zₙ₊₁ = zₙ + c:

var z_Re = 0; // Recall that the first z value (Zo) must be 0.
var z_Im = 0; // Recall that the first z value (Zo) must be 0.

var c_belongsToMandelbrotSet = true;
for (var iterationCount = 1; iterationCount <= MAX_ITERATIONS; iterationCount++) {
  var z_Re_squared = z_Re * z_Re; // A small speed optimization.
  var z_Im_squared = z_Im * z_Im; // A small speed optimization.
  
  // The next two lines perform Zn+1 = (Zn)^2 + c (note that (x + yi)^2 = x^2 - y^2 + 2xyi, thus the real part is x^2 - y^2 and the imaginary part is 2xyi).
  z_Im = (2 * z_Re * z_Im) + c_Im; // We must calculate z_Im first because it's a function of z_Re.          
  z_Re = z_Re_squared - z_Im_squared + c_Re; // The is not a function of z_Re.

  if ( z_Re_squared + z_Im_squared > 4 ) { // Checks if |z^2| is greater than 2.
    c_belongsToMandelbrotSet = false; // This complex c value is not part of the Mandelbrot set.
    break; // So we immediately check the next c value.
  } // if
} // for          
          
if (c_belongsToMandelbrotSet) { 
  ctx.fillRect(x, y, 1, 1);  // This c value is probably part of the Mandelbrot set, so set the color of the associated pixel to black. Increase MAX_ITERATIONS to increase the probability.
} // if

To explain this code fragment, consider the following expansion of the Mandelbrot recurrence relation:

Because zₙ₊₁ = Aₙ + Bₙi, the real Aₙ and Bₙ values can be used to calculate zₙ₊₂ as follows:

Furthermore, we can use the values of Aₙ and Bₙ to calculate Aₙ₊₁ and Bₙ₊₁, as follows:

And using Aₙ₊₁ and Bₙ₊₁, zₙ₊₃ is calculated as above:

This inductive argument can be extended indefinitely to calculate as many z values as required, and in particular, explains the previous two lines, which are repeated here:

z_Im = (2 * z_Re * z_Im) + c_Im; 
z_Re = z_Re_squared - z_Im_squared + c_Re;

That is, the first line is equivalent to:

And the second to:

Be aware that if z_Re where calculated before z_Im (that is, if the previous two lines were switched), the formula for z_Im would not be using the current value of z_Re, but the next value of z_Re, producing incorrect results.

Lastly, if the absolute value of zₙ doesn't tend towards infinity (that is, z_Re_squared + z_Im_squared <= 4) within MAX_ITERATIONS, then the associated c value, that is the point (x, y) in the canvas coordinate system representing c, is (most likely) part of the Mandelbrot set and we paint the pixel at (x, y) black. Otherwise, (z_Re_squared + z_Im_squared > 4) and c is not part of the Mandelbrot set, and the pixel at (x, y) remains white.

Now that we have a means of converting canvas screen coordinates to the complex plane, we're in a position to implement zoom box functionality, as discussed in Implementing a zoom box.

Implementing a zoom box