吴小林直线算法

吴小林算法是一种绘制抗锯齿直线的算法，因为其较高的执行效率被发表在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 xfunction ipart(x) is return floor(x)function round(x) is return ipart(x + 0.5)// fractional part of xfunction 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 ifend function 注意：如果在程序开始abs(dx) < abs(dy)为 true，那么所有的绘图应该做X和Y逆转。