文档介绍：第2章实面积图形的生成
赵立强
第2章实面积图形的生成
实面积图形即封闭图形(或有界表面),在其封闭的面积上(轮廓内)具有相同的亮度或色彩,这意味着要让计算机填充光栅扫描图形显示器(点阵图形显示器)中封闭面积上的每一个显示点(像素点)。实面积图形既能描述物体的几何轮廊,还能表现物体的表面色彩,这与人们观察物体表面的****惯相一致,易为人们接受。更为重要的是实面积图形还是描述三维物体、三维真实感图形的显示基础,它对今后学****三维图形学帮助极大。
根据表示实面积图形的方法不同,实面积图形的生成可分为两大类。第一类叫多边形的填充,即实面积图形的轮廓用其封闭多边形的顶点坐标数据来描述定义(简称实面积图形的图形表示法),在其封闭的多边形内部填充用户指定的颜色;第二类叫种子填充,即用点阵方式描述定义实面积图形,这个图形的实面积由用户指定的点阵颜色包围或组成(简称实面积图形的图像表示法),在图形的实面积上填充用户指定的颜色,其中这个指定的第一个填充点又称为种子。
多边形的填充
一、多边形的定义与性质
多边形是一个由折线段组成的封闭图形,它由有序顶点的点集[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,若这三个点不在一条直线上(否则可合并它们为一条直线),那么当这三点所形成的向量叉乘Vi-1 Vi×Vi Vi+1的数值为正,该多边形逆时针方向旋转,否则顺时针方向旋转。
多边形的外环、内环定义方向示意图
由一个外环和数个内环组成的多边形称为带孔多边形,若多边形没有内环即为不带孔多边形。
、凸多边形的判别方法
定义: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
二、多边形的填充原理
多边形图形的填充原理:找出所有位于封闭图形内的像素点,把这些点置换成所要求的像素值。
一般方法:如果在显示屏中,采用从上到下、从左到右找出每一个显示点,然后通过多边形的边界函数(凸多边形有边界函数且表达方式简单)等方法,判断其是否位于封闭图形之内后再填充。
评价:这种方法原理虽然简单,但速度太慢,特别不适合凹多边形与带孔多边形的填充需要。
因此有必要寻找一种通用的(适用于凸、凹、带孔的多边形)快速判断像素点位于封闭图形之内的计算方法,这是多边形图形填充的关键。
利用射线的交点计数法判断像素点位于封闭图形内外的方法
从封闭图形外找一点,引一水平射线(称为扫描线)与封闭图形相交。当交点计数为奇数时,扫描线在封闭图形内(射线穿人封闭图形);当交点计数为偶数时,扫描线在封闭图形外,该方法简称交点计数法则。
缺点:这种计算交点的方法不能正确处理如y=7时的情况。必须提出补充规则以完善交点计数法则。
改进方法(1)
,不计算其交点个数;
,其交点个数计算两次;而对于扫描线与多边形的其余每条斜边相交,其交点个数仅计算一次。
所谓奇异点即封闭图形的极值点,图中共有(7,7),(7,1),(2,9),(13,11)等4个奇异点.
这样保证了任何一条扫描线与多边形相交,其交点个数总是偶数。由此能正确地判断出每一条扫描线中哪一部分位于封闭图形之内,哪一部分位于其外。
改进方法(2)
由于奇异点的交点个数要计算两次,这对于实际操作来讲还不