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:
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.