计算机图像图形学-中点画线法.ppt
《计算机图像图形学-中点画线法.ppt》由会员分享,可在线阅读,更多相关《计算机图像图形学-中点画线法.ppt(31页珍藏版)》请在三一办公上搜索。
1、中点画线法,潘万鹏,3.1.2 中点画线法,这里先讨论直线斜率在0l之间。如图3.2所示,若直线在x方向上增加一个单位,则在y方向上的增量只能在01之间。假设直线上当前已确定的一个像素点坐标为(xp,yp),用实心小圆表示。,图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。这
2、种以中点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),并判断它的符号。,构造判别式 dF(M)=F(xp+1,yp+0.5)=a(xp+1)+b(yp+0.5)+c,当 d0时,M在直线上方(即在Q的上方),故应取右方的P1作为
3、下一个像素。而当d0,则应取右上方的P2。当d=0时,约定取右方P1。,对每一个像素计算判别式d,根据它的符号确定下一像素。,由于d是xp和yp的线性函数,可采用增量计算,以便提高运算效率。,在d0的情况下,取正右方像素P1,欲判断再下一个像素应取那个,应计算 d1=F(xp+2,yp+0.5)=a(xp+2)+b(yp+0.5)+c=(a(xp+1)+b(yp+0.5)+c)+a=d+a故d的增量为a。,在d0时,取右上方像素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
4、+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)=0。因此,d的初始值为d0=a0.5b。,由于我们使用的只是d的符号,而且d的增量都是整数,只是其初始值包含小数。因此,我们可以用2d代替d,就可以写出仅包含整数运算的中点画线算法(斜率在0l):,故d的增量为ab。,void MidpointLine(int x1,int y1,int x2,int y2,int co
5、lor)int x,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(xx2)x=x+1;if(d0)y=y+1;d+=d2;else d+=d1;putpixel(x,y,color);,3.2 圆与椭圆的生成,3.2.1 圆的特性,由于圆是图形和图像中经常使用的元素,因此在大多数图形软件中都包含有生成圆和圆弧的过程。也会提供一个既能显示圆曲线,又能显示椭圆曲线的绘图函数。,圆被定义为所有离一中心位置(xc,yc)距离为给定值r的点集,可用如下方程表示:(x
6、xc)2+(y yc)2=r 2,利用这个方程,我们可以沿x轴从xcr到xc+r以单位步长计算对应的y值来得到圆周上每点的位置:y=yc,但这并非是生成圆的最好方法。这个方法的一个问题是每一步包含很大的计算量。而且所画像素位置间的间距是不一致的,在靠近x轴的0和180处像素点之间的间距越来越大。当然可以在圆斜率的绝对值大于1后,交换x和y(即步进y值,计算x值)来调整间距。但这样增加了算法所需的计算量和处理过程。,另一种消除不等间距的方法是使用极坐标r和计算沿圆周的点。以参数极坐标形式表示圆方程可得到方程组:x=xc+r cos y=yc+r sin,使用上述方法以固定角度为步长生成显示时,圆
7、就可沿圆周等距点绘制出来。但这个方法使用了三角函数调用和浮点运算,运算速度太慢。,考虑到圆的对称性可以减少计算量。只要能生成8分圆,那么圆的其他部分可通过一系列的简单反射变换得到。,如图3.4所示,假设已知一个圆心在原点的圆上一点(x,y),根据对称性可得另外七个8分圆上的对应点(y,x),(y,x),(x,y),(x,y),(y,x),(y,x),(x,y)。因此,只需讨论8分圆的生成算法。,另外,为了方便起见,我们只考虑中心在原点,半径为整数R的圆x2y2=R2。对于中心不在原点的圆,可先通过平移变换,化为中心在原点的圆,再进行扫描转换,把所得的像素坐标加上一个位移量即得所求像素坐标。,图
8、3.4 圆的对称性,3.2.2 中点画圆法,由于圆的对称性,下面主要考虑中心在原点半径为r的圆的第二8分圆。若从圆的正上方开始讨论如何确定最佳逼近于该圆弧的像素序列。,图3.5 中点画圆法示意图,假定当前已确定了圆弧上的一个像素点为P(xp,yp),那么,下一个像素只能是正右方的P1(xp+1,yp)或右下方的P2(xp+1,yp1)两者之一。如图3.5所示。,那么,当F(M)0时,M在圆外,这说明P2距离圆弧更近,应取P2作为下一像素。而当F(M)0时,P1离圆弧更近,应取P1。当F(M)=0时,在P1与P2之中随便取一个即可,约定取P2。,对于圆上的点,F(x,y)=0;对于圆外的点,F(
9、x,y)0;而对于圆内的点,F(x,y)0。与中点画线法类似,设M是P1和P2的中点,即M=(xp+1,yp 0.5)。,构造函数:F(x,y)=x2y2 r2(35),若d0,则应取P1为下一像素,而且再下一个像素的判别式为 d=F(xp+2,yp 0.5)=(xp+2)2+(yp 0.5)2 R2=d+2xp+3所以,沿正右方向,d的增量为2xp+3。,与中点画线法一样,构造判别式 d=F(M)=F(xp+1,yp 0.5)=(xp+1)2+(yp 0.5)2 r2,而若d0,则P2是下一像素,而且下一像素的判别式为 d=F(xp+2,yp 1.5)=(xp+2)2+(yp 1.5)2 R
10、2=d+(2xp+3)+(2yp+2)所以,沿右下方向,判别式d的增量为2(xpyp)+5。,再来看看d的初始值d0。由于我们从圆的正上方开始,因此第一像素是(0,r),判别式d的初始值为:d0=F(l,r 0.5)=1+(r 0.5)2 r2=1.25 r,由于上述公式中只有d0包含小数,而它又仅仅作为一个判别式,因此可以做一些特殊处理来摆脱浮点数,在算法中全部使用整数。,若用e=d 0.25代替d,则d0=l.25 r 对应于e0=1 r。判别式d0对应于e 0.25。算法中其他与d有关的式子可把d直接换成e。这样,就可以写出完全用整数实现的中点画圆算法。算法中e仍用d来表示。,以下是中点
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 计算机 图像 图形学 中点 画线

链接地址:https://www.31ppt.com/p-6606232.html