资源预览内容
第1页 / 共123页
第2页 / 共123页
第3页 / 共123页
第4页 / 共123页
第5页 / 共123页
第6页 / 共123页
第7页 / 共123页
第8页 / 共123页
第9页 / 共123页
第10页 / 共123页
亲,该文档总共123页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
第2章 光栅图形学2.1直线段的扫描转换算法 2.2圆弧的扫描转换算法 2.3多边形的扫描转换与区域填充 2.4字符 2.5裁剪 2.6反走样 2.7消隐计算机图形学基础 2.1 直线段的扫描转换算法直线的扫描转换: 确定最佳逼近于该直线的 一组象素,并且按扫描线顺序,对这些象 素进行写操作。 三个常用算法: 2.1.1数值微分法(DDA) 2.1.2中点画线法 2.1.3Bresenham算法。计算机图形学基础 2.1.1 数值微分(DDA)法基本思想 已知过端点P0 (x0, y0), P1(x1, y1)的直线段L y=kx+b直线斜率为 从x的左端点x0开始,向x右端点步进。步长=1(个象 素),计算相应的y坐标y=kx+B;取象素点(x, round(y)作为当前点的坐标。计算机图形学基础 计算yi+1= kxi+1+B = k1 xi+B+kx= yi+kx 当x =1;yi+1 = yi+k 即:当x每递增1,y递增k(即直线斜率); 注意上述分析的算法仅适用于k 1的情形 。在这种情况下,x每增加1,y最多增加1。 当 k 1时,必须把x,y地位互换计算机图形学基础 例:画直线段p(0,0)-P1(5,2)x int(y+0.5) y+0.5 000 100.4+0.5 210.8+0.5 311.2+0.5 421.6+0.5 522.0+0.5 注:网格点表示象素计算机图形学基础 void DDALine(int x0,int y0,int x1,int y1,int color) int x; float dx, dy, y, k; dx, = x1-x0, dy=y1-y0; k=dy/dx, y=y0; for (x=x0; xx1, x+) drawpixel (x, int(y+0.5), color); y=y+k;计算机图形学基础 2.1.2 中点画线法基本思想 当前象素点为(xp, yp) 。下一个象素点为P1或P2。 设M=(xp+1, yp+0.5),为p1与p2 之中点,Q为理想直线与x=xp+1 垂线的交点。将Q与M的y坐标进行比较。 当M在Q的下方,则P2 应为下一个象素点; M在Q的上方,应取P1为下一点。计算机图形学基础 构造判别式:d=F(M)=F(xp+1,yp+0.5)=a(xp+1)+b(yp+0.5)+c其中a=y0-y1, b=x1-x0, c=x0y1-x1y0当d0,M在L(Q点)上方,取右方P1为下一个象素; 当d=0,选P1或P2均可,约定取P1为下一个象素;d是xp, yp的线性函数,因此可采用增量计算,提高运算效率 。计算机图形学基础 若当前象素处于d0情况,则取正右方象素P1(xp+1, yp), 要判下一个象素位置,应计算d1=F(xp+2, yp+0.5)=a(xp+2)+b(yp+0.5)=d+a; 增量为a若d=0, 则应取P2为下一象素,而且下一象素的判别式为第 一个象素是(0,R),判别式d的初始值为计算机图形学基础 为了进一步提高算法的效率,可以将上面 的算法中的浮点数改写成整数,将乘法运 算改成加法运算,即仅用整数实现中点画 圆法。 使用e=d-0.25代替d e0=1-R计算机图形学基础 算法过程MidPointCircle(int r int color) int x,y;float d;x=0; y=r; d=1.25-r;circlepoints (x,y,color); /显示圆弧上的八个对称点while(x i 结点的x值递增x; 若允许多边形的边自相交,则用冒泡排 序法对AET表重新排序; /* polyfill */计算机图形学基础 边界标志算法基本思想: 帧缓冲器中对多边形的每条边进行直线扫描转 换,亦即对多边形边界所经过的象素打上标志 。 然后再采用和扫描线算法类似的方法将位于多 边形内的各个区段着上所需颜色。 使用一个布尔量inside来指示当前点是否在多 边形内的状态。计算机图形学基础 算法过程void edgemark_fill(polydef, color) 多边形定义 polydef; int color; 对多边形polydef 每条边进行直线扫描转换;inside = FALSE;for (每条与多边形polydef相交的扫描线y )for (扫描线上每个象素x ) if(象素 x 被打上边标志)inside = ! (inside);if(inside!= FALSE)drawpixel (x, y, color);else drawpixel (x, y, background);计算机图形学基础 用软件实现时,扫描线算法与边界标志算 法的执行速度几乎相同, 但由于边界标志算法不必建立维护边表以 及对它进行排序,所以边界标志算法更适 合硬件实现,这时它的执行速度比有序边 表算法快一至两个数量级。计算机图形学基础 2.3.2区域填充算法区域指已经表示成点阵形式的填充图形, 它是象素的集合。 区域可采用内点表示和边界表示两种表示 形式。 区域可分为4向连通区域和8向连通区域。 区域填充指先将区域的一点赋予指定的颜 色,然后将该颜色扩展到整个区域的过程 。区域填充算法要求区域是连通的计算机图形学基础 4向连通区域和8向连通区域四个方向运动 八个方向运动 四连通区域 八连通区域计算机图形学基础 区域填充的递归算法内点表示的4连通区域的递归填充算法: void FloodFill4(int x,int y,int oldcolor,int newcolor) if(getpixel(x,y)=oldcolor) /属于区域内点oldcolor drawpixel(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); 计算机图形学基础 边界表示的4连通区域的递归填充算法: void BoundaryFill4(int x,int y,int boundarycolor,int newcolor) int color; if(color!=newcolor BoundaryFill4 (x,y+1, boundarycolor,newcolor); BoundaryFill4 (x,y-1, boundarycolor,newcolor); BoundaryFill4 (x-1,y, boundarycolor,newcolor); BoundaryFill4 (x+1,y, boundarycolor,newcolor); 计算机图形学基础 区域填充的扫描线算法算法步骤: 首先填充种子点所在扫描线上的位于给定区域 的一个区段 然后确定与这一区段相连通的上、下两条扫描 线上位于给定区域内的区段,并依次保存下来 。 反复这个过程,直到填充结束。计算机图形学基础 (1)初始化:堆栈置空。将种子点(x,y)入栈。 (2)出栈:若栈空则结束。否则取栈顶元素(x,y),以y作为 当前扫描线。 (3)填充并确定种子点所在区段:从种子点(x,y)出发,沿 当前扫描线向左、右两个方向填充,直到边界。分别标记区段 的左、右端点坐标为xl和xr。 (4)并确定新的种子点:在区间xl,xr中检查与当前扫描线y上 、下相邻的两条扫描线上的象素。若存在非边界、未填充的象 素,则把每一区间的最右象素作为种子点压入堆栈,返回第( 2)步。 上述算法对于每一个待填充区段,只需压栈一次;因此,扫描 线填充算法提高了区域填充的效率。计算机图形学基础 2.4 字 符字符指数字、字母、汉字等符号。 计算机中字符由一个数字编码唯一标识。 “美国信息交换用标准代码集”简称ASCII码 。它是用7位二进制数进行编码表示128个字符 汉字编码的国家标准字符集。每个符号由一个 区码和一个位码(2字节)共同标识。 区分ASCII码与汉字编码,采用字节的最高位 来标识计算机图形学基础 点阵字符:每个字符由一个位图表示 矢量字符:记录字符的笔画信息点阵字符 点阵字库中的位图表示 矢量轮廓字符计算机图形学基础 特点: 点阵字符:存储量大,易于显示 矢量字符:存储量小,美观,变换方便 需要光栅化后才能显示。计算机图形学基础 字符属性字体 宋体 仿宋体 楷体 黑体 隶书字高 宋体 宋体 宋体 宋体字宽 字倾斜角 倾斜 倾斜 对齐 (左对齐、中心对齐、右对齐) 字色 红色、绿色、蓝色 写方式:替换方式。与方式计算机图形学基础 2.5 裁剪裁剪:确定图形中哪些部分落在显示区之内,哪些落 在显示区之外,以便只显示落在显示区内的那部分图形。 这个选择过程称为裁剪。2.5.1直线段裁剪 2.5.2 多边形裁剪计算机图形学基础 2.5.1直线段裁剪直线段裁剪算法是复杂图元裁剪的基础。 复杂的曲线可以通过折线段来近似,从而 裁剪问题也可以化为直线段的裁剪问题。计算机图形学基础 Cohen-Sutherland裁剪基本思想:对于每条线段P1P2分为三种情况处理分为 三种情况处理: (1)若P1P2完全在窗口内,则显示该线段P1P2简称“ 取”之。 (2)若P1P2明显在窗口外,则丢弃该线段,简称“弃 ”之。 (3)若线段不满足“取”或 “弃”的条件,则在交 点处把线段分为两段。其中一段完全在窗口外,可弃 之。然后对另一段重复上述处理。计算机图形学基础 为快速判断,采用如下编码方法: 每个区域赋予4位编码计算机图形学基础 编码 线段裁剪计算机图形学基础 若P1P2完全在窗口内code1=0,且code2=0,则“ 取”若P1P2明显在窗口外code1y=y1+(y2-y1)*(XL-x1)/(x2-x1); else if(RIGHTy=y1+(y2-y1)*(XR-x1)/(x2-x1); else if(BOTTOMx=x1+(x2-x1)*(YB-y1)/(y2-y1);else if(TOP x=x1+(x2-x1)*(YT-y1)/(y2-y1);计算机图形学基础 中点分割裁剪算法基本思想:与前一种Cohen-Sutherland算法一样首先对线 段端点进行编码,并把线段与窗口的关系分为三 种情况: 全在、完全不在和线段和窗口有交。对前两种 情况,进行一样的处理。 对于第三种情况,用中点分割的方法求出线段 与窗口的交点。计算机图形学基础 求线段与窗口的交点A、B分别为距p0、p1最近的可见点,Pm为p0p1中点计算机图形学基础 从 出发找最近可见点的方法 先求出 的中点 若 不是显然不可见的,并且 在窗口 中有可见部分,则距 最近的可见点一定落在 上,所以用 代替 ;计算机图形学基础 否则取 代替再对新的 求中点 。重复上述过程,直 到 长度小于给定的控制常数为止,此时 收敛于交点。从p1出发找最近可见点采用上面类似方法。计算机图形学基础 梁友栋Barskey算法梁-Barskey算法的几何含义计算机图形学基础 参数化形式写出裁剪条件:可以统一表示为形式:计算机图形学基础 pk=0且qk0,线段从裁剪边
收藏 下载该资源
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号