Rasterization of lines

The rasterization of lines is an elementary task of computer graphics , in which a line is drawn ( rasterized ) on the point grid of a raster graphic or a raster graphics device . To do this, those points or pixels that approximate the ideal route as closely as possible are colored .

Basic algorithms only rasterize lines in one color. A better display with several color gradations is obtained with advanced methods that support antialiasing (edge ​​smoothing).

Since more complex geometrical figures such as polygons and any curves are often composed of line segments in computer graphics, the rasterization of lines also forms the starting point for their rasterization. Another application that often requires a large number of lines to be drawn is the display of wire frame models .

Two rasterized lines. The colored pixels are shown as circles. Above: monochrome rasterization; below: Gupta-Sproull antialiasing, the ideal line is considered here as a surface.

Monochrome halftone

Single-color rasterization draws lines with a single foreground color on a background. It is suitable for devices with monochrome display, for example laser printers .

The start and end points of the line to be rasterized are usually given in integer coordinates, that is, they lie directly on the points of the raster. Therefore, most of the methods are only formulated for such start and end points. There are several options for rasterizing thick lines, which are also suitable for other curves, see the article Screening .

Simple methods

Naive method of screening using rounding

The simplest way to rasterize is to directly implement the equation that defines the line. If ( x _a , y _a ) is the start point and ( x _e , y _e ) the end point of the line, the points on the line satisfy the straight line equation , where is the slope . ${\displaystyle y=m(x-x_{a})+y_{a}}$ ${\displaystyle \textstyle m={\frac {\Delta y}{\Delta x}}={\frac {y_{e}-y_{a}}{x_{e}-x_{a}}}}$

The line is drawn by calculating the corresponding value in a loop for each from to value according to this formula and rounding it to the nearest integer. The pixel ( x , y ) is then colored. ${\displaystyle x}$ ${\displaystyle x_{a}}$ ${\displaystyle x_{e}}$ ${\displaystyle y}$

This method is unnecessarily slow because a multiplication is performed within the loop, which on most computers requires considerably more computation time than an addition or subtraction. A faster method is to consider the difference between two successive steps:

${\displaystyle y_{i+1}-y_{i}\!}$	${\displaystyle =(m(x_{i+1}-x_{a})+y_{a})-(m(x_{i}-x_{a})+y_{a})\!}$
	${\displaystyle =m(x_{i+1}-x_{i})\!}$
	${\displaystyle =m\!}$.

Accordingly, it is sufficient to start with ( x _a , y _a ) and increase by with each loop pass . This method is also known as a Digital Differential Analyzer (DDA). ${\displaystyle y}$ ${\displaystyle m}$

Since the rounding of to the next integer corresponds to the rounding off of , an additional control variable can also be used, which is initialized with 0.5 and to which is added with every loop pass. Every time the control variable reaches or exceeds 1.0, it is increased by 1 and 1.0 is subtracted from the control variable. This means that rounding is no longer necessary. This method can be rephrased to use only faster integer operations and can be implemented neatly in assembly language . Nevertheless, a slow division ( ) is still necessary at the beginning, which cannot be compensated for by the fast loop for short lines. ${\displaystyle y}$ ${\displaystyle y+0{,}5}$ ${\displaystyle m}$ ${\displaystyle y}$ ${\displaystyle \Delta y/\Delta x}$

Generalization in any direction

Rasterization of any lines by using symmetry properties. The permissible area of ​​the original procedure is shown in color; the three changes to the algorithm also open up the other areas.

The methods just described only work with line slopes between 0 and 1, which corresponds to an angle of 0 ° to 45 ° to the horizontal. In the case of other slopes, the line is not drawn or drawn incorrectly. However, it is sufficient to describe an algorithm only for slopes between 0 and 1, since other lines can be displayed correctly by using symmetries. This is done through the following three changes:

1. A distinction is made between two cases, depending on whether (in terms of amount) or vice versa. In the first case, the loop is run through as before and calculated in the body of the loop , otherwise it is run through and calculated using. ${\displaystyle \Delta x>\Delta y}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle y}$ ${\displaystyle x}$
2. Within the body of the loop, or is not increased by 1, but depending on the sign of or, the value +1 or −1 is added. ${\displaystyle y}$ ${\displaystyle x}$ ${\displaystyle \Delta y}$ ${\displaystyle \Delta x}$
3. If or , the loop must be run through backwards. ${\displaystyle \Delta x<0}$ ${\displaystyle \Delta y<0}$

By applying these generalizations, the following table can be created for a better overview:

quadrant	m <= 1	otherwise (m> 1)	direction
1	x ++ y = y1 + m * i	x = x1 + i / m y ++	from bottom left to top right
2	x-- y = y1 + m * i	x = x1 + i / m y ++	from bottom right to top left
3	x-- y = y1 - m * i	x = x1 - i / m y--	from top right to bottom left
4th	x ++ y = y1 + m * i	x = x1 - i / m y--	from top left to bottom right

Where i for m <= 1 values ​​between 0 and and for m> 1 values ​​between 0 and . Lines that are parallel to the X or Y axis are also covered by this table and do not have to be considered separately. The indicated direction refers to the graphic on the right, assuming that x increases to the right and y increases upwards. x1 and y1 are the coordinates of the starting point of a line and x2 and y2 are the coordinates of the end point. ${\displaystyle \Delta x}$ ${\displaystyle \Delta y}$

Furthermore, the following pseudocode can only be created by changing the sign, which covers all eight cases described:

  signX = 1;
  signY = 1;

  if x1 > x2
      signX = -1;

  if y1 > y2
      signY = -1;

  if m <= 1
      for i=0; i <= deltaX; i++
          drawPixel( ceil(x1 + i * signX), ceil(y1 + i * m * signY) )
  else
      for i=0; i<= deltaY; i++
          drawPixel( ceil(x1 + i / m * signX), ceil(y1 + i * signY) )

Where ceil () is a function to round up and drawPixel can be any function to set a pixel.

Bresenham's algorithm

The oldest published algorithms for rasterizing lines date from the early 1960s. They were used to control digital plotters , in which the pen could only move horizontally, vertically or diagonally on a grid at fixed intervals. This also included the Bresenham algorithm presented by Jack Bresenham in 1963 , which only uses integer calculations. Pitteway gave an equivalent derivation of this algorithm, which has the advantage over Bresenham's rather geometric formulation that it can also be applied to curves other than lines. The resulting algorithm, sometimes called the "midpoint algorithm", is exactly the same as in Bresenham's paper.

Choice of the next pixel in the Bresenham algorithm

The idea of ​​the Bresenham algorithm is to choose between the two pixels to the right ("east") and top right ("northeast") of the last pixel drawn at each step. The pixel that is closer to the ideal line is selected. To do this, look at the midpoint between the pixels in the midpoint formulation and : if it is above the ideal line, it is closer, otherwise . ${\displaystyle M}$ ${\displaystyle O}$ ${\displaystyle NO}$ ${\displaystyle M}$ ${\displaystyle O}$ ${\displaystyle NO}$

To find the position of opposite the line, another form of the straight line equation is used: ${\displaystyle M}$

${\displaystyle F(x,\,y)=ax+by+c=\Delta y\cdot x-\Delta x\cdot y+c=0}$.

F ( x, y ) is 0 for points on the line, positive for points below and negative for points above the line. If the coordinates of are inserted into this equation , the value is obtained ${\displaystyle M}$

${\displaystyle \textstyle d_{i}=F(x_{i}+1,\,y_{i}+{\frac {1}{2}})=\Delta y(x_{i}+1)-\Delta x(y_{i}+{\frac {1}{2}})+c}$.

Depending on the sign of this control variable , the pixel or is selected. ${\displaystyle d_{i}}$ ${\displaystyle O}$ ${\displaystyle NO}$

In order to obtain an efficient algorithm, the control variable is calculated incrementally, i.e. increased step by step. How you change it between two successive steps depends on whether pixels or was selected. For each of these cases, consider the difference between the value of the control variable for the next but one and the next pixel: ${\displaystyle O}$ ${\displaystyle NO}$

${\displaystyle {\begin{aligned}\textstyle \Delta _{O}&=\textstyle d_{i+1}-d_{i}=F(x_{i}+2,\,y_{i}+{\frac {1}{2}})-d_{i}=\Delta y\\\textstyle \Delta _{NO}&=\textstyle d_{i+1}-d_{i}=F(x_{i}+2,\,y_{i}+{\frac {3}{2}})-d_{i}=\Delta y-\Delta x\\\end{aligned}}}$

At each step the control variable is increased by or depending on the selected pixel . If , then is above the straight line, which is why it is selected, otherwise . ${\displaystyle \Delta _{O}}$ ${\displaystyle \Delta _{NO}}$ ${\displaystyle d_{i}\leq 0}$ ${\displaystyle M}$ ${\displaystyle O}$ ${\displaystyle NO}$

The initial value of the control variable can also be calculated efficiently if the starting point of the line is exactly on a pixel: ${\displaystyle d}$ ${\displaystyle F(x_{a},\,y_{a})=0}$

${\displaystyle \textstyle d_{0}=F\left(x_{a}+1,\,y_{a}+{\frac {1}{2}}\right)=\ \underbrace {\Delta y\cdot x_{a}-\Delta x\cdot y_{a}+c} _{=F(x_{a},\,y_{a})=0}\,+\,\Delta y-{\frac {\Delta x}{2}}=\Delta y-{\frac {\Delta x}{2}}}$

To eliminate the division by 2, all values ​​of the control variable are doubled; the decisive sign is retained. The Bresenham algorithm for lines with a slope between 0 and 1 can thus be expressed in the following pseudocode . The algorithm only needs additions within the loop; the simple multiplications outside the loop can also be implemented by adding.

Change in the control variable in the Bresenham algorithm

d = 2×Δy – Δx ΔO = 2×Δy ΔNO = 2×(Δy − Δx) y = ya Pixel (xa, ya) einfärben Für jedes x von xa+1 bis xe Wenn d ≤ 0 d = d + ΔO ansonsten d = d + ΔNO y = y + 1 Pixel (x, y) einfärben

Another interpretation of the algorithm is based on the finding that the rasterized line contains horizontal and diagonal steps. In order to “mix” these two step types, each step is either subtracted from the control variable or added. The corresponding step type is carried out in which the resulting amount of the control variable is lower. This is also clear from the graphic above, in which the control variable is always as close as possible to the zero axis. Thompson described an algorithm based on this formulation in 1964, but did not discuss the choice of the correct initial value for the control variable. Before Bresenham, Fred Stockton published an algorithm for rasterizing lines in 1963, which also only uses integer calculations, but is unnecessarily complicated. ${\displaystyle m=\Delta x-\Delta y}$ ${\displaystyle n=\Delta y}$ ${\displaystyle m}$ ${\displaystyle n}$

Lines whose end points are given with non-integer coordinates can also be rasterized using the Bresenham algorithm. To do this, the initial value of the control variable must be calculated according to its original definition; general simplifications are not possible. The rest of the algorithm remains valid.

Rows of pixels

Although the Bresenham algorithm is quite efficient, it only draws one pixel per loop and needs an addition. A method that draws all pixels in a "row" - that is, pixels with the same y -coordinate - at once was developed by Reggiori for the first time. Rows with only one pixel were treated separately. Bresenham later presented a more general algorithm that managed without tests for this special case.

With Bresenham's pixel row algorithm, it is not incrementally increased, but . The end of the current row is calculated for each . This is done by looking at the points at which the ideal line intersects a horizontal running through the center point between two vertically adjacent pixels. The end of the row of pixels is the rounded value of the x -coordinate of this intersection: ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle y}$

The end point coordinates of the pixel rows can also be calculated incrementally. Since some points can be incorrectly calculated here with certain slopes, the algorithm uses a symmetry to the straight line of slope ½.

No additions are required in the innermost loop of Bresenham's new algorithm, because all pixels in a row are colored at once. However, division is required for initialization. Fung replaced it with a search procedure and made some further optimizations.

N -step method

The four possible pixel patterns in the double step method

Another way of rasterizing, first introduced by Wu and Rokne, is to take steps of several pixels along the x- axis and to color all pixels of the line in between at once. To do this, a choice is made between the various possible “pixel patterns”. Bresenham's algorithm can be seen as a special case of this method, in which only steps of one pixel each are taken and in which only two "patterns" (pixels on the right or top right) are chosen.

In order to be able to differentiate between the four possible patterns in the double step method, the last pixel column of the pattern is first considered. If the pixel to be rasterized is at the bottom or at the top, it is trivial to infer patterns 1 or 4. If, on the other hand, the pixel is in the middle, an additional test of the middle column is necessary in order to be able to choose between patterns 2 and 3.

These tests are simplified by the fact that with a slope m  ½ pattern 4 and with m  ½ pattern 1 cannot occur. Similar to the Bresenham algorithm, the control variable for the tests can also be calculated incrementally with the double-step method. In the end, the algorithm only gets by with additions and a simple multiplication, which can be implemented with a fast bit shift .

Triple and quadruple step algorithms have also been developed that work on the same principle but are considerably more complicated and longer. Another four-step algorithm uses a slightly different formulation that systematically examines the conditions under which a particular pattern occurs and that can be generalized to any number of steps.

Bidirectional screening

Above: A line rasterized from left to right using the Bresenham algorithm; below: bidirectional screening. The hollow circles indicate the pixels that will be colored when the other pixel is selected at d = 0.

To further increase the speed of the rasterization, it makes sense to draw the line bidirectionally, i.e. at the same time from the start and end point to the center point. Here the loop only runs over half of the line; with each step the two pixels involved are colored on each side of the line. Both the Bresenham algorithm and other methods can be modified in this way.

It must be noted, however, that the line rasterized with the normal methods is not necessarily point-symmetrical in itself . This is because there are ambiguous situations in the rasterization in which the ideal line runs exactly through the center of two vertically adjacent pixels, between which you can freely choose. The Bresenham algorithm listed above, for example, always selects the pixel with the smaller y coordinate in such cases ( ) . When drawing from right to left, however, due to the use of symmetry, the pixel with the larger y coordinate is selected. If the line is drawn bidirectionally or from right to left, the appearance can therefore change compared to the normal algorithm, unless the ambiguous cases are tested separately. ${\displaystyle d=0}$

Other techniques

periodicity

It can be shown that the values ​​of the control variable repeat a times in the Bresenham algorithm , where a is the greatest common divisor of and . This means that the values ​​of the control variable only have to be calculated for part of the line and can then be applied to the other parts. For this, however, the GCD must be calculated. This method can also be combined with bidirectional screening. ${\displaystyle \Delta x}$ ${\displaystyle \Delta y}$

Rows of pixels of the first, second and third order

Hierarchical rows of pixels

The length of the rows of pixels in a rasterized line follows a certain pattern. Rosenfeld proved that the length of all rows of pixels, except possibly the first and the last, differ by no more than one pixel. He also found that the sequence of rows of pixels itself has this structure, as does the sequence of those sequences, and so on. Rasterized lines are built up hierarchically from rows of the “ nth order”, each of which can only assume certain lengths. Stephenson described workable algorithms that can draw a line from rows of any high order, as well as a recursive algorithm that starts from the highest possible order. This generalizes both the Bresenham algorithm and the pixel row algorithm. The algorithm for rows of "zeroth order", in which the rows of pixels are ignored, corresponds to the usual Bresenham algorithm.

Structural algorithms

Other algorithms have been proposed for rasterization, but they do not work incrementally, but make direct use of the structural properties of the rasterized lines. They are based on considerations from image processing or digital geometry and in practice do not achieve the speed of conventional methods, as they manipulate character strings or require other slow operations.

Brons' algorithm, for example, represents the rasterized line by a string of zeros and ones, where 0 stands for a horizontal and 1 for a diagonal step. The algorithm assumes a character string that represents a first approximation of the line, combines sequences of zeros and ones and distributes them evenly. The same process is applied to the resulting sequence. This is repeated until no further improvement can be achieved. However, the line rasterized in this way is not optimal; to get the same line as with the Bresenham algorithm, additional adjustments are necessary.

Properties and comparison

Although numerous algorithms have been discovered that are less complex than the Bresenham algorithm, their practical speed advantage is small. This is because the instructions for coloring pixels on today's hardware are very slow compared to running the raster algorithm itself. However, some graphics cards provide somewhat faster functions for coloring multiple pixels at once, such as the rectwrite function on SGI systems. This is an advantage for pixel row algorithms that can draw such a row quickly at once.

The speed of execution of the various algorithms depends on the length of the line to be rasterized. Algorithms whose inner loop is fast, but which require a lot of time to initialize, can only boast a speed advantage with long lines. It was therefore proposed to choose the most efficient algorithm in each case as a function of the length of the line. A statistical analysis of the line lengths in various applications such as the display of wire frame models, curve segments and characters came to the result that almost three quarters of all rasterized lines were less than ten pixels long. It is therefore worthwhile to optimize for the special case of short lines. Algorithms that are more advantageous for rasterizing long lines are better suited for output devices with a higher resolution than screens and thus longer lines on average, such as laser printers. With some algorithms, the speed also depends on the slope of the line - pixel row algorithms, for example, are less efficient with diagonal lines, since only one pixel per row can be drawn here.

Another factor in choosing an algorithm is program length. Manufacturers of graphics processors who implement rasterization directly on the hardware level and therefore need to save space prefer short algorithms such as the Bresenham algorithm. In software implementations, this factor is less critical.

Problems

Different brightnesses depending on the slope

All monochrome screening algorithms can cause problems in certain situations:

Different brightness

When rasterizing lines of the same length but different gradients, the same number of pixels are not necessarily colored. In the example opposite, the diagonal line is longer than the horizontal one, but the same number of pixels are colored in both cases. As a result, the two lines appear differently light on the output device. This problem cannot be circumvented with monochrome devices.

Line styles

Using symmetry to rasterize lines with any starting and ending point can cause undesirable effects if certain line styles are used. If dashed or dotted lines are to be drawn, the respective pattern starts at the starting point of the line. Such lines are drawn differently if the start and end points are swapped. If the strokes of a line style are defined by a certain number of pixels to be colored, the actual stroke length also varies depending on the gradient.

Clipping

This clipping is an operation which restricts the screening to a specific, usually rectangular area. This is done by moving the start and end points of the line to be rasterized to the edges of the rectangular area, if they protrude. In general, this means that the coordinates of these points are no longer integers. If these coordinates are rounded anyway, a line with a different slope and thus possibly a different appearance results. To avoid this, additional tests are necessary after clipping. The Bresenham algorithm can also be combined with a clipping algorithm.

Antialiasing

The biggest problem with monochrome rasterized lines is their generally "stair-like" appearance, also known as the staircase effect . This effect can be counteracted by anti-aliasing on graphics devices that are capable of displaying multiple brightness levels . Here, the line to be rasterized is usually no longer viewed as a one-dimensional line, but as a two-dimensional shape, in the simplest case as a rectangle with the desired thickness. For the rasterization, the color values ​​of the pixels in the vicinity of the rectangle must be determined.

Method of Gupta and Sproull

Illustration of the conical smoothing kernel. The intensity of the pixel is proportional to the volume V.

With antialiasing, the color value of a pixel can be determined by placing a so-called smoothing kernel or reconstruction filter over the pixel. Gupta and Sproull proposed a cone with a radius of one pixel as the smoothing core . The color value of the pixel is proportional to the volume of the part of the cone that overlaps the line to be rasterized (here the rectangle to be rasterized). This volume in turn depends on the distance between the center line of the rectangle and the pixel. ${\displaystyle D}$

The three possible pixels that are colored with a line thickness of one pixel

The Gupta-Sproull algorithm is based on the Bresenham algorithm, but also calculates for each of the pixels whose smoothing core overlaps the line. With a line width of one pixel, this is a maximum of three pixels per column. For reasons of efficiency, the distances are not calculated exactly, only 24 possible distances are considered. The intensity values ​​corresponding to these distances have been calculated in advance and stored in a table ( lookup table ) so that they can be called up quickly. ${\displaystyle D}$

The line ends must be treated separately, as more than three pixels, up to six in total, are involved. The intensities of these pixels depend on the slope of the line. They are calculated in advance for some inclines and also saved here in a table. Other shapes for the line ends are also conceivable, for example rounded end points; the intensities of the pixels involved change accordingly.

The Gupta-Sproull algorithm is suitable for lines with any line thickness, although the lookup table also changes. If the line width is greater than one pixel, it must be noted that the smoothing cores of more than three pixels may overlap the line.

A problem with the Gupta-Sproull algorithm is that screened lines often appear to be of different lightness in different places. This "rope-like" appearance is mainly due to the inadequacy of the cone as a smoothing core.

Method of Wu

Calculation of the intensities in Wu antialiasing

Wu took a different approach to anti-aliasing, based not on the use of a specific smoothing kernel, but on a measure of error. In its basic form, the method can only be used on ideal, infinitely thin lines.

The Bresenham algorithm tries to approximate the ideal line by minimizing the "error", ie the distance between the ideal line and two possible pixels. Wu suggested another measure of error that can be applied to any curve. The error in the sense of this error measure can be completely eliminated if any color values ​​are permitted. To do this, the two pixels that are directly above and below the ideal line must assume color values ​​proportional to the vertical distance to the ideal line.

Wu gave a particularly fast algorithm for lines. Thanks to clever integer operations, he only needs one control variable, which is changed step by step and determines both the position of the two column pixels involved and their intensity.

Other techniques

Various anti-aliasing methods using the example of a CAD wire grid model. From left to right: No antialiasing (Bresenham), Gupta-Sproull, unweighted area scanning and Wu.

Another possibility of antialiasing is unweighted area sampling . Here, the color value of a pixel corresponds to the area portion of the line within a square with an edge length of one pixel around the relevant pixel, so the smoothing core is in this case a cube. Fast algorithms have been developed for this method. A disadvantage of the unweighted surface scanning is the blurred appearance of the lines.

As with monochrome screening, the structure of the rows of pixels can be used to increase the speed of screening.

In addition to the anti-aliasing processes specially optimized for lines, general processes can also be used, such as Whitted's method, in which a high-resolution raster graphic is moved along the line as a "brush".

Special optimizations

The rasterization of lines can be made even more efficient through approximation methods, use of or direct implementation in hardware and parallelization . This is necessary when a very large number of lines have to be rasterized in real time .

Approximation method

Boyer and Bourdin presented an approximation method that always colors the pixels that are directly below the ideal line. Such a rasterized line has some special properties that can be exploited. In this case, for example, not only the Bresenham control variable but also the line segments are periodic. Together with further optimizations, the result is an algorithm that is considerably faster than the precise method, especially with longer lines. A deterioration in quality is noticeable in the case of lines with a very low gradient.

Parallelization

A simple method for parallelizing the monochrome rasterization allows different algorithms to run in parallel which - each shifted slightly - draw several pixels at certain intervals. Another possibility is to divide the line into several roughly equal parts, each of which is assigned to a processor for rasterization. Each part is rendered using the Bresenham algorithm; the main problem is calculating the correct initial values ​​of the variables. It is also possible to have several processors calculate the end point coordinates of the rows using Bresenham's pixel row algorithm. Algorithms were also presented for massively parallel vector computers with over 1000 processors. Each pixel of the raster graphic is assigned to a processor that decides whether this pixel should be colored or not.

In order to accelerate the slow memory accesses during rasterization, special memory architectures were developed, for example those in which the memory is divided into cells in which part of the line can be drawn independently of one another. The screening with antialiasing can also be supported by hardware.

Related problems

4-linked grid. The squares selected in addition to the 8-connected grid are shown hatched.

Lines can not only be 8-connected as is normally the case, but also 4-connected (4-connected) . This means that no diagonal steps, but only horizontal and vertical steps are allowed. If you think of the grid of points as divided into squares, all the squares that are overlapped by the line are selected. A generalization of this technique to three dimensions is used in voxel grating, an acceleration technique of ray tracing . It is used to determine the voxels through which a ray travels during ray tracing.

In the case of rasterized lines, the diagonal pixel steps are distributed as evenly as possible. Algorithms for rasterizing lines can therefore also be used to distribute points with integer coordinates evenly in a certain interval . Possible applications are linear interpolation or downsampling in signal processing. There are further parallels to the Euclidean algorithm as well as Farey series and some other mathematical constructs.

literature

• James D. Foley, among others: Computer Graphics: Principles and Practice in C . Addison-Wesley, Reading (Massachusetts) 1995, ISBN 978-0-201-84840-3 . (Covers Bresenham's algorithm, rasterization problems, and Gupta-Sproull antialiasing)

Individual articles:

This list is a selection; a detailed bibliography is included in Stephenson's dissertation.

1. ↑ See sample code in http://www.crbond.com/papers/newline.pdf (250 kB)
2. ^ Algorithm for computer control of a digital plotter. IBM Systems Journal 4, 1 (1965): 25-30, ISSN  0018-8670 ( PDF, 220 kB ). Already presented in August 1963 as a lecture at the ACM National Conference in Denver.
3. ↑ Mike LV Pitteway: Algorithm for Drawing Ellipses or Hyperbolae with a digital plotter. The Computer Journal 10, 3 (November 1967): 282-289, ISSN  0010-4620
4. ^ JR Thompson: Correspondence: Straight lines and graph plotters. The Computer Journal 7, 3 (Aug 1964): 227
5. ^ Fred G. Stockton: Algorithm 162: XYmove plotting. Communications of the ACM 6, 4 (April 1963): 161, ISSN  0001-0782
6. ↑ Giovanni B. Reggiori: digital computer transformations for irregular line drawings. Technical Report 403-22, New York University, New York, April 1972
7. ^ Jack E. Bresenham et al.: Run length slices for incremental lines. IBM Technical Disclosure Bulletin 22-8B (1980): 3744-3747, ISSN  0018-8689
8. ↑ ^{a b} Khun Yee Fung: A Run-Length Slice Line Drawing Algorithm without Division Operations. Computer Graphics Forum 11, 3 (1992): 267-277, ISSN  0167-7055
9. ↑ Xiaolin Wu, Jon G. Rokne: Double-step incremental generation of lines and circles. Computer Vision, Graphics, and Image Processing 37,3 (March 1987): 331-344, ISSN  0734-189X
10. ↑ Phil Graham, S. Iyengar Sitharama: Double- and triple-step incremental generation of lines. In ACM CSC '93 Proceedings: 384-389. ACM Press, Indianapolis 1993, ISBN 0-89791-558-5
11. ^ Paul Bao, Jon G. Rokne: Quadruple-step line generation. Computers & Graphics 13, 4 (1989): 461-469, ISSN  0097-8493
12. ^ Graeme W. Gill: N-Step Incremental Straight-Line Algorithms. IEEE Computer Graphics and Applications 14, 3 (May 1994): 66-72, ISSN  0272-1716
13. ↑ ^{a b} Giulio Casciola: Basic concepts to accelerate line algorithms. Computers & Graphics 12, 3/4 (1988): 489-502
14. ^ Azriel Rosenfeld: Digital Straight Line Segments. IEEE Transactions on Computers C-23, 12 (December 1974): 1264-1269, ISSN  0018-9340
15. ^ ^{A b} Peter Stephenson: The Structure of the Digitized Line: with Applications to Line Drawing and Ray Tracing in Computer Graphics. PhD Thesis, James Cook University of North Queensland, Australia, 1998 ( Online ( Memento of the original from September 5, 2007 in the Internet Archive ) Info: The archive link has been inserted automatically and has not yet been checked. Please check the original and archive link according to the instructions and remove then this note. ) 
16. ^ Reyer Brons: Linguistic Methods for the Description of a Straight Line on a Grid. Computer Graphics and Image Processing 3 (1974): 48-62, ISSN  0146-664X
17. ^ Jim X. Chen: The Analysis and Statistics of Line Distribution. IEEE Computer Graphics and Applications 22, 6 (November / December 2002): 100-107
18. ^ Yevgeny P. Kuzmin: Bresenham's Line Generation Algorithm with Built-in Clipping. Computer Graphics Forum 14, 5 (1995): 275-280
19. ↑ Satish Gupta, Robert F. Sproull: Filtering edges for gray-scale displays. In ACM SIGGRAPH '81 Proceedings: 1-5. ACM Press, Dallas 1981, ISBN 0-89791-045-1
20. ^ AR Forrest: Antialiasing in practice. In RA Earnshaw (ed.): Fundamental Algorithms for Computer Graphics (= NATO ASI Series F.17): 113-134. Springer, Berlin 1985, ISBN 3-540-13920-6
21. ↑ Xiaolin Wu: An efficient antialiasing technique. In ACM SIGGRAPH '91 Proceedings: 143-152. ACM Press, New York 1991, ISBN 0-89791-436-8
22. ↑ See e.g. Vincent Boyer, Jean-Jacques Bourdin: Discrete Analysis for Antialiased Lines. Short Presentation, Eurographics 2000 ( PDF, 230 kB )
23. ↑ Nicholas A. Diakopoulos, Peter D. Stephenson: Anti-aliased Lines Using Run masks. Computer Graphics Forum 24, 2 (June 2005): 165-172
24. ^ Turner Whitted: Anti-aliased line drawing using brush extrusion. In ACM SIGGRAPH '83 Proceedings: 151-156. ACM Press, Detroit 1983, ISBN 0-89791-109-1
25. ↑ Vincent Boyer, Jean-Jacques Bourdin: Fast Lines: a Span by Span Method. Computer Graphics Forum 18, 3 (1999): 377–384 ( PDF, 400 kB )
26. ^ Robert F. Sproull: Using program transformations to derive line-drawing algorithms. ACM Transactions on Graphics 1,4 (October 1982): 259-273, ISSN  0730-0301
27. ^ William E. Wright: Parallelization of Bresenham's line and circle algorithms. IEEE Computer Graphics and Applications 10, 5 (September 1990): 60-67
28. ↑ Ivo Považan, Tomáš Hrúz: Parallel Line: a Unified Solution. In WSCG '97 Proceedings: 60-67. University of West Bohemia, Pilsen 1997, ISBN 80-7082306-2 ( online )
29. ↑ Alex T. Pang: Line-drawing algorithms for parallel machines. IEEE Computer Graphics and Applications 10, 5 (September 1990): 54-59
30. ↑ 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
31. ↑ See for example Robert McNamara et al: Prefiltered Antialiased Lines Using Half-Plane Distance Functions. In HWWS 2000 Proceedings: 77-85. ACM Press, New York 2000, ISBN 1-58113-257-3
32. ↑ 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
33. ^ Mitchell A. Harris, Edward M. Reingold: Line drawing, leap years, and Euclid. ACM Computing Surveys 36, 1 (March 2004): 68–80, ISSN  0360-0300 ( PDF, 270 kB ( Memento of the original dated December 16, 2006 in the Internet Archive ) Info: The archive link was inserted automatically and has not yet been checked. Please check the original and archive link according to the instructions and then remove this note. ) 

Web links

• Bresenham's algorithm (NIST Dictionary of Algorithms and Data Structures) - Background to the Bresenham algorithm, with original source code
• Rasterization of lines, circles, ellipses (Uni Magdeburg, Institute for Simulation and Graphics) - Java applet for reproducing the Bresenham algorithm
• Project: Line Statistics (George Mason University Computer Graphics Lab) - Study on the distribution of line lengths and slopes
• The Beauty of Bresenham's Algorithm - A Simple Implementation for Drawing Lines, Circles, Ellipses, and Bézier Curves

This article was added to the list of excellent articles on May 4, 2007 in this version .