Search code examples
javascriptalgorithmgraphicsdrawingline

Algorithm for drawing line with thickness / width

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.

Solution

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