计算机图形学 第2章 实面积图形的生成.ppt

1、第2章 实面积图形的生成,第2章 实面积图形的生成,实面积图形即封闭图形(或有界表面)，在其封闭的面积上(轮廓内)具有相同的亮度或色彩，这意味着要让计算机填充光栅扫描图形显示器(点阵图形显示器)中封闭面积上的每一个显示点(像素点)。实面积图形既能描述物体的几何轮廊，还能表现物体的表面色彩，这与人们观察物体表面的习惯相一致，易为人们接受。更为重要的是实面积图形还是描述三维物体、三维真实感图形的显示基础，它对今后学习三维图形学帮助极大。 根据表示实面积图形的方法不同，实面积图形的生成可分为两大类。第一类叫多边形的填充，即实面积图形的轮廓用其封闭多边形的顶点坐标数据来描述定义(简称实面积图形的图形表

2、示法)，在其封闭的多边形内部填充用户指定的颜色；第二类叫种子填充，即用点阵方式描述定义实面积图形，这个图形的实面积由用户指定的点阵颜色包围或组成(简称实面积图形的图像表示法)，在图形的实面积上填充用户指定的颜色，其中这个指定的第一个填充点又称为种子。,21 多边形的填充,一、多边形的定义与性质 1多边形 多边形是一个由折线段组成的封闭图形，它由有序顶点的点集Vi(i=1n)及有向边的线集Ei定义。n为多边形的顶点数或边数，且Ei=ViVi+1，i=1，2，n。这里Vn+1=V1，用以保证多边形的封闭性。应注意，当用多边形来表示有界平面或实面积图形的边界时，规定多边形每条有向边的左侧为实面积图形

3、的实面积区域(或内部区域)，因此它不允许多边形的边线自相交叉(见图)。,V1,V3,V4,V2,V7,V6,V5,V4,V3,V2,V1,V8,2. 环,因为多边形的有向边线左侧为其实面积区域，故沿实面积图形外轮廓线多边形的顶点方向顺序环行时，要求该多边形顶点的整个环行方向逆时针旋转；而沿其内轮廓线多边形的顶点方向顺序环行时，要求该多边形顶点的整个环行方向顺时针旋转。这种定义了环行方向的多边形称为环。前者为外环、后者为内环(见图)。 判断一个多边形环行方向的方法 ： 对于一个给定多边形所对应的n个顶点，总能找到一个点Vi，它位于该多边形的最高处(或最低、最左、最右处等)以及与它相邻的两个点Vi

4、-1与Vi+1，若这三个点不在一条直线上(否则可合并它们为一条直线)，那么当这三点所形成的向量叉乘Vi-1 ViVi Vi+1的数值为正，该多边形逆时针方向旋转，否则顺时针方向旋转。,多边形的外环、内环定义方向示意图,3带孔多边形,由一个外环和数个内环组成的多边形称为带孔多边形，若多边形没有内环即为不带孔多边形。,4凹、凸多边形的判别方法,定义：Vi-1Vi ViVi+1=ak 其中，a为实值，向量k与Vi-1Vi，ViVi+1符合右手螺旋法则。 若数值a0，则Vi点为凹点，否则为凸点。具有凹点的多边形为凹多边形，只具有凸点的多边形为凸多边形。外环的凹点对应的内角一定大于180，凸点的内角小于

5、180。并且任何一个多边形，其外形上凸点的个数总是多于其凹点的个数。,V9,V3,V8,V7,V6,V5,V4,V2,V2,V1,二、多边形的填充原理,多边形图形的填充原理：找出所有位于封闭图形内的像素点，把这些点置换成所要求的像素值。 一般方法：如果在显示屏中，采用从上到下、从左到右找出每一个显示点，然后通过多边形的边界函数(凸多边形有边界函数且表达方式简单)等方法，判断其是否位于封闭图形之内后再填充。 评价：这种方法原理虽然简单，但速度太慢，特别不适合凹多边形与带孔多边形的填充需要。 因此有必要寻找一种通用的(适用于凸、凹、带孔的多边形)快速判断像素点位于封闭图形之内的计算方法，这是多边形

6、图形填充的关键。,利用射线的交点计数法判断像素点位于封闭图形内外的方法,从封闭图形外找一点，引一水平射线(称为扫描线)与封闭图形相交。当交点计数为奇数时，扫描线在封闭图形内(射线穿人封闭图形)；当交点计数为偶数时，扫描线在封闭图形外，该方法简称交点计数法则。,缺点：这种计算交点的方法不能正确处理如y=7时的情况 。必须提出补充规则以完善交点计数法则 。,改进方法(1),1.当扫描线与封闭多边形的水平边相交时，不计算其交点个数； 2.当扫描线与封闭多边形的奇异点相交时，其交点个数计算两次；而对于扫描线与多边形的其余每条斜边相交，其交点个数仅计算一次。,所谓奇异点即封闭图形的极值点，图中共有(7，

7、7)，(7，1)，(2，9)，(13，11)等4个奇异点.,这样保证了任何一条扫描线与多边形相交，其交点个数总是偶数。由此能正确地判断出每一条扫描线中哪一部分位于封闭图形之内，哪一部分位于其外。,改进方法(2),由于奇异点的交点个数要计算两次，这对于实际操作来讲还不够简练，因此对于多边形填充又提出另一种对奇异点的简单近似的处理方法： 在计算扫描线与多边形的每一斜边的交点之前，将斜边中最低的端点在y方向上缩短一个屏坐标刻度单位(注意，这将忽略近似水平斜边)，然后再计算水平扫描线与多边形各斜边的所有交点。经过这样处理后，对多边形的极大值奇异点计算两次交点，而忽略了极小值奇异点的存在。,缺点：严重时

8、，实面积图形的下部分缺少一条扫描填充线 。,总评,经过上述约定与处理之后，使得同一扫描线与封闭多边形的交点总是成对出现，因此在正确计算扫描线与封闭多边形的所有交点之后，图形的填充就成了画直线的过程。这种逐个计算要显示的各点并显示的过程又称扫描转换。根据组织上述扫描线与封闭多边形的交点方法不同，其多边形的填充又有(YX)，Y-X与多边形优先级等多种算法。,三、多边形的(YX)填充算法,(YX)填充算法根据多边形填充算法的原理，先求出多边形各斜边与扫描线的所有交点并记录；然后按从上到下、从左到右的次序对所有的交点进行排序；最后利用这些交点总是成对出现并从上到下、从左到右排列的规律画直线，画完所有的

9、直线即完成填充任务。,多边形,交叉点表,(YX)填充算法虽然简单，但当多边形的形状复杂时，其交点表的容量非常大，而且对交点进行排序很费时，这极大地影响了该算法的使用效果。,四、多边形的Y-X填充算法,为了克服（YX）算法两个缺点，可对该算法进行如下 改进： 改进存储方式。不存储多边形上每个交点的坐标，而是存储其每条斜边。如果一条斜边用其2个顶点坐标变量(x1，y1)，(x2，y2)来代替的话，这将比存储斜边上的每个交点坐标所需的存储容量要少得多； 改进交点的计算方法，并要求斜边上的每一交点与填充扫描线同步出现，以便画线填充多边形； 因多边形的斜边总量远比其交点总量小，故对斜边的排序相对较快。

10、基于上述三点要求，可重新安排斜边上交点的计算方法。 由于填充过程是从上到下逐行进行，故有: yi+l=yi-1 利用这一递推关系可求得斜边上对应交点的x坐标为: xi+1=xi+ x 其中 x=-(x2-x1+ )/(y2-y1) (y1y2即为斜边),显然当填充扫描线的高度， y=ymax=maxy1,y2时，开始计算该斜边上的第一个交点，此时该斜边又称为激活斜边；当填充扫描线的高度y=ymin=miny1,y2时，停止计算该斜边上的最后一个交点(即忽略斜边最低的交点坐标)。,这一递推计算交点公式的叠加分量，初始、结束条件为 :,不难发现，这4个递推参数(xs,ys， x,ye)既能明确无误

11、地表示一条斜边，又能非常方便地递推出该斜边与扫描线的所有交点，因此Y-X填充算法就主要存储这4个递推参数而不用存储其每条斜边的两个顶点。,多边形总的填充过程是:从上到下、从左到右逐行逐点地填充多边形内的每一个显示点。 因此无论多边形的各斜边等参数如何存储，最后要求各斜边上交点出现的次序是：排在上面的交点先出现，排在下面的交点后出现；对于同一高度的扫描线而言，排在左侧的交点先出现，排在右侧的交点后出现；且最好仅当填充哪一扫描行时，才要求递推出该行上的所有斜边上的交点以利于填充。,由于此时该算法存储的是每一条斜边而非交点，故在具体地填充之前，对这些斜边应按从上到下、从左到右的次序排序。虽然如此，这

12、种排序并不能保证在填充过程中，其交点出现的次序一定满足从左到右这一要求。 例如：,引发的问题,填充前，斜边排序后的结果为： AB，AC，DE，DF，FE 在填充yi+1行扫描线时，由于出现了新的斜边DE，DF，即有4条斜边被扫描填充，这些斜边的次序为： AB，DE，DF，AC，FE,结论：填充前对斜边进行的排序，只能保证其交点是从上到下的出现次序；而在动态填充过程中，每当出现新的斜边时，都要对斜边进行从左到右的排序，才能保证其交点是从左到右这一出现次序，这样才能保证多边形的填充过程顺利进行。,实现算法的数据结构-初始边表(EOT),由于算法需要进行上述两种排序，为了保存这两种排序结果，特设计了

13、如下相应的数据结构。 构造初始边表(EOT) 求出多边形各斜边的上述4个递推参数，然后对各斜边按 ymax 值从上到下排序。对具有同一高度的各斜边(见图2-8)，用一指针的指向表示其从左到右的排序结果。另外，把所有斜边的高度 ymax 值集中存放于一个高度表(术语为y桶表)中，此刻高度表的索引值为各斜边的高度，高度表的内容为指向各斜边的指针。为使高度表的操作简单，通常令高度表的大小等于显示器的纵向分辨率，如图2-9所示。各斜边从左到右排序的方法是：若两斜边的 ys 与 xs 两参数分别相同，则把x 值小的斜边排在前，反之排在后；若两斜边的 ys 值相同，则把 xs 值小的斜边排在前，反之排在后

14、。此时 y 桶表与所链接的斜边结点并称为多边形的初始边表(EOT)。,实现算法的数据结构-活动边表(AET),活动边表(AET) 当构造完初始边表(EOT)之后，就可以用递推的方法，从上到下地计算出每条扫描线与多边形各斜边的交点，这些交点用活动边表(AET)来保存。活动边表具有与初始边表相同的结点结构，并用指针的指向实现其斜边即交点从左到右的排列次序，见图。应注意的是，在活动边表中，仅仅记录当前扫描线与各斜边交点的x值以及所需的递推参数x与ymin，以便填充画线并不断地递推出下一扫描线与各斜边的交点。对于已填充过的交点，不用保存其x值，该x值不断被以后新出现的交点值所置换。因该表如此变化，故称

15、其为活动边表(AET)。,在活动边表中： AET表初始指针指示该行扫描线交点的最小x值； x值为当前扫描线与斜边交点的横坐标； ymin ,x递推参数意义与上同。,活动边表的主要操作过程,活动边表的主要操作过程如下： 令AET表为空。 y=TOP(显示设备坐标最大值)；y=y-1运算；直至指向EOT表中第一个非空单元。 反复做以下各步，直至y=0。 第一步，将EOT表中的结点加入AET表中，并按从左到右的次序对AET表中的结点排序。 第二步，根据AET表中成对结点所形成的区域，用相应像素值填充画直线。 第三步， y=y-1运算，如果y0，转第四步，否则结束。 第四步，当ymin=y时，将AET

16、表中相应结点删除(用简单近似方法处理奇异点)。 第五步，AET表中保留的结点执行x=x+ x运算。 第六步，如果此时EOT表中项ymax对应值为，则转第二步，否则转第一步。,在Y-X填充算法中，由于它利用了多边形的边线相关特性，即它们在同一高度上，其边线的X方向的顺序(左右关系)是很少改变的，因此在AET表的动态变化过程中，对其结点进行排序相对较少。 Y-X填充算法经过上述优化处理之后，虽然节省了存储空间，减少了排序量，提高了多边形的填充速度，但却大大增加了算法过程本身的难度，这是不尽人意的地方。但该算法仍不失为目前实面积图形生成的一们艮重要的算法，它扩展至三维图形的表面模型输出显示时，有很重

17、要的地位。,填充例子,该多边形的各边数据分别是 E1: (2,6), (ll,1);E2: (11,1), (17,5) ;E3:(17,10), (15,10); E4: (15,10), (10,8);E5: (10,8), (6,16);E6: (6,16), (2,16); E7: (2,16), (2,6);Es: (4,7), (8,8);E9: (8,8), (6,1.2); E10: (6,12),)(4,12);E11: (8,8), (6,12),在本算法的执行过程中，AET表中的结点要不断地进行插入、排序、删除。图2-1-3表示了在算法执行过程中扫描线的高度即y值、EOT

18、表与AET表的动态变化等过程。,五、多边形的优先级填充算法,在一个显示屏幕上显示多个实面积图形时，如果这些实面积图形相互重叠，则它们之间会发生相互遮挡的情况。为了明确地区分一个多边形遮挡另一个多边形，有必要给每一个多边形一个优先级编号，而且各多边形的优先级编号互不相同。 规定如下：编号大的多边形，其优先级低，该多边形应先生成显示；而编号小的多边形，其优先级高，该多边形应后生成显示。那么在光栅扫描图形显示器中，后生成的多边形自然地就覆盖了先生成的多边形。这一处理实面积图形之间相互遮挡关系的过程与画家在画布上处理多个不透明图画的具体过程非常相似，故用这种方法生成各个多边形的算法称为画家算法。,显然

19、在画家算法中，需先对各多边形的优先级编号(用户表示)进行从大到小的排序，然后再逐次生成各个多边形。此时当每个多边形用(YX)算法填充生成时，该画家算法又记为P-(YX)填充算法；当每个多边形用Y-X算法填充生成时，该画家算法又记为P-(Y-X)填充算法(或记为P-Y-X填充算法)。,画家算法的缺点和改进,画家算法原理虽然简单，但仍有不足之处。这是因为它的图形输出直观效果不明显，往往是那些重要的多边形因具有较高的优先级而在最后出现，这会分散用户的注意力，使用户感到非常不方便或产生混乱。如果屏幕中的多个多边形是整个的从上到下平稳地进行填充生成(如图所示)，就不会分散用户的注意力了。这种情况可以通过

20、先一次画完同一高度的所有多边形的填充线(按优先级的次序逐一画各多边形的填充线)，再画下一高度的所有多边形的各填充线，直到画完所有的多边形。这样就不会像画家算法那样，生成一个多边形之后再生成另一个多边形，而是缓慢地一次生成用户希望最终产生的结果。,1. (YPX)填充算法,1(YPX)填充算法 该算法的主要步骤如下： (1)对于每个多边形，计算其斜边与扫描线的全部交点，把(x,y,p)3个量作为一组数据输入到交点表中(即所有多边形的全部交点都保存在这个交点表中)。其中(x，y)为交点坐标，p为各多边形的优先级。 (2)交点表中的交点按x，y，p进行分类排序。就是说，仅当(y1y2)或(y1=y2

21、而p1p2)或(y1=y2，p1=p2而x1x2)的交点(x1，y1，p1)才排在交点(x2，y2，p2)之前。-上-下 高-低 左-右 (3)检索其交点表，对于一条扫描线，利用每个多边形中其交点成对出现这一规律，填充每一多边形的直线段，填充后的交点从交点表中删除。不断循环这一过程直至处理完所有交点。 (YPX)填充算法的缺点在于交点表很大，这会使得其分类排序非常缓慢，利用Y(PX)填充算法能改善这一点。,2Y-(PX)填充算法,Y-(PX)填充算法与Y-X填充算法非常类似，但这两者主要在分类排序方法与结点结构上有区别。Y-(PX)填充算法主要按Y，P，X的次序排序，而它的结点结构如图216所示。 Y-(PX)填充算法的主要步骤如下： (1)所有多边形的各斜边按Y，P，X的次序排序，其排序结果用一个初始边表保存。 (2)活动边表动态记录与当前扫描线相交的所有多边形各斜边的当前交点。 (3)每当活动边表中出现新的斜边结点时，这些斜边都要进行优先级编号从大到小、斜边从左到右的排序。 (4)利用活动边表中成对的交点所形成的区域画填充线，直至结束。