Xiaolin Wu's line algorithm: Difference between revisions

Revision as of 15:05, 17 December 2007

Latest revision as of 17:26, 25 June 2025

(96 intermediate revisions by 75 users not shown)

Line 1:

{{Short description|Line algorithm with antialiasing}}

[[Image:XiaolinWuLine.png|right|thumb|Antialiased line drawn with Xiaolin Wu's algorithm]]

{{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==

'''Xiaolin Wu's line algorithm''' is an [[algorithm]] for line [[antialiasing]], which was presented in the article ''An Efficient Antialiasing Technique'' in the July [[1991]] issue of ''[[Computer Graphics]]'', as well as in the article ''Fast Antialiasing'' in the June [[1992]] issue of ''[[Dr. Dobb's Journal]]''.

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 cannotdoes not perform anti-aliasing. In addition, it cannot handle theany casecases where the line endpoints do not lie exactly on integer points of the pixel grid. A naïvenaive approach to anti-aliasing the line would take an extremely long time, but. Wu's algorithm is quitecomparatively fast, (itbut is still slower than Bresenham's, though)algorithm. The basis of the algorithm isconsists toof drawdrawing pairs of pixels straddling the line, each coloured according to proximityits distance from the line. Pixels at the line ends are handled separately. Lines less than one pixel long should beare handled as a special case.

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

==Algorithm==

==Pseudocode implementation==

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

Here is [[pseudocode]] for the nearly-horizontal case (<math>\Delta x > \Delta y</math>). To extend the algorithm to work for all lines, swap the x and y coordinates when near-vertical lines appear (for reference, see [[Bresenham's line algorithm]]).

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 ]]

<code>

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

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

plot the pixel at (x, y) with brightness c (where 0 &le; c &le; 1)

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.

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

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

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

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

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

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

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

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

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

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

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

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

function draw_line(x0, y0, x1, y1)

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

N := 8 # brightness resolution (bits)

M := 15 # fixed-point fractional bits

'''function''' drawLine(x1,y1,x2,y2) '''is'''

I '''if''':= x2maximum <brightness x1value

swap x1, x2

# Compute gradient and convert to fixed-point step

swap y1, y2

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

'''end if'''

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

dx = x2 - x1

# Start with fully covered pixels at each end

dy = y2 - y1

img[x0, gradienty0] := dyimg[x1, /y1] dx:= I

D := 0 # Fixed-point accumulator

''// handle first endpoint''

xend = round(x1)

while true:

yend = y1 + gradient * (xend - x1)

xgap x0 := rfpart(x1x0 + 0.5)1

x1 := x1 - 1

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

ypxl1 = ipart(yend) if x0 > x1:

break

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

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

D := D + d

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

if D overflows:

y0 := y0 + 1

''// handle second endpoint''

xend y1 := round(x2)y1 - 1

yend = y2 + gradient * (xend - x2)

# Brightness = upper N bits of fractional part of D

xgap = fpart(x2 + 0.5)

xpxl2 = xend ''v // this will be:= usedD in>> the(M main- loop''N)

ypxl2 = ipart(yend)

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

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

plot(xpxl2 img[x0, ypxl2y0 + 1] := img[x1, fpart(yend)y1 -1] *:= xgap)v

</syntaxhighlight>

''// main loop''

===Floating Point Implementation===

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

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

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

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

function plot(x, y, c) is

intery = intery + gradient

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

'''repeat'''

'''end function'''

// fractional part of x

</code>

function fpart(x) is

return x - floor(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

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://wwwarchive.gamedev.net/archive/reference/articles/article382.asphtml

| title = Fast Antialiasing (Column)

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

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

}}

* {{cite journal

Line 77 ⟶ 163:

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

| title = An efficient antialiasing technique

| journal=[[ACM SIGGRAPH Computer Graphics]]

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

| doi = 10.1145/127719.122734

| id = ISBN 0-89791-436-8

| isbn=0-89791-436-8

| url-access=subscription

}}

* {{cite book

Line 85 ⟶ 173:

| year = 1991

| chapter = Fast Anti-Aliased Circle Generation

| editor = James Arvo (Ed.)

| title = Graphics Gems II

| pages = pp. 446–?446–450

| ___location = San Francisco

| publisher = Morgan Kaufmann

| idisbn = 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:Geometric algorithms]]

[[Category:Anti-aliasing algorithms]]

[[Category:Articles with example pseudocode]]

[[ru:Алгоритм Ву]]