图形学课件4章节
1,3.2 SCAN CONVERTING CIRCLES (圆的扫描转换),仅考虑圆心在原点，半径为R(整数)的圆 对于圆心不在原点的圆,可通过平移获得. 如:若圆心在(xc,yc),可先计算圆心在原点的相同半径的圆上的点(x,y)，经变换(x+xc,y+yc)即可得到所要求的圆上的似点.,2,(xc,yc),SCAN CONVERTING CIRCLES,3,Representation of circle,Original definition,equivalent definitions,4,Inefficient algorithms,5,在扫描转换时,仅考虑其在第一象限的第二个1/8圆.,(x,y),原点,(x,-y),(-x,y),(-x,-y),X轴,Y轴,y=x直线,(y,x),(y,-x),(-y,x),(-y,-x),Eight-Way Symmetry,6,Midpoint Circle Algorithm（1）,原理：,7,定义圆函数：,特点：,引入判别参数：,Midpoint Circle Algorithm（2）,8,算法描述： （假设X方向的步长为1）,?： how to calculate dk efficiently?,Midpoint Circle Algorithm（3）,9,使用增量计算方法改进判别参数 的计算效率,Midpoint Circle Algorithm（4）,10,Midpoint Circle Algorithm（5）,11,Midpoint Circle Algorithm（6）,判别参数d的递推公式如下： 初值：,关于计算效率的考虑: eliminate the fraction,12,考虑：点的选择只与判别量的符号相关 引入：,Midpoint Circle Algorithm（7）,递推公式中其它与d有关的式子可把d直接换成pk。 由于pk的初值为整数，且在运算过程中的增量也是整数，故pk始终是整数，所以pk -0.25等价于pk 0。,13,Midpoint Circle Algorithm（8）,例：Center（0，0），r8,14,Midpoint Circle Algorithm（9）,迭代必须满足点的坐标xy,15,提高计算效率,类似地：,Midpoint Circle Algorithm（10）,则, x=x+1, y=y-1, x=x+1, y=y,16,Midpoint Circle Algorithm（11）,以上结论可归结为下表,作业：按上述表格法，画圆心在（5,7），半径为11的圆在第一象限的部分。,17,Void MidPointCircle(int r, int color) int x,y,d; x=0;y=r;d=1-r; delta1=3;delta2=5-2r; drawpiexl(x,y,color); while(yx) if(d0) d+=delta1; delta2+=2; else d+=delta2; delta2+=4; y- delta1+=2; x+; putpiexl(x,y,color); putotherpiexl(x,y,color); /while /end,Midpoint Circle Algorithm（12）,18,Bresenham画圆算法,19,Bresenham Algorithm（1）,问题：在P点已确定的前提下，当前需要在点H和点L中选择。 思想：用两点到圆弧的距离的远近来判别选哪个点。 定义两个候选点到圆弧的距离平方差为：,20,Bresenham Algorithm（2）,构造判别参数：,在圆弧的两侧 D(H)0 , D(L)0 因此，当d 0时，选L点 当d0时，选H点,H，L点的分布只有三种情况：在圆弧的两侧；同在圆弧的内侧；同在圆弧的外侧。,21,Bresenham Algorithm（3）,(2)同在圆弧外侧 D(H)0 , D(L)0 此时，d 0，选L点 (3)同在圆弧内侧 D(H)0 , D(L)0 此时，d 0，选H点,因此，三种情况可统一写为： 当d 0时，选L点； 当d0时，选H点,22,圆的内接正多边形迫近法,23,基础知识（1）-三角函数,24,基础知识（2）-矩阵表示,表达式：,可写成矩阵形式：,25,基础知识（3）-矢量及其运算,26,圆的内接正多边形迫近法(1),内接正n边形顶点为,图4-6圆的多边形迫近,由图可知，pi的幅角为 i ，则,27,圆的内接正多边形迫近法(2),使用增量计算确定多边形顶点：,同理:,28,圆的内接正多边形迫近法(3),上述递推公式可用矩阵形式表示为：,其中，是常数，计算一个顶点只需四次乘法。 采用这种方法扫描转换圆弧只需4n次乘法，外加用中点算法生成长度约为2R的直线段的计算量。,29,圆的内接正多边形迫近法(4),30,圆的内接正多边形迫近法(5),改进的增量计算：求一个顶点只做两次乘法，但需使用两个初始点,B,
