Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

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.

like image 738
horseyguy Avatar asked Aug 03 '09 14:08

horseyguy


People also ask

What is Bresenham's line drawing algorithm with example?

Given the starting and ending coordinates of a line, Bresenham Line Drawing Algorithm attempts to generate the points between the starting and ending coordinates.

What is the purpose of Bresenham line drawing algorithm?

Bresenham's line algorithm is a line drawing algorithm that determines the points of an n-dimensional raster that should be selected in order to form a close approximation to a straight line between two points.

What is the basic principle of Bresenham's line drawing algorithm?

The basic principle of Bresenham's line algorithm is to select the optimum raster locations to represent a straight line.


2 Answers

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.

Test page with bresenham lines with different thickness

like image 135
Armin J. Avatar answered Oct 04 '22 09:10

Armin J.


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.

like image 21
Martin B Avatar answered Oct 04 '22 08:10

Martin B