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

直线段扫描转换

v

假设

??像素间均匀网格，整数型坐标系，直线段斜率0

直线段的扫描转换算法

v直线的扫描转换?? 确定最佳逼近于该直线的一组象素??按扫描线顺序，对这些象素进行写操作

v三个常用算法：

1数值微分法（DDA）2中点画线法

3Bresenham算法。

数值微分(DDA)法(1/5)

已知线段端点：P0(x0,y0), P1(x1,y1)v直线方程

y=kx+b

{(xi, yi)}, i=0,….n.

v浮点数取整 : yi=round(yi)=(int)(yi+0.5)

v

??用到浮点数的乘法、加法和取整运算

数值微分(DDA)法(2/5)

v增量算法??yi+1=kxi+1+b=k(xi+1)+b=yi+k??(xi,yi)→(xi+1,yi+k)

v缺点：

??有浮点数取整运算??不利于硬件实现??效率低

??仅适用于?k? ≤1的情形:x每增加1,y最多增加1。

当 ?k? ?1时，必须把x，y互换。

数值微分(DDA)法(3/5)

vdigital differential analyzer

v基本思想??用数值方法解微分方程

dx/dt = ?xdy/dt = ?y

如何选取?？ xn+1 = xn + ??x yn+1 = yn + ??y 选取?的原则：使0.5≤|??x|,|??y|≤1