Line Drawing Algorithms

Since the raster display screen can be considered as a matrix of discrete elements (pixels), each of which can be highlighted, we cannot directly draw the segment from one point to another. The process of determining pixels that best approximate the specified line segment, is called the decomposition to the raster. For horizontal, vertical and inclined at an angle of 45° segments selection of screen elements is obvious. For any other orientation we select the desired pixels harder, as shown in Fig. 4.1.

Fig.4.1. Decomposition Line Segment to the Raster

Before proceeding to discuss specific line drawing algorithms, it is useful to answer the question, what are the desirable characteristics of the result image and examine the general requirements for these algorithms:

· the segments have to look straight, start and finish at fixed points;

· brightness along the segment should be constant and not depend on the length and inclination;

· drawing should be quick.

As often happens, not all of these criteria can be satisfied. The very nature of the raster display eliminates the generation of absolutely straight lines (except for some special cases), as well as the exact start and end of the segment with the given points. Nevertheless, at sufficiently high resolution display can get a reasonable approximation.

Constant brightness along the entire segment is achieved only during the horizontal, vertical and inclined at an angle of 45° lines. For all other orientations the expansion will lead to uneven screen brightness, as shown in Fig. 4.1. Even for special cases, the brightness depends on the slope: note, for example, that the distance between neighboring pixels for a segment at an angle of 45 ° is greater than for the vertical and horizontal lines. Therefore, the vertical and horizontal segments will look brighter than the oblique ones. For ensuring equal brightness along segments of different lengths and orientation it is required to take the square root, but it will slow down the calculation. A common compromise for this situation is finding the approximate length of the segment, reducing of computation to a minimum, the preferred using of integer arithmetic, and implementation of algorithms in hardware or firmware level.

Поиск по сайту: