第三章图形生成图像的基本原理.ppt

1、第三章 图形生成图像的基本原理,3.1 图形图像的关系： 1）区别： 图形是用矢量表示的，是用几何学的点、线、面对客观世界建模的结果。图形中不但包含几何信息，而且可以包含拓扑、颜色等非几何信息。这些信息是设备无关的。 图像是用点阵表示的，其中只有各个点的颜色信息，不含拓扑关系，也没有几何学的点、线、面。从数学上说，图像是定义域和值域都不连续的一个函数（数字图像）。 图形和图像各有其优点，图形适合表达几何信息（建模），图像适合表达视觉信息（照片）。 2）存储： 图形使用矢量文件，图像使用点阵文件。 3）转换关系： 图形通过光栅扫描可以转化为光栅图像；图像通过识别和处理可以转化为矢量表示的图形形式

2、，但通常它无法恢复图形信息。,3.2 直线生成算法,1）数值微分(DDA)法 过两点(x0,y0)，(xn,yn)作直线： 其直线方程为：(y-y0)/(yn-y0)=(x-x0)/(xn-x0) 整理后为：y=kx+b 其中k(yn-y0)/(xn-x0) 当k1时，取x方向步长为1， 则有，对中间需要计算的点（i=0,n-2） xi1xi1； yi+1=kxi+1+b = k(xi+1)+b = kxi+b+k = yi+k 这里xi为整数，yi、k为浮点数 在屏幕上显示点(x0,y0),(x1,int(y1+0.5),(xn-1,int(yn-1+0.5),(xn,yn),则显示出该直线

3、。 由于y方向增量每次小于1(反证)，所以直线是连通的。 当k1时，交换x，y位置进行处理。,实例：用DDA方法在点（0,0）和（5,2）之间画线,n=5 (x0,y0) = (0,0) (xn,yn) = (5,2) k=(2-0)/(5-0) = 0.4,动画,2)Bresenham算法 （最常用）,前面已知当直线的斜率k1是，x方向每次增加一个步长，y方向增加不到一个步长。 如右图所示，每次y是否增加取决于误差项d，当d0.5时，y取直线上面的网格点，否则y取直线下面的网格点。 即对中间象素(i=0, i=n-2)，作下列操作： 1）xi+1= xi+1 2）ei+1= ei+k，(e0

4、=-0.5，e不同于d，它是误差减0.5) 3）当ei+10时 yi+1 = yi+1；ei+1= ei+1-1 否则 yi+1= yi 这里的xi，yi均为整数，即象素点的坐标。 4）显示（xi+1,yi+1),实例：用Bresenham方法在点（0,0）和（5,2）之间画线,n=5 (x0,y0) = (0,0) (xn,yn) = (5,2) k=(2-0)/(5-0) = 0.4,3.3 圆的生成算法(中点画圆法),圆的特点决定只需要计算1/8圆弧上的点（右上图） 假设圆的方程为：x2+y2=r2 函数F(x,y) = x2+y2-r2，则 F(x,y)0，对圆外点 F(x,y) =

5、0，对圆上点 F(x,y) 0，对圆内点 (只需计算第一象限上半1/8圆弧)如果已得到圆弧的象素点P(xp,yp)，则下一可能的象素点是P1(xp+1,yp)和P2(xp+1,yp-1)，究竟是P1还是P2由P1和P2的中点M(xp+1,yp-0.5)的函数值F(xm,ym)来决定： 如果F(xm,ym)0，说明圆弧在P1和M之间，则取P1点为下一象素。 且下一象素的F(xp+2,yp-0.5)=F(xp+1,yp-0.5)+2xp+3 如果F(xm,ym)0，说明圆弧在P2和M之间，则取P2为下一象素。 且下一象素的F(xp+2,yp-1.5)=F(xp+1,yp-0.5)+2(xp-yp)

6、+5 而F(1,r-0.5) = 1.25-r;,(x,y),(y,x),(y,-x),(x,-y),(-y,x),(-x,y),(-y,-x),(-x,-y),程序：,MidCircle18(int r) int x,y; float f; x=0; y=r; f=1.25-r; /注意f为下一点（1，r-0.5）的判别式 point(x,y); while(x=y) if(f0) f+=2*x+3; else f+=2*(x-y)+5; y-; x+; point(x,y); 作业1：将上述程序改造为一个完整的画圆程序，函数名为 MidCircle(int x0, int y0, int

7、r) 其中x0,y0为圆心坐标，r为半径,动画:,3.3 多边形的扫描转换,多边形分为三种：凸多边形、凹多边形、含内环的多边形。多边形的边界不能相交。 凸多边形是指任意两顶点间的连线均在多边形内。 凹多边形是指任意两顶点间的连线有不在多边形内的部分。 含内环的多边形是指多边形内再套有多边形。多边形内的多边形称为内环。,1）扫描线算法,扫描线方法通过从多边形最低点到最高点之间的水平扫描，完成对多边形的扫描转换。对每条扫描线，多边形的扫描转换分为四个步骤： （1）求交：计算扫描线与多边形各边的交点； （2）排序：把所有交点按x值递增顺序排序； （3）配对：奇偶交点配对，每对交点代表扫描线与多边形的

8、一个相交区间。 （4）着色：把相交区间内的象素置成多边形颜色。,为了提高效率，在处理一条扫描线时，仅对与它相交的多边形的边进行求交运算。与当前扫描线相交的边称为活性边，把它们按与扫描线交点x坐标递增的顺序存放在一个链表中，此链表称为活性边表(AET)。活性边表只有一个。,扫描线6的活性边表,与当前扫面线的x交点坐标,每条扫描线的x增量,本条线段的最大y坐标,注：每条扫描线的X增量是斜率的倒数，可以是任何数值。对水平线需要特殊处理，对垂线其值为0。不必考虑X的增量大于1的情形，因为这里生成的是区域，而不是直线，它总是连通的(对非奇异图形)。,为了方便活性边表的建立与更新，为每一条扫描线建立一个新

9、边表（NETi）,存放在该扫描线第一次出现的边。也就是说，若某边的较低端点为ymin，则该边就放在扫描线ymin的新边表中。每条扫描线有一个新边表，新编表可以为空，表示这条扫描线不需要加入新边，而且大多数新编表都应该为空。,每条扫描线有新边表（NETi），所有新编表构成NET（可以用数组也可以用链表）。,此边的最低y值（ymin）,算法过程：,void polyfill (polygon, color) int color;多边形 polygon; 构造新编表NET（NETi为第i条扫描线对应的新边表头，见前页图）； y = 最低扫描线号（在这里是0）； 初始化活性边表AET为空； 对各条扫描

10、线i，作下列操作 把新边表NETi中的边结点插入AET表，并使之按x坐标递增顺序排列； 将活性边表AET中的边奇偶为区间，对区间内的象素(x, y)，用drawpixel (x, y, color) 着色； 检查活性边表AET ，把ymax= i的结点从AET表中删除，其它边的x交点坐标按增量递增（x）； ,需要考虑的特殊情形原则：不遗漏点，无重复点。,可以采取的措施： 1）新加入边时，要考虑退出边的情况，否则会重复计点。（P1、P7）。 2）适当进行区间合并（过P9点扫描线）。 3）水平边不参与计算（P6P5、P3P2）。 4）对三角剖分应当考虑其它模式（思考）。,P8,P0,P1,P2,P

11、3,P4,P6,P7,P5,P9,2）边界标志算法,边界标志算法的基本思想是： 在帧缓冲器中对多边形的每条边进行直线扫描转换，亦即对多边形边界所经过的象素打上标志。然后再采用和扫描线算法类似的方法将位于多边形内的各个区段着上所需颜色。 对每条与多边形相交的扫描线依从左到右的顺序，逐个访问该扫描线上的象素。使用一个布尔量inside来指示当前点是否在多边形内的状态。 Inside的初值为假，每当当前访问的象素为被打上边标志的点，就把inside取反。对未打标志的象素，inside不变。若访问当前象素时，inside为真，说明该象素在多边形内，则把该象素置为填充颜色。 用软件实现时，扫描线算法与边

12、界标志算法的执行速度几乎相同，但由于边界标志算法不必建立维护边表以及对它进行排序，所以边界标志算法更适合硬件实现，这时它的执行速度比有序边表算法快一至两个数量级。,3.4 光栅图形的区域填充,区域填充指先将区域的一点（种子点）赋予指定的颜色，然后将该颜色扩展到整个区域的过程。 区域可采用内点表示和边界表示两种表示形式。在内点表示中，区域内的所有象素着同一颜色。在边界表示中，区域的边界点着同一颜色。,区域填充的区域是连通的。区域可分为4向连通区域和8向连通区域。 4连通区域指的是从区域内任一象素出发，通过上、下、左、右四个方向的移动，可以到达区域内的任意象素。 8连通区域指的是从区域内任一象素出

13、发，通过上、下、左、右、左上、右上、左下、右下八个方向的移动，可以到达区域内的任一象素。,四连通区域 八连通区域,1）区域填充的递归算法,内点表示的4连通区域的递归填充算法： void FloodFill4(x, y, oldcolor, newcolor) int x, y; COLOR oldcolor,newcolor; if(getpixel(x,y)=oldcolor) drawpixel(x,y,newcolor); FloodFill4(x,y+1,oldcolor,newcolor); FloodFill4(x,y-1,oldcolor,newcolor); FloodFill

14、4(x-1,y,oldcolor,newcolor); FloodFill4(x+1,y,oldcolor,newcolor); ,边界表示的4连通区域的递归填充算法 ： void BoundaryFill4(x, y, edgecolor, newcolor) int x, y; COLOR edgecolor, newcolor; COLOR color = getpixel(x,y); if(color!=newcolor ,对于内点表示和边界表示的8连通区域的填充，只要将上述相应代码中递归填充相邻的4个象素增加到递归填充8个象素即可。,动画:边界表示的4连通区域的递归填充算法,2）区域

15、填充的扫描线算法,区域填充的递归算法原理和程序都很简单，但由于递归太多，效率不高。 扫描线算法的基本过程如下： 当给定种子点(x,y)时，首先填充种子点所在扫描线上的位于给定区域的一个区段，然后确定与这一区段相连通的上、下两条扫描线上位于给定区域内的区段，并依次保存下来。反复这个过程，直到填充结束。 由于对于每一个待填充区段，只需压栈一次，扫描线填充算法提高了区域填充的效率。 扫描线算法可由下列四个步骤实现：,(1)初始化：堆栈置空。将种子点(x,y)入栈。 (2)出栈：若栈空则结束。否则取栈顶元素(x,y)，以y作为当前扫描线。 (3)填充并确定种子点所在区段：从种子点(x,y)出发，沿当前

16、扫描线向左、右两个方向填充，直到边界。分别标记区段的左、右端点坐标为xl和xr。 (4)确定新的种子点：在区间xl，xr中检查与当前扫描线y上、下相邻的两条扫描线上的象素。若存在非边界、未填充的象素，则把每一区间的最右象素作为种子点压入堆栈，返回第（2）步。,（内点表示）程序：,typedef struct int x, y; Seed; /记录种子点 void ScanLineFill4(int x,int y, COLOR oldcolor,COLOR newcolor) int xl,xr,i; bool spanNeedFill; /决定是否压栈 Seed pt; setstackem

17、pty(); pt.x =x; pt.y=y; stackpush(pt); /种子进栈 while(!isstackempty() pt = stackpop(); x=pt.x; y=pt.y; /出栈 while(getpixel(x,y)=oldcolor)/向右填充 drawpixel(x,y,newcolor); x+; xr = x-1; x = pt.x-1; while(getpixel(x,y)=oldcolor)/向左填充 drawpixel(x,y,newcolor); x-; xl = x+1;,/处理上面一条扫描线 x = xl; /四连通 y = y+1; whi

18、le(x=xr) spanNeedFill=FALSE; while(getpixel(x,y)=oldcolor) spanNeedFill=TRUE; x+; /处理内点 if(spanNeedFill) pt.x=x-1;pt.y=y; stackpush(pt); /每一区间的最右象素 spanNeedFill=FALSE; while(getpixel(x,y)!=oldcolor / 上面已经1 while(x=xr) . /End of while(i=xr) /End of while(!isstackempty() ,OpenGL对光栅化的处理,OpenGL规定在子象素级进行光栅化，它将点视为数学点，将直线图元视为数学直线，将填充图元视为由数学直线包围的区域。程序员应将窗口坐标空间视为笛卡儿网格，其中的每个网格对应屏幕上的一个象素。 1、光栅化点图元时，如果该点位于象素边界内，则光栅化该点。 2、光栅化直线时，OpenGL光栅化位于两个