《人机交互论文基于扫描线区域填充算法》由会员分享，可在线阅读，更多相关《人机交互论文基于扫描线区域填充算法（12页珍藏版）》请在金锄头文库上搜索。
1、-*师*大学研究生作业论文专用封面作业论文题目：基于扫描线的区域填充算法课程名称：人机交互与界面设计任课教师*：*彬研究生*：*宝健*： 51 年级： 10级研专业：计算机应用技术学院部、所：数计学院任课教师评分：评阅意见：任课教师签名：年月日基于扫描线的区域填充算法数学与计算机科学学院 *宝健(51)摘要 ：图形通常由点、线、面、体等几何元素和灰度、色彩、线型、线宽等非几何属性组成。从处理技术上来看，图形主要分为两类，一类是基于线条信息表示的，如工程图、等高线地图、曲面的线框图等，另一类是明暗图，也就是通常所说的真实感图形。计算机图形学一个主要的目的就是要利用计算机产生令人赏心悦目的真实感图
2、形。为此，必须建立图形所描述的场景的几何表示，再用*种光照模型，计算在假想的光源、纹理、材质属性下的光照明效果。关键词 ：计算机图形学、区域填充、扫描线算法第一章 绪论1.1研究的背景在计算机中重现真实世界的场景叫做真实感绘制。真实感绘制的主要任务是模拟真实物体的物理属性，简单的说就是物体的形状、光学性质、外表的纹理和粗糙程度，以及物体间的相对位置、遮挡关系等等。实时的真实感绘制已经成为当前真实感绘制的研究热点，而当前真实感图形实时绘制的两个热点问题则是物体网格模型的面片简化和基于图象的绘制IBR Image Based Rendering。网格模型的面片简化，就是指对网格面片表示的模型，在一
3、定误差的精度*围内，删除点、边、面，从而简化所绘制场景的复杂层度，加快图形绘制速度。IBR完全摒弃传统的先建模，然后确定光源的绘制的方法。它直接从一系列的图象中生成未知视角的图象。这种方法省去了建立场景的几何模型和光照模型的过程，也不用进展如光线跟踪等极费时的计算。该方法尤其适用于野外极其复杂场景的生成和漫游。1.2研究的主要内容及构造主要任务是实现多边形区域扫描线填充的有序边表算法，设计相关的数据构造如链表构造、结点构造等，并将实现的算法应用于任意多边形的填充，区域填充,指的是在输出平面的闭合区域内完整地填充*种颜色或图案。以下所述及的区域填充算法或相关程序,主要针对显示平面内的区域而言。区
4、域填充的问题一般分两大类,一是多边形填充；一是种子填充；种子填充在学生掌握了“栈这一抽象数据类型的实现方法的前提下,比较容易完成。而边标志填充算法却是介于这两类之间,局部地具有它们的痕迹,算法思想巧妙,实现起来更容易。多边形填充有一定难度，我们主要对多边形的扫描线算法填充做一些探讨，具体将以五角星为实例。第二章 理论综述2.1 区域填充的理论知识 区域填充的概念 将区域的边界表示转换为区域内部象素表示的过程称为区域填充。区域填充是计算机图形学中的一个根本问题， 在计算机辅助设计、 真实感图形显示、 图像分析等领域有着广泛的应用。区域填充算法是指给出一个区域的边界，要求在边界*围内对所有像素单元
5、赋予指定的颜色代码。目前，区域填充算法中最常用的是多边形填色，常用的多边形填色算法有两种： 一类是种子填充算法， 一类是扫描线填充算法。研究如何用一种颜色或图案来填充一个二维区域。一般来说，区域的封闭轮廓是简单的多边形。假设轮廓线由曲线构成，则可将曲线转换成多条直线段顺连而成，此时，区域轮廓线仍然是一种多边形逼近。在计算机图形学中，多边形区域有两种重要的表示方法：顶点表示和点阵表示。所谓顶点表示，即是用多边形的顶点序列来表示多边形。这种表示直观、几何意义强、占内存少、易于进展几何变换，但由于它没有明确指出哪些像素在多边形内，故不能直接用于区域填充。所谓点阵表示，则是用位于多边形内的像素集合来刻
6、画多边形。这种表示丧失了许多几何信息，但便于进展填充。根据区域的定义，可以采用不同的填充算法，其中最具代表性的是：适用于顶点表示的扫描线类算法和适应于点阵表示的种子填充算法。 扫描线算法的描述扫描线填充算法一般包括四个步骤：求交、排序、交点配对、区域填充。正确求得扫描线与区域填内外轮廓线的交点是算法成败的关键问题。另一方面，采用适宜的数据构造又可以简化操作、提高算法的效率。本论文由于采用链表构造记录轮廓线和交点，无需焦点排序的过程，因而提高了算法效率。扫描线来源于光栅显示器的显示原理：对于屏幕上所有待显示像素的信息，将这些信息按从上到下、自左至右的方式显示。扫描线多边形区域填充算法是按扫描线顺
7、序，计算扫描线与多边形的相交区间，再用要求的颜色显示这些区间的象素，即完成填充工作。区间的端点可以通过计算扫描线与多边形边界限的交点获得。对于一条扫描线，多边形的填充过程可以分为四个步骤： 1求交：计算扫描线与多边形各边的交点； 2排序：把所有交点按*值递增顺序排序； 3配对：第一个与第二个，第三个与第四个等等；每对交点代表扫描线与多边形的一个相交区间; 4填色：把相交区间内的象素置成多边形颜色;2.2 数据构造与算法 扫描线多边形填充算法的主要步骤1.建立NET(NewEdgeList)2.从最低扫描线开场到最高扫描线循环： 3.建立或调整AET(ActiveEdgeList)； 4.按照A
8、ET中的接点顺序填充。扫描线填充算法的目标是减少递归层次。步骤是填充并确定种段；初始化：将种子区段压入堆栈；出栈：如果堆栈为空，则算法完毕；否则取栈顶元素 (y, *Left, *Right)，以纵坐标为 y 的扫描线为当前扫描线，*Left, yLeft为搜索区间；填充并确定新的区段。因此，扫描线多边形区域填充算法的根本原理是，待填充区域按y方向(*方向亦可)扫描线顺序扫描生成。具体实现时，首先按扫描线顺序，计算扫描线与多边形的相交区间；再用指定的颜色填充这些区间内的像素，即完成这一条扫描线的填充工作。区间的端点可以通过计算扫描线与多边形边界的交点获得。为了提高效率，在处理每一条扫描线时，仅
9、对与它相交的多边形的边进展求交运算。我们把当前扫描线相交的边称为活性边(active edge)，并把它们按扫描线交点*坐标递增的顺序存放在一个链表中，称此链表为活性边表(AET)。为了提高速度，假定当前扫描线与多边形*一条边的交点的*坐标为*i，则下一条扫描线与该点的交点不需要重新计算，而是通过增加一个增量*来获得。对于直线a*+by+c=0,*=-b/a为常数。另外使用增量法计算时，还需要知道一条边何时不再与下一条扫描线相交，以便及时把它从活性边表中删除出去。因此，活性边表结点的数据构造应保存如下内容：第1项保存当前扫描线与边的交点坐标*值；第2项保存从当前扫描线到下一条扫描线间*的增量*
10、；第3项保存该边所交的最高扫描线好yma*。第4项存指向下一条边的指针。活性边表的每个节点的内容：Yma* *mindelta*为了方便活性边表的建立与更新，可为每一条扫描线建立一个边表(ET)，存放在该扫描线第一次出现的边。也就是说，假设*边的较低端点为ymin，则该边就放在扫描线ymin的边表中。 边的分类表ET按照边的下端点y坐标对非水平边进展分类的指针数组活化边表AEL记录与当前扫描线相交的边交点边的算法:typedef struct int yma*; float *,delta; struct Edge *ne*tEdge;Edge;yma*:边的上端点y坐标*:在AEL中表示当前
11、扫描线与边的交点的*坐标，在ET中的初值为边的下端点的*坐标。delta*:边的斜率的倒数ne*tEdge:指向下一条边的指针。具体步骤如下:step1：把新边表NETi中的边结点，用插入排序法 插入活性边表AET，使之按*坐标递增顺序排序；step2：遍历AET表，把配对交点之间的区间(左闭右开)上的各象 素(*，Y)，用drawpi*el(*,y,color)改写象素颜色值；step3：遍历AET表，把Yma*=i的结点从AET表中删除，并把 Yma*i的结果点的*值递增*；step4：重复各扫描线顶点交点的计数问题 :扫描线与多边形顶点相交时，必须正确的进展交点个数计算，否则，在进展填充
12、时会出现错误。扫描线与多边形相交的边分处扫描线的两侧，则计一个交点；扫描线与多边形相交的边分处扫描线同侧，且yiy(i-1),yiy(i-1),yiy(i+1)，则计0个交点；扫描线与多边形边界重合，则计1个交点。是否正确求取扫描线与多边形的交点是扫描线填充算法成败的关键。研究发现，求取扫描线与多边形的交点，既要利用边界点的局部信息，又要利用一条扫描线上所有交点的全部信息。因此，论文的求交过程包括以下三步：第一步：遍历多边形的边一次，确定扫描线纵坐标的变化*围ymin 和yma*,建立一个空间的扫描线交点链表；第二步：遍历多边形区域的边一次，根据每一边界点与前驱、后继之间的空间关系，初步求得各
13、扫描线与边的交点；第三步：对第二步中求得的交点进展修剪，得到正确的扫描线交点表。当遍历完区域多边形轮廓线上的所有边界点之后，求交过程的第二步完毕，此时的扫描线活动边表所记录得是各条扫描线与区域轮廓线的交点。但是，此时还不能保证各条扫描线上的交点的数目为偶数，因此不能直接用于配对，必须对各个扫描线的交点链表进展修剪。求交点过程的第三步对每一条扫描线的交点链表进展修剪，其目的是删除那些由于出现“半交半切的情况而多算的交点，以便实现正确的配对。假设待修剪的扫描线为y=i,修正的过程为：1) 以扫描线y=i的交点链表上的第一个交点Pi,l点作为起点；2) 如果起点为空，转5完毕；否则，按照从左到右的顺
14、序遍历链表上的每一个点，如果遇到一个标号非零的交点Pf(设其标号值为lf),则从Pf的后继开场，寻找第二个标号非零的交点Ps,设其标号值为ls,此时：如果lf与ls 符号一样，则转3；如果lf与ls符号相反，则转4；3) 将Pf和Ps从交点链表中删除，并以Ps 的后继作为起点，转2；4) 将Pf从交点链表中删除，令Ps的标号ls=0，并以Ps的后继作为起点，转2；5) 完毕。通过分析不难发现，对于任意多边形区域，经上述算法所求的每一条扫描线与多边形的交点数目为偶数，按照先后次序两两配对时，能确保交点之间的区域位于区域的内部。描述扫描线与多边形交点的数据构造定义一为：struct crosspo
15、intint *;/*交点的横坐标*/int y;/*交点的纵坐标*/int l;/*交点的标记*/crosspoint* pNe*tPoint;/*下一个交点*/采用单链表的方式记录多边形上的所有与扫描线的交点坐标，以下图所示。图中，E表示多边形的边，E，=1,2,n。由于多边形的外轮廓具有封闭性，所以链表的起点E和终点E也具有8-连通关系。对于链表中任意一个边界点E，定义E为E的前驱，E为E的后继。后面将会看到，前去和后继对于判断交点的属性是必不可少的。 把与当前扫描线相交的边称为活性边，并把它们按与扫描线交点*坐标递增的顺序存放在一个链表中，称此链表为活性边表(AET)。AEL：E1EnE3E22.3扫描线的算法步骤：1） 分析多边形区域扫描线填充算法的原理，确定算法流程 初始化：构造边表ET，置AET表为空； 将第一个不空的ET表中的边插入AET表； 由AET表取出交点进展配对
