how do I create a line of arbitrary thickness using Bresenham?

Question

I am currently using Bresenham's algorithm to draw lines but they are (of course) one pixel in thickness. My question is what is the most efficient way to draw lines of arbitrary thickness?

The language I am using is C.

Lyophilize

Retagged "language-agnostic" since the implementation language is not really relevant. – Mcallister

here is a related SO question: #102218 – Terisateriyaki

@banister: you got some demo to share with us? – Magavern

Answer 1

I think the best way is to draw a rectangle rather than a line since a line with width is a two dimensional object. Tring to draw a set of parallel lines to avoid overdraw (to reduce write bandwidth) and underdraw (missing pixels) would be quite complex. It's not too hard to calculate the corner points of the rectangle from the start and end point and the width.

So, following a comment below, the process to do this would be:-

1. Create a rectangle the same length as the required line and width equal to the desired width, so (0,0) to (width,length)
2. Rotate and translate the rectangles corner coordinates to the desired position using a 2D transformation
3. Rasterise the rotated rectangle, either using a hardware accelerated renderer (an OpenGL quad for example*) or use a software rasteriser. It can be rendered using a quad rasteriser or as a pair of triangles (top left and bottom right for example).

Note *: If you're using OpenGL you can also do Step 2 at the same time. Of course, using OpenGL does mean understanding OpenGL (big and complex) and this application may make that a tricky thing to implement at such a late stage in development.

Alburg

I didn't got your solution. Can you elaborate please. – Magavern

That would only work if the line is perfectly vertical or horizontal. – Moravia

@Jonathan: A line of arbitary thickness can be thought of as a rotated rectangle so isn't limited to just vertical or horizontal lines. Of course, drawing rectangles at arbitary angles will result in the jaggies unless you add some anti-aliasing to smooth things off a bit. Doing anti-aliasing is a whole separate question. – Alburg

@Alburg My mistake. I was assuming that a rotated rectangle would require actually rotating a rectangle, which would be difficult for someone trying to implement Bresenham's algorithm. However, you can draw a rotated rectangle using two triangles, so I withdraw my criticism. If you update your answer to describe how to draw a rotated rectangle, I will upvote. – Moravia

Answer 2

Take another Bresenham loop and use it to modify the start and end position of original line in rectangular direction. Problem is to efficently find the right starting point and not to draw any pixel twice (or skip a pixel) while drawing next line.

Working and tested C code is available from Github C code .

Here a test page including a few sample lines created by this code. The black pixels are the starting points for the algorithm.

Sideboard

If I could, I would upvote this answer more, because it's the only one that directs the reader to a clean, working implementation in C - just as the OP asked for. – Andromada

That is so clever! – Astrakhan

Answer 3

Here is a paper and Delphi implementation of a modified version of Bresenham's algorithm for drawing thickened lines.

You may also want to take a look at Anti-Grain Geometry, a library for high-quality and high-performance software rendering of 2D graphics. Take a look at the demo page to get an idea of what it can do.

---

That paper on Murphy's Modified Bresenham Line Drawing looks useful, but link-only answers can have limited value here, so here's a little summary of it.

A line with thickness is a rectangle. The algorithm uses an outer Bresenham loop to step along one of the rectangle's edges without actually drawing it. An Bresenham loop draws a perpendicular line at each step of the outer loop. By passing not only the (x, y) coordinate but also the error term from the outer loop to the inner loop, it ensures that all of the perpendicular lines are "in phase" ensuring the rectangle is filled without gaps. Every pixel set is set exactly once.

Mcallister

Anti-Grain Geometry seems to be a dead link, but I think it can still be found on SourceForge. – Currey

Answer 4

For best accuracy, and also good performance for thicker lines especially, you can draw the line as a polygon. Some pseudo code:

draw_line(x1,y1,x2,y2,thickness)
  Point p[4];
  angle = atan2(y2-y1,x2-x1);
  p[0].x = x1 + thickness*cos(angle+PI/2);
  p[0].y = y1 + thickness*sin(angle+PI/2);
  p[1].x = x1 + thickness*cos(angle-PI/2);
  p[1].y = y1 + thickness*sin(angle-PI/2);
  p[2].x = x2 + thickness*cos(angle-PI/2);
  p[2].y = y2 + thickness*sin(angle-PI/2);
  p[3].x = x2 + thickness*cos(angle+PI/2);
  p[3].y = y2 + thickness*sin(angle+PI/2);
  draw_polygon(p,4)

And optionally a circle could be drawn at each end point.

Knox

In a way this is reducing the problem to a more complex one. In order to get it to work (in Python), I had to adjust things, though: a) exchange the sin and the cos. b) instead of multiplying by thickness, multiply by thickness/2.0. – Hermanhermann

@Hermanhermann I think it's the angle that is wrong. This should be atan2(y2-y1, x2-x1). – Trinitrophenol

How would you like to implement draw_polygon (or, in fact, fill_polygon) then? – Fiden

How to implement fill_polygon is quite a broad question. There are various techniques depending on the environment and other requirements. In most cases there are suitable libraries available with functions for basic drawing (hopefully using hardware acceleration). Otherwise a common technique (if the polygon is guaranteed to be completely convex such as in this case) is having two arrays containing the x-coordinates of each side of the polygon and draw vertical lines between them. But you should probably search for questions about drawing filled polygons specifically to get more details. – Knox

"how do I implement this algorithm?" "use this other algorithm" "how do I implement this other algorithm?" "it's complicated" – Koala

@Dev It's more about turning a specific problem into a more generic problem. Drawing a thick line is kind of a complicated problem to begin with. But drawing a polygon is at least a well known problem that is already solved in many situations. And otherwise easier to find a fitting solution to. – Knox

"Drawing a thick line is kind of a complicated problem to begin with" - efficiently? yes. You can draw circles along each point in a Bresenham line (extremely inefficient, draws over each pixel way too many times). You can draw two filled circles and connect them with a filled quad (which is easy-ish, but looks bad depending on how you round the corners), etc. Lots of methods, none of which are perfect. – Koala

@Dev The question was about "the most efficient way to draw lines of arbitrary thickness" so I thought efficiency was implied. But of course you're right, if it doesn't have to be efficient it doesn't have to be very complicated either. – Knox

This worked for me in the case of working around a software opengl implementation on windows that did not fully support a shader properly to implement antialiased thick lines through VTK. – Floris

Answer 5

Some simple routes to use:

1. for any width n where n is odd. for any point p plotted also plot the points above/below it for n/2 (if the line is > 45 degree angle draw side to side instead).
   • not really a proper line of the right thickness, more like an italic pen, but very fast.
2. for start point p(x,y) pick the points t0 and b such that they are centred on p but n pixels apart. for the end point do the same resulting in t1 b1. Draw lines from t0 -> t1, t1->b1, b1 -> t0, b0 -> t1. Fill in the resulting rectangle.
   • The trick here is picking the points such that they appear orthogonal to the path direction.
3. for each point p on the line instead of drawing a point draw a circle.
   • This has the advantage of making the end points 'clean' no matter what the orientation.
   • there should be no need to render any circles in solid except for the first.
   • somewhat slow

Footpath

Answer 6

The easiest way to create a line of almost arbitrary thickness would be to first do a bresenham, then apply as many dilation iterations as you wish. Each dilation pads both sides of your line equally.

EDIT: It is also worth noting that this method has the nice feature of being easily generalizable to 3D, because both Bresenham and dilation are easily generalizable to 3D.

Bresenham → thickness 1:

Dilation mask:

0 1 0
1 1 1
0 1 0

Bresenham + 1 dilation → thickness 2

Bresenham + 2 dilations → thickness 3

etc.

Stoichiometric

This is a nice and simple approach. How would you generate appropriate masks for arbitrary sizes? – Courtund

The thickness depends on the number of dilation iterations. But it’s good that you’re asking. I noticed that just one mask is needed. See the edited answer. – Stoichiometric

Oh I see, you can apply that same mask to itself repeatedly to increase the size, clever! :) (The explanation of dilation on the linked page is a bit difficult to understand) – Courtund

this defeats the purpose of Bresenham, as the complexity is of the entire 2d image, rather than of the 1d line – Batwing

If the performance is suitable for the purpose, I don't see anything wrong with combining bresenham with dilations as a quick solution. – Stoichiometric

Answer 7

http://members.chello.at/~easyfilter/bresenham.html

The example at the bottom of this link is javascript, but should be easy enough to adapt to C. It's a fairly straightforward antialiasing algorithm to draw lines of variable thickness.

Brisco

Answer 8

I assume that you would draw horizontal spans from one bounding line to another, and compute the x-value of each of the lines by Bresenham's method as you go (in a single loop).

Haven't tried it.

The end points may need some attention, lest they look oddly cut-off.

Maharanee

yes this was the strategy that i had in mind too and i agree that the end-points will need some thought. – Lyophilize

Answer 9

I do this quite often to generate images of fibers and spheres for porous media simulations. I have a nice simple way do this using a very standard image analysis technique know as the 'distance transform'. This requires having access to some image analysis package. I use Python with Scipy, so this is no problem. Here is a demo to convert randomly distributed points into spheres:

import scipy as sp
import scipy.ndimage as spim

im1 = sp.rand(100, 100) < 0.995  # Create random points in space
dt = spim.distance_transform_edt(im1)
im2 = dt < 5  # To create sphere with a radius of 5

And that is it! The distance transform can be slow for very large images, but there are efficient version out there. For instance, ImageJ has a parallelized one. Obviously, to create thick fibers you just create your image of thin ones, then apply the steps 2 and 3 above.

Cram

Answer 10

For those who want a Python version here goes the code (based on the answer of @Fabel):

def drawline(x1,y1,x2,y2,**kwargs):  
    if kwargs.get('thickness')==None:
        thickness=1
    else:
        thickness=kwargs['thickness']
    if kwargs.get('roundcap')==None:
        roundcap=False
    else:
        roundcap=True
    angle = np.arctan2(y2-y1,x2-x1)
    xx = np.zeros(4)
    yy = np.zeros(4)
    xx[0] = np.round(x1 + thickness*np.cos(angle+np.pi/2))
    yy[0] = np.round(y1 + thickness*np.sin(angle+np.pi/2))
    xx[1] = np.round(x1 + thickness*np.cos(angle-np.pi/2))
    yy[1] = np.round(y1 + thickness*np.sin(angle-np.pi/2))
    xx[2] = np.round(x2 + thickness*np.cos(angle-np.pi/2))
    yy[2] = np.round(y2 + thickness*np.sin(angle-np.pi/2))
    xx[3] = np.round(x2 + thickness*np.cos(angle+np.pi/2))
    yy[3] = np.round(y2 + thickness*np.sin(angle+np.pi/2))
    u,v=polygon(xx,yy)    
    if roundcap:
        temp1x, temp1y = circle(x1,y1,thickness)
        temp2x, temp2y = circle(x1,y1,thickness)
        u = np.append(u,temp1x,temp2x)
        v = np.append(v,temp1y,temp2y)
    return u,v

When calling the function you can optionally specify thickness and roundcap. For example:

drawline(10,10,50,50,thickness=3,roundcap=False)

Eleusis

you are calling polygon here. What is that? – Batwing

@Batwing if the line has high thickness then it will be a polygon. – Eleusis

I mean, you are calling the function polygon which has no import or implementation. Where is that? – Batwing

There are many approaches but you can use the matplotlib function. Check this: #43971759 – Eleusis

I am not trying to render anything, I want the underlying result of which pixels are on and off, without going through an image. – Batwing

Answer 11

For my embedded thermal printer application, using Bresenham's algorithm, the line was way too thin. I don't have GL or anything fancy. I ended up simply decrementing the Y value and drawing more lines under the first one. Each number of thickness added another line. Very quick to implement and made for the desired results printing from monochrome bitmap to the thermal.

Jiggered

I liked your idea, how did you test/calculate the desired distance between lines so that you mimic the thickness ? was it by trial and error ? – Nippy

Every dot has another dot below it... no calculations; the line was visibly thicker. I ended up using 3 lines, each with a Y value less than previous. Any y less than y minimum was change to Y minimum. – Jiggered

Sorry I miss confused about controlling the thickness and controlling the width of the line. – Nippy

If you do what you said, then vertical lines always have a thickness of 1, and always longer than requested by the thickness. – Fiden

Answer 12

I was facing the same problem some time ago. Based on this paper, I created a Matlab reference implementation, which I would like to share on GitHub.

Pathetic