Exporter (0) Imprimer
Développer tout

Simplification de la mise en œuvre de la zone d’agrandissement

S’appuyant sur les informations présentées dans Mappage de coordonnées d’écran au plan complexe, cette rubrique examine comment réécrire Mandelbrot 1 pour simplifier la mise en œuvre de la fonctionnalité de zone d’agrandissement.

Pour des raisons de performances et du fait que les coordonnées d’une zone d’agrandissement (coins supérieur gauche et inférieur droit) seront toujours en coordonnées d’écran de zone de dessin, nous réécrivons Mandelbrot 1 comme suit :

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>

La première chose à remarquer est que la classe complexe a été remplacée par des calculs en boucle plus performants. Par exemple, l’opération de racine carrée coûteuse associée à z.modulus() > 2 a été remplacée par z_Re_squared + z_Im_squared > 4 comme suit :

Module mis au carré

Quelques autres petites optimisations ont été effectuées afin de supprimer le plus de calculs possibles des trois boucles for (à triple imbrication), comme indiqué par les commentaires dans l’exemple de code précédent.

Ensuite, souvenez-vous que nos équations de transformation supposent qu’il existe une proportionnalité (voir Mappage de coordonnées d’écran au plan complexe). La ligne :

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

permet de s’assurer que la largeur et la hauteur du plan complexe sont proportionnelles à la largeur et à la hauteur de la zone de dessin. Sans cette vérification, il serait possible de choisir une valeur RE_MAX qui enfreindrait la supposition de proportionnalité, ce qui génèrerait une image penchée de l’ensemble de Mandelbrot.

La principale différence entre Mandelbrot 1 et Mandelbrot 2, toutefois, est le fait que chaque pixel de la zone de dessin est maintenant considéré comme une valeur c :

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
    ...

Ici, nous parcourons en boucle chaque pixel de la zone de dessin (x, y) et nous construisons le point c associé (coincident) (c_Re, c_Im) dans le plan complexe à l’aide des équations de transformation de coordonnées décrites dans Mappage de coordonnées d’écran au plan complexe.

Ensuite, nous construisons z0 (qui doit toujours être 0) pour déterminer si c est dans l’ensemble de Mandelbrot en observant le comportement de z en cas d’itération de zn+1 = zn + 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

Pour expliquer ce fragment de code, considérez l’extension suivante de la relation de récurrence de Mandelbrot :

Extension symbolique de relation de récurrence de Mandelbrot pour l’itération 1

Étant donné que zn+1 = An + Bni, les valeurs réelles An et Bn peuvent être utilisées pour calculer zn+2 comme suit :

Extension symbolique de relation de récurrence de Mandelbrot pour l’itération 2 (première partie)

De plus, nous pouvons utiliser les valeurs de An et Bn pour calculer An+1 et Bn+1 comme suit :

Extension symbolique de relation de récurrence de Mandelbrot pour l’itération 2 (deuxième partie)

Et en utilisant An+1 et Bn+1, zn+3 est calculé comme suit :

Extension symbolique de relation de récurrence de Mandelbrot pour l’itération 3

Cet argument inductif peut être étendu à l’infini pour calculer autant de valeurs z qu’on le souhaite et il explique en particulier les deux lignes précédentes, qui sont répétées ici :


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

À savoir, la première ligne équivaut à :

Équation B sub n + 1

Et la seconde équivaut à :

Équation A sub n + 1

Notez que si z_Re était calculé avant z_Im (autrement dit, si l’on intervertissait les deux lignes précédentes), la formule pour z_Im n’utiliserait pas la valeur actuelle de z_Re, mais la valeur suivante de z_Re, ce qui génèrerait des résultats incorrects.

Pour finir, si la valeur absolue de zn ne tend pas vers l’infini (autrement dit, z_Re_squared + z_Im_squared <= 4) dans les limites de MAX_ITERATIONS, alors il est plus que probable que la valeur c associée, c’est-à-dire le point (x, y) dans le système de coordonnées de la zone de dessin représentant c, fait partie de l’ensemble de Mandelbrot et nous peignons le pixel à (x, y) en noir. Autrement, (z_Re_squared + z_Im_squared > 4) et c ne fait pas partie de l’ensemble de Mandelbrot. Le pixel à (x, y) reste donc blanc.

Maintenant que nous connaissons un moyen de convertir des coordonnées d’écran de toile de dessin en plan complexe, nous pouvons implémenter la fonctionnalité de zone d’agrandissement, comme discuté dans Mise en œuvre d’une zone d’agrandissement.

Rubriques connexes

Mise en œuvre d’une zone d’agrandissement

 

 

Afficher:
© 2014 Microsoft