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 posite 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?
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 posite 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?
Share Improve this question edited Jun 20, 2020 at 9:12 CommunityBot 11 silver badge asked May 31, 2018 at 13:48 Blindman67Blindman67 54.2k11 gold badges86 silver badges150 bronze badges3 Answers
Reset to default 2Since you are doing pixel art, why not make it at a pixel level: manipulating an ImageData directly.
You stated that your canvas may well be tainted, and that it will have filters and gCO set up. None of this really matters.
Use a second offscreen canvas, only to generate your pixel-art renderings.
Set its size to the one of your rendered pixels grid (i.e originalCanvasSize / pixelSize).
Perform your Maths on the offscreen's ImageData directly.
Put the ImageDaat on your offscreen-canvas
Use gCO to set your pixel-art colors.
Draw back your offscreen canvas on the rendered one using drawImage with no image smoothing (imageSmoothingEnbaled = false).
The filters and gCO you wanted to be applied on your Path drawing will also be applied on this final drawImage(offscreenCanvas)
I am sure you will be able to rewrite it in a cleaner way, but here is a rough proof of concept:
class PixelArtDrawer {
constructor(ctx, options = {}) {
if (!(ctx instanceof CanvasRenderingContext2D)) {
throw new TypeError('Invalid Argument 1, not a canvas 2d context');
}
this.cursor = {
x: 0,
y: 0
};
this.strokeStyle = '#000';
this.renderer = ctx;
this.ctx = document.createElement('canvas').getContext('2d');
this.setPixelSize((options && options.pixelSize) || 10);
}
setPixelSize(pixelSize) {
this.pixelSize = pixelSize;
const ctx = this.ctx;
const canvas = ctx.canvas;
const renderer = this.renderer.canvas;
canvas.width = (renderer.width / pixelSize) | 0;
canvas.height = (renderer.height / pixelSize) | 0;
ctx.globalCompositeOperation = 'source-in';
this.image = ctx.createImageData(canvas.width, canvas.height);
this.data = new Uint32Array(this.image.data.buffer);
}
beginPath() {
this.data.fill(0);
this.cursor.x = this.cursor.y = null;
}
stroke() {
const renderer = this.renderer
const currentSmoothing = renderer.imageSmoothingEnbaled;
const ctx = this.ctx;
ctx.putImageData(this.image, 0, 0);
// put the color
ctx.fillStyle = this.strokeStyle;
ctx.fillRect(0, 0, this.image.width, this.image.height);
renderer.imageSmoothingEnabled = false;
renderer.drawImage(ctx.canvas, 0, 0, renderer.canvas.width, renderer.canvas.height);
renderer.imageSmoothingEnabled = currentSmoothing;
}
moveTo(x, y) {
this.cursor.x = (x / this.pixelSize) | 0;
this.cursor.y = (y / this.pixelSize) | 0;
}
lineTo(x, y) {
if (this.cursor.x === null) {
this.moveTo(x, y);
return;
}
const data = this.data;
const width = this.image.width;
const height = this.image.height;
var x1 = this.cursor.x;
var y1 = this.cursor.y;
const x2 = (x / this.pixelSize) | 0;
const y2 = (y / this.pixelSize) | 0;
// from here it is OP's code
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;
var index;
while (!end) {
// this check would probably be better done out of the loop
if (x1 >= 0 && x1 <= width && y1 >= 0 && y1 <= height) {
// here we need to convert x, y coords to array index
index = ((y1 * width) + x1) | 0;
data[index] = 0xff000000;
}
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;
}
}
}
this.cursor.x = x2;
this.cursor.y = y2;
}
}
const ctx = renderer.getContext('2d');
const pixelArt = new PixelArtDrawer(ctx);
const points = [{
x: 0,
y: 0
}, {
x: 0,
y: 0
}];
draw();
renderer.onmousemove = function(e) {
const rect = this.getBoundingClientRect();
const lastPoint = points[points.length - 1];
lastPoint.x = e.clientX - rect.left;
lastPoint.y = e.clientY - rect.top;
};
renderer.onclick = e => {
const lastPoint = points[points.length - 1];
points.push({
x: lastPoint.x,
y: lastPoint.y
});
};
function draw() {
ctx.clearRect(0, 0, renderer.width, renderer.height);
pixelArt.beginPath();
points.forEach(drawLine);
pixelArt.stroke();
requestAnimationFrame(draw);
}
function drawLine(pt) {
pixelArt.lineTo(pt.x, pt.y);
}
color_picker.onchange = function() {
pixelArt.strokeStyle = this.value;
}<input type="color" id="color_picker"><br>
<canvas id="renderer" width="500" height="500"></canvas>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.pileShader(vs);
gl.pileShader(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>Fast Bresenham's line for HTML5 canvas.
The solution
The rendering can be improved if I reduce the number of path calls. eg less calls to ctx.rect(x,y,1,1);
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.
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
// ###
// ###
// ###
// ###
// ###
But it could be rendered with only 5 calls using 3 pixel wide rectangles.
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
The new algorithm
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 puted 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.
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.
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.
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.