《计算机图形学基础 基本图形生成算法5-2》由会员分享，可在线阅读，更多相关《计算机图形学基础 基本图形生成算法5-2（58页珍藏版）》请在金锄头文库上搜索。
1、计算机图形学 计算机学院 万琳 87556154 wanlin-计算机图形学基础计算机图形学 计算机学院 万琳 87556154 wanlin-基本图形生成算法提出问题：如何在指定的输出设备上根据坐标描述构造基本二维几何图形（点、直线、圆、椭圆、多边形域、字符串及其相关属性等）计算机图形学 计算机学院 万琳 87556154 wanlin-4 多边形的扫描转换与区域填充多边形的扫描转换： 主要是通过确定穿越区域的扫描线的覆盖区间来填充区域填充： 从给定的位置开始涂描直到指定的边界条件为止计算机图形学 计算机学院 万琳 87556154 wanlin-4.1 多边形的扫描转换顶点表示：顶点表示：
2、用多边形的顶点序列来刻划多边形1. 什么是多边形的扫描转换点阵表示：点阵表示：用位于多边形内的象素的集合来刻划多边形多边形的扫多边形的扫描转换或多描转换或多边形的填充边形的填充计算机图形学 计算机学院 万琳 87556154 wanlin-2. x-扫描线算法基本思想算法步骤：(1)确定多边形所占有的最大扫描线数，得到多边形顶点的最小和最大y值（ymin和ymax）。(2)从y=ymin到y=ymax，每次用一条扫描线进行填充。(3)对一条扫描线填充的过程可分为四个步骤：a.求交b.排序c.交点配对d.区间填色计算机图形学 计算机学院 万琳 87556154 wanlin-存在问题：存在问题：
3、当扫描线与多边形顶点相交时，交点的取舍问题。解决方法： 当扫描线与多边形的顶点相交时，v若共享顶点的两条边分别落在扫描线的两边，交点只算一个；v若共享顶点的两条边在扫描线的同一边，这时交点作为零个或两个。 计算机图形学 计算机学院 万琳 87556154 wanlin-实例：解决方法： 当扫描线与多边形的顶点相交时：v若共享顶点的两条边分别落在扫描线的两边，交点只算一个；v若共享顶点的两条边在扫描线的同一边，这时交点作为零个或两个。 计算机图形学 计算机学院 万琳 87556154 wanlin-3. 改进的有效边表算法（Y连贯性算法）改进原理：v处理一条扫描线时，仅对有效边求交v利用扫描线的
4、连贯性v利用多边形边的连贯性计算机图形学 计算机学院 万琳 87556154 wanlin-有效边（Active Edge）： 指与当前扫描线相交的多边形的边，也称为活性边。有效边表（Active Edge Table, AET）： 把有效边按与扫描线交点x坐标递增的顺序存放在一个链表中，此链表称为有效边表。有效边表的每个结点： x ymax 1/k next计算机图形学 计算机学院 万琳 87556154 wanlin-边表（边表（Edge TableEdge Table）的构造：(2)将每条边的信息链入与该边最小y坐标（ymin ）相对应的桶处。也就是说，若某边的较低端点为ymin，则该边
5、就放在相应的扫描线桶中。(1)首先构造一个纵向链表，链表的长度为多边形所占有的最大扫描线数，链表的每个结点，称为一个桶，则对应多边形覆盖的每一条扫描线。(3)每条边的数据形成一个结点，内容包括：该扫描线与该边的初始交点x（即较低端点的x值），1/k，以及该边的最大y值ymax。x|ymin ymax 1/k NEXT(4)同一桶中若干条边按X|ymin由小到大排序，若X|ymax 相等，则按照1/m由小到大排序。计算机图形学 计算机学院 万琳 87556154 wanlin-解决顶点交点计为1时的情形：计算机图形学 计算机学院 万琳 87556154 wanlin-计算机图形学 计算机学院 万
6、琳 87556154 wanlin-边表边表的构造：(1) 构造一个纵向链表，链表长度为多边形所占有的最大扫描线数；(2)将每条边的信息链入与该边最小y坐标（ymin ）相对应的桶处； (3)每条边的数据形成一个结点，包括：该扫描线与该边的初始交点x（即较低端点的x值），1/k，以及该边的最大y值ymax。计算机图形学 计算机学院 万琳 87556154 wanlin-算法步骤算法步骤：(1)初始化：构造边表，AET表置空；(2)将第一个不空的ET表中的边与AET表合并；(3)由AET表中取出交点对进行填充。填充之后删除y=ymax的边；(4)yi+1=yi+1,根据xi+1=xi+1/m计算
7、并修改AET表，同时合并ET表中y=yi+1桶中的边，按次序插入到AET表中，形成新的AET表；(5)AET表不为空则转(3)，否则结束。计算机图形学 计算机学院 万琳 87556154 wanlin-4.2 边缘填充算法算法简单，但对于复杂图形，每一象素可能被访问多次计算机图形学 计算机学院 万琳 87556154 wanlin-栅栏填充算法栅栏指的是一条过多边形顶点且与扫描线垂直的直线。它把多边形分为两半。计算机图形学 计算机学院 万琳 87556154 wanlin-边标志算法分为两个步骤：(1)打标记(2)填充 Inside 初值：假 遇到标记点：取反 真：填充； 假：不填充 当用软件
8、实现本算法时，速度与改进的有效边表算法相当，但本算法用硬件实现后速度会有很大提高。计算机图形学 计算机学院 万琳 87556154 wanlin-4.3 区域填充区域是指已经表示成点阵形式的填充图形，它是像素集合。定义：4-邻接点和8-邻接点计算机图形学 计算机学院 万琳 87556154 wanlin-4-连通区域和8-连通区域 把位于给定区域的边界上的象素一一列举出来的方法称为边界表示法。 边界填充算法（Boundary-fill Algorithm） 枚举出给定区域内所有象素的表示方法称为内点表示。 泛填充算法（Flood-fill Algorithm）计算机图形学 计算机学院 万琳 8
9、7556154 wanlin-1. 边界填充算法算法的输入：种子点坐标(x,y)，填充色和边界颜色。栈结构实现4 4-连通边界填充算法的算法步骤：种子象素入栈；栈非空时重复执行三步操作：(1)栈顶象素出栈；(2)将出栈象素置成填充色；(3)检查出栈象素的4-邻接点，若其中某个象素点不是边界色且未置成多边形色，则把该象素入栈。计算机图形学 计算机学院 万琳 87556154 wanlin-栈结构实现8- -连通边界填充算法连通边界填充算法的算法步骤算法步骤：种子象素入栈；栈非空时重复执行三步操作：(1)栈顶象素出栈；(2)将出栈象素置成填充色；(3)检查出栈象素的8-邻接点，若其中某个象素点不是
10、边界色且未置成多边形色，则把该象素入栈。计算机图形学 计算机学院 万琳 87556154 wanlin-边界填充算法特点：v可以用于填充带有内孔的平面区域v把太多的象素压入堆栈计算机图形学 计算机学院 万琳 87556154 wanlin- 改进：通过沿扫描线填充水平象素段，来代替处理4-邻接点和8-邻接点。 算法步骤： 种子象素入栈；当栈非空时作如下三步操作：(1)栈顶象素出栈；(2)填充出栈象素所在扫描行的连续象素段，直到遇到边界象素为止，即每出栈一个象素，就对包含该象素的整个扫描线区间进行填充；(3)在区间中检查与当前扫描线相邻的上下两条扫描线的有关象素是否全为边界象素或已填充的象素，若
11、存在非边界、未填充边界的象素，则把每一区间的最右象素取作种子象素入栈。计算机图形学 计算机学院 万琳 87556154 wanlin-2. 泛填充算法算法的输入：种子点坐标(x,y)，填充色和内部点的颜色。算法原理算法原理： 算法从指定的种子(x,y)开始，用所希望的填充颜色赋给所有当前为给定内部颜色的象素点。计算机图形学 计算机学院 万琳 87556154 wanlin-8-连通泛填充算法步骤如下：种子象素入栈；当栈非空时重复执行如下三步操作：(1)栈顶象素出栈；(2)将出栈象素置成填充色；(3)检查出栈象素的8-邻接点，若其中某个象素点是给定内部点的颜色且未置成新的填充色，则把该象素入栈。
12、计算机图形学 计算机学院 万琳 87556154 wanlin-注意注意： 当以边界表示时，4-连通边界填充算法只能填充4-连通区域，8-连通边界填充算法也只能填充8-连通区域。 当以内点表示时，8-连通泛填充算法可以填充8-连通区域也可以填充4-连通区域，当然4-连通泛填充算法还是只能填充4-连通区域。计算机图形学 计算机学院 万琳 87556154 wanlin-4.4 其他相关的概念1. 内-外测试不自交的多边形 、自相交的多边形奇-偶规则（Odd-even Rule）从任意位置p作一条射线，若与该射线相交的多边形边的数目为奇数，则p是多边形内部点，否则是外部点。计算机图形学 计算机学院
13、 万琳 87556154 wanlin-非零环绕数规则（Nonzero Winding Number Rule）v首先使多边形的边变为矢量。v将环绕数初始化为零。v再从任意位置p作一条射线。当从p点沿射线方向移动时，对在每个方向上穿过射线的边计数，每当多边形的边从右到左穿过射线时，环绕数加1，从左到右时，环绕数减1。v处理完多边形的所有相关边之后，若环绕数为非零，则p为内部点，否则，p是外部点。外部or内部计算机图形学 计算机学院 万琳 87556154 wanlin-2. 曲线边界区域的填充相交计算计算机图形学 计算机学院 万琳 87556154 wanlin-5 字符处理ASCII码：“美
14、国信息交换用标准代码集”(American Standard Code for Information Interchange)，简称ASCII码。127个字符：7位+最高位（不用或用作奇偶校验位） 国标码：“中华人民共和国国家标准信息交换编码，简称为国际码，代号GB231280。常用汉字6763个，图形符号682个（94区*94位） 7+7，最高位区分字库：字库中储存了每个字符的图形信息。矢量字库 点阵字库计算机图形学 计算机学院 万琳 87556154 wanlin-5.1 点阵字符在点阵表示中，每个字符由一个点阵位图来表示显示时：形成字符的象素图案计算机图形学 计算机学院 万琳 8755
15、6154 wanlin-5.2 矢量字符矢量字符采用直线和曲线段来描述字符形状，矢量字符库中记录的是笔划信息笔划信息。显示时显示时：解释字符的每个笔划信息计算机图形学 计算机学院 万琳 87556154 wanlin-6 属性处理当前属性值表6.1 线型和线宽1. 线型处理实心段和中间空白段的长度（象素数目）可用象素模板(pixel mask)指定存在问题：如何保持任何方向的划线长度近似地相等计算机图形学 计算机学院 万琳 87556154 wanlin-解决：可根据线的斜率来调整实心段和中间空白段的象素数目。计算机图形学 计算机学院 万琳 87556154 wanlin-2. 线刷子和方刷子
16、处理线宽线刷子：垂直刷子、水平刷子计算机图形学 计算机学院 万琳 87556154 wanlin-特点n实现简单、效率高。n斜线与水平(或垂直)线不一样粗。n当线宽为偶数个象素时，线的中心将偏移半个象素。n利用线刷子生成线的始末端总是水平或垂直的，看起来不太自然。解决：添加“线帽（line cap）”计算机图形学 计算机学院 万琳 87556154 wanlin-n当比较接近水平的线与比较接近垂直的线汇合时，汇合处外角将有缺口 解决：斜角连接（miter join）、圆连接（round join）、斜切连接（bevel join）计算机图形学 计算机学院 万琳 87556154 wanlin-
17、方刷子特点：n方刷子绘制的线条（斜线）比用线刷子所绘制的线条要粗一些n方刷子绘制的斜线与水平（或垂直）线不一样粗n方刷子绘制的线条自然地带有一个“方线帽”计算机图形学 计算机学院 万琳 87556154 wanlin-3. 其它线宽处理方式n区域填充n改变刷子形状：计算机图形学 计算机学院 万琳 87556154 wanlin-4. 曲线的线型和线宽线型线型：可采用象素模板象素模板的方法计算机图形学 计算机学院 万琳 87556154 wanlin-线宽：n线刷子n方刷子要显示一致的曲线宽度可通过旋转刷子方向以使其在沿曲线移动时与斜率方向一致，n圆弧刷子n采用填充的办法。计算机图形学 计算机学
18、院 万琳 87556154 wanlin-6.2 字符的属性字体、字形、字号、字间距、行间距等等。一般字体确定风格，字形确定外观，字号确定尺寸。字符的常用属性计算机图形学 计算机学院 万琳 87556154 wanlin-字符串的属性字符串的属性文本高度、文本宽度（扩展/压缩因子）、字符方向、文本路径方向、对齐方式（左对齐，中心对齐，或右对齐，指定起始、终止点）、文本字体、字符的颜色属性等。反绘（从右到左）、倒绘（旋转180）、写方式（替换或与方式）等。计算机图形学 计算机学院 万琳 87556154 wanlin-6.3 区域填充属性区域填充属性选择包括颜色、图案和透明度。计算机图形学 计算
19、机学院 万琳 87556154 wanlin-根据图案和透明度属性来填充平面区域的基本思想是：n首先用模板定义各种图案。n然后，修改填充的扫描转换算法：在确定了区域内一象素之后，不是马上往该象素填色而是先查询模板位图的对应位置。若是以透明方式填充图案，则当模板位图的对应位置为1时，用前景色写象素，否则，不改变该象素的值。若是以不透明方式填充图案，则视模板位图对应位置为1或0来决定是用前景色还是背景色去写象素。计算机图形学 计算机学院 万琳 87556154 wanlin-确定区域与模板之间的位置关系（对齐方式）：一种对齐方式是把有模板原点与填充区域边界或内部的某点对齐一种对齐方式是把模板原点与
20、填充区域外部的某点对齐计算机图形学 计算机学院 万琳 87556154 wanlin-7 反走样走样（Liasing）用离散量表示连续量引起的失真，就叫做走样。反走样（antialiasing）用于减少或消除这种效果的技术，称为反走样。计算机图形学 计算机学院 万琳 87556154 wanlin-走样现象：n光栅图形产生的阶梯形n 图形中包含相对微小的物体时，这些物体在静态图形中容易被丢弃或忽略，在动画序列中时隐时现，产生闪烁计算机图形学 计算机学院 万琳 87556154 wanlin-一种简单方法： 过取样（supersampling），或后滤波 区域取样（area sampling），
21、或前滤波受到启发：高分辨率下取样计算 低分辨率下的像素属性对几个象素属性进行平均计算机图形学 计算机学院 万琳 87556154 wanlin-7.1 过取样简单过取样计算机图形学 计算机学院 万琳 87556154 wanlin-重叠过取样计算机图形学 计算机学院 万琳 87556154 wanlin-基于加权模板的过取样计算机图形学 计算机学院 万琳 87556154 wanlin-7.2 简单的区域取样计算机图形学 计算机学院 万琳 87556154 wanlin-如何计算直线段与象素相交区域的面积？可以利用一种求相交区域的近似面积的离散计算方法： (1)将屏幕象素分割成n个更小的子象素
22、， (2)计算中心落在直线段内的子象素的个数m， (3)m/n为线段与象素相交区域面积的近似值。计算机图形学 计算机学院 万琳 87556154 wanlin-简单的区域取样特点：v直线段对一个象素亮度的贡献与两者重叠区域的面积成正比v相同面积的重叠区域对象素的贡献相同计算机图形学 计算机学院 万琳 87556154 wanlin-7.3 加权区域取样原理：假想一个连续的加权曲面（或过滤函数）覆盖象素。当直线条经过该象素时，该象素的灰度值是在二者重叠区域上对滤波器（过滤函数）进行积分的积分值。计算机图形学 计算机学院 万琳 87556154 wanlin-计算机图形学 计算机学院 万琳 87556154 wanlin-加权区域取样特点特点：v接近理想直线的象素将被分配更多的灰度值；v相邻两个象素的滤波器相交，有利于缩小直线条上相邻象素的灰度差。
