2

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 seamlessly, 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.

Kevin Brown-Silva
  • 40,873
  • 40
  • 203
  • 237
Thomas O
  • 6,026
  • 12
  • 42
  • 60
  • 3
    I don't think that [how do I create a line of arbitrary thickness using Bresenham?](http://stackoverflow.com/questions/1222713/how-do-i-create-a-line-of-arbitrary-thickness-using-bresenham) is a duplicate as such, but it is probably relevant. – dmckee --- ex-moderator kitten Oct 11 '10 at 17:30
  • +1 & Thanks for the link. This involves outlined lines, so I'm looking for an efficient way of drawing a line with a border. Drawing a thick line then a thin line would be essentially identical to what I gave as an option. – Thomas O Oct 11 '10 at 17:33
  • Yes. The line is like ordinary Bresenham and is 1 pixel wide. I want to draw a 1 pixel outline on this line, so the line will be in total 3 pixels wide. – Thomas O Oct 12 '10 at 12:00
  • 4
    This is *clearly* not asking for an off-site resource, nor have off-site resources been provided. Dear close-voters, please learn to read. With love, – Shog9 Feb 05 '15 at 00:35

2 Answers2

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);
}
Edgar Bonet
  • 3,416
  • 15
  • 18
  • That's basically it - this example doesn't use the fast Bresenham algorithm, but the idea can be adapted. In words rather than pseudocode: each 'line' pixel needs an 'outline' pixel up,down,left&right. So, for every horizontal segment, put an outline pixel to the left, go along the segment drawing the line and outlining above+below, then put an outline pixel to the right. Similarly for the next horizontal segment. But you can optimise, since the top border for this horizontal segment overlaps the right border of the last one, so you only need to do the L/R pixels for the first/last segments. – psmears Oct 12 '10 at 21:47
  • @psmears: You really want to draw the L/R borders for all segments, because you may have a left-to-right segment followed by a right-to-left segment, for example when drawing something like the '>' symbol. – Edgar Bonet Oct 13 '10 at 12:23
  • 1
    If the processor cannot do floating point arithmetic in hardware, I would instead compute the slope using fixed point. Then, assuming you can spare 16 bits for the fractional part, the computation of y would become: `hi_res_y += slope; y = hi_res_y >> 16;`. That's just one add and one bit shift. I would initialize `hi_res_y = (y << 16) + 0x8000` in order to get correct runding. – Edgar Bonet Oct 13 '10 at 12:25
  • Thanks. :) I will investigate this further. – Thomas O Oct 13 '10 at 14:59
  • Also, thanks for the polyline function - that would be very useful. I was thinking I would have to correct it manually by placing pixels. – Thomas O Oct 13 '10 at 14:59
  • @Edgar: the processor has no FPU so thanks for your suggestion. If I can get away without using software FPU it will be much faster. – Thomas O Oct 13 '10 at 15:00
  • @Edgar Bonet: The question asked about a straight line. Yes, if you are drawing more than one straight line then you'll need to do caps at the end of each straight line, but within each straight line you can omit the ends of the horizontal segments that make up that line (as indeed your solution already does :-) BTW I wouldn't use fixed point or floating point arithmetic, which are approximate & can have rounding errors, when the Bresenham algorithm uses just integer arithmetic and is exact (to within the resolution of the display)--see http://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm – psmears Oct 13 '10 at 16:01
  • @psmears: Sorry, I confused "horizontal segments" and "straight lines". The question asked about a straight line, but also about seamlessly connecting two such lines. I interpreted this last requirement as polylines. – Edgar Bonet Oct 13 '10 at 16:56
  • @psmears again: The Wikipedia link you give for the Bresenham's algorithm is not integer arithmetic: `error` and `deltaerr` are defined as `real`. Rounding errors should not be an issue with fixed point if you have enough bits for the fractional part. If you don't have enough bits to hold both the integer and fractional parts of y in the same variable, then you have to split them into two variables and manually handle the overflow of the fractional part into the integer part. That's basically what the Bresenham's algorithm does. – Edgar Bonet Oct 13 '10 at 16:59
  • @Edgar Bonet: (1) Sure, it's very confusing when we start making lines out of lines, adding polylines etc - we need more words :) (2) The first parts use `real` for clarity, but if you read the whole article (see the section entitled "Optimization") it shows how it can be transformed to use integer arithmetic with no rounding. It's not really the same as fixed point, because the "fixed" of "fixed point" implies a constant denominator; here the denominator's variable, and chosen to make the calculations exact - that's why the algorithm is so clever :) - but beyond that yes, it's very similar :) – psmears Oct 13 '10 at 20:27
  • This will give a low quality result because the border pixels are always y+-1 from the center regardless of the line's angle. So the line will be sqrt(2)~=1.4 times too narrow at 45 degrees. Better will be to choose a "brush" pattern that's a short line segment _perpendicular_ to the one you're drawing with the end two pixels having the border color. Draw two bordered bresenham circles for the end caps, then paint with such a brush in 1 pass. Ought to produce a nice result. If you want to see the integer math for this, post another comment. – Gene Jun 26 '15 at 00:12
0

My approach would be to use the Bresenham to draw multiple lines. Looking at your ASCII art, you'll note that the outline lines are just the same as the Bresenham line, just shifted 1 pixel up and down -- plus a single pixel to the left of the first point and to the right of the last.

For a generic version, you'll need to determine whether your line is flat or steep -- i.e., whether abs(y1 - y0) <= abs(x1 - x0). For steep lines, the outlines are shifted by 1 pixel to the left and right, and the closing pixels are above the starting and below the ending point.

It could be worth optimizing this by drawing the line and two outline pixels in one go for each line pixel. However, if you need seamless outlines, the simplest solution would be to first draw all outlines, then the lines themselves -- which wouldn't work with the "three-pixel-Bresenham" optimization.

Franz D.
  • 1,061
  • 10
  • 23