《光栅图形生成算法课件》由会员分享，可在线阅读，更多相关《光栅图形生成算法课件（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;,逐
4、点比较法,设步距为t, 直线在x,y方向的增量分别为x 和y.按上述运算方法,绘图笔从直线的起点画到终点,在x方向应走| x/ t|步,在y方向应走| y/ t|步.取n= | x/ t|+ | y/ t|作为终点判断的控制数,并将此数存入计数器内. 在x或y方向上每走一步计数器减1,当计数器减到零时,作图停止.,（2）终点判断,直线生成算法,Bresenham直线生成算法,基本原理：沿某一计长方向上，每次变化一个单位步长，另一方向上的变化量通过计算获得。这种方法在计算判别式时，计算量很小，生成的直线光滑，因而应用广泛。 假设直线的斜率在01之间，k=y/ x，x的变化率比y的变化率大，约定每
5、次x方向变化一个像素单位，相应y方向的变化量为0或1个像素单位。,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),计算判
6、别式: 理论直线上点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=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-
7、1),且xi+1=xi+1，得 di+1=di+2y-2x(yi+1-yi) (3-3) 其中,yi+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)装入帧缓冲器，画
8、第一个点； 计算常量：x、y、2y和2y-2x，并得到决策参数的第一个值： p0 = 2yx； 从k=0开始，在沿线的每个xk处，进行下列检测： 假如pk0，画下一个点(xk+1，yk)， 且：pk+1= pk+2y； 否则，下一个待画点(xk+1，yk+1)， 且：pk+1=pk + 2y-2x。 k=k+1； 重复步骤4，共x次。,像素生成过程,该算法仅涉及整数加法运算和乘2(左移)操作，运算效率高，易于硬件实现。 与逐点比较法相比，生成的直线光滑。 若将该算法的范围扩大到整个平面，相应的d增量式及其初始值,以及下一像素位置的取法道理相似，请思考！,本章讨论内容,直线生成算法 圆和圆弧的程
9、序设计 区域填充算法 字符生成 反走样技术,圆的生成算法-中点圆生成算法,以单位间隔取样并在每个步长中确定离指定圆最近的像素位置。 对于给定半径r和屏幕中心(xc，yc)， 运用平移：先给出计算中心在坐标原点(0，0)圆的像素位置的算法，然后通过将xc加到x和yc加到y而把每个计算出的位置(x，y)移动到其适当的屏幕位置。 运用对称：在第一像限中，圆弧段从x=0到x=y，曲线的斜率从0变化到-1，因此，可以这八分圆上的正x方向取单位步长，并使用决策参数来确定每一步中两个可能的y位置中更接近于圆的位置，而后在其它七个八分圆中的位置可由对称性得到。,中点圆生成算法：算法原理,定义圆函数：fcirc
10、le(x，y) = x2+ y2r2 ， 圆边界上任何具有半径r的点(x，y)满足方程fcircle(x，y)=0。 任何点(x，y)的相对位置可由对圆函数符号的检测来决定： fcircle(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上的像素(高像素)接近圆
11、边界。 假如pk0，中点位于圆外或在圆周边界上，选择扫描线yk-1的像素(低像素)。,中点圆生成算法：决策参数,下图示出了取样位置xk+1处两候选像素间的中点， 假设(xk，yk)为前一像素， 需要决定下列哪个像素：像素位置(xk+1，yk)，像素位置(xk+1，yk-1)更接近于圆？ 注意：圆在第一像限，y0，y方向应取减量。,中点圆生成算法：生成过程,1. 输入圆半径r和圆心(xc，yc)，并得到圆心在原点的圆周上的第一点为：(x0，y0)=(0，r) 2. 计算决策参数的初始值为：p0=5/4-r 3. 在每个xk位置处，从k=0开始，完成下列检测： 假如pk0，中心在(0,0)的圆的下
12、一个点为(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. 确定在其它七个八分圆中的对称点。 5. 将每个计算出的像素位置(x,y)移动到中心在(xc,yc)的园路径上，并画坐标值：x=x+xc，y=y+yc 6. 重复步骤3到5，直止xy。,本章讨论内容,直线生成算法 圆和圆弧的程序设计 区域填充算法 字符生成 反走样技术,区域填充,区域是指一组相邻而又连通、具有相同属性的像素集。在区域内，生成某一属性的实心或图案的过程称为区
13、域填充。 内点, 边界和外点:位于区域的点称为内点, 与内点相邻但又不属于该区域的像素组成了边界,不是内点和边界的像素是外点.,光栅系统有两种区域填充算法： 扫描线填充算法：主要用于填充多边形、圆、椭圆以及其它简单曲线所围成的封闭区域。 种子填充算法：适用于具有复杂形状边界的区域填充。,扫描线填充算法,按顺序计算扫描线与多边形的相交区域，用要求的颜色显示这些区间的像素，即完成填充工作。,例如，y=6的扫描线与多边形有四个交点，显然，第1与第2、第3与第4间的区域落在多边形内，这些区间的像素填充预期的颜色。,填充过程，对于一条扫描线，可以分成四个步骤：,(1)求交：计算扫描线与多边形每个边的交点
14、。 (2)排序：把所求出的交点按x递增的顺序排序。,(3)交点配对：第一与第二，第三与第四等等，每对交点代表扫描线与多边形的一个相交区域。 (4)区间填色：把相交区域内的像素设置成多边形的颜色，把相交区域外的像素设置成背景色。,解决两个特殊问题,扫描线与多边形的顶点相交，交点的取舍。,多边形边界上的像素的取舍问题。,2,4,6,8,解决两个特殊问题,扫描线与多边形的顶点相交，交点的取舍。,多边形边界上的像素的取舍问题。,2,4,6,8,种子填充算法,基本思想:从区域内部已定义新值的某像素(种子)开始,搜索与该种子相邻且位于区域内的像素,该像素为新的种子；不断地递归搜索,逐个像素填充所需颜色,直
15、到填充完区域边界内的所有像素为止。,区域分四连通区域和八连通区域:,连通区域定义,4连通区域： 任取区域内两点，在该区域内，允许通过上、下、左、右四个方向的运动，这两点相互可达。 8连通区域： 任取区域内两点，在该区域内，允许通过水平、垂直、两个对角线八个方向的运动，这两点相互可达。,连通区域定义,由定义可知：4连通区域也可以看作是8连通区域。但它作为4连通区域和8连通区域的边界是不同的(4连通比8连通约束紧。左下图)： 像素作为4连通区域，其边界只要是连通就可以了； 像素作为8连通区域，其边界必须是连通区域。否则，欠约束。 8连通区域能用来填充更复杂的图形(如下图所示)。,(1) 边界填充算法,如果区域采用边界定义，即边界上的所有像素具有某个相同的特定值(颜色或亮度)，区域内部所有像素均具有非新值的某个给定值；这种区域内的种子填充算法又称边界填充算法。,Boundary-fill-4(x,y,newcolor,boundarycolor) int x,y,newcolor,boundaryc
