土质土力学01绪论

1、2021-10-30计算机图形学1计算机图形学期末复习2直线的扫描转换n直线的扫描转换的任务n确定最佳逼近于该直线的一组象素n按扫描线顺序，对这些象素进行写操作n直线的扫描转换的方法n数值微分(dda)算法n中点画线法nbresenham画线算法3dda算法4中点画线法的思想 ) 1(5 . 0)5 . 0, 1(),(bxkyyxfyxfdiiiimm5中点画线法步骤n1.输入直线的两端点p0(x0,y0)和p1(x1,y1)。n2.计算初始值x、y、d=0.5-k、x=x0、y=y0；n3.绘制点(x,y)。判断d的符号；n4.若d0，则(x,y)更新为(x+1,y+1)，d更新为d+1-

2、k；否则(x,y)更新为(x+1,y)，d更新为d-k。n5.当直线没有画完时，重复步骤3。否则结束6改进算法n改进改进：因为d只用来做符号判断，用2*x*d代替dn1.输入直线的两端点p0(x0,y0)和p1(x1,y1)。n2.计算初始值x、y、d=x-2y、x=x0、y=y0。n3.绘制点(x,y)。判断d的符号。n若d0.5 ，则(x,y)更新为(x+1,y+1)，同时将d更新为d-1；否则(x,y)更新为(x+1,y)。5.当直线没有画完时，重复步骤3和4。否则结束。9bresenham算法改进n改进1：令e=d-0.5ne值的变化为：ne初=-0.5，n每走一步有e=e+k。nif

3、(y方向上走一步) then e=e-10)(e 0)(e 1111iiiiiyyyxx10bresenham算法步骤1.输入直线的两端点p0(x0,y0)和p1(x1,y1)。2.计算初始值x、y、e=-0.5、x=x0、y=y0。3.绘制点(x,y)。4.e更新为e+k，判断e的符号。若e0，则(x,y)更新为(x+1,y+1)，同时将e更新为e-1；否则(x,y)更新为(x+1,y)。5.当直线没有画完时，重复步骤3和4。否则结束。11bresenham算法改进n改进2：用2ex来替换ene值的变化为：ne初=-x， ，n每走一步有e=e+2y 。nif (y方向上走一步) then e

4、=e-2x0)(e 0)(e 1111iiiiiyyyxx12bresenham改进步骤1.输入直线的两端点p0(x0,y0)和p1(x1,y1)。2.计算初始值x、y、e=-x、x=x0、y=y0。3.绘制点(x,y)。4.e更新为e+2y，判断e的符号。若e0，则(x,y)更新为(x+1,y+1)，同时将e更新为e-2x；否则(x,y)更新为(x+1,y)。5.当直线没有画完时，重复步骤3和4。否则结束。13bresenham画线法示例n例：用bresenham画线法p0(0,0) p1(5,2)d=0；k=0.4 xi yi 第一次d 第二次d 0 0 0 0 1 0 0.4 0.4 2

5、 1 0.8 -0.2 3 1 0.2 0.2 4 2 0.6 -0.4 5 2 00 1 2 3 4 532114中点画圆法基本思想np为当前点亮象素，那么，下一个点亮的象素可能是p1（xp+1，yp）或p2（xp +1，yp -1)。nf（x，y）=x2 + y2 - r2 ，有如下结论：nf（m） 取p1nf（m）= 0 则m在圆外- 取p2mp1p2p（xp ，yp ）第一象限靠近y轴的八分之一圆15中点画圆法基本思想nf（x，y）=x2 + y2 - r2 ，有如下结论：nf（m）m在圆内- 取p1nf（m）= 0 -m在圆外- 取p2mp1p2p（xp ，yp ）m=(xp+1,y

6、p-0.5)16中点画圆法基本思想nd = f(m) = f(xp + 1, yp - 0.5) =(xp + 1)2 + (yp - 0.5) 2 - r2 n若d=0, 则p2(xp + 1, yp 1) 为下一个象素，那么：d1 = f(xp + 2, yp - 1.5) = d + （2xp + 3）+（-2 yp + 2）n若d0, 则p1(xp + 1, yp ) 为下一个象素，那么：d2 = f(xp + 2, yp - 0.5)= d + 2xp +3 17中点画圆法基本思想nd的初值: d0 = f(1, r-0.5)= 1 + (r-0.5)2 - r2 = 1.25 -

7、rmp1p2p（xp ，yp ）18中点画圆法算法步骤n1.输入圆的半径r。n2.计算初始值d=1.25-r、x=0、y=r。n3.绘制点(x,y)及其在八分圆中的另外七个对称点。n4.判断d的符号。若d0，则先将d更新为d+2x+3，再将(x,y)更新为(x+1,y)；否则先将d更新为d+2(x-y)+5，再将(x,y)更新为(x+1,y-1)。n5.当xy时，重复步骤3和4。否则结束。19中点画圆法代码midpointcircle(int r, int color) int x,y; float d; x=0; y=r; d=1.25-r; drawpixel(x,y,color); wh

8、ile(xy) if(d0) d+ = 2*x+3; x+; elsed+ = 2*(x-y) + 5; x+;y-; drawpixel(x,y,color); 20中点画圆法分析n为了进一步提高算法的效率，可以将上面的算法中的浮点数改写成整数，将乘法运算改成加法运算，即仅用整数实现中点画圆法。n使用e=d-0.25代替dne0=1-r21区域填充n用某种颜色或图案来填充一个有界区域。n填充区域：n多边形填充n任意区域的填充n填充算法：n扫描线填充算法-扫描线顺序n有序边表算法n种子填充算法-内部一个点出发22多边形扫描转换步骤n确定多边形所占有的最大扫描线数，得到多边形顶点的最小和最大y值

9、（ymin和ymax）。n从y=ymin到y=ymax，每次用一条扫描线进行填充。n对一条扫描线填充的过程可分为四个步骤：na.求交nb.排序nc.交点配对nd.区间填色23多边形扫描转换分析n分析：影响扫描线填充算法效率因素有求交和排序。n事实：所有的边和扫描线求交，效率很低。n解决：n处理扫描线时只对与它相交的直线进行处理。n由于边的连贯性，即当某条边与当前扫描线相交时，它很可能也与下一条扫描线相交，为此，计算下一条扫描线与同一条边的交点x值时，只需把当前交点x值加上边的斜率的倒数即可。24有序边表算法n多边形填充进行求交运算时，与当前扫描线相交的多边形的边称为活性边。n把活性边按与扫描线

10、交点x坐标递增的顺序存放在一个链表中，此链表称为有序边表也叫活化边表。n利用有序边表进行多边性填充的算法也被称为有序边表算法。25有序边表的结点n有序边表的结点：n扫描线5示例：012345671234567yx88910扫描线5p4p1p2p3p5扫描线2i1i2i3i4x ymax 1/k next170 47-5/3 862 10 60 26有序边表的使用更新n使用：交点配对n更新：012345671234567yx88910扫描线5p4p1p2p3p5扫描线2i1i2i3i4170 47-5/3 862 10 60 27新边表n为了方便有序边表的建立与更新，可以为每一条扫描线建立一个新

11、边表，存放在该扫描线第一次出现的边。1234567891011123-1/3353/485-1/2891/21122/5712-1795p0p6728有序边表算法步骤n输入欲填充多边形的顶点数及其顶点坐标。n计算所有多边形顶点坐标中y的最大值和最小值，以此作为扫描线的处理范围。n对处理范围内的每条扫描线建立新边表。n对处理范围内的每条扫描线，重复下列步骤：n用有序边表建立当前扫描线的活化边表；n从活化边表中依次取出一对交点，对该两个交点内的像素进行填充；n为下一条扫描线更新活化边表，即增加交点的x值和删除不再相交的边；n重排活化边表。29种子填充算法n种子填充指先将区域的一点赋予指定的颜色，然

12、后将该颜色扩展到整个区域的过程。种子填充算法要求区域是连通的。n这种填充算法在交互式绘图中很常用。30区域填充算法n区域区域指已经表示成点阵形式的填充图形，它是象素的集合。n区域填充区域填充指先将区域的一点赋予指定的颜色，然后将该颜色扩展到整个区域的过程。区域填充算法要求区域是连通的31区域填充n表示方法：表示方法：内点表示、边界表示n内点表示内点表示n枚举处区域内部的所有像素n内部的所有像素着同一个颜色n边界像素着与内部像素不同的颜色n边界表示边界表示n枚举出边界上所有的像素n边界上的所有像素着同一颜色n内部像素着与边界像素不同的颜色32区域填充区域填充要求区域是连通的区域填充要求区域是连通

13、的n连通性连通性 4连通、8连通n4 4连通：连通：n8 8连通连通33区域填充n4 4连通与连通与8 8连通区域的区别连通区域的区别n连通性：连通性： 4 4连通可看作连通可看作8 8连通区域，但对边界有要求连通区域，但对边界有要求n对边界的要求对边界的要求34区域连通方式和填充结果4连通区域边界填充算法的填充结果8连通区域边界填充算法的填充结果35a：适合于内点表示区域的填充算法设g为一内点表示的区域，(x,y)为区域内一点，old_color为g的原色。现取(x,y)为种子点对区域g进行填充：即先置像素(x,y)的颜色为new_color，然后逐步将整个区域g都置为同样的颜色。 步骤如下

14、：种子象素入栈，当栈非空时，执行如下三步操作： （1）栈顶象素出栈； （2）将出栈象素置成new_color ； （3）按上、下、左、右的顺序检查与出栈象素相邻的四个象素，若其中某个象素在边界内且未置成new_color ，则把该象素入栈。种子填充算法36种子填充算法n例 ： 多 边 形 由p0p1p2p3p4构 成 ，p0(1,5)p1(5,5)p2(7,3)p3(7,1)p4(1,1)n设种子点为（3，3），搜索的方向是上、下、左、右。依此类推，最后像素被选中并填充的次序如图中箭头所示 37种子填充算法递归算法可实现如下递归算法可实现如下void floodfill4(int x,int

15、y,int oldcolor,int newcolor) if(getpixel(x,y) = oldcolor) putpixel(x,y,newcolor); floodfill4(x,y+1,oldcolor,newcolor); floodfill4(x,y-1,oldcolor,newcolor); floodfill4(x-1,y,oldcolor,newcolor); floodfill4(x+1,y,oldcolor,newcolor); /*end of floodfill4()*/ 38种子填充算法n边界表示的边界表示的4 4连通区域连通区域void boundaryfil

16、l4(int x,int y,int boundarycolor,int newcolor)int color;color = getpixel(x,y);if(color != boundarycolor) & (color != newcolor)putpixel(x,y,newcolor);boundaryfill4(x,y+1,oldcolor,newcolor);boundaryfill4(x,y-1,oldcolor,newcolor);boundaryfill4(x-1,y,oldcolor,newcolor);boundaryfill4(x+1,y,oldcolor,n

17、ewcolor);/*end of boundaryfill4()*/ 39n该算法也可以填充有孔区域。该算法也可以填充有孔区域。 n缺点缺点： (1) 有些象素会入栈多次，降低算法效率； (2) 递归执行，算法简单，但效率不高，区域内每一象素都引起一次递归，进/出栈，费时费内存。n改进算法，减少递归次数，提高效率。解决方法是用扫描线填充算法种子填充算法40种子填充算法n程序从(x, y)开始，先检测该点的颜色，如果它与边界色和填充色均不相同，就用填充色填充该点，然后检测相邻位置，以确定它们是否是边界色和填充色，若不是，就填充该相邻点。这个过程延续到已经检测完区域边界范围内的所有像素为止。67

18、54s932841种子填充算法演示6754s93286754s9328ss2479384794847956847968479784798479947947979942种子填充算法分析n有些象素会入栈多次，降低算法效率；栈结构占空间。n递归执行，算法简单，但效率不高，区域内每一象素都引起一次递归，进/出栈，费时费内存。43扫描线算法n扫描线算法扫描线算法n目标：减少递归层次目标：减少递归层次n适用于边界表示的适用于边界表示的4 4连通区域连通区域算法思想算法思想：在任意不间断区间中只取一个种子像素（不间断区间指在一条扫描线上一组相邻元素），填充当前扫描线上的该段区间；然后确定与这一区段相邻的上下

19、两条扫描线上位于区域内的区段，并依次把它们保存起来，反复进行这个过程，直到所保存的各个区段都填充完毕。44扫描线填充算法(1)初始化：堆栈置空。将种子点（x，y）入栈。(2)出栈：若栈空则结束。否则取栈顶元素（x，y），以y作为当前扫描线。(3)填充并确定种子点所在区段：从种子点（x，y）出发，沿当前扫描线向左、右两个方向填充，直到边界。分别标记区段的左、右端点坐标为xl和xr。(4)并确定新的种子点：在区间xl，xr中检查与当前扫描线y上、下相邻的两条扫描线上的象素。若存在非边界、未填充的象素，则把每一区间的最右象素作为种子点压入堆栈，返回第（2）步。上述算法对于每一个待填充区段，只需压栈一

20、次；因此，扫描线填充算法提高了区域填充的效率。45扫描线算法分析（举例分析）n该算法也可以填充有孔区域。像素中的序号标指它所在区段位于堆栈中的位置46扫描线算法分析（举例分析）47扫描线算法分析（举例分析）48扫描线算法分析（举例分析）49多边形扫描转换与区域填充方法比较联系：都是光栅图形面着色，用于真实感图形显示。可相互转换。多边形的扫描转换转化为区域填充问题：当给定多边形内一点为种子点，并用bresenham或dda算法将多边形的边界表示成八连通区域后，则多边形的扫描转换转化为区域填充。区域填充转化为多边形的扫描转换；若已知给定多边形的顶点，则区域填充转化为多边形的扫描转换。 50多边形扫

21、描转换与区域填充方法比较n不同点：1.基本思想不同；顶点表示转换成点陈表示后者只改变区域内填充颜色，没有改变表示方法。2.对边界的要求不同n前者只要求扫描线与多边形边界交点个数为偶数。后者：区域封闭，防止递归填充跨界。3.基本的条件不同n前者：从边界顶点信息出发。n后者：区域内种子点。51cohen-sutherland裁剪n将窗口边线两边沿长，得到九个区域，每一个区域都用一个四位二进制数标识。n编码的顺序为：上 下 右 左 10010001010110000000010010100010011052cohen-sutherland裁剪n直线的端点都按其所处区域赋予相应的区域码，用来标识出端点

22、相对于裁剪矩形边界的位置。bcd10010001010110000000010010100010011053cohen-sutherland裁剪n若p1p2完全在窗口内则code1=0,且code2=0n若p1p2完全在窗口外则code1&code20n其他情况在交点处把线段分为两段。其中一段完全在窗口外，可弃之。然后对另一段重复上述处理。100110001010000100000010010101000110p1p2p3p454编码的计算nint encode(float x,float y)nnint c;nc=0;nif(xxr)nc=c|right;nif(yyt)nc=c|t

23、op;nreturn c;n#define left 1#define right 2#define bottom 4#define top 855交点的计算n计算线段p1(x1,y1)p2(x2,y2)与窗口边界的交点if(left&code)!=0)/*当直线和左边界有交点*/x=xl;y=y1+(y2-y1)*(xl-x1)/(x2-x1);else if(right&code)!=0)x=xr;y=y1+(y2-y1)*(xr-x1)/(x2-x1);else if(bottom&code)!=0) y=yb;x=x1+(x2-x1)*(yb-y1)/(y2-y

24、1); else if(top & code)!=0) y=yt;x=x1+(x2-x1)*(yt-y1)/(y2-y1);56cohen-sutherland代码nvoid cs_lineclip(float x1,float y1,float x2,float y2)nn code1=encode(x1,y1);code2=encode(x2,y2);n while(code1!=0 |code2!=0)n n if(code1&code2)!=0) return;n code = code1;n if(code1=0) code = code2;n （求交点）n if(c

25、ode =code1)x1=x; y1=y;code1 =encode(x,y);n elsex2=x;y2=y;code2 =encode(x,y);nnsetcolor(4);nline(x1,y1,x2,y2);n57cohen-sutherland算法分析n优点：n用编码方法可快速判断线段的完全可见和显然不可见。n简单，易于实现。n缺点：n本算法对于其它形状的窗口未必同样有效。58中点分割裁剪算法n与cohen-sutherland算法一样首先对线段端点进行编码，并把线段与窗口的关系分为三种情况，对前两种情况，进行一样的处理；对于第三种情况，用中点分割的方法求出线段与窗口的交点。p0p

26、1pmab59中点分割裁剪算法n所谓中点分割算法实质上是采用对分查找法求交点。n将线段分割成相等的两段，然后对每一小段重复上述的检查，直至找到每段与窗口边界的交点或分割小段的长度充分小，可以视为一点时为止。p0p1pmab60中点分割裁剪算法n从p0点出发利用中点分割算法找出离p0最近的可见点a。n从p1点出发利用中点分割算法找出离p1最近的可见点b。p0p1pmab61中点分割裁剪算法n从p0出发找距离p0最近可见点：n先求出p0p1的中点pm,n若p0pm不是显然不可见的，则距p0最近的可见点一定落在p0pm上，所以用p0pm代替p0p1；n否则取pmp1代替p0p1。n再对新的p0p1求

27、中点pm。重复上述过程，直到pmp1长度小于给定的控制常数为止，此时pm收敛于交点。62中点分割裁剪算法63中点分割裁剪算法实现n求中点：n判断取舍：np1与pm同侧，移动p1点；if(c1&c)!=0) p1=p;np1与pm不同侧，移动p2点。if(c1&c)=0) p2=p;pmp1用用p1pm代替代替p1p2p2p2用用pmp2代替代替p1p2pmp164梁友栋-barskey算法n 设要裁剪的线段是p0p1。 p0p1和窗口边界交于a,b,c,d四点，见图。算法的基本思想是从a,b和p0三点中找出最靠近p1的点，图中要找的点是p0。从c,d和p1中找出最靠近p0的点。

28、图中要找的点是c点。那么p0c就是p0p1线段上的可见部分。65n思想：基于直线段参数方程分析的快速直思想：基于直线段参数方程分析的快速直线裁剪算法线裁剪算法n参数方程参数方程直线两端点直线两端点 p1(x1, y1), p2 (x2, y2)x = x1 + (x2 - x1)uy = y1 + (y2 - y1)u, 0u1梁友栋-barskey算法66n已知直线端点已知直线端点 ： 起点起点p1(x1, y1)，终点，终点p2(x2, y2)n参数方程：参数方程：x = x1 + (x2 - x1)uy = y1 + (y2 - y1)u p1p2u167n参数化形式写出裁剪条件： 可以

29、统一表示为形式： k = 1, 2, 3, 4 入边 出边121121 , xlxu xxrxxxybyuyytyyy，kkqup 144133122111yytqypybyqypxxrqxpxlxqxp68n =0 且 0，则线段完全在边界外， 0，则该线段平行于裁剪边界并且在窗口内。kpkqkq69n当 0，n当 0,线段从裁剪边界延长线的内部延伸到外部。kpkpkp70 当pk0时，直线是从裁剪窗口第k条边界线的外部延伸到内部。例如当p10时，则x2x1, 直线必然从裁剪窗口的左边界线的外部进入内部，如下图中的线段p1p2。当pk0时，直线是从裁剪窗口第k条边界线的内部延伸到外部。例如p

30、20时，则x2x1, 直线必然从裁剪窗口的右边界线的内部进入外部,如下图中的线段p3p4。71xlxrybytubulutur01dxdy72 当pk不等于零时，可以计算出线段与第k条裁剪窗口边界线的交点参数： 根据定义，对于每条线段，pk中必有两个小于零，而另两个大于零。对于小于零的pk，直线同第k条裁剪窗口边线是从外到内相遇的，此时如果线段同第k条裁剪窗口边界线有交点的话，是参数u从0变大时遇到的，这时计算出相应的rk值，取0和各个rk值之中的最大值记为u1。与此相反，对于大于零的pk，计算出相应的rk值，取1和各个rk值之中的最小值记为u2。两个参数u1和u2定义了在裁剪窗口内的线段部分

31、。如果u1u2，则线段完全落在裁剪窗口之外，应被舍弃。否则被裁剪线段可见部分的端点由参数u1和u2计算出来。rk=qk/pk73n算法描述算法描述n计算计算 pk, qk, k=14npk = 0，表示直线平行于窗口某边界，表示直线平行于窗口某边界nqk = 0，直线在窗口内，平行边界内，直线在窗口内，平行边界内n对对 pk0的情形的情形, 用用qk/pk计算交点所对计算交点所对应的应的u值值74n对每条线计算参数对每条线计算参数u1&u2u1=max(qk/pk|pk 0 u 1)n如果如果u1 u2, 则直线在窗口外，否则计算则直线在窗口外，否则计算交点坐标交点坐标 x(u) =

32、x1+dx*u y(u) = y1+dy*u75lblb线段裁剪算法线段裁剪算法 例例1 1n已知线段的两个端点已知线段的两个端点p1(3, 4)，p2(8, 2) 窗口边界窗口边界x=1, x=4, y=1, y=3n用用lb算法对线段进行裁剪算法对线段进行裁剪76n线段的参数方程 x = 3 + 5u y = 4 - 2unp1 = -5, q1 = 2, r1 = -2/5p2 = 5, q2 = 1, r2 = 1/5p3 = 2, q3 = 3, r3 = 3/2p4 = -2, q4 = -1, r4 = 1/2nu1 = max(0, -2/5, 1/2) = 1/2u2 = m

33、in(1, 1/5, 3/2) = 1/5nu1 u2 所以线段全部被裁剪77线段的两个端点（线段的两个端点（-2，-1）和（）和（1，1.5）窗口边界窗口边界x1 = -1, x2 = 1, y1 = -1, y2 = 1lb线段裁剪算法线段裁剪算法 例例278x = 3, y = 2.5 p1 = -3q1 = -1 r1 = 1/3 p2 = 3q2 = 3r2 = 1p3 = -2.5 q3 = 0r3 = 0p4 = 2.5q4 = 2r4 = 4/5对于p 0，u2 = min1，1， 4/5 = 4/5则u1u2，则可见线段的端点坐标：x = x1 + u1 x = -1,y = y1 + u1 y = -1/6 即(-1, -1/6)x=x1+u2 x=2/5,y=y1+u2 y =1 即(2/5, 1)79图形变换n平移、对称、旋转、错切、缩放。构成图形的控制点的位置发生变化构成图形的控制点的个数和拓扑关系没有发生变化8081矩阵表示nx y=x y+m n1001yxyxcossinsincosyxyx101tgyxyx82几何变换n平移变换n比例变换n旋转变换n沿x错切变换101000