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

Structural Algorithms

The midpoint algorithm requires in addition to the computations for the initialisation n operations to draw a line of n pixels, so that its computational complexity is linear. Structural algorithms try to reduce this complexity further by analysing repeated patterns that occur when a line is drawn on a pixel raster. Figure 3.6 illustrates such a repeated pattern with an overall length of five pixels. In order to better identify the repeated pattern, the pixels within one pattern are marked differently. The basic pattern in Fig. 3.6 consists of a first pixel (filled circle), two neighbouring pixels right above the first pixel (simple circles), followed by two other neighbouring pixels (double circles) right above the previous ones. Let D denote a diagonal step (drawing a “north-eastern” pixel) and H a horizontal step (drawing an “eastern” pixel). Then drawing the pixel line can be described by a repetition of the basic pattern DHDHD.

If the line in Fig. 3.5 on page 52 would not end at the point (10, 6), the corresponding pattern HDHHDHDHD would be repeated again. This can also be seen from the calculations of the midpoint algorithm in Table 3.1 on page 52. The initial value Dinit of the decision variable is equal to the last value Dinit+8 in Table 3.1. Continuing the calculations of the midpoint algorithm would therefore lead to the same results as shown in the table.

Since it was assumed that the endpoints (x0,y0) and (x\,y\) of the line to be drawn lie on the pixel raster, the numbers x0, y0, xi, yi must be integers and therefore also the values dx = x1 — x0 and dy = y1 — y0. The line has a rational slope of dx. For drawing the line, the y-values

with a rational constant b and integer values x have to be rounded, no matter whether this calculation is carried out explicitly as in the naïve line drawing algorithm or implicitly as in the midpoint algorithm. It is obvious that only a finite number of different remainders is possible for the computation of the y-values (3.9). Therefore, any pixel line connecting two endpoints on the pixel raster must be based on a repeated pattern, although the pattern might be quite long. In the worst case the repetition of the pattern would only start again when the final endpoint of the line is reached.

Fig. 3.6 A repeated pixel pattern for drawing a line on pixel raster

Structural algorithms make use of this fact for drawing lines and determine the underlying basic pattern that defines the line. This can lead to a reduction for line drawing to a logarithmic complexity, but with the price of more complex integer operations than simple additions.

For the same reasons as in the context of the midpoint algorithm, the considerations for structural algorithms will also be restricted to lines with a slope between zero and one. A structural algorithm constructs the repeated pattern for drawing the pixels as a sequence of horizontal (H) and diagonal steps (D), based on the following principles.

Given the two endpoints (x0 ,y0 ) and (x1 ,y1 ) of a line with slope between zero and one, the values dx = x1 — x0 and dy = y1 — y0 are computed. In addition to the initial pixel dx more pixels have to be drawn. For these dx pixels dy diagonal steps are required. The remaining (dx — dy) must be horizontal steps. The problem to be solved consists of finding the correct order of the diagonal and horizontal steps. The sequence3 Hdx—dy Ddy, containing the correct number of horizontal and diagonal steps but probably in the wrong order, is used as a first approximation for the drawing pattern of the line. A suitable permutation of this initial sequence will yield the correct sequence for drawing the line.

Bronsy algorithm constructs the correct permutation of the initial sequence Hdx-dy Ddy in the following way [3, 4]:

•    If dx and dy (and therefore also (dx — dy)) have a common divisor greater than one, i.e., g = gcd(dx, dy) > 1, then the pixel line can be drawn by g repetitions of a sequence of length dx/g.

•    Therefore, it can be assumed without loss of generality that dx and dy have no common divisor.

•    Let P and Q be two words (sequences) over the alphabet {D, H}.

• From a starting sequence Pp Qq with frequencies p and q having no common divisor and assuming without loss of generality 1 < q < p, the integer division

leads to the permutated sequence

• Apply the same procedure in a recursive manner to the subsequences of length r and (q — r), respectively, until r = 1 or (q — r) = 1 holds.

As an example how to apply this procedure, drawing a line from the point (x0,y0) = (0,0) to the point (x1,y1) = (82, 34) is considered. Obviously, dx = 82, dy = 34 and therefore gcd(dx, dy) = 2 holds. The line has a slope of dy/dx = 17/41. Starting from the initial pixel (x0,y0) that is located on the ideal line, the next pixel on the ideal line is reached after 41 pixels. Therefore, it is sufficient to construct a sequence for drawing the first half of the line up to the pixel (41,17) and to repeat this sequence for drawing the remaining pixels. Therefore, the values dx = dx/2 = 41 and dy = dy/2 = 17 are considered. So the initial sequence is H24D17 and the corresponding integer division with p = 24 and q = 17 yields 24 = 1 · 17 + 7. This leads to the sequence (HD)10(H2D)7 with p = 10 and q = 7. Integer division for this sequence produces 10 = 1 · 7 + 3, resulting in the sequence (HDH2D)4((HD)2H2D)3. Here p = 4 and q = 3 holds and the final integer division yields 4 = 1 · 3 + 1. The corrected sequence of intermediate steps is therefore

This sequence has to be applied twice for drawing the pixel line connecting the points (0, 0) and (82, 34).

Pixel Densities and Line Styles

Drawing lines in a raster graphics framework causes various undesired effects. The pixel grid leads to jaggies or staircasing instead of straight lines. This so-called aliasing effect and how to avoid it will be discussed in Sect. 3.8 in more detail. So far it was assumed that the width of a line should be one pixel, resulting in very thin lines. Drawing lines will be the topic of Sect. 3.9. The density of thin lines where one pixel is set per step in the x – or y-direction depends on the slope of the line. Figure 3.7 illustrates this effect. The highest pixel density is achieved for horizontal lines. An increasing slope leads to thinner lines and the lowest density is reached at a slope of one. Since lines with a larger absolute slope than one are drawn by exchanging the roles of the coordinate axes, the pixel density increases again for lines with a slope greater than one. The same applies to lines with negative slopes.

Fig. 3.7 Different pixel densities depending on the slope of a line

Table 3.2 Pixel densities for lines with different slopes

m	Slope	Length of the line	Pixel density
0	0	n	1
n	1
m

Analysing the example of a line connecting the points (0,0) and (n, m) with m < n will provide a better understanding of the influence of the slope of a line on its pixel density. No matter how m, i.e., the slope, is chosen, the line will always contain n pixels, not counting the first pixel at (0, 0). The pixel densities depending on the choice of m are listed in Table 3.2. The last line of the table contains the general formula for arbitrary values m < n.

The horizontal line, having a length of n and containing n pixels, has the highest pixel density. The pixel density of a diagonal line with slope one reduces to 1 /V2 « 0.7, roughly 70% of the density of a horizontal line. If not only black and white, but also grey pixels with different intensities can be drawn, one can try to compensate this effect by using the maximum intensity only for diagonal lines and drawing horizontal and vertical lines with only 70% intensity of the diagonal lines. However, this compensation strategy will reduce the overall intensity, since only lines with the lowest pixel density obtain full intensity. The intensity for all other lines will be reduced, so that they look more palish.

The slope of a line not only can influence how thick it occurs on a pixel raster, but it can also have similar effects when lines are drawn with different line styles. A line style determines the way a line is drawn. So far it was always assumed that the two endpoints of a line had to be connected by a solid line. This corresponds to the default or standard line style. Other common line styles include dotted or dashed lines.

Fig. 3.8 Different line styles

Bitmasks offer a simple way for defining different line styles. A bitmask is a finite sequence of zeros and ones. The repeated bitmask is mapped to the pixels of the line. Only those pixels are drawn where a one occurs in the bitmask. Pixels where the bitmask has a zero are skipped.

Figure 3.8 illustrates how bitmasks determine which pixels have to be drawn and how the resulting line looks, when a specific bitmask is chosen for a line style. For each line, the underlying bitmask is shown once in the beginning in slightly enlarged boldface digits, afterwards the repetitions of the bitmask are shown in the normal font. Below the bitmask the corresponding sequence of pixels is drawn in a magnified manner. Below the pixels it is illustrated how the corresponding line style should look. The first bitmask for drawing a solid line consists of a single 1. For a dashed line one could use, for instance, the bitmask 111000 with three pixels drawn and three pixels skipped, alternatingly.

Since a bitmask determines the pixels to be drawn based on the way the line is traversed, i.e., the corresponding coordinate axis, similar effects occur as they have already been discussed for pixel densities in connection with the slope of the line. For instance, for a dashed line the length of the dashes based on a bitmask depends on the slope of the line. If the bitmask 1"0" is used, i.e., n pixels are drawn and n pixels are skipped alternatingly, the length of a single dash varies with the slope of the line. For vertical and horizontal lines the length of a single dash is n, whereas a line with a slope of 45° will have dashes with a length of n · VÎ. This means that diagonal lines have dashes that are 40% longer than those of horizontal or vertical lines. Figure 3.9 illustrates how the slope of a line influences the length of the dashes, when a simple bitmask is used.

Fig. 3.9 Different dash lengths for the same bitmask

Different Line Styles with Java 2D

Java 2D provides the class BasicStroke not only for defining different line styles, but also for controlling the thickness of lines as well as the shape of line endings and joins between lines in a polyline. The default thickness of a line is 1.0 pixel in Java 2D and since such lines tend to be very thin on high-resolution output devices, it is recommended to choose a larger value for the line thickness. This can be achieved in the following way:

In this case the chosen line thickness is specified as 3.0 pixels. For defining dash patterns, the constructor

can be used. The float-value thickness specifies the thickness of the line to be drawn. The three following parameters determine how the endings of lines should look and how joins in polylines should be drawn. The corresponding effects and choices will be explained in Sect. 3.9. The float-array dashPattern defines the desired dash pattern. For drawing a dashed line, whose dashes are 20 pixels long with gaps in between with a length of 10 pixels, the array dashPattern must have two entries, the corresponding values 20 and 10.

float[] dashPattern = new float[]{20,10};

The float-value dashPhase determines at which position in the dash pattern drawing should begin.

Figure 3.10 shows a selection of lines for which different dash patterns were defined. For the left line, only the simple constructor new BasicStroke(3.0f) was used to make it a little bit thicker. The three rightmost lines were drawn with the above-given dash pattern dashPattern. The two rightmost lines have an offset of dashPhase=0, whereas the offset was set to 10 for the line in the middle. Comparing the two rightmost lines shows that Java 2D does not work with a simple bitmask which is applied to pixels. Java 2D computes the dash pattern in such a way that the dash length is kept independent of the slope of the line. 

Fig. 3.10 Examples for different line styles

The second line to the left is based on a dashPattern with the values 4, 5, 8, 5, 12, 5, 16, 5, 20, 5, so that the gaps between the dashes have a constant length of 5, whereas the lengths of the dashes increase from 4 to 20.

Figure 3.10 was generated by the program StrokingExample.java.

Line Clipping

When objects of a more complex “world” are modelled in terms of vector graphics, it is necessary to specify which section of the world—the scene—is chosen for display. Then it must be decided for each object whether it belongs completely or at least partially to the section of the world to be displayed. The task of deciding whether objects belong to the scene to be displayed or whether they can be neglected for the specific scene is called clipping. The part of the world to be displayed is the clipping area or clipping region. This section focusses on specific algorithms for clipping lines.

In the case of line clipping, four different cases, as illustrated in Fig. 3.11, are possible.

•    Both endpoints of the line lie within the clipping area. This means the line is included completely in the clipping area, so that the whole line must be drawn.

•    One endpoint of the line lies within, the other outside the clipping area. It is necessary to determine the intersection point of the line with the bounding rectangle of the clipping area. Only a part of the line should be drawn.

•    Both endpoints are located outside the clipping area and the line does not intersect the clipping area. In this case, the line lies completely outside the clipping area and can be neglected for the scene.

•    Both endpoints are located outside the clipping area and the line intersects the clipping area. The two intersection points of the line with the clipping area must be determined. Only the part of the line between these two intersection points should be drawn.

A straightforward way to implement line clipping would be to compute all intersection points of the line with the bounding rectangle of the clipping area. It should be noted that this problem is more difficult than determining the intersection points of infinite lines.

Fig. 3.11 Different cases for line clipping

The line to be drawn has limited extension bounded by its two endpoints. For the clipping procedure it is important to know whether an intersection point lies between or outside the two endpoints of the line segment. The same applies to the four edges of the bounding rectangle of the clipping area. The edges have also limited extension. Intersection points outside the edges or outside the endpoints of the considered line have no influence on drawing the line. For the computation of the intersection points it is useful to represent the line segment between the two endpoints (x0,y0) and (x\,y\) as a convex combination of these two points.

Let (xmin,ymin) and (xmax,ymax) be the lower left and the upper right corner, respectively, of the rectangle defining the clipping area. As an example for the necessary computations for clipping, the calculation of a possible intersection point of the line with the lower edge of the clipping rectangle is described in the following. For determining a possible intersection point the formulae for the two lines, the line segment (3.10) and the lower edge, must be equal:

Two equations for t1 and t2 result from considering the x – and y-component of (3.11). If this system of two linear equations does not have a unique solution, the two lines are parallel, so that the lower edge of the clipping rectangle would not be important for clipping the line. If the system of equations has a unique solution, the following cases must be distinguished.

• t1 < 0 and t2 < 0: The intersection point lies not between the endpoints of the line segment and lies before xmin.

•    0 < ti < 1 and t2 < 0: The line segment intersects the extension of the lower edge before xmin.

• t1 > 1 and t2 < 0: The intersection point lies not between the endpoints of the line segment and lies before xmin.

Fig. 3.12 Bit code for Cohen-Sutherland clipping

• t1 < 0 and 0 < t2 < 1: The intersection point of the line with the lower edge lies before (x0 ,y0).

•    0 < t1 < 1 and 0 < t2 < 1: The line segment intersects the lower edge.

•    t1 > 1 and 0 < t2 < 1: The intersection point of the line with the lower edge lies behind (x1 ,y1).

• t1 < 0 and t2 > 1: The intersection point lies not between the endpoints of the line segment and lies behind xmax.

•    0 < t1 < 1 and t2 > 1: The line segment intersects the extension of the lower edge behind xmax.

• t1 > 1 and t2 > 1: The intersection point lies not between the endpoints of the line segment and lies behind xmax.

Similar considerations can be carried out for the other edges of the clipping rectangle. Combining the results for the single edges will provide the necessary information as to which part of the line should be drawn.

The Cohen-Sutherland line clipping algorithm (see for instance [7]) tries to avoid the complex computations of intersection points for lines. To simplify the calculations, the plane is divided into nine areas described by a 4-bit code. The bit codeis    assigned    to    the    point according to the following rules:

Figure 3.12 shows the nine areas and their corresponding bit codes.

Clipping should be applied to a line connecting the two endpoints P and Q. The corresponding bit code b(P) and b(Q) of P and Q, respectively, can be determined by simple comparisons of numbers. For drawing the correct part of the line, three cases must be distinguished. The part of the line that has to be drawn is determined in an iterative procedure. The first two cases terminate the calculations. In the third case, the line segment is further subdivided.

Case 1: The bitwise logical disjunction of the bit codes of the two points yields b(P) V b(Q) = 0000.  

Then both points lie within the clipping rectangle, the whole line PQ must be drawn, and no further clipping is needed for this line.

Case 2: The bitwise logical conjunction of the bit codes of the two points yields b(P) λ b(Q) = 0000.

This means that the two bit codes must share the entry one in at least one position. If the common one of the two bit codes is at the first position, then the whole line is left of the clipping rectangle. If the common one is at the second position, the whole line lies right of the clipping rectangle. Analogously, a common one at the third or fourth position indicates that the line lies completely below or completely above the clipping rectangle. In all these cases no further clipping is required for the line.

Case 3: Neither the first nor the second case apply.

Then b(P) = 0000 and b(Q) = 0000 must be true.

Without loss of generality, it can be assumed that b(P) = 0000. Otherwise the points P and Q are simply exchanged. Note that b(P) = 0000 = b(Q) is impossible, since this would lead to case 1. Since the bit code of P must contain a value one, P cannot lie within the clipping rectangle. The bit code of P cannot contain a one at more than two positions. From the definition of the bit code it is clear that it is impossible to have a one simultaneously at the first two positions, since the point cannot lie left and right of the clipping rectangle at the same time. The same applies to the last position. Now it is necessary to compute possible intersection points of the line with edges of the clipping rectangle. Starting from point P the line can enter the clipping rectangle only via an edge that is associated with a one in the bit code of P .If the first component of the bit code is one, this means that P lies left of the clipping rectangle and the line might enter the clipping rectangle via its left edge. The same holds for the other edges and the corresponding position of the one in the bitcode. So there can be one or at most two possible edges by which the line might enter the clipping area.

If there is only one possible edge as a candidate for the intersection with the line, the intersection point of the line with the prolongation of the corresponding edge is determined and the point P is replaced by this intersection point. If there are two candidate edges, the intersection of the line with the prolongation of one of the edges is determined and the point P is replaced by this intersection point. In both cases, the algorithm starts again with the updated point P. In this way, the line is shortened and the shortened line is treated in the same way as the original one until one of the first two cases of the algorithm applies.

Figure 3.13 illustrates how the Cohen-Sutherland line clipping algorithm works. The line PQ is reduced stepwise to the lines S1Q, S2Q, S2S3 and finally to S2S4. The last line lies completely within the clipping rectangle and can be drawn immediately.

Fig. 3.13 Cohen-Sutherland line clipping

Fig. 3.14 Cyrus-Beck line clipping

The Cyrus-Beck line clipping algorithm [5] uses normals of the edges of the clipping rectangle to determine the part of the line which should be drawn. The line is represented in a parametric form in terms of a convex combination of its endpoints p0 and P1 as introduced in (3.10) on page 60.

For each of the four edges of the clipping rectangle, a normal vector is determined in such way that it points outwards of the rectangle. The corresponding normal vector for the left edge is therefore (—1, 0)T, for the lower edge it is (0, —1)T, and for the upper and the right edge the normal vectors (0,1)T and (1,0)T are obtained, respectively.

Figure 3.14 illustrates the principle of the Cyrus-Beck line clipping algorithm for the left edge of the clipping rectangle. In addition to the normal vector n a point on the corresponding edge is also chosen. For the left edge this point is denoted by pE in Fig. 3.14.

The vector connecting the point pE with a point on the line defined by the points p0 and p1 can be written in the following form:

Fig. 3.15 Potential intersection points with the clipping rectangle

For the intersection point of the line with the corresponding edge of the clipping rectangle

must hold. This equation requires that the vector connecting pE with the intersection point must be orthogonal to the normal vector nE, since the connection vector must be parallel to the left edge of the clipping rectangle. Solving for t yields

The denominator can only be zero, if either p0 = p1 holds, meaning that the line to be clipped consists only of a single point, or if the line is orthogonal to the normal vector nE . The latter case implies that the line is parallel to the edge E, so that no intersection point with this edge has to be computed.

The value t is determined for each of the four edges of the clipping rectangle in order to determine whether the line to be drawn intersects the corresponding edge. A value of t outside the interval [0,1] indicates that the line does not intersect the corresponding edge of the clipping rectangle. The dot products in the numerator and the denominator of (3.12) are simplified to choosing the x- or the y-component of (p0 — pE) and (P1 — p0) and a possible change of the sign since the normal vectors nE are all of the form ±(1,0)T or ±(0,1)T.

A t-value between zero and one in (3.12) means that the line to be drawn either intersects the corresponding edge itself or the prolongation of the edge. Therefore, only those intersection points for t-values between zero and one are potential points where the line enters or leaves the clipping rectangle. These points are marked as possible entering (PE) and possible leaving points (PL). All of them lie between the endpoints of the line, but not necessarily on an edge of the clipping rectangle. Figure 3.15 illustrates the situation.

The angle between the line pôpT and the normal vector n of the corresponding edge of the clipping rectangle determines whether a point should be marked PE or PL.

• If the angle is larger than 90°, the intersection point should be marked PE.

Fig. 3.16 Finding the pixel where a line enters the clipping rectangle

• If the angle is less than 90°, the intersection point should be marked PL.

For the decision PE or PL it is sufficient to determine the sign of the dot product

In the case of PE, the sign will be negative. PA will lead to a positive sign. Since only one of the components of the normal vector n is nonzero, the sign of the dot product is obtained by considering only the signs of the corresponding component of the vector p1 — p0 and the nonzero component of the normal vector.

In order to determine which part of the line lies within the clipping rectangle, the largest value tE for PE-points and the smallest value tL for possible PL-points must be computed. If tE < tL holds, then the part of the line between the points p0 + (P1 — p0)tE and p0 + (P1 — p0)tL must be drawn. In case of tE > tL the line lies out of the clipping rectangle and nothing has to be drawn.

Apart from determining which part of a line should be drawn for a given clipping area, computing the first pixel of the line inside the clipping rectangle is another problem. In general, it is not sufficient to calculate the rounded coordinates of the intersection point of the line with the corresponding edge of the clipping rectangle where the line enters the clipping area. Figure 3.16 shows an example where this procedure would lead to an incorrect result. The left or "eastern” edge of the clipping rectangle is marked with "left,” the lower or "southern” edge with "lower.” In this example, the first pixel would be missed if rounding the coordinates of the intersection point of the line with the lower edge was applied. For lines with a smaller slope, the procedure could miss many more pixels. Therefore, instead of the intersection of the line with the edge, its intersection point with the edge shifted 0.5 unit downwards is computed. The rounded x-value of this intersection point gives the correct position where drawing of the line should start. The other edges are treated analogously.