计算机图形学教学资料4.ppt
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 )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)MSEMEMSEEPreviouspixel7n定义圆函数：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使用增量计算方法改进判别参数的计算效率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)MSEMEMSEEPreviouspixel)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考虑：点的选择只与判别量的符号相关引入：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）迭代必须满足点的坐标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)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表达式：可写成矩阵形式：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
