光栅图形生成算法.ppt
《光栅图形生成算法.ppt》由会员分享,可在线阅读,更多相关《光栅图形生成算法.ppt(53页珍藏版)》请在三一办公上搜索。
1、Ch3 光栅图形生成算法,光栅显示器显示的图形是用一系列紧靠该图形路径的像素表示的。,确定哪些像素能构成所需图形的过程称为图形的光栅化(也称光栅图形生成算法),或称为图形的扫描转换。,本章讨论内容,直线生成算法圆和圆弧的程序设计区域填充算法字符生成反走样技术,直线生成算法,直线是最基本的图元,曲线由一系列直线段逼近,复杂图形可看作是由无数直线段组成的。直线生成质量影响计算机图形设计的质量。因此,光栅化直线生成算法必须服从四条原则:直而光滑、端点准确、亮度均匀、速度快。,直线生成算法,逐点比较法 绘图仪常用的一种方法。在每次画图过程中,绘图笔每画一笔,就与规定的图形进行比较,然后决定下一步的走向
2、,用步步逼近的方法画出规定的图形。,X,Y,O,假设以坐标原点作为直线起点,各象限中画笔走向如图所示。,逐点比较法,一般公式:要画的线段为OA,画笔的当前的位置为M。以OM,OA的斜率的大小来计算偏差。d=tg-tg=ym/xm-ya/xa=(ym*xa-ya*xm)/xm*xa;,(1)偏差计算(以第一象限为例),当d=0时,表示笔在OA线段的上方,应该走+x一步。只判断d的正负,不管大小,第一象限xm,xa均为正。,第一象限偏差的判断公式:Fm=ym*xa-ya*xm,X,Y,O,A(xA,yA),M(xM,yM),逐点比较法,递推公式:上述公式要计算两次乘法,设法用前一点的偏差来推算走步
3、的方向以及走步后的偏差.,(1)偏差计算,笔的当前位置为Mi(xi,yi),此时Fi=yixa-yaxi.,如果Fi0,应走+y一步到Mi+1,即:xi+1=xi,yi+1=yi+1;Mi+1处的偏差Fi+1=yi+1xa-yaxi+1=yixa+xa-yaxi=Fi+xa;,如果Fi=0,应走+x一步到Mi+1,即:xi+1=xi+1,yi+1=yi;Mi+1处的偏差Fi+1=yi+1xa-yaxi+1=yixa-yaxi-ya=Fi-ya;,如果 Fi=0 则走+x一步,此时Fi+1=Fi-ya;如果 Fi0 则走+y一步,此时Fi+1=Fi+xa;,逐点比较法,设步距为t,直线在x,y方
4、向的增量分别为x 和y.按上述运算方法,绘图笔从直线的起点画到终点,在x方向应走|x/t|步,在y方向应走|y/t|步.取n=|x/t|+|y/t|作为终点判断的控制数,并将此数存入计数器内.在x或y方向上每走一步计数器减1,当计数器减到零时,作图停止.,(2)终点判断,直线生成算法,Bresenham直线生成算法,基本原理:沿某一计长方向上,每次变化一个单位步长,另一方向上的变化量通过计算获得。这种方法在计算判别式时,计算量很小,生成的直线光滑,因而应用广泛。假设直线的斜率在01之间,k=y/x,x的变化率比y的变化率大,约定每次x方向变化一个像素单位,相应y方向的变化量为0或1个像素单位。
5、,Bresenham直线生成算法,已知直线起点(x1,y1),终点(x2,y2);直线上第i个像素为P(xi,yi),它是已经选定的离直线最近的当前像素。现在要决定下一个像素是S(xi+1,yi),还是T(xi+1,yi+1)?若s=t,则选择T。,P(xi,yi),Q(x,y),计算判别式:理论直线上点Q坐标为y=k(xi+1)+b;求s和t:s=y-yi=k(xi+1)+b-yi;t=(yi+1)-y=(yi+1)-k(xi+1)-b,s,t,P(xi,yi),S(xi+1,yi),T(xi+1,yi+1),计算判别式:理论直线上点Q坐标为y=k(xi+1)+b;求s和t:s=y-yi=k
6、(xi+1)+b-yi;t=(yi+1)-y=(yi+1)-k(xi+1)-b,则 s-t=2k(xi+1)-2yi+2b-1由于k=yx,x=x2-x1,y=y2-y1,代入上式,得到 x(s-t)=2yxi-2xyi+(2y-x+2bx)(3-1)记di=x(s-t),x0,di与(s-t)同号;di值符号为选择下一个像素的判别因子。为得到di的递推形式,以i+1代入式(3-1)的i,得 di+1=2yxi+1-2xyi+1+(2y-x+2bx)(3-2),计算判别式:,将(3-2)减去(3-1),且xi+1=xi+1,得 di+1=di+2y-2x(yi+1-yi)(3-3)其中,yi+
7、1-yi=0或1取决于判别因子di值的符号。如果di0,取S为下一像素,即xi+1=xi1,yi+1=yi,有 di+1=di+2y(3-4)如果di0,取T为下一像素,即xi+1=xi+1,yi+1=yi+1,有 di+1=di+2y-2x(3-5)将y1=kx1+b代入式(3-1),得di初始值:d0=2y-x(3-6),Bresenham画线算法流程,|m|1的Bresenham画线算法输入线的两个端点,并将左端点存贮在(x0,y0)中;将(x0,y0)装入帧缓冲器,画第一个点;计算常量:x、y、2y和2y-2x,并得到决策参数的第一个值:p0=2yx;从k=0开始,在沿线的每个xk处,
8、进行下列检测:假如pk0,画下一个点(xk+1,yk),且:pk+1=pk+2y;否则,下一个待画点(xk+1,yk+1),且:pk+1=pk+2y-2x。k=k+1;重复步骤4,共x次。,像素生成过程,该算法仅涉及整数加法运算和乘2(左移)操作,运算效率高,易于硬件实现。与逐点比较法相比,生成的直线光滑。若将该算法的范围扩大到整个平面,相应的d增量式及其初始值,以及下一像素位置的取法道理相似,请思考!,本章讨论内容,直线生成算法圆和圆弧的程序设计区域填充算法字符生成反走样技术,圆的生成算法-中点圆生成算法,以单位间隔取样并在每个步长中确定离指定圆最近的像素位置。对于给定半径r和屏幕中心(xc
9、,yc),运用平移:先给出计算中心在坐标原点(0,0)圆的像素位置的算法,然后通过将xc加到x和yc加到y而把每个计算出的位置(x,y)移动到其适当的屏幕位置。运用对称:在第一像限中,圆弧段从x=0到x=y,曲线的斜率从0变化到-1,因此,可以这八分圆上的正x方向取单位步长,并使用决策参数来确定每一步中两个可能的y位置中更接近于圆的位置,而后在其它七个八分圆中的位置可由对称性得到。,中点圆生成算法:算法原理,定义圆函数:fcircle(x,y)=x2+y2r2,圆边界上任何具有半径r的点(x,y)满足方程fcircle(x,y)=0。任何点(x,y)的相对位置可由对圆函数符号的检测来决定:fc
10、ircle(x,y)0,(x,y)位于圆边界内;fcircle(x,y)0,(x,y)位于圆边界上;fcircle(x,y)0,(x,y)位于圆边界外。在中点算法中圆函数是决策参数,并且可像在画线算法中一样为这个函数设置增量运算。决策参数是圆函数在这两个候选像素的中点处求值:Pk=fcircle(xk+1,yk-1/2);根据决策参数判断:假如pk0,这个中点在圆内,扫描线yk上的像素(高像素)接近圆边界。假如pk0,中点位于圆外或在圆周边界上,选择扫描线yk-1的像素(低像素)。,中点圆生成算法:决策参数,下图示出了取样位置xk+1处两候选像素间的中点,假设(xk,yk)为前一像素,需要决定
11、下列哪个像素:像素位置(xk+1,yk),像素位置(xk+1,yk-1)更接近于圆?注意:圆在第一像限,y0,y方向应取减量。,中点圆生成算法:生成过程,1.输入圆半径r和圆心(xc,yc),并得到圆心在原点的圆周上的第一点为:(x0,y0)=(0,r)2.计算决策参数的初始值为:p0=5/4-r3.在每个xk位置处,从k=0开始,完成下列检测:假如pk0,中心在(0,0)的圆的下一个点为(xk+1,yk),且:pk+1=pk+2xk+1+1;否则,圆的下一点是(xk+1,yk-1),且:pk+1=pk+2xk+1+1-2yk+1。其中:2xk+1=2xk+2,且 2yk+1=2yk-2。,4
12、.确定在其它七个八分圆中的对称点。5.将每个计算出的像素位置(x,y)移动到中心在(xc,yc)的园路径上,并画坐标值:x=x+xc,y=y+yc6.重复步骤3到5,直止xy。,本章讨论内容,直线生成算法圆和圆弧的程序设计区域填充算法字符生成反走样技术,区域填充,区域是指一组相邻而又连通、具有相同属性的像素集。在区域内,生成某一属性的实心或图案的过程称为区域填充。内点,边界和外点:位于区域的点称为内点,与内点相邻但又不属于该区域的像素组成了边界,不是内点和边界的像素是外点.,光栅系统有两种区域填充算法:扫描线填充算法:主要用于填充多边形、圆、椭圆以及其它简单曲线所围成的封闭区域。种子填充算法:
13、适用于具有复杂形状边界的区域填充。,扫描线填充算法,按顺序计算扫描线与多边形的相交区域,用要求的颜色显示这些区间的像素,即完成填充工作。,例如,y=6的扫描线与多边形有四个交点,显然,第1与第2、第3与第4间的区域落在多边形内,这些区间的像素填充预期的颜色。,填充过程,对于一条扫描线,可以分成四个步骤:,(1)求交:计算扫描线与多边形每个边的交点。(2)排序:把所求出的交点按x递增的顺序排序。,(3)交点配对:第一与第二,第三与第四等等,每对交点代表扫描线与多边形的一个相交区域。(4)区间填色:把相交区域内的像素设置成多边形的颜色,把相交区域外的像素设置成背景色。,解决两个特殊问题,扫描线与多
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 光栅 图形 生成 算法
链接地址:https://www.31ppt.com/p-6087301.html