I'm looking for a fast algorithm that draws lines with a certain thickness. The lines don't have to be antialiased, speed is priority. Something fairly simple like this would suffice:
The use case is a Javascript game where worms leave trails. (HTML5 Canvas obviously draws lines, but getImageData() is very slow and so is collision detection)
I couldn't find anything that does this for the last 2.5 hours. And yes, I'm aware that there are almost identical questions on SO, quite a lot of them in fact, but not a single one has a working solution. The only solution I currently have is to draw circles along a Bresenham line, which is not very efficient.
Some code (pseudo-code, JS or at least a link to an article) would be great.
I'm looking for a fast algorithm that draws lines with a certain thickness. The lines don't have to be antialiased, speed is priority. Something fairly simple like this would suffice:
The use case is a Javascript game where worms leave trails. (HTML5 Canvas obviously draws lines, but getImageData() is very slow and so is collision detection)
I couldn't find anything that does this for the last 2.5 hours. And yes, I'm aware that there are almost identical questions on SO, quite a lot of them in fact, but not a single one has a working solution. The only solution I currently have is to draw circles along a Bresenham line, which is not very efficient.
Some code (pseudo-code, JS or at least a link to an article) would be great.
Share Improve this question edited Nov 16, 2013 at 18:39 blade asked Nov 16, 2013 at 18:30 bladeblade 12.9k7 gold badges41 silver badges40 bronze badges 8- 2 Seems a bit rich to insist on being given code when you haven't done so yourself... – YXD Commented Nov 16, 2013 at 18:33
- 2 Line drawing is usually done using the Bresenham algorithm: en.wikipedia/wiki/Bresenham%27s_line_algorithm. It should be rather straight forward to draw thick lines with this approach, too. – PMF Commented Nov 16, 2013 at 18:38
-
I think Canvas is the way to go. You can use DOM-elements and rotate them, but this will be way inferior especially performance-wise. Collision detection can be done with Canvas and JS-objects quite performant. What do you want to use
getImageData()for? – Max Commented Nov 16, 2013 at 18:41 - 1 I didn't include any code as I'm only using Bresenham's algorithm - found here stackoverflow./a/4672319/388994 The problem is - it doesn't draw thick lines. At least I can't find any way to do so properly. – blade Commented Nov 16, 2013 at 18:41
- 1 @81403 just draw bigger squares (rectangles) instead of individual pixels. – Pointy Commented Nov 16, 2013 at 18:43
1 Answer
Reset to default 15http://members.chello.at/~easyfilter/bresenham.html
check at the bottom. It is an anti-aliased line, but should be easy enough to mod to non-anti-aliasing.
edit: I've added a simple function to do this that uses putImageData to display the "pixel" vs fillRect which should speed up the function on longer lines.
<html>
<head>
<title>An (Optimal?) Bresenham Line Function in Javascript and HTML Canvas</title>
<script>
// using imagedata for pixel, because fillRect can be slow on larger lines
// imagedata will be slower on shorter lines
function drawLine(ctx, x0, y0, x1, y1, color_r, color_g, color_b, opacity) {
// Calculate differences and direction to step in each axis
const dx = Math.abs(x1 - x0);
const dy = Math.abs(y1 - y0);
const sx = x0 < x1 ? 1 : -1;
const sy = y0 < y1 ? 1 : -1;
// Initialize error term and starting point
let err = dx - dy;
let x = x0;
let y = y0;
// Create a new image data object to hold the pixels for the line
const imageData = ctx.createImageData(1, 1);
const data = imageData.data;
data[0] = color_r; // R
data[1] = color_g; // G
data[2] = color_b; // B
data[3] = opacity; // A (opacity)
// Loop over line until endpoint is reached
while (x !== x1 || y !== y1) {
// Set pixel color in image data
ctx.putImageData(imageData, x, y);
// Calculate error term and update current point
const e2 = err * 2;
if (e2 > -dy) {
err -= dy;
x += sx;
}
if (e2 < dx) {
err += dx;
y += sy;
}
}
// Set pixel color in image data for endpoint
ctx.putImageData(imageData, x1, y1);
}
</script>
</head>
<body>
<canvas id="canvas" width="200" height="200"></canvas>
<script>
// sample use our line function
const canvas = document.getElementById('canvas');
const ctx = canvas.getContext('2d');
drawLine(ctx, 0, 0, 200, 200, 255, 0, 0, 255);
drawLine(ctx, 0, 200, 200, 0, 0, 255, 0, 255);
drawLine(ctx, 0, 100, 200, 100, 0, 0, 255, 255);
drawLine(ctx, 100, 0, 100, 200, 255, 255, 0, 255);
</script>
</body>
</html>