实验报告
一、实验目的
1、掌握有序边表算法填充多边形区域；
2、理解多边形填充算法的意义；
3、增强C语言编程能力。
二、算法原理介绍
根据多边形内部点的连续性知：一条扫描线与多边形的交点中，入点和出点之间所有点都是多边形的内部点。所以，对所有的扫描线填充入点到出点之间所有的点就可填充多边形。
判断扫描线上的点是否在多边形之内，对于一条扫描线，多边形的扫描转换过程可以分为四个步骤：
（1）求交：计算扫描线与多边形各边的交点；
（2）排序：把所有交点按x值递增顺序排序；
（3）配对：第一个与第二个，第三个与第四个等等；每对交点代表扫描线与多边形的一个相交区间;
（4）着色：把相交区间内的象素置成多边形颜色，把相交区间外的象素置成背景色。
p1,p3,p4,p5属于局部极值点，要把他们两次存入交点表中。如扫描线y=7上的交点中，有交点(2,7,13)，按常规方法填充不正确，而要把顶点(7,7)两次存入交点表中(2,7,7,13)。p2，p6为非极值点，则不用如上处理。
为了提高效率，在处理一条扫描线时，仅对与它相交的多边形的边进行求交运算。把与当前扫描线相交的边称为活性边，并把它们按与扫描线交点x坐标递增的顺序存放在一个链表中，称此链表为活性边表(AET)。
对每一条扫描线都建立一个与它相交的多边形的活性边表（AET）。每个AET的一个节点代表一条活性边，它包含三项内容
1.x -当前扫描线与这条边交点的x坐标；
2.Δx -该边与当前扫描线交点到下一条扫描线交点的x增量；
3.ymax -该边最高顶点相交的扫描线号。
每条扫描线的活性边表中的活性边节点按照各活性边与扫描线交点的x值递增排序连接在一起。
当扫描线y移动到下一条扫描线y = y+1时，活性边表需要更新，即删去不与新扫描线相交的多边形边，同时增加与新扫描线相交的多边形边，并根据增量法重新计算扫描线与各边的交点x。
当多边形新边表ET构成后，按下列步骤进行：
①对每一条扫描线i，初始化ET表的表头指针ET[i]；
②将ymax = i的边放入ET[i]中；
③使y =多边形最低的扫描线号；
④初始化活性边表AET为空；
⑤循环，直到AET和ET为空。
●将新边表ET中对应y值的新边节点插入到AET表。
●遍历AET表，将两两配对的交点之间填充给定颜色值。
●遍历AET表，将 ymax= y的边节点从AET表中删除，并将ymax> y的各边节点
的x值递增Δx；并重新排序。
●y增加1。
三、程序源代码
#include "graphics.h"
#define WINDOW_HEIGHT 480
#define NULL 0
#include "alloc.h"
#include "stdio.h"
#include "dos.h"
#include "conio.h"
typedef struct tEdge /*typedef是将结构定义成数据类型*/ { int ymax; /* 边所交的最高扫描线号 */
float x; /*当前扫描线与边的交点的x值 */ float dx; /*从当前扫描线到下一条扫描线之间的x增量*/ struct tEdge *next;
}Edge;
typedef struct point{int x,y;}POINT;
/*将结点插入边表的主体函数*/
void InsertEdge(Edge *list,Edge *edge)/*活性边edge插入活性边表list中*/ {
Edge *p,*q=list;
p=q->next; /*记住q原来所指之结点*/ while(p!=NULL) /*按x值非递减顺序增加边表*/ {
if(edge->x
p=NULL;
else /*要插入的边的x较小应该在当前插入*/
{q=p;
p=p->next;
}
}
edge->next=q->next; /*使欲插入之结点edge指向q原来所指之结点*/ q->next=edge; /*使q指向插入之结点*/ }
int yNext(int k,int cnt,POINT *pts)
/*对于多边形中的某个顶点序号k(0,1...6)，返回下一顶点的纵坐标,如果这2
个顶点所在边是水平的，则顺延，即返回第(k+2)个顶点的纵坐标),cnt是顶点个数
+1,pts指向多边形顶点结构体的指针*/
{
int j;
if((k+1)>(cnt-1))/*当前顶点为最后一个顶点，则下一个顶点为第0个顶点 */ j=0;
else
j=k+1; /*当前顶点不是最后一个顶点，下一个顶点为数组下标加一*/ while(pts[k].y==pts[j].y)
/*扫描线扫过平行顶点，需分情况找到当前顶点下下个顶点*/
if((j+1)>(cnt-1))
j=0;
else
j++;
return(pts[j].y); /*返回下一个顶点的y值 */ }
/* 计算增量，修改AET*/
/*生成边表结点，并插入到边表中的主体函数*/
void MakeEdgeRec(POINT lower,POINT upper,int yComp,Edge *edge,Edge
*edges[])
/*把边结点edge,放到lower.y扫描线所在的边结点指针数组edges[]中 */
{edge->dx=(float)(upper.x-lower.x)/(upper.y-lower.y);
edge->x=lower.x;
if(upper.y
/*奇点，应该把这点当作两个点而分开，所以把y的最大值减一，向下移动*/
else
edge->ymax=upper.y; /*不是奇点，不需改变y值 */ insertEdge(edges[lower.y],edge); /*插入一个边缘扫描线，插入到列表 */ }
/*创建边表的主体函数*/
void BuildEdgeList(int cnt,POINT *pts,Edge *edges[])
/*建立新边表,cnt:多边形顶点个数+1,edges[]:指向活性边结点的指针数组*/
{
Edge *edge;
POINT v1,v2;
int i,yPrev=pts[cnt-2].y;
/*当前顶点的前一个顶点的y值，在当前顶点不是奇点时使用该参数*/ v1.x=pts[cnt-1].x;
v1.y=pts[cnt-1].y;
for(i=0;i { v2=pts[i]; if(v1.y!=v2.y) /*非水平线*/ { edge=(Edge *)malloc(sizeof(Edge)); edge=(Edge*)malloc(sizeof(Edge)); if(v1.y /*当前顶点不是奇点，建立边表时使用下一个顶点的y值即yNext*/ MakeEdgeRec(v1,v2,yNext(i,cnt,pts),edge,edges); /*确定v1,v2边较高端点的开闭*/ else MakeEdgeRec(v2,v1,yPrev,edge,edges); /*当前顶点是奇点*/ } yPrev=v1.y; v1=v2; } } /*建立活性边表的主体函数：建立第scan条扫描线的活性边表*/ void BuildActiveList(int scan,Edge *active,Edge *edges[]) /*建立扫描线scan的活性边表,把活性边结点放入扫描线scan的结点指针数组edges[scan]中*/ { Edge *p,*q; p=edges[scan]->next; /*查找当前扫描线对应的y桶*/ while(p) /*y桶不空*/ {q=p->next; /*找到最后一个边结点，插入*/ InsertEdge(active,p); /*把更新后的边表重新插入边表中保存*/ p=q; } } /*填充一对交点的主体函数*/ void FillScan(int scan,Edge *active,int color) /*填充扫描线:填充扫描线上,且在下一结点到再下一结点之间的点*/ { Edge *p1,*p2; int i; p1=active->next; while(p1) { p2=p1->next; for(i=p1->x;i putpixel((int)i,scan,color); /*画出图形内部的点*/ p1=p2->next; /*活性表的下一条边表 */ } } void DeleteAfter(Edge *q) /*删除链表中结点,删除边结点q的后续结点p*/ { Edge *p=q->next; q->next=p->next; /*删除结点*/ free(p); } /* 删除 y=ymax 的边 */ /*填充完后，更新活动边表的主体函数*/ void UpdateActiveList(int scan,Edge *active) /*删除扫描线scan完成交点计算的活性边,同时更新交点x域*/ { Edge *q=active,*p=active->next; while(p) if(scan>=p->ymax) /*扫描线超过边的最大y值，此条边的节点应该删掉*/ { p=p->next; deleteAfter(q); } else /*扫描线未超过边的最大y值，相应的x值增加*/ { p->x=p->x+p->dx; q=p;p=p->next; } } /*对活性边表结点重新排序的主体函数*/ void ResortActiveList(Edge *active) /*活性边表active中的结点按x域从小到大重新排序*/ { Edge *q,*p=active->next; active->next=NULL; while(p) {q=p->next; InsertEdge(active,p); /*把更新后的边表重新插入边表中保存 */ p=q; } } /*多边形填充的主体程序*/ void ScanFill(int cnt,POINT *pts,int color) /*填充函数,输入:多边形顶点个数+1=cnt, 指向多边形顶点的指针数组pts*/ { Edge *edges[WINDOW_HEIGHT],*active; int i,scan,scanmax=0,scanmin=WINDOW_HEIGHT; for(i=0;i if(scanmin>pts[i].y)scanmin=pts[i].y; } for(scan=scanmin;scan<=scanmax;scan++) /*初始化每条扫面线的边链表*/ {edges[scan]=(Edge *)malloc(sizeof(Edge)); /*建“桶”*/ edges[scan]->next=NULL; } BuildEdgeList(cnt,pts,edges); /*建立有序边表*/ active=(Edge *)malloc(sizeof(Edge)); active->next=NULL; for(scan=scanmin;scan<=scanmax;scan++) /*扫描每条扫描线，求活性表*/ { BuildActiveList(scan,active,edges); /*建立活性边表*/ if(active->next) /*活性边表不为空*/ { FillScan(scan,active,color); /*填充当前扫描线*/ UpdateActiveList(scan,active); /*更新活化边表*/ ResortActiveList(active); /*重排活化边表*/ } } } /*开始菜单*/ void main() { POINT pts[7]; /*保存数组*/ int gdrive=DETECT,gmode; pts[0].x=100;pts[0].y=40; /*多边形顶点x、y坐标*/ pts[1].x=220;pts[1].y=140; pts[2].x=280;pts[2].y=80; pts[3].x=350;pts[3].y=300; pts[4].x=200;pts[4].y=380; pts[5].x=50;pts[5].y=280; pts[6].x=100;pts[6].y=40; /*合并桶中的新边，按次序插入到 AET 中*/ initgraph(&gdrive,&gmode,"C:\\TC3.0\\BGI"); /*设置graphic模式*/ ScanFill(7,pts,2); getch(); } 四、实验结果 图1 用有序边表算法生成的多边形 五、总结与体会 实验步骤 1)分析多边形区域扫描线填充算法的原理，确定算法流程 ①初始化：构造边表，AET表置空 ②将第一个不空的ET表中的边插入AET表 ③由AET表取出交点进行配对（奇偶）获得填充区间，依次对这些填充区间着色 ④y=yi+1时，根据x=xi+1/k修改AET表所有结点中交点的x坐标。同时如果相 应的ET表不空，则将其中的结点插入AET表，形成新的AET表 ⑤AET表不空，则转（3），否则结束。 2)编程实现 ①首先确定多边形顶点和ET/AET表中结点的结构 ②编写链表相关操作（如链表结点插入、删除和排序等） ③根据1）中的算法结合上述已有的链表操作函数实现多边形区域扫描线填充的 主体功能 ④编写主函数，测试该算法 通过运用C语言环境下的图像显示设置，本次实验我学会了多边形区域扫描线填充的有序边表算法，设计相关的数据结构（如链表结构、结点结构等），并将实现的算法应用于任意多边形的填充，为深一步的学习做好了铺垫。 六、参考文献 [1]张家广等编著.计算机图形学（第3版）.北京：清华大学出版社,1998年9月. [2]陈传波，陆枫主编，《计算机图形学基础》，电子工业出版社，2002年3月. 实验题目：实验二有效边表填充算法 1.实验目的： 设计有效边表结点和边表结点数据结构 设计有效边表填充算法 编程实现有效边表填充算法 2.实验描述： 下图1 所示多边形覆盖了12 条扫描线，共有7 个顶点和7 条边。7 个顶点分别为：P0（7，8），P1（3，12），P2（1，7），P3（3，1）, P4（6，5）, P5（8，1）, P6（12，9）。在1024×768 的显示分辩率下，将多边形顶点放大为P0（500,400），P1（350，600），P2（250，350），P3（350，50）, P4（500，250）, P5（600，50）, P6（800，450）。请使用有效边表算法填充该多边形。 图1示例多边形 图2 屏幕显示多边形 3.算法设计： （1）建立AET和BUCKET类； （2）初始化桶，并在建立桶结点时为其表示的扫描线初始化为带头结点的链表； （3）对每个桶结点进行循环，将桶内每个结点的边表合并为有效边表，并进行有效边表循环； （4）按照扫描线从小到大的移动顺序，计算当前扫描线与多边形各边的交点，然后把这些交点按X值递增的顺序进行排序，配对，以确定填充区间； （5）用指定颜色点亮填充区间内的所有像素，即完成填充工作。 4.源程序： 1)//AET.h class AET { public: AET(); virtual ~AET(); double x; int yMax; double k;//代替1/k AET *next; }; //AET..cpp AET::AET() { } AET::~AET() { } 2) //Bucket.h #include "AET.h" class Bucket { public: Bucket(); virtual ~Bucket(); int ScanLine; AET *p;//桶上的边表指针 Bucket *next; }; // Bucket.cpp Bucket::Bucket() { } Bucket::~Bucket() { } 3)//TestView.h #include "AET.h"//包含有效边表类 #include "Bucket.h"//包含桶类 #define Number 7//N为闭合多边形顶点数，顶点存放在整型二维数组Point[N]中class CTestView : public CView { 。。。。。。。。。 public: void PolygonFill();//上闭下开填充多边形 void CreatBucket();//建立桶结点桶 void Et();//构造边表 void AddEdge(AET *);//将边插入AET表 void EdgeOrder();//对AET表进行排序 一、填空题（每空0.5分，共 1 0 分） 1、 计算机图形学中的图形是指由点、线、面、体等 和明暗、灰度（亮度）、色 彩等 构成的，从现实世界中抽象出来的带有灰度、色彩及形状的图或形。 2、 一个计算机图形系统至少应具有 、 、输入、输出、 等 基本功能。 3、 常用的字符描述方法有：点阵式、 和 。 4、 字符串剪裁的策略包括 、 和笔划/像素精确度 。 5、 所谓齐次坐标就是用 维向量表示一个n 维向量。 6、 投影变换的要素有：投影对象、 、 、投影线和投影。 7、 输入设备在逻辑上分成定位设备、描画设备、定值设备、 、拾取设备 和 。 8、 人机交互是指用户与计算机系统之间的通信，它是人与计算机之间各种符号和动作 的 。 9、 按照光的方向不同，光源分类为： ， ， 。 10、从视觉的角度看，颜色包含3个要素：即 、 和亮度。 二、单项选择题（每题 2分，共 30 分。请将正确答案的序号填在 题后的括号内） 1、在CRT 显示器系统中，（ ）是控制电子束在屏幕上的运动轨迹。 A. 阴极 B. 加速系统 C. 聚焦系统 D. 偏转系统 2、分辨率为1024×1024的显示器需要多少字节位平面数为16的帧缓存？（ ） A. 512KB B. 1MB C. 2MB D. 3MB 3、计算机图形显示器一般使用什么颜色模型？（ ） A. RGB B. CMY C. HSV D. HLS 4、下面哪个不属于图形输入设备？（ ） A. 键盘 B. 绘图仪 C. 光笔 D. 数据手套 5、多边形填充算法中，错误的描述是（ ）。 A. 扫描线算法对每个象素只访问一次，主要缺点是对各种表的维持和排序的耗费较大 B. 边填充算法基本思想是对于每一条扫描线与多边形的交点，将其右方象素取补 C. 边填充算法较适合于帧缓冲存储器的图形系统 太原工业学院 实验拓展：绘制颜色渐变的三角形和四边形。 void CTriangle::Draw(CDC* pDC)//画出来一个三角形 { pDC->MoveTo(point0.x,point0.y); pDC->LineTo(point1.x,point1.y); pDC->LineTo(point2.x,point2.y); pDC->LineTo(point0.x,point0.y); } void CTriangle::GouraudShader(CDC* pDC) { SortVertex();//point0点为y坐标最小的点,point1点为y坐标最大的点,point2点的y坐标位于二者之间。如果y值相同，取x最小的点//定义三角形覆盖的扫描线条数 int nTotalScanLine = point1.y - point0.y + 1; //定义span的起点与终点数组 SpanLeft = new CPoint2[nTotalScanLine];//跨度左边数组 SpanRight = new CPoint2[nTotalScanLine];//跨度右边数组 //判断三角形与P0P1边的位置关系，0-1-2为右手系 int nDeltz = (point1.x - point0.x) * (point2.y - point1.y) - (point1.y - point0.y) * (point2.x - point1.x);//点矢量叉积的z坐标 if(nDeltz > 0)//三角形位于P0P1边的左侧 { nIndex = 0; DDA(point0, point2, TRUE); DDA(point2, point1, TRUE); nIndex = 0; DDA(point0, point1, FALSE); } 计算机图形学课程设计设计题目改进的有效边表算法对多边形的填充学院名称信息科学与技术学院 专业名称计算机科学与技术 学生姓名刘柯 学生学号201213030112 任课教师梅占勇 设计（论文）成绩 教务处制 2015年9 月28 日 目录 一、设计内容与要求 (3) 1.1设计题目 (3) 1.2 设计内容 (3) 1.3 设计目标 (3) 二、总体设计 (3) 2.1 多边形的表示 (3) 2.2 x-扫描线算法 (4) 2.3 改进的有效边表算法 (4) 2.3.1 改进的有效边表算法 (4) 2.3.2 有效边表 (5) 2.3.3 边表 (6) 三、详细设计 (8) 3.1 改进的有效边表算法的实现 (8) 3.2 有效边表算法程序流程图 (9) 四、测试结果 (9) 五、总结 (15) 六、源代码 (15) 参考文献 (26) 一、设计内容与要求 1.1设计题目 用改进的有效边表算法实现多边形的填充 1.2 设计内容 使用OpenGL实现用改进的有效边表算法填充多边形 1.3 设计目标 参照课本上改进的有效边表算法的思想，实现该算法的C语言代码，并用该算法搭配OpenGL以像素点的方式绘制出给定顶点坐标的多边形。 二、总体设计 2.1 多边形的表示 在计算机图形学中，多边形有2种重要的表示方法：顶点表示和点阵表示。 顶点表示用多边形的顶点序列来刻画多边形，这种方法直观、几何意义强，占用内存少，应用普遍，但它没有明确指出哪些像素在多边形内，故不能直接用于面着色。 点阵表示用位于多边形内的像素的集合来刻画多边形。这种表示法虽然失去了许多重要的几何信息，但便于运用帧缓存表示图形，是面着色所需要的图形表示形式。 大多数图形应用系统采用顶点序列表示多边形，而顶点表示又不能直接用于显示，那么就必须有从多边形的顶点表示到点阵表示的转换，这种转换称为多边形的扫描转 实验二2-2 一、实验题目 给定四个点绘制图4-44所示的不同转角的两个正方形，使用有效边表算法进行填充，填充效果如图4-45所示，注意采用“左闭右开”和“上闭下开”的原则，使得每个正方形的右边界和下边界没有填充。 二、实验思想 有效边表填充算法通过维护边表和有效边表，避开了扫描线与多边形所有边求交的复杂运算。填充原理是按照扫描线从小到大的移动顺序，计算当前扫描线与有效边的交点，然后把这些交点按x值递增的顺序进行排序、配对，以确定填充区间，最后用指定颜色填充区间内的所有像素，即完成填充工作。 三、实验代码 void CTestView::GetMaxX()//获得屏幕宽度 { CRect Rect; GetClientRect(&Rect); MaxX=Rect.right; } void CTestView::GetMaxY()//获得屏幕高度 { CRect Rect; GetClientRect(&Rect); MaxY=Rect.bottom; } void CTestView::ReadPoint()//读入点表函数 { //设置第一个正方形的4个顶点 int a=160; P1[0]=CP2(MaxX/4-a,MaxY/2+a);//P0 P1[1]=CP2(MaxX/4+a,MaxY/2+a);//P1 P1[2]=CP2(MaxX/4+a,MaxY/2-a);//P2 P1[3]=CP2(MaxX/4-a,MaxY/2-a);//P3 //设置第二个正方形的4个顶点 int b=ROUND(sqrt(2)*a); P2[0]=CP2(3*MaxX/4,MaxY/2+b);//P0 P2[1]=CP2(3*MaxX/4+b,MaxY/2);//P1 P2[2]=CP2(3*MaxX/4,MaxY/2-b);//P2 P2[3]=CP2(3*MaxX/4-b,MaxY/2);//P3 } void CTestView::DrawRect(CDC *pDC,CP2 *P)//绘制正方形函数{ CP2 T; CLine line; for(int i=0;i<4;i++)//边循环 { if(i==0) { line.MoveTo(pDC,P[i]); T=P[0]; } else { line.LineTo(pDC,P[i]);; } } line.LineTo(pDC,T);//闭合 } void CTestView::OnMENUIFill() { // TODO: Add your command handler code here COLORREF FColor; CColorDialog ccd(RGB(255,0,0)); if(ccd.DoModal()==IDOK)//调用调色板选取色 { FColor=ccd.GetColor(); m_Red=GetRValue(FColor);//获得颜色的红色分量 计算机图形学实验报告 班级： 学号： 姓名： 实验三多边形填充 一实验目的 1)掌握多边形的有效边表填充算法； 2)掌握边界像素处理原则； 3)掌握菱形图形的填充方法。 二实验要求 1)设计实现多边形填充类，可以设置顶点序列，调用填充函 数。 2)多边形填充采用有效边表填充算法进行实现，通过建立多 边形的桶表和边表数据，按照算法步骤依次扫描填充；3)调用设计实现的多边形填充类，对菱形线框进行颜色填充。三实验步骤 第1步:创建MFC应用程序框架 参照第一章的步骤建立空的MFC应用程序框架。 第2步:设计实现直线绘制类 设计实现多边形填充类 1）有效边表填充算法原理 在多边形填充过程中，常采用：“下闭上开”和“左闭右开”的原则对边界像素进行处理。有效边表填充算法通过维护“桶表和边表”数据，节省了有效数据存储空间，避免了扫描线与多 边形所有边求交的运算耗时。 图1 边表结点数据结构 有效边表填充算法实现步骤为： a）根据多边形的顶点序列，建立其“桶表和边表”数据。b）按照扫描线从小到大的移动顺序，取出当前扫描线对应桶的边表数据。 c）如果“桶表”数据已经取完，则填充结束；否则，继续后续填充操作。 d）将当前桶里的边表数据加入到有效边表，根据“下闭上开”的原则，删除已经到y max的无效边。 e）对当前扫描线的有效边表按x值递增的顺序进行排序、配对，以确定填充区间；根据“左闭右开”的原则，对两两配对的填充空间进行像素填充。 f）继续回到步骤b。 1）新建多边形填充类CFillPoly头文件 首先声明二维点类“CP2”、边表类“CAET”和桶表类“CBucket”，用于存储和传递多边形“桶表和边表”数据。多边形填充类中主要包括存放多边形顶点数据、有效边表结点指针和桶表结点指针的成员变量，以及创建桶表、边表、有效边表排序和填充多边形等成员函数。“FillPoly.h”头文件中具体类型声明代码如下： #pragma once class CP2 { public: CP2 (); virtual~CP2 (); CP2 (double,int); 实验报告 一、实验目的 1、掌握有序边表算法填充多边形区域； 2、理解多边形填充算法的意义； 3、增强C语言编程能力。 二、算法原理介绍 根据多边形内部点的连续性知：一条扫描线与多边形的交点中，入点和出点之间所有点都是多边形的内部点。所以，对所有的扫描线填充入点到出点之间所有的点就可填充多边形。 判断扫描线上的点是否在多边形之内，对于一条扫描线，多边形的扫描转换过程可以分为四个步骤： （1）求交：计算扫描线与多边形各边的交点； （2）排序：把所有交点按x值递增顺序排序； （3）配对：第一个与第二个，第三个与第四个等等；每对交点代表扫描线与多边形的一个相交区间; （4）着色：把相交区间内的象素置成多边形颜色，把相交区间外的象素置成背景色。 p1,p3,p4,p5属于局部极值点，要把他们两次存入交点表中。如扫描线y=7上的交点中，有交点(2,7,13)，按常规方法填充不正确，而要把顶点(7,7)两次存入交点表中(2,7,7,13)。p2，p6为非极值点，则不用如上处理。 为了提高效率，在处理一条扫描线时，仅对与它相交的多边形的边进行求交运算。把与当前扫描线相交的边称为活性边，并把它们按与扫描线交点x坐标递增的顺序存放在一个链表中，称此链表为活性边表(AET)。 对每一条扫描线都建立一个与它相交的多边形的活性边表（AET）。每个AET的一个节点代表一条活性边，它包含三项内容 1.x -当前扫描线与这条边交点的x坐标； 2.Δx -该边与当前扫描线交点到下一条扫描线交点的x增量； 3.ymax -该边最高顶点相交的扫描线号。 每条扫描线的活性边表中的活性边节点按照各活性边与扫描线交点的x值递增排序连接在一起。 当扫描线y移动到下一条扫描线y = y+1时，活性边表需要更新，即删去不与新扫描线相交的多边形边，同时增加与新扫描线相交的多边形边，并根据增量法重新计算扫描线与各边的交点x。 当多边形新边表ET构成后，按下列步骤进行： ①对每一条扫描线i，初始化ET表的表头指针ET[i]； ②将ymax = i的边放入ET[i]中； ③使y =多边形最低的扫描线号； ④初始化活性边表AET为空； ⑤循环，直到AET和ET为空。 ●将新边表ET中对应y值的新边节点插入到AET表。 ●遍历AET表，将两两配对的交点之间填充给定颜色值。 ●遍历AET表，将 ymax= y的边节点从AET表中删除，并将ymax> y的各边节点 的x值递增Δx；并重新排序。 ●y增加1。 三、程序源代码 #include "graphics.h" #define WINDOW_HEIGHT 480 #define NULL 0 #include "alloc.h" #include "stdio.h" #include "dos.h" #include "conio.h" typedef struct tEdge /*typedef是将结构定义成数据类型*/ { int ymax; /* 边所交的最高扫描线号 */ 软件学院《计算机图形学》课程示范性教学设计 一、本课程教学方法 1. 教学方法 概述：教学手段以多媒体教学为主、板书教学为辅，考虑到本课程内容多、学时少的特点，教学方法采用基础算法详细讲解、高级应用以专题讲座形式介绍的金字塔式教学方法，即对本科生应掌握的基本内容先详细介绍，以便学生上机时可以直接动手编程实现，然后对后面稍难一些的内容采用专题讲座的形式，即每次课介绍一个专题，既有“点”的深度，又有“面”的广度，点面结合，相辅相成，以达到在有限的学时内、开阔学生视野、提高学生学习兴趣的目的。 (1) 从宏观上介绍计算机图形学的研究内容及其应用领域。 (2) 选择一些常用的、经典的计算机图形学算法详细介绍。 (3)为了加深学生对算法实现过程的理解，强调理论联系实际的重要性，通过编程演示算法的实现结果，并借助于动画软件Flash演示算法的执行过程。 2．建议开课学期：第5学期 3．建议教学形式与教学方法：多媒体授课 二、各部分重点及难点 概述：本课程主要内容包括计算机图形学的研究内容、发展与应用，图形输入输出设备，图形显示原理，图形软件标准，基本图形生成算法，图形几何变换与裁剪，自由曲线和曲面，三维实体造型，分形几何造型，分形艺术，隐藏面消除，光照模型，颜色模型，光线跟踪，纹理细节模拟，常用的计算机动画技术和软件等。 第1章绪论 主要知识点：计算机图形学的研究内容及其与相关学科的关系，计算机图形学的发展与应用 主要能力点：通过阅读文献了解计算机图形学软硬件方面的最新研究进展，提高跟踪学科前沿能力、把握学科方向能力、进行文献检索、文献阅读和文献综述的能力。 主要素质点：科研工作人员的基本素质——把握学科方向、文献检索、阅读和综述 重点：计算机图形学的研究内容 难点：计算机图形学与相关学科的关系 第2章图形输入输出设备 主要知识点：交互式计算机图形处理系统的组成，图形输入输出设备，显示器分类，光栅扫描图形显示原理 主要能力点：通过阅读文献了解在图形输入、输出设备方面的最新研究进展，提高跟踪学科前沿能力、把握学科方向能力、进行文献检索、文献阅读和文献综述的能力。 主要素质点：科研工作人员的基本素质——把握学科方向、文献检索、阅读和综述 实验二有效边表填充算法 1.实验目的： 设计有效边表结点和边表结点数据结构 设计有效边表填充算法 编程实现有效边表填充算法 2.实验描述： 下图1 所示多边形覆盖了12 条扫描线，共有7 个顶点和7 条边。7 个顶点分别为：P0（7，8），P1（3，12），P2（1，7），P3（3，1）, P4（6，5）, P5（8，1）, P6（12，9）。在1024×768 的显示分辩率下，将多边形顶点放大为P0（500,400），P1（350，600），P2（250，350），P3（350，50）, P4（500，250）, P5（600，50）, P6（800，450）。请使用有效边表算法填充该多边形。 图1示例多边形 图2 屏幕显示多边形 3.算法设计： 4.源程序： 1）//AET.h和AET..cpp class AET { } 2）//Bucket.h和Bucket.cpp class Bucket { } 3) // TestView.h #include "AET.h"//包含有效边表类 #include "Bucket.h"//包含桶类 #define Number 7//N为闭合多边形顶点数，顶点存放在整型二维数组Point[N]中class CTestView : public CView { 。。。。。。。。。 public: void PolygonFill();//上闭下开填充多边形 void CreatBucket();//建立桶结点桶 void Et();//构造边表 void AddEdge(AET *);//将边插入AET表 void EdgeOrder();//对AET表进行排序 实验5 多边形区域扫描线填充 一、实验目的和要求 通过本次实验要求学生掌握多边形区域扫描线填充的有序边表算法的基本原理和算法设计。要求画出算法实现的程序流程图，使用VC++实现算法，并演示。 二、实验主要内容 实现多边形区域扫描线填充的有序边表算法，设计相关的数据结构（如链表结构、结点结构等），并将实现的算法应用于任意多边形的填充，注意多边形的顶点应由键盘输入或鼠标拾取，填充要准确，不能多填也不能少填。 三、参考实验步骤 1）分析多边形区域扫描线填充算法的原理，确定算法流程 ①初始化：构造边表，AET表置空 ②将第一个不空的ET表中的边插入AET表 ③由AET表取出交点进行配对（奇偶）获得填充区间，依次对这些填充区间着色 ④y=y i+1时，根据x=x i+1/k修改AET表所有结点中交点的x坐标。同时如果相应的 ET表不空，则将其中的结点插入AET表，形成新的AET表 ⑤AET表不空，则转（3），否则结束。 2）编程实现 ①首先确定多边形顶点和ET/AET表中结点的结构 ②编写链表相关操作（如链表结点插入、删除和排序等） ③根据1）中的算法结合上述已有的链表操作函数实现多边形区域扫描线填充的主体 功能 ④编写主函数，测试该算法 参考程序 void CFillView::OnDraw(CDC* pDC) { CFillDoc* pDoc = GetDocument(); ASSERT_V ALID(pDoc); POINT pt[5]={{225,10},{155,200},{330,55},{120,55},{295,200}}; CBrush brush(HS_DIAGCROSS,RGB(255,0,0)); /*设置填充的样式和颜色*/ CBrush* oldbrush=pDC->SelectObject(&brush); pDC->SetPolyFillMode(WINDING); /*选择填充模式*/ pDC->Polygon(pt,5); /*画五角星并填充图形*/ pDC->SelectObject(oldbrush); POINT pt1[4]={{200,300},{500,300},{500,500},{200,500}}; CBrush brush1(HS_CROSS,RGB(255,0,0)); /*设置填充的样式和颜色*/ CBrush* oldbrush1=pDC->SelectObject(&brush1); pDC->Polygon(pt1,4); /*画矩形并填充图形*/ pDC->SelectObject(oldbrush); brush.DeleteObject(); // TODO: add draw code for native data here } 计算机图形学实验报告实验三二维图形的区域填充 一．实验目的： 1．理解二维图形区域填充的含义。 2．理解有序边表算法的基本思想。 3．理解边填充算法的基本思想。 4．掌握种子填充算法的原理及实现。 5．掌握你所使用的开发环境的填充函数及相关函数。 2．实验内容： 1.实现种子填充算法，并测试你的算法，用它填充一个圆域和一个多边形域。 2.（tc下）测试getpixel、floodfill、setfillstyle函数。（其它环境选择相应函数） 2．（选做）实现有序边表填充算法。 3．（选做）实现边填充算法。 三．实验报告 1. 问题描述：采用种子填充算法填充圆 2. 程序清单： #include "graphics.h" #include "conio.h" void YING(int x,int y,int oldcolor,int newcolor); void main() { int gdriver=DETECT,gmode; initgraph(&gdriver,&gmode,"C:\\TC30\\BGI"); setbkcolor(LIGHTBLUE); setcolor(RED); circle(100,100,20); YING(100,100,BLACK,RED); getch(); closegraph(); } void YING(int x,int y,int oldcolor,int newcolor) { if(getpixel(x,y)==oldcolor) { putpixel(x,y,newcolor); getch(); YING(x,y+1,oldcolor,newcolor); YING(x,y-1,oldcolor,newcolor); YING(x-1,y,oldcolor,newcolor); YING(x+1,y,oldcolor,newcolor); } } 实验二有效边表填充算法 实验题目：有效边表填充算法学号： 姓名：班级： 指导老师：完成日期： 1.实验目的： 设计有效边表结点和边表结点数据结构 设计有效边表填充算法 编程实现有效边表填充算法 2.实验描述： 下图1 所示多边形覆盖了12 条扫描线，共有7 个顶点和7 条边。7 个顶点分别为：P0（7，8），P1（3，12），P2（1，7），P3（3，1）, P4（6，5）, P5（8，1）, P6（12，9）。在1024×768 的显示分辩率下，将多边形顶点放大为P0（500,400），P1（350，600），P2（250，350），P3（350，50）, P4（500，250）, P5（600，50）, P6（800，450）。 图1示例多边形 图2屏幕显示多边形 3.算法设计： 多边形的有效边表填充算法的基本原理是按照扫描线从小到大的移动顺序，计算当前扫描线与多边形各边的交点，然后把这些交点按x值递增的顺序进行排序、配对，以确定填充区间，然后用指定颜色点亮填充区间的所有像素，即完成填充工作。有效边表填充算法通过访问多边形覆盖区间内的每个像素，可以填充凸、凹多边形和环，已成为目前最为有效的多边形填充算法。 4.源程序： 1）//AET.h和AET..cpp class AET { public: AET(); virtual ~AET(); double x; int yMax; double k; //代替1/k AET *next; } 2）//Bucket.h和Bucket.cpp class Bucket { public: Bucket(); virtual ~Bucket(); int ScanLine; AET *p;//桶上的边表指针 Bucket *next; } 3) // TestView.h #include "AET.h"//包含有效边表类 #include "Bucket.h"//包含桶类 #define Number 7//N为闭合多边形顶点数，顶点存放在整型二维数组Point[N]中class CTestView : public CView { 。。。。。。。。。 public: void PolygonFill();//上闭下开填充多边形 void CreatBucket();//建立桶结点桶 void Et();//构造边表 void AddEdge(AET *);//将边插入AET表 void EdgeOrder();//对AET表进行排序 。。。。。。。。。。 protected: COLORREF GetColor;//调色板 CPoint Point[7];//定义多边形 Bucket *HeadB,*CurrentB;//桶的头结点和当前结点 AET E[Number],*HeadE,*CurrentE,*T1,*T2;//有效边表的结点 4)// TestView.cpp CTestView::CTestView() { //设置多边形的7个顶点 Point[0]=CPoint(550,400);//P0 Point[1]=CPoint(350,600);//P1 Point[2]=CPoint(250,350);//P2 Point[3]=CPoint(350,50);//P3 Point[4]=CPoint(500,250);//P4 Point[5]=CPoint(600,50);//P5 Point[6]=CPoint(800,450);//P6 } void CTestView::OnDraw(CDC* pDC) { 实验三多边形的有效边表填充算法 一、实验目的与要求 1、理解多边形的扫描转换原理、方法； 2、掌握有效边表填充算法； 3、掌握链表的建立、添加结点、删除节点的基本方法； 3、掌握基于链表的排序操作。 二、实验内容 在实验二所实现工程的基础上，实现以下内容并把实现函数封装在类 CMyGL 中。 1、C++实现有效边表算法进行多边形扫描转换 2、利用1进行多边形扫描转换和区域填充的实现； 三、实验原理 请同学们根据教材及上课的PPT独立完成。 四、实验步骤（程序实现）。 1、建立并选择工程项目。打开VC6.0->菜单File 的New 项,在projects 属性页选择MFC AppWizard(exe)项，在Project name 中输入一个工程名,如“Sample”。单文档。 2、新建一个图形类。选择菜单Insert New class，Class type 选择“Generic Class”，Name 输入类名，如“CMyCG。 3、向新建的图形类中添加成员函数（实际就是加入实验要求实现的图形生成算法的实现代码）。在工作区中直接鼠标右键单击，选择“Add Member Function…”项，添加绘制圆的成员函数。 void PolygonFill(int number, CPoint *p, COLORREF color, CDC* pDC) 添加其他成员函数： CreatBucket(); CreatET(); AddEdge(); EdgeOrder(); 4、成员函数的实现。实现有效边表填充算法。这一部分需要同学们去实现。 参考实现： 多边形的有效边表填充算法的基本过程为： 1、定义多边形： 2、初始化桶 3、建立边表 4、多边形填充 1)对每一条扫描线，将该扫描线上的边结点插入到临时AET表中，HeadE. 2)对临时AET表排序，按照x递增的顺序存放。 3)根据AET表中边表结点的ymax抛弃扫描完的边结点，即ymax>=scanline 4)扫描AET表，填充扫描线和多边形相交的区间。 《计算机图形学》教学大纲 安徽大学计算机学院 二零一七年二月 课程的性质与设置目的要求 《计算机图形学》课程是计算机类专业高等教育的专业技术基础课程。《计算机图形学》以高级语言、数据结构等课程为逻辑起点，以高年级本科生为讲授对象，是集理论性与应用性为一体的学科。 设置本课程的目的是：使学习者在全面了解计算机图形学的历史、现状与发展趋势的基础上，系统掌握计算机图形学的理论、方法、技术，并具备一定的图形应用系统开发的实际技能，从而胜任计算机辅助设计和制造、科学计算可视化、计算机图形处理、图形算法的设计、图形软件的开发等方面的工作。 学习本课程的要求是：通过一学期的学习，学习者应掌握计算机图形学的基本概念，了解图形设备的工作原理和特性；掌握基本图元及常用曲线的生成算法；熟练掌握图形几何变换、投影变换及裁剪、填充等图形处理的常用算法；能够了解三维图形的消隐技术，及真实感图形的基本知识；熟练掌握一种语言的图形函数和图形程序的设计技能，具有开发以图形为主的软件设计基本能力。通过本课程的学习，要求学生不但要了解和掌握计算机图形学的原理、方法和应用。另外，在实验技能方面，应比较熟练地掌握图形在计算机中的表示、图形生成算法的设计与调试。 先修课程要求：高级语言程序设计、数据结构 本课程计划34学时（讲授34学时），2学分 选用教材：《计算机图形学》，陆枫、何云峰编著，电子工业出版社 教学手段：多媒体教学 考核方法：本课程采用闭卷考试的方法 第一章绪论 一、学习目的 通过本章的学习，理解计算机图形学的有关概念，了解计算机图形学的产生、发展及应用。本章计划2学时。 二、课程内容 第一节计算机图形学及其相关概念 (一)计算机图形学的定义 计算机图形学是研究怎样用计算机生成、处理和显示图形的学科。 (二)计算机图形学和几个相关学科的关系 图像处理、计算机视觉、计算机图形学。 第二节计算机图形学的发展 (一)计算机图形学学科的发展 在1962年由MIT林肯实验室的Ivan.E.Sutherland提出。 (二) 图形硬件设备的发展 （三）图形软件的发展 第三节计算机图形学的应用 （一）计算机辅助设计与制造 (二) 计算机辅助绘图 （三）计算机辅助教学 （四）其他等 第四节计算机图形学研究动态 （一）计算机动画 (二)地理信息系统 （三）人机交互 （四）其他等 三、重点、难点提示和教学手段 重点掌握计算机图形学的定义，及图形学的典型应用。 代码： draw.cpp //using OpenGL #include "opengl.h" #include flush(); } void fill(){ //make k=(x2-x1)/(y2-y1) float k[PN]={0.0};for(int i=0;i!=PN;i++){k[i]=((float)(point[(i+1)%PN][0]-point[i][ 0])/(float)(point[(i+1)%PN][1]-point[i][1]));} //find min and max with selection sort. int min=point[0][1],max=min;for(int i=0;i!=PN;i++){if(point[i][1]>max){max=point[i][1];};;if( point[i][1] 计算机图形学论文基于扫描线的区域填充算法 姓名：魏艳娜 学号： 2012151115 班级： 201201 基于扫描线的区域填充算法 [摘要] ：图形通常由点、线、面、体等几何元素和灰度、色彩、线型、线宽等非几何属性组成。从处理技术上来看，图形主要分为两类，一类是基于线条信息表示的，如工程图、等高线地图、曲面的线框图等，另一类是明暗图，也就是通常所说的真实感图形。为此，必须建立图形所描述的场景的几何表示，再用某种光照模型，计算在假想的光源、纹理、材质属性下的光照明效果。计算机图形学的内容非常广泛，如图形硬件、图形标准、图形交互技术、光栅图形生成算法，以及科学计算可视化、计算机动画、虚拟现实等，这里重点研究区域填充。 [关键词]：计算机图形学；区域填充；扫描线算法 第1章绪论 1.1研究的背景 在计算机中重现真实世界的场景叫做真实感绘制。真实感绘制的主要任务是模拟真实物体的物理属性，简单的说就是物体的形状、光学性质、表面的纹理和粗糙程度，以及物体间的相对位置、遮挡关系等等。实时的真实感绘制已经成为当前真实感绘制的研究热点，而当前真实感图形实时绘制的两个热点问题则是物体网格模型的面片简化和基于图象的绘制。网格模型的面片简化，就是指对网格面片表示的模型，在一定误差的精度范围内，删除点、边、面，从而简化所绘制场景的复杂层度，加快图形绘制速度。IBR完全摒弃传统的先建模，然后确定光源的绘制的方法。它直接从一系列已知的图象中生成未知视角的图象。这种方法省去了建立场景的几何模型和光照模型的过程，也不用进行如光线跟踪等极费时的计算。该方法尤其适用于野外极其复杂场景的生成和漫游。 1.2研究的主要内容及结构 主要任务是实现多边形区域扫描线填充的有序边表算法，设计相关的数据结构，并将实现的算法应用于任意多边形的填充，区域填充,指的是在输出平面的闭合区域内完整地填充某种颜色或图案。以下所述及的区域填充算法或相关程序,主要针对显示平面内的区域而言。 区域填充的问题一般分两大类,一是多边形填充；一是种子填充；种子填充在学生掌握了“栈”这一抽象数据类型的实现方法的前提下,比较容易完成。而边标志填充算法却是介于这两类之间,部分地具有它们的痕迹,算法思想巧妙,实现起来更容易。多边形填充有一定难度，我们主要对多边形的扫描线算法填充做一些探讨，具体将以五角星为实例。 第2章理论综述 2.1 区域填充的理论知识 2.1.1 区域填充的概念 将区域的边界表示转换为区域内部象素表示的过程称为区域填充。区域填充是计算机图形学中的一个基本问题，在计算机辅助设计、真实感图形显示、图像分析等领域有着广泛的应用。区域填充算法是指给出一个区域的边界，要求在边界范围内对所有像素单元赋予指定的颜色代码。目前，区域填充算法中最常用的是多边形填色，常用的多边形填色算法 实验报告 Experimentation Report of Taiyuan teachers College 报告内容 一、实验目的四、实验方法 二、实验原理五、实验记录及数据处理 三、实验仪器及材料六、误差分析及讨论 系部年级课程 姓名同组者日期 项目有序边表算法 一、实验目的： 1、掌握有序边表算法填充多边形区域； 2、理解多边形填充算法的意义； 3、增强C语言编程能力。 二、实验内容： 根据多边形内部点的连续性知：一条扫描线与多边形的交点中，入点和出点之间所有点都是多边形的内部点。所以，对所有的扫描线填充入点到出点之间所有的点就可填充多边形。 判断扫描线上的点是否在多边形之内，对于一条扫描线，多边形的扫描转换过程可 以分为四个步骤： （1）求交：计算扫描线与多边形各边的交点； （2）排序：把所有交点按x值递增顺序排序； （3）配对：第一个与第二个，第三个与第四个等等；每对交点代表扫描线与多边形的一个相交区间; （4）着色：把相交区间内的象素置成多边形颜色，把相交区间外的象素置成背景色。 如图所示p1,p3,p4,p5属于局部极值点，要把他们两次存入交点表中。如扫描线y=7上的交点中，有交点(2,7,13)，按常规方法填充不正确，而要把顶点(7,7)两次存入交点表中 (2,7,7,13)。p2，p6为非极值点，则不用如上处理。 为了提高效率，在处理一条扫描线时，仅对与它相交的多边形的边进行求交运算。 把与当前扫描线相交的边称为活性边，并把它们按与扫描线交点x坐标递增的顺序存放在一个链表中，称此链表为活性边表(AET)。对每一条扫描线都建立一个与它相交的多边形的活性边表（AET）。每个AET的一个节点代表一条活性边，它包含三项内容： 1. x -当前扫描线与这条边交点的x坐标； 2. Δx -该边与当前扫描线交点到下一条扫描线交点的x增量； 3. ymax -该边最高顶点相交的扫描线号。 每条扫描线的活性边表中的活性边节点按照各活性边与扫描线交点的x值递增排序连接在一起。 当扫描线y移动到下一条扫描线y = y+1时，活性边表需要更新，即删去不与新扫描线相交的多边形边，同时增加与新扫描线相交的多边形边，并根据增量法重新计算扫描线与各边的交点x。当多边形新边表ET构成后，按下列步骤进行： ①对每一条扫描线i，初始化ET表的表头指针ET[i]； ②将ymax = i的边放入ET[i]中； ③使y =多边形最低的扫描线号； ④初始化活性边表AET为空； ⑤循环，直到AET和ET为空。 将新边表ET中对应y值的新边节点插入到AET表。 遍历AET表，将两两配对的交点之间填充给定颜色值。 遍历AET表，将 ymax= y的边节点从AET表中删除，并将ymax> y的各边节点的x值递增Δx；并重新排序。y增加1。 三、程序代码： #include "graphics.h" #define WINDOW_HEIGHT 480 #define NULL 0 #include "alloc.h" #include "stdio.h"计算机图形学 有效边表填充算法实验报告
《计算机图形学》试卷及答案
计算机图形学实验二
计算机图形学课程设计-有效边表填充算法的实现
计算机图形学实验有效边表填充算法
多边形填充
《计算机图形学》有序边表填充算法
计算机图形学课程示范性教学设计
实验二 有效边表填充算法
MFC多边形填充
计算机图形学圆的填充
有效边表填充算法
多边形的有效边表填充算法-
计算机图形学教学大纲(必修) 修改版
扫描线填充算法--有效边表填充算法
用扫描线算法实现多边形填充
有序边表算法
相关主题
文本预览