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

问题描述

我正在使用 Bresenham的线算法可实时渲染像素画线。它每次都会渲染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();        
};

如何改进此功能？

推荐答案

Bresenham的HTML5快速画布行。

解决方案

如果减少路径调用的数量，则可以改善渲染。例如，更少调用 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阶（八分圆0）或x阶跃（八分圆1）的距离可以是根据累积误差值计算得出。该距离给出了 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度的线（在45deg的线上速度更快））太小，以至于无法调用。最佳情况（接近或水平或垂直）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屋！