Line drawing algorithm
In computer graphics, a line drawing algorithm is an algorithm for approximating a line segment on discrete graphical media, such as pixel-based displays and printers.
On such media, line drawing requires an approximation (in nontrivial cases).
A better representation with multiple color gradations requires an advanced process, spatial anti-aliasing.
On continuous media, by contrast, no algorithm is necessary to draw a line.
For example, cathode-ray oscilloscopes use analog phenomena to draw lines and curves.
The line can then be drawn by evaluating this equation via a simple loop, as shown in the following pseudocode: Here, the points have already been ordered so that
This algorithm is unnecessarily slow because the loop involves a multiplication, which is significantly slower than addition or subtraction on most devices.
A faster method can be achieved by viewing the Difference between two consecutive steps: Therefore, it is enough to simply start at the point
However, for short lines, this faster loop does not make up for the expensive division
(i.e., slope greater than 1), the line becomes quite sparse with many gaps, and in the limiting case of
In certain situations, single color line drawing algorithms run into issues: When drawing lines of the same length with differing slopes, different numbers of pixels are drawn.
This is done by moving the start- and end points of the given line to the borders of this area if they lie outside of it.
Generally, this leads to the coordinates of these points no longer being integer numbers.
If these coordinates are simply rounded, the resulting line will have a different slope than intended.
On devices capable of displaying multiple levels of brightness, this issue can be avoided through antialiasing.
For this, lines are usually viewed in a two-dimensional form, generally as a rectangle with a desired thickness.
To draw these lines, points lying near this rectangle have to be considered.
An optimized variant of the Gupta-Sproull algorithm can be written in pseudocode as follows: The IntensifyPixels(x,y,r) function takes a radial line transformation and sets the intensity of the pixel (x,y) with the value of a cubic polynomial that depends on the pixel's distance r from the line.
Line drawing algorithms can be made more efficient through approximate methods, through usage of direct hardware implementations, and through parallelization.
Such optimizations become necessary when rendering a large number of lines in real time.
Boyer and Bourdin introduced an approximation algorithm that colors pixels lying directly under the ideal line.
This results in an algorithm which is significantly faster than precise variants, especially for longer lines.
A simple way to parallelize single-color line rasterization is to let multiple line-drawing algorithms draw offset pixels of a certain distance from each other.
[2] Another method involves dividing the line into multiple sections of approximately equal length, which are then assigned to different processors for rasterization.
These may, for example, divide memory into multiple cells, which then each render a section of the line independently.
A generalization of 4-connected line drawing methods to three dimensions is used when dealing with voxel grids, for example in optimized ray tracing, where it can determine the voxels that a given ray crosses.
Line drawing algorithms distribute diagonal steps approximately evenly.
Thus, line drawing algorithms may also be used to evenly distribute points with integer coordinates in a given interval.
[6] Possible applications of this method include linear interpolation or downsampling in signal processing.
There are also parallels to the Euclidean algorithm, as well as Farey sequences and a number of related mathematical constructs.
