第2章实面积图形的生成 赵立强
第2章 实面积图形的生成 赵立强
Q第2章实面积图形的生成 实面积图形即封闭图形(或有界表面),在其封闭的面积上(轮 廊内)具有相同的亮度或色彩,这意味着要让计算机填充光栅扫描 图形显示器(点阵图形显示器中封闭面积上的每一个显示点(像素 点)。实面积图形既能描述物体的几何轮廊,还能表现物体的表面 色彩,这与人们观察物体表面的习惯相一致,易为人们接受。更 为重要的是实面积图形还是描述三维物体、三维真实感图形的显 示基础,它对今后学习三维图形学帮助极大。 根据表示实面积图形的方法不同,实面积图形的生成可分为 两大类。第一类叫多边形的填充,即实面积图形的轮廓用其封闭 多边形的顶点坐标数据来描述定义(简称实面积图形的图形表示 法),在其封闭的多边形内部填充用户指定的颜色;第二类叫种子 填充,即用点阵方式描述定义实面积图形,这个图形的实面积由 用户指定的点阵颜色包围或组成简称实面积图形的图像表示法 在图形的实面积上填充用户指定的颜色,其中这个指定的第一个 填充点又称为种子
第2章 实面积图形的生成 实面积图形即封闭图形(或有界表面)，在其封闭的面积上(轮 廓内)具有相同的亮度或色彩，这意味着要让计算机填充光栅扫描 图形显示器(点阵图形显示器)中封闭面积上的每一个显示点(像素 点)。实面积图形既能描述物体的几何轮廊，还能表现物体的表面 色彩，这与人们观察物体表面的习惯相一致，易为人们接受。更 为重要的是实面积图形还是描述三维物体、三维真实感图形的显 示基础，它对今后学习三维图形学帮助极大。 根据表示实面积图形的方法不同，实面积图形的生成可分为 两大类。第一类叫多边形的填充，即实面积图形的轮廓用其封闭 多边形的顶点坐标数据来描述定义(简称实面积图形的图形表示 法)，在其封闭的多边形内部填充用户指定的颜色；第二类叫种子 填充，即用点阵方式描述定义实面积图形，这个图形的实面积由 用户指定的点阵颜色包围或组成(简称实面积图形的图像表示法)， 在图形的实面积上填充用户指定的颜色，其中这个指定的第一个 填充点又称为种子
2.1多边形的填充 多边形的定义与性质 1.多边形 多边形是一个由折线段组成的封闭图形,它由有序顶点的点集 Vi](i=1.n及有向边的线集[Ei]定义。n为多边形的顶点数或边数, 且Ei=viVi+1,i=1,2,,n。这里Vn+1=V1,用以保证多边形的封 闭性。应注意,当用多边形来表示有界平面或实面积图形的边界时, 规定多边形每条有向边的左侧为实面积图形的实面积区域(或内部 区域),因此它不允许多边形的边线自相交叉(见图)。 VI V3 VI V6 V8 V4 V4 V3
2．1 多边形的填充 一、多边形的定义与性质 1．多边形 多边形是一个由折线段组成的封闭图形，它由有序顶点的点集 [Vi](i=1…n)及有向边的线集[Ei]定义。n为多边形的顶点数或边数， 且Ei=ViVi+1，i=1，2，…，n。这里Vn+1=V1，用以保证多边形的封 闭性。应注意，当用多边形来表示有界平面或实面积图形的边界时， 规定多边形每条有向边的左侧为实面积图形的实面积区域(或内部 区域)，因此它不允许多边形的边线自相交叉(见图)。 V1 V3 V4 V2 V7 V6 V5 V4 V3 V2 V1 V8
|2环 因为多边形的有向边线左侧为其实面积区域,故沿实面积图形外轮廓 线多边形的顶点方向顺序环行时,要求该多边形顶点的整个环行方向逆时 针旋转;而沿其内轮廓线多边形的顶点方向顺序环行时,要求该多边形顶 点的整个环行方向顺时针旋转。这种定义了环行方向的多边形称为环。前 者为外环、后者为内环(见图)。 判断一个多边形环行方向的方法 对于一个给定多边形所对应的n个顶点,总能找到一个点Vi,它位于 该多边形的最高处(或最低、最左、最右处等以及与它相邻的两个点Vi-1与 Vi+1,若这三个点不在一条直线上(否则可合并它们为一条直线),那么当 这三点所形成的向量叉乘Ⅴi-1Ⅵ×iVi+1的数值为正,该多边形逆时针方 向旋转,否则顺时针方向旋转。 多边形的外环、内 环定义方向示意图
2. 环 因为多边形的有向边线左侧为其实面积区域，故沿实面积图形外轮廓 线多边形的顶点方向顺序环行时，要求该多边形顶点的整个环行方向逆时 针旋转；而沿其内轮廓线多边形的顶点方向顺序环行时，要求该多边形顶 点的整个环行方向顺时针旋转。这种定义了环行方向的多边形称为环。前 者为外环、后者为内环(见图)。 判断一个多边形环行方向的方法： 对于一个给定多边形所对应的n个顶点，总能找到一个点Vi，它位于 该多边形的最高处(或最低、最左、最右处等)以及与它相邻的两个点Vi-1与 Vi+1，若这三个点不在一条直线上(否则可合并它们为一条直线)，那么当 这三点所形成的向量叉乘Vi-1 Vi×Vi Vi+1的数值为正，该多边形逆时针方 向旋转，否则顺时针方向旋转。 多边形的外环、内 环定义方向示意图
3.带孔多边形 由一个外环和数个内环组成的多边形称为带孔多边形,若多边 形没有内环即为不带孔多边形 4.凹、凸多边形的判别方法 定义:Vi-1Vi×viVi+1=ak其中,a为实值,向量k与Vi Vi,ViVi+1符合右手螺旋法则。 若数值a<0,则Vi点为凹点,否则为凸点。具有凹点的多边形 为凹多边形,只具有凸点的多边形为凸多边形。外环的凹点对应的 内角一定大于180°,凸点的内角小于180°。并且任何一个多边形, 其外形上凸点的个数总是多于其凹点的个数。 V8 V7 VI V4 V3
3．带孔多边形 由一个外环和数个内环组成的多边形称为带孔多边形，若多边 形没有内环即为不带孔多边形。 4．凹、凸多边形的判别方法 定义：Vi-1Vi × ViVi+1=ak 其中，a为实值，向量k与Vi- 1Vi，ViVi+1符合右手螺旋法则。 若数值a<0，则Vi点为凹点，否则为凸点。具有凹点的多边形 为凹多边形，只具有凸点的多边形为凸多边形。外环的凹点对应的 内角一定大于180°，凸点的内角小于180°。并且任何一个多边形， 其外形上凸点的个数总是多于其凹点的个数。 V9 V3 V8 V7 V6 V5 V4 V2 V2 V1
Q|二、多边形的填充原理 多边形图形的填充原理:找出所有位于封闭图形内的像素点, 把这些点置换成所要求的像素值。 般方法:如果在显示屏中,采用从上到下、从左到右找出每一 个显示点,然后通过多边形的边界函数(凸多边形有边界函数且表 达方式简单等方法,判断其是否位于封闭图形之内后再填充。 评价:这种方法原理虽然简单,但速度太慢,特别不适合凹多边 形与带孔多边形的填充需要 因此有必要寻找一种通用的(适用于凸、凹、带孔的多边形) 快速判断像素点位于封闭图形之内的计算方法,这是多边形图形 填充的关键
二、多边形的填充原理 多边形图形的填充原理：找出所有位于封闭图形内的像素点， 把这些点置换成所要求的像素值。 一般方法：如果在显示屏中，采用从上到下、从左到右找出每一 个显示点，然后通过多边形的边界函数(凸多边形有边界函数且表 达方式简单)等方法，判断其是否位于封闭图形之内后再填充。 评价：这种方法原理虽然简单，但速度太慢，特别不适合凹多边 形与带孔多边形的填充需要。 因此有必要寻找一种通用的(适用于凸、凹、带孔的多边形) 快速判断像素点位于封闭图形之内的计算方法，这是多边形图形 填充的关键
利用射线的交点计数法判断像素点位于封 闭图形内外的方法 从封闭图形外找一点,引一水平射线(称为扫描线)与封闭图形 相交。当交点计数为奇数时,扫描线在封闭图形内(射线穿人封闭 图形);当交点计数为偶数时,扫描线在封闭图形外,该方法简称 交点计数法则。 60000 缺点:这种计算交 点的方法不能正确 处理如y=7时的情 况。必须提出补充 规则以完善交点计 数法则。 012343678910B6 图2-3封闭图形与扫描线
利用射线的交点计数法判断像素点位于封 闭图形内外的方法 从封闭图形外找一点，引一水平射线(称为扫描线)与封闭图形 相交。当交点计数为奇数时，扫描线在封闭图形内(射线穿人封闭 图形)；当交点计数为偶数时，扫描线在封闭图形外，该方法简称 交点计数法则。 缺点：这种计算交 点的方法不能正确 处理如y=7时的情 况 。必须提出补充 规则以完善交点计 数法则
Q改进方法() 1.当扫描线与封闭多边形的水平边相交时,不计算其交点个数; 2.当扫描线与封闭多边形的奇异点相交时,其交点个数计算两次 而对于扫描线与多边形的其余每条斜边相交,其交点个数仅计算 次 所谓奇异点即封闭图 形的极值点,图中共 有(7,7),(7 (2 9),(3,1)等4个奇8-0006000 异点 这样保证了任何一条扫描4 线与多边形相交,其交点3 个数总是偶数。由此能正 确地判断出每一条扫描线 中哪一部分位于封闭图形0123456789101456 之内,哪一部分位于其外。 图23封闭图形与扫描线
改进方法(1) 1.当扫描线与封闭多边形的水平边相交时，不计算其交点个数； 2.当扫描线与封闭多边形的奇异点相交时，其交点个数计算两次； 而对于扫描线与多边形的其余每条斜边相交，其交点个数仅计算 一次。 所谓奇异点即封闭图 形的极值点，图中共 有(7，7)，(7，1)，(2， 9)，(13，11)等4个奇 异点. 这样保证了任何一条扫描 线与多边形相交，其交点 个数总是偶数。由此能正 确地判断出每一条扫描线 中哪一部分位于封闭图形 之内，哪一部分位于其外
改进方法(2) 由于奇异点的交点个数要计算两次,这对于实际操作来讲还不够简练, 因此对于多边形填充又提出另一种对奇异点的简单近似的处理方法: 在计算扫描线与多边形的每一斜边的交点之前,将斜边中最低的端点 在y方向上缩短一个屏坐标刻度单位(注意,这将忽略近似水平斜边),然后 再计算水平扫描线与多边形各斜边的所有交点。经过这样处理后,对多边 形的极大值奇异点计算两次交点,而忽略了极小值奇异点的存在。 eeeeee 66ee由 X (a)该点填充两次 (b)缩短一个y单位, (c)缩短一个y单位, 该点填充一次 缺少这条扫描线 图24奇异点的简单近似处理方法 缺点:严重时,实面积图形的下部分缺少一条扫描填充线
改进方法(2) 由于奇异点的交点个数要计算两次，这对于实际操作来讲还不够简练， 因此对于多边形填充又提出另一种对奇异点的简单近似的处理方法： 在计算扫描线与多边形的每一斜边的交点之前，将斜边中最低的端点 在y方向上缩短一个屏坐标刻度单位(注意，这将忽略近似水平斜边)，然后 再计算水平扫描线与多边形各斜边的所有交点。经过这样处理后，对多边 形的极大值奇异点计算两次交点，而忽略了极小值奇异点的存在。 缺点：严重时，实面积图形的下部分缺少一条扫描填充线
总评 经过上述约定与处理之后,使得同一扫 描线与封闭多边形的交点总是成对出现,因 此在正确计算扫描线与封闭多边形的所有交 点之后,图形的填充就成了画直线的过程。 这种逐个计算要显示的各点并显示的过程又 称扫描转换。根据组织上述扫描线与封闭多 边形的交点方法不同,其多边形的填充又有 (YX),Y-X与多边形优先级等多种算法
总评 经过上述约定与处理之后，使得同一扫 描线与封闭多边形的交点总是成对出现，因 此在正确计算扫描线与封闭多边形的所有交 点之后，图形的填充就成了画直线的过程。 这种逐个计算要显示的各点并显示的过程又 称扫描转换。根据组织上述扫描线与封闭多 边形的交点方法不同，其多边形的填充又有 (YX)，Y-X与多边形优先级等多种算法