Xiaolin Wu's line algorithm: Difference between revisions

Revision as of 14:52, 15 June 2005

Latest revision as of 17:26, 25 June 2025

(121 intermediate revisions by 95 users not shown)

Line 1:

{{Short description|Line algorithm with antialiasing}}

'''Xiaolin Wu's line algorithm''' is an [[algorithm]] for line [[antialiasing]], which was presented in the article ''An

{{multiple|

{{third-party|date=April 2018}}

{{no footnotes|date=January 2013}}

{{Cleanup|reason=Implementation does not provide explanation|date=November 2023}}

}}

[[File:LineXiaolinWu.gif|thumb|336px|Demonstration of Xiaolin Wu's algorithm]]

'''Xiaolin Wu's line algorithm''' is an [[algorithm]] for line [[spatial anti-aliasing|antialiasing]].

[[File:Xiaolin anti-aliased line comparison.png|thumb|Anti-Aliased Lines (blue) generated with Xiaolin Wu's line algorithm alongside standard lines (red) generated with Bresenham's line algorithm]]

==Antialiasing technique==

Efficient Antialiasing Technique'' in the [[July]] [[1991]] issue of ''[[Computer Graphics]]'', as well as in the article

Xiaolin Wu's line algorithm was presented in the article "An Efficient Antialiasing Technique" in the July 1991 issue of ''[[Computer Graphics (newsletter)|Computer Graphics]]'', as well as in the article "Fast Antialiasing" in the June 1992 issue of ''[[Dr. Dobb's Journal]]''.

[[Bresenham's line algorithm|Bresenham's algorithm]] draws lines extremely quickly, but it does not perform anti-aliasing. In addition, it cannot handle any cases where the line endpoints do not lie exactly on integer points of the pixel grid. A naive approach to anti-aliasing the line would take an extremely long time. Wu's algorithm is comparatively fast, but is still slower than Bresenham's algorithm. The algorithm consists of drawing pairs of pixels straddling the line, each coloured according to its distance from the line. Pixels at the line ends are handled separately. Lines less than one pixel long are handled as a special case.

''Fast Antialiasing'' in the [[June]] [[1992]] issue of ''[[Dr. Dobb's Journal]]''.

An extension to the algorithm for circle drawing was presented by Xiaolin Wu in the book ''Graphics Gems II''. Just as 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.

[[Bresenham's line algorithm|Bresenham's algorithm]] draws lines extremely quickly, but it cannot perform anti-aliasing. In

==Algorithm==

addition, it cannot handle the case where the line endpoints do not lie exactly on integer points of the pixel grid. A

Like [[Bresenham's line algorithm|Bresenham’s line algorithm]], this method steps

naïve approach to anti-aliasing the line would take an extremely long time, but Wu's algorithm is quite fast (It is

along one axis and considers the two nearest pixels to the ideal line. Instead of

choosing the nearest, it draws both, with intensities proportional to their vertical

distance from the true line. This produces smoother, anti-aliased lines.

[[File:Wu-line-animation.gif|thumb|Animation showing symmetry of Wu's line algorithm ]]

still slower than [[Bresenham's line algorithm|Bresenham's]], though. The basis of the algorithm is to draw pairs of pixels

The pseudocode below assumes a line where <math>x_0 < x_1</math>, <math>y_0 < y_1</math>,

straddling the line, coloured according to proximity. Pixels at the line ends are handled separately. Lines less than one

and the slope <math>k = \frac{dy}{dx}</math> satisfies <math>0 \le k \le 1</math>. This

is a standard simplification — the algorithm can be extended to all directions using symmetry.

The algorithm is well-suited to older CPUs and microcontrollers because:

pixel long should be handled as a special case.

* It avoids floating point arithmetic in the main loop (only used to initialize d)

Here is [[pseudocode]] for the nearly-horizontal case (<math>&delta;x > &delta;y</math>). The extension to cover

* It renders symmetrically from both ends, halving the number of iterations

* The main loop uses only addition and bit shifts — no multiplication or division

nearly-vertical lines is trivial, and left as an exercise for the reader.

{{wikicode}}

<code>

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

plot the pixel at (x,y) with brightness c ''// where <math>0<=c<=1</math>''

}

'''function''' ipart(x) {

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

}

'''function''' round(x) {

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

}

'''function''' fpart(x) {

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

}

'''function''' rfpart(x) {

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

}

''// check that x₁ < x₂''

'''if x₂ < x₁

swap x₁, x₂

dx = x₂ - x₁

dy = y₂ - y₁

gradient = dy / dx

''// handle first endpoint''

xend = round(x₁)

yend = y₁ + gradient * (xend - x₁)

xgap = rfpart(x₁ + 0.5)

xpxl1 = xend

ypxl1 = ipart(yend)

brightness1 = rfpart(yend) * xgap

brightness2 = fpart(yend) * xgap

plot(xpxl1, ypxl1, brightness1)

plot(xpxl1, ypxl1+1, brightness2)

intery = yend + gradient ''// first y-intersection for later''

''// handle second endpoint''

xend = round(x₂)

yend = y₂ + gradient * (xend - x₂)

xgap = rfpart(x₂ - 0.5)

xpxl2 = xend

ypxl2 = ipart(yend)

brightness1 = rfpart(yend) * xgap

brightness2 = fpart(yend) * xgap

plot(xpxl2, ypxl2, brightness1)

plot(xpxl2, ypxl2+1, brightness2)

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

brightness1 = rfpart(intery)

brightness2 = fpart(intery)

plot(x, ipart(intery), brightness1)

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

intery = intery + gradient

}

</code>

<syntaxhighlight lang="python" line="1">

An extension to the algorithm for circle drawing was presented by Xiaolin Wu in the book ''Graphics Gems II''. Just like the

function draw_line(x0, y0, x1, y1)

N := 8 # brightness resolution (bits)

M := 15 # fixed-point fractional bits

I := maximum brightness value

# Compute gradient and convert to fixed-point step

line drawing algorithm is an replacement for of [[Bresenham's line algorithm]], the circle drawing algorithm is a replacement

k := float(y1 - y0) / (x1 - x0)

d := floor((k << M) + 0.5)

# Start with fully covered pixels at each end

for Bresenham's circle drawing algorithm.

img[x0, y0] := img[x1, y1] := I

D := 0 # Fixed-point accumulator

==References==

* {{Journal reference issue| Author=Abrash, Michael | Title=[http://www.whisqu.se/per/docs/graphics75.htm Fast Antialiasing]

while true:

(Column). | Journal=[[Dr. Dobb's Journal]] | Year=June 1992 | Volume=17 | Issue=6 | Pages=139(7)}}

x0 := x0 + 1

* {{Journal reference issue| Author=Wu, Xiaolin | Title=[http://portal.acm.org/citation.cfm?id=122734 An efficient

x1 := x1 - 1

if x0 > x1:

break

D := D + d

antialiasing technique] | Journal=[[Computer Graphics]] | Year=July 1991 | Volume=25 | Issue=4 | Pages=143--152}} ISBN

if D overflows:

y0 := y0 + 1

y1 := y1 - 1

# Brightness = upper N bits of fractional part of D

0-89791-436-8.

v := D >> (M - N)

* Wu, Xiaolin (1991). Fast Anti-Aliased Circle Generation. In James Arvo (Ed.),

img[x0, y0] := img[x1, y1] := I - v

''[http://print.google.com/print?id=Kw3YPvf8A-AC&pg=446&lpg=446&prev=http://print.google.com/print%3Fq%3Dwu%2Bcircle%2Balgori

img[x0, y0 + 1] := img[x1, y1 -1] := v

</syntaxhighlight>

===Floating Point Implementation===

thm%26ie%3DUTF-8%26id%3DKw3YPvf8A-AC&sig=xFsWaJHNOOlbog9Rgk-3hbCvJws Graphics Gems II]''. pp. 446--?. San Francisco: Morgan

<syntaxhighlight lang="pascal" line="1">

Kaufmann. ISBN 0-12-064480-0.

function plot(x, y, c) is

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

// fractional part of x

==External links==

function fpart(x) is

* [http://www.ece.mcmaster.ca/~xwu/ Xiaolin Wu's homepage]

return x - floor(x)

function rfpart(x) is

{{comp-stub}}

return 1 - fpart(x)

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

[[Category:Geometric algorithms]]

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

dy := y1 - y0

if dx == 0.0 then

gradient := 1.0

else

gradient := dy / dx

end if

// handle first endpoint

xend := floor(x0)

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

xgap := 1 - (x0 - xend)

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

ypxl1 := floor(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

xend := ceil(x1)

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

xgap := 1 - (xend - x1)

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

ypxl2 := floor(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

if steep then

for x from xpxl1 + 1 to xpxl2 - 1 do

begin

plot(floor(intery) , x, rfpart(intery))

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

intery := intery + gradient

end

else

for x from xpxl1 + 1 to xpxl2 - 1 do

begin

plot(x, floor(intery), rfpart(intery))

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

intery := intery + gradient

end

end if

end function

</syntaxhighlight>

==References==

* {{cite journal

| author=Abrash, Michael

| url = http://archive.gamedev.net/archive/reference/articles/article382.html

| title = Fast Antialiasing (Column)

| journal=[[Dr. Dobb's Journal]]

| date=June 1992 | volume=17 | issue=6 | pages=139(7)

}}

* {{cite journal

| author=Wu, Xiaolin

| url = http://portal.acm.org/citation.cfm?id=122734

| title = An efficient antialiasing technique

| journal=ACM SIGGRAPH Computer Graphics

| date=July 1991 | volume=25 | issue=4 | pages=143–152

| doi = 10.1145/127719.122734

| isbn=0-89791-436-8

| url-access=subscription

}}

* {{cite book

| author = Wu, Xiaolin

| year = 1991

| chapter = Fast Anti-Aliased Circle Generation

| editor = James Arvo

| title = Graphics Gems II

| pages = 446–450

| ___location = San Francisco

| publisher = Morgan Kaufmann

| isbn = 0-12-064480-0

}}

==External links==

* [http://www.ece.mcmaster.ca/~xwu/ Xiaolin Wu's homepage]

* [https://www.eng.mcmaster.ca/ece/faculty/dr-xiaolin-wu Xiaolin Wu's homepage at McMaster University]

{{DEFAULTSORT:Xiaolin Wu's Line Algorithm}}

[[Category:Anti-aliasing algorithms]]

[[Category:Articles with example pseudocode]]