Javascript Julia Fractal 缓慢且不详细

Question

我正在尝试使用 math.js

在 javascript 中的 canvas 中生成 Julia 分形

不幸的是每次在canvas上绘制分形都比较慢而且不是很详细

任何人都可以告诉我这个脚本如此缓慢是否有特定原因，或者只是对浏览器的要求太多？（注意：鼠标移动部分被禁用，它仍然有点慢）

我试过升高和降低“bail_num”，但是高于 1 的所有内容都会使浏览器崩溃，低于 0.2 的所有内容都会使所有内容变黑。

// Get the canvas and context
var canvas = document.getElementById("myCanvas"); 
var context = canvas.getContext("2d");

// Width and height of the image
var imagew = canvas.width;
var imageh = canvas.height;

// Image Data (RGBA)
var imagedata = context.createImageData(imagew, imageh);

// Pan and zoom parameters
var offsetx = -imagew/2;
var offsety = -imageh/2;
var panx = -2000;
var pany = -1000;
var zoom = 12000;

// c complexnumber
var c = math.complex(-0.310, 0.353);

// Palette array of 256 colors
var palette = [];

// The maximum number of iterations per pixel
var maxiterations = 200;
var bail_num = 1;


// Initialize the game
function init() {

//onmousemove listener
canvas.addEventListener('mousemove', onmousemove);

    // Generate image
    generateImage();

    // Enter main loop
    main(0);
}

// Main loop
function main(tframe) {
    // Request animation frames
    window.requestAnimationFrame(main);

    // Draw the generate image
    context.putImageData(imagedata, 0, 0);
}

// Generate the fractal image
function generateImage() {
    // Iterate over the pixels
    for (var y=0; y<imageh; y++) {
        for (var x=0; x<imagew; x++) {
            iterate(x, y, maxiterations);
        }
    }
}

// Calculate the color of a specific pixel
function iterate(x, y, maxiterations) {
    // Convert the screen coordinate to a fractal coordinate
    var x0 = (x + offsetx + panx) / zoom;
    var y0 = (y + offsety + pany) / zoom;
    var cn = math.complex(x0, y0);

    // Iterate
    var iterations = 0;
    while (iterations < maxiterations && math.norm(math.complex(cn))< bail_num ) {
        cn = math.add( math.sqrt(cn) , c);   
        iterations++;
    }

    // Get color based on the number of iterations
    var color;
    if (iterations == maxiterations) {
        color = { r:0, g:0, b:0}; // Black
    } else {
        var index = Math.floor((iterations / (maxiterations)) * 255);
        color = index;
    }

    // Apply the color
    var pixelindex = (y * imagew + x) * 4;
    imagedata.data[pixelindex] = color;
    imagedata.data[pixelindex+1] = color;
    imagedata.data[pixelindex+2] = color;
    imagedata.data[pixelindex+3] = 255;
}


function onmousemove(e){
var pos = getMousePos(canvas, e);
//c = math.complex(-0.3+pos.x/imagew, 0.413-pos.y/imageh);

//console.log( 'Mouse position: ' + pos.x/imagew + ',' + pos.y/imageh );

// Generate a new image
    generateImage();

}

function getMousePos(canvas, e) {
    var rect = canvas.getBoundingClientRect();
    return {
        x: Math.round((e.clientX - rect.left)/(rect.right - rect.left)*canvas.width),
        y: Math.round((e.clientY - rect.top)/(rect.bottom - rect.top)*canvas.height)
    };
}
init();

Answer 1

代码执行最多的部分是这段：

while (iterations < maxiterations && math.norm(math.complex(cn))< bail_num ) {
    cn = math.add( math.sqrt(cn) , c);   
    iterations++;
}

对于给定的 canvas 大小和您使用的偏移量，上面的 while 主体被执行了 19,575,194 次。因此，有一些明显的方法可以提高性能：

以某种方式减少必须执行循环的点数
以某种方式减少每个点执行这些语句的次数
以某种方式改进这些语句，使它们执行得更快

第一个想法很简单：减少 canvas 维度。但这可能不是你想做的事情。

第二个想法可以通过减小 bail_num 的值来实现，因为这样 while 条件将更快被违反（假定 norm 复数总是正实数）。然而，这只会导致更黑，并提供与缩小分形中心相同的视觉效果。例如尝试使用 0.225：只剩下 "distant star"。当 bail_num 减少太多时，你甚至找不到分形了，因为一切都变黑了。因此，为了补偿，您可能需要更改偏移和缩放系数，以便更近距离地查看分形中心（顺便说一句，它仍然在那里！）。但是朝向分形的中心，点需要更多的迭代才能低于 bail_num，所以最后什么也得不到：你会回到第一个方块用这个方法.这不是真正的解决方案。

另一种实现第二个想法的方法是减少最大迭代次数。但是，这将相应地降低分辨率。很明显，您可以使用的颜色会更少，因为这个数字直接对应于您最多可以拥有的迭代次数。

第三个想法意味着您将以某种方式优化复数的计算。事实证明收获颇丰：

使用高效计算

在while条件下计算出的范数可以作为计算同一个数的平方根的中间值，在下一条语句中需要用到。这是从复数求平方根的公式，如果你已经有了它的范数：

           __________________
root.re = √ ½(cn.re + norm)
root.im = ½cn.im/root.re

其中 re 和 im 属性表示相应复数的实部和虚部。您可以在 this answer on math.stackexchange.

中找到这些公式的背景

因为你的代码中平方根是单独计算的，没有利用前面计算范数的优势，这肯定会带来好处。

此外，在 while 条件下，您实际上并不需要与 bail_num 进行比较的范数（涉及平方根）。可以省略平方根运算，与bail_num的平方比较，结果是一样的。显然，您只需在代码开头计算一次 bail_num 的平方。这样您就可以在发现条件为真时延迟平方根运算。范数平方的计算公式如下：

square_norm = cn.re² + cn.im²

对 math 对象的方法调用有一些开销，因为该库允许在其多个方法中使用不同类型的参数。因此，如果您不依赖 math.js 直接编写计算代码，将有助于提高性能。无论如何，上述改进已经开始这样做了。在我的尝试中，这也带来了相当大的性能提升。

预定义颜色

虽然与昂贵的 while 循环无关，但您可以通过在代码开头计算所有可能的颜色（根据迭代次数）并将它们存储在数组中来获得更多收益以迭代次数为关键字。这样您就可以在实际计算期间执行查找。

可以做一些其他类似的事情来节省计算：例如，您可以避免在沿 X 轴移动时将屏幕 y 坐标转换为世界坐标，因为它始终是相同的值。

这是在我的 PC 上将原始完成时间缩短了 10 倍的代码：

添加了初始化：

// Pre-calculate the square of bail_num:
var bail_num_square = bail_num*bail_num;
// Pre-calculate the colors:
colors = [];
for (var iterations = 0; iterations <= maxiterations; iterations++) {
    // Note that I have stored colours in the opposite direction to 
    // allow for a more efficient "countdown" loop later
    colors[iterations] = 255 - Math.floor((iterations / maxiterations) * 255);
}
// Instead of using math for initialising c:
var cx = -0.310;
var cy = 0.353;

用这个函数替换函数 `generateImage` 和 `iterate`

// Generate the fractal image
function generateImage() {
    // Iterate over the pixels
    var pixelindex = 0,
        step = 1/zoom,
        worldX, worldY,
        sq, rootX, rootY, x0, y0;
    for (var y=0; y<imageh; y++) {
        worldY = (y + offsety + pany)/zoom;
        worldX = (offsetx + panx)/zoom;
        for (var x=0; x<imagew; x++) {
            x0 = worldX;
            y0 = worldY;
            // For this point: iterate to determine color index
            for (var iterations = maxiterations; iterations && (sq = (x0*x0+y0*y0)) < bail_num_square; iterations-- ) {
                // root of complex number
                rootX = Math.sqrt((x0 + Math.sqrt(sq))/2);
                rootY = y0/(2*rootX);
                x0 = rootX + cx;
                y0 = rootY + cy;
            }
            // Apply the color
            imagedata.data[pixelindex++] = 
                imagedata.data[pixelindex++] = 
                imagedata.data[pixelindex++] = colors[iterations];
            imagedata.data[pixelindex++] = 255;
            worldX += step;
        }
    }
}

使用上面的代码，您不再需要包含 math.js。

这是一个处理了鼠标事件的小片段：

// Get the canvas and context
var canvas = document.getElementById("myCanvas"); 
var context = canvas.getContext("2d");

// Width and height of the image
var imagew = canvas.width;
var imageh = canvas.height;

// Image Data (RGBA)
var imagedata = context.createImageData(imagew, imageh);

// Pan and zoom parameters
var offsetx = -512
var offsety = -430;
var panx = -2000;
var pany = -1000;
var zoom = 12000;

// Palette array of 256 colors
var palette = [];

// The maximum number of iterations per pixel
var maxiterations = 200;
var bail_num = 0.8; //0.225; //1.15;//0.25;

// Pre-calculate the square of bail_num:
var bail_num_square = bail_num*bail_num;
// Pre-calculate the colors:
colors = [];
for (var iterations = 0; iterations <= maxiterations; iterations++) {
    colors[iterations] = 255 - Math.floor((iterations / maxiterations) * 255);
}
// Instead of using math for initialising c:
var cx = -0.310;
var cy = 0.353;

// Initialize the game
function init() {

    // onmousemove listener
    canvas.addEventListener('mousemove', onmousemove);

    // Generate image
    generateImage();

    // Enter main loop
    main(0);
}

// Main loop
function main(tframe) {
    // Request animation frames
    window.requestAnimationFrame(main);

    // Draw the generate image
    context.putImageData(imagedata, 0, 0);
}

// Generate the fractal image
function generateImage() {
    // Iterate over the pixels
    console.log('generate', cx, cy);
    var pixelindex = 0,
        step = 1/zoom,
        worldX, worldY,
        sq_norm, rootX, rootY, x0, y0;
    for (var y=0; y<imageh; y++) {
        worldY = (y + offsety + pany)/zoom;
        worldX = (offsetx + panx)/zoom;
        for (var x=0; x<imagew; x++) {
            x0 = worldX;
            y0 = worldY;
            // For this point: iterate to determine color index
            for (var iterations = maxiterations; iterations && (sq_norm = (x0*x0+y0*y0)) < bail_num_square; iterations-- ) {
                // root of complex number
                rootX = Math.sqrt((x0 + Math.sqrt(sq_norm))/2);
                rootY = y0/(2*rootX);
                x0 = rootX + cx;
                y0 = rootY + cy;
            }
            // Apply the color
            imagedata.data[pixelindex++] = 
                imagedata.data[pixelindex++] = 
                imagedata.data[pixelindex++] = colors[iterations];
            imagedata.data[pixelindex++] = 255;
            worldX += step;
        }
    }
    console.log(pixelindex);
}


function onmousemove(e){
    var pos = getMousePos(canvas, e);
    cx = -0.31+pos.x/imagew/150;
    cy = 0.35-pos.y/imageh/30;
    

    generateImage();
}

function getMousePos(canvas, e) {
    var rect = canvas.getBoundingClientRect();
    return {
        x: Math.round((e.clientX - rect.left)/(rect.right - rect.left)*canvas.width),
        y: Math.round((e.clientY - rect.top)/(rect.bottom - rect.top)*canvas.height)
    };
}
init();

<canvas id="myCanvas" width="512" height="200"></canvas>

Javascript Julia Fractal 缓慢且不详细

Javascript Julia Fractal slow and not detailed

javascript

performance

fractals

math.js

使用高效计算

预定义颜色

添加了初始化：

用这个函数替换函数 `generateImage` 和 `iterate`

Javascript Julia Fractal 缓慢且不详细

Javascript Julia Fractal slow and not detailed

javascript

performance

fractals

math.js

使用高效计算

预定义颜色

添加了初始化：

用这个函数替换函数 generateImage 和 iterate

用这个函数替换函数 `generateImage` 和 `iterate`