《计算机图形学教学资料》(4)

1、2022-1-31编辑ppt1Scan converting ellipses 2022-1-31编辑ppt2Characteristics of ellipses(1)12222byaxn对称性(symmetry)vEquation of standard ellipsesbaxy(x,y)(x,y)(x,-y)(x,-y)(-x,-y)(-x,-y)(-x,y)(-x,y)2022-1-31编辑ppt3Characteristics of ellipses(2)时，点在椭圆内时，点在椭圆上时，点在椭圆外则：0),(0),(0),(yxfyxfyxf222)()()(),(abaybxyxf

2、引入函数：v空间的正负划分性2022-1-31编辑ppt4Scan converting ellipsesnproblem：drawing the arc in first quadrant （象限）n solvent: midpoint scan converting algorithmn the principle is similar with circlesn Notice: the arc should be divided by the tangent slope（切线斜率）2022-1-31编辑ppt5Dividing the quadrant into two regionsv

3、以弧上切线斜率为-1的点C 为分界点jijiyaxbyFxFyxgradF2222/),(Region 1Region 2Tangent slope= -1Gradient vectorv Find the point whose gradient vector has a slope of 1j iGradi e nt vectorABCvGradient vector(法向量） defined as2022-1-31编辑ppt6Midpoint ellipse algorithmIf at the next midpoint, , we switch from region 1 to re

4、gion 2. )21() 1(22ppyaxbESESSERegion 1Region 2Tangent slope= -1Gradient vector2022-1-31编辑ppt7In region 1设当前已选点是（设当前已选点是（xi，yi），），此此时的候选象素是（时的候选象素是（xi，yi）的右方点和右下方点的右方点和右下方点则判别式则判别式d1 ：2222221) 5 . 0() 1( ) 5 . 0, 1(bayaxbyxFdiiii 若d10，当前选右下方点 (xi+1, yi 1)，Pxi iy yi i-2-2x xi i+1+1y yi iy yi i-1-1x xi

5、 i+2+22022-1-31编辑ppt8In region 1)x(bd )x(bba).(ya)(xb ba).(ya)(xb).,yF(xdiiiiiiii3232501502 5022122222222222221 若若d10，当前取点当前取点 (xi+1, yi 1)，下一中点是下一中点是(xi+2, yi1.5) 22() 32 ( ) 22() 32 () 5 . 0() 1( ) 5 . 1() 2( ) 5 . 1, 2(221222222222222221iiiiiiiiiiyaxbdyaxbbayaxbbayaxbyxFdPx xi ix xi i+2+2x xi i+1

6、+1y yi i-1-1y yi iy yi i-2-22022-1-31编辑ppt10In region 1上段弧起点为（0，b），因此第一个中点是（1，b0.5)25. 0( )5 . 0( )5 . 0, 1 (22222220babbababbFd初值：2022-1-31编辑ppt11In region 2P(xi,yi)Pl(xi,yi-1)Pr(xi+1,yi-1)M(xi+0.5,yi-1)2022-1-31编辑ppt12In region 2设当前已选点是（设当前已选点是（xi，yi），），判别式判别式 2222222)1()5 . 0( )1, 5 . 0(bayaxbyxF

7、diiii 若若d2 0，取取Pl(xi, yi-1)若若d20，取取Pr(xi+1, yi-1)2022-1-31编辑ppt13In region 2判别式的递推判别式的递推：d2 0，当前，当前取取Pl(xi, yi-1)，则则下一步的中点是下一步的中点是(xi+0.5, yi-2)y(ad )y(aba)(ya)(xb ba)(ya)(xb),yF(xdiiiiiiii323215 . 025 . 0 25 . 0 2222222222222222Px xi iy yi i-2-2x xi i+1+1y yi iy yi i-1-1x xi i+2+22022-1-31编辑ppt14In

8、 region 2d20,当前当前取取Pr(xi+1, yi-1)，下一步的中点取下一步的中点取(xi +1.5, yi-2)Px xi ix xi i+2+2x xi i+1+1y yi i-1-1y yi iy yi i-2-2) 32() 22 ( ) 32() 22 () 1() 5 . 0( ) 2() 5 . 1( ) 2, 5 . 1(222222222222222222iiiiiiiiiiyaxbdyaxbbayaxbbayaxbyxFd2022-1-31编辑ppt15In region 2v初值d2若在region 1中所选择的最后一个象素是 (xi, yi)，则下半部分的中

9、点判别式初值d2在(xi+0.5 , yi1)处计算。第一象限椭圆弧扫描转换中点算法第一象限椭圆弧扫描转换中点算法(1)Void MidPointEllipse(int a, int b)int x, y; float d1, d2; x=0; y=b; d1=b b+a a (-b+0.25); Putpixel(x, y); while(b b (x+1)0) if (d2 0) d2+= b b (2x+2)+ a a (-2y+3); x+; y-; else d2+= a a (-2y+3); y-; Putpixel(x, y); /下半部分椭圆弧下半部分椭圆弧0 0 x x1 1

10、2 26 65 54 43 32 21 10 08 87 76 65 54 43 3y ya=8，b=6的椭圆弧的椭圆弧2022-1-31编辑ppt193.3 区域填充区域填充2022-1-31编辑ppt203.3.1 Filling rectangles（1）v可利用矩形的简单性提高扫描转换的效率。vExploiting the spatial coherenceminxmaxxminymaxyminxmaxxminymaxyv采用两层嵌套循环来实现矩形区域的填充2022-1-31编辑ppt21Filling rectangles（2）Solution:象素中心位于矩形的左、下边界时绘制象素

11、点vProblem:shared common edge？2022-1-31编辑ppt223.3.2 Filling polygonsvRepresentations of polygons:n多边形的扫描转换：n从顶点表示转换为点阵表示形式，以便于光栅显示的实现。n顶点表示点阵表示2022-1-31编辑ppt23多边形扫描转换算法分类v以点为中心的填充算法：v逐点判别算法v以扫描线为中心的填充算法：v多边形有序边表填充算法(扫描线算法)v边缘填充算法v种子填充算法：从区域内部一点开始填充直至边界。v递归填充算法v扫描线算法2022-1-31编辑ppt24Scan Line Algorithm

12、v扫描线:光栅扫描显示器的一行象素点叫一条扫描线 P1 P2 P3 P4 P5 P6 0 2 4 6 8 10 2022-1-31编辑ppt25v 设多边形P的顶点是Pi=(xi,yi),i=0,1,2,n,v 又设yi0,yi1,yin是各顶点Pi的纵坐标yi的递减数列,即yikyik+1,0 k n-1v 屏幕上位于yik和yik+1两条扫描线之间的长方形区域被P 的边分割成若干梯形(三角形可看作其中一底边长为零的梯形),这些梯形具有下列性质:Region Coherence (1) 2022-1-31编辑ppt26梯形的两底边分别在y=yik和y=yik+1扫描线上,腰边在P的边上或在屏

13、幕的边界上;这些梯形分为两类:一类在多边形P内,一类在P外;两类相间排列.依照上述性质依照上述性质,可根据长方可根据长方形区域内的任一点形区域内的任一点q的内的内外关系外关系,确定确定所有所有梯形梯形 的的内外关系内外关系:若若q在内在内,则则q所所在区域位于在区域位于P内内,与该区域与该区域相邻的区域位于相邻的区域位于P外外,依次依次类推类推.Region Coherence(2)qP0P1P2P4P5P7P8P3P6y=yiky=yik+12022-1-31编辑ppt27 设e为一整数, yi0eyin,y=e的扫描线与多边形的边Pi-1Pi的交点横坐标记为xei 假设y=e 扫描线与多边

14、形各边交点横坐标的递增序列为: xei1, xei2 , xei3 ,. , xeim (1) Scan-Line Coherence则由区域的连贯性,可知交点序列有如下性质:m 是偶数, 即共有偶数个交点; 在该扫描线上,只有区段( xeik, xeik+1)(k=1,3,m-1)位于多边形P内，其余区段都在P外 .（奇入偶出）2022-1-31编辑ppt28 设d=e-1,y=d的扫描线与P的边的交点序列为 xdj1, xdj2 , xdj3 ,. ,xdjn (2) 若多边形P的一条边Pr-1Pr与扫描线y=d,y=e都相交,则由xdr可推出xer: xer=xdr+1/m m is t

15、he slope of edge Pr-1PrEdge Coherence (1)2022-1-31编辑ppt29Suppose intersection (xi,yi) on scan line i bayxyyyifiiii11max11byai) 1(axima1Where , m is the slope of the edge of polygonEdge Coherence(2)2022-1-31编辑ppt30 若yike,dyik+1,即和扫描线e相交的边与和扫描线d相交的边都一样,则有以下边的连贯性: 两交点序列元素的个数相等,即m=n; 点(xeir,e) 与(xdjr,d)

16、位于多边形P的同一条边上,即ir=jr. xeir=xdjr+1/m Edge Coherence(3)2022-1-31编辑ppt31Round up or down x?If x is a decimal fraction, it should be round.(b) Left vertex: round upRight vertex: round down2022-1-31编辑ppt32 对左下角为(1,1),右上角为(3,3)的正方形填充时,若对边界上所有象素都进行填充,就得到面积为3x3的区域,如下图(a);而实际面积只有2x2.显然,这是由于对边界上所有象素未加处理而引起的.为此

17、,在填充时,采用“左闭右开”,“下闭上开”的原则对扫描线进行填充.如下图(b).(a)(b)Handle the intersection2022-1-31编辑ppt33Interior or exterior?vIf x is a integer coordinate, it should be decided interior or exterior(b) On right edge: be exteriorOn left edge: be interior2022-1-31编辑ppt34 当扫描线与多边形P的顶点相交时，则称该交点为奇异点。 (4)奇异点的处理(1)P0P1P2P4P5P

18、7P8P3P612对奇异点的处理如下： 首先将奇点分为两类:extrema and nonextrema (极值点和非极值点.)2022-1-31编辑ppt35对点Pi,若(yi-1- yi)*(yi+1- yi) 0 则称Pi为极值点; 否则,称之为非极值点.P0P1P2P4P5P7P8P3P612奇异点的处理(2)2022-1-31编辑ppt36对非极值点,将按一个交点处理;对极值点, 若其是局部最高点,则按0个交点处理; 若其是局部最低点,则按2个交点处理.奇异点的处理(3)2022-1-31编辑ppt37On shared verticesvIntersections on share

19、d vertices can be counted once, twice or zero. Such as P1P0P0P0P0P1P1P1P1P2P2P2P2(a)(b)(c)(d)(a) (b) is counted once (c) is counted twice (d) is zeroRule: the vertex with ymin is counted the vertex with ymax is not counted 2022-1-31编辑ppt38PiPi对非极值点的处理对局部最高点的处理Pi奇异点的处理(4)Pi2022-1-31编辑ppt391.求交.对每条扫描线

20、(y=y0,y= y0 +1,y= y0+2,.)，求与多边形各边的交点；2.按x坐标递增方式对交点排序；3.在每一对交点之间,着指定象素值.交点总数为偶数个.问题：水平边如何处理？(5)Process and Data StructureThree-step process to fill the spans：2022-1-31编辑ppt40Three-step process to fill the spansvFind the intersections of the scan line with all edges of the polygon.vSort the intersecti

21、ons by increasing x coordinatevFill in all pixels between pairs of intersections that lie interior to the polygon?：horizontal edges2022-1-31编辑ppt41ymaxxxnext在ET表中表示边的下端点下端点的x值;在AET表中表示交点的x坐标边的斜率的倒数1/m边的上端点的y坐标指向下一条边的指针Data Structure(1) 算法采用两个链表结构:边表(Edge Table)和活性边表(Active Edge Table).链表结构ET和AET中的基本

22、元素为多边形的边,边的数据结构由四个域组成: 2022-1-31编辑ppt42 ET表是所有边的指针数组,它记录了所有边的结构及其关系.ET表按边的下端点的纵坐标y对非水平边非水平边进行分类. (edges are kept in order of increasing x coordinate or x ).边的活性链表AET由与当前扫描线相交的所有多边形的边组成,它记录了多边形沿扫描线的交点序列(x递增序列).AET表可递推产生.Data Structure(2)2022-1-31编辑ppt43y递增顺序形成ET表;y=ET表中第一个非空节点的y值(最小扫描线的y值);AET表,将AET

23、表设置为空;y执行下列步骤,直至ET和AET都为空.(1)若ET中第y类元素非空，则将ET中有关y扫描线的信息和并到AET中,并使AET按x递增顺序排列;(2)对于扫描线y, 取AET中两两一对x坐标,填充所需的象素值(color);(3)从AET中删去y= ymax的项;(4)对AET中保留的项,令x=x+1/m;(即xi+1=xi+ x);(5) y=y+1形成下一条扫描线，GOTO 4。Algorithm2022-1-31编辑ppt44算法伪代码：Polygongfill(polydef,color)Point polydef;int color; for(多边形各条边e) 建立边的分类

24、表EdgeTablei; i=0; ActiveEdgeList=0；/当前扫描线对应的活性边表初始化 for(各条扫描线i) 把EdgeTablei插入ActiveEdgeList中，并排序； 遍历ActiveEdgeList，把配对交点构成半开半闭区间； 填充各区间； 从ActiveEdgeList中删除y=ymax的边； 刷新ActiveEdgeList中交点的X坐标值； /for2022-1-31编辑ppt45Example(1):24681012 1424681012P1(7,1)P2(13,5)P3(13,11)P4(7,7)P5(2,9)P6(2,3)e1e2e3e4e5e620

25、22-1-31编辑ppt46Example (2) :24681012 1424681012P1(7,1)P2(13,5)P3(13,11)P4(7,7)P5(2,9)P6(2,3)e1e2e3e4e5e62022-1-31编辑ppt47Example (3) :24681012 1424681012P1(7,1)P2(13,5)P3(13,11)P4(7,7)P5(2,9)P6(2,3)e1e2e3e4e5e62022-1-31编辑ppt48Example (4) :24681012 1424681012P1(7,1)P2(13,5)P3(13,11)P4(7,7)P5(2,9)P6(2,3)e1e2e3e4e5e62022-1-31编辑ppt49Example (5)