计算机图形学 多边形裁剪与填充 计算机图形学课程设计

计算机图形学课程设计一、课程目标知识目标：1. 让学生掌握计算机图形学的基本概念、基本原理和基本算法，如二维图形的表示、变换、裁剪和三维图形的建模、光照模型等。

2. 使学生了解计算机图形学在实际应用中的发展现状和前景，如虚拟现实、计算机辅助设计等。

3. 帮助学生建立计算机图形学与相关学科（如数学、物理、艺术等）的联系，提高跨学科素养。

技能目标：1. 培养学生运用计算机图形学知识解决实际问题的能力，如使用相关软件进行二维绘图、三维建模等。

2. 提高学生的编程能力，使其能够使用至少一种计算机图形学编程库（如OpenGL、DirectX等）实现基本图形绘制和动画效果。

3. 培养学生的团队协作能力和沟通表达能力，通过小组项目实践，共同完成具有一定难度的计算机图形学任务。

情感态度价值观目标：1. 激发学生对计算机图形学的兴趣，培养其主动探究、创新实践的精神。

2. 培养学生具有良好的审美观，能够从美学的角度评价和优化计算机生成的图形。

3. 强化学生的版权意识，尊重他人知识产权，遵循学术道德，树立正确的价值观。

本课程针对高中年级学生，结合学科特点和教学要求，将目标分解为具体的学习成果，以便于后续的教学设计和评估。

通过本课程的学习，期望学生能够掌握计算机图形学的基础知识，提高实际操作技能，培养良好的情感态度价值观。

二、教学内容1. 计算机图形学基本概念与历史：介绍计算机图形学的定义、发展历程、应用领域及发展趋势。

- 教材章节：第一章 计算机图形学概述- 内容安排：1课时2. 二维图形的表示与处理：讲解二维图形的数学表示、几何变换、裁剪算法等。

- 教材章节：第二章 二维图形处理- 内容安排：4课时3. 三维图形的建模与渲染：介绍三维图形的建模方法、光照模型、纹理映射等。

- 教材章节：第三章 三维图形处理- 内容安排：5课时4. 计算机动画与视觉效果：探讨计算机动画原理、关键帧动画、粒子系统等视觉效果技术。

- 教材章节：第四章 计算机动画与视觉效果- 内容安排：4课时5. 计算机图形学编程实践：学习计算机图形学编程库（如OpenGL、DirectX 等）的基本使用，完成二维和三维图形绘制实例。

计算机图形学(C语言)教案第一章：计算机图形学概述1.1 课程介绍介绍计算机图形学的定义、发展和应用领域。

解释图形和图像的区别。

1.2 图形学基本概念什么是点、线、面和体。

坐标系统和变换。

图形表示方法和存储结构。

1.3 图形处理流程图形输入、输出和显示。

图形裁剪和映射。

图形渲染和着色。

1.4 常见图形算法直线、圆和椭圆的算法。

填充算法和图像处理算法。

第二章：C语言基础2.1 C语言简介介绍C语言的历史和特点。

解释C语言在计算机图形学中的应用。

2.2 基本数据类型和语法整型、浮点型、字符型数据。

变量、常量和运算符。

2.3 控制语句条件语句和循环语句。

分支语句和循环控制语句。

2.4 函数和数组函数的定义和调用。

一维、二维数组和字符串。

第三章：图形库和API3.1 图形库简介什么是图形库和API。

常见的图形库和API介绍。

3.2 图形库的使用方法图形库的安装和配置。

图形库的基本函数和功能。

3.3 图形API的调用过程初始化图形环境。

创建图形对象和操作图形对象。

处理图形事件和关闭图形环境。

3.4 示例：绘制简单的图形使用图形库绘制点、线、圆等基本图形。

调整图形属性和颜色。

第四章：图形绘制和变换4.1 图形绘制基础绘制基本图形和文本。

使用图形属性调整图形外观。

4.2 图形变换坐标变换和几何变换。

矩阵和变换矩阵的运算。

4.3 图形裁剪和映射裁剪原理和算法。

映射原理和算法。

4.4 示例：绘制复杂的图形使用图形变换绘制复杂的图形。

应用图形裁剪和映射技术。

第五章：图形渲染和着色5.1 图形渲染基础什么是图形渲染和着色。

光和材质的模型。

5.2 颜色模型和转换RGB颜色模型和HSV颜色模型。

颜色转换和混合。

5.3 图形着色和光照基本着色算法和纹理映射。

点光源、聚光灯和环境光。

5.4 示例：实现简单的光照效果使用图形着色和光照技术绘制三维图形。

调整光照参数和观察光照效果。

第六章：图形界面设计6.1 图形界面设计基础界面设计原则和概念。

简单多边形裁剪算法摘要：多边形裁剪算法与线性裁剪算法具有更广泛的实用意义，因此它是目前裁剪研究的主要课题。

本文主要介绍了一种基于多边形顶点遍历的简单多边形裁剪算法，它有效降低了任意多边形裁剪复杂度。

通过记录交点及其前驱、后继信息，生成结果多边形，该算法简化了交点的数据结构，节省了存储空间，降低了算法的时间复杂度，具有简单、易于编程实现、运行效率高的特点。

关键词：多边形裁剪；交点；前驱；后继；矢量数组一、技术主题的基本原理简单多边形裁剪算法综合考虑现有多边形裁剪算法的优缺点，它是一种基于多边形顶点遍历来实现简单多边形裁剪工作的。

其主要的原理是遍历多边形并把多边形分解为边界的线段逐段进行裁剪，输出结果多边形。

二、发展研究现状近年来,随着遥感绘图、CAD辅助设计、图象识别处理技术的发展,图形裁剪算法从最初在二维平面上线和图形的裁剪扩展到三维空间里体和场的裁剪,国内外相继提出不少行之有效的算法,但越来越复杂的图形和计算也对算法的速度和适用性提出了越来越高的要求。

因此,不断简化算法的实现过程,完善细节处理,满足大量任意多边形的裁剪也就成了当今算法研究的焦点之一。

以往多边形裁剪算法不是要求剪裁多边形是矩形，就是必须判断多边形顶点的顺时针和逆时针性，即存在不实用或者是增加了多边形裁剪算法的难度。

为了解决现在的问题，我们研究现在的新多边形算法，其中，裁剪多边形和被裁剪多边形都可以是一般多边形，且不需要规定多边形输入方向。

它采用矢量数组结构，只需遍历剪裁多边形和被裁剪多边形顶点即完成多边形的裁剪，具有算法简单、运行效率高的特点。

三、新算法设计1、算法的思想本算法是为了尽量降低任意多边形裁剪算法复杂度而提出的，其主要思想是采用矢量数组结构来遍历裁剪多边形和被裁多边形顶点，记录裁剪多边形和被裁减多边形交点及其前驱、后继信息，并通过记录相邻交点的线段，然后通过射线法选择满足条件的线段，之后进行线段连接，输出对应的裁剪结果。

《计算机图形学》课程设计一、 设计要求1. 根据设计任务，编制程序，在机器上调试运行，并通过上机考核。

2. 按照下面的“三、课程设计报告格式”的要求，写出课程设计报告。

3. 课程设计报告在第19周之前交来。

二、 设计任务1．1）给定直线的起点坐标为P0（x0，y0）、终点坐标为P1（x1，y1），容易计算出直线斜率k 。

假设0≤k ≤1，则x 方向为主位移方向，绘制直线的递推公式为：,这称为数值微分法（Digital Differential Analyzer ，DDA ），请编程实现之。

提示：DDA 算法实质上是对直线斜率进行了四舍五入计算。

2）椭圆的扫描转换。

2.用鼠标在屏幕上绘制任意顶点数的封闭多边形并填充，填充效果如下图所示。

编程要求：⑴多边形的顶点数不受限制；⑵按下鼠标左键，拖动鼠标绘制多边形，同时按下Shift 键可以绘制水平边或垂直边； ⑶单击鼠标右键闭合多边形； ⑷使用边缘填充算法填充多边形。

⎩⎨⎧+=+=++k y y x x i i i i 1113请按照图所示，使用对话框输入直线的起点和终点坐标。

在窗口左侧区域绘制输入直线和“窗口”，在窗口右边右侧区域绘制“视区”并输出裁剪结果。

这里需要用到窗视变换的公式。

请分别用Cohen-Sutherland算法、中点分割裁剪算法和梁友栋－Barsky算法实现。

4在屏幕上使用鼠标绘制控制多边形，根据控制多边形的阶次绘制Bezier曲线和B样条曲线。

5．1）使用VC编程实现，以直角三角形为基础绘制下图所示Sierpinski三角形。

2）以屏幕范围为基础绘制下图所示Sierpinski地毯。

6．1）给定直线的起点颜色（如红色）和终点颜色（如黑色）不同，请使用中点Bresenham算法绘制任意斜率的颜色渐变直线，效果如图所示。

2）用梁友栋－Barsky算法裁剪线段P1(3，3)，P2(-2，-1)，裁剪窗口为wxl=0，wxr=2，wyb=0，wyt=2。

河南理工大学万方科技学院课程设计报告2010 — 2011学年第二学期课程名称计算机图形学设计题目多边形裁剪算法学生姓名孙晓芳学号**********专业班级计算机科学与技术10升指导教师侯守明2011 年6 月29 日目录目录目录 (I)第1章程序运行环境................................................................................... 错误!未定义书签。

1.1 程序运行环境的简单介绍................................................................. 错误!未定义书签。

1.2 程序运行环境的安装......................................................................... 错误!未定义书签。

1.3 多边形裁剪算法设计的内容........................................................................... 第2章直线裁剪和多边形裁剪的简单比较 (4)2.1 直线裁剪的介绍 (4)2.1.1 直线裁剪的基本原理………………………………………......................................2.1.2 直线裁剪算法的分类以及和窗口交点参数值的计算……………………………..2.2 多边形裁剪介绍 (9)2.2.1 多边形裁剪的基本思想……………………………………………………………..2.2.2 多边形和窗口相交的判定方法…………………………………………..第3章多边形裁剪方法的详细介绍 (12)3.1 Sutherland-Hodgman算法………………………………………………………………….3.2 多边形裁剪算法的流程图 (12)3.3多边形裁剪算法的实现 (13)第4章代码的实现 (14)第5章总结 (21)参考文献 (22)第1章程序的运行环境1.1 程序运行环境的简单介绍本次设计主要是运用了程序设计语言主要以C/C++语言为主，开发平台为Visual C++。

《计算机图形学》课程设计一、 设计要求1. 根据设计任务，编制程序，在机器上调试运行，并通过上机考核。

2. 按照下面的“三、课程设计报告格式”的要求，写出课程设计报告。

3. 课程设计报告在第19周之前交来。

二、 设计任务1．1）给定直线的起点坐标为P0（x0，y0）、终点坐标为P1（x1，y1），容易计算出直线斜率k 。

假设0≤k ≤1，则x 方向为主位移方向，绘制直线的递推公式为：,这称为数值微分法（Digital Differential Analyzer ，DDA ），请编程实现之。

提示：DDA 算法实质上是对直线斜率进行了四舍五入计算。

2）椭圆的扫描转换。

2.用鼠标在屏幕上绘制任意顶点数的封闭多边形并填充，填充效果如下图所示。

编程要求：⑴多边形的顶点数不受限制；⑵按下鼠标左键，拖动鼠标绘制多边形，同时按下Shift 键可以绘制水平边或垂直边； ⑶单击鼠标右键闭合多边形； ⑷使用边缘填充算法填充多边形。

⎩⎨⎧+=+=++k y y x x i i i i 1113请按照图所示，使用对话框输入直线的起点和终点坐标。

在窗口左侧区域绘制输入直线和“窗口”，在窗口右边右侧区域绘制“视区”并输出裁剪结果。

这里需要用到窗视变换的公式。

请分别用Cohen-Sutherland算法、中点分割裁剪算法和梁友栋－Barsky算法实现。

4在屏幕上使用鼠标绘制控制多边形，根据控制多边形的阶次绘制Bezier曲线和B样条曲线。

5．1）使用VC编程实现，以直角三角形为基础绘制下图所示Sierpinski三角形。

2）以屏幕范围为基础绘制下图所示Sierpinski地毯。

6．1）给定直线的起点颜色（如红色）和终点颜色（如黑色）不同，请使用中点Bresenham算法绘制任意斜率的颜色渐变直线，效果如图所示。

2）用梁友栋－Barsky算法裁剪线段P1(3，3)，P2(-2，-1)，裁剪窗口为wxl=0，wxr=2，wyb=0，wyt=2。

实验2：多边形区域扫描线填充或种子填充实验类型：验证、设计所需时间：3学时主要实验内容及要求：实现多边形区域扫描线填充的有序边表算法，并将实现的算法应用于任意多边形的填充，要求多边形的顶点由键盘输入或鼠标拾取，填充要准确，不能多填也不能少填。

要求掌握边形区域扫描线填充的有序边表算法的基本原理和算法设计，画出算法实现的程序流程图，使用C或者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）中的算法结合上述已有的链表操作函数实现多边形区域扫描线填充的主体功能④编写主函数，测试该算法源代码：#include<gl/glut.h>#include<iostream>using namespace std;typedef struct dePt{int x;int y;}dePt;void fill(GLint x1,GLint y1,GLint z1){glBegin(GL_POINTS);glVertex3f(x1,y1,0.0f);glEnd();}typedef struct Edge{int yUpper;float xIntersect, dxPerScan;struct Edge *next;}Edge;void insertEdge(Edge *list, Edge *edge){Edge *p,*q=list;p=q->next;while(p!=NULL){if(edge->xIntersect<p->xIntersect)p=NULL;else{q=p;p=p->next;}}edge->next=q->next;q->next=edge;}int yNext(int k, int cnt, dePt*pts){int j;if((k+1)>(cnt-1))j=0;elsej=k+1;while(pts[k].y==pts[j].y)if((j+1)>(cnt-1))j=0;else j++;return (pts[j].y);}void makeEdgeRec(dePt lower, dePt upper,int yComp,Edge *edge,Edge *edges[]) {edge->dxPerScan=(float)(upper.x-lower.x)/(upper.y-lower.y);edge->xIntersect=lower.x;if(upper.y<yComp)edge->yUpper=upper.y-1;elseedge->yUpper=upper.y;insertEdge(edges[lower.y],edge);}void buildEdgeList(int cnt,dePt *pts,Edge *edges[]){Edge *edge;dePt v1,v2;int i,yPrev=pts[cnt-2].y;v1.x=pts[cnt-1].x;v1.y=pts[cnt-1].y;for(i=0;i<cnt;i++){v2=pts[i];if(v1.y!=v2.y){edge=(Edge *)malloc(sizeof(Edge));if(v1.y<v2.y)makeEdgeRec(v1,v2,yNext(i,cnt,pts),edge,edges);elsemakeEdgeRec(v2,v1,yPrev,edge,edges);}yPrev=v1.y;v1=v2;}}void buildActiveList(int scan,Edge *active,Edge *edges[]) {Edge *p,*q;p=edges[scan]->next;while(p){q=p->next;insertEdge(active,p);p=q;}}void fillScan(int scan,Edge *active){Edge *p1,*p2;int i;p1=active->next;while(p1){p2=p1->next;for(i=p1->xIntersect;i<p2->xIntersect;i++)fill((int)i,scan,3);p1=p2->next;}}void deleteAfter(Edge *q){Edge *p=q->next;q->next=p->next;free(p);}void updateActiveList(int scan,Edge *active) {Edge *q=active, *p=active->next;while(p)if(scan>=p->yUpper){p=p->next;deleteAfter(q);}else{p->xIntersect=p->xIntersect+p->dxPerScan; q=p;p=p->next;}}void resortActiveList(Edge *active){Edge *q,*p=active->next;active->next=NULL;while(p){q=p->next;insertEdge(active,p);p=q;}}void scanFill(int cnt,dePt *pts){Edge *edges[1024],*active;int i,scan;for(i=0;i<1024;i++){edges[i]=(Edge *)malloc(sizeof(Edge)); edges[i]->next=NULL;}buildEdgeList(cnt,pts,edges);active=(Edge *)malloc(sizeof(Edge)); active->next=NULL;for(scan=0;scan<1024;scan++)buildActiveList(scan,active,edges);if(active->next){fillScan(scan,active);updateActiveList(scan,active);resortActiveList(active);}}}void ChangeSize(GLsizei w,GLsizei h){GLfloat nRange=400.0f;if(h==0) h=1;glViewport(0,0,w,h);glMatrixMode(GL_PROJECTION);glLoadIdentity();if(w<=h)glOrtho(-nRange,nRange,-nRange*h/w,nRange*h/w,-nRange,nRange);elseglOrtho(-nRange*h/w,nRange*h/w,-nRange,nRange,-nRange,nRange); glMatrixMode(GL_MODELVIEW);glLoadIdentity();}void Display(void){glClear(GL_COLOR_BUFFER_BIT);glLineWidth(5.0);int n,x,y,i;cout<<"请输入多边形顶点数："<<endl;cin>>n;dePt *t=new dePt[n];for(i=0;i<n;i++){cout<<"请输入第"<<i+1<<"个顶点坐标"<<endl;cin>>x>>y;t[i].x=x;t[i].y=y;glVertex2i(t[i].x,t[i].y);} glEnd();glFlush();scanFill(n,t);glFlush();}void SetupRC()glClearColor(1.0f,1.0f,1.0f,1.0f); glColor3f(1.0f,0.0f,0.0f);}实验结果：。