《计算机图形学》电子教案 第3章

《《计算机图形学》电子教案 第3章》由会员分享，可在线阅读，更多相关《《计算机图形学》电子教案 第3章（48页珍藏版）》请在金锄头文库上搜索。

1、第3章 基本图形 生成算法,3.1 生成直线的常用算法,均假定所画直线的斜率k0，1。 3.1.1 DDA画线算法 DDA（Digital Differential Analyzer）画线算法也称数值微分法，是一种增量算法。它的算法实质是用数值方法解微分方程，通过同时对x和y各增加一个小增量，计算下一步的x、y值。,已知一条直线段L（P0, P1）,其端点坐标为：P0 (x0, y0), P1(x1, y1)。可计算出直线的斜率k为： 假定端点坐标均为整数，取直线起点P0 (x0, y0)作为初始坐标。画线过程从x的左端点x0开始，向x右端点步进，每步x递增1，y递增k（即直线斜率）；取像素点

2、（x，round（y）作为当前点的坐标。,3.1.2 中点画线算法 假设x坐标为xp的各像素点中，与直线最近者已确定，为P（xp,yp），那么，下一个与直线最近的像素只能是正右方的P1(xp+1,yp)，或右上方的P2（xp+1,yp+1）两者之一。令M为P1和P2的中点，易知M的坐标为（xp+1,yp+0.5）。 设Q是理想直线与垂直线x=xp+1 的交点。显然，若M在Q的下方，则P2 离直线近，应取为下一个像素；否则应 取P1。,令a=y0-y1，b=x1-x0，c=x0y1-x1y0。 构造判别式： d=a(xp+1)+b(yp+0.5)+c d的初始值d0 = a+0.5b 在d0的情

3、况下，取正右方像素P1， d1=a(xp+2)+b(yp+0.5)+c =d+a 在d0的情况下，取右上方像素P2， d2=a(xp+2)+b(yp+1.5) = d+a+b,由于我们使用的只是d的符号，而且d的增量都是整数，只是其初始值包含小数。因此，我们可以用2d代替d，来摆脱小数。 如果进一步把算法中2*a改为a+a等等，那么这个算法不仅只包含整数变量，而且不包含乘除法，适合硬件实现。,3.1.3 Bresenham画线算法 过各行各列像素中心构造一组虚拟网格线，按直线从起点到终点的顺序计算直线与各垂直网格线的交点，然后确定该列像素中与此交点最近的像素。 由图3-5不难看出：若st， 则

4、Si比较靠近理想直线，应 选Si;若st，则Ti比较靠近 理想直线，应选Ti。,令dx=x2-x1，dy=y2-y1 递推公式 ： di的初值： 当di0时，选Ti， 当di0时，选Si， 由于只包含加、减法和左移（乘2）的运算，而且下一个像素点的选择只需检查di的符号，因此Bresenham画线算法很简单，速度也相当快。,3.1.4 直线属性 1线型 2线宽 3线色,3.2 生成圆弧的常用算法,3.2.1 圆的特性 圆心位于原点的圆有四条对称轴：x=0，y=0，x=y和x=-y直线。若已知圆弧上一点（x,y），可以得到其关于四条对称轴的其它7个点，这种性质称为八对称性，如下图所示。 本节讨论

5、的圆的生成算法 均只计算从x=0到x=y分段内 （1b区域）的像素点，其余的 像素位置利用八对称性即可得 出。,3.2.2 中点画圆算法 假设x坐标为xp的各像素点中，与该圆弧最近者已确定，为P（xp,yp），那么，下一个与圆弧最近的像素只能是正右方的P1(xp+1,yp)，或右下方的P2（xp+1,yp-1）两者之一。 令M为P1和P2的中点，易知 M的坐标为（xp+1,yp-0.5）。 显然，若M在圆内，则P1离圆弧 近，应取为下一个像素；否则应 取P2。,判别式d： d的初始值为： 在d0的情况下，取右下方像素P2， 在d0的情况下，取正右方像素P1，,3.2.3 Bresenham画圆

6、算法 假设生成圆心在坐标原点，半径为r，从x=0到x=y的1/8圆弧。 xi+1=xi +1 相应的y则在两种可能中选择： y=yi，或者y=yi-1 选择的原则是考察理想的y值 是靠近yi还是靠近yi-1。,判别式： d i+1=2(xi+1)2+yi2+(yi-1)2-2r2 判断式d的初始值为： d0= 3-2r。 如果d i+1=0，则y=yi-1， di+2 =d i+1 + 4(xi- yi)+10 如果d i+10，则y=yi， d i+2 =d i+1+ 4x i+6,3.3 区域填充,3.3.1 区域的表示和类型 顶点表示：也称为几何表示，是用区域的顶点序列来表示区域。 点阵

7、表示：也称为像素表示，是用位于多边形内的像素集合来刻画多边形。 内点表示：区域内的所有像素着同一颜色，而区域外的所有像素具有另一种颜色； 边界表示：区域边界上的所有像素点具有特定的颜色（可以是填充色），在区域内的所有像素均不能具有这一特定色，而且边界外的像素不能具有与边界相同的颜色。,区域填充算法要求区域是连通的，因为只有在连通区域中，才可能将种子点的颜色扩展到区域内的其它点。 区域按连通情况又可分为四连通区域和八连通区域。 四连通区域指的是从区域上一点出发，可通过四个方向，即上、下、左、右移动的组合，在不越出区域的前提下，到达区域内的任意像素。 八连通区域指的是从区域内每一像素出发，可通过八

8、个方向，即上、下、左、右、左上、右上、左下、右下移动的组合，在不越出区域的前提下，到达区域内的任意像素。,3.3.2 扫描线多边形填充算法 扫描线多边形填充算法是按扫描线顺序，计算扫描线与多边形的相交区间，再用要求的颜色显示这些区间的像素，即完成填充工作。 对于一条扫描线，多边形的填充过程可以分为四个步骤： 求交 排序 配对 填色,边表（ET）：边表一般是由一系列的存储桶构成的，桶的数目与扫描线数一样多，按扫描线递增（减）顺序存放。 边表的建立：先按下端点的y坐标值对所有的边进行分组，若某边的下低端点y值为ymin，则该边就放在ymin所对应的桶中；然后用排序方法，按下端点的x坐标值递增的顺序

9、将同一组中的边排列成行。 活化链表（AEL）：我们把与当前扫描线相交的边称为活性边，并把它们按与扫描线交点x坐标递增的顺序存放在一个链表中，称此链表为活化链表（AEL）。,ET和AEL中的基本元素为多边形的边。边表示成结点的形式，每个边结点由以下四个域组成： 其中，各符号的含义为： ymax： 边的上端点的y坐标 x：在ET中表示边的下端点的x坐标，在AEL中表示边与扫描线的交点的x坐标 1/k：边的斜率的倒数 next：指向下一条边的指针,当建立了边表ET后，扫描线多边形填充算法可按如下步骤进行： （1）初始化AEL，使之为空，取扫描线纵坐标y的初始值为ET中非空元素的最小序号。 （2）按从

10、下到上的顺序对每条扫描线重复以下各步，直至AEL和ET为空 。 将ET中与当前y有关的结点加入至AEL，同时保存AEL中按x值从小到大实现的排序序列 对于AEL中的扫描线y，在一对交点之间填充所需要的像素值 从AEL中删掉y=ymax的结点 对于留在AEL中的每个结点，执行xi+1=xi + 1/k 对AEL中的各结点按x值从小到大排序 y =y+1，成为下一条扫描线的坐标,3.3.3 边填充算法 基本原理：对每一条扫描线，依次求与多边形各边的交点，将该扫描线上交点右边的所有像素求补。 算法虽然简单易行，但对于复杂图形而言，一些像素的颜色值需反复改变多次，且多边形外的像素处理过多，输入、输出的

11、量比有序边表大的多。,栅栏填充算法： 对于每条扫描线与多边形的交点，将交点与栅栏之间的扫描线上的像素取补，也就是说，若交点位于栅栏左边，则将交点之右、栅栏之左的所有像素取补；若交点位于栅栏右边，则将栅栏之右、交点之左的所有像素取补。 多边形外的像素处理大大减少，被重复取补的像素数目也有减少，但仍有一些像素被重复取补。,边标志算法： 对多边形边界所在像素置一个特殊标志；对于每条与多边形相交的扫描线，从左至右逐个访问该扫描线上的像素。使用一个布尔变量inside来指示当前点的状态，若点在多边形内，则inside为真。若点在多边形外，则inside为假。inside 的初始值为假，每当当前访问像素为

12、被打上标志的点，就把inside取反。对未打标志的点，inside不变。若访问当前像素时，对inside作必要操作之后，inside为真，则把该像素置为多边形要填充的颜色。 对每个像素只访问一次，硬件执行速度快。,3.3.4 种子填充算法 基本思想：假设在多边形区域内部至少有一个像素是已知的（此像素称为种子像素），由此出发找到区域内所有其他像素，并对其进行填充。 由于区域可采用边界定义和内点定义两种方式，区域按连通性又可分为四连通区域和八连通区域两类，所以常用的种子填充算法有： 边界表示的四连通区域种子填充算法 内点表示的四连通区域种子填充算法 边界表示的八连通区域种子填充算法 内点表示的八连

13、通区域种子填充算法,1边界表示的四连通区域种子填充算法 基本思想：从多边形内部任一点（像素）出发，依“左上右下”顺序判断相邻像素，若其不是边界像素且没有被填充过，对其填充，并重复上述过程，直到所有像素填充完毕。 可以使用栈结构来实现该算法，算法的执行步骤如下： 种子像素入栈，当栈非空时，重复执行如下三步操作： （1）栈顶像素出栈； （2）将出栈像素置成多边形填充的颜色； （3）按左、上、右、下的顺序检查与出栈像素相邻的四个像素，若其中某个像素不在边界上且未置成多边形色，则把该像素入栈。,2内点表示的四连通区域种子填充算法 基本思想：从多边形内部任一点（像素）出发，依“左上右下”顺序判断相邻像素

14、，如果是区域内的像素，则对其填充，并重复上述过程，直到所有像素填充完毕。它也常称为漫水法。 可以使用栈结构来实现该算法，算法的执行步骤如下： 种子像素入栈，当栈非空时，重复执行如下三步操作： （1）栈顶像素出栈； （2）将出栈像素置成多边形填充的颜色； （3）按左、上、右、下的顺序检查与出栈像素相邻的四个像素，若其中某个像素是区域内的像素，则把该像素入栈。,3扫描线种子填充算法 算法思想：在任意不间断区间中只取一个种子像素（不间断区间指在一条扫描线上一组相邻元素），填充当前扫描线上的该段区间；然后确定与这一区段相邻的上下两条扫描线上位于区域内的区段，并依次把它们保存起来，反复进行这个过程，直到

15、所保存的每个区段都填充完毕。 可以填充有孔区域，对于每一个待填充区段，只需入栈一次，因此提高了区域填充的效率。,3.3.5 圆域的填充 对每条扫描线，计算它与圆域的相交区间。接着，为每一条扫描线建立一个新圆表，存放在该行第一次出现的圆的有关信息。然后，为当前扫描线设置一个活化圆表。由于一条线与一个圆只能相交一个区间，所以在活性圆表中，每个圆只需一个结点即可。结点内存放当前扫描线的区间端点，以及用于计算下一条扫描线与圆相交的区间端点所需的增量。该增量用于在当前扫描线处理完毕之后，对端点坐标进行更新计算，以便得到下一条扫描线的区间端点。,3.3.6 区域填充属性 1填充样式 2填充颜色 3填充图案

16、,3.4 字符,3.4.1 字符存储与显示 1点阵字符 每个字符都是利用掩膜来定义，并将其写入帧缓存保存和显示。 点阵字符的显示：首先从字库中将它的位图检索出来，然后将检索到的位图写到帧缓冲器中。读取帧缓存中这些像素值，就可以在屏幕上显示此字符。如果将保存在帧缓存中某字符掩膜相应像素值均置成背景色或背景光强，就可以擦除帧缓存中的该字符。,2矢量字符 矢量字符被表达为一个点坐标的序列，相邻两点表示一条矢量，字符的形状便由矢量序列刻划。 矢量字符的显示：首先从字库中读它的字符信息。然后取出端点坐标，对其进行适当的几何变换，再根据各端点的标志显示出字符。,3.4.2 字符属性 显示的字符的外观由字体、字形、字号、字间距、行间距等属性控制。一般来说，字体确定风格，字形确定外观，字号确定尺寸。 1单个字符属性 2文本属性,3.5 裁剪,3.5.1 点的裁剪 对于一点P（x , y），要判断其是否可见，可利用下面的不等式组来判断此点是否落在窗口范围内： 满足上述不等式组的点则在窗口范围内，可见