《计算机图形学教学资料4.ppt》由会员分享,可在线阅读,更多相关《计算机图形学教学资料4.ppt(30页珍藏版)》请在优知文库上搜索。
1、13.2 SCAN CONVERTING CIRCLES(圆的扫描转换)n仅考虑圆心在原点,半径为R(整数)的圆 对于圆心不在原点的圆,可通过平移获得.如:若圆心在(xc,yc),可先计算圆心在原点的相同半径的圆上的点(x,y),经变换(x+xc,y+yc)即可得到所要求的圆上的点.2(xc,yc)(x+xc,y+yc)(x,y)(x,y)x+xc,y+yc(x+xc,y+yc)SCAN CONVERTING CIRCLES3Representation of circleRyyxx2020)()(Original definition equivalent definitions v v v
2、 )offset),(00222yxRyx22xRy2,0sincosRyRx4Inefficient algorithms,.,1,022RxxRy5n在扫描转换时,仅考虑其在第一象限的第二个1/8圆.(x,y)原点(x,-y)(-x,y)(-x,-y)X轴Y轴y=x直线(y,x)(y,-x)(-y,x)(-y,-x)BAEight-Way Symmetry6Midpoint Circle Algorithm(1)n原理:0181k:圆弧上的切线斜率满足在上Choices for next pixelChoices for current pixelP=(xk,yk)MSEMEMSEEPre
3、viouspixel7n定义圆函数:f x yxyr(,)222f x yx yx yx y(,)(,)(,)(,)000位于圆边界内位于圆边界上位于圆边界外)21,1()(kkkyxfMfdn特点:n引入判别参数:Midpoint Circle Algorithm(2)8n算法描述:(假设X方向的步长为1)),1(E0)1,1(0kkkkkkyxdyxSEd点为:时,下一点应取当;点为:时,下一点应取当n?:how to calculate dk efficiently?Midpoint Circle Algorithm(3)222)5.0()1(ryxdiik9使用增量计算方法改进判别参数
4、的计算效率Midpoint Circle Algorithm(4)Choices for next pixelChoices for current pixelP=(xk,yk)MSEMEMSEEPreviouspixel3232)5.0()1()5.0(1)1()5.0,2(2222221kkkkkkkkkkxdxryxryxyxfd)5.0,2(M),1E(0d)1(Ekkkkkyxyx下次中点为,则时,选点当10Midpoint Circle Algorithm(5)Choices for next pixelChoices for current pixelP=(xk,yk)MSEME
5、MSEEPreviouspixel)5.1,2(M)1,1E(0d)2(SEkkkkkyxyxS则下次中点为,时,选点当5)(25)(2)5.0()1(1)5.0(1)1()5.1,2(2222221kkkkkkkkkkkkyxdyxryxryxyxfd11Midpoint Circle Algorithm(6)判别参数d的递推公式如下:初值:0)11(5)(20)1(321kkkkkkkkkkkkdyxyxddyxxdd,选,选递推公式:rrfd25.1)5.0,1(ry0 x000,关于计算效率的考虑:eliminate the fraction12n考虑:点的选择只与判别量的符号相关引入
6、:rprd125.100对应:初值:25.0kkdp25.00kkpd对应于判别式Midpoint Circle Algorithm(7)递推公式中其它与d有关的式子可把d直接换成pk。由于pk的初值为整数,且在运算过程中的增量也是整数,故pk始终是整数,所以pk-0.25等价于pk 0。13opypyyxxppyxppxpprpkkkkkkkkkkkkkkkk10105)(203211110算法:为决策参数的中点画圆则以结论:Midpoint Circle Algorithm(8)例:Center(0,0),r814Midpoint Circle Algorithm(9)迭代必须满足点的坐标
7、xytimexypkPutpixel(x,y)008-7(0,8)118-4(1,8)2281(2,8)337-6(3,7)4473(4,7)5562(5,6)6655 15n提高计算效率,321kkxd令类似地:310d初值:rd2520初值:Midpoint Circle Algorithm(10)5)(22kkkyxd则21kkddddd,x=x+1,y=y-1,x=x+1,y=y0d当0d当22)32(3)1(23211111kkkkkdxxxd040221212dddddkkk16Midpoint Circle Algorithm(11)xdyd1d2x+1dx)if(d0 ,D(L
8、)0因此,当d 0时,选L点当d0 ,D(L)0此时,d 0,选L点(3)同在圆弧内侧D(H)0 ,D(L)0此时,d 0,选H点Choices for next pixelChoices for current pixelP=(xi,yi)MSEMEMLHPreviouspixel因此,三种情况可统一写为:因此,三种情况可统一写为:当当d 0时,选时,选L点;点;当当d0时,选时,选H点点22圆的内接正多边形迫近法23基础知识(1)-三角函数sincosryrx),(yxprsincoscossin)sin(sinsincoscos)cos(24基础知识(2)-矩阵表示vducyvbuax表
9、达式:可写成矩阵形式:vudcbayx25基础知识(3)-矢量及其运算abcacbcba),(yxPijj yi xPyxP26圆的内接正多边形迫近法(1)222ryx定义圆的方程:内接正n边形顶点为niyxpiii,.,1,0),(ip1ipi图4-6圆的多边形迫近iiiiryrxsincos由图可知,pi的幅角为 i,则27圆的内接正多边形迫近法(2)n使用增量计算确定多边形顶点:sincos)cos(1iiiiyxrx同理:cossin)sin(1iiiiyxryip1ipi28圆的内接正多边形迫近法(3)上述递推公式可用矩阵形式表示为:iiiiyxyxcossinsincos11其中,是常数,计算一个顶点只需四次乘法。采用这种方法扫描转换圆弧只需4n次乘法,外加用中点算法生成长度约为2R的直线段的计算量。29圆的内接正多边形迫近法(4)2nn确定:由夹角顶点数值:则大距离多边形与圆弧之间的最为指定逼近误差值和边数如何确定)(:ndd2cosrrdrrarccos230圆的内接正多边形迫近法(5)n改进的增量计算:求一个顶点只做两次乘法,但需使用两个初始点1cos21iipOpOipO显然:1111cos2iiiiiiyxyxyx亦即:ip1ip1ipOpB