吳小林直線算法
 | 此條目翻譯品質不佳。 |
| 吳小林直線算法 | |
|---|---|
 吳小林算法畫出的抗鋸齒線段 | |
| 概況 | |
| 類別 | 計算機圖形學算法 |
| 複雜度 | |
| 相關變量的定義 | |
吳小林算法是一種繪製抗鋸齒直線的算法，因為其較高的執行效率被發表在1991年7月的《 Computer Graphics》和1992年6月的《Dr. Dobb's Journal》上。
布雷森漢姆直線演算法繪製直線非常快，但它不支持抗鋸齒。此外，它不能處理線段端點的坐標不是整數的情況。一個不成熟的反鋸齒畫線方法需要非常長的時間，但吳的算法是相當快的（雖然它仍然較布雷森漢姆直線算法慢）。該算法的基本思想是畫兩個像素點在岔在直線兩邊，並按照直線相近的顏色着色，而線段末端的像素點另外處理。如果線段寬度小於一像素，將會被作為特殊情況考慮。
吳小林的《Graphics Gems II》一書描述了一個繪製圓的算法，作為布雷森漢姆圓繪製算法的替代品。
function plot(x, y, c) is
plot the pixel at (x, y) with brightness c (where 0 ≤ c ≤ 1)
// integer part of x
function ipart(x) is
return floor(x)
function round(x) is
return ipart(x + 0.5)
// fractional part of x
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
gradient := dy / dx
if dx == 0.0 then
gradient := 1.0
end if
// 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
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
if steep then
for x from xpxl1 + 1 to xpxl2 - 1 do
begin
plot(ipart(intery) , x, rfpart(intery))
plot(ipart(intery)+1, x, fpart(intery))
intery := intery + gradient
end
else
for x from xpxl1 + 1 to xpxl2 - 1 do
begin
plot(x, ipart(intery), rfpart(intery))
plot(x, ipart(intery)+1, fpart(intery))
intery := intery + gradient
end
end if
end function
注意：如果在程序開始abs(dx) < abs(dy)為 true，那麼所有的繪圖應該做X和Y逆轉。
參考文獻
- Abrash, Michael. Fast Antialiasing (Column). Dr. Dobb's Journal. June 1992, 17 (6): 139(7) [2012-02-01]. （原始內容存檔於2010-03-01）.
- Wu, Xiaolin. An efficient antialiasing technique. Computer Graphics. July 1991, 25 (4): 143–152. ISBN 0-89791-436-8. doi:10.1145/127719.122734.
- Wu, Xiaolin. Fast Anti-Aliased Circle Generation. James Arvo (Ed.) (編). Graphics Gems II. San Francisco: Morgan Kaufmann. 1991: 446–450. ISBN 0-12-064480-0.