Line drawing algorithm

You can help expand this article with text translated from the corresponding article in German. (December 2009) Click [show] for important translation instructions. 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

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 ${\displaystyle x_{2}>x_{1}}$. This algorithm works just fine when ${\displaystyle dx\geq dy}$ (i.e., slope is less than or equal to 1), but if ${\displaystyle dx<dy}$ (i.e., slope greater than 1), the line becomes quite sparse with many gaps, and in the limiting case of ${\displaystyle dx=0}$, 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