第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,线段从裁剪边