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

《计算机图像图形学-中点画线法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、中点画线法潘万鹏3.1.2中点画线法这里先讨论直线斜率在0～l之间。如图3.2所示，若直线在x方向上增加一个单位，则在y方向上的增量只能在0～1之间。假设直线上当前已确定的一个像素点坐标为(xp,yp)，用实心小圆表示。P=(xp,yp)P2P1MQ图3.2中点画线法示意图那么，下一个与直线最近的像素只能是正右方的P1(xp+1、yp)或右上方的P2(xp+1、yp+1)两者之一，用空心小圆表示。为了方便地确定出下一个像素是P1还是P2，设M为P1与P2的中点，即M=(xp+1,yp+0.5)。又设Q是理想直线与

2、垂直线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。因此，欲判断前述Q在M的上方还是下方，只要把M代入F(x，y)，

3、并判断它的符号。构造判别式d＝F(M)=F(xp+1,yp+0.5)=a(xp+1)+b(yp+0.5)+c当d>0时，M在直线上方（即在Q的上方），故应取右方的P1作为下一个像素。而当d<0，则应取右上方的P2。当d=0时，约定取右方P1。对每一个像素计算判别式d，根据它的符号确定下一像素。由于d是xp和yp的线性函数，可采用增量计算，以便提高运算效率。在d≥0的情况下，取正右方像素P1，欲判断再下一个像素应取那个，应计算d1=F(xp+2,yp+0.5)=a(xp+2)+b(yp+0.5)+c=(a(xp+1

4、)+b(yp+0.5)+c)+a=d+a故d的增量为a。在d<0时，取右上方像素P2。要判断再下一个像素，应计算d2=F(xp+2,yp+l.5)=a(xp+2)+b(yp+1.5)+c=(a(xp+1)+b(yp+0.5)+c)+a+b=d+a+b再看d的初始值。直线的第一个像素为左端点(x1,y1)，所以相应的判别式值为d0=F(x1+1,y1+0.5)=a(x1+1)+b(y1+0.5)+c=(ax1+by1+c)+a+0.5b=F(x1，y1)+a+0.5b由于(x1,y1)在直线上，故F(x1,y1)=

5、0。因此，d的初始值为d0=a＋0.5b。由于我们使用的只是d的符号，而且d的增量都是整数，只是其初始值包含小数。因此，我们可以用2d代替d，就可以写出仅包含整数运算的中点画线算法(斜率在0～l)：故d的增量为a＋b。voidMidpointLine(intx1,inty1,intx2,inty2,intcolor){intx,y,a,b,d1,d2,d;a=y1-y2;b=x2-x1;d=2*a+b;d1=2*a;d2=2*(a+b);x=x1;y=y1;putpixel(x,y,color);while(x<

6、x2){x=x+1;if(d<0){y=y+1;d+=d2;}else{d+=d1;}putpixel(x,y,color);}}3.2圆与椭圆的生成3.2.1圆的特性由于圆是图形和图像中经常使用的元素，因此在大多数图形软件中都包含有生成圆和圆弧的过程。也会提供一个既能显示圆曲线，又能显示椭圆曲线的绘图函数。圆被定义为所有离一中心位置(xc，yc)距离为给定值r的点集，可用如下方程表示：(x–xc)2+(y–yc)2=r2利用这个方程，我们可以沿x轴从xc–r到xc+r以单位步长计算对应的y值来得到圆周上每点的位

7、置：y=yc±但这并非是生成圆的最好方法。这个方法的一个问题是每一步包含很大的计算量。而且所画像素位置间的间距是不一致的，在靠近x轴的0°和180°处像素点之间的间距越来越大。当然可以在圆斜率的绝对值大于1后，交换x和y（即步进y值，计算x值）来调整间距。但这样增加了算法所需的计算量和处理过程。另一种消除不等间距的方法是使用极坐标r和θ计算沿圆周的点。以参数极坐标形式表示圆方程可得到方程组：x=xc+rcosθy=yc+rsinθ使用上述方法以固定角度为步长生成显示时，圆就可沿圆周等距点绘制出来。但这个方法使用了

8、三角函数调用和浮点运算，运算速度太慢。考虑到圆的对称性可以减少计算量。只要能生成8分圆，那么圆的其他部分可通过一系列的简单反射变换得到。如图3.4所示，假设已知一个圆心在原点的圆上一点(x，y)，根据对称性可得另外七个8分圆上的对应点(y,x),(y,–x),(x,–y),(–x,–y),(–y,–x),(–y,x),(–x,y)。因此，只需讨论8分圆的生成算法。另外，为