用于 HTML 画布的更快 Bresenham 线 [英] Faster Bresenham line for HTML canvas

问题描述

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

I am using Bresenham's line algorithm to render pixel art lines in real time. It renders 1 pixel at a time ctx.rect(x,y,1,1) which is a slow operation. I can not use the pixel buffer, which would greatly reduce the render overhead, as I am using composite operations, alpha, and filters (some of which taint the canvas).

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();        
};

如何改进这个功能?

推荐答案

Fast Bresenham's line for HTML5 canvas.

解决办法

如果我减少路径调用的次数，可以改进渲染.例如减少对 ctx.rect(x,y,1,1);

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

The difference in render time between a single rectangle 1 pixel long or 20 pixels is so small I can not measure it. So reducing the number of calls will give a significant improvement.

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

Looking at a line from 1,1 to 15,5 it requires 10 calls to ctx.rect

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

但它可以使用 3 像素宽的矩形仅通过 5 次调用进行渲染.

But it could be rendered with only 5 calls using 3 pixel wide rectangles.

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

The standard algorithm requires the max coordinate length plus one path calls. Eg 1,1 to 15,5 is Math.max(15-1, 5-1) + 1 === 15 but it can be done in the min length + 1 Eg Math.min(15-1, 5-1) + 1 === 5

使用与 Bresenham 线相同的误差方法，并在八分圆中工作，可以根据累积误差值计算到下一个 y 步长(八分之一)或 x 步长(八分之一)的距离.这个距离给出了要绘制的 ctx.rect 长度(以像素为单位)以及添加到下一行的误差中的数量.

Using the same error method as Bresenham's line, and working in octants, the distance to the next y step (octant 0) or x step (octant 1) can be computed from the accumulating error value. This distance gives the ctx.rect length in pixels to draw and the amount to add to the error for the next line.

水平线和垂直线在单个路径调用中呈现.45deg 处的行需要最多的路径调用，但由于它是一种特殊情况，该函数获得了 javascript 性能优势.

Horizontal and vertical lines are rendered in a single path call. Lines at 45deg require the most path calls but as it is a special case the function gets a javascript performance benefit.

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

For a random selection of lines it should reduce the number of draw calls to 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();
}

• 缺点:生成的函数有点长，并且不是与原始像素完美匹配，错误仍然使像素保持在线.

  • Cons : The resulting function is somewhat longer and is not a pixel perfect match to the original, the error still keeps the pixels over the line.

    优点:对于随机均匀分布的线路，性能平均提高 55%.最坏的情况(接近 45 度的线，(在 45 度线上更快))太小了，太接近了.最佳情况(接近或水平或垂直)快 70-80%+.还有一个额外的好处，因为该算法更适合渲染像素艺术多边形.

    Pros : There an average of 55% performance increase for randomly evenly distributed lines. Worst case (lines near 45 degree, (on 45deg lines are faster) ) is so small its too close to call. Best case (near or on horizontal or vertical) 70-80%+ faster. There is also an extra benefit as this algorithm is much better suited for when rendering pixel art polygons.

    这篇关于用于 HTML 画布的更快 Bresenham 线的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！