《基本图形生成算法》由会员分享，可在线阅读，更多相关《基本图形生成算法（57页珍藏版）》请在金锄头文库上搜索。
1、 2004 Dept. of Computer Science and Engineer *第四章 基本图形生成算法 （三） 2004 Dept. of Computer Science and Engineer *2 / 59主要内容：直线的扫描转换圆与椭圆的扫描算法区域填充线宽与线型的处理字符裁剪反走样 2004 Dept. of Computer Science and Engineer *3 / 59字符字符的生成：-包括数字、字母、汉字与符号（电路、公差、液压)等；标准字符集-美国信息交换用标准代码集（ASCII）： 共127个。 031 不可见，控制字符。 32127可见（大小写字
2、母，数字，运算符号，标点符号等）。 编码用一个字节可以表示-信息交换用汉字编码字符集基本集（GB2312-80）: 汉字量大，必须用两个字节表示。 6000多个常用汉字，英文字母、数字和其他图形符号；-为在终端或绘图仪上输出字符，系统中必须装备有字符库。字符库中存放 了每个字符的形状信息。 2004 Dept. of Computer Science and Engineer *4 / 59字符 字符库分有矢量型和点阵型两种； 笔式绘图仪：矢量型字符，采用矢量代码序 列表示字符的各个笔画； 终端显示器：点阵型字符库，为每个字符定 义一个字符掩膜，即表示该字符的象素图案 的一个点阵；-1） 点阵
3、字符 每个字符定义成称为字符掩膜的矩阵； 西文字符：57的点阵字符； 汉文字符：1616的点阵字符； 打印：2424，4040，7272的点阵字符 特殊字符：按需确定。A二进制数表示的矩阵编码（ASCII）存储西文需35位，4个多字节 存储汉文需256位，32个字节问题：信息量大，质量，变换，动画，.解决：压缩，矢量。 2004 Dept. of Computer Science and Engineer *5 / 59字符2）矢量字符对每个字符定义矢量代码序列描述字符的几何形状：- 不同的应用使用不同的方法。 以AutoCAD采用的定义方法为例： -AutoCAD采用一种称为形（SHAPE）
4、的实体来定义字符 -基本笔画：直线和圆弧 -形描述格式如下：* ， ，0 2004 Dept. of Computer Science and Engineer *6 / 59字符0123456789AEFBCD形编号：1255整数； 字节数：形定义描述行中包括结 束符0在内的字节数目； 形名称：用大写字母；否则认为 是形的解释性信息，不存储； ：定义字符组成矢量的 方向和大小，分为标识位、低四 位和高四位三组数字。标识位表 示十六进制（0）或十进制（无 标识位）;高四位表示矢量的长 度，低四位表示矢量方向。 如：040即表示一16进制数，其 中，4表示矢量的长度，0表示矢 量方向。所有矢量都
5、具有“相同”的长 度，即（2）的单位长度是（ 0）的单位长度的2倍 2004 Dept. of Computer Science and Engineer *7 / 59字符实例：二极管符号：* 133, 11, DIDOE040, 044, 04c, 042, 04c, 040, 048, 04c, 046, 04c, 0把每一个字符都按上述方法描述后，存入一形文件中，即建 立了相应的矢量字符库。 2004 Dept. of Computer Science and Engineer *8 / 59字符字型技术：节约空间，采用压缩技术（字型数据压缩存储，使 用时，还原成字符点阵）：-黑白段压
6、缩法： 优点：简单快速不失真； 缺点：压缩较差，不方便，一般用于低级文字处理系统；-部件压缩法： 优点：压缩比大 缺点：字型质量不保证；-轮廓字型法：压缩比大，质量保证（采用直线、BEZIER曲线 的集合描述字符的轮廓线; 轮廓线和控制信息（属性、控制点/线）构成压缩数据，结合填充算法 以取得较好的效果； 2004 Dept. of Computer Science and Engineer *9 / 59字符 一种轮廓字型法：True Type字型技术-Apple和Microsoft公司联合开发；-利用二次Bezier曲线描述字符轮廓，对字符轮廓线的控制点 进行编号； 顺序：按顺时针方向走一
7、圈，填充部分始终在其右边。 以大写字母H为例： 2004 Dept. of Computer Science and Engineer *10 / 59字符True Type字型控制信息-X方向控制信息： 1）字身最左起始点到字母主干的距离间隙； 2）字母主题部分的宽度； 3）字身的宽度； 4）字母H主干的宽度； 5）字母H的衬线；-Y方向控制信息： 6）字母H横干的厚度； 7）字母H衬线的厚度； 8）字母主题部分的厚度； 9）字母H横干的高度；-产生控制信息表； 2004 Dept. of Computer Science and Engineer *11 / 59字符字符的输出：-绘图仪输
8、出：方向、位移值转换为设备驱动指令；-显示器/打印机输出：指定字符掩膜的原点与祯缓存中的字符 左下脚位置对应，从而将字符掩膜中的值平移的写入祯缓存 中； 2004 Dept. of Computer Science and Engineer *12 / 59主要内容：直线的扫描转换圆与椭圆的扫描算法区域填充线宽与线型的处理字符裁剪反走样 2004 Dept. of Computer Science and Engineer *13 / 59裁剪 直线段裁剪 裁剪目的-判断图形元素是否落在裁剪窗口之内并找出其位于内部的部分； 裁剪处理的基础-图元关于窗口内外关系的判别；-图元与窗口的求交； 假定
9、条件-裁剪窗口：xmin,xmax，ymin,ymax-待裁剪线段： 待裁剪线段和窗口的关系 -1）线段完全可见 -2）显然不可见 -3）线段至少有一端点在窗口之外，部分线段可见为提高效率，算法设计时应考虑： (一）快速判断情形(1)(2)； (二) 设法减少情形(3)求交次数和每次求交时所需的计算量。 2004 Dept. of Computer Science and Engineer *14 / 59裁剪 直线段裁剪点裁剪-点(x, y)在窗口内的充 分必要条件是：线段裁剪方法：-Cohen-SutherLand裁减算 法-中点分割算法；-参数化方法； 直接求交算法步骤 2004 Dep
10、t. of Computer Science and Engineer *15 / 59裁剪 直线段裁剪 Cohen-SutherLand算法Cohen-SutherLand算法-算法步骤： 第一步 判别线段两端点是否都落在窗口内，如果是，则线段完全可见 ；否则进入第二步； 第二步 判别线段是否为显然不可见，如果是-裁剪结束；否则继续； 第三步 求线段与窗口边延长线的交点，这个交点将线段分为两段，其 中一段显然不可见，丢弃。 第四步 对余下的另一段重新进行判断，直至结束 ；裁剪过程是递归过程！ 2004 Dept. of Computer Science and Engineer *16 /
11、59裁剪 直线段裁剪 Cohen-SutherLand算法Cohen-SutherLand算法的改进：编码算法-目的：对显然不可见线段实现快速判别；-编码方法：由窗口四条边所在直线把二维平面分成9个区域，每个区域赋 予一个四位编码，Ct Cb Cr Cl，上下右左； 2004 Dept. of Computer Science and Engineer *17 / 59裁剪 直线段裁剪 Cohen-SutherLand算法-端点编码：定义为它所在区域的编码；-结论：当线段的两个端点编码的逻辑“与”非零时 ，线段为显 然不可见：端点同时在上方、下方、左方或右方。 2004 Dept. of Co
12、mputer Science and Engineer *18 / 59裁剪 直线段裁剪 Cohen-SutherLand算法-对那些非显然可见、非显然不可见的线段，需要求交 （如，线段CD)，求交前先测试与窗口哪条边所在直线 有交？(按序判断端点编码中各位的值ClCtCrCb）；- 1）特点：用编码方法可快速判断线段 完全可见 和显然不可见。- 2）特别适用二种场合： 大窗口场合； 窗口特别小的场合(如,光标拾取图形时,光标看作 小的裁剪窗口。） 2004 Dept. of Computer Science and Engineer *19 / 59裁剪 直线段裁剪 Nicholl-Lee-
13、Nicholl算法 Nicholl-Lee-Nicholl算法-目的：通过对二维平面的更详细划分，消除Cohen_Sutherland 算法中线段在被裁剪时需多次求交的情况。 2004 Dept. of Computer Science and Engineer *20 / 59裁剪 直线段裁剪 Nicholl-Lee-Nicholl算法 Nicholl-Lee-Nicholl算法-算法假设：假定待裁剪线段P0、P1为非完全可见且非显然不可见。-步骤： 第一步，窗口四边所在的直线将二维平面划分成9个区域，假定P0 落在区域0、4、5 2004 Dept. of Computer Science
14、 and Engineer *21 / 59裁剪 直线段裁剪 Nicholl-Lee-Nicholl算法第二步：从P0点向窗口的四个角点发出射线，这四条射线和窗 口的四条边所在的直线一起将二维平面划分为更多的小区域； 2004 Dept. of Computer Science and Engineer *22 / 59裁剪 直线段裁剪 Nicholl-Lee-Nicholl算法此时P1的位置决定了P0、 P1和窗口边的相交关系； 2004 Dept. of Computer Science and Engineer *23 / 59裁剪 直线段裁剪 Nicholl-Lee-Nicholl算法
15、第三步，确定P1所在的区域（判断P1所在区域位置，可判 定P0、P1与窗口那条边求交)。 根据窗口四边的坐标值及P0P1和各射线的斜率可确定P1所在 的区域。第四步，求交点，确定P0P1的可见部分 。结论：效率较高，但仅适合二维矩形窗口； 2004 Dept. of Computer Science and Engineer *24 / 59裁剪 直线段裁剪 中点分割法中点分割法-思想： 从P0点出发找出距P0最近 的可见点 从P1点出发找出距P1最近 的可见点。-取中点Pm=(P1+P2)/2； （算法过程见框图）求线段中点可以由加法和位移实现，易于用硬件实现 2004 Dept. of Computer Science and Engineer *25 / 59裁剪 直线段裁剪 参数化方法参数化方法-思想：利用数学上线段的参数方程；-如：考虑凸多边形R和线段P1，计算线段落在区域R中的部分。如图： 2004 Dept. of Computer Science and Engineer *26 / 59裁剪 直线段裁剪 参数化方法-设： A：区域R边界上的一点； N：区域边界在A点的内法向量； P1P2线段：-凸多边形性质： P(t)在多边形内的充要条件：对于凸多边形边界上任意一点A和该 处内法向量N，都有N(P(t)-A)0；对线段上任意一点:P(t),有三种可
