Xiaolin Wu's line algorithm: Difference between revisions

Revision as of 13:15, 23 September 2012

Revision as of 06:15, 7 December 2012

Line 7:

An extension to the algorithm for circle drawing was presented by Xiaolin Wu in the book ''[[Graphics Gems]] II''. Just like the line drawing algorithm is a replacement for Bresenham's line drawing algorithm, the circle drawing algorithm is a replacement for Bresenham's circle drawing algorithm.

<syntaxhighlight lang="pascal">

<code>

'''function''' plot(x, y, c) '''is'''

plot the pixel at (x, y) with brightness c (where 0 ≤ c ≤ 1)

'''function''' ipart(x) '''is'''

'''return''' ' 'integer part of x''

'''function''' round(x) '''is'''

'''return''' ipart(x + 0.5)

'''function''' fpart(x) '''is'''

'''return''' ''fractional part of x''

'''function''' rfpart(x) '''is'''

'''return''' 1 - fpart(x)

'''function''' drawLine(x0,y0,x1,y1) '''is'''

boolean steep := abs(y1 - y0) > abs(x1 - x0)

'''if''' steep '''then'''

swap(x0, y0)

swap(x1, y1)

'''end if'''

'''if''' x0 > x1 '''then'''

swap(x0, x1)

swap(y0, y1)

'''end if'''

dx := x1 - x0

Line 39:

gradient := dy / dx

''// handle first endpoint''

xend := round(x0)

yend := y0 + gradient * (xend - x0)

xgap := rfpart(x0 + 0.5)

xpxl1 := xend '' // this will be used in the main loop''

ypxl1 := ipart(yend)

'''if''' steep '''then'''

plot(ypxl1, xpxl1, rfpart(yend) * xgap)

plot(ypxl1+1, xpxl1, fpart(yend) * xgap)

'''else'''

plot(xpxl1, ypxl1 , rfpart(yend) * xgap)

plot(xpxl1, ypxl1+1, fpart(yend) * xgap)

'''end if'''

intery := yend + gradient ''// first y-intersection for the main loop''

''// handle second endpoint''

''//handle second endpoint''

xend := round(x1)

yend := y1 + gradient * (xend - x1)

xgap := fpart(x1 + 0.5)

xpxl2 := xend '' //this will be used in the main loop''

ypxl2 := ipart(yend)

'''if''' steep then

plot(ypxl2 , xpxl2, rfpart(yend) * xgap)

plot(ypxl2+1, xpxl2, fpart(yend) * xgap)

'''else'''

plot(xpxl2, ypxl2, rfpart(yend) * xgap)

plot(xpxl2, ypxl2+1, fpart(yend) * xgap)

'''end if'''

''// main loop''

'''for''' x '''from''' xpxl1 + 1 '''to''' xpxl2 - 1 '''do'''

for x from xpxl1 '''if'''+ steep1 '''then'''to xpxl2 - 1 do

if steep then

plot(ipart(intery) , x, rfpart(intery))

plot(ipart(intery)+1, x, fpart(intery))

'''else'''

plot(x, ipart (intery), rfpart(intery))

plot(x, ipart (intery)+1, fpart(intery))

'''end if'''

intery = intery + gradient

'''end function'''

</syntaxhighlight>

</code>

'''Note:''' If at the beginning of the routine abs(''dx'') < abs(''dy'') is true, then all plotting should be done with ''x'' and ''y'' reversed.