计算机图形学

读书报告

（计算机图形学的发展前景）

专 业： 数字媒体技术 班 级： 1306班 姓 名： 燕旱雨

学 号： （2013100661）

一、计算机图形学的基本知识

计算机图形学是研究怎样用计算机表示、生成、处理、和显示图形的一门学科，在计算机辅助设计、地理信息系统、计算机游戏、计算机动画、虚拟现实等方面有着广泛的应用。

计算机图形 用计算机表示、生成、处理和显示对象。从范围上说，计算机图形包括了山、水、虫、水、人等客观世界存在的所有物体甚至意识形态；从内容上说，计算机图形学也已不仅仅是物体的形状，还包含了物体的材质、运动等各种属性。因此，计算机图形是储存在计算机内部的物体的坐标、纹理等各种属性。

数字图形 由规则排列的像素上的颜色值组成的二维数组。数字图像可能由数码相机、摄像机或者其成像设备如CT机从外界获取，也可能在计算机上通过计算机图形装化而成。

除了计算机图形和数字图像外，物体在计算机内部的表达还可以是符号或抽象模型、图像中的的一个区域等，研究物体的这些在计算机内部的表达及表达间的装换形成了和计算机图形学密切相关的几个重要学科。

图像处理 将客观世界中原来存在的物体的影像处理成新的数字化图像的相关技术，如CT扫描，人脸识别，X射线探伤等。

模式识别 对所输入的图像进行分析和识别，找出其中蕴含的内在联系或抽象模型，如邮政分拣，人脸识别，地貌地形识别等。

计算几何 也称为计算机辅助几何设计，是研究几何模型和数据处理的学科，探究几何形体的计算机表示、分析和综合，研究如何灵活、有效地建立几何形体的数学模型以及在计算机中更好的储存和管理这些模型数据。

计算机视觉 模拟人的视觉机理使计算机获得与人类相似的获取和处理视觉信息能力的学科

二、计算机图形学的发展方向

1、智能CAD

CAD 的发展也显现出智能化的趋势，就大多数流行的CAD软件来看，主要功能是支持产品的后续阶段一一工程图的绘制和输出，产品设计功能相对薄弱， 利用AutoCAD最常用的功能还是交互式绘图，如果要想进行产品设计， 最基本的是要其中的AutoLisp语言编写程序，有时还要用其他高级语言协助编写，很不方便。而新一代的智能CAD 系统可以实现从概念设计到结构设计的全过程。智能CAD的另一个领域是工程图纸的自动输入与智能识别，随着CAD技术的迅速推广应用，各个工厂、设计院都需将成千上万张长期积累下来的设计图纸快速而准确输入计算机，作为新产品开发的技术资料。多年来，CAD 中普遍采用的图形输入方法是图形数字化仪交互输入和鼠标加键盘的交互输入方法．很难适应工程界大量图纸输入的迫切需要。因此， 基于光电扫描仪的图纸自动输入方法已成为国内外CAD工作者的努力探索的新课题。但由于工程图的智能识别涉及到计算机的硬件、计算机图形学、模式识别及人工智能等高新技术内容，使得研究工作的难点较大。工程图的自动输入与智能识别是两个密不可分的过程，用扫描仪将手绘图纸输入到计算机后，形成的是点阵图象。CAD 中只能对矢量图形进行编辑， 这就要求将点阵图象转化成矢量图形．而这些工作都让计算机自动完成．这就带来了许多的问题．如① 图象的智能识别；② 字符的提取与识别；③ 图形拓扑结构的建立与图形的理解；④实用

化的后处理方法等等。国家自然科学基金会和863计划基金都在支持这方面的研究， 国内外已有一些这方面的软件付诸实用，如美国的RVmaster，德国的VPmax， 以及清华大学，东北大学的产品等。但效果都不很理想．还未能达到人们企盼的效果。

2、美术与设计

计算机美术的发展

19xx年．美国的Ben ．Laposke用模拟计算机做的波型图《电子抽象画》预示着电脑美术的开始(比计算机图形学的正式确立还要早)。计算机美术的发展可分为三个阶段： 代表作品：19xx年Wiuiam Ferrter为波音公司制作的人体工程学实验动态模拟．模拟飞行员在飞机中各种情况；19xx年Kenneth Know Iton的打印机作品《裸体》。19xx年日本GTG小组的《回到方块》。

? 伦敦第一次世界计算机美术大展一“控制论珍宝 (Cybernehic Serendipity1为标志，进入世界性研究与应用阶段；计算机与计算机图形技术逐步成熟， 一些大学开始设置相关课题， 出现了一些CAD应用系统和成果， 三维造型系统产生并逐渐完善。代表作品：19xx年美国IBM 研究所Richerd Voss设计出分形山(可到网站“分形频道hrtp：ttfracta1．126．tom 中查找有关“分形”的知识)

? 个人计算机图形系统逐渐走向成熟， 大批商业性美术(设计)软件面市； 以苹果公司的MAC 机和图形化系统软件为代表的桌面创意系统被广泛接受，CAD成为美术设计领域的重要组成部分。代表作品：19xx年Jefrey Shaw的交互图形作品“易读的城市f The legible city) 。 计算机设计学(Computer Designics)

包括三个方面：环境设计(建筑、汽车)、视觉传达设计(包装)、产品设计。

3、计算机动画艺术

计算机动画的简介

计算机动画技术的发展是和许多其它学科的发展密切相关的。计算机图形学、计算机绘画、计算机音乐、计算机辅助设计、电影技术、电视技术、计算机软件和硬件技术等众多学科的最新成果都对计算机动画技术的研究和发展起着十分重要的推动作用50年代到60年代之间，大部分的计算机绘画艺术作品都是在打印机和绘图仪上产生的。一直到60年代后期，才出现利用计算机显示点阵的特性，通过精心地设计图案来进行计算机艺术创造的活动。

电影特技

计算机动画的一个重要应用就是制作电影特技 可以说电影特技的发展和计算机动画的发展是相互促进的。19xx年由著名的计算机动画专家塔尔曼夫妇领导的MIRA 实验室制作了一部七分钟的计算机动画片《相会在蒙特利尔》 再现了国际影星玛丽莲?梦露的风采。19xx年，美国电影《谁陷害了兔子罗杰》 (Who Framed Roger Rabbit?)中二维动画人物和真实演员的完美结合，令人瞠目结舌、叹为观止 其中用了不少计算机动画处理。19xx年美国电影《终结者II：世界末日》展现了奇妙的计算机技术。此外，还有《侏罗纪公园》(Jurassic Park)、《狮子王》、《玩具总动员》(Toy Story)等。

计算机动画的应用领域十分宽广 除了用来制作影视作品外， 在科学研究、视觉模拟、电子游戏、工业设计、教学训练、写真仿真、过程控制、平面绘画、建筑设计等许多方面都有重要应用，如军事战术模拟

4、科学计算可视

科学计算的可视化是发达国家八十年代后期提出并发展起来的一门新兴技术，它将科学计算过程中及计算结果的数据转换为几何图形及图象信息在屏幕上显示出来并进行交互处理，成为发现和理解科学计算过程中各种现象的有力工具。

19xx年2月英国国家科学基金会在华盛顿召开了有关科学计算可视化的首次会议。会议一致认为“将图形和图象技术应用于科学计算是一个全新的领域” 科学家们不仅需要分析由计算机得出的计算数据，而且需要了解在计算机过程中数据的变化。会议将这一技术定名为“科学计算可视化(Visualization in Scientific Computing)”。科学计算可视化将图形生成技术图象理解技术结合在一起， 它即可理解送入计算机的图象数据．也可以从复杂的多维数据中产生图形。它涉及到下列相互独立的几个领域：计算机图形学、图象处理、计算机视觉、计算机辅助设计及交互技术等。科学计算可视按其实现的功能来分， 可以分为三个档次：(1)结果数据的后处理；(2)结果数据的实时跟踪处理及显示；(3)结果数据的实时显示及交互处理。

5、虚拟现实技术

“虚拟现实”(Virtual Reality)- 词是由美国喷气推动实验室(VPL)的创始人拉尼尔(Jaron Lanier)首先提出的 在克鲁格(Myren Kruege)70年代中早期实验里．被称为 人工现实”(Artificial reality)；而在吉布森(William Gibson)l984 年出版的科幻小说Neuremanccr里，又被称为“可控空间”(Cyberspaee)。虚拟现实， 也育人称之为虚拟环境(Virtual Environment)是美国国家航空和航天局及军事部门为模拟而开发的一门高新技术 它利用计算机图形产生器，位置跟踪器，多功能传感器和控制器等有效地模拟实际场景和情形，从而能够使观察者产生一种真实的身临其境的感觉虚拟环境由硬件和软件组成，硬件部分主要包括：传感器(Sensors)、印象器(Efeeter)和连接侍感器与印象器 产生模拟物理环境的特殊硬件。利用虚拟现实技术产生虚拟现实环境的软件需完成以下三个功能：建立作用器(Actors)以及物体的外形和动力学模型：建立物体之间以及周围环境之间接照牛顿运动定律所决定的相互作用；描述周围环境的内容特性

虚拟现实，是指由计算机实时生成一个虚拟的三维空间。这个空间可以是小到分子、原子的微观世界，或是大到天体的宏观世界，也可以是类似于真实社会的生活空间。它可以乱真，所以又称之为虚拟现实。用户可以在这个三维空间中“自由”地走动，随意地观察，并可通过一些设备与其中的虚拟景物进行交互操作。交互是多通道的，自然的，用以传递信息的可以是一个手势、一个眼神，也可以是一个表情等。在此环境中，用户看到的是由计算机生成的逼真图像，听到的是虚拟环境中的声音，身体感受到的是虚拟环境所反馈的作用力，由此产生身临其境的感觉。

虚拟现实技术主要研究用计算机模拟（构造）三维图形空间，并使用户能够自然地与该空间进行交互。它涉及很多科学的知识，对三维图形处理技术的要求特别高。简单的虚拟现实系统早在70年代便被应用于军事领域，训练驾驶员。80年代后随着计算机软硬件技术的提高，它也得到重视并迅速发展。它已在航空航天、医学、教育、艺术、建筑等领域得到初步的应用。例如，19xx年7月，美国航天局的旅居者号火星车着陆距地球约1.9亿公里的火星。这辆在火星表面缓慢爬行的小车中并没有驾驶员，它是由地球上的工程师通过虚拟现实系统操纵的。

虚拟现实应用

虚拟现实技术主要应用于脑外科规划的双手操作空间接口工具、虚拟环境用于恐高症治疗、虚拟风洞、封闭式战斗作战训练器、虚拟现实技术在建筑设计中应用、地理信息系统（地理信息系统是建立在地理图形之上的关于人口、矿藏、森林、旅游等资源的综合信息管理系统。它在发达国家中已得到广泛应用，我国也对其开展了广泛的研究与应用。在地理信息系统中，计算机图形学技术被用来产生高精度的各种资源的图形，包括地理图、地形图、森林分布图、人口分布图、矿藏分布图、气象图、水资源分布图等等。地理信息系统为管理和决策者提供非常有效的支持。）

总之．虚拟现实技术是一门多学科交叉和综合集成的新技术。因此， 它的发展将取决于相关科学技术的发展和进步 虚拟现实技术最基本的要求就是反映的实时性和场景的真实性。但一般来说，实时性与真实性往往是相互矛盾的。

电脑用户界面

用户界面是计算机系统中人与计算机之间相互通讯的重要组成部分。八十年代以WIMP(窗口、图符、菜单、鼠标)为基础的图形用户界面(GUD极大地改善了计算机的可用性、可学性和有效性，迅速代替了命令行为代表的字符界面，成为当今计算机用户界面的主流。以用户为中心的系统设计思想．增进人机交互的自然性，提高人机交互的效率和带宽是用户界面的研究方向。于是提出了多通道用户界面的思想，它包括语言、姿势输入、头部跟踪、视觉跟踪、立体显示、三维交互技术、感觉反馈及自然语言界面等。可以这样说人体的表面就是人机界面。人体的任何部分都应成为人机对话的通道。虚拟现实显示是关键所在，这不仅要求软件来实现，更主要的是硬件上的实现。概括起来虚拟现实的人机交互通道可分为两个方面：主要的感觉通道和主要作用通道。 总结

计算机图形学的发展迅速，如今已经成为了一门学科走进了我们的世界，走在了科学的前端。计算机图形学已经应用到了各个领域，在我们的生活中到处可见，使我们的生活变得绚丽多彩，给我的生活带来很大的便利，不仅提高人们物质生活水平，同时也带来了精神世界的享受。只是计算机图形学发展的迟，还有好多没有好多领域发展不成熟，需要慢慢去完善，所以计算机图形学有很大的发展前景，而且在人们的生活中会扮演很重要的作用。

 

第二篇：计算机图形学试验报告

信科0306班

计算机图形学实验报告 指导老师：陈明

计算机图形学实验报告

一、实验目的与要求

计算机图形学是数学学院信息与计算科学专业学生的重要专业课, 计算机图形学是随着计算机及外围设备而产生和发展起来的，它是近代计算机科学与雷达、电视及图像处理技术的发展汇合而产生的硕果。在造船、航空航天、汽车、电子、机械、土建工程、影视广告、地理信息、轻纺化工等领域中的广泛应用，推动了这门学科的不断发展。

通过<<计算机图形学>>的实验课程，要求学生掌握计算机图形学的一些主要算法并编程实现。

二、实验内容

计算机图形学的算法，并用ｃ语言编写绘图程序。主要内容包括线段、园、区域填充、线型线宽、字符、裁剪、等基本图形生成算法；样条、Bezier、等常用曲线的生成算法；Coons曲面、Bezier曲面、B样条曲面等常用曲面的生成算法。

三、实验说明

3.1、头文件声明

#include "Conio.h"

#include "graphics.h"

#include "stdio.h"

#include "math.h"

#define closegr closegraph

3.2、图形界面的初始化

void initgr(void) /* BGI初始化 */

{ int gd = DETECT, gm = 0; /* 和gd = VGA,gm = VGAHI是同样效果 */

registerbgidriver(EGAVGA_driver);/* 注册BGI驱动后可以不需要.BGI文件的支持运行 */ initgraph(&gd, &gm, "");

}

3.2、数据类型的声明

1、边的数据结构声明

struct Edge /*边的结构*/

{int ymax;

float x,delatx;

struct Edge *nextEdge;};

2、点的数据结构声明

A、链式结构

struct point /*点的结构*/

{int x,y;

struct point *next; };

B、孤立节点结构

struct point /*点的结构*/

{int x,y;

}

1

3、多边形的数据结构

typedef struct

{int pointNum;

Point *vertices;

}Polygon;

4、枚举类型Boolean的数据

typedef enum {False,True}Boolean;

5、堆栈定义:

typedef struct

{Span *top;

Span *base;

int stacksize;

}SqStack;

6、待处理区段的三元组定义为:

typedef struct

{int y;

int xLeft;

int xRight;

}Span;

7、矩形的数据结构

typedef struct

{int xmin;int xmax;int ymin;int ymax;}Rectangle;

四、算法分析与程序设计

4.1、直线的生成

4.1.1、生成直线的DDA算法思想

1、算法思想

生成直线的DDA算法思想是源用初中直线的方程得出来的，而生成直线的中点算法是通过将DDA算法的方程式改为隐函数形式，然后通过与中点的比较确定该取的像素，绘制图线。

2、程序代码

生成直线段的DDA算法参见教材程序3.1。

3、程序运行与算法分析

算法分析，DDA算法采用了浮点加法，浮点运算在输出时需要取整，这两个方面都影响了DDA的效率

4.1.2、生成直线的中点算法

1、算法思想

中点算法主要是利用椭圆的正负划分性，利用已知或以求出的点，根据递推关系来判断下一个点的位置。

2、程序代码

生成直线的程序代码参见教材程序3.2。

3、程序过程及算法分析

中点算法有效地消除了DDA浮点运算效率低下的问题，将直线的斜率m转化为可加的数，然后通过中点来确定要选择的点，这样使得中点算法的效率大大提高，使之成为被图形软件广泛采用的算法之一。

2

4.2、圆弧的生成

4.2.1生成圆弧的中点算法

1、算法思想

为了生成圆弧，只需要计算出从x=0到x=y分段内的像素点即可，其余的像素位置利用圆的八对称性即可得出。

设圆的半径是R，从初始坐标点（0，R）开始递推，假设已计算出象素P（x,y），那么，下一个与圆弧最近的像素只能是正右方的P1(x+1,y)，或右下方的P2（x+1,y-1）两者之一。令M为P1和P2的中点，易知M的坐标为（x+1,y-1/2）。显然，若M在圆内，则P1离圆弧近，应取为下一个像素；否则应取P2。

判断M位置的递推公式如下：

di?0,di?1?di?2xi?3;di?0,di?1?di?2(xi?yi)?5.

5其中d0??R4

2、程序代码

A、/*根据圆的八对称性声明如下函数*/

void CirclePoints(int x,int y,int color) putpixel(xo+y,yo-x,color);

{putpixel(xo+x,yo+y,color); putpixel(xo+x,yo-y,color);

putpixel(xo+y,yo+x,color); putpixel(xo-x,yo-y,color);

putpixel(xo-y,yo+x,color); putpixel(xo-y,yo-x,color);

putpixel(xo-x,yo+y,color); }

B、生成圆弧的中点算法

void MidPointCircle(int radius,int color)参见教材程序3.4。

C、可以改进递推方程和利用差分方法来消除浮点运算和乘法运算，改进后的程序见教材程序3.5。

3、程序运行与算法分析

由于设备坐标点（0，0）在屏幕的左上角，故需要平移原点坐标，取原点坐标xo =300, yo =250, 即用如下两个语句：#define xo 300,#define yo 250。

4、线宽处理（移动刷子方法）：

只要将程序中CirclePoints(int x,int y,int color)函数中所有的putpixel换成putpixels(int x,int y,int color,int n)并修改相应参数即可通过如下代码产生宽图元：

void putpixels(int x,int y,int color,int n)

{ int i,j;/*移动刷子*/

for(i=-n/2;i<=n/2;i++)

for(j=-n/2;j<=n/2;j++)

putpixel(x+j,y+i,color);

}

调用MidPointCircle1(200,2,10)画改变线宽后的圆弧，可看出，在切线水平或竖直处宽度最小，而当斜率向?1变化时，宽度变大，在m?1处，宽度达到最大。

运行后的图形基本符合预期效果，但是改进后的中点算法和未改进的算法在画出的实际图形方面并没有明显的差别。

4.2.2、生成圆弧的多边形迫近法

3

1、算法思想：

当一个内接正多边形的边数足够多时，该多边形可以和圆任意接近。利用圆的极坐标公式，并给定正多边形的边所对应的圆心角的度数?，就可以算出圆的内接正多边形各顶点的递推公式。给定圆弧和内接正多边形之间的最大逼近误差DELTA，可算出max??2*arccosradius?DELTA2?,n?,n为多边形的边数，利用顶点递推公式算出radius?

多边形的顶点之后，利用C语言的line函数依次连接各顶点，即可画出近似圆弧的正多边形。

2、程序代码：

A、多边形的绘制函数

void CircleToPolygonDraw(int radius,int color)

{ int i=0;

Polygon *polygon=NULL;

CircleToPolygon(radius,polygon);

setcolor(color);

for(i=0;i<polygon->pointNum-1;i++)

{ line(xo+polygon->vertices[i].x, yo+polygon->vertices[i].y,xo+polygon->vertices[i+1].x, yo+polygon->vertices[i+1].y);}

line(xo+polygon->vertices[i].x, yo+polygon->vertices[i].y,

xo+polygon->vertices[0].x, yo+polygon->vertices[0].y);

}

B、多边形迫近法生成多边形的程序见教材程序3.8。

3、程序运行与算法分析

给定最大逼近误差DELTA=10.0，即#define DELTA 10.0。计算多边形顶点的程序返回值为一个Polygon类型的指针，其中C语言中采用弧度制，在计算多边形边数时n=(int)(2*3.1415926/alfa+0.5)，考虑到舍入误差，故加上0.5。

调用CircleToPolygonDraw(50,5)绘制。由大至小不断更改最大逼近误差DELTA，可以看到多边形逐步向圆逼近，当DELTA=1.0时，多边形也就相当于一个圆弧了。

4.2.3、生成圆弧的正负法

1、算法思想：

正负法是利用平面曲线划分正负区域来直接生成圆弧的方法。圆弧是易画曲线，可以用正负法绘制。只考虑中心在原点的圆弧在第一象限内的1/4圆弧，用EllipsePoints函数即可生成其他部分。对圆的方程F(x,y)=0,当点(x,y)在圆内时，有F(x,y)<0;当点(x,y)在圆外时，F(x,y)>0。初始定向为(0,radius)－>(1,radius)。

前进递推关系式如下：

1、F(xi,yi)?0,xi?1?xi,yi?1?yi?1

2、F(xi,yi)?0,xi?1?xi?1,yi?1?yi

判别式的递推公式如下：

?F(xi,yi)?2yi?1,F(xi,yi)?0F(xi?1,yi?1)??,初值F(x1,y1)?1 F(x,y)?2x?1,F(x,y)?0iiiii?

2、程序代码

A、据圆的对称性，声明函数如下：

4

void EllipsePoints(int x,int y,int color)

{putpixel(xo+x,yo+y,color);

putpixel(xo-x,yo+y,color);

putpixel(xo+x,yo-y,color);

putpixel(xo-x,yo-y,color);

}

B、正负法生成圆弧

正负法生成圆弧的程序见教材程序3.9

3、程序运行与算法分析

用PositiveNegativeArc(150,4)画出圆弧。对正负法生成的圆弧和中点算法生成的圆弧做一对比，可看出，正负法生成的圆弧顶端突出了一点，就是初始定向所确定的线段。

4、正负法生成圆弧的线宽处理（象素复制方法）：

void putpixelsh(int x,int y,int color,int n) void putpixelx(int x,int y,int color,int n) {int i;/*竖直方向上象素复制*/ {int i;/*水平方向上象素复制*/ for(i=-n/2;i<=n/2;i++) for(i=-n/2;i<=n/2;i++)

putpixel(x,y+i,color); putpixel(x+i,y,color);

} }

void EllipsePoints(int x,int y,int color,int n)/*y=x上方,应竖直方向复制象素*/

{putpixelsh(xo+x,yo+y,color,n);

putpixelsh(xo-x,yo+y,color,n);

putpixelsh(xo+x,yo-y,color,n);

putpixelsh(xo-x,yo-y,color,n);

}

void EllipsePointx(int x,int y,int color,int n)/*y=x下方,应水平方向复制象素*/

{putpixelx(xo+x,yo+y,color,n);

putpixelx(xo-x,yo+y,color,n);

putpixelx(xo+x,yo-y,color,n);

putpixelx(xo-x,yo-y,color,n);

}

void PositiveNegativeArc(int radius,int y--;

color,int n) }

else /* 线宽处理后的正负法生成圆弧 */

{int x,y,d; {d=d+2*x+1;

x=0; x++;

y=radius; }

EllipsePoints(x,y,color,n); EllipsePoints(x,y,color,n);

x=1; } /*end of if*/

EllipsePoints(x,y,color,n); else/*y=x下方*/

d=1; {

while(y>=0) if(d>=0)

{d=d-2*y+1; {if(y>x)/*y=x上方*/

{ y--;

if(d>=0) }

{d=d-2*y+1; else

5

{d=d+2*x+1; }

x++; }/*end of while*/

} }/*end*/

EllipsePointx(x,y,color,n);

调用PositiveNegativeArc(150,4,10) 改变线宽后的圆弧，可看出，在切线水平或竖直处宽度最大，而当斜率向?1变化时，宽度变小，在m?1处，宽度达到最小。

4.3、椭圆弧的生成

4.3.1、中点算法生成椭圆弧

1、算法思想

生成椭圆的中点算法思想和生成圆弧的中点算法思想和基本处理方法基本一致，不过由于椭圆的方程更加复杂，故计算过程更加复杂。

相对于圆，椭圆只有两条对称轴，对于中心在的椭圆(x0,y0)，已知其中一点(x,y)，可以得到椭圆上的四个点，为了画出椭圆上所有的像素，只须扫描转换四分之一椭圆弧即可。因此，只要扫描转换第一象限的椭圆弧即可。在第一象限的椭圆弧上，切线为-1的直线和椭圆的切点将椭圆分成两部分，必须对这两部分进行分别讨论。

算法的其他思想与生成圆弧的中点算法基本一致（参见教材3.3.3小节）。

2、程序代码

生成椭圆弧的中点算法主要程序如下：

void EllipsePoints(int x0,int y0,int x,int {if(d<=0)/* 取像素E*/

y,int color) d+=4*sqb*(2*x+3);

else /*绘椭圆弧上对称的四个像素*/

{ putpixel(x0+x,y0+y,color); /*取像素SE*/ putpixel(x0-x,x0+y,color); {d+=4*sqb*(2*x-3)-8*sqa*(y-1);

putpixel(x0+x,y0-y,color); y--; }

putpixel(x0-x,y0-y,color); x++;

} EllipsePoints(x0,y0,x,y,color); void MidPointEllipse(int x0,int y0,int }

a,int b,int color) /*生成第一象限的下半部分椭圆弧*/

x=a; y=0; /*椭圆的中心在（x0，y0），a,b分别为

两个半轴的长度*/ d=4*(sqa-a*sqb)+sqb;/*初始化*/

{ long sqa,sqb,d=0; EllipsePoints(x0,y0,x,y,color);

int x,y,xp,yp; while(y<yp)

sqa=a*a; {if(d<=0)

sqb=b*b; d+=4*sqa*(2*y+3);

xp=(int)(0.5+(float)sqa/sqrt((float)(sqa+sqb))); else

yp=(int)(0.5+(float)sqb/sqrt((float)(sqa+sqb))); {d+=4*sqa*(2*y+3)-8*sqb*(x-1);

x--; } /*生成第一象限的上半部分椭圆弧*/

x=0;y=b; y++;

EllipsePoints(x0,y0,x,y,color); d=4*(sqb-sqa*b)+sqa;/*初始化*/

EllipsePoints(x0,y0,x,y,color); }

while(x<=xp) }

4.3.2、正负法生成椭圆弧

6

1、算法思想

由于椭圆也具有正负划分性，且二阶连续，满足易画曲线的特性，故可以运用正负法，采取类似正负法生成圆弧的算法生成椭圆。

算法的原理参见教材3.4.1以及前面4.2。

2、程序代码

void MidPointEllipse(int x0,int y0,int a,int {d+=4*squareb*(2*x+3)-8*squarea*(y-1); b,int color) y--;

} /*假定椭圆的中心在(x0,y0)*/

x++; /*a和b分别为两个半轴的长度*/

{long x,y,d,xP,yP,squarea,squareb; EllipsePoints(x0,y0,x,y,color); squarea=a*a; }

squareb=b*b; x=a; y=0;

d=4*(squarea-a*squareb)+squareb; /*计算分界点P*/

xP=(0.5+(float)squarea/sqrt((float)(squarea+s EllipsePoints(x,y,color);

quareb))); while(y<yP)

yP=(0.5+(float)squareb/sqrt((float)(squarea+s {if(d<=0)

quareb))); d+=4*squarea*(2*y+3);

else /*生成第一象限内的上半部分椭圆弧*/

x=0; y=b; {d+=4*squarea*(2*y+3)-8*squareb*(x-1); d=4*(squareb-squarea*b)+squarea; x--;

EllipsePoints(x,y,color); }

while(x<=xP) y++;

{if(d<=0) EllipsePoints(x,y,color);

d+=4*squareb*(2*x+3); }

else }

4.4、线型与线宽控制

4.4.1、线宽控制

1、算法思想

通过复制像素得方法使图元得宽度得到调整，通过控制像素输出控制线形，两个元素放在一起就可以控制图元的大小和形式。

2、程序代码

void putpixels(int x,int y,int color,int n)

{ int i,j;

for(i=-n/2;i<n/2;i++)

for(j=-n/2;j<n/2;j++)

putpixel(x+i,y+j,color) ;

}

4.4.2、线型控制

1、算法思想

线型控制采用了一个屏蔽器，通过定义一个由0、1构成的数组，当前像素对应的数组元素为1时显示该像素，为0时不显示。用这样的数组的数组控制线型时，线型可以任何整数为周期进行重复。

2、程序代码

void putpixelt(int x,int y,int color,int i)

7

{int a[8]={1,1,1,1,0,0,0,0};

if(a[i%8])putpixel(x,y,color);

4.5、扫描转换

4.5.1、扫描线算法扫描多边形

1、算法原理

扫描线算法的基本思想是将扫描转换多边形的问题分解到一条条扫描线上来考虑。其填充过程为求扫描线与多边形各边的交点，所求的交点按横坐标从小到大排序，将交点两两配对，并填充每一区段（其原理参见教材4.2.2）。

扫描线算法描述如下：

（1） 建立边的分类表ET；

（2） 将扫描线纵坐标y的初值为ET中非空元素的最小序号；

（3） 置活化边表AEL为空；

（4） 执行下列步骤直至ET和AEL都为空；

A、 如果ET中的第y类非空，则将其中的所有边取出并插入AEL中，在插入过

程忠进行排序；

B、 对AEL中的边两两配对，将每对边中x坐标按规则取整，获得有效的填充区

段，再填充；

C、 将当前扫描线纵坐标y值递增1，即y=1；

D、 将AEL中满足y=ymax边删去；

E、 对AEL中剩下的每一条边的x递增deltax，即x=x+deltax；

2、程序代码

setcolor(14); struct point *creat() /*顺时针输入顶点*/

{ struct point *h,*p,*r=NULL; q=h;

int x,y; sx=q->x;

sy=q->y; printf("顺序输入顶点坐标");

scanf("%d,%d",&x,&y); q=q->next;

h=NULL; while (q!=NULL)

while (x!=0) {line(sx,sy,q->x,q->y);

{ p=(struct point *)malloc(sizeof (struct sx=q->x;

point)); sy=q->y;

p->x=x; q=q->next;

p->y=y; }

if (h==NULL) h=p; q=h;

else r->next=p; line(sx,sy,q->x,q->y);

r=p; }

scanf("%d,%d",&x,&y); int vertymax(int x1,int x2)

} /*求边的上端点的y坐标*/

r->next=NULL; {int x;

return(h); if(x1>x2) x=x1;

} else x=x2;

return x; /*画出多边形边*/

void draw(struct point *h) }

{ int sx,sy; int vertymin(int x1,int x2)

struct point *q; /*求边的下端点的y坐标*/

8

{float x;

if(x1<x2) x=x1; else x=x2; return x; }

main() {

struct Edge *p,*s,*r,*net[480],*Ael=NULL; struct point *q,*t,*head; int i,y,m=0; initgr();

head=creat(); draw(head);

/*转化为边的结构*/ q=head; t=head; for(i=0;i<480;i++) net[i]=NULL;

while(q!=NULL&&q->next!=NULL)

{p=(struct Edge*)malloc(sizeof(struct Edge));

p->ymax=vertymax(q->y,q->next->y); if(q->y>q->next->y)p->x=q->next->x; else

p->x=q->x;

p->delatx=(float)(q->x-q->next->x)/(float)(q->y-q->next->y);

p->nextEdge=NULL; /*定义一个新的节点边结构节点p*/ i=vertymin(q->y,q->next->y); if(net[i]==NULL&&i<=480) net[i]=p; else

{s=net[i];

while(s->nextEdge!=NULL)s=s->nextEdge; s->nextEdge=p; } q=q->next; } q=head;

while(q->next!=NULL)q=q->next; t=q;q=head;

p=(struct Edge *)malloc(sizeof(struct Edge));

p->ymax=vertymax(q->y,t->y); if(q->y>t->y) p->x=t->x;

9

else p->x=q->x;

p->delatx=(float)(q->x-t->x)/(float)(q->y-t->y);

p->nextEdge=NULL; /*定义一个新的节点边结构节点p */ i=vertymin(q->y,t->y);

if(net[i]==NULL&&i<=480) net[i]=p;

else{s=net[i];

while(s->nextEdge!=NULL)s=s->nextEdge; s->nextEdge=p; }

printf("\n边的结构:"); for(i=0;i<480;i++) if(net[i]!=NULL) {r=net[i];

while(r!=NULL) {m++;

printf("\nnet[%d]:%d,%f,%f",i,r->ymax,r->x,r->delatx);

r=r->nextEdge; } }

/*m表示边的分类表中边的个数*/ printf("\n多边形的边数:m=%d",m); y=0;

while(net[y]==NULL)y++;/**/ do{

if(net[y]!=NULL)/*排序插入*/ {/*全部插入*/

while(net[y]!=NULL) { p=net[y];

if(Ael==NULL) { Ael=p;

net[y]=p->nextEdge; Ael->nextEdge=NULL; } else

{s=Ael;

if(net[y]->x>s->x)

{while(net[y]->x>s->x&&s!=NULL) {r=s;

s=s->nextEdge; s=Ael;

} while(s!=NULL)/*配对，获取有效填充 r->nextEdge=p; 区段，并填充*/

net[y]=p->nextEdge;

p->nextEdge=s; {line((int)(s->x+0.5),y,(int)(s->nextEdge->x+ } 0.5),y);

else s=s->nextEdge->nextEdge; {Ael=p; }

net[y]=p->nextEdge; y++;

Ael->nextEdge=s; /*如果满足条件，则从活化边表中删 } 除*/

}

} for(s=Ael;s!=NULL;p=s,s=s->nextEdge) m=0; if(Ael->ymax==y)

for(i=0;i<480;i++) Ael=Ael->nextEdge;

if(net[i]!=NULL)m++; else if(s!=NULL&&s->ymax==y) s=Ael; p->nextEdge=s->nextEdge; printf("\n此时边结构:\n"); for(s=Ael;s!=NULL;s=s->nextEdge) while(s!=NULL){ printf("%d->(%d,%f,%f)-", s->x=s->x+s->delatx;

y,s->ymax,s->x,s->delatx); }while(Ael!=NULL||m!=0);

s=s->nextEdge; } getch();

getch(); closegr();

} }

3、程序过程及算法分析

在程序运行以后，按顺时针或逆时针输入顶点坐标，最后输入0，结束输入。按任意键则填充直至有新的边插入活化边表。

扫描线的数据结构和算法本身比逐点判断法复杂的多，但是它利用边的连贯性以加速交点的计算，利用ET以排除盲目求交，利用扫描线的连贯性以避免逐点判断，算法要比逐点判断法快。

4.6、区域填充

4.6.1、递归填充算法

1、算法思想

设（x，y）为边界表示4连通区域内的一点，区域边界像素颜色为boundaryColor,以（小，y）为种子点，要将整个区域填充为新的颜色newColor。递归算法的过程如下：先判别像素（x，y）的颜色，若它的值不等于边界的颜色或新的颜色，说明该像素位于区域以内并且没有尚未填充。置该像素的颜色为newColor，再对其上、下、左、右四个相邻像素分别作递归填充。

2、程序代码

递归算法的程序参见教材程序4.4；

3、程序执行与算法分析

区域填充的递归算法原理和程序都很简单，但由于递归次数太多，区域内的每一个像素都引起一个递归，效率不高。

4.6.2、扫描线算法填充

1、算法思想

10

基本过程：在任意不间断区间中只取一个种子像素（不间断区间指在一条扫描线上一组相邻元素），填充当前扫描线上的该段区间；然后确定与这一区段相邻的上下两条扫描线上位于区域内的区段，并依次把它们保存起来，反复进行这个过程，直到所保存的每个区段都填充完毕。

实现步骤：

1> 确定种子区段：从种子点出发，沿当前扫描线向左右两个方向填充直到边界。用三元

组(y,xLeft,xRight)记录此区段。

2> 初始化：将堆栈设为空，将种子区段压入堆栈。

3> 出栈：若堆栈为空，算法结束;否则取栈顶元素，以纵坐标为y的扫描线为当前扫描

线，[xLeft,xRight]为搜索区间。

4> 进栈：分别确定与当前扫描线相邻的上下两条扫描线与区段(y,xLeft,xRight)连通的位

于给定区域内的区段。如果有这样的区段，填充并将它们的信息压入堆栈，返回步骤3。

2、程序代码

A、定义在堆栈上的基本操作的算法描述:

} 堆栈的初始化:

void InitStack() 出栈:

{ S->base=(Span Span PopStack(Span e)

*)malloc(100*sizeof(Span)); {

if(S->top==S->base){exit(0);} if(!S->base)exit(0);/*存储分配失败则退

S->top-=1; 出*/

S->top=S->base; e=*S->top;

S->stacksize=100; return e;

} } 清空堆栈:

void ClearStack() 判栈空,栈空则返回True,否则返回False: { S->top=S->base; Boolean isStackEmpty()

} {

if(S->top==S->base) return(True); 入栈:

void PushStack(Span e) else return(False);

{ *S->top=e; }

S->top+=1;

B、扫描线算法程序

void ScanLineFill(int x,int y,int oldColor,int span.xRight=i-1;/*确定区段右边界*/ newColor) i=x-1;

{int xLeft,xRight,i; while(getpixel(i,y)==oldColor)/*向左填充*/ Boolean isLeftEndSet,spanNeedFill; {putpixel(i,y,newColor);

Span span; i--;

InitStack(); }

/*填充并确定种子点（x,y）所在的区段*/ span.xLeft=i+1;/*确定区段左边界*/ i=x; ClearStack();

span.y=y; while(getpixel(i,y)==oldColor)/*向右填充*/

{putpixel(i,y,newColor); PushStack(span);

i++; /*终止判断*/

} while(S->top!=S->base)/*出栈*/ 11

{ } /*end of while(!isStackEmpty)*/ span=PopStack(span); /*处理下面一条扫描线*/

y=span.y+1; y=y-2;

xRight=span.xRight; xRight=span.xRight;

i=span.xLeft-1; i=span.xLeft-1;

isLeftEndSet=False; isLeftEndSet=False;

while(getpixel(i,y)==oldColor) while(getpixel(i,y)==oldColor)

{putpixel(i,y,newColor); /*向左填充*/

{putpixel(i,y,newColor); i--;

i--; }

} if(i!=span.xLeft-1)

{isLeftEndSet=True; if(i!=span.xLeft-1)/*确定区段左边界*/

{isLeftEndSet=True; xLeft=i+1;

xLeft=i+1; }

} i=span.xLeft;

i=span.xLeft; while(i<xRight)

while(i<xRight) {spanNeedFill=False;

{spanNeedFill=False; while(getpixel(i,y)==oldColor)

{if(!spanNeedFill) while(getpixel(i,y)==oldColor)/*向右

{spanNeedFill=True; 填充*/

{if(!spanNeedFill) if(!isLeftEndSet)

{spanNeedFill=True; {isLeftEndSet=True; if(!isLeftEndSet) xLeft=i;

{isLeftEndSet=True; }

xLeft=i; }

} putpixel(i,y,newColor); } i++;

putpixel(i,y,newColor); }

i++; if(spanNeedFill)

} {span.y=y;

span.xLeft=xLeft; if(spanNeedFill)/*如果确定种子填充

span.xRight=i-1; 点,则入栈*/

{span.y=y; PushStack(span);

span.xLeft=xLeft; isLeftEndSet=False;

span.xRight=i-1; spanNeedFill=False;

PushStack(span); }

isLeftEndSet=False; while(getpixel(i,y)!=oldColor&&i<getmaxx() spanNeedFill=False; )

} i++;

while(getpixel(i,y)!=oldColor&&i<getmaxx() }

} /*end of while(!isStackEmpty)*/ )/*扫描一行,以确定是否还有区域内的点*/

i++;

3、运行过程及结果分析：

先用fillellipse(100,100,60,40) 画出实心椭圆，然后用如上算法填充，代码如下： 12

setcolor(5);

fillellipse(300,250,60,40);

ScanLineFill(300,250,15,5);

此算法还能填充带边框的多边形，如下代码填充一个矩形区域，oldColor为背景色0： rectangle(100,20,200,50);

ScanLineFill(125,30,0,5);

如下代码填充带孔的四连通区域：

bar(100,80,150,180);

bar(150,80,200,90);

bar(200,80,250,180);

bar(150,130,200,180);

ScanLineFill(110,150,15,2);

对于每一个待填充的区段，只需压栈一次，因此扫描线算法的效率提高了很多。

4.7、二维裁剪

4.7.1、Cohen-Sutherland算法

1、算法思想

本算法也称为编码算法，算法分为三个步骤：判断线段两端是否都在窗口内，如果是，线段完全可见；否则判断线段是否显然不可见，如果是，裁剪结束。否则求线段与窗口边延长线的交点，此线段将线段分为两段，其中一段不可见，舍弃。对余下的线段继续进行递归裁剪。

算法的编码是进行二进制位运算，若顶点在窗口内，则二进制编码为0000；否则进行编码，具体方法可见教材6.1.3。

2、程序代码

void CompOutCode(float x,float y,struct struct OutCode Rectangle *rect,struct OutCode *outcode) outcode0,outcode1,*outcodeout;

float x,y; {outcode->all=encode(x,y,rect);/*对直线

顶点进行二进制编码,以确定直线位置*/ accept=0; done=0;/*判断条件初始化*/

outcode->top=outcode->bottom=0; CompOutCode(x0,y0,rect,&outcode0); if(y>(float)rect->ymax) CompOutCode(x1,y1,rect,&outcode1); outcode->top=1;

else if(y<(float)rect->ymin) do{if(outcode0.all==0&&outcode1.all==0) outcode->bottom=1; {accept=1;done=1; } /*完全可见 outcode->right=outcode->left=0; */

if(x>(float)rect->xmax) else

outcode->right=1; if((outcode0.all&outcode1.all)!=0)

else if(x<(float)rect->xmin) done=1; /*完全不 outcode->left=1; 可见*/

} else

void CohenSutherlandLineClip(float { if(outcode0.all!=0)

x0,float y0,float x1,float y1,struct Rectangle outcodeout=&outcode0; *rect) else

{void CompOutCode(float,float,struct outcodeout=&outcode1;

Rectangle *,struct OutCode *); if(outcodeout->left)

int accept,done; /*与窗口左边求交*/

13

{x=x0+(x1-x0)*(rect->ymin-y0)/(y1-y0); {y=y0+(y1-y0)*(rect->xmin-x0)/(x1-x0); y=(float)rect->ymin;

x=(float)rect->xmin; }

}

else if(outcodeout->top) if(outcodeout->all==outcode0.all)

{x0=x; /*与窗口上边求交*/

y0=y;

{x=x0+(x1-x0)*(rect->ymax-y0)/(y1-y0); CompOutCode(x0,y0,rect,&outcode0);

y=(float)rect->ymax; }

} else

else if(outcodeout->right) {x1=x;

/*与窗口右边求交*/ y1=y;

{y=y0+(y1-y0)*(rect->xmax-x0)/(x1-x0); CompOutCode(x1,y1,rect,&outcode1);

x=(float)rect->xmax; }

} }/*else*/

else if(outcodeout->bottom) /* }while(!done);

if(accept) 与窗口下边求交*/

line((int)x0,(int)y0,(int)x1,(int)y1);

3、程序运行与算法分析

本程序借鉴了教材上程序6.1，进行了改进，把编码函数变得简单易懂，提高了效率。本算法对于完全不可见和完全可见的线段裁剪极为有效。

4.7.2、中点分割算法

1、算法思想

中点分割算法分别找出最靠近直线两个端点的可见点，这两个可见点之间的连线即为可见线段。而找出离端点最近的可见点的方法是采取中点分割方法。在求端点的时候，必须对端点的位置进行判断。进行位置的判断，运用了位运算。

2、程序代码

int encode(int x,int y,int xl,int xr,int yb,int yt) long d,d1,d2;

{int c=0; pt=(struct point *)malloc(sizeof(struct if (x<xl) c=c|1; point));

else if (x>xr) c=c|2; code1=encode(x1,y1,xl,xr,yb,yt); if (y<yb) c=c|4; code2=encode(x2,y2,xl,xr,yb,yt); else if (y>yt) c=c|8; if (code1==0)/*(x1,y1)在裁剪窗口内,返回 return c; 该点*/

} {xx=x1; yy=y1;

struct point pt->x=xx; pt->y=yy;

{int x; return pt;

int y;}; }

struct point *edgepoint(int x1,int y1,int x2,int if ((code1&code2)!=0) return NULL; y2,int xl,int xr,int yb,int yt) do{

{struct point *pt; xx=(x1+x2)/2;

int code1,code2,code; yy=(y1+y2)/2;

int xx,yy; code=encode(xx,yy,xl,xr,yb,yt); 14

d1=(yy-y1)*(yy-y1); line(xl,yt,xr,yt); line(xl,yb,xr,yb); d2=(xx-x1)*(xx-x1); line(xl,yt,xl,yb); line(xr,yt,xr,yb);

d=sqrt(d1+d2); printf("Enter the first point of the line:"); pt->x=xx;pt->y=yy; scanf("%d,%d",&x1,&y1);

if((code&code1)!=0) printf("Enter the second point of the line:"); {x1=xx;y1=yy; scanf("%d,%d",&x2,&y2);

} setcolor(1);

else{x2=xx; line(x1,y1,x2,y2);

y2=yy;} /*求出最靠近(x1,y1)的内点*/

}while(d>1); p1=edgepoint(x1,y1,x2,y2,xl,xr,yb,yt); return pt; /*求出最靠近(x2,y2)的内点*/

}

main() p2=edgepoint(x2,y2,p1->x,p1->y,xl,xr,yb,yt); { int xl,xr,yt,yb; setcolor(14);

int x1,y1,x2,y2; if(p1!=NULL&&p2!=NULL)

struct point *p1,*p2; line(p1->x,p1->y,p2->x,p2->y); initgr(); else

printf("Enter the left,right,buttom,top printf("\nthe line is invisiable."); edge:"); getch();

scanf("%d,%d,%d,%d",&xl,&xr,&yb,&yt); closegraph();

setcolor(12);

3、程序运行与算法分析

中点算法主要运用了位运算，计算过程只用了加法和除2运算，所以特别适合用硬件来实现。对于分辨率为2?2的显示器，上述二分过程至多运算N次，算法复杂度有限。

4.7.3、梁友栋-Barsky线段裁减算法

1．算法思想

将待裁减线段P0P1及矩形均看作点集，裁减结果就成为两个点集的交集，将交集求出来再画出来就实现了裁减算法，具体的实现方法参见教材P115页

2．程序代码

A、生成矩形裁剪框的程序

void painRectangle(Rectangle *rect,int color)

{ setcolor(color);

line(rect->xmin,rect->ymin,rect->xmax,rect->ymin) ;

line(rect->xmax,rect->ymin,rect->xmax,rect->ymax) ;

line(rect->xmax,rect->ymax,rect->xmin,rect->ymax) ;

line(rect->xmin,rect->ymax,rect->xmin,rect->ymin) ;

}

B、裁剪的算法见教材程序6.2。

3、程序运行与算法分析

算法分析，梁友栋算法的算法思想不失为一种很好的算法，特别是他将二维图形转化为一维图形来考虑的思想确实很好，在算法实现时我加了一个矩形框作为裁减窗口，便于我们观察裁减的结果。

4.8、Bezier曲线的生成

15 NN

1、Bezier曲线的介绍

Bezier曲线是一种广泛应用于外形设计的参数曲线，它通过对一些特定点的控制来曲线的形状，这些点即为控制顶点。给定n?1个点，p0p1?pn?1，折线p0p1?pn?1称为控制多边形。曲线的参数表达式为P(t)??PBEZi

i?0ni,n(t),t?(0,1)。其中BEZi,n(t)是Bernsetin

基函数，因此BEZi,n(t)函数决定了Bezier曲线的性质。

Bezier曲线具有对称性、仿射不变形、凸包性等性质。

2、生成三次Bezier曲线的程序

int main(void) C[j][3]=-p[j][0]+3*p[j][1]-3*p[j][2]+p[j][3]; { float C[2][4],t=0,deltat; }

float xt,yt; deltat=1.0/count;

int j,count=200; t=0;

float p[2][4]={50,140,400,600, moveto(p[0][0],p[1][0]);

400,100,20,420}; for(j=1;j<=count;j++)

{t+=deltat; initgr(); /* BGI初始化 */

setcolor(14); xt=C[0][0]+t*(C[0][1]+t*(C[0][2]+t*C[0][3])); moveto(p[0][0],p[1][0]); yt=C[1][0]+t*(C[1][1]+t*(C[1][2]+t*C[1][3])); for (j=1;j<4;j++) lineto(p[0][j],p[1][j]); lineto((int)(xt+0.5),(int)(yt+0.5));

setcolor(12); }

for(j=0;j<2;j++) getch();

{C[j][0]=p[j][0]; closegraph();

C[j][1]=-3*p[j][0]+3*p[j][1]; return 0;

C[j][2]=3*p[j][0]-6*p[j][1]+3*p[j][2]; }

五、实验报告说明

以上实验由信科0306班汤剑（班长）、李涛（学习委员）、赵正洋、刘文钊、沈贤龙五位同学共同参与完成。

其中4.1、4.2、4.3、4.4的编程由实验小组讨论完成。4.1由沈贤龙，4.2由刘文钊，4.3由赵正洋分别执笔完成；4.4由沈贤龙和刘文钊共同完成。

此外，赵正洋还完成了4.5，4.6.1，4.7.1，4.7.2、4.8的编程和报告，刘文钊完成了4.6.2的编程和报告，沈贤龙完成了4.7.3的编程和报告。

16