计算机图形学-圆弧的生成.ppt

计算机图形学 计算机图形学 中原工学院理学院 4.3.1圆弧的生成 判别式d： d的初始值为： 在d≥0的情况下，取右下方像素 ， 在d0的情况下，取正右方像素 ， Bresenham画圆算法是最有效的算法之一。 Bresenham画圆算法的基本原理是如下图所示，若 为已经选定的点，那么下一个可能的像素点为其正右方的点 或右下方的点 。若 到圆弧的距离小于 到圆弧的距离，则取 ，反之取 。 Thank you ! * 1. 数值微分法（DDA法） 2. 中点画圆算法 3. Bresenham画圆算法 4. 正负法 与直线的生成类似，圆的生成算法的好坏将直接影响到绘图的效率。本节仅讨论圆心位于坐标原点的圆弧生成算法，对于圆心为任意的圆弧，可以先将其平移到原点，然后光栅化，再平移到原来的位置。 圆弧的DDA算法和直线段DDA法类似，也是根据圆弧的微分方程来实现的，我们以圆心在坐标系原点，半径为R的一段圆弧为例来讨论。 圆心在原点（0，0），半径为R的方程为： 1、数值微分法（DDA法） 它的微分方程为： 若令 即可得离散变量微分方程式为： 式中： 为一很小的常数。若设 为用DDA法顺 时针画第一象限的圆弧在X,Y方向的增量值，由上式可知，则有： (4-1) 用矩阵表示为： (4-2) 但是，由式(4-1)得： 所以式(4-1)表示的并不是一个圆，而是一个半径逐渐增大的螺旋线。要得到圆的方程，需要使式(4-2)中系数矩阵行列式值为1.即将式(4-2)中的 变为1。若取 即能满足要求。即有： 也即： (4-3) 由(4-3)可知，在计算时我们不用 的结果，而是 直接引用 的值。 2、中点画圆算法 假设x坐标为 的各像素点中，与该圆弧最近者已确定， 为 ,那么，下一个与圆弧最近的像素只能 是正右方的 ，或右下方的 两者之一。令M为 和 的中点，易知M的坐标为 。显然，若M在圆内，则 离圆弧 近，应取为下一个像素；否则应取 。 为了消除在计算判别式初始值产生的浮点数运算，将用 4d来代替d。 下述程序使用中点画圆算法绘制一个1/8圆弧。 void MidPointCircle(int r,int color) { int x,y,d x=0; y=r; d=5-4r; CirclePoint(x,y,color); while(x=y) { if(d=0) d+=8x+12; else { d+=8(x-y)+20;y--; } x++; CirclePoint(x,y,color); } } 3. Bresenham画圆算法 设R为圆弧的半径，记P（x,y）到原点的距离的平方 与圆的半径的平方之差为D（P），即 令 则 下面给出 的递推公式。 当 0时，点 做为下一个像素点 ,故 当 ≥0时，点 做为下一个像素点 ,故 根据算法，可得Bresenham生成圆弧的程序如下： void bresenham_arc(int R,int color) { int x,y,d; x=0;y=R; d=3-2*R; while(xy) { putpixel(x,y,color); if(d0) d+=4*x+6; else { d+=4*(x-y)+10; y-=1; } x++; } if(x==y) putpixel(x,y,color); } 4. 生成圆弧的正负法 原理： 设圆的方程为 ; 假设求得 的坐标为 ； 则当 在圆内时，有 ； 当 在圆外时，有