Next: 3.4.2 Other Line Segment Up: 3.4 Line Segments Previous: 3.4 Line Segments

## 3.4.1 Basic Line Segment Rasterization

Line segment rasterization begins by characterizing the segment as either x-major or y-major. x-major line segments have slope in the closed interval ; all other line segments are y-major (slope is determined by the segment's endpoints). We shall specify rasterization only for x-major segments except in cases where the modifications for y-major segments are not self-evident.

Ideally, the GL uses a ``diamond-exit'' rule to determine those fragments that are produced by rasterizing a line segment. For each fragment f with center at window coordinates and , define a diamond-shaped region that is the intersection of four half planes:

Essentially, a line segment starting at and ending at produces those fragments f for which the segment intersects , except if is contained in . See Figure 3.4.

To avoid difficulties when an endpoint lies on a boundary of we (in principle) perturb the supplied endpoints by a tiny amount. Let and have window coordinates and , respectively. Obtain the perturbed endpoints given by and given by . Rasterizing the line segment starting at and ending at produces those fragments f for which the segment starting at and ending on intersects , except if is contained in . is chosen to be so small that rasterizing the line segment produces the same fragments when is substituted for for any .

When and lie on fragment centers, this characterization of fragments reduces to Bresenham's algorithm with one modification: lines produced in this description are ``half-open,'' meaning that the final fragment (corresponding to ) is not drawn. This means that when rasterizing a series of connected line segments, shared endpoints will be produced only once rather than twice (as would occur with Bresenham's algorithm).

Figure 3.4: Visualization of Bresenham's algorithm. A portion of a line segment is shown. A diamond shaped region of height 1 is placed around each fragment center; those regions that the line segment exits cause rasterization to produce corresponding fragments.

Because the initial and final conditions of the diamond-exit rule may be difficult to implement, other line segment rasterization algorithms are allowed, subject to the following rules:

1. The coordinates of a fragment produced by the algorithm may not deviate by more than one unit in either x or y window coordinates from a corresponding fragment produced by the diamond-exit rule.
2. The total number of fragments produced by the algorithm may differ from that produced by the diamond-exit rule by no more than one.
3. For an x-major line, no two fragments may be produced that lie in the same window-coordinate column (for a y-major line, no two fragments may appear in the same row).
4. If two line segments share a common endpoint, and both segments are either x-major (both left-to-right or both right-to-left) or y-major (both bottom-to-top or both top-to-bottom), then rasterizing both segments may not produce duplicate fragments, nor may any fragments be omitted so as to interrupt continuity of the connected segments.

Next we must specify how the data associated with each rasterized fragment are obtained. Let the window coordinates of a produced fragment center be given by and let and . Set

(Note that t=0 at and t=1 at .) The value of an associated datum f for the fragment, whether it be R, G, B, or A (in RGBA mode) or a color index (in color index mode), or the s, t, or r texture coordinate (the depth value, window z, must be found using equation 3.3, below), is found as

where and are the data associated with the starting and ending endpoints of the segment, respectively; and are the clip w coordinates of the starting and ending endpoints of the segments, respectively. for all data except texture coordinates, in which case and ( and are the homogeneous texture coordinates at the starting and ending endpoints of the segment; results are undefined if either of these is less than or equal to 0). Note that linear interpolation would use

The reason that this formula is incorrect (except for the depth value) is that it interpolates a datum in window space, which may be distorted by perspective. What is actually desired is to find the corresponding value when interpolated in eye space, which equation 3.2 does. A GL implementation may choose to approximate equation 3.2 with 3.3, but this will normally lead to unacceptable distortion effects when interpolating texture coordinates.

Next: 3.4.2 Other Line Segment Up: 3.4 Line Segments Previous: 3.4 Line Segments

David Blythe
Sat Mar 29 02:23:21 PST 1997