Drawing Lines and Curves (Introduction to Computer Graphics Using Java 2D and 3D) Part 1

The previous topic has introduced basic objects and geometric transformations for two-dimensional computer graphics using the principles of vector graphics. As already mentioned in the introduction, drawing geometric objects in a raster graphics framework requires efficient algorithms. This topic illustrates the basic problems and solutions in the context of drawing lines and curves within raster graphics.

Lines and Pixel Graphics

Drawing a line connecting the points (x0,y0) and (x1,y1) within a raster graphics framework seems to be a very simple task. However, it will turn out that a naïve approach can lead to inefficient algorithms or even unacceptable results. For reasons of simplicity, it is assumed that the two points to be connected by the line lie on the pixel raster. This means their coordinates are given by integer values. Without loss of generality it is assumed that the first point is not located right of the second point. This means that x0 < X1 holds. If this is not satisfied, the two points can simply be exchanged for drawing the line.

The naïve approach to drawing the corresponding line on the pixel raster would step incrementally through the x-coordinates starting from x0 and ending at x1 and compute the corresponding y-value for each x-value. Since the y-value will usually not be an integer value, it must be rounded to the closest integer value in order to draw the closest pixel on the raster with the corresponding x- and the rounded y-value. Figure 3.1 describes this strategy in pseudocode.


First of all, it should be noted that this algorithm will fail in the case of a vertical line where x0 = X1 holds, leading to a division by zero error when the slope m of the line is computed. Of course, this special case could easily be treated separately. Although the algorithm will no longer have problems with division by zero it will still fail to draw acceptable lines as can be seen in Fig. 3.2. The upper, horizontal line is as perfect as can be expected in raster graphics. The line below with a slightly negative slope is also drawn correctly in terms of raster graphics, taking into account that—at least at the moment—pixels can either be drawn in full black colour or they can be left white. The ideal line that is approximated by the drawn pixels is also included in the figure for illustration purposes.

tmpc009-65_thumb

Fig. 3.1 Pseudocode for a naïve line drawing algorithm

Fig. 3.2 Lines resulting from the naïve line drawing algorithm

Lines resulting from the naïve line drawing algorithm

However, the line in the lower left with the highly negative slope is not drawn correctly, even in terms of the necessary discretisation for raster graphics. A number of pixels are missing that should be drawn for the raster graphics representation of the line. The problem is caused by the fact that the increment for the x-values is one, but due to the large absolute slope of the line the y -value of the line will change by more than one. This leads to the gaps in the representation of the line in raster graphics, since the increments, or the jumps, in the y-values are larger than one. The same effect will occur for all lines with an absolute slope larger than one. The higher the slope of the line, the larger the gaps in the pixel representation will be.

Exchanging the roles of the x- and the y-axis for drawing lines with an absolute slope greater than one solves the problem. This means that instead of incrementing the x-values by one and computing the corresponding y -value, the y -values are incremented and the corresponding rounded x-values are computed for the line.

This also solves the previously mentioned problem of division by zero for vertical lines. A vertical line with infinite slope becomes a horizontal line with slope zero, when the coordinate axes are exchanged.

Drawing a line on a pixel raster is a task within computer graphics which has to be carried out many times even for a single image. Therefore, efficient line drawing algorithms are needed to speed up drawing images. One could use the naïve line drawing algorithm described in Fig. 3.1 and extend it by the necessary exchange of the coordinate axes for lines with absolute slope larger than one. But there are still two choices in the last line of the pseudocode. The first formula requires only a single addition to compute the y-value of the line for the next step. The second one needs two additions1 and one multiplication. A multiplication demands more computation time than an addition. Therefore, the first version for the computation of the y-value should be preferred. The only disadvantage of this formula is the danger of accumulated roundoff errors. However, this can be neglected, since the number of iterations in the loop is limited by the number of pixels on the x- and the y-axis. So even in the case of a larger high-resolution monitor, the loop cannot contain more than a few thousand iterations. Because rounding to an integer number must be carried out in the end anyway, even the accumulated roundoff error can be neglected.

The Midpoint Algorithm for Lines

Drawing lines can be carried out in a way much faster than the naïve line drawing algorithm from the previous section. The naïve line drawing algorithm is based on floating point arithmetic for determining rounded integer pixel coordinates. Since integer arithmetic is much faster than floating point arithmetic, a considerable speedup of the line drawing algorithm could be achieved, if floating point arithmetic could be avoided completely. A line drawing algorithm relying only on integer arithmetic was introduced by J.E. Bresenham [1]. This algorithm will be explained in the following.

When examining the naïve line drawing algorithm in detail, it was already noted that it should be ensured that the line to be drawn has an absolute slope of at most one. For a line with absolute slope greater than one, the roles of the coordinate axes are exchanged for drawing, leading to a line with absolute slope less than one in the modified coordinate system. So in any case, before starting to compute the actual pixels representing a line, the first step is to decide which coordinate axis should be considered as the x-axis in order to ensure that the line has an absolute slope of at most one. Therefore, it is assumed for the following considerations that a line with absolute slope less than one should be drawn. The considerations are even restricted to the case that the slope is between 0 and 1. For lines with a slope between 0 and -1 a corresponding algorithm can be developed analogously.

The two candidates for the next pixel for the line drawing algorithm

Fig. 3.3 The two candidates for the next pixel for the line drawing algorithm

If a line with slope between 0 and 1 is drawn pixel by pixel and the last pixel which was drawn is located at (xp,yp), then there are only two choices for the next pixel. It is obvious that the x-coordinate of the next pixel is xp+1 = xp + 1. Since the line has a nonnegative slope, the next y-value cannot be smaller than the previous one. On the other hand, the slope of the line is bounded by one so that it cannot jump over two pixels in the y-direction, when the x-coordinate is incremented by one. Altogether, this means that the pixel to be drawn after the pixel (xp,yp) can only be one of the two pixels (xp+i,yp+i) = (xp + 1,yp) or (xp+i,yp+i) = (xp + 1,yp + 1). Therefore, in each step of the line drawing algorithm there are only two choices for the pixel to be drawn.

Figure 3.3 illustrates the situation. The right (“eastern”) neighbouring pixel of (xp,yp) is marked by E, the neighbouring pixel to the upper right (“north-eastern”) by NE.

The pixel to be drawn is the one closer to the point Q on the ideal line with x-coordinate xp + 1. In order to decide whether the pixel E or NE is the correct choice, the midpoint M between these two pixels is considered. If M lies below the ideal line, the upper pixel must be drawn, i.e., NE is the correct choice. If M is above the line, E should be chosen. In case M lies exactly on the line, one can choose either of the two pixels. The decision for pixel NE corresponds to rounding 0.5 to one, the decision for E corresponds to rounding 0.5 to zero. It is not important which of the two alternatives is chosen. But once a choice is made, one should always stick to the same alternative, when the midpoint lies exactly on the line.

The above considerations reduce the choice for the pixel to be drawn in each step of a line drawing algorithm to two alternatives. In the following, this reduction to two alternatives will be further exploited to avoid floating point arithmetic and use only integer computations in order to decide whether the midpoint M is above or below the ideal line, inducing which pixel should be drawn.

A line considered as a function in the mathematical sense is usually specified in the form

tmpc009-68_thumb

This notation reflects the intuition of a computational procedure. For any given x-value the corresponding unique y-value can be calculated using this simple equation. In the context of computer graphics, this representation is not always the most suitable one. On the one hand, vertical lines cannot be represented in the notation of (3.1). On the other hand, this notation is not very useful to follow the considerations above that involve the location of the midpoint between two pixels with respect to the line. Of course, it would be possible to calculate the corresponding y-value on the line by (3.1) and then compare it with the y-value of the midpoint. However, the comparison then becomes superfluous, since there is no need to consider the midpoint anymore, because the pixel to be drawn can be obtained directly by rounding the computed y-value. Therefore, another representation of lines than (3.1) is preferred.

Any function y = f(x), especially a simple function like a line, can be rewritten in implicit form as

tmpc009-69_thumb

The implicit form does no longer consider the function in terms of an explicit computational procedure, but as a definition for the graph of the function. The graph of a function consists of all points belonging to the set

tmpc009-70_thumb

This is the set of pairs (x, y) that fulfil the implicit equation (3.2) defining the function. A line can be written in implicit representation in the form

tmpc009-71_thumb

For example, the line y = m · x + b can be rewritten as

tmpc009-72_thumb

This representation is much better suited for the purpose of determining whether a point, especially the midpoint M that will be considered here, is above, below or on a given line. Inserting the point (xM,yM) into (3.4) leads to three possible outcomes, assuming m > 0.

•    F(xM,yM) = 0: The point (xM,yM) is on the considered line.

•    F(xm,ym) > 0: If    the point would be on the line, the corresponding value yM  had to be greater. In other words, yM is too small, so that the point (xM,yM) lies below the line.

•    F(xm,ym) < 0: In  this case, if the point would be on    the line, the corresponding value yM had    to be smaller. Therefore, the point (xM,yM) lies above the line.

This means that it is sufficient to know the sign of F(xM,yM) in order to decide where the point (xM,yM) lies with respect to the line defined by the implicit equation (3.4). Making use of this implicit equation it is now possible to avoid floating point arithmetic for the determination of the location of the midpoint. Taking into account that the connecting line between the given pixels (x0,y0) and (x\,y\) should be drawn, (3.4) can be reformulated, so that only integer operations are needed for the computation. The line through the points (x0,y0) and (x\,y\) can be written in the form

tmpc009-73_thumb

Solving for y and defining the integer values2 dx = x\ — x0 and dy = yi – y0, leads to

tmpc009-74_thumb

This gives the implicit form

tmpc009-75_thumb

Multiplication of this equation by the factor dx yields the final implicit form

tmpc009-76_thumb

where

tmpc009-77_thumb

The aim of these considerations and calculations was to restrict the computations for drawing a line to integer arithmetic. Based on the underlying assumption that the line has a slope between zero and one, it could be concluded that for the pixel to be drawn in each step there are only two choices. In order to decide which of the two pixels is the correct one, the location of the line with respect to the midpoint M between the two pixels is considered as illustrated in Fig. 3.3 on page 46. For this purpose, the representation of the line in implicit form is very useful. Inserting the midpoint into the implicit equation, the resulting sign indicates the location of the midpoint with respect to the line. The midpoint M = (xM,yM) lies on the raster in the x-direction and in the middle between two raster points in the y-direction. Therefore, its x-coordinate xM is an integer value, whereas the y-coordinate yM has the form

tmpc009-78_thumb

where the value yM) is also an integer value.

The new midpoint depending on whether the previously drawn pixel was E or NE

Fig. 3.4 The new midpoint depending on whether the previously drawn pixel was E or NE

Using the implicit form (3.5) for the line and inserting the value yM, floating point operations are still required. However, multiplying (3.5) by the factor 2, the implicit form for the considered line becomes

tmpc009-80_thumb

When the midpoint M = (xM,yM) is inserted into this equation, the computations can be reduced to integer arithmetic. Instead of inserting the value yM with 0.5 as the value after the decimal point directly, the term 2 · yM can be replaced by the integer value 2 · y(°) + 1.

In this way, the computations for drawing lines can be reduced completely to integer arithmetic. Nevertheless, (3.6) is not used directly for drawing lines since it still contains multiplications that are more expensive in terms of computational costs than additions or subtractions. The multiplications can be avoided by an incremental computation scheme. Instead of calculating the value (3.6) for the midpoint M in each step directly, only the value for the first midpoint is computed and afterwards the change of (3.6) in each step is added to the previously computed value.

Instead of (3.6) the form (3.5) is used for the derivation of the incremental computation scheme. In each step, the decision variable

tmpc009-81_thumb

determines whether the pixel above or below the midpoint M = (xM,yM) should be drawn. The upper pixel NE must be chosen for d > 0, the lower pixel E in the case of d < 0. How does d change in each step, when going from one pixel to the next? Assuming that the pixel (xp,yp) has been drawn correctly in terms of rounding the y-value, how does d change, when the pixel (xp+\,yp+\) has been drawn and the next midpoint is inserted to determine the pixel (xp+2 ,yp+2)? Two cases must be distinguished here, which are illustrated in Fig. 3.4.

Case 1: E, i.e., (xp+\,yp+\) = (xp + 1,yp) was the pixel to be drawn after (xp,yp). This case corresponds to the left situation in Fig. 3.4. Therefore, the midpoint Mnew to be considered for drawing the pixel (xp+2,yp+2) has the coordinates (xp + 2,yp + 2). Inserting this point into (3.5) yields the following value for the decision variable d :

tmpc009-82_thumb

In the previous step for determining the pixel (xp+1,yp+1), the midpoint (xp + 1,yp + 1 ) had to be inserted into (3.5), so that the decision variable took the value

tmpc009-83_thumb

Thus, the change of the decision variable is in this case given by

tmpc009-84_thumb

Case 2: NE, i.e., (xp+1,yp+1) = (xp + 1,yp + 1) was the pixel to be drawn after (xp,yp). This case corresponds to the right situation in Fig. 3.4. So here the midpoint Mnew = (xp + 2,yp + |) must be considered for finding the pixel (xp+2,yp+2). Thus, the value for the decision variable is

tmpc009-85_thumb

The previous value of the decision variable d is the same as in the first case of the pixel E, resulting in the change of the decision variable given by

tmpc009-86_thumb

Combining the two cases together, the change of the decision variable is

tmpc009-87_thumb

This means

tmpc009-88_thumb

Δ is always an integer value, so that the decision variable d will only be changed by integer values.

In order to be able to compute the value of the decision variable d in each step, in addition to its change the initial value of d is also needed. The initial value is obtained by inserting the first midpoint into (3.5). The first pixel to be drawn for the line has the coordinates (x0,y0). Therefore, the first midpoint to be considered is (x0 + 1,y0 + 1 ), so that the initial value of the decision variable becomes

tmpc009-89_thumb

The value F(x0,y0) is zero since the initial point (x0,y0) lies by definition on the line to be drawn.

Unfortunately, the initial value dinit is not an integer value, except when dx happens to be even. Since the change dx of d is always integer-valued, this problem can be avoided by considering the new decision variable D = 2 · d. This corresponds to replacing the implicit form (3.5) of the line to be drawn by the implicit form

tmpc009-90_thumb

For determining the pixel to be drawn, it does not matter whether the decision variable d or D = 2 · d is used, since only the sign of D is relevant for the choice of the pixel.

Putting everything together leads to the following equations for initialising and updating the decision variable D:

tmpc009-91_thumb

The decision variable can only take integer values. For the initialisation of D one multiplication and one subtraction is required. The two values for Δ should also be computed only once in the beginning. This needs two more multiplications and one subtraction. The iterative update of Δ in each step can then be accomplished by a single addition.

The problem of drawing a line connecting the points (2, 3) and (10, 6) shall illustrate the principle of this algorithm, also called midpoint algorithm or named after its inventor Bresenham algorithm. The resulting values for the initialisation and for the decision variable are given step by step in Table 3.1.

Table 3.1 Steps required for the calculation of the line connecting the points (2, 3) and (10, 6) using the midpoint algorithm

dx

=

10 — 2

=

8

dy

=

6 — 3

=

3

Δε

=

2 · dy

=

6

Δνε

=

2 · (dy — dx)

=

— 10

Dinit

=

2 · dy — dx

=

—2 (E)

Dinit+1

=

tmpc009-92

=

4 (NE)

Dinit+2

=

tmpc009-93

=

—6 (E)

Dinit+3

=

tmpc009-94

=

0 (E?)

Dinit+4

=

tmpc009-95

=

6 (NE)

Dinit+5

=

tmpc009-96

=

—4 (E)

Dinit+6

=

tmpc009-97

=

2 (NE)

Dinit+7

=

tmpc009-98

=

—8 (E)

Dinit+8

=

tmpc009-99

=

—2

Fig. 3.5 Drawing a line with the Bresenham algorithm

Drawing a line with the Bresenham algorithm

After setting the start pixel (2, 3), the initial decision variable Dm results in the negative value of -2, so that the next pixel to be drawn is the one "east” or right of the start pixel. The decision variable must be changed by ΔΕ = 6. This makes the new decision variable positive, meaning that the next pixel to be drawn should be "north-east” or right above the previous pixel and that the decision variable should be changed by the value ΔνΕ . This results in a zero-value for the decision variable in the next step. In other words, the line passes exactly through the midpoint between the two candidates for the next pixel to be drawn. Here, the convention is assumed to prefer the "eastern” pixel in such cases. The remaining values can be calculated analogously. Figure 3.5 shows the resulting pixel line.

The precondition for the application of the midpoint algorithm is that the line to be drawn has a slope between 0 and 1. It was already mentioned that the roles of the x – and the y-axis can be exchanged for drawing lines with an absolute slope greater than 1. In this case, the y-values are incremented step by step and the decision variable D is used for the computation of the corresponding x -value. By exchanging the roles of the coordinate axes if necessary, it can always be guaranteed that the slope of the line to be drawn is between — 1 and 1. The above-described midpoint algorithm can only take care of lines with a slope between 0 and 1. In a completely analogous way, an algorithm for lines with a slope between — 1 and 0 can be derived.

Instead of the “north-eastern” pixel, the “south-eastern” pixel has to be considered for the midpoint algorithm for lines with slope between —1 and 0.

A crucial prerequisite for the midpoint algorithm is the assumption that the line to be drawn connects two pixels. This restricts the endpoints of the line to integer coordinates. For a line that was modelled in a vector graphics framework, it is not guaranteed at all that the endpoints fulfil this requirement. In this case, the line connecting the endpoints with rounded coordinates is drawn. This might lead to a small deviation of the pixel line obtained from rounding the y-coordinates compared to the ideal line. However, the deviation is at most one pixel and can therefore be tolerated for the higher computational efficiency.

Next post:

Previous post: