计算机图像图形学-中点画线法.ppt

中点画线法 潘万鹏 3.1.2 中点画线法 这里先讨论直线斜率在0l之间。如图3.2所示，若直线在x方向上增加一 个单位，则在y方向上的增量只能在01之间。假设直线上当前已确定的一个 像素点坐标为(xp,yp)，用实心小圆表示。 P=(xp,yp) P2 P1 M Q 图3.2 中点画线法示意图 那么，下一个与直线最近的像 素只能是正右方的P1(xp+1、yp)或右 上方的P2(xp+1、yp+1)两者之一，用 空心小圆表示。 为了方便地确定出下一个像素是P1还是P2，设M为P1与P2的中点，即 M=(xp+1, yp+0.5)。又设Q是理想直线与垂直线 x = xp+l的交点。显然，若M在Q 的上方，则P1离直线近，应取为下一个像素；否则应取P2。这种以中点M作为 判别标志的方法就是中点画线算法。 下面来讨论中点画线法的具体实现。 直线方程为：F (x, y)= ax + by + c 0 假设直线的起点和终点分别为(x1,y1)和(x2,y2)，则上述参数：a = y1 - y2，b = x2 - x1，c = x1y2 - x2y1。 对于直线上的点，F(x,y)= 0；对于直线上方的点，F(x,y)0；而对于直线 下方的点，F(x，y)0时，M在直线上方（即在Q的上方），故应取右方的P1作为下一个 像素。而当d0时，M在圆外，这说明P2距离圆弧更近，应取P2作为下一 像素。而当F(M)0；而对于圆内的点， F (x, y)=0，取右下方像素，yi+1= yi-1，则： di+1=2(xi+1+1)2+(yi-1)2+(yi-1-1)2-2r2= di+4(xi-yi)+10 由此，可写出Bresenham画圆算法的C程序： void BresenhamCircle (int xc, int yc, int r, int color) int x =0, y =r, d=3-2*r; while (x 0 说明(x, y)在椭圆边界外 由于椭圆的对称性，我们只要讨论第一象限椭圆弧的生成。在处理这段 椭圆弧时，我们进一步把它分为两部分：上部分和下部分。 以弧上斜率为1的点作为分界，如图3.7(P83)所示。在上部分，在x方向 取单位步长，确定下一像素的位置；在斜率小于1的下部分，在y方向取单位 步长来确定下一像素的位置。 椭圆的斜率可从方程(36)中计算出： dy / dx = 2b2x / 2a2y 在上部分和下部分的交界处, 斜率dy/dx= 1, 则上式变为： 2b2x = 2a2y 因此，从上部分变为下部分的条件是： 2b2x = 2a2y 与中点画圆算法类似，当我们确定一个像素之后，接着在两个候选像素 的中点计算一个判别式的值。并根据判别式符号确定两个候选像素哪个离椭 圆更近。下面讨论算法的具体步骤。先看椭圆弧的上部分。假设当前已确定 的椭圆弧上的像素点为(xp,yp)，那么下一对候选像素的中点是(xp+l,yp 0.5) 。 因此判别式为 dp = F(xp+1, yp0.5)= b2(xp+1)2 + a2(yp0.5)2 a2b2 它的符号将决定下一个像素是取正右方的那个，还是右下方的那个。 若dp 0) y ; dy = twoaa; if (d 0 ) d += aa dy