Line drawing algorithm
- View a machine-translated version of the German article.
- Machine translation, like DeepL or Google Translate, is a useful starting point for translations, but translators must revise errors as necessary and confirm that the translation is accurate, rather than simply copy-pasting machine-translated text into the English Wikipedia.
- Do not translate text that appears unreliable or low-quality. If possible, verify the text with references provided in the foreign-language article.
- You must provide copyright attribution in the edit summary accompanying your translation by providing an interlanguage link to the source of your translation. A model attribution edit summary is
Content in this edit is translated from the existing German Wikipedia article at [[:de:Rasterung von Linien]]; see its history for attribution.
- You may also add the template
{{Translated|de|Rasterung von Linien}}
to the talk page. - For more guidance, see Wikipedia:Translation.
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). Basic algorithms rasterize lines in one color. 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.
List of line drawing algorithms
The following is a partial list of line drawing algorithms:
- Naive algorithm
- Digital Differential Analyzer (graphics algorithm) — Similar to the naive line-drawing algorithm, with minor variations.
- Bresenham's line algorithm — optimized to use only additions (i.e. no division Multiplications); it also avoids floating-point computations.
- Xiaolin Wu's line algorithm — can perform spatial anti-aliasing, appears "ropey" from brightness varying along the length of the line, though this effect may be greatly reduced by pre-compensating the pixel values for the target display's gamma curve, e.g. out = in ^ (1/2.4).[original research?]
- Gupta-Sproull algorithm
A naive line-drawing algorithm
The simplest method of screening is the direct drawing of the equation defining the line.
dx = x2 − x1 dy = y2 − y1 for x from x1 to x2 do y = y1 + dy × (x − x1) / dx plot(x, y)
It is here that the points have already been ordered so that . This algorithm works just fine when (i.e., slope is less than or equal to 1), but if (i.e., slope greater than 1), the line becomes quite sparse with many gaps, and in the limiting case of , a division by zero exception will occur.
The naive line drawing algorithm is inefficient and thus, slow on a digital computer. Its inefficiency stems from the number of operations and the use of floating-point calculations. Algorithms such as Bresenham's line algorithm or Xiaolin Wu's line algorithm are preferred instead.
Gupta and Sproull algorithm
The Gupta-Sproull algorithm is based on Bresenham's line algorithm but adds 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.
References
- Fundamentals of Computer Graphics, 2nd Edition, A.K. Peters by Peter Shirley