View source for Line drawing algorithm

{{Short description|Methods of approximating line segments for pixel displays}}
{{Expand German|Rasterung von Linien|fa=yes|topic=sci|date=December 2009}}
[[File:Line scan-conversion.svg|thumb|upright=1.0|Two rasterized lines. The colored pixels are shown as circles. Above: monochrome screening; below: Gupta-Sproull anti-aliasing; the ideal line is considered here as a surface.]]

In [[computer graphics]], a '''line drawing algorithm''' is an [[algorithm]] for approximating a [[line segment]] on discrete [[Graphics|graphical]] media, such as [[pixel]]-based [[computer display|displays]] and [[computer printer|printers]]. On such media, line drawing requires an [[Approximation algorithm|approximation]] (in nontrivial cases). Basic algorithms [[Rasterisation|rasterize]] lines in one color. A better representation with multiple [[Gradation (art)|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 oscilloscope]]s use analog phenomena to draw lines and curves.

== Single color line drawing algorithms ==
[[File:Xiaolin Wu lines.png|thumb|Lines using Xiaolin Wu's algorithm, showing "ropey" appearance]]
Single color line drawing algorithms involve drawing lines in a single foreground color onto a background. They are well-suited for usage with monochromatic displays.

The starting point and end point of the desired line are usually given in integer coordinates, so that they lie directly on the points considered by the algorithm. Because of this, most algorithms are formulated only for such starting points and end points.

=== Simple methods ===
The simplest method of drawing a line involves directly calculating pixel positions from a line equation. Given a starting point <math>(x_1, y_1)</math> and an end point <math>(x_2, y_2)</math>, points on the line fulfill the equation <math>y = m(x-x_1) + y_1</math>, with <math>\textstyle m = \frac{\Delta y}{\Delta x} = \frac{y_2-y_1}{x_2-x_1}</math> being the [[slope]] of the line. The line can then be drawn by evaluating this
equation via a simple loop, as shown in the following pseudocode:

 dx = x2 − x1
 dy = y2 − y1
 m = dy/dx
 '''for''' x '''from''' x1 '''to''' x2 '''do'''
     y = m × (x − x1) + y1
     plot(x, y)

Here, the points have already been ordered so that <math>x_2 > x_1</math>.

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:

:{|
|-
| <math>y_{i+1} - y_i \!</math>
| <math>= (m(x_{i+1}-x_1) + y_1) - (m(x_i-x_1) + y_1) \!</math>
|-
|  || <math>= m(x_{i+1}-x_i) \!</math>
|-
|  || <math>= m \!</math>.
|}

Therefore, it is enough to simply start at the point <math>(x_1, y_1)</math> and then increase <math> y </math> by <math> m </math> once on every iteration of the loop. This algorithm is known as a [[Digital differential analyzer (graphics algorithm) | Digital differential analyzer]].

Because rounding <math> y </math> to the nearest whole number is equivalent to rounding <math> y+0.5 </math> down, rounding can be avoided by using an additional control variable that is initialized with the value 0.5. <math> m </math> is added to this variable on every iteration. Then, if this variable exceeds 1.0, <math> y </math> is incremented by 1 and the control variable is decremented by 1. This allows the algorithm to avoid rounding and only use integer operations. However, for short lines, this faster loop does not make up for the expensive division <math>\textstyle m = \frac{\Delta y}{\Delta x} = \frac{y_2-y_1}{x_2-x_1}</math>, which is still necessary at the beginning.

These algorithm works just fine when <math>dx \geq dy</math> (i.e., slope is less than or equal to 1), but if <math>dx < dy</math> (i.e., slope greater than 1), the line becomes quite sparse with many gaps, and in the limiting case of <math>dx = 0</math>, a division by zero exception will occur.

=== Issues ===
In certain situations, single color line drawing algorithms run into issues:

==== Inconsistent brightness ====
When drawing lines of the same length with differing slopes, different numbers of pixels are drawn. This leads to steeper lines being made up of fewer pixels than flatter lines of the same length, which leads to the steeper line appearing brighter than the flat line. This problem is unavoidable on monochromatic devices.

==== Clipping ====
[[Clipping_(computer_graphics)|Clipping]] is an operation that limits rasterisation to a limited, usually rectangular, area. 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. For this issue to be avoided, additional tests are necessary after clipping.

== Antialiasing ==
The biggest issue of single color line drawing algorithms is that they lead to [[Jaggies|lines with a rough, jagged appearance]]. On devices capable of displaying multiple levels of brightness, this issue can be avoided through [[Spatial anti-aliasing| 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.

=== Gupta and Sproull algorithm ===
The [[Gupta-Sproull algorithm|Gupta-Sproull]] algorithm is based on [[Bresenham's line algorithm|Bresenham's]] line algorithm but adds [[Anti-aliasing|antialiasing]].

An optimized variant of the Gupta-Sproull algorithm can be written in pseudocode as follows:

 DrawLine(x1, x2, y1, y2) {
     x = x1;
     y = y1;
     dx = x2 − x1;
     dy = y2 − y1;
     d = 2 * dy − dx; // discriminator

     // Euclidean distance of point (x,y) from line (signed)
     D = 0; 

     // Euclidean distance between points (x1, y1) and (x2, y2)
     length = sqrt(dx * dx + dy * dy); 

     sin = dx / length;
     cos = dy / length;
     '''while''' (x <= x2) {
         IntensifyPixels(x, y − 1, D + cos);
         IntensifyPixels(x, y, D);
         IntensifyPixels(x, y + 1, D − cos);
         x = x + 1
         '''if''' (d <= 0) {
             D = D + sin;
             d = d + 2 * dy;
         } '''else''' {
             D = D + sin − cos;
             d = d + 2 * (dy − dx);
             y = y + 1;
         }
     }
 }

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.

== Optimizations ==
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_computing|real time]].

=== Approximate methods ===
Boyer and Bourdin introduced an approximation algorithm that colors pixels lying directly under the ideal line.<ref>Vincent Boyer, Jean-Jacques Bourdin: ''Fast Lines: a Span by Span Method.'' Computer Graphics Forum 18, 3 (1999): 377–384 ({{webarchive|url=https://www.ai.univ-paris8.fr/~jj/Gris/Articles/eg99.pdf |wayback=20070118211901 |text=PDF, 400 kB |date=23 April 2024}})</ref> A line rendered in this way exhibits some special properties that may be taken advantage of. For example, in cases like this, sections of the line are periodical. This results in an algorithm which is significantly faster than precise variants, especially for longer lines. A worsening in quality is only visible on lines with very low steepness.

=== Parallelization ===
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.<ref>Robert F. Sproull: ''Using program transformations to derive line-drawing algorithms.'' ''ACM Transactions on Graphics'' 1, 4 (October 1982): 259–273, {{ISSN|0730-0301}}</ref> Another method involves dividing the line into multiple sections of approximately equal length, which are then assigned to different [[Processor_(computing)|processors]] for rasterization. The main problem is finding the correct start points and end points of these sections. 

Algorithms for [[massively parallel]] processor architectures with thousands of processors also exist. In these, every pixel out of a grid of pixels is assigned to a single processor, which then decides whether the given pixel should be colored or not.<ref>Alex T. Pang: ''Line-drawing algorithms for parallel machines.'' IEEE Computer Graphics and Applications 10, 5 (September 1990): 54–59</ref>

Special memory hierarchies have been developed to accelerate memory access during rasterization. These may, for example, divide memory into multiple cells, which then each render a section of the line independently.<ref>See for example Pere Marès Martí, Antonio B. Martínez Velasco: ''Memory architecture for parallel line drawing based on nonincremental algorithm.'' In: ''[[Euromicro]] 2000 Proceedings:'' Vol. 1, 266–273. IEEE Computer Society Press, Los Alamitos 2000, ISBN 0-7695-0780-8</ref>
Rasterization involving Antialiasing can be supported by dedicated Hardware as well.<ref>See for example Robert McNamara u. a.: ''Prefiltered Antialiased Lines Using Half-Plane Distance Functions.'' In ''HWWS 2000 Proceedings:'' 77–85. ACM Press, New York 2000, ISBN 1-58113-257-3</ref>

== Related problems ==
Lines may not only be drawn 8-connected, but also 4-connected, meaning that only horizontal and vertical steps are allowed, while diagonal steps are prohibited. Given a raster of square pixels, this leads to every square containing a part of the line being colored. A generalization of 4-connected line drawing methods to three dimensions is used when dealing with [[voxel]] grids, for example in optimized [[Ray tracing (graphics)|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.<ref>Chengfu Yao, Jon G. Rokne: ''An integral linear interpolation approach to the design of incremental line algorithms.'' Journal of Computational and Applied Mathematics 102, 1 (February 1999): 3–19, {{ISSN|0377-0427}}</ref> 
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 sequence|Farey sequences]] and a number of related mathematical constructs.<ref>Mitchell A. Harris, Edward M. Reingold: ''Line drawing, leap years, and Euclid.'' ACM Computing Surveys 36, 1 (March 2004): 68–80, {{ISSN|0360-0300}} ({{webarchive|url=http://emr.cs.iit.edu/~reingold/bresenham.pdf |date = 16 December 2006|wayback=20061216194847 |text=PDF, 270 kB }})</ref>

== See also ==
* [[Bresenham's line algorithm]]
* [[Circle drawing algorithm]]
* [[Rasterization]]

== References ==
{{Reflist}}
* Fundamentals of Computer Graphics, 2nd Edition, A.K. Peters by [[Peter Shirley]]

{{DEFAULTSORT:Line Drawing Algorithm}}
[[Category:Computer graphics algorithms]]