用于 HTML 画布的更快 Bresenham 线

Question

缓慢渲染

我正在使用Bresenham 的线条算法来实时渲染像素艺术线条。它一次渲染 1 个像素，ctx.rect(x,y,1,1)这是一个缓慢的操作。我无法使用像素缓冲区，这会大大减少渲染开销，因为我正在使用复合操作、alpha 和过滤器（其中一些会污染画布）。

功能

function pixelArtLine(ctx, x1, y1, x2, y2) {
    x1 = Math.round(x1);
    y1 = Math.round(y1);
    x2 = Math.round(x2);
    y2 = Math.round(y2);
    const dx = Math.abs(x2 - x1);
    const sx = x1 < x2 ? 1 : -1;
    const dy = -Math.abs(y2 - y1);
    const sy = y1 < y2 ? 1 : -1;
    var e2, er = dx + dy, end = false;
    ctx.beginPath();
    while (!end) {
        ctx.rect(x1, y1, 1, 1);
        if (x1 === x2 && y1 === y2) {
            end = true;
        } else {
            e2 = 2 * er;
            if (e2 > dy) {
                er += dy;
                x1 += sx;
            }
            if (e2 < dx) {
                er += dx;
                y1 += sy;
            }
        }
    }
    ctx.fill();        
};

我该如何改进这个功能？

Answer 1

Fast Bresenham 的 HTML5 画布系列。

解决方案

如果减少路径调用的数量，可以改善渲染效果。例如，更少的呼叫ctx.rect(x,y,1,1);

1 像素长或 20 像素长的单个矩形之间的渲染时间差异非常小，我无法测量它。因此，减少调用次数将会带来显着的改进。

查看从 1,1 到 15,5 的一行，需要 10 次调用ctx.rect

//     shows 10 pixels render of line 1,1 to 15,5
// ###
//    ###
//       ###
//          ###
//             ###

但使用 3 像素宽的矩形只需 5 次调用即可渲染它。

标准算法需要最大坐标长度加上一次路径调用。例如 1,1 到 15,5 是Math.max(15-1, 5-1) + 1 === 15，但可以在最小长度 + 1 例如中完成Math.min(15-1, 5-1) + 1 === 5

新算法

使用与 Bresenham 线相同的误差方法，并以八分圆为单位，可以根据累积误差值计算到下一个 y 步骤（八分圆 0）或 x 步骤（八分圆 1）的距离。该距离给出了ctx.rect要绘制的长度（以像素为单位）以及添加到下一行的误差中的量。

水平线和垂直线在单个路径调用中呈现。45 度的线需要最多的路径调用，但由于这是一种特殊情况，该函数可以获得 JavaScript 性能优势。

对于随机选择的线，它应该将绘制调用的数量减少到 42%

function BMFastPixelArtLine(ctx, x1, y1, x2, y2) {
    x1 = Math.round(x1);
    y1 = Math.round(y1);
    x2 = Math.round(x2);
    y2 = Math.round(y2);
    const dx = Math.abs(x2 - x1);
    const sx = x1 < x2 ? 1 : -1;
    const dy = Math.abs(y2 - y1);
    const sy = y1 < y2 ? 1 : -1;
    var error, len, rev, count = dx;
    ctx.beginPath();
    if (dx > dy) {
        error = dx / 2;
        rev = x1 > x2 ? 1 : 0;
        if (dy > 1) {
            error = 0;
            count = dy - 1;
            do {
                len = error / dy + 2 | 0;
                ctx.rect(x1 - len * rev, y1, len, 1);
                x1 += len * sx;
                y1 += sy;
                error -= len * dy - dx;
            } while (count--);
        }
        if (error > 0) {ctx.rect(x1, y2, x2 - x1, 1) }
    } else if (dx < dy) {
        error = dy / 2;
        rev = y1 > y2 ? 1 : 0;
        if (dx > 1) {
            error = 0;
            count --;
            do {
                len = error / dx + 2 | 0;
                ctx.rect(x1 ,y1 - len * rev, 1, len);
                y1 += len * sy;
                x1 += sx;
                error -= len * dx - dy;
            } while (count--);
        }
        if (error > 0) { ctx.rect(x2, y1, 1, y2 - y1) }
    } else {
        do {
            ctx.rect(x1, y1, 1, 1);
            x1 += sx;
            y1 += sy;
        } while (count --); 
    }
    ctx.fill();
}

• 缺点：生成的函数有点长，并且与原始函数的像素不完美匹配，错误仍然使像素在线上。

• 优点：对于随机均匀分布的线路，性能平均提高 55%。最坏的情况（接近 45 度的线，（45 度线更快））太小，以至于无法判断。最好的情况（接近或水平或垂直）速度提高 70-80% 以上。还有一个额外的好处，因为该算法更适合渲染像素艺术多边形。