计算机图形学课程设计任务书.doc

计算机图形学课程设计任务书

23
2020年4月19日
文档仅供参考，不当之处，请联系改正。

课程设计(论文)任务书

软 件 学 院 学　　院　　 专　　业 　班
一、课程设计(论文)题目　 区域填充算法演示系统
二、课程设计(论文)工作自 年 6 月 8 日起至 年 6 月 12 日止。
三、课程设计(论文) 地点: 软 件 学 院 实 训 中 心
四、课程设计(论文)内容要求：
1．本课程设计的目的
计算机图形学课程设计是计算机图形学课程中的知识、技术和技能的一个综合应
用， 是培养图形软件开发能力的综合训练。经过课程设计，使学生更深入地理解和掌
握计算机图形学理论与相关算法，巩固课内所学的知识、技术和技能，进一步提高图
形软件开发的能力。为毕业设计和毕业后从事计算机绘图、计算机辅助设计、辅助教
学、辅助工程、图形处理等打下基础。
2．课程设计的任务及要求
1）课程设计任务：
（1)能实现区域填充光栅化算法的原理性演示。（算法过程的可视化及动画演示）
（2)要求有算法参数输入窗口和算法的图形化结果显示窗口。人机交互必须友好。
(3)将象素网格表现出来，建立网格坐标系。
（4) 如果采用种子填充算法实现填充，用鼠标选择种子点（也能够经过参数输入窗口
输入种子），用表格的形式显示堆栈存储的象素，象素出栈或入栈的过程要显示出来。
关键是要将象素填充的顺序表现出来。
2）创新要求：
实现对多边形的填充
3）课程设计论文编写要求
（1）课程设计任务及要求
（2）设计思路--工作原理、功能规划
（3）详细设计---数据分析、算法思路、功能实现（含程序流程图、主要代码及注
释）、界面等。
（4）运行调试与分析讨论---给出运行屏幕截图，分析运行结果，有何改进想法等。
（5）设计体会与小结---设计遇到的问题及解决办法，经过设计学到了哪些新知识，
巩固了哪些知识，有哪些提高。
（6）参考文献（必须按标准格式列出，可参考教材后面的参考文献格式）
（7）报告按规定排版打印，要求装订平整，否则要求返工；
（8）课设报告的装订顺序如下：封面---任务书---中文摘要---目录----正文---附录
(代码及相关图片)
（9）严禁抄袭，如有发现，按不及格处理。
4）课程设计评分标准：
（1）学习态度：10分；
（2）系统设计：20分；
（3）编程调试：20分；
（4）回答问题：20分；
（5）论文撰写：30分。
5）参考文献：
（1）陆枫 何云峰. 计算机图形学基础（第2版）[M]. 电子工业出版社
（2）张曦煌 杜俊俐. 计算机图形学[M]. 北京邮电大学出版社
（3）孙家广. 计算机图形学[M]. 清华大学出版社.
6）课程设计进度安排
1．准备阶段（4学时）：选择设计题目、了解设计目的要求、查阅相关资料
2．程序模块设计分析阶段（4学时）：程序总体设计、详细设计
3．代码编写调试阶段（8学时）：程序模块代码编写、调试、测试
4．撰写论文阶段（4学时）：总结课程设计任务和设计内容，撰写课程设计论文

学生签名：
年 6 月 8 日

课程设计(论文)评审意见
（1）学习态度（10分）：优（　）、良（　）、中（　）、一般（　）、差（　）；
（2）系统设计（20分）：优（ ）、良（　）、中（　）、一般（　）、差（　）；
（3）编程调试（20分）：优（　）、良（　）、中（　）、一般（　）、差（　）；
（4）回答问题（20分）：优（　）、良（　）、中（　）、一般（　）、差（　）；
（5）论文撰写（30分）：优（　）、良（　）、中（　）、一般（　）、差（　）；

评阅人： 　　　 职称： 讲师
年 6 月 日

中文摘要
[摘要] ：图形一般由点、线、面、体等几何元素和灰度、色彩、线型、线宽等非几何属性组成。从处理技术上来看，图形主要分为两类，一类是基于线条信息表示的，如工程图、等高线地图、曲面的线框图等，另一类是明暗图，也就是一般所说的真实感图形。计算机图形学一个主要的目的就是要利用计算机产生令人赏心悦目的真实感图形。为此，必须建立图形所描述的场景的几何表示，再用某种光照模型，计算在假想的光源、纹理、材质属性下的光照明效果。
[关键词] ：计算机图形学、区域填充、扫描线算法
目　录

一、课程设计任务及要求 1
二、需求分析 2
三、设计思路 3
四、详细设计 4
五、运行调试与分析讨论 5
六、设计体会与小结 6
七、参考文献 7

一、课程设计任务及要求
1)能实现区域填充光栅化算法的原理性演示。（算法过程的可视化及动画演示）
2）要求有算法参数输入窗口和算法的图形化结果显示窗口。人机交互必须友好。
3）将象素网络表现出来，建立网格坐标系。
4）如果采用种子填充算法实现填充，用鼠标选择种子点（也能够经过参数输入窗口输入点），用表格的形式显示堆栈存储的象素，象素出栈或入栈的过程要显示出来。关键是要将象素填充的顺序表现出来。
二、需求分析
在计算机中重现真实世界的场景叫做真实感绘制。真实感绘制的主要任务是模拟真实物体的物理属性，简单的说就是物体的形状、光学性质、表面的纹理和粗糙程度，以及物体间的相对位置、遮挡关系等等。实时的真实感绘制已经成为当前真实感绘制的研究热点，而当前真实感图形实时绘制的两个热点问题则是物体网格模型的面片简化和基于图象的绘制（IBR Image Based Rendering）。网格模型的面片简化，就是指对网格面片表示的模型，在一定误差的精度范围内，删除点、边、面，从而简化所绘制场景的复杂层度，加快图形绘制速度。IBR完全摒弃传统的先建模，然后确定光源的绘制的方法。它直接从一系列已知的图象中生成未知视角的图象。这种方法省去了建立场景的几何模型和光照模型的过程，也不用进行如光线跟踪等极费时的计算。该方法特别适用于野外极其复杂场景的生成和漫游。
主要任务是实现多边形区域扫描线填充的有序边表算法，设计相关的数据结构（如链表结构、结点结构等），并将实现的算法应用于任意多边形的填充，区域填充,指的是在输出平面的闭合区域内完整地填充某种颜色或图案。以下所述及的区域填充算法或相关程序,主要针对显示平面内的区域而言。
区域填充的问题一般分两大类,一是多边形填充；一是种子填充；种子填充在学生掌握了“栈”这一抽象数据类型的实现方法的前提下,比较容易完成。而边标志填充算法却是介于这两类之间,部分地具有它们的痕迹,算法思想巧妙,实现起来更容易。多边形填充有一定难度，我们主要对多边形的扫描线算法填充做一些探讨，具体将以五角星为实例。
扫描线填充算法一般包括四个步骤：求交、排序、交点配对、区域填充。正确求得扫描线与区域填内外轮廓线的交点是算法成败的关键问题。另一方面，采用合适的数据结构又能够简化操作、提高算法的效率。本论文由于采用链表结构记录轮廓线和交点，无需焦点排序的过程，因而提高了算法效率。扫描线来源于光栅显示器的显示原理：对于屏幕上所有待显示像素的信息，将这些信息按从上到下、自左至右的方式显示。
扫描线多边形区域填充算法是按扫描线顺序，计算扫描线与多边形的相交区间，再用要求的颜色显示这些区间的象素，即完成填充工作。区间的端点能够经过计算扫描线与多边形边界线的交点获得。对于一条扫描线，多边形的填充过程能够分为四个步骤：
（1）求交：计算扫描线与多边形各边的交点；
（2）排序：把所有交点按x值递增顺序排序；
（3）配对：第一个与第二个，第三个与第四个等等；每对交点代表扫描线与多边形的一个相交区间;
（4）填色：把相交区间内的象素置成多边形颜色;

三、总体设计
1） 分析多边形区域扫描线填充算法的原理，确定算法流程
① 初始化：构造边表ET，置AET表为空；
② 将第一个不空的ET表中的边插入AET表；
③ 由AET表取出交点进行配对（奇偶）获得填充区间，依次对这些填充区间着色；
④ y=yi+1时，根据x=xi+1/k修改AET表所有结点中交点的x坐标。同时如果相应的ET表不空，则将其中的结点插入AET表，形成新的AET表；
⑤ AET表不空，则转（3），否则结束。
2） 编程实现
① 首先确定多边形顶点和ET/AET表中结点的结构
② 编写链表相关操作（如链表结点插入、删除和排序等）
③ 根据1）中的算法结合上述已有的链表操作函数实现多边形区域扫描线填充的主体功能
④ 编写主函数，测试该算法

3）算法描述：
void polyfill (多边形 polygon, 颜色 color)
{ for (各条扫描线i )
  { 初始化新边表头指针NET [i]；把ymin = i 的边放进边表NET [i];   }
   y = 最低扫描线号；
   初始化活性边表AET为空；
   for (各条扫描线i )
    { 把新边表NET[i]中的边结点用插入排序法插入AET表，使之按x坐标递增顺序排列；
      遍历AET表，把y max= i 的结点从AET表中删除，并把y max > i结点的x值递增D x；
      若允许多边形的边自相交，则用冒泡排序法对AET表重新排序；
      遍历AET表，把配对交点区间(左闭右开)上的象素(x, y)，用drawpixel (x, y, color) 改写象素颜色值；
     }
} /* polyfill */

四、详细设计
1.用扫描线算法实现五角星填充
以（50,0），（60,30），（90,30），（70,45），（80,90），（50,60），（20,90），（30,45），（10,30），（40,30）这十个点作为五角星的十个点，利用扫描线算法将这个五角星进行填充。
根据扫描线的算法步骤，可将其算法过程描述如下：
３．１．１画五角星图形

(1)五角星图形

Ｙ

９０　　　　　　　　　　　　　　ｐ８　　　　　　　　　　　　　　　　　　　　　ｐ６
８０　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　ｅ７　　　　　ｅ６　
７０
　　　　　　　　　　　　　　　　　　　　　　　　　　　ｐ７　　　　　　　　　　　　　　　　ｙ＝６０
６０　　　　　　　　　　　　　　　ｅ８　　　　　　　　　　　　　　　　　ｅ５

５０　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　ｙ＝４５　　
　　　　　　　　　　　　　　ｐ９　　　　　　　　　　　　　　　　　　　ｐ５　　　　　　　　　　　　　　　　　　　　

４０　　　　　　　　ｅ９　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　ｅ４
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　ｙ＝３０　
３０　　　　　　ｐ０　　　ｅ０　　　　　ｐ１　　　　　　　　　　ｐ３　　　ｅ３　　　　　ｐ４
２０　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　ｅ１ ｅ２ｅ２　　　　　　　　　　　ｙ＝１０
１０　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
０　　　　　１０　　　２０　　　３０　　　４０　　　５０　ｐ２　６０　　　７０　　　８０　　　　９０　　ｘ
图3.1 五角星图形
(2)五角星的边表

构造ET表算法描述如下：

void CreatET(Edge *et[],struct pointtype p[]) /*根据顶点数组构造ET表*/
{
int i,lasty,lastx,nextx,nexty,ymax,cy,cx;
Edge *pe;
for(i=0;i<EDGEMAX;i++){
cy=p[i].y;
cx=p[i].x;

/*确定上一点的坐标及下一点的坐标，考虑数组的首尾点。。。*/
if(0==i){
lasty=p[EDGEMAX-1].y;
lastx=p[EDGEMAX-1].x;
}
else{
lasty=p[i-1].y;
lastx=p[i-1].x;
}
if(EDGEMAX-1==i){
nexty=p[0].y;
nextx=p[0].x;
}
else{
nexty=p[i+1].y;
nextx=p[i+1].x;
}

图3.2 五角星的边的分类表

(3)相对应活化边表
（a）y=0对应的活化边表

(b)y=3对应的活化边表

（c）y=6对应的活化边表

图3.3 活化边表
(4) 描述边算法的数据结构定义为：
typedef struct{
int ymax;
float x,delta;
struct Edge *nextEdge;
}Edge;

void CreatET(Edge *et[],struct pointtype p[]); /*根据顶点数组构造ET表*/

void EdgeInAel(Edge *ael,Edge *edge); /*ET表中某边edge插入至AEL表中，并排序，x相同时用下一点x+delta判断*/

void EdgeOutAel(Edge *ael,int y); /*删除AEL中y=ymax的边，并同时修改每边的delta值*/

(5) 顶点交点的计数问题

（6）对AEL中的边两两配对，（1和2为一对，3和4为一对，……）配对算法描述如下：
void EdgeDraw(Edge *ael,int y); /*按AEL中的1，2配对，3,4配对……然后x按规则去整后填充*/
（7）如果ET中的第y类非空，则将其中的结点插入AET表，形成新的AET表，算法描述如下：
void EtInAel(Edge *et[],Edge *ael,int y); /*找出ET中对应Y非空的边而且排序进入AEL活化边表*/
（8）实现五角星主要算法：
void main()
{
int gd=DETECT,gm;
int i,y,ymax;
struct pointtype p[EDGEMAX]={{50,0},{60,30},{90,30},{70,45},{80,90},{50,60},{20,90},{30,45},{10,30},{40,30},{50,0}};
Edge *et[ETMAX]={0};
Edge *ael;
ael->nextEdge=NULL;
initgraph(&gd,&gm,"");

CreatET(et,p);
for(i=0;i<ETMAX;i++){
if(et[i]!=NULL){
y=i;
break;
}
}/*确定y的最小序号*/

ymax=p[0].y;
for(i=0;i<EDGEMAX;i++){
if(p[i].y>ymax){
ymax=p[i].y;
}
}/*确定ymax*/

while(y<=ymax){
EtInAel(et,ael,y);
EdgeDraw(ael,y);
y++;
EdgeOutAel(ael,y);
}

填充算法如下：
void EdgeDraw(Edge *ael,int y) /*按AEL中的1，2配对，3,4配对……然后x按规则去整后填充*/
{
int counter=1; /*奇偶计数器*/
int color,maxcolor;
Edge *pmove;
float xlast,xcur;
int ylast,ycur;
maxcolor=getmaxcolor();
pmove=ael->nextEdge;
while(pmove!=NULL){
if(counter%2==1){
xlast=pmove->x;
}
else{ /*每两次边画线一次并重新赋值开始*/
xcur=pmove->x;
color=random(maxcolor);
setcolor(color);
line((int)xlast+1,y,(int)xcur,y);
xlast=0;
xcur=0;
}
counter++;
pmove=pmove->nextEdge;
}
}

五、运行调试与分析讨论

算法运行结果如下：未填充颜色:
填充彩色如下：

六、 设计体会与小结

七、参考文献
[1] 作者1，作者2. 参考书籍名称[M]. 出版地：出版社名称，出版年限
1． 李桂清，李淘渊.扫描线种子填充的问题及改进[J].广西大学学报（自然科学版），1998；（9）：207～212
2． 余正生，马立庄，彭群生.任意区域的边界扫描线转换[J].工程图学学报，1999；（1）：72～77
3． 倪明田，吴良芝. 计算机图形学[M].北京大学出版社， .
4． 唐泽圣，周嘉玉，李新友. 计算机图形学基础[M]. 清华大学出版社， .
5． 张志龙，李吉成，沈振康.一种快速复杂连通区域扫描线填充算法[J].国防科技大学电子科学与工程学院。 .