计算机图形学-基本图形生成算法-图形的扫描转换

Bresenham画线算法（5/11）

v设e=e×2?x，不影响判断的准确性ve0=2?y - ?x

v当e≥0时，最接近P2(xi+1,yi+1)

P2e’e??y方向走一步

v当e<0时，最接近P1(xi+1,yi)

PP1??y方向不走步

P2ePP1e’Bresenham画线算法（6/11）

v下一步误差的计算v当e≥0时，y方向走一步

P2??e’=2?y/ ?x - 1 =e + ?y/ ?x - 1 ??e’=e + 2?y - 2?x

v当e<0时，y方向不走步

e’ePP1??e’=2?y/ ?x=e + ?y/ ?x??e’=e + 2?y

PP2eP1e’Bresenham画线算法（7/11）

v先确定最大位移方向

v确定误差e的计算方法，并根据e确定在非最

大位移方向上如何走步

Bresenham画线算法（8/11）

v先确定最大位移方向??|k|<1时，x为最大位移方向??|k|>1时，y为最大位移方向v增1还是减1，取决于直线y增1x减1x减1yy增1x++x--x++y++x增1y++y++x

o(x0,y0)x增1x--x++y--y--y减1y减1所在象限

???x≥0时，s1=1,否则s1=-1???y≥0时，s2=1,否则s2=-1Bresenham画线算法（9/11）

v确定误差e的计算方法，并根据e确定在非最大位移方向上如何走步v误差初值的计算

??|k|<1时， e=2|?y| - |?x|??|k|>1时， e=2|?x| - |?y|