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

中点画圆法（2/2）

若 d<0, 取P1为下一象素，再下一象素的判别式为

若d>=0, 取P2为下一象素，再下一象素的判别式为

初始象素是（0,R），判别式d的初值为

P1(Xp+1,Yp)

使用e=d-0.25代替de0=1-R

P2(Xp+1,Yp-1)

DDA画圆法（1/3）

222v圆的方程：f(x,y)=x+y-R=0

v全微分：df(x,y)=2xdx+2ydy=0v微分方程：dy/dx=-x/yv递推方程:

(yn+1-yn)/ (xn+1-xn)=-?xn/ ?yn xn+1 - xn = ?yn yn+1 - yn = -?xn

实际画出的曲线不是圆，而是螺旋线，为什么？DDA画圆法（2/3）

v

将递推公式写成矢量形式：

v

构造一个行列式值为1的矩阵

对应的圆方程递推关系为 xn+1 = xn + ?yn

yn+1 = -?xn +(1-?2)yn= yn- ?xn+1

v

DDA画圆法（3/3）

v针对不同象限及顺逆时针画圆，赋给?适当的

符号

v ?不同，圆形状不同， ?大近似椭圆

Bresenham画圆算法（1/7）

v顺时针画第一四分圆，下一步选择哪个点？v基本思想：

??通过比较像素与圆的距离平方来避免开方运算v下一像素有3种可能的选择222??mH=|(xi+1)+yi-R|

??mD=|(xi+1)2+(yi-1)2-R2|??mV=|xi2 +(yi-1)2-R2 |

v选择像素的原则②Pi(xi,yi)H(xi+1,yi)①④V③D(x+1,y-1)ii(xi,yi-1)⑤??使其与实际圆弧的距离平方达到最小