计算机图形学课程设计

摘要：巩固和实践计算机图形学课程中的理论和算法;学习表现计算机图形学算法的技巧;培养认真学习,积极探索的精神.总体要求:策划,设计并实现一个能够充分表现某个图形学算法的...

关键词：计算机,算法

类别：专题技术

来源：牛档搜索（Niudown.COM）

---

　　本文系牛档搜索（Niudown.COM）根据用户的指令自动搜索的结果，文中内涉及到的资料均来自互联网，用于学习交流经验，作品其著作权归原作者所有。不代表牛档搜索（Niudown.COM）赞成本文的内容或立场，牛档搜索（Niudown.COM）不对其付相应的法律责任！

计算机图形学课程设计

内容及要求

（构造算法方向）

一、      总体目标和要求

目标：深入研究算法，以某个（或某类）图形学算法为目标，深入研究。继而策划、设计并实现一个能够表现该算法原理的或完整过程的演示系统，并能从某些方面作出评价和改进意见。通过完成一个完整程序，经历策划、设计、开发、测试、总结和验收各阶段，达到：

u  巩固和实践计算机图形学课程中的理论和算法；

u  学习表现计算机图形学算法的技巧；

u  培养认真学习、积极探索的精神。

总体要求：策划、设计并实现一个能够充分表现某个图形学算法的演示系统，界面要求美观大方，能清楚地演示算法执行的每一个步骤。

开发环境：Viusal C++ 6.0

工具库的限制：不允许使用任何图形软件包，如OpenGL，DirectX，Java3D等。但可应用如文件读取（特别是图像文件读取、外部模型文件读取）、数据组织（如STL）等非图形工具。

项目选择：选择以下所列程序中的一个即可，具体见第三节。

二、      时间节点和分值

课程设计的时间安排上分若干阶段，每个阶段有相应截止时间、要求、分值和评分标准。总分为100分。作业的提交方式参见附录。

第n周末表示第n周的周六晚上12：00之前，滞后提交的作业将扣除相应分值直至全部扣除。

第一次

时间：

第12周末。

要求：

选择本方式的同学以电子邮件方式提交。邮件中姓名、班级、学号和联系方式（包括寝室号，电话，电子邮件）。回执中将会给出号码，请保留该号码以便以后提交作业时使用。（共2分）

评分标准：

按时寄出邮件，内容完整清晰。

第二次

时间：

第14周末。

要求：

提交策划报告，包括程序概述，准备完成的功能列表，以及后续的进度安排，这一不分要清楚地写出以何种方式表现该算法，指导以后的工作。这一部分相当重要，请同学们务必重视。（共18分）

评分标准：

清晰的功能列表，算法表现策略，合理且明确的进度安排。中期检查将参照此进度安排。

第三次

时间：

第16周末。

要求：

中期检查，至少提交至概要设计报告，并有一个原型系统。

概要设计确定使用的开发环境，整体模块结构等，可参见相关国家标准文档，但不必完全依照。

原型系统能够基本实现该算法，为以后表现该算法作准备。（共25分）

评分标准：

规范、翔实的概要设计报告（5分），功能正确的原型系统（20分）。

第四次

时间：

下学期第2周末。

要求：

终期检查，提交包括前几次作业在内的所有文档、代码和程序。

包括：策划报告、概要设计、详细设计、开发日志、测试报告、源程序、可执行文件、使用手册和实验报告（共45分，其中有25分为系统的总体表现）

所有内容以打包方式通过FTP上传提交，地址到时另行通知。打包内容的目录结构为：

--以分配的组号为目录名的文件夹

|--doc（所有文档）

|--src（源代码及工程文件）

|--bin（可执行文件）

|--sample（用开发的程序所生成的示例文件）

|--readme.txt（对整个打包文件内容的说明）

评分标准：

提交的文件结构清晰、内容完整（5分），源程序可读性（5分），使用手册易用性（5分），实验报告（5分），总体表现（25分）。

实验报告第一页写明学号、姓名。内容上应包括程序概述、完成功能列表、技术细节的实现、个人创新点（如果有的话）、项目总结和参考资料。实验报告的内容可能会影响到对系统总体表现的评价，请认真对待，把完成的任务表述清楚。

第五次

时间：

下学期第3周。

要求：

组织面试。面试时间为每人10分钟，其中2分钟准备时间，4分钟演示时间和4分钟问答时间。（10分）

评分标准：

演示条理清晰，内容详实（5分），问答（5分）。

三、      内容与要求

作业分为九项内容，只要做其中一项即可。

1)      简单图形的生成

内容：

直线的生成

              ①DDA法 ②中点画线法 ③Bresenham法

圆的生成

              ①中点法 ② Bresenham法

椭圆的生成

①  中点法 ② Bresenham法

要求：

Ø  将象素网格表现出来，建立网格坐标系

Ø  用橡皮筋的形式输入参数

Ø  鼠标移动时，显示鼠标当前位置

Ø  显示判别式的计算过程和下一点的选择策略

Ø  记录生成点的坐标，建议用表的形式

Ø  图形生成过程可以重复进行

Ø  建议在一个程序中实现上述算法

2)      多边形区域填充

内容：

种子填充算法；扫描线填充算法；扫描线种子填充算法；边填充算法；栅栏填充算法

要求：

Ø  将象素网格表现出来，建立网格坐标系

Ø  用橡皮筋的形式输入多边形

Ø  鼠标移动时，显示鼠标当前位置

Ø  种子填充算法中用鼠标选择种子点，用表格的形式显示堆栈存储的象素，象素出栈或入栈的过程要显示出来。关键是要将象素填充的顺序表现出来。

Ø  扫描线算法中先显示一条自上而下的扫描线，如果不与多边形相交，则直接向下移动，否则需要填充多边形内的交点。多边形形成以后，要显示边表的内容，扫描线移动的时候，要动态改变活性边表的内容，一条边加入活性边表或从活性边表中删除需要给出提示。

3)      二维裁剪

内容：

线段裁剪

窗口为长方形：①Cohen-SutherLand算法 ②中点分割算法 ③Liang-Barsky 算法

窗口为任意多边形：Cyrus-Beck算法

多边形裁剪

       Sutherland-Hodgman算法，Weiler-Atherton算法（任意多边形互裁剪）

要求：

Ø  将象素网格表现出来，建立网格坐标系

Ø  用橡皮筋的形式输入剪裁线段或多边形

Ø  对于线段裁剪，线段被窗口的四条边裁剪的过程要显示出来

Ø  对于中点分割算法，要显示线段一步步分割的过程

Ø  Liang-Barsky 算法和Cyrus-Beck算法要显示矢量的计算和选择t参数的过程

Ø  Sutherland-Hodgman多边形裁剪过程需先输入一多边形，然后用窗口四边裁剪的过程中要显示顶点增删的过程。

Ø  Weiler-Atherton算法需要指明裁剪多边形和被裁剪多边形，从而决定交点的分类

Ø  可以根据程序的需要决定是否在一个程序中完成。

4)      直线和多边形的反走样

内容：实现以下四种反走样的方法：提高分辨率、超采样、连续区域采样、离散区域采样

要求：

Ø  将象素网格表现出来，建立网格坐标系

Ø  用橡皮筋输入一条直线或多边形，线的宽度可以设置，为一整数

Ø  对于提高分辨率方法，首先用网格象素法表示一条直线或多边形，然后将网格缩小，观察直线的变化

Ø  超采样法需要根据经过的不同子象素的数目决定该象素的亮度

Ø  连续区域采样需要根据直线所占象素面积来决定象素的亮度

Ø  离散区域采样将所占面积离散化，根据所占象素点的数目决定亮度，需要考虑加权模板，模板的大小为奇数

Ø  如以上点需要计算，则必须显示计算步骤

5)      曲线曲面生成

内容：

       曲线：Bezier曲线、二次B样条曲线、三次B样条曲线、Nurbs曲线

       曲面：Ferguson曲面、Bezier曲面、三次B样条曲面、Nurbs曲面、Coons曲面

要求：

对于曲线：

Ø  采用橡皮筋方法输入型值点

Ø  第n个点为鼠标当前位置，使得曲线的形状随鼠标变化

Ø  输入的点存入表格中

Ø  在完成一段曲线后，可以移动型值点的位置产生新的曲线

Ø  Nurbs曲线需要输入权因子

Ø  可以显示曲线的型值点多边形

对于曲面：

Ø  采用键盘输入点的坐标

Ø  曲面生成后，可以用鼠标操纵多角度观察，曲面有两种方式切换：网格曲面和光滑曲面（光滑曲面需要加上一个缺省光照）

6)      图形变换

内容：简单图形的平移、旋转、缩放

要求：

可以产生一些基本几何体（球，椭球体，圆锥，长方体，四面体等），大小先利用缺省值，然后在点取物体，在菜单上选择操作方式，程序应该能自动生成变换矩阵并显示出来。另外还可以定义变换，放入变换列表，将若干个变换组合起来形成统一的变换矩阵，然后一下实施变换操作。

7)      简单几何体的消隐

内容：简单几何体（球，椭球体，圆锥，长方体，四面体等）的生成和消隐

要求：

体用线框形式表示，可以在消隐和未消隐之间切换，用鼠标可以操纵形体的位置的角度，包括自消隐和互消隐（多个物体之间的消隐）。

8)      纹理映射

内容：将纹理映射到简单的曲面上

要求：

纹理应该可以自定义，也可以导入外面的纹理图片

曲面包括：平面，二次曲面，Bezier曲面，三次B样条曲面，曲面可以导入外面的图形文件，也可以在程序中生成。

能任意指定映射关键点，能消除纹理走样。

9)      光源效果

内容：演示光源效果

要求：

可以添加光源，删除光源，对每一个光源进行命名；对每一个光源可以进行编辑，包括散射参数，镜面参数，光源位置参数，聚光方向，聚光指数，聚光角度，聚光终止角度，三个衰减系数等。还可以对环境光进行调整，调整采用滑动条的形式。需要制作高光效果，光源效果作用在一个球体上，球体可以指定材质，插值方式分面片模型、Phong模型和Gouraud模型三种可以从不同的角度实时观察。

       注：

作业提交方式与做一图形系统的方式相同。

欢迎大家有好的想法，设计出美观大方，表现力好，有创意的程序。

上面列出的是最基本的要求，如果大家能提出更好的建议，请提出来。

 

 

第二篇：计算机图形学实验报告 课程设计 大作业

安徽建筑工业学院

计算机图形学 实验报告

院（系）名称： 专 业：

班 级： 姓 名： 学 号： 指 导 老 师：

实验一 实现任意直线的中点画线算法

【实验目的】

掌握直线的中点画线算法；

【实验环境】

VC++6.0

【实验内容】

利用任意的一个实验环境，编制源程序，实现直线的中点画线法。

【实验原理】

假定直线斜率k在0~1之间，当前象素点为（xp,yp），则下一个象素点有两种可选择点P1（xp+1,yp）或P2（xp+1,yp+1）。若P1与P2的中点（xp+1,yp+0.5）称为M，Q为理想直线与x=xp+1垂线的交点。当M在Q的下方时，则取P2应为下一个象素点；当M在Q的上方时，则取P1为下一个象素点。这就是中点画线法的基本原理。

图2.1.2 中点画线法每步迭代涉及的象素和中点示意图 下面讨论中点画线法的实现。过点(x0,y0)、(x1, y1)的直线段L的方程式为F(x, y)=ax+by+c=0，其中，a=y0-y1, b=x1-x0, c=x0y1-x1y0，欲判断中点M在Q点的上方还是下方，只要把M代入F（x，y），并判断它的符号即可。为此，我们构造判别式: d=F(M)=F(xp+1, yp+0.5)=a(xp+1)+b(yp+0.5)+c

当d<0时，M在L(Q点)下方，取P2为下一个象素；

当d>0时，M在L(Q点)上方，取P1为下一个象素；

当d=0时，选P1或P2均可，约定取P1为下一个象素；

注意到d是xp, yp的线性函数，可采用增量计算，提高运算效率。

若当前象素处于d?0情况，则取正右方象素P1(xp+1, yp),要判下一个象素位置，应计算 d1=F(xp+2, yp+0.5)=a(xp+2)+b(yp+0.5)=d+a，增量为a。

若d<0时，则取右上方象素P2(xp+1, yp+1)。要判断再下一象素，则要计算d2= F(xp+2, yp+1.5)=a(xp+2)+b(yp+1.5)+c=d+a+b ，增量为a＋b。画线从(x0, y0)开始，d的初值 d0=F(x0+1, y0+0.5)=F(x0, y0)+a+0.5b，因 F(x0, y0)=0，所以d0=a+0.5b。

由于我们使用的只是d的符号，而且d的增量都是整数，只是初始值包含小数。因此，我们可以用2d代替d来摆脱小数，写出仅包含整数运算的算法程序。

【实验程序】

void Midpoint Line (int x0,int y0,int x1, int y1,int color)

{ int a, b, d1, d2, d, x, y；

a=y0-y1； b=x1-x0；d=2*a+b；

d1=2*a；d2=2* (a+b)；

x=x0；y=y0；

drawpixel(x, y, color);

while (x<x1)

{ if (d<0) {x++；y++； d+=d2; }

else {x++； d+=d1;}

drawpixel (x, y, color);

} /* while */

} /* mid PointLine */

举例：用中点画线方法扫描转换连接两点P0（0,0）和P1（5,2）的直线段。 a=y0-y1=-2; b=x1-x0=5; d0=2*a+b=1;d1=2*a=-4;d2=2*(a+b)=6 ,

x y d

0 0 1

1 0 -3

2 1 3

3 1 -1

42 5

52 15

2.1.3 中点画线法

实验二 实现任意一种线段的裁剪算法以及多

边形裁剪算法

【实验目的】

1、 掌握直线段裁剪的基本原理；

2、 掌握多边形裁剪的基本原理；

【实验环境】

VC++6.0

【实验内容】

编制程序，完成直线段和多边形的裁减过程。

【实验原理】

1．算法基本思想

对每条直线段p1(x1,y1)p2(x2,y2)分三种情况处理：

(1) 直线段完全可见，“简取”之。

(2) 直线段完全不可见，“简弃”之。

(3) 直线段既不满足“简取”的条件，也不满足“简弃”的条件，需要对直线段按交点进行分段，分段后重复上述处理。

2．算法步骤

(1) 编码

对于任一端点(x,y)，赋予一个4 位的二进制码D3D2D1D0。

编码规则如下：

若x<wxl，则D0=1，否则D0=0；

若x>wxr，则D1=1，否则D1=0；

若y<wyb，则D2=1，否则D2=0；

若y>wyt，则D3=1，否则D3=0。

(2) 裁剪

先求出端点p1 和p2 的编码code1 和code2，然后：

若code1|code2=0，对直线段应简取之。

若code1&code2≠0，对直线段可简弃之。

若上述两条件均不成立。则需求出直线段与窗口边界的交点。在交点处把线段一分为二，其中必有一段完全在窗口外，可以弃之。再对另一段重复进行上述处理，直到该线段完全被舍弃或者找到位于窗口内的一段线段为止。

(3) 求交

假定直线的端点坐标为(x1,y1)和(x2,y2)左、右边界交点的计算上、下边界交点的计算。

3．算法实现

(1) 输入直线段的两端点坐标：p1(x1,y1)、p2(x2,y2)，以及窗口的四条边界坐标：wyt、wyb、wxl 和wxr。

(2) 对p1、p2 进行编码：点p1 的编码为code1，点p2 的编码为code2。

(3) 若code1|code2=0，对直线段应简取之，转(6)；否则，若code1&code2≠0，对直线段可简弃之，转(7)；当上述两条均不满足时，进行步骤(4)。

(4) 确保p1 在窗口外部：若p1 在窗口内，则交换p1 和p2 的坐标值和编码。

(5) 按左、右、上、下的顺序求出直线段与窗口边界的交点，并用该交点的坐标值替换p1 的坐标值。也即在交点s 处把线段一分为二，并去掉p1s 这一段。考虑到p1 是窗口外的一点，因此可以去掉p1s。转(2)。

(6) 用直线扫描转换算法画出当前的直线段p1p2。 (7) 算法结束。

【实验程序】

一：Cohen-Sutherland线段裁剪算法

#include <gl/glut.h>

//#include <gl/wingdi.h> /* SetPixel() */ #include <math.h> #include <stdio.h>

///////////////////////////////////////////////////////////////////////////

const winLeftBitCode=0x1; const winRightBitCode=0x2; const winBottomBitCode=0x4; const winTopBitCode=0x8;

///////////////////////////////////////////////////////////////////////////

class wcPt2D{ public:GLfloat x,y; };

///////////////////////////////////////////////////////////////////////////

inline int inside(int code){return int (!code);}

//////////////////////////////////////////////////////////////////////////

inline int reject(int code1,int code2) { return int (code1&code2);

}

/////////////////////////////////////////////////////////////////////////

inline int accept(int code1,int code2) { return int (!(code1|code2));

}

////////////////////////////////////////////////////////////////////

/////

GLubyte encode(wcPt2D

pt,wcPt2D

winMin,wcPt2D winMax)

{ GLubyte code=0x00; if(pt.x<winMin.x) code=code|winLeftBitCode; if (pt.x>winMax.x) code=code+winRightBitCode; if(pt.y<winMin.y) code=code|winBottomBitCode; if(pt.y>winMax.y)

code=code|winTopBitCode; return (code);

}

////////////////////////////////////////////////////////////////////

////////

void swapPts(wcPt2D *p1,wcPt2D *p2) { wcPt2D tmp; tmp=*p1;

*p1=*p2;

*p2=tmp; }

//////////////////////////////////////////////////////////////////////////

void swapCodes(GLubyte *c1,GLubyte *c2) { GLubyte tmp;

tmp=*c1; *c1=*c2;*c2=tmp;

}

////////////////////////////////////////////////////////////////////////

void draw_pixel(int ix,int iy/*,int value*/) { glBegin(GL_POINTS); glVertex2i(ix,iy); glEnd(); }

////////////////////////////////////////////////////////////////////////

int inline round(const float a){return int (a+0.5);}

/////////////////////////////////////////////////////////////////////////

void lineDDA(int x0,int y0,int x_end,int y_end,double a,double b,double c)

{ glColor3f(a,b,c); int dx=x_end-x0; int dy=y_end-y0; int steps,k;

float xIncrement,yIncrement,x=x0,y=y0; if(abs(dx)>abs(dy)) steps=abs(dx);

else

steps=abs(dy);

xIncrement=float (dx)/float (steps);

yIncrement=float (dy)/float (steps);

draw_pixel(round(x),round(y)); for (k=0;k<steps;k++) { x+=xIncrement; y+=yIncrement;

draw_pixel(round(x),round(y));

}

}

////////////////////////////////////////////////////////////////////////////////////

void lineClipCohSuth(wcPt2D

winMin,wcPt2D winMax,wcPt2D p1,wcPt2D p2)

{ GLubyte code1,code2;

GLint done=false,plotLine=false; GLfloat m; while(!done) { code1=encode(p1,winMin,winMax); code2=encode(p2,winMin,winMax); if(accept(code1,code2)) { done=true; plotLine=true;

} else if(reject(code1,code2)) done=true; else { if(inside(code1)) {

swapPts(&p1,&p2);

swapCodes(&code1,&code2);

}

if(p2.x!=p1.x)

m=(p2.y-p1.y)/(p2.x-p1.x);

if(code1&winLeftBitCode) {

p1.y+=(winMin.x-p1.x)*m; p1.x=winMin.x; } else

if(code1&winRightBitCode) {

p1.y+=(winMax.x-p1.x)*m;

p1.x=winMax.x;

} else

if(code1&winBottomBitCode) {

if(p2.x!=p1.x) p1.x+=(winMin.y-p1.y)/m;

p1.y=winMin.y;

} else

if(code1&winTopBitCode) {

if(p2.x!=p1.x) p1.x+=(winMax.y-p1.y)/m;

p1.y=winMax.y;

}

}

}

if(plotLine)

lineDDA(round(p1.x),round(p1.y),round(p2.x),round(p2.y),0.0,0.0,1.0);

}

///////////////////////////////////////////////////////////////////////////////////////

void display() { glClear(GL_COLOR_BUFFER_BIT); wcPt2D

winMin,winMax,p1,p2,q1,q2,t1,t2,m1,m2;

//裁剪窗口 winMin.x=80; winMin.y=100;

winMax.x=290; winMax.y=500;

/*lineDDA(80,100,80,450,1.0,0.0,0.0); lineDDA(80,100,290,100,1.0,0.0,0.0); lineDDA(290,100,290,450,1.0,0.0,0.0); lineDDA(80,450,290,450,1.0,0.0,0.0); */

/* //全图 winMin.x=0; winMin.y=000; winMax.x=500; winMax.y=500; */ /////////////////////// p1.x=0; p1.y=0; p2.x=400; p2.y=400; ////////////////////// q1.x=0; q1.y=0; q2.x=100; q2.y=400; ////////////////////// t1.x=100; t1.y=400; t2.x=400;

t2.y=400;

////////////////////// m1.x=300; m1.y=200; m2.x=100; m2.y=400;

//只显示裁剪框内的线段

lineClipCohSuth(winMin,winMax,p1,p2); lineClipCohSuth(winMin,winMax,q1,q2); lineClipCohSuth(winMin,winMax,t1,t2); lineClipCohSuth(winMin,winMax,m1,m2)

;

//显示裁剪框和待剪线段

/*

lineDDA(300,200,100,400,0.0,0.0,1.0); lineDDA(0,0,100,400,0.0,0.0,1.0); lineDDA(100,400,400,400,0.0,0.0,1.0); lineDDA(0,0,400,400,0.0,0.0,1.0);

*/

glFlush(); }

void myinit() { glClearColor(0.8,1.0,1.0,1.0); //glColor3f(0.0,0.0,1.0); glPointSize(1.0);

glMatrixMode(GL_PROJECTION); glLoadIdentity();

gluOrtho2D(0.0,500.0,0.0,500.0); glViewport(0,0,200,500);

}

void main(int argc,char **argv ) { glutInit(&argc,argv);

glutInitDisplayMode(GLUT_SINGLE|GLUT_RGB);

glutInitWindowSize(500,500); glutInitWindowPosition(200.0,200.0);

glutCreateWindow("CG_test_CG_test_Co

hen-Sutherland 线段裁剪算法示例");

// glutFullScreen(); glutDisplayFunc(display); myinit(); glutMainLoop();

}

稍微修改源程序即可得到以下裁剪框以及被裁剪线段：

二：Sutherland_Hodgman多边形裁剪算法

#define TRUE 1 #define FALSE 0

typedef struct { float x, y; } vertex;

void intersect(p1, p2, clipboundary, intersectp) vertex p1, p2, *clipboundary, *intersectpt; /* p1和p2为多边形的边的起点和终点，clipboundary为窗口边界，intersectpt中返回边与窗口边界的交点 */

{

if ( clipboundary[0].y== clipboundary[1].y ) /* 水平边界 */

{

intersectpt->y = clipboundary[0].y; intersectpt->x =

p1.x

+

(clipboundary[0].y-p1.y)*(p2.x-p1.x)/(p2.y-p1.y);

}

else /* 垂直边界 */ {

intersectpt->x = clipboundary[0].x; intersectpt->y =

p1.y

+

(clipboundary[0].x-p1.x)*(p2.y-p1.y)/(p2.x-p1.x);

} }

int inside(testvertex, clipboundary) vertex testvertex, *clipboundary;

/* 如果顶点testvertex在窗口边界clipboundary的内部，那么返回TRUE；否则返回FALSE */

{

if ( clipboundary[1].x < clipboundary[0].x ) /* 上边界 */

if ( testvertex.y <= clipboundary[0].y ) return TRUE;

if ( clipboundary[1].x > clipboundary[0].x ) /* 下边界 */

if ( testvertex.y >= clipboundary[0].y ) return TRUE;

if ( clipboundary[1].y > clipboundary[0].y ) /* 右边界 */

if ( testvertex.x <= clipboundary[0].x ) return TRUE;

if ( clipboundary[1].y < clipboundary[0].y ) /* 左边界 */

if ( testvertex.y <= clipboundary[0].x ) return TRUE; return FALSE; }

outputvertex(outvertex, outlength, outvertexlist) vertex outvertex; int *outlength; vertex *outvertexlist

/* 向输出顶点序列中输出顶点outvertex */ {

outvertexlist[*outlength] = outvertex; (*outlength)++; } void

Sutherland_Hodgman_Polygon_Clipping(invertexlist, outvertexlist, inlength, outlength, clipboundary)

vertex *invertexlist, *outvertexlist; int inlength, *outlength; vertex *clipboundary;

/* invertexlist为输入顶点序列，inlength为输入序列长度；outvertexlist为输出顶点序列，outlenght中返回输出序列长度；clipboundary为窗口边界 */

{

vertex s, p, i; int j;

*outlength = 0;

s = invertexlist[inlength-1]; /* 输入顶点序

列的最后一个顶点 */

for ( j=0; j<inlength; j++ ) {

p = invertexlist[j];

if ( inside(p,clipboundary) ) /* 情况1和4 */

{

if ( inside(s,clipboundary) ) /* 情况1 */

outputvertex(p,outlength,outvertexlist); else /* 情况4 */ {

intersect(s,p,clipboundary,&i); outputvertex(i,outlength,outvertexlist); outputvertex(p,outlength,outvertexlist); } }

else /* 情况2和3 */

{ if ( inside(s,clipboundary) ) /* 情况2 */ {

intersect(s,p,clipboundary,&i); outputvertex(i,outlength,outvertexlist); }

} /* 情况3无输出 */ s = p; /* 准备处理下一条边 */ } }

实验三 实现任意一种区域填充算法

【实验目的】

1、掌握多边形填充的基本原理；

2、掌握边界标志算法来实现多边形填充的思想。

【实验环境】

VC++6.0

【实验内容】

利用任意的一个实验环境，编制源程序，实现区域填充的描绘线算法

【实验原理】

这里讨论的区域指已经表示成点阵形式的填充图形，它是象素的集合。区域可采用内点表示和边界表示两种表示形式。在内点表示中，区域内的所有象素着同一颜色。在边界表示中，区域的边界点着同一颜色。区域填充指先将区域的一点赋予指定的颜色，然后将该颜色扩展到整个区域的过程。

区域填充算法要求区域是连通的，因为只有在连通区域中，才可能将种子点的颜色扩展到区域内的其它点。区域可分为4向连通区域和8向连通区域。4向连通区域指的是从区域上一点出发，可通过四个方向，即上、下、左、右移动的组合，在不越出区域的前提下，到达区域内的任意象素；8向连通区域指的是从区域内每一象素出发，可通过八个方向，即上、下、左、右、左上、右上、左下、右下这八个方向的移动的组合来到达。

四连通区域 八连通区域

图2.3.7 四连通区域和八连通区域

图2.3.8 区域的内点表示和边界表示

【算法实现步骤】

(1)初始化：堆栈置空。将种子点(x,y)入栈。

(2)出栈：若栈空则结束。否则取栈顶元素(x,y)，以y作为当前扫描线。

(3)填充并确定种子点所在区段：从种子点(x,y)出发，沿当前扫描线向左、右两个方向填充，直到边界。分别标记区段的左、右端点坐标为xl和xr。

(4)并确定新的种子点：在区间[xl，xr]中检查与当前扫描线y上、下相邻的两条扫描线上的象素。若存在非边界、未填充的象素，则把每一区间的最右象素作为种子点压入堆栈，返回第（2）步。

【实验程序】

区域填充的扫描线算法

typedef struct{ //记录种子点

intx;

int y；

} Seed;

void ScanLineFill4(int x,int y,COLORREF oldcolor,COLORREF newcolor)

{ int xl,xr,i;

bool spanNeedFill;

Seed pt;

setstackempty();pt.x =x; pt.y=y;stackpush(pt); //将前面生成的区段压入堆栈

while(!isstackempty())

{ pt = stackpop();

y=pt.y;

x=pt.x; while(getpixel(x,y)==oldcolor) //向右填充

{ drawpixel(x,y,newcolor);

x++;

}

xr = x-1; x = pt.x-1; while(getpixel(x,y)==oldcolor) //向左填充

{ drawpixel(x,y,newcolor);

x--;

}

xl = x+1;//处理上面一条扫描线

x = xl;

y = y+1;while(x<xr){ spanNeedFill=FALSE; while(getpixel(x,y)==oldcolor)

{ spanNeedFill=TRUE;

x++;

}

if(spanNeedFill)

{ pt.x=x-1;pt.y=y;

stackpush(pt);

spanNeedFill=FALSE;

}

while(getpixel(x,y)!=oldcolor && x<xr) x++;

}//End of while(i<xr)

//处理下面一条扫描线，代码与处理上面一条扫描线类似

x = xl;

y = y-2;while(x<xr)

{ ....

}//End of while(i<xr)}//End of while(!isstackempty())

}