10

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.

blade
  • 12,057
  • 7
  • 37
  • 38
  • 2
    Seems a bit rich to insist on being given code when you haven't done so yourself... – YXD Nov 16 '13 at 18:33
  • 2
    Line drawing is usually done using the Bresenham algorithm: http://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm. It should be rather straight forward to draw thick lines with this approach, too. – PMF Nov 16 '13 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 Nov 16 '13 at 18:41
  • 1
    I didn't include any code as I'm only using Bresenham's algorithm - found here http://stackoverflow.com/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 Nov 16 '13 at 18:41
  • 1
    @81403 just draw bigger squares (rectangles) instead of individual pixels. – Pointy Nov 16 '13 at 18:43
  • @Max getting just a single pixel from a ~HD canvas with getImageData() is very slow - see http://jsperf.com/getimagedata-complexity/2 . This would be the easiest way, but unfortunately is too slow. – blade Nov 16 '13 at 18:44
  • @81403 I'm aware of that. I just don't exactly see the reason you need it in the first place. How is the game built so far? – Max Nov 16 '13 at 18:47
  • @Max The game just draws rounded line for each worm into canvas that persists throughout one match. That works great until you're dealing with collisions - get one pixel ahead of each worm and 1 on both sides. With 8 players being maximum, this makes 24 reads.That's why I wanted to make an invisible array where I would manually draw the lines and get collisions from there. – blade Nov 16 '13 at 18:52

1 Answers1

15

http://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>
PlugTrade
  • 837
  • 11
  • 19