Looking for a fast outlined line rendering algorithm

Question

I'm looking for a fast algorithm to draw an outlined line. For this application, the outline only needs to be 1 pixel wide. It should be possible, whether by default or through an option, to make two lines connect together seemlessly, if they share a common point.

Excuse the ASCII art but this is probably the best way to demonstrate it.

Normal line:

 ##
   ##
     ##
       ##
         ##
           ##

"Outlined" line:

 **
*##**
 **##**
   **##**
     **##**
       **##**
         **##*
           **

I'm working on a dsPIC33FJ128GP802. It's a small microcontroller/digital signal processor, capable of 40 MIPS (million instructions per second.) It is only capable of integer math (add, subtract and multiply: it can do division, but it takes ~19 cycles.) It's being used to process an OSD layer at the same time and only 3-4 MIPS of the processing time is available for calculations, so speed is critical. The pixels occupy three states: black, white and transparent; and the video field is 192x128 pixels. This is for Super OSD, an open source project: http://code.google.com/p/super-osd/

The first solution I thought of was to draw 3x3 rectangles with outlined pixels on the first pass and normal pixels on the second pass, but this could be slow, as for every pixel at least 3 pixels are overwritten and the time spent drawing them is wasted. So I'm looking for a faster way. Each pixel costs around 30 cycles. The target is <50,000 cycles to draw a line of 100 pixels length.

Thanks!

Answer 1

I suggest this (C/pseudocode mix) :

void draw_outline(int x1, int y1, int x2, int y2)
{
    int x, y;
    double slope;

    if (abs(x2-x1) >= abs(y2-y1)) {
        // line closer to horizontal than vertical
        if (x2 < x1) swap_points(1, 2);
        // now x1 <= x2
        slope = 1.0*(y2-y1)/(x2-x1);
        draw_pixel(x1-1, y1, '*');
        for (x = x1; x <= x2; x++) {
            y = y1 + round(slope*(x-x1));
            draw_pixel(x, y-1, '*');
            draw_pixel(x, y+1, '*');
            // here draw_line() does draw_pixel(x, y, '#');
        }
        draw_pixel(x2+1, y2, '*');
    }
    else {
        // same as above, but swap x and y
    }
}

Edit: If you want to have successive lines connect seamlessly, I think you really have to draw all the outlines in the first pass, and then the lines. I edited the code above to draw only the outlines. The draw_line() function would be exactly the same but with one single draw_pixel(x, y, '#'); instead of four draw_pixel(..., ..., '*');. And then you just:

void draw_polyline(point p[], int n)
{
    int i;

    for (i = 0; i < n-1; i++)
        draw_outline(p[i].x, p[i].y, p[i+1].x, p[i+1].y);
    for (i = 0; i < n-1; i++)
        draw_line(p[i].x, p[i].y, p[i+1].x, p[i+1].y);
}