Faster Bresenham line for HTML canvas

Question

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?

Answer 1

Since 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>

---

Answer 2

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>