第四章 基本图形生成算法 （三） 2019/4/6 IBM Confidential

主要内容： 直线的扫描转换 圆与椭圆的扫描算法 区域填充 线宽与线型的处理 字符 裁剪 反走样 2019/4/6

字符 字符的生成： 标准字符集 共127个。 0－31 不可见，控制字符。 32－127可见（大小写字母，数字，运算符号，标点符号等）。 包括数字、字母、汉字与符号（电路、公差、液压……)等； 标准字符集 美国信息交换用标准代码集（ASCII）： 共127个。 0－31 不可见，控制字符。 32－127可见（大小写字母，数字，运算符号，标点符号等）。 编码用一个字节可以表示 信息交换用汉字编码字符集基本集（GB2312-80）: 汉字量大，必须用两个字节表示。 6000多个常用汉字，英文字母、数字和其他图形符号； 为在终端或绘图仪上输出字符，系统中必须装备有字符库。字符库中存放了每个字符的形状信息。 2019/4/6

A 字符 字符库分有矢量型和点阵型两种； 笔式绘图仪：矢量型字符，采用矢量代码序列表示字符的各个笔画； 终端显示器：点阵型字符库，为每个字符定义一个字符掩膜，即表示该字符的象素图案的一个点阵； 1） 点阵字符 每个字符定义成称为字符掩膜的矩阵； 西文字符：5×7的点阵字符； 汉文字符：16×16的点阵字符； 打印：24×24，40×40，72×72的点阵字符 特殊字符：按需确定。 A 二进制数表示的矩阵 编码（ASCII） 存储西文需35位，4个多字节 存储汉文需256位，32个字节 问题：信息量大，质量，变换，动画，... 解决：压缩，矢量。 2019/4/6

字符 2）矢量字符 对每个字符定义矢量代码序列描述字符的几何形状： 以AutoCAD采用的定义方法为例： 不同的应用使用不同的方法。 以AutoCAD采用的定义方法为例： AutoCAD采用一种称为形（SHAPE）的实体来定义字符 基本笔画：直线和圆弧 形描述格式如下： * <形编号>，<字节数>，<形名称> <字节1>，<字节2>，...... 0 2019/4/6

字符 1 2 3 4 5 6 7 8 9 A E F B C D 形编号：1－255整数； 字节数：形定义描述行中包括结束符0在内的字节数目； 形名称：用大写字母；否则认为是形的解释性信息，不存储； <字节N>：定义字符组成矢量的方向和大小，分为标识位、低四位和高四位三组数字。标识位表示十六进制（0）或十进制（无标识位）;高四位表示矢量的长度，低四位表示矢量方向。 如：040即表示一16进制数，其中，4表示矢量的长度，0表示矢量方向。 所有矢量都具有“相同”的长度，即（2）的单位长度是（0）的单位长度的2倍 2019/4/6

字符 实例：二极管符号： * 133, 11, DIDOE 040, 044, 04c, 042, 04c, 040, 048, 04c, 046, 04c, 0 把每一个字符都按上述方法描述后，存入一形文件中，即建立了相应的矢量字符库。 2019/4/6

字符 字型技术：节约空间，采用压缩技术（字型数据压缩存储，使用时，还原成字符点阵）： 黑白段压缩法： 部件压缩法： 优点：简单快速不失真； 缺点：压缩较差，不方便，一般用于低级文字处理系统； 部件压缩法： 优点：压缩比大 缺点：字型质量不保证； 轮廓字型法：压缩比大，质量保证（采用直线、BEZIER曲线的集合描述字符的轮廓线; 轮廓线和控制信息（属性、控制点/线）构成压缩数据，结合填充算法以取得较好的效果； 2019/4/6

一种轮廓字型法：True Type字型技术 字符 一种轮廓字型法：True Type字型技术 Apple和Microsoft公司联合开发； 利用二次Bezier曲线描述字符轮廓，对字符轮廓线的控制点进行编号； 顺序：按顺时针方向走一圈，填充部分始终在其右边。 以大写字母H为例： 2019/4/6

字符 True Type字型控制信息 X方向控制信息： Y方向控制信息： －》产生控制信息表； 1）字身最左起始点到字母主干的距离间隙； 2）字母主题部分的宽度； 3）字身的宽度； 4）字母H主干的宽度； 5）字母H的衬线； Y方向控制信息： 6）字母H横干的厚度； 7）字母H衬线的厚度； 8）字母主题部分的厚度； 9）字母H横干的高度； －》产生控制信息表； 2019/4/6

字符 字符的输出： 绘图仪输出：方向、位移值转换为设备驱动指令； 显示器/打印机输出：指定字符掩膜的原点与祯缓存中的字符左下脚位置对应，从而将字符掩膜中的值平移的写入祯缓存中； 2019/4/6

主要内容： 直线的扫描转换 圆与椭圆的扫描算法 区域填充 线宽与线型的处理 字符 裁剪 反走样 2019/4/6

裁剪 －直线段裁剪 裁剪目的 判断图形元素是否落在裁剪窗口之内并找出其位于内部的部分； 裁剪处理的基础 图元关于窗口内外关系的判别； 图元与窗口的求交； 假定条件 裁剪窗口：[xmin,xmax]，[ymin,ymax] 待裁剪线段： 待裁剪线段和窗口的关系 1）线段完全可见 2）显然不可见 3）线段至少有一端点在窗口之外，部分线段可见 为提高效率，算法设计时应考虑： (一）快速判断情形(1)(2)； (二) 设法减少情形(3)求交次数和每次求交时所需的计算量。 2019/4/6

裁剪 －直线段裁剪 点裁剪 点(x, y)在窗口内的充分必要条件是： 线段裁剪方法： Cohen-SutherLand裁减算法 中点分割算法； 参数化方法； 直接求交算法步骤 2019/4/6

裁剪 －直线段裁剪－ Cohen-SutherLand算法 算法步骤： 第一步 判别线段两端点是否都落在窗口内，如果是，则线段完全可见；否则进入第二步； 第二步 判别线段是否为显然不可见，如果是->裁剪结束；否则继续； 第三步 求线段与窗口边延长线的交点，这个交点将线段分为两段，其中一段显然不可见，丢弃。 第四步 对余下的另一段重新进行判断，直至结束 ； 裁剪过程是递归过程！ 2019/4/6

裁剪 －直线段裁剪 － Cohen-SutherLand算法 目的：对显然不可见线段实现快速判别； 编码方法：由窗口四条边所在直线把二维平面分成9个区域，每个区域赋予一个四位编码，Ct Cb Cr Cl，上下右左； 2019/4/6

裁剪 －直线段裁剪 － Cohen-SutherLand算法 端点编码：定义为它所在区域的编码； 结论：当线段的两个端点编码的逻辑“与”非零时 ，线段为显然不可见：端点同时在上方、下方、左方或右方。 2019/4/6

裁剪 －直线段裁剪 － Cohen-SutherLand算法 对那些非显然可见、非显然不可见的线段，需要求交（如，线段CD)，求交前先测试与窗口哪条边所在直线有交？(按序判断端点编码中各位的值ClCtCrCb）； 1）特点：用编码方法可快速判断线段 － 完全可见和显然不可见。 2）特别适用二种场合： 大窗口场合； 窗口特别小的场合(如,光标拾取图形时,光标看作小的裁剪窗口。） 2019/4/6

裁剪 －直线段裁剪 － Nicholl-Lee-Nicholl算法 目的：通过对二维平面的更详细划分，消除Cohen_Sutherland算法中线段在被裁剪时需多次求交的情况。 2019/4/6

裁剪 －直线段裁剪 － Nicholl-Lee-Nicholl算法 算法假设：假定待裁剪线段P0、P1为非完全可见且非显然不可见。 步骤： 第一步，窗口四边所在的直线将二维平面划分成9个区域，假定P0 落在区域0、4、5 2019/4/6

裁剪 －直线段裁剪 － Nicholl-Lee-Nicholl算法 第二步：从P0点向窗口的四个角点发出射线，这四条射线和窗口的四条边所在的直线一起将二维平面划分为更多的小区域； 2019/4/6

裁剪 －直线段裁剪 － Nicholl-Lee-Nicholl算法 此时P1的位置决定了P0、P1和窗口边的相交关系； 2019/4/6

裁剪 －直线段裁剪 － Nicholl-Lee-Nicholl算法 第三步，确定P1所在的区域（判断P1所在区域位置，可判定P0、P1与窗口那条边求交)。 根据窗口四边的坐标值及P0P1和各射线的斜率可确定P1所在的区域。 第四步，求交点，确定P0P1的可见部分 。 结论：效率较高，但仅适合二维矩形窗口； 2019/4/6

求线段中点可以由加法和位移实现，易于用硬件实现 裁剪 －直线段裁剪 －中点分割法 中点分割法 思想： 从P0点出发找出距P0最近的可见点 从P1点出发找出距P1最近的可见点。 取中点Pm=(P1+P2)/2； （算法过程见框图） 求线段中点可以由加法和位移实现，易于用硬件实现 2019/4/6

裁剪 －直线段裁剪 －参数化方法 参数化方法 思想：利用数学上线段的参数方程； 如：考虑凸多边形R和线段P1，计算线段落在区域R中的部分。如图： 2019/4/6

对线段上任意一点:P(t),有三种可能性： 裁剪 －直线段裁剪 －参数化方法 设： A：区域R边界上的一点； N：区域边界在A点的内法向量； P1P2线段： 凸多边形性质： P(t)在多边形内的充要条件：对于凸多边形边界上任意一点A和该处内法向量N，都有N(P(t)-A)>0； 对线段上任意一点:P(t),有三种可能性： 1）N(P(t)-A)<0：P(t)在多边形外侧； 2）N(P(t)-A)＝0：P(t)在多边形边界或其延长线上； 3）N(P(t)-A)>0：P(t)在多边形内侧； 2019/4/6

裁剪 －直线段裁剪 －参数化方法 设多边形有N条边，在每个边上取一个点Ai和该点处的内法向量Ni（i＝1，2，…,k)，则可见线段的参数区间为求解下列不等式的解： 实际上，只需关心解的最小值和最大值； 如果Ni(P2-P1)＝0等于0，则法向量与线段垂直，即线段P1P2与对应边平行，无交点，分两种情况考虑： 1）线段在区域外侧:直接判断直线在多边形外； 2）线段在区域内侧：忽略，继续处理其它边； 2019/4/6

当凸多边形是矩形窗口，且矩形的边平行于坐标轴时，上述算法简化为Liang-Barsky算法； 裁剪 －直线段裁剪 －参数化方法 解的几何意义： 参数化方法求得的交点参数Ti，按照P1P2与内法向量的内积符号分为两组： 下线组：以判别式大于0为特征，表示在该点沿P1P2方向前进将接近或进入多边形内侧； 上限组：以判别式小于0为特征，表示在该点沿P1P2方向前进将越来越远地离开多边形区域。 当凸多边形是矩形窗口，且矩形的边平行于坐标轴时，上述算法简化为Liang-Barsky算法； 2019/4/6

Cohen-Sutherland与中点法在区码测试阶段能以位运算方式高效率进行－》大多数线段能够简单地取舍时，效率较好； 裁剪 －直线段裁剪 －四种算法比较 Cohen-Sutherland与中点法在区码测试阶段能以位运算方式高效率进行－》大多数线段能够简单地取舍时，效率较好； Cyrus-Beck(参数化方法)：在多数线段需要进行裁剪时效率高：因为运算只涉及到参数，仅仅必要时才进行坐标计算； Liang Barsky算法只能应用在矩形窗口情形，效率比参数化方法更高。 2019/4/6

裁剪 －多边形裁剪 错觉：直线段裁剪的组合？ 2019/4/6

裁剪 －多边形裁剪 问题：2）一个凹多边形可能被裁剪成几个小的多边形，如何确定这些小多边形的边界？ 2019/4/6

裁剪 －多边形裁剪 Sutherland-Hodgman算法（逐边裁剪算法）： 分割处理策略：将多边形关于矩形窗口的裁剪分解为多边形关于窗口四边所在直线的裁剪； 流水线过程(左上右下)：左边的结果是上边的开始； 2019/4/6

Sutherland-Hodgman算法： 裁剪 －多边形裁剪 Sutherland-Hodgman算法： 裁剪结果的顶点构成：裁剪边内侧的原顶点；多边形的边与裁剪边的交点； 顺序连接； 结论： 裁剪算法采用流水线方式，适合硬件实现； 可推广到任意凸多边形裁剪窗口； 2019/4/6

Weiler-Athenton算法（内裁剪方法）： 裁剪 －多边形裁剪 Weiler-Athenton算法（内裁剪方法）： 裁剪窗口为任意多边形（凸、凹、带内环）的情况： 主多边形：被裁剪多边形，记为A 裁剪多边形：裁剪窗口，记为B 2019/4/6

裁剪 －多边形裁剪 Weiler-Athenton算法： 多边形顶点的排列顺序（使多边形区域位于有向边的左侧 ） 外环：逆时针 内环：顺时针 四个区域 ： 主多边形和裁剪多边形把二维平面分成两部分； 内裁剪：A∩B； 外裁剪：A-B； 裁剪结果区域的边界由A的部分边界和B的部分边界两部分构成，并且在交点处边界发生交替： 即由A的边界转至B的边界，或由B的边界转至A的边界； 2019/4/6

Weiler-Athenton算法： 裁剪 －多边形裁剪 如果主多边形与裁剪多边形有交点，则交点成对出现，它们被分为如下两类： 进点：主多边形边界由此进入裁剪多边形内（图中奇下标I点）如，I1,I3, I5, I7, I9, I11； 出点：主多边形边界由此离开裁剪多边形区域，如， I0,I2, I4, I6, I8, I10 ； 2019/4/6

Weiler-Athenton算法： 算法（内裁剪）步骤： 1、建立主多边形和裁剪多边的顶点表． 2、求主多边形和裁剪多边形的交点，并将这些交点按顺序插入两多边形的顶点表中。在两多边表形顶点表中的相同交点间建立双向指针 。 3、裁剪：如果存在没有被跟踪过的交点，执行以下步骤： (1)建立裁剪结果多边形的顶点表． (2)选取任一没有被跟踪过的交点为始点，将其输出到结果多边形顶点表中． (3)如果该交点为进点，跟踪主多边形边边界；否则跟踪裁剪多边形边界． (4) 跟踪多边形边界，每遇到多边形顶点，将其输出到结果多边形顶点表中，直至遇到新的交点． (5)将该交点输出到结果多边形顶点表中，并通过连接该交点的双向指针改变跟踪方向（如果上一步跟踪的是主多边形边界，现在改为跟踪裁剪多边形边界；如果上一步跟踪裁剪多边形边界，现在改为跟踪主多边形边界）． (6)重复(4)、(5)直至回到起点 2019/4/6

裁剪 －多边形裁剪 － Weiler-Athenton算法： 交点的奇异情况处理 1、与裁剪多边形边重合的主多边形的边不参与求交点； 2、对于顶点落在裁剪多边形的边上的主多边的边，如果落在该裁剪边的内侧，将该顶点算作交点；而如果这条边落在该裁剪边的外侧，将该顶点不看作交点 ； 2019/4/6

裁剪 －字符裁剪 1)基于字符串 2)基于字符 2019/4/6

裁剪 －字符裁剪 基于构成字符的最小元素： 点阵字符：点裁剪，字符掩膜写入象素前，判断是否在窗口内； 矢量字符：线裁剪，对跨越窗口边界的笔划进行裁剪； 2019/4/6

主要内容： 直线的扫描转换 圆与椭圆的扫描算法 区域填充 线宽与线型的处理 字符 裁剪 反走样 2019/4/6

反走样（混淆，aliasing）- 混淆现象 像素的表示: 中心在(x,y)，边长为1的正方形 2019/4/6

反走样（混淆，aliasing）- 混淆现象 混淆现象（1/3） 混淆:用离散量（象素）表示连续量（图形）引起的失真; 不光滑(阶梯状）的图形边界; （直线 多边形） 2019/4/6

反走样（混淆，aliasing）- 混淆现象 图形细节失真（比象素更窄的细节丢失） 静态：容易被丢弃或忽略； 2019/4/6

反走样（混淆，aliasing）- 混淆现象 狭小图形的遗失（引起动态图形的闪烁） 不能反映狭小图形的运动过程 狭小图形没覆盖任何象素，没被显示 （多边形尖角不连续） 2019/4/6

反走样（混淆，aliasing）- 反混淆方法 什么是反混淆： 减少或消除混淆现象的方法； 提高分辨率的反混淆方法： 缺陷：硬件代价太大，只能减轻，而不能消除走样问题； 2019/4/6

反走样（混淆，aliasing）- 反混淆方法 非加权区域采样方法 数学上基于两点假设（直线扫描算法） 1、象素是数学上抽象的点，它的面积为0，它的亮度由覆盖该点的图形的亮度所决定； 2、直线段是数学上抽象直线段，它的宽度为0； 现实 像素的面积不为0； 直线段的宽度至少为1个像素； 假设与现实的矛盾是导致混淆出现的原因之一； 2019/4/6

反走样（混淆，aliasing）- 反混淆方法 解决方法：改变直线段模型； 实现步骤： 1、将直线段看作具有一定宽度的狭长矩形； 2、当直线段与某象素有交时，求出两者相交区域的面积； 3、根据相交区域的面积，确定该象素的亮度（灰度）值； 2019/4/6

反走样（混淆，aliasing）- 反混淆方法 计算相交区域的面积（上述算法的关键） 2019/4/6

反走样（混淆，aliasing）- 反混淆方法 求相交区域的近似面积的离散计算方法 1、将屏幕象素分割成m个更小的子象素； 2、计算中心点落在直线段内的子象素的个数，记为k； 3、k/m为线段与象素相交区域面积的近似值； 2019/4/6

反走样（混淆，aliasing）- 反混淆方法 加权区域采样方法－》盒式滤波器：进行前置滤波后再取样 非加权区域采样方法的性质 1、直线段对一个象素亮度（灰度）的贡献与两者相交区域的面积成正比； 2、直线段和象素不相交时，它对该象素的亮度没有影响； 3、相同面积的相交区域对象素的亮度贡献相同，而与这个相交区域落在象素内什么位置无关； 4、直线条上沿理想直线方向的相邻两个象素有时会有较大的亮度（灰度）差； 改进第3、4条性质－》圆锥形滤波器 相交区域对象素亮度的贡献依赖于该区域与象素中心的距离； 2019/4/6

反走样（混淆，aliasing）- 反混淆方法 加权区域采样方法 权函数W(x,y)； 以象素A的中心为原点建立二维坐标系； w(x,y)反应了微面积元dA对整个象素亮度的贡献大小： 权性（ w(x,y)在象素上具有权性） 2019/4/6

反走样（混淆，aliasing）- 反混淆方法 加权区域采样方法 相交区域 对该象素的亮度贡献 特例：当 时， 加权区域采样方法退化为非加权区域采样方法。 2019/4/6

反走样（混淆，aliasing）- 反混淆方法 实现步骤 1．求直线段与象素的相交区域； 2．计算的值； 3．上面所得到的值介于0、1之间，用它乘象素的最大灰度值，即设该象素的显示灰度。 问题：计算量大 2019/4/6

反走样（混淆，aliasing）- 反混淆方法 离散计算方法 1．将屏幕象素均匀分割成m个子象素 ，则每个子象素的面积为 ，计算每个子象素对原象素亮度的贡献，记为  ,将 保存在一张加权表中; 2．求出所有中心落于直线段内的子象素，记为 ， 3．计算所有这些子象素对原象素亮度贡献之和 该值乘以象素的最大灰度值即为象素的显示灰度值. 加权表的取法 2019/4/6

反走样（混淆，aliasing）- 反混淆方法 加权区域取样方法： 程序源码：pp214 2019/4/6

Thank you! Best Wishes! 谢谢! 2019/4/6