圆的扫描转换.ppt

圆与椭圆的生成 第六讲 知识回顾 扫描转换 将连续图形以最小误差近似于光栅网格点（离散化）的过程 必要性 要求 直线的扫描转换 DDA算法 Bresenham算法 DDA算法 直线方程 y=kx+b 增量思想 xi+1=xi+1 yi+1=yi+k y值是浮点数 四舍五入运算 算法改进 选点规则 Bresenham算法——距离差——符号 增量思想 内容提要 圆的扫描转换 中点圆算法 Bresenham算法 椭圆的扫描转换 中点椭圆算法 问题 圆的扫描转换 圆 给定圆心位置和半径 圆的方程 考虑圆心在原点的圆 x2+y2=R2 圆的参数方程 一个像素宽 直接的扫描转换方法 利用圆的参数方程 SetPixel(Round(x),Round(y),color) 存在的问题 需要调用三角函数,涉及浮点运算 使用较小的 ? 能避免缝隙, 但对不同的半径难于确定不同的? . 直接的扫描转换方法 直接利用圆的方程 四分之一圆 x按单位步长变化 存在问题 需要乘法、平方根及四舍五入运算 点间距不均匀，存在较大缝隙 圆的八方向对称性 void CirclePoints (int x, int y, COLORREF color) { SetPixel(x,y,color); SetPixel(y,x,color); SetPixel(-y,x,color); SetPixel(x,-y,color); SetPixel(-x,-y,color); SetPixel(-y,-x,color); SetPixel(y,-x,color); SetPixel(-x,y,color); } 圆的八方向对称性 考虑45°圆弧(八分之一圆弧) 半径R为整数 From x=0 to ? while(y=x) 圆的扫描转换 间距问题 对称性 乘法、平方根及四舍五入运算 ？ 乘法、平方根用于求y 四舍五入用于确定y增0或-1 直线的扫描转换 中点画线法、Bresenham算法 有两个像素待选 位置相对固定 圆的扫描转换算法 最接近圆的像素序列 x每次增1 E、NE哪点离圆更近？ 中点算法 Bresenham算法 中点圆算法 标记 参照点——中点M 候选像素E、SE 位置判定 中点圆算法 判定标准 中点M位于圆的哪一侧 M在圆内 取E点 M在圆外 取SE点 M在圆上 取SE点 中点圆算法 问题 如何判定中点M与圆的位置关系？ 位置关系判别方法 圆的隐式函数 F(x,y)=x2+y2-R2=0 点和圆的位置判定 F(x,y)=0——点在圆上 F(x,y)0——点在圆外 F(x,y)0——点在圆内 判别方法 判定变量 d=F(M)=F(xp+1,yp-1/2) d0 M在圆外——取SE d0 M在圆内——取E d=0 M在圆上——E、NE均可 取SE 判定变量的变化 d0,取E点 dold=F(xp+1,yp-1/2) =(xp+1)2+(yp-1/2)2-R2 Pnew(xp+1,yp) M(xp+2,yp-1/2) dnew=F(xp+2,yp-1/2) =(xp+2)2+(yp-1/2)2-R2 dnew=dold+2xp+1+1 incrE=2xp+1+1 判定变量的变化 d≥0,取SE点 dold=F(xp+1,yp-1/2) =(xp+1)2+(yp-1/2)2-R2 Pnew(xp+1, yp-1) M (xp+2, yp-3/2) dnew=F(xp+2,yp-3/2) =(xp+2)2+(yp-3/2)2-R2 dnew= dold+2xp-2yp+5 △SE=2xp+1-2yp+1+1 循环 初始化 初始点 P(0,R) 中点 M(1,R-1/2) 判定变量 dstart=F(M)=F(1,R-1/2)=5/4-R 修正判定变量——整数运算 h=d-1/4 ——d=h+1/4 h=1-R d0——h1/4——h0 中点圆算法 Void MidpointCircle (int radius, COLORREF color) { int x=0; y=radius;d=1-radius; CirclePoints(x, y, color); while (y = x) { if (d 0) d += 2*x+3; /* 选择 E */ else { d +=2*(x-y)+5; /* 选择 SE */ y--; } x++; CirclePoints(x, y, color); } } 中点圆算法画任意圆 Void MidpointCircle (int xc, int yc, int radi