javascript - Faster Bresenham line for HTML canvas

Question

Ask a Question

Welcome To Ask or Share your Answers For Others

javascript - Faster Bresenham line for HTML canvas

asked Oct 24, 2021 in Technique[技术] by 深蓝 (71.8m points)

Slow render

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

The function

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

How can I improve this function?

See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙；凝视深渊过久,深渊将回以凝视…

254 views

1 Answer

深蓝 · Answer 1 · 2021-10-23T18:21:42+0000

I can suggest two ways to tackle your problem. The first is to use ctx.createImageData(w,h) to create an imageData object that contains a bitmap array (ImageData.data, it's an Uint8ClampedArray), Once you are done manipulating the data it can be put on the canvas with ctx.putImageData(ImageData,0,0).

Or you could use a solution powered by WebGL to draw your lines for you. (If you want to disable smoothing to get pixelated lines the gl context just needs to be created with anti aliasing disabled).

Using WebGL is preferrable as any solution written in JS at the moment can realistically only operate on one pixel at a time (Web Workers with a shared array buffer could provide you with concurrent multithreaded JS but it had been disabled in all browsers at the beginning of this year).

below is a module powered by WebGL that can be used to quickly draw lines of differing thicknesses and colours.

(To test speed the snippet below is drawing 10000 lines).

<!doctype html>
<html>
<head>
<meta charset="utf-8">
<style>
body {
background-color: black;
}

canvas {
display: block;
margin-top: 30px;
margin-left: auto;
margin-right: auto;
border: solid 1px white;
border-radius: 10px;
width: 180px;
height: 160px;
}
</style>
</head>

<body>
<canvas id="canvas"></canvas>
<script type="application/javascript">

var glLine = function() {

"use strict";

var width = 1;
var height = 1;
var lineWidth = 1;
var tmpBuffer = new Float32Array(12);
var canvas = document.createElement("canvas");
var gl = canvas.getContext("webgl",{antialias: false,preserveDrawingBuffer: true});
gl.clearColor(0.0,0.0,0.0,0.0);

var buffer = function() {
var b = gl.createBuffer();

gl.bindBuffer(gl.ARRAY_BUFFER,b);
gl.bufferData(gl.ARRAY_BUFFER,tmpBuffer,gl.DYNAMIC_DRAW);
}();

var uInvResolution = null;
var uColour = null;

var program = function() {
var vs = gl.createShader(gl.VERTEX_SHADER);
var fs = gl.createShader(gl.FRAGMENT_SHADER);

gl.shaderSource(vs,`
precision lowp float;

attribute vec2 aPosition;

uniform vec2 uInvResolution;

void main() {
vec2 vPosition = vec2(
aPosition.x * uInvResolution.x * 2.0 - 1.0,
-(aPosition.y * uInvResolution.y * 2.0 - 1.0)
);

gl_Position = vec4(vPosition,0.0,1.0);
}
`);

gl.shaderSource(fs,`
precision lowp float;

uniform vec4 uColour;

void main() {
gl_FragColor = uColour;
}
`);

gl.compileShader(vs);
gl.compileShader(fs);

var p = gl.createProgram();

gl.attachShader(p,vs);
gl.attachShader(p,fs);
gl.linkProgram(p);
gl.deleteShader(vs);
gl.deleteShader(fs);
gl.useProgram(p);

uInvResolution = gl.getUniformLocation(p,"uInvResolution");
uColour = gl.getUniformLocation(p,"uColour");

return p;
}();

gl.vertexAttribPointer(0,2,gl.FLOAT,gl.FALSE,8,0);
gl.enableVertexAttribArray(0);

addEventListener("unload",function() {
gl.deleteBuffer(buffer);
gl.deleteProgram(program);
gl = null;
});

return {
clear: function() {
gl.clear(gl.COLOR_BUFFER_BIT);
},

draw: function(x1,y1,x2,y2) {
var x = x2 - x1;
var y = y2 - y1;
var invL = 1.0 / Math.sqrt(x * x + y * y);

x = x * invL;
y = y * invL;

var hLineWidth = lineWidth * 0.5;
var bl_x = x1 - y * hLineWidth;
var bl_y = y1 + x * hLineWidth;
var br_x = x1 + y * hLineWidth;
var br_y = y1 - x * hLineWidth;
var tl_x = x2 - y * hLineWidth;
var tl_y = y2 + x * hLineWidth;
var tr_x = x2 + y * hLineWidth;
var tr_y = y2 - x * hLineWidth;

tmpBuffer[0] = tr_x;
tmpBuffer[1] = tr_y;
tmpBuffer[2] = bl_x;
tmpBuffer[3] = bl_y;
tmpBuffer[4] = br_x;
tmpBuffer[5] = br_y;
tmpBuffer[6] = tr_x;
tmpBuffer[7] = tr_y;
tmpBuffer[8] = tl_x;
tmpBuffer[9] = tl_y;
tmpBuffer[10] = bl_x;
tmpBuffer[11] = bl_y;

gl.bufferSubData(gl.ARRAY_BUFFER,0,tmpBuffer);
gl.drawArrays(gl.TRIANGLES,0,6);
},

setColour: function(r,g,b,a) {
gl.uniform4f(
uColour,
r * 0.00392156862745098,
g * 0.00392156862745098,
b * 0.00392156862745098,
a * 0.00392156862745098
);
},

setLineWidth: function(width) {
lineWidth = width;
},

setSize: function(_width,_height) {
width = _width;
height = _height;

canvas.width = width;
canvas.height = height;

gl.uniform2f(uInvResolution,1.0 / width,1.0 / height);
gl.viewport(0,0,width,height);
gl.clear(gl.COLOR_BUFFER_BIT);
},

getImage: function() {
return canvas;
}
};

}();

void function() {

"use strict";

var canvasWidth = 180;
var canvasHeight = 160;
var canvas = null;
var ctx = null;

onload = function() {
canvas = document.getElementById("canvas");
canvas.width = canvasWidth;
canvas.height = canvasHeight;
ctx = canvas.getContext("2d");

glLine.setSize(canvasWidth,canvasHeight);

ctx.fillStyle = "gray";
ctx.fillRect(0,0,canvasWidth,canvasHeight);

for (var i = 0, l = 10000; i < l; ++i) {
glLine.setColour(
(Math.random() * 255) | 0,
(Math.random() * 255) | 0,
(Math.random() * 255) | 0,
255
);

glLine.setLineWidth(
3 + (Math.random() * 5) | 0
);

glLine.draw(
Math.random() * canvasWidth,
Math.random() * canvasHeight,
Math.random() * canvasWidth,
Math.random() * canvasHeight
);
}

ctx.drawImage(glLine.getImage(),0,0);
}

}();

</script>
</body>
</html>

Categories

javascript - Faster Bresenham line for HTML canvas

Slow render

The function

Please log in or register to add a comment.

Please log in or register to answer this question.

1 Answer

Please log in or register to add a comment.

Just Browsing Browsing

Most popular tags