Efficiently rendering line segments on a computer display

A method for rendering a line segment extending in the negative-x direction and positive-y direction with an absolute value of its slope between 0 and 1 on a computer display given a starting point and an ending point, the starting point having the form (xs, ys) and the ending point having the form (xe, ye), xs, ys, xe, ye each having an integer portion and a fractional portion, the computer display having a current location initially set to a pixel containing the starting point, the method including:

• determining Δx by computing Δx=|xe−xs|;
• determining Δy by computing Δy=|ye−ys|;
• finding dt(0)=(yf*Δx)−((1−xf)*Δy), where xf is the fractional portion of xs and yf is the fractional portion of ys;
• for each column n containing a portion of said line segment:
• plotting said current location if dt(n)<=0.5*Δx and plotting a pixel above said current location if dt(n)>0.5*Δx;
• moving said current location to the left one pixel if dt(n)<=0.5*Δx and moving said current location to the left and up one pixel if dt(n)>0.5*Δx;
• correcting dt(n) by computing dt(n)=dt(n)−Δx if dt(n)>0.5*Δx;
• and
• computing dt(n+1)=dt(n)+Δy.

A method for rendering a line segment extending in the positive-x direction and negative-y direction with an absolute value of its slope between 0 and 1 on a computer display given a starting point and an ending point, the starting point having the form (xs, ys) and the ending point having the form (xe, ye), xs, ys, xe, ye each having an integer portion and a fractional portion, the computer display having a current location initially set to a pixel containing the starting point, the method including:

• determining Δx by computing Δx=|xe−xs|;
• determining Δy by computing Δy=|ye−ys|;
• finding dt(0)=((1yf)*Δx)−(xf*Δy), where xf is the fractional portion of xs and yf is the fractional portion of ys;
• for each column n containing a portion of said line segment:
• plotting said current location if dt(n)<=0.5*Δx and plotting a pixel below said current location if dt(n)>0.5*Δx;
• moving said current location to the right one pixel if dt(n)<=0.5*Δx and moving said current location to the right and down one pixel if dt(n)>0.5*Δx;
• correcting dt(n) by computing dt(n)=dt(n)−Δx if dt(n)>0.5*Δx;
• and
• computing dt(n+1)=dt(n)+Δy.

A method for rendering a line segment extending in the negative-x direction and negative-y direction with an absolute value of its slope between 0 and 1 on a computer display given a starting point and an ending point, the starting point having the form (xs, ys) and the ending point having the form (xe, ye), xs, ys, xe, ye each having an integer portion and a fractional portion, the computer display having a current location initially set to a pixel containing the starting point, the method including:

• determining Δx by computing Δx=|xe−xs|;
• determining Δy by computing Δy=|ye−ys|;
• finding dt(0)=((1−yf)*Δx)−((1−xf)*Δy), where xf is the fractional portion of xs and yf is the fractional portion of ys;
• for each column n containing a portion of said line segment:
• plotting said current location if dt(n)<=0.5*Δx and plotting a pixel below said current location if dt(n)>0.5*Δx;
• moving said current location to the left one pixel if dt(n)<=0.5*Δx and moving said current location to the left and down one pixel if dt(n)>0.5*Δx;
• correcting dt(n) by computing dt(n)=dt(n)−Δx if dt(n)>0.5*Δx;
• and
• computing dt(n+1)=dt(n)+Δy.

A method for rendering a line segment extending in the positive-x direction and positive-y direction with an absolute value of its slope greater than 1 on a computer display given a starting point and an ending point, the starting point having the form (xs, ys) and the ending point having the form (xe, ye), xs, ys, xe, ye each having an integer portion and a fractional portion, the computer display having a current location initially set to a pixel containing the starting point, the method including:

• determining Δx by computing Δx=|xe−xs|;
• determining Δy by computing Δy=|ye−ys|;
• finding dt(0)=(xf*Δy)−(yf*Δx), where xf is the fractional portion of Xs and yf is the fractional portion of ys;
• for each row r containing a portion of said line segment:
• plotting said current location if dt(n)<=0.5Δy and plotting a pixel to the right of said current location if dt(n)>0.5*Δy;
• moving said current location up one pixel if dt(n)<=0.5*Δy and moving said current location to the right and up one pixel if dt(n)>0.5*Δy;
• and
• correcting dt(n) by computing dt(n)=dt(n)−Δy if dt(n)>0.5*Δy;
• and
• computing dt(n+1)=dt(n)+Δx.

A method for rendering a line segment extending in the negative-x direction and positive-y direction with an absolute value of its slope greater than 1 on a computer display given a starting point and an ending point, the starting point having the form (xs, ys) and the ending point having the form (xe, ye), xs, ys, xe, ye each having an integer portion and a fractional portion, the computer display having a current location initially set to a pixel containing the starting point, the method including:

• determining Δx by computing Δx=|xe−xs|;
• determining Δy by computing Δy=|ye−ys|;
• finding dt(0)=((1−xf)*Δy)−(yf*Δx), where xf is the fractional portion of xs and yf is the fractional portion of ys;
• for each row r containing a portion of said line segment:
• plotting said current location if dt(n)<=0.5*Δy and plotting a pixel to the left of said current location if dt(n)>0.5*Δy;
• moving said current location up one pixel if dt(n)<=0.5*Δy and moving said current location to the left and up one pixel if dt(n)>0.5*Δy;
• correcting dt(n) by computing dt(n)=dt(n)−Δy if dt(n)>0.5*Δy;
• and
• computing dt(n+1)=dt(n)+Δx.

A method for rendering a line segment extending in the positive-x direction and negative-y direction with an absolute value of its slope greater than 1 on a computer display given a starting point and an ending point, the starting point having the form (xs, ys) and the ending point having the form (xe, ye), xs, ys, xe, ye each having an integer portion and a fractional portion, the computer display having a current location initially set to a pixel containing the starting point, the method including:

• determining Δx by computing Δx=|xe−xs|;
• determining Δy by computing Δy=|ye−ys|;
• finding dt(0)=(xf*Δy)−((1−yf)*Δx), where xf is the fractional portion of xs and yf is the fractional portion of ys;
• for each row r containing a portion of said line segment:
• plotting said current location if dt(n)<=0.5*Δy and plotting a pixel to the right of said current location if dt(n)>0.5*Δy;
• moving said current location down one pixel if dt(n)<=0.5*Δy and moving said current location to the right and down one pixel if dt(n)>0.5*Δy;
• correcting dt(n) by computing dt(n)=dt(n)−Δy if dt(n)>0.5*Δy;
• and
• computing dt(n+1)=dt(n)+Δx.

A method for rendering a line segment extending in the negative-x direction and negative-y direction with an absolute value of its slope greater than 1 on a computer display given a starting point and an ending point, the starting point having the form (xs, ys) and the ending point having the form (xe, ye), xs, ys, xe, ye each having an integer portion and a fractional portion, the computer display having a current location initially set to a pixel containing the starting point, the method including:

• determining Δx by computing Δx=|xe−xs|;
• determining Δy by computing Δy=|ye−ys|;
• finding dt(0)=((1−xf)*Δy)−((1−yf)*Δx), where xf is the fractional portion of xs and yf is the fractional portion of ys;
• for each row r containing a portion of said line segment:
• plotting said current location if dt(n)<=0.5*Δy and plotting a pixel to the left of said current location if dt(n)>0.5*Δy;
• moving said current location down one pixel if dt(n)<=0.5*Δy and moving said current location to the left and down one pixel if dt(n)>0.5*Δy;
• correcting dt(n) by computing dt(n)=dt(n)−Δy if dt(n)>0.5*Δy;
• and
• computing dt(n+1)=dt(n)+Δx.

An apparatus for rendering a line segment on a computer display given a starting point and an ending point, the starting point having the form (xs, ys) and the ending point having the form (xe, ye), xs, ys, xe, ye each having an integer portion and a fractional portion, the computer display having a current pixel initially set to a pixel containing the starting point, the apparatus including:

• a Δx determiner;
• a Δy determiner;
• a dt(0) finder coupled to said Δx determiner wherein dt(0) is determined by computing dt(0)=((1−xf)*Δy)−((1−yf)*Δx) where xf is the fractional portion of xs and yf is the fractional portion of ys;
• and said Δy determiner;
• an iteration control;
• a dt(n) comparator coupled to said iteration control, said dt(0) finder, and said Δx determiner;
• a current pixel plotter coupled to said iteration control and said dt(n) comparator wherein dt(n) is determined by computing dt(n)<=0.5*Δy for plotting said current pixel, and for plotting the pixel above the current pixel dt(n) is determined if dt(n)>0.5*Δy;
• a current pixel mover coupled to said iteration control and said dt(n) comparator wherein dt(n) is determined by computing dt(n)<=0.5*Δy if the current pixel is moved down one pixel, and dt(n)>0.5*Δy if the current pixel moved to the left and down one pixel;
• a dt(n) corrector coupled to said iteration control and said dt(n) comparator, and said Δy determiner wherein dt(n) is determined by computing dt(n)=dt(n)−Δy if dt(n)>0.5*Δy;
• and
• a dt(n+1) computer coupled to said iteration control, said dt(n) comparator, said Δx determiner wherein Δx is determined by computing Δx=|xe−xs|;
• Δy is determined by computing Δy=|ye−ys;
• and dt(n+1) is determined by computing dt(q+1)=dt(n)+Δx;
• and said Δy determiner.

An apparatus for rendering a line segment extending in the positive-x direction and positive-y direction with an absolute value of its slope between 0 and 1 on a computer display given a starting point and an ending point, the starting point having the form (xs, ys) and the ending point having the form (xe, ye), xs, ys, xe, ye each having an integer portion and a fractional portion, the computer display having a current location initially set to a pixel containing the starting point, the apparatus including:

• means for determining Δx by computing Δx=|xe−xs|;
• means for determining Δy by computing Δy=|ye−ys|;
• means for finding dt(0)=(yf*Δx)−(xf*Δy), where xf is the fractional portion of xs and yf is the fractional portion of ys;
• for each column n containing a portion of said line segment:
• means for plotting said current location if dt(n)<=0.5*Δx and plotting a pixel above said current location if dt(n)>0.5*Δx;
• means for moving said current location to the right one pixel if dt(n)<=0.5*Δx and moving said current location to the right and up one pixel if dt(n)>0.5*Δx;
• means for correcting dt(n) by computing dt(n)=dt(n)−Δx if dt(n)>0.5 *Δx;
• and
• means for computing dt(n+1)=dt(n)+Δy.

An apparatus for rendering a line segment extending in the negative-x direction and positive-y direction with an absolute value of its slope between 0 and 1 on a computer display given a starting point and an ending point, the starting point having the form (xs, ys) and the ending point having the form (xe, ye), xs, ys, xe, ye each having an integer portion and a fractional portion, the computer display having a current location initially set to a pixel containing the starting point, the apparatus including:

• means for determining Δx by computing Δx=|xe−xs|;
• means for determining Δy by computing Δy=|ye−ys|;
• means for finding dt(0)=(yf*Δx)−((1−xf)*Δy), where xf is the fractional portion of xs and yf is the fractional portion of ys;
• for each column n containing a portion of said line segment:
• means for plotting said current location if dt(n)<=0.5*Δx and plotting a pixel above said current location if dt(n)>0.5*Δx;
• means for moving said current location to the left one pixel if dt(n)<=0.5 *Δx and moving said current location to the left and up one pixel if dt(n)>0.5*Δx;
• means for correcting dt(n) by computing dt(n)=dt(n)−Δx if dt(n)>0.5 *Δx;
• and
• means for computing dt(n+1)=dt(n)+Δy.

An apparatus for rendering a line segment extending in the positive-x direction and negative-y direction with an absolute value of its slope between 0 and 1 on a computer display given a starting point and an ending point, the starting point having the form (xs, ys) and the ending point having the form (xe, ye), xs, ys, xe, ye each having an integer portion and a fractional portion, the computer display having a current location initially set to a pixel containing the starting point, the apparatus including:

• means for determining Δx by computing Δx=|xc−xs|;
• means for determining Δy by computing Δy=|ye−ys|;
• means for finding dt(0)=((1−yf)*Δx)−(xf *Δy), where xf is the fractional portion of xs and yf is the fractional portion of ys;
• for each column n containing a portion of said line segment:
• means for plotting said current location if dt(n)<=0.5*Δx and plotting a pixel below said current location if dt(n)>0.5*Δx;
• means for moving said current location to the right one pixel if dt(n)<=0.5*Δx and moving said current location to the right and down one pixel if dt(n)>0.5*Δx;
• means for correcting dt(n) by computing dt(n)=dt(n)−Δx if dt(n)>0.5*Δx;
• and
• means for computing dt(n+1)=dt(n)+Δy.

An apparatus for rendering a line segment extending in the negative-x direction and negative-y direction with an absolute value of its slope between 0 and 1 on a computer display given a starting point and an ending point, the starting point having the form (xs, ys) and the ending point having the form (xe, ye), xs, ys, xe, ye each having an integer portion and a fractional portion, the computer display having a current location initially set to a pixel containing the starting point, the apparatus including:

• means for determining Δx by computing Δx=|xe−xs|;
• means for determining Δy by computing Δy=|ye−ys|;
• means for finding dt(0)=((1−yf)*Δx)−((1−xf)*Δy), where xf is the fractional portion of xs and yf is the fractional portion of ys;
• for each column n containing a portion of said line segment:
• means for plotting said current location if dt(n)<=0.5*Δx and plotting a pixel below said current location if dt(n)>0.5*Δx;
• means for moving said current location to the left one pixel if dt(n)<=0.5*Δx and moving said current location to the left and down one pixel if dt(n)>0.5*Δx;
• means for correcting dt(n) by computing dt(n)=dt(n)−Δx if dt(n)>0.5*Δx;
• and
• means for computing dt(n+1)=dt(n)+Δy.

An apparatus for rendering a line segment extending in the positive-x direction and positive-y direction with an absolute value of its slope greater than 1 on a computer display given a starting point and an ending point, the starting point having the form (xs, ys) and the ending point having the form (xe, ye), xs, ys, xe, Ye each having an integer portion and a fractional portion, the computer display having a current location initially set to a pixel containing the starting point, the apparatus including:

• means for determining Δx by computing Δx=|xe−xs|;
• means for determining Δy by computing Δy=|ye−ys|;
• means for finding dt(0)=(xf*Δy)−(yf*Δx), where xf is the fractional portion of xs and yf is the fractional portion of ys;
• for each row r containing a portion of said line segment:
• means for plotting said current location if dt(n)<=0.5*Δy and plotting a pixel to the right of said current location if dt(n)>0.5*Δy;
• means for moving said current location up one pixel if dt(n)<=0.5*Δy and moving said current location to the right and up one pixel if dt(n)>0.5*Δy;
• means for correcting dt(n) by computing dt(n)=dt(n)−Δy if dt(n)>0.5*Δy;
• and
• means for computing dt(n+1)=dt(n)+Δx.

An apparatus for rendering a line segment extending in the negative-x direction and positive-y direction with an absolute value of its slope greater than 1 on a computer display given a starting point and an ending point, the starting point having the form (xs, ys) and the ending point having the form (xe, ye), xs, ys, xe, ye each having an integer portion and a fractional portion, the computer display having a current location initially set to a pixel containing the starting point, the apparatus including:

• means for determining Δx by computing Δx=|xe−xs|;
• means for determining Δy by computing Δy=|ye−ys|;
• means for finding dt(0)=((1−xf)*Δy)−(yf*Δx), where xf is the fractional portion of xs and yf is the fractional portion of ys;
• for each row r containing a portion of said line segment:
• means for plotting said current location if dt(n)<=0.5*Δy and plotting a pixel to the left of said current location if dt(n)>0.5*Δy;
• means for moving said current location up one pixel if dt(n)<=0.5*Δy and moving said current location to the left and up one pixel if dt(n)>0.5*Δy;
• means for correcting dt(n) by computing dt(n)=dt(n)−Δx if dt(n)>0.5*Δy;
• and
• means for computing dt(n+1)=dt(n)+Δx.

An apparatus for rendering a line segment extending in the positive-x direction and negative-y direction with an absolute value of its slope greater than 1 on a computer display given a starting point and an ending point, the starting point having the form (xs, ys) and the ending point having the form (xe, ye), xs, ys, xe, ye each having an integer portion and a fractional portion, the computer display having a current location initially set to a pixel containing the starting point, the apparatus including:

• means for determining Δx by computing Δx=|xe−xs|;
• means for determining Δy by computing Δy=|ye−ys|;
• means for finding dt(0)=(xf*Δy)−((1−yf)*Δx), where xf is the fractional portion of xs and yf is the fractional portion of ys;
• for each row r containing a portion of said line segment:
• means for plotting said current location if dt(n)<=0.5*Δy and plotting a pixel to the right of said current location if dt(n)>0.5*Δy;
• means for moving said current location down one pixel if dt(n)<=0.5*Δy and moving said current location to the right and down one pixel if dt(n)>0.5*Δy;
• means for correcting dt(n) by computing dt(n)=dt(n)−Δy if dt(n)>0.5*Δy;
• and
• means for computing dt(n+1)=dt(n)+Δx.

An apparatus for rendering a line segment extending in the negative-x direction and negative-y direction with an absolute value of its slope greater than 1 on a computer display given a starting point and an ending point, the starting point having the form (xs, ys) and the ending point having the form (xe, ye), xs, ys, xe, ye each having an integer portion and a fractional portion, the computer display having a current location initially set to a pixel containing the starting point, the apparatus including:

• means for determining Δx by computing Δx=|xe−xs|;
• means for determining Δy by computing Δy=|ye−ys|;
• means for finding dt(0)=((1−xf)*Δy)−((1−yf)*Δx), where xf is the fractional portion of xs and yf is the fractional portion of ys;
• for each row r containing a portion of said line segment:
• means for plotting said current location if dt(n)<=0.5*Δy and plotting a pixel to the left of said current location if dt(n)>0.5*Δy;
• means for moving said current location down one pixel if dt(n)<=0.5*Δy and moving said current location to the left and down one pixel if dt(n)>0.5*Δy;
• means for correcting dt(n) by computing dt(n)=dt(n)−Δy if dt(n)>0.5*Δy;
• and
• means for computing dt(n+1)=dt(n)+Δx.

A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine for rendering a line segment extending in the positive-x direction and positive-y direction with an absolute value of its slope between 0 and 1 on a computer display given a starting point and an ending point, the starting point having the form (xs, ys) and the ending point having the form (xe, ye), xs, ys, xe, ye each having an integer portion and a fractional portion, the computer display having a current location initially set to a pixel containing the starting point, the method including:

• determining Δx by computing Δx=|xe−xs|;
• determining Δy by computing Δy=|ye−ys|;
• finding dt(0)=(yf*Δx)−(xf*Δy), where xf is the fractional portion of xs and yf is the fractional portion of ys;
• for each column n containing a portion of said line segment:
• plotting said current location if dt(n)<=0.5*Δx and plotting a pixel above said current location if dt(n)>0.5*Δx;
• moving said current location to the right one pixel if dt(n)<=0.5*Δx and moving said current location to the right and up one pixel if dt(n)>0.5*Δx;
• correcting dt(n) by computing dt(n)=dt(n)−Δx if dt(n)>0.5*Δx;
• and
• computing dt(n+1)=dt(n)+Δy.

A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine for rendering a line segment extending in the negative-x direction and positive-y direction with an absolute value of its slope between 0 and 1 on a computer display given a starting point and an ending point, the starting point having the form (xs, ys) and the ending point having the form (xe, ye), xs, ys, xe, ye each having an integer portion and a fractional portion, the computer display having a current location initially set to a pixel containing the starting point, the method including:

• determining Δx by computing Δx=|xe−xs|;
• determining Δy by computing Δy=|ye−ys|;
• finding dt(0)=(yf*Δx)−((1−xf)*Δy), where xf is the fractional portion of xs and yf is the fractional portion of ys;
• for each column n containing a portion of said line segment:
• plotting said current location if dt(n)<=0.5*Δx and plotting a pixel above said current location if dt(n)>0.5*Δx;
• moving said current location to the left one pixel if dt(n)<=0.5*Δx and moving said pixel to the left and up one pixel if di(n)>0.5*Δx;
• correcting dt(n) by computing dt(n)=dt(n)−Δx if dt(n)>0.5*Δx;
• and
• computing dt(n+1)=dt(n)+Δy.

A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine for rendering a line segment extending in the positive-x direction and negatively direction with an absolute value of its slope between 0 and 1 on a computer display given a starting point and an ending point, the starting point having the form (xs, ys) and the ending point having the form (xe, ye), xs, ys, xe, ye each having an integer portion and a fractional portion, the computer display having a current location initially set to a pixel containing the starting point, the method including:

• determining Δx by computing Δx=|xe−xs|;
• determining Δy by computing Δy=|ye−ys|;
• finding dt(0)=((1−yf)*Δx)−(xf*Δy), where xf is the fractional portion of xs and yf is the fractional portion of ys;
• for each column n containing a portion of said line segment:
• plotting said current location if dt(n)<=0.5*Δx and plotting a pixel below said current location if dt(n)>0.5*Δx;
• moving said current location to the right one pixel if dt(n)<=0.5*Δx and moving said current location to the right and down one pixel if dt(n)>0.5*Δx;
• correcting dt(n) by computing dt(n)=dt(n)−Δx if dt(n)>0.5*Δx;
• and
• computing dt(n+1)=dt(n)+Δy.

A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine for rendering a line segment extending in the negative-x direction and negative-y direction with an absolute value of its slope between 0 and 1 on a computer display given a starting point and an ending point, the starting point having the form (xs, ys) and the ending point having the form (xe, ye), xs, ys, xe, ye each having an integer portion and a fractional portion, the computer display having a current location initially set to a pixel containing the starting point, the method including:

• determining Δx by computing Δx=|xe−xs|;
• determining Δy by computing Δy=|ye−ys|;
• finding dt(0)=((1−yf)*Δx)−((1−xf)*Δy), where xf is the fractional portion of xs and yf is the fractional portion of ys;
• for each column n containing a portion of said line segment:
• plotting said current location if dt(n)<=0.5*Δx and plotting a pixel below said current location if dt(n)>0.5*Δx;
• moving said current location to the left one pixel if dt(n)<=0.5*Δx and moving said current location to the left and down one pixel if dt(n)>0.5*Δx;
• correcting dt(n) by computing dt(n)=dt(n)−Δx if dt(n)>0.5*Δx;
• and
• computing dt(n+1)=dt(n)+Δy.

A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine for rendering a line segment extending in the positive-x direction and positive-y direction with an absolute value of its slope greater than 1 on a computer display given a starting point and an ending point, the starting point having the form (xs, ys) and the ending point having the form (xe, ye), xs, ys, xe, ye each having an integer portion and a fractional portion, the computer display having a current location initially set to a pixel containing the starting point, the method including:

• determining Δx by computing Δx=|xe−xs|;
• determining Δy by computing Δy=|ye−ys|;
• finding dt(0)=(xf*Δy)−(yf*Δx), where xf is the fractional portion of xs and yf is the fractional portion of ys;
• for each row r containing a portion of said line segment:
• plotting said current location if dt(n)<=0.5*Δy and plotting a pixel to the right of said current location if dt(n)>0.5*Δy;
• moving said current location up one pixel if dt(n)<=0.5*Δy and moving said current location to the right and up one pixel if dt(n)>0.5*Δy;
• and
• correcting dt(n) by computing dt(n)=dt(n)−Δy if dt(n)>0.5*Δy;
• and
• computing dt(n+1)=dt(n)+Δx.

A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine for rendering a line segment extending in the negative-x direction and positive-y direction with an absolute value of its slope greater than 1 on a computer display given a starting point and an ending point, the starting point having the form (xs, ys) and the ending point having the form (xe, ye), xs, ys, xe, ye each having an integer portion and a fractional portion, the computer display having a current location initially set to a pixel containing the starting point, the method including:

• determining Δx by computing Δx=|xe−xs|;
• determining Δy by computing Δy=|ye−ys|;
• finding dt(0)=((1−xf)*Δy)−(yf*Δx), where xf is the fractional portion of xs and yf is the fractional portion of ys;
• for each row r containing a portion of said line segment:
• plotting said current location if dt(n)<=0.5*Δy and plotting a pixel to the left of said current location if dt(n)>0.5*Δy;
• moving said current location up one pixel if dt(n)<=0.5*Δy and moving said current location to the left and up one pixel if dt(n)>0.5*Δy;
• correcting dt(n) by computing dt(n)=dt(n)−Δy if dt(n)>0.5*Δy;
• and
• computing dt(n+1)=dt(n)+Δx.

A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine for rendering a line segment extending in the positive-x direction and negative-y direction with an absolute value of its slope greater than 1 on a computer display given a starting point and an ending point, the starting point having the form (xs, ys) and the ending point having the form (xe, ye), xs, ys, xe, ye each having an integer portion and a fractional portion, the computer display having a current location initially set to a pixel containing the starting point, the method including:

• determining Δx by computing Δx=|xe−xs|;
• determining Δy by computing Δy=|ye−ys|;
• finding dt(0)=(xf*Δy)−((1−yf)*Δx), where xf is the fractional portion of xs and yf is the fractional portion of ys;
• for each row r containing a portion of said line segment:
• plotting said current location if dt(n)<=0.5*Δy and plotting a pixel to the right of said current location if dt(n)>0.5*Δy;
• moving said current location down one pixel if dt(n)<=0.5*Δy and moving said current location to the right and down one pixel if dt(n)>0.5*Δy;
• correcting dt(n) by computing dt(n)=dt(n)−Δy if dt(n)>0.5*Δy;
• and
• computing dt(n+1)=dt(n)+Δx.

A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine for rendering a line segment extending in the negative-x direction and negative-y direction with an absolute value of its slope greater than 1 on a computer display given a starting point and an ending point, the starting point having the form (xs, ys) and the ending point having the form (xe, ye), xs, ys, xe, ye each having an integer portion and a fractional portion, the computer display having a current location initially set to a pixel containing the starting point, the method including:

• determining Δx by computing Δx=|xe−xs|;
• determining Δy by computing Δy=|ye−ys|;
• finding dt(0)=((1−xf)*Δy)−((1−yf)*ΔX), where xf is the fractional portion of xs and yf is the fractional portion of ys;
• for each row r containing a portion of said line segment:
• plotting said current location if dt(n)<=0.5*Δy and plotting a pixel to the left of said current location if dt(n)>0.5*Δy;
• moving said current location down one pixel if dt(n)<=0.5*Δy and moving said current location to the left and down one pixel if dt(n)>0.5*Δy;
• correcting dt(n) by computing dt(n)=dt(n)−Δy if dt(n)>0.5*Δy;
• and
• computing dt(n+1)=dt(n)+Δx.