图形学算法

习题1.1

5..证明等式gcd(m,n)=gcd(n,m mod n)对每一对正整数m,n都成立. Hint:

根据除法的定义不难证明:

?

如果d整除u和v, 那么d一定能整除u±v;

? 如果d整除u,那么d也能够整除u的任何整数倍ku.

对于任意一对正整数m,n,若d能整除m和n,那么d一定能整除n和r=m mod n=m-qn；显然，若d能整除n和r，也一定能整除m=r+qn和n。

数对(m,n)和(n,r)具有相同的公约数的有限非空集，其中也包括了最大公约数。故gcd(m,n)=gcd(n,r)

6.对于第一个数小于第二个数的一对数字,欧几里得算法将会如何处理?该算法在处理这种输入的过程中,上述情况最多会发生几次?

Hint:

对于任何形如0<=m

gcd(m,n)=gcd(n,m)

并且这种交换处理只发生一次.

7.a.对于所有1≤m,n≤10的输入, Euclid算法最少要做几次除法?(1次) b. 对于所有1≤m,n≤10的输入, Euclid算法最多要做几次除法?(5次) gcd(5,8)

习题1.2 1.(农夫过河)

P—农夫 W—狼 G—山羊 C—白菜 2.(过桥问题)

1,2,5,1

OpenGL图形API的配置与透视效果的3D图形显示

一、实验目的

能够灵活的运用OpenGL图形API函数，基于C++程序语言，自行设计出各种各样的计算机图形方案并调整不同的透视模型。

二、设计内容

运用所学的C＋＋语言图形程序设计的知识，学会配置OpenGL图形函数API，设计(1)在屏幕上显示基本3D图形；(2)设置图形的表面光照模型及投影变换模型；

三、实验要求

1.所有图形（例如球体，正方体）有清晰的轮廓。 2.学会设置图形表面的光照色彩以及投影变换模型。 3.尽可能采用高效的算法，以降低时间复杂性和空间复杂性。

四、实验报告

实验报告的内容：

实验名称、实验目的、实验任务、实验内容、实验过程描述（包括实验结果分析、实验过程遇到的问题及体会）。

实验报告的要求：

实验报告以文本或电子版形式递交，实验报告书写要求如下：

1.问题描述：包括实验名称、目的、内容，以简洁明了的叙述说明本次图形程序设计的任务和目标，程序的输入和输出要求以及程序的功能。

2.主要仪器设备：包括实验过程中所用的主要仪器设备、软件等。

3.实验过程描述：包括源程序的各个组成部分以及算法分析过程，图形演示结果等。 4.分析和体会：包括实验结果分析，测试、调试过程所遇

OpenGL图形API的配置与透视效果的3D图形显示

一、实验目的

能够灵活的运用OpenGL图形API函数，基于C++程序语言，自行设计出各种各样的计算机图形方案并调整不同的透视模型。

二、设计内容

运用所学的C＋＋语言图形程序设计的知识，学会配置OpenGL图形函数API，设计(1)在屏幕上显示基本3D图形；(2)设置图形的表面光照模型及投影变换模型；

三、实验要求

1.所有图形（例如球体，正方体）有清晰的轮廓。 2.学会设置图形表面的光照色彩以及投影变换模型。 3.尽可能采用高效的算法，以降低时间复杂性和空间复杂性。

四、实验报告

实验报告的内容：

实验名称、实验目的、实验任务、实验内容、实验过程描述（包括实验结果分析、实验过程遇到的问题及体会）。

实验报告的要求：

实验报告以文本或电子版形式递交，实验报告书写要求如下：

1.问题描述：包括实验名称、目的、内容，以简洁明了的叙述说明本次图形程序设计的任务和目标，程序的输入和输出要求以及程序的功能。

2.主要仪器设备：包括实验过程中所用的主要仪器设备、软件等。

3.实验过程描述：包括源程序的各个组成部分以及算法分析过程，图形演示结果等。 4.分析和体会：包括实验结果分析，测试、调试过程所遇

实 验 报 告

一、 实验目的

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坐标递增的顺序

实验六 9-7

一、实验题目

z-buffer算法的代表性案例是绘制三个相互交叉的红绿蓝条，如图9-85所示，请使用MFC编程实现。

二、实验思想

Z-Buffer算法建立两个缓冲器：

深度缓冲器，用以存储图像空间中每一像素相应的深度值，初始化为最大深度值（zs坐标）。

帧缓冲器，用以存储图像空间中的每个像素的颜色，初始化为屏幕的背景色。

① 帧缓冲器初始值置为背景色。

② 确定深度缓冲器的宽度、高度和初始深度。一般将初始深度置为最大深度值。 ③ 对于多边形表面中的每一像素（xs,ys），计算其深度值zs（xs,ys）。

④ 将zs（xs,ys）与存储在z缓冲器中该位置的深度值zBuffer（xs,ys）进行比较。 ⑤ 如果zs（xs,ys）≤zBuffer（xs,ys），则将此像素的颜色写入帧缓冲器，且用z（xs,ys）

重置zbuffer（xs,ys）。

三、实验代码

CZBuffer::~CZBuffer() { }

void CZBuffer::SetPoint(CPi3 p[],int m) {

P=new CPi3[m]; delete []P;

for(int i=0;i

void CZBuffer:

计 算 机 图 形 学

实 验 指 导

学号：1441901105 姓名：谢卉

书

实验一：图形的几何变换

实验学时：4学时 实验类型：验证 实验要求：必修 一、实验目的

二维图形的平移、缩放、旋转和投影变换（投影变换可在实验三中实现）等是最基本的图形变换，被广泛用于计算机图形学的各种应用程序中，本实验通过算法分析以及程序设计实验二维的图形变换，以了解变换实现的方法。如可能也可进行裁剪设计。 二、实验内容

掌握平移、缩放、旋转变换的基本原理，理解线段裁剪的算法原理，并通过程序设计实现上述变换。建议采用VC++实现OpenGL程序设计。 三、实验原理、方法和手段

1．

图形的平移

在屏幕上显示一个人或其它物体（如图1所示），用交互操作方式使其在屏幕上沿水平和垂直方向移动Tx和Ty，则有

x’=x+Tx y’=y+Ty

其中：x与y为变换前图形中某一点的坐标，x’和y’为变换后图形中该点的坐标。其交互方式可先定义键值，然后操作功能键使其移动。

2．

图形的缩放

在屏幕上显示一个帆船（使它生成在右下方），使其相对于屏幕坐标原点缩小s倍（即x方向和y方向均缩小s倍）。则有：

x’=x*s

湖北大学2012—2013学年度第二学期课程考试 试题纸（第 1 页 共 6 页）

1. 显示器1024×768分辨率，256灰度的图象，至少需要_____768423________字节（byte）保存128×100大小的图像，若显示同样分辨率的真彩色（2）图象，则至少需要_____________字节保存。 2.对于平面上任意一点p(xp,yp),代入半径为r的圆方程中，若xp+yp-r<0，则p在圆内，若xp+yp-r>0，则p在圆外。 3.计算机图形所研究的基本图形算法主要考虑__________和___________作为重要因数。 4.比例变换可以改变图形的___大小__________和___形状__________。 5.反映曲线变化方向趋势的属性是___________,反映曲线变化的平缓度是___________. 6. 线段裁剪的裁剪窗口定义为__________和__________。 7. 线宽的绘制时可依据直线的斜率选择__线刷子________和___方形刷子_______。 8. 字符的型状存储方式有__矢量________和__标量________。 9. (x, y, z)点的齐次坐标是_(hx, hy, hz，h)_________,

题目：

武汉工业学院

《计算机图形学》课程设计

绘制三次Bezier曲线，三次B样条曲线和Cantor图

指导老师：刘文涛 姓 名：庞璐 学 号：070505129

院 （系）：计算机与信息工程系

专 业：软件工程

完成日期： 2010年1 月4 日

一．课题题目介绍

设计任务9：

1）给定下图所示的四个控制点：P0=(228,456），P1=(294,247），P2=(452,123），P3=(705,197）。分别绘制三次Bezier曲线和三次B样条曲线。

2）使用VC编程，在窗口中一次绘制n＝0～5的所有Cantor

图。

二．整体功能及设计

1）主模块：Bezier，B样条，cantor集算法的实现。 2）响应模块:a.Bezier，B样条，cantor集的鼠标响应；

b.Bezier，B样条，cantor集的菜单和提示对话框响应。 c. Bezier，B样条，cantor集的快捷按钮响应。

3）附加功

计算机图形学C语言图形程序设计基础

第三章C语言图形程序设计基础 3.1屏幕显示模式和坐标系 1.文本模式： DEF在屏模上只能显示文本的显示模式 历史原因 Turbo C的默认的显示模式是文本模式。

2.图形模式和点坐标 图形模式： DEF在屏幕上显示图形的方式，称为图形模式。 点坐标：屏幕是由像素点组成的，在图形模式下，屏 幕上每个像素的显示位置用点坐标来描述。

在图形模式下,以屏幕的左上角为坐标原点(0,0)水 平方向为x轴，垂直方向为y轴(0,0)

Max x

(0,0)

799

(10,4)

Max y

599

例：一个分辨率为800*600的分辨率的显示 屏(800列，600行)

3.图形系统的初始化

一个简单的图形程序 #include “graphics.h” // 图形函数库 #include “stdio.h” //标准输入输出函数库 #include

main() { int gdriver,gmode; detectgraph(&gdriver,&gmode) ; if(gdriver<0) exit(1) ;

“conio.h” //控制台输入

实验五：图形变换

一、实验目的：

1、掌握图形变换的基本方法。

2、初步掌握映射菜单消息和捕获键盘消息的方法。

二、实验内容及要求：

1、 2、 3、

以三角形为例，使用Visual C＋＋实现二维图形的平移、旋转和缩放功能。 每人单独完成实验。

按要求撰写实验报告，写出实验心得，并在实验报告中附上程序的核心算法代码。

三、实验设备：

微机，Visual C++6.0

四、实验内容和步骤：

1、 打开VC，新建一个MFC Appwizard项目，选择创建单文档工程（SDI工程）。假设工程名为

Transform。如图1和图2所示。

图1

图2

2、 在图2的界面上点击Finish，完成工程的创建。 3、 在TransformView.h文件中，加入如下代码： public: CPoint Pt[3]; //存储三角形的三个顶点 float dAngle; //存储三角形旋转的角度

4、 在类CTransformView的构造函数中定义三角形的三个顶点的初始坐标和dAngle的初值，代码如

下；

CTransformView::CTransformView() {

// TODO: add construction code here P