计算机图形学课件：4 圆的扫描转换.ppt

3.2 SCAN CONVERTING CIRCLES(圆的扫描转换)n仅考虑圆心在原点，半径为R(整数)的圆 对于圆心不在原点的圆,可通过平移获得. 如:若圆心在(xc,yc),可先计算圆心在原点的相同半径的圆上的点(x,y)，经变换(x+xc,y+yc)即可得到所要求的圆上的点.1(xc,yc)(x+ xc,y+ yc)(x,y)(x,y)x+ xc,y+ yc(x+ xc,y+ yc)SCAN CONVERTING CIRCLES2Representation of circle Original definition equivalent definitions v v v 3Inefficient algorithms4n在扫描转换时,仅考虑其在第一象限的第二个1/8圆.(x,y)原点(x,-y)(-x,y)(-x,-y)X轴Y轴y=x直线(y,x)(y,-x)(-y,x)(-y,-x)BAEight-Way Symmetry5Midpoint Circle Algorithm（1）n原理：Choices for next pixelChoices for current pixelP=(xk,yk)MSEMEMSEEPreviouspixel6n定义圆函数：n特点：n引入判别参数：Midpoint Circle Algorithm（2）7n算法描述： （假设X方向的步长为1）n?： how to calculate dk efficiently?Midpoint Circle Algorithm（3）8使用增量计算方法改进判别参数的计算效率Midpoint Circle Algorithm（4）Choices for next pixelChoices for current pixelP=(xk,yk)MSEMEMSEEPreviouspixel9Midpoint Circle Algorithm（5）Choices for next pixelChoices for current pixelP=(xk,yk)MSEMEMSEEPreviouspixel10Midpoint Circle Algorithm（6）判别参数d的递推公式如下：初值： 关于计算效率的考虑: eliminate the fraction11n考虑：点的选择只与判别量的符号相关引入：Midpoint Circle Algorithm（7）•递推公式中其它与d有关的式子可把d直接换成pk。

•由于pk的初值为整数，且在运算过程中的增量也是整数，故pk始终是整数，所以pk <-0.25等价于pk <012Midpoint Circle Algorithm（8）例：Center（0，0），r＝813Midpoint Circle Algorithm（9）迭代必须满足点的坐标xx){ if(d<0){ d+=delta1; delta2+=2; } else{ d+=delta2; delta2+=4; y--} delta1+=2; x++; putpiexl(x,y,color); putotherpiexl(x,y,color); }//while}//endMidpoint Circle Algorithm（12）17Bresenham画圆算法18Bresenham Algorithm（1）Choices for next pixelChoices for current pixelP=(xi,yi)MSEMEMLHPreviouspixel问题：问题：在P点已确定的前提下，当前需要在点H和点L中选择。

思想：思想：用两点到圆弧的距离的远近来判别选哪个点定义两个候选点到圆弧的距离平方差为：19Bresenham Algorithm（2）构造判别参数：(1)在圆弧的两侧(2)D(H)>0 , D(L)<0(3)因此，当d≥ 0时，选L点(4)当d<0时，选H点Choices for next pixelChoices for current pixelP=(xi,yi)MSEMEMLHPreviouspixelH，L点的分布只有三种情况：在圆弧的两侧；同在圆弧的内侧；在圆弧的两侧；同在圆弧的内侧；同在圆弧的外侧同在圆弧的外侧20Bresenham Algorithm（3）(2)同在圆弧外侧D(H)>0 , 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点；点； 当当d<0时，选时，选H点点21圆的内接正多边形迫近法22基础知识（1）--三角函数23基础知识（2）--矩阵表示表达式：可写成矩阵形式：24基础知识（3）--矢量及其运算25圆的内接正多边形迫近法(1)内接正n边形顶点为图4-6圆的多边形迫近由图可知，pi的幅角为θ i ，则26圆的内接正多边形迫近法(2)n使用增量计算确定多边形顶点：同理:27圆的内接正多边形迫近法(3)上述递推公式可用矩阵形式表示为：其中，α是常数，计算一个顶点只需四次乘法。

采用这种方法扫描转换圆弧只需4n次乘法，外加用中点算法生成长度约为2πR的直线段的计算量28圆的内接正多边形迫近法(4)29圆的内接正多边形迫近法(5)n改进的增量计算：求一个顶点只做两次乘法，但需使用两个初始点pB30。