To draw THICK lines using Bresenham's Algorithm

[sunkingac]

Hi...

I am using Bresenham Algorithm for drawing lines and polygons to fill the frame buffer pixel by pixel.

I draw the Lines or Polygons of single pixel thickness.
But i have to draw Lines or Polygons with stroke-thickness of 2 to 10 pixels.

Please help in developing the thick lines using Bresenham's Algorithm


Thanks,
Arun AC

++++++++++++++++++++++++++++++++++++++++++++++++++++

I'm not smart, but I like to observe. Millions saw the apple fall,
but Newton was the one who asked why.

-- William Hazlitt
++++++++++++++++++++++++++++++++++++++++++++++++++++

[Andrea_Rossini]

I don't have any tip for the code but I can give an idea:
drawing a single pixel thick line is like drawing the pixel from here to there.

So I can suppose that drawing a thick line is like drawing a "thick pixel" from here to there.

A "thick pixel" is nothing more than a circle of center x with x being the real pixel, so the beginning pixel will be a filled circle.

Then for every pixel that Bresenham got to draw you will draw a circle for every pixel.

OK, this is slow and repetitive so I got another idea: instead of drawing circles you could just draw the first one, then draw only half circles (not the area just the external points) according to the direction of the line.

Hope I been clear

[MikeAThon]

It seems to me that you can run Bresenham's algorithm multiple times, one time for each pixel's width of your line. At each time you run the algorithm, you offset the start and end positions by one.

Mike

[Andrea_Rossini]

It seems to me that you can run Bresenham's algorithm multiple times, one time for each pixel's width of your line. At each time you run the algorithm, you offset the start and end positions by one.

Mike

good idea
with your method the start pos offset must be horizontal if deltaY > deltaX and being vertical when deltaY < deltaX ?

it would be cool to draw an half circle at the beginnig and one at the end, to make a nice pencil effect. I love halfcircles

[sunkingac]

thanks...
i will try it...


Regards,
Arun AC

[macklin01]

good idea
with your method the start pos offset must be horizontal if deltaY > deltaX and being vertical when deltaY < deltaX ?

it would be cool to draw an half circle at the beginnig and one at the end, to make a nice pencil effect. I love halfcircles

One thing you might consider doing, assuming the endpoints are (x1,y1) and (x2,y2), and thickness 2*r:

1) Use the line direction to get the perpendicular direction. Call it Vperp = (vx,vy). Assume (vx,vy) is normalized.

2) Determine the half circle of radius r at point (x1,y1). You want to start tracking at (x1,y1) + r*(vx,vy) and end at (x1,y1) - r*(vx,vy).

3) Depending upon the direction of the line, calculate each pixel that's approximately on that circle. These are the new endpoints for your parallel Bresenham lines.

On a slightly alternative route, you might consider choosing the perpendicular direction (vx,vy) as above, and using Bresenham to first draw a line between (x1,y1) - r*(vx,vy) and (x1,y1) + r*(vx,vy). If you keep track of the pixel coordinates as you draw the short line, you'll have a whole series of new left endpoints for parallel Bresenham. Do the same thing along the right boundary. Since the two end lines are parallel, you should have an identical number of left and right endpoints. Now, do Bresenham between each of these pairs of endpoints. The result should be a series of parallel Bresenham lines in the original direction, going up to r above and r below. (i.e., with total thickness r.)

Lastly, you might consider drawing all these lines via Bresenham, and then using an anti-aliased line on the boundaries to smooth the thick line.

-- Paul

[macklin01]

Hmm, I was thinking about it more.

It would probably be best to only use Bresenham for the four lines that form the boundary of the "thick" line. The interior should be filled with a fast fill algorithm.

Triangle algorithms come to mind for me here. You can draw a vertical (or horizontal) line from the top (left or right) vertex to turn it into two easier subtriangles. For each subtriangle, you go from left to right (bottom to top) and color all pixels between the bottom line and the top line. In this situation, Bresenham becomes a fast algorithm for determining the top and the bottom of each "scan line".

I'd take a good look at rasterization algorithms, because this is nothing other than filling a rotated rectangle. In fact, if you browse a CG text, you'll see that the method to fill a polygon is to come up with pairs of endpoints (from edges and other subdivisions of the polygon) and color all pixels between them from one side to the other. -- Paul