吴小林直线算法
 | 此條目翻譯品質不佳。 |
| 吴小林直线算法 | |
|---|---|
 吴小林算法画出的抗锯齿线段 | |
| 概况 | |
| 類別 | 计算机图形学算法 |
| 复杂度 | |
| 相关变量的定义 | |
吴小林算法是一种绘制抗锯齿直线的算法，因为其较高的执行效率被发表在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.