计算机图形学课件

计算机图形学东北大学闻时光计算机图形学东北大学闻时光1课程简介学习方法实验课小组项目联系方式CGcourse@163.com83688326闻时光课程简介学习方法2参考书目陈元琰《计算机图形学实用技术》清华大学出版社2007.3孔令德《计算机图形学实用教程》清华大学出版社2008.4PhilipJ.Schneider《计算机图形学几何工具算法详解》电子工业出版社2005.1参考书目陈元琰《计算机图形学实用技术》清华大学出版社203图形图形是传递信息最主要的媒体之一。人们使用图形来表达与交流思想有着悠久的历史，工程领域和各个科学分支都离不开图。它能使人们通观全局，一目了然。人的眼睛从一张图纸中吸收信息比从一张数据表格吸收信息快得多。若图形和数字互为补充，则可使人们更深刻地认识事物的本质及其内在联系。图形图形是传递信息最主要的媒体之一。4计算机图形学定义是研究怎样利用计算机表示、生成、处理和显示图形的原理、算法、方法和技术的一门学科。它与一般的科学计算不同。在一般的科学计算中，涉及的是数字运算，在计算机图形学中则是以基本的几何元素为其运算对象的。这些几何元素描述物体的模拟图示表示：符号、线图、阴影区域和物体等。研究计算机图形学的主要工具是图形显示系统和绘图机、打印机等，乃至三维虚拟环境。计算机图形学定义是研究怎样利用计算机表示、生成、处理和显示图5计算机图形学相关学科C.G.——对非图形信息产生图形I.P.——对图象采用增强、变换等技术进行处理增强(对比度)：对暴光过度或不足，以及 模糊的图象进行处理。变换：一幅亮度范围宽的图象—>两种亮 度的图象—>线条状图形P.R.——对图象提取特征、予以分类 和描述关系，再进行模式匹配计算机图形学相关学科C.G.——对非图形信息产生图形I.P.6C.G.、I.P.和P.R.之间的区别描述图像I.P.C.G.P.R.C.G.、I.P.和P.R.之间的区别描述图像I.P.C7应用领域1.管理、科学技术2.制图学3.动画4.计算机辅助设计CAD5.模拟6.艺术和教育7.办公自动化应用领域1.管理、科学技术8管理、科学技术绘制数学、物理以及经济函数的二维及三维图形：直方图、线条图、扇形图、进程图...特点：简洁、直观——>数据的模型和趋势。管理、科学技术绘制数学、物理以及经济函数的二维及三维图形：直9制图学以高精度的地理或其他自然现象的图形—>纸或胶片上。包括地图、地质图、油层图、海图、气象、人口密度图...制图学以高精度的地理或其他自然现象的图形—>纸或胶片上10动画用计算机可以产生逼真的动画效果，可用于艺术创作，模拟真实的环境，或进行飞机、驾驶等训练。动画用计算机可以产生逼真的动画效果，可用于艺术创作，模拟真11计算机辅助设计CAD设计{元部件：机械、电气、电子设备...系统{结构(建筑物、汽车车身、飞机和船的外壳及内部结构)光学系统电话及计算机网络计算机辅助设计CAD设计{元部件：机械、电气、电子设备..12汽车效果图和线框图汽车效果图和线框图13模拟数学图形——科学现象的数学模型(液体流动、相对论、核反应、化学反应、生理系统与器官以及有负载时结构的变形等)DNA皮肤结构：真皮，上皮及附属结构模拟数学图形——科学现象的数学模型(液体流动、相对论、核14模拟云雾、烟、其他大小形状不同的飞机等特殊景物飞行模拟器：固定环境的景色可用在月球登陆的宇航员(练习登月）、宇宙飞船驾驶员(首航前训练)模拟云雾、烟、其他大小形状不同的飞机等特殊景物15过程控制利用交互式图形生成技术形成的人机交互系统，实现人与控制或管理对象之间的相互作用。如工厂中的设备、工序控制，机场与铁路的调度等。过程控制利用交互式图形生成技术形成的人机交互系统，实现人与控16艺术和教育：教学活动蝉（线框图）艺术和教育：教学活动蝉（线框图）17艺术和教育艺术广告艺术绘画艺术和教育艺术广告18办公自动化在办公室中，用图形方式显示并交换文件、报表、图例和其它信息，并在输出设备上输出、保存起来。办公自动化在办公室中，用图形方式显示并交换文件、报表、图例和19图形学发展历史50s1950年，第一台图形显示器作为美国麻省理工学院（MIT）旋风I号（WhirlwindI）计算机的附件诞生了。该显示器用一个类似于示波器的阴极射线管（CRT）来显示一些简单的图形。1958年美国Calcomp公司由联机的数字记录仪发展成滚筒式绘图仪，GerBer公司把数控机床发展成为平板式绘图仪。图形学发展历史50s1950年，第一台图形显示器作为美国麻省20图形学发展历史60s1962年，MIT林肯实验室的IvanE.Sutherland发表了一篇题为“Sketchpad：一个人机交互通信的图形系统”的博士论文，首次使用“ComputerGraphics”这个术语，证明了交互计算机图形学是一个可行的、有用的研究领域1964年MIT的教授StevenA.Coons提出了被后人称为超限插值的新思想，通过插值四条任意的边界曲线来构造曲面。同在60年代早期，法国雷诺汽车公司的工程师PierreBézier发展了一套Bézier曲线、曲面的理论，成功地用于几何外形设计。Coons方法和Bézier方法是CAGD最早的开创性工作。图形学发展历史60s1962年，MIT林肯实验室的Ivan21图形学发展历史70s70年代是计算机图形学发展过程中一个重要的历史时期。光栅显示器的产生，图形学进入了第一个兴盛的时期，并开始出现实用的CAD图形系统1977、1979年开始，计算机图形学标准制定，真实感图形学和实体造型技术的产生。1970年Bouknight提出了第一个光反射模型，1971年Gourand提出“漫反射模型＋插值”的思想，被称为Gourand明暗处理。r1975年Phong提出了著名的简单光照模型—Phong模型。这些可以算是真实感图形学最早的开创性工作。从1973年开始，相继出现了英国剑桥大学CAD小组的Build系统、美国罗彻斯特大学的PADL-1系统等实体造型系统。图形学发展历史70s70年代是计算机图形学发展过程中一个重要22图形学发展历史80s1980年Whitted提出了一个光透视模型—Whitted模型，并第一次给出光线跟踪算法的范例，实现Whitted模型。1984年，美国Cornell大学和日本广岛大学的学者分别将热辐射工程中的辐射度方法引入到计算机图形学中，用辐射度方法成功地模拟了理想漫反射表面间的多重漫反射效果。1986年，美国科学基金会（NSF）专门召开了一次研讨会，会上提出了“科学计算可视化（VisualizationinScientificComputing，简称为ViSC）”。图形学发展历史80s1980年Whitted提出了一个光透视23SIGGRAPHSIGGRAPH会议，“TheSpecialInterestGrouponComputerGraphicsandInteractiveTechniques”ACMSIGGRAPH会议是计算机图形学最权威的国际会议，每年在美国召开，参加会议的人在50,000人左右。世界上没有第二个领域每年召开如此规模巨大的专业会议，SIGGRAPH会议很大程度上促进了图形学的发展。

1974年在Colorado大学召开了第一届SIGGRAPH年会。因为每年只录取大约50篇论文，在ComputerGraphics杂志上发表，因此论文的学术水平较高，基本上代表了图形学的主流方向。SIGGRAPHSIGGRAPH会议，“TheSpec24虚拟现实虚拟现实技术就是利用计算机生成一个逼真的三维虚拟环境，通过自然技能使用传感设备与之相互作用的新技术。它与传统的模拟技术完全不同，是将模拟环境、视景系统和仿真系统合三为一，利用头盔显示器、图形眼镜、数据服、立体声耳机、数据手套及脚踏板等传感装置，把操作者与计算机生成的三维虚拟环境连结在一起。与传统计算机相比，虚拟现实系统具有三个重要特征：临境性、交互性、想象性。虚拟现实建模语言VRML是描述虚拟环境中场景的一种标准，可以利用它在INTERNET建立交互式的三维多媒体环境。VRML的基本特征包括分布式、交互式、平台无关、三维、多媒体集成和逼真自然等，国际标准化组织1998年1月正式将其批准为国际标准。虚拟现实虚拟现实技术就是利用计算机生成一个逼真的三维虚拟环境25计算机艺术可用于美术创作的软件很多，如二维平面的画笔程序(如CorelDraw，Photoshop，PaintShop)、专门的图表绘制软件(如Visio)、三维建模和渲染软件包(如3DMAX，Maya)、以及一些专门生成动画的软件(如Alias，SoftImage)等。这些软件不仅提供多种风格的画笔、画刷，而且提供多种多样的纹理贴图，甚至能对图像进行雾化/变形等操作。很多功能是一个传统的艺术家无法实现也不可想象的。当然，传统艺术的一些效果也是上述软件所不能达到的。例如钢笔素描的效果，由于钢笔素描与传统的图形学绘制方法差别很大，所以研究起来难度也颇大，很多学者已在这方面做了卓有成效的工作，取得了一定的成果。计算机艺术可用于美术创作的软件很多，如二维平面的画笔程序(如26图形用户接口用户接口是人们使用计算机的第一观感。一个友好的图形化的用户界面能够大大提高软件的易用性，在DOS时代，计算机的易用性很差，编写一个图形化的界面要费去大量的劳动，过去软件中有60％的程序是用来处理与用户接口有关的问题和功能的。进入80年代后，随着Xwindow标准的面世，苹果公司图形化操作系统的推出，特别是微软公司Windows操作系统的普及，标志着图形学已经全面融入计算机的方方面面。目前几个大的软件公司都在研究下一代用户界面，开发面向主流应用的自然、高效多通道的用户界面。研究多通道语义模型、多通道整合算法及其软件结构和界面范式是当前用户界面和接口方面研究的主流方向，而图形学在其中起主导作用。图形用户接口用户接口是人们使用计算机的第一观感。一个友好的图27计算机图形学研究的基本问题图形描述基本几何：直线、圆弧等；高级几何：曲线、曲面等图形变换二、三维变换、三维到二维、观察流程、几何变换等图形运算基本几何间的计算、裁剪、布尔运算等图形显示/输出基本图形生成算法、消隐、绘图、光照模型等图形输入交互技术、参数化设计、造型技术等算法和算法复杂性分析空间和时间等计算机图形学研究的基本问题图形描述28两个核心问题如何建模交互技术曲线造型如何绘制光栅图形学光照模型裁剪计算颜色模型两个核心问题如何建模29图形描述一个物体的计算机描述叫做模型，它能被计算机所懂得，并在一定的条件下（变换和投影）被转换成相应的图形在显示屏幕或绘图机上输出；而图形是模型的一个具体可见像，是人们所看到的模型的表征。在三维空间，描述的是几何形体和几何曲面，只有在平面上，它才是人们通常所称的图形。图形描述一个物体的计算机描述叫做模型，它能被计算机所懂得，并30图形描述几何形体以封闭的表面表示，一般为一个由平面和曲面围成的多面体。一个几何形体在空间上应是完备的(几何性和拓扑性)，而且包含足够的用于推导的任何空间函数(如直线方程、平面方程、曲面构造等)以及进行各种形体运算与处理的信息。图形描述几何形体以封闭的表面表示，一般为一个由平面和曲面围成31图形描述在多面体表示中，有关的基本元素（体、面、环、棱和顶点）的信息分为二大类：几何信息：用以确定每个分量在欧氏空间中的几何位置(如点坐标)和描述(如平面方程系数)；拓扑信息：用来定义几何元素的数目及相互间的连接关系。几何信息只考虑点、线和无限面。拓扑信息将点看作顶点，将线限制为棱(线段)，由外环和内环定义出面和内孔。一个完全的三维几何体描述，几何信息和拓扑信息两者都是必要的图形描述在多面体表示中，有关的基本元素（体、面、环、棱和顶点32图形描述描述一个多面体各元素之间的拓扑关系可以互相推导。故理论上只需存储一种关系就行了，但由于关系的推导要付出代价，所以一般的系统常同时存储若于种拓扑关系。这些拓扑关系，既要足够地表示出几何形体的构造，又要尽量压缩信息的存储量，且要便于检索和修改，而十分重要的是要便于计算机的自动生成。图形描述描述一个多面体各元素之间的拓扑关系可以互相推导。故理33图形描述对于曲表面的几何形体，需分别研究自由曲线和自由曲面的建立；用于插值和数学放样的三次样条函数是应用得最早研究得最详尽的一种。Bezier曲线和曲面与B样条曲线和曲面是在计算机辅助几何设计应用最广的曲线和曲面几何构型方法。关于这些方面的研究，至今仍在继续发展中。图形描述对于曲表面的几何形体，需分别研究自由曲线和自由曲面的34图形描述平面上图形的描述是基于直线和圆弧的描述。仅用这两种基本几何元素就可构成平面上的任何图形。因而直线段和圆弧段也叫基本几何段，本课程将详加阐述。数据结构技术在图形描述中起着关键的作用。线性链接表、树结构、堆栈、队列等将广泛应用于几何模型的描述、运算和显示中。图形描述平面上图形的描述是基于直线和圆弧的描述。仅用这两种基35图形输入图形输入需要解决的问题是：交互输入的方法。工程设计图纸直接输入（矢量识别）的方法。将自由手书的立体构造或三视图重构的方法。计算机自动生成方法。从物体的多幅深度图像重建三维几何模型。通过三维激光扫描仪在物体表面测得一些离散点，再用重构算法生成网格模型等等。图形输入图形输入需要解决的问题是：36图形输入图形输入的常规方法是将事先写好的源程序(指令)在屏幕上输入，即所谓的编程输入，使得人、机之间的交互作用缓慢。对于工程上常用的一类规格化图形，可以编制一个通用程序，采用格式数据输入的办法得到图形。但是在处理三维的，或是形状复杂的物体时还有较多的困难，输入数据太多就是一个障碍。图形输入图形输入的常规方法是将事先写好的源程序(指令)在屏幕37图形输入除了这种图形的直接输入之外，通过对基本体元的构型产生新的、复杂的三维物体也是一种输入的手段，当然这需要涉及更多的研究。从计算机图形学的发展情况看，对图形输出的研究多于对图形输入的研究，许多人往往被计算机输出的美妙图形所迷惑，却看不到为得到这些图形所做的大量数据输入的准备工作。图形输入的工作量和难度并不亚于几何算法和图形输出。随着时间的推移，图形输入将越来越成为计算图形学应用中的主要障碍。图形输入除了这种图形的直接输入之外，通过对基本体元的构型产生38图形变换一个图形系统需具有图形变换的功能。这种变换包括二维变换、三维变换和三维向二维的变换三种。对应于几何元素及其选定的坐标系来说，则包括几何变换和坐标系变换两种。这些变换系统称为图形变换。在构造、产生、处理和输出图形的各个环节，图形变换起着重要的作用。图形变换一个图形系统需具有图形变换的功能。这种变换包括二维变39图形变换人们可以直接定义一个几何图形或几何体，也可通过对某些几何体的变换去构造新的几何体或其中的某个部份。这种变换可以是平移、放大(缩小)、旋转、反射、错切等。一个三维场景通常就是由一些基本几何元素通过上述操作构造的。例如，可以通过平移的办法装配一幢建筑物的大部份窗子，这使得图形输入大为简化。在进行图形处理的过程中，还可以放大一个图形以便使其某一部份能更清楚地显示；缩小图形以便看到图形更多的部份。图形变换人们可以直接定义一个几何图形或几何体，也可通过对某些40图形变换在显示或绘制一个环境的时候，需要将三维信息映射到二维屏幕上。轴测投影、平行投影和透视投影用于完成这项工作。在视点改变得非常快或物体相对运动的应用场合，变换必须反复运用。因此，找到一个有效的方法去实现图形变换是十分重要的。图形变换在显示或绘制一个环境的时候，需要将三维信息映射到二维41图形变换采用向量、矩阵和齐次坐标的形式去描述图形变换是一种比较好的办法，它允许将线性代数的一些基本理论应用到图形变换中。例如一个矩阵对应于一个变换，图形的连续变换可由矩阵的相乘实现，而逆矩阵对应于一个逆变换。所有的变换都基于点变换，例如对一条线段的变换只需考虑其两个端点的变换就可以了。基本几何元素描述的变换也和点的变换有密切的联系。例如描述一条直线的方程系数在不同坐标下的关系也可由点变换的相应变换矩阵求得。图形变换采用向量、矩阵和齐次坐标的形式去描述图形变换是一种比42图形运算在三维空间，图形的运算是一种几何形体的运算，它是CAGD的一个重要操作，这种操作通常叫做物体造型，或几何造型。设计人员可通过修改立方体，圆柱体之类的基本体元来生成形体。例如通过缩放，通过用集合论中的并、交、非、差等概念所进行的各种布尔运算把一些基本物体体元组合起来。设计人员的职责是把各体元正确地定位下来，使得这些运算能进行下去。另一方面几何造型系统还负责估计各体元之间的相互作用，各种相交出现的位置以及它们之间的相互关系，以确保生成法定的三维形体。系统还必须正确地、在计算机限制下内尽可能精确地完成相交分析。图形运算在三维空间，图形的运算是一种几何形体的运算，它是CA43图形运算几何造型系统常处理一些比较简单的体元：立方体、圆柱体、楔、嵌条，以直线或圆弧为边界的薄片等。所涉及的线和面在几何上是简单的直线、圆弧、平面和圆柱面，处理这些由一个正确的方式构造出来的物体的相交，从概念上是比较容易的。但主要困难在于：虽然几何简单，但多个元素的拼合却是复杂的。故对于确实复杂的形体的组合问题，所需的几何算法的效率就变得十分重要，需进行几何复杂性分析。图形运算几何造型系统常处理一些比较简单的体元：立方体、圆柱体44图形运算几何造型系统较之早期图形系统的显著优越之处在于：无需人为干预就能预定形体与执行一连串运算。即具有高度自动化的图形定义或构造、产生处理或演变功能。几何元素的定向在图形运算中起着相当大的作用。例如平面图形的几何运算就是建立在以向量为基本几何元素的环的基础上实现的。直线和圆弧这两种基本几何段的相贯运算是平面图形运算的基础，保证这些算法的准确性，提高这些算法的效率是计算机图形系统一项基础性的工作。图形运算几何造型系统较之早期图形系统的显著优越之处在于：无需45图形输出图形输出是人—机交互系统中人们能够得到的最直观的结果。它直接向人们显示出计算机图形系统的效果。相对而言，图形输出计算机图学中研究得最早、最深入、解决得最好的一部份工作。图形输出图形输出是人—机交互系统中人们能够得到的最直观的结46图形输出一个物体的制造者可以从一张多视图的图样里了解到许多内容。因此，一个能在二维参考平面里提供综合的，绘制直线和曲线的系统也就提供了画出一个复杂而详细的图形或物体的基础。但是，图形只是三维物体的某一个特定的不完整的表示。而物体有一种图里没有的，与众不同的特性——完全的三维定义。人们可以随意地在三维空间中把物体旋转和平移以及物体的综合，但一般不能用图形做到这一点。图形输出一个物体的制造者可以从一张多视图的图样里了解到许多内47图形输出基本几何（点、直线、圆及圆弧等）和文字的光栅化显示，几何裁剪算法基本几何的描述、相交算法，曲线拟合和双圆弧逼近算法，动态显示的插值算法。图形显示中的裁剪算法，通常称为窗口算法；隐藏线、隐藏面消除算法。光照模型及算法。纹理贴图；大规模场景显示算法；图形显示软件和打印机、绘图机等的图形输出后处理软件等等。图形输出基本几何（点、直线、圆及圆弧等）和文字的光栅化显示，48几何算法、几何复杂性和计算效率一个动画程序，一个游戏程序，用户的起码要求是“流畅”；支撑它的是几何算法，几何复杂性问题及计算的效率。许多通过交互设计各种形体的系统，其成功的主要断依据是凭视觉。例如套料问题，这在造船、服装等行业是极为有用的，然而至今存在的系统还是由人机交互作用来完成。而几何造型系统在相交问题的正确算法和处理组合比较复杂问题的能力，这种系统的发展表明，需要多多研究几何算法。几何算法、几何复杂性和计算效率一个动画程序，一个游戏程序，用49几何算法、几何复杂性和计算效率几何相交问题在几何算法中占有较大的比重，在平面上，它处理直线和直线，圆弧和直线，圆弧和圆弧等基本几何的相交，在三维空间则是处理直线和平面，平面和平面的相互关系。但是，并不是所有的处理直线和直线的相交都是简易的。例如，考虑两个平面多边形相交的状态，按照Shamos(1978)算法，如果这两个多边形是凸的，对于n条边的多边形可以用O(n)的时间解决这个问题。而对于两个任意非凸多边形，为解决这个问题要花O(n2)的时间，可能形成达n2/4个不相叠的凸多边形。几何算法、几何复杂性和计算效率几何相交问题在几何算法中占有较50几何算法、几何复杂性和计算效率观察一个时间复杂性的例子：问题：设给定n个已经排序的数的队列，现在要插入一个新的数到这个队列中，并保持队列原有的次序，几何复杂性为O(n)次主算。应用二分法，可降为O(log2n)次。如果不计检索到元素后对其处理所花费的计算时间，而只对n的步数计算时间，那末当n=60时：n：6×10-5秒N^2：36×10-4秒N^3：216×10-3秒N^5：13分钟2^n：366世纪3^n：1.3×1013世纪几何算法、几何复杂性和计算效率观察一个时间复杂性的例子：51几何算法、几何复杂性和计算效率降低几何复杂性是几何算法的一个努力目标，它可以提高算法的效率。过去开发仅仅能“工作”的算法就常常足够了，即使在某些情况下效率低也无妨。随着使用计算机进行几何设计的增加，以及要解决问题的范围之扩大，效率、精度和正确性的问题就变得非常重要了。几何算法、几何复杂性和计算效率降低几何复杂性是几何算法的一个52计算机图形学的相关开发技术计算机图形学经过几十年的发展，已经达到了比较高的水平，目前已有若干图形学软件开发技术。利用这些开发技术，编写图形程序就容易多了，不必从底层开始，而只需将精力集中到图形程序本身上。计算机图形学的相关开发技术计算机图形学经过几十年的发展，已经53OpenGLOpenGL：OpenGL是OpenGraphicsLib的缩写，是一套三维图形处理库，也是该领域的工业标准。OpenGL源于SGI公司为其图形工作站开发的IRISGL，在跨平台移植过程中发展成为OpenGL。OpenGL被设计成独立于硬件，独立于窗口系统的，在运行各种操作系统的各种计算机上都可用，并能在网络环境下以客户/服务器模式工作，是专业图形处理、科学计算等高端应用领域的标准图形库。OpenGLOpenGL：OpenGL是OpenGraph54OpenGLMicrosoft、SGI、IBM、DEC、SUN、HP等大公司都采用了OpenGL作为三维图形标准。许多软件厂商也纷纷以OpenGL为基础开发出自己的产品，包括动画制作软件SoftImage和3DStudioMAX、仿真软件OpenInventor、VR软件WorldToolKit、CAD软件Pro/Engineer、GIS软件ARC/INFO等等。OpenGL实际上是一个开放的三维图形软件包，它独立于窗口系统和操作系统，以它为基础开发的应用程序可以十分方便地在各种平台间移植；OpenGL与C++紧密接合，便于实现图形的相关算法，并可保证算法的正确性和可靠性；OpenGL使用简便，效率高。OpenGLMicrosoft、SGI、IBM、DEC、SU55ACISACIS是美国SpatialTechnology公司推出的三维几何引擎，为各种3D造型应用的开发提供了几何造型平台，目前的最高本版已经到了R13。ACIS能够安装在多种平台上，包括Windows,Linux,Unix,Solaris,AIX等。ACIS采用了软件组件技术，用C++技术构造，它包含一整套的C++类和函数，开发人员可以使用这些类和函数构造一个面向终端用户的2/3维软件系统。ACIS是一个基于边界表示法的造型引擎，集线框、曲面和实体造型于一体，并允许这三种表示共存于统一的数据结构中。ACISACIS是美国SpatialTechnology公56ACISACIS系统的造型方法有：覆盖技术(covering)：覆盖一个由曲线组成的闭合区域的曲面放样技术(lofting)：通过一系列的曲线和与这些曲线相关联的曲面来构造新曲面的一种技术蒙面技术(skinning)：在一系列曲线之间构造一个曲面ACISACIS系统的造型方法有：57ACIS网格曲面(netsurfaces)：用一族曲线网来定义曲面的u和v参数方向，这为控制最终的曲面形状提供了很大的自由度规则(law)和图(graph)：提供规则类，直接用数学方程定义实体中的边和面扫掠(sweeping)：通过扫描一个轮廓(profile)来生成实体（solidbody）或者薄片体(sheetbody)。ACIS有三种不同的扫掠操作：规则扫掠、垂直扫掠以及刚性扫掠ACIS网格曲面(netsurfaces)：用一族曲线网来58DirectXDirectX是一种图形应用程序接口（API），它是一个提高系统性能的加速软件，由微软公司创建开发，微软将其定义为“硬件设备无关性”。DirectX就是一系列的DLL(DynamicLinkLib)，通过这些DLL，程序员可以在无视于设备差异的情况下访问底层的硬件。DirectX并不是一个单纯的图形API，它是一个用途广泛的API，它包含有DirectGraphics(Direct3D+DirectDraw)、DirectInput、DirectPlay、DirectSound、DirectShow、DirectSetup和DirectMediaObjects等多个组件，它提供了一整套的多媒体接口方案。DirectXDirectX是一种图形应用程序接口（API）59DirectXDirectX主要应用于游戏软件的开发。微软公司给众多的软、硬件商家提供一个共同开发的标准平台(就是DirectX)，大家都遵循这个标准，硬件制造商按照此标准研发制造更好的产品，游戏程序员根据这套标准开发游戏。无论硬件是否支持某特殊效果，只要DirectX标准中有，程序员就可以把它写到游戏中，当这个游戏在硬件上运行，如果此硬件根据DirectX标准把这个效果做到了此硬件驱动程序中，驱动程序驾驭其硬件算出此效果，用户就可以欣赏到此效果。DirectXDirectX主要应用于游戏软件的开发。60Java3DJava3DAPI是Sun定义的用于实现3D显示的接口。3D技术是底层的显示技术，Java3D提供了基于Java的上层接口。Java3D把OpenGL和DirectX这些底层技术包装在Java接口中。这种全新的设计使3D技术变得不再繁琐并且可以加入到J2SE、J2EE的整套架构，这些特性保证了Java3D技术强大的扩展性。Java3DJava3DAPI是Sun定义的用于实现3D显61Java3DJava3D实现了以下三维显示能够用到的功能生成简单或复杂的形体（也可以调用现有的三维形体）使形体具有颜色、透明效果、贴图等在三维环境中生成灯光、移动灯光等具有行为处理判断能力（键盘、鼠标、定时等）生成雾、背景、声音等。使形体变形、移动、生成三维动画等。编写非常复杂的应用程序，用于各种领域如VR（虚拟现实）Java3D是一个独立的可选组件，可以单独下载Java3DJava3D实现了以下三维显示能够用到的功能62VRMLVRML(VirtualRealityModelingLanguage)是一种标记语言，而不是一种API开发包。它使用VRML浏览器能读懂的ASCⅡ文本格式来描述世界和链接。VRML既可以用来建立真实世界场景的模型，也可以建立虚构的三维世界，就像许多游戏那样。VRML的设计是从在Web上欣赏实时的3D图像开始的。VRML浏览器，既是插件，又是帮助应用程序，还是独立运行的应用程序，它是传统的虚拟现实中同样也使用的实时3D着色引擎。这使得VRML应用从三维建模和动画应用中分离出来，在三维建模和动画应用中可以预先对前方场景进行着色，但是没有选择方向的自由。VRMLVRML(VirtualRealityModeli63VRMLVRML提供了6+1个自由度，可以沿着三个方向移动，也可以沿着三个方位旋转，同时还可以建立与其他3D空间的超链接。因此VRML是超空间的。VRML使用场景图(SceneGraph)数据结构来建立3D实境，这种数据结构是以SGI开发的OpenInventor3D工具包为基础的一种数据格式。VRML的场景图是—种代表所有3D世界静态特征的节点等级：几何关系、质材、纹理、几何转换、光线、视点以及嵌套结构。几乎所有生产三维产品的厂商，无论是CAD、建模、动画、VR，还是VRML，它们的结构核心都有场景图。VRMLVRML提供了6+1个自由度，可以沿着三个方向移动，64VRMLVRML在许多方面是与HTML平行的。VRML的文件.wrl是由可阅读的ASCⅡ文本构成的。这样一个文本编辑器就可以变成一个VRML世界的生成工具。程序员可以通过直接操作场景图来得到完全的控制权和高度的灵活性。VRMLVRML在许多方面是与HTML平行的。65五种计算机图形开发技术比较五种计算机图形开发技术比较66总结光栅图形学：经典基础算法基本几何的表示和计算：算法的基础数据结构：计算机图形学的基础图形变换：新的叙述方法——几何表示图形输入：三维造型、曲线、曲面图形输出：光照模型虚拟现实：计算机图形学的极致应用总结光栅图形学：经典基础算法67考核方法开发语言C/C++/matlab工具库OpenGL,OGRE,Direct3D,不强调全部自己开发分组可以采用单人或分组方式，人数最多不超过四人可以跨班级组队评分作品创意，效果，难度，分工，总结材料考核方法开发语言C/C++/matlab68总结材料文档总体方案详细设计源代码注释成果展示要求提交的文件结构清晰，内容完整源程序可读性好设计报告有总体框架，算法描述总结材料文档69作品综合运用各个课程知识策划设计开发测试总结作品综合运用各个课程知识70计算机图形学东北大学闻时光计算机图形学东北大学闻时光71课程简介学习方法实验课小组项目联系方式CGcourse@163.com83688326闻时光课程简介学习方法72参考书目陈元琰《计算机图形学实用技术》清华大学出版社2007.3孔令德《计算机图形学实用教程》清华大学出版社2008.4PhilipJ.Schneider《计算机图形学几何工具算法详解》电子工业出版社2005.1参考书目陈元琰《计算机图形学实用技术》清华大学出版社2073图形图形是传递信息最主要的媒体之一。人们使用图形来表达与交流思想有着悠久的历史，工程领域和各个科学分支都离不开图。它能使人们通观全局，一目了然。人的眼睛从一张图纸中吸收信息比从一张数据表格吸收信息快得多。若图形和数字互为补充，则可使人们更深刻地认识事物的本质及其内在联系。图形图形是传递信息最主要的媒体之一。74计算机图形学定义是研究怎样利用计算机表示、生成、处理和显示图形的原理、算法、方法和技术的一门学科。它与一般的科学计算不同。在一般的科学计算中，涉及的是数字运算，在计算机图形学中则是以基本的几何元素为其运算对象的。这些几何元素描述物体的模拟图示表示：符号、线图、阴影区域和物体等。研究计算机图形学的主要工具是图形显示系统和绘图机、打印机等，乃至三维虚拟环境。计算机图形学定义是研究怎样利用计算机表示、生成、处理和显示图75计算机图形学相关学科C.G.——对非图形信息产生图形I.P.——对图象采用增强、变换等技术进行处理增强(对比度)：对暴光过度或不足，以及 模糊的图象进行处理。变换：一幅亮度范围宽的图象—>两种亮 度的图象—>线条状图形P.R.——对图象提取特征、予以分类 和描述关系，再进行模式匹配计算机图形学相关学科C.G.——对非图形信息产生图形I.P.76C.G.、I.P.和P.R.之间的区别描述图像I.P.C.G.P.R.C.G.、I.P.和P.R.之间的区别描述图像I.P.C77应用领域1.管理、科学技术2.制图学3.动画4.计算机辅助设计CAD5.模拟6.艺术和教育7.办公自动化应用领域1.管理、科学技术78管理、科学技术绘制数学、物理以及经济函数的二维及三维图形：直方图、线条图、扇形图、进程图...特点：简洁、直观——>数据的模型和趋势。管理、科学技术绘制数学、物理以及经济函数的二维及三维图形：直79制图学以高精度的地理或其他自然现象的图形—>纸或胶片上。包括地图、地质图、油层图、海图、气象、人口密度图...制图学以高精度的地理或其他自然现象的图形—>纸或胶片上80动画用计算机可以产生逼真的动画效果，可用于艺术创作，模拟真实的环境，或进行飞机、驾驶等训练。动画用计算机可以产生逼真的动画效果，可用于艺术创作，模拟真81计算机辅助设计CAD设计{元部件：机械、电气、电子设备...系统{结构(建筑物、汽车车身、飞机和船的外壳及内部结构)光学系统电话及计算机网络计算机辅助设计CAD设计{元部件：机械、电气、电子设备..82汽车效果图和线框图汽车效果图和线框图83模拟数学图形——科学现象的数学模型(液体流动、相对论、核反应、化学反应、生理系统与器官以及有负载时结构的变形等)DNA皮肤结构：真皮，上皮及附属结构模拟数学图形——科学现象的数学模型(液体流动、相对论、核84模拟云雾、烟、其他大小形状不同的飞机等特殊景物飞行模拟器：固定环境的景色可用在月球登陆的宇航员(练习登月）、宇宙飞船驾驶员(首航前训练)模拟云雾、烟、其他大小形状不同的飞机等特殊景物85过程控制利用交互式图形生成技术形成的人机交互系统，实现人与控制或管理对象之间的相互作用。如工厂中的设备、工序控制，机场与铁路的调度等。过程控制利用交互式图形生成技术形成的人机交互系统，实现人与控86艺术和教育：教学活动蝉（线框图）艺术和教育：教学活动蝉（线框图）87艺术和教育艺术广告艺术绘画艺术和教育艺术广告88办公自动化在办公室中，用图形方式显示并交换文件、报表、图例和其它信息，并在输出设备上输出、保存起来。办公自动化在办公室中，用图形方式显示并交换文件、报表、图例和89图形学发展历史50s1950年，第一台图形显示器作为美国麻省理工学院（MIT）旋风I号（WhirlwindI）计算机的附件诞生了。该显示器用一个类似于示波器的阴极射线管（CRT）来显示一些简单的图形。1958年美国Calcomp公司由联机的数字记录仪发展成滚筒式绘图仪，GerBer公司把数控机床发展成为平板式绘图仪。图形学发展历史50s1950年，第一台图形显示器作为美国麻省90图形学发展历史60s1962年，MIT林肯实验室的IvanE.Sutherland发表了一篇题为“Sketchpad：一个人机交互通信的图形系统”的博士论文，首次使用“ComputerGraphics”这个术语，证明了交互计算机图形学是一个可行的、有用的研究领域1964年MIT的教授StevenA.Coons提出了被后人称为超限插值的新思想，通过插值四条任意的边界曲线来构造曲面。同在60年代早期，法国雷诺汽车公司的工程师PierreBézier发展了一套Bézier曲线、曲面的理论，成功地用于几何外形设计。Coons方法和Bézier方法是CAGD最早的开创性工作。图形学发展历史60s1962年，MIT林肯实验室的Ivan91图形学发展历史70s70年代是计算机图形学发展过程中一个重要的历史时期。光栅显示器的产生，图形学进入了第一个兴盛的时期，并开始出现实用的CAD图形系统1977、1979年开始，计算机图形学标准制定，真实感图形学和实体造型技术的产生。1970年Bouknight提出了第一个光反射模型，1971年Gourand提出“漫反射模型＋插值”的思想，被称为Gourand明暗处理。r1975年Phong提出了著名的简单光照模型—Phong模型。这些可以算是真实感图形学最早的开创性工作。从1973年开始，相继出现了英国剑桥大学CAD小组的Build系统、美国罗彻斯特大学的PADL-1系统等实体造型系统。图形学发展历史70s70年代是计算机图形学发展过程中一个重要92图形学发展历史80s1980年Whitted提出了一个光透视模型—Whitted模型，并第一次给出光线跟踪算法的范例，实现Whitted模型。1984年，美国Cornell大学和日本广岛大学的学者分别将热辐射工程中的辐射度方法引入到计算机图形学中，用辐射度方法成功地模拟了理想漫反射表面间的多重漫反射效果。1986年，美国科学基金会（NSF）专门召开了一次研讨会，会上提出了“科学计算可视化（VisualizationinScientificComputing，简称为ViSC）”。图形学发展历史80s1980年Whitted提出了一个光透视93SIGGRAPHSIGGRAPH会议，“TheSpecialInterestGrouponComputerGraphicsandInteractiveTechniques”ACMSIGGRAPH会议是计算机图形学最权威的国际会议，每年在美国召开，参加会议的人在50,000人左右。世界上没有第二个领域每年召开如此规模巨大的专业会议，SIGGRAPH会议很大程度上促进了图形学的发展。

1974年在Colorado大学召开了第一届SIGGRAPH年会。因为每年只录取大约50篇论文，在ComputerGraphics杂志上发表，因此论文的学术水平较高，基本上代表了图形学的主流方向。SIGGRAPHSIGGRAPH会议，“TheSpec94虚拟现实虚拟现实技术就是利用计算机生成一个逼真的三维虚拟环境，通过自然技能使用传感设备与之相互作用的新技术。它与传统的模拟技术完全不同，是将模拟环境、视景系统和仿真系统合三为一，利用头盔显示器、图形眼镜、数据服、立体声耳机、数据手套及脚踏板等传感装置，把操作者与计算机生成的三维虚拟环境连结在一起。与传统计算机相比，虚拟现实系统具有三个重要特征：临境性、交互性、想象性。虚拟现实建模语言VRML是描述虚拟环境中场景的一种标准，可以利用它在INTERNET建立交互式的三维多媒体环境。VRML的基本特征包括分布式、交互式、平台无关、三维、多媒体集成和逼真自然等，国际标准化组织1998年1月正式将其批准为国际标准。虚拟现实虚拟现实技术就是利用计算机生成一个逼真的三维虚拟环境95计算机艺术可用于美术创作的软件很多，如二维平面的画笔程序(如CorelDraw，Photoshop，PaintShop)、专门的图表绘制软件(如Visio)、三维建模和渲染软件包(如3DMAX，Maya)、以及一些专门生成动画的软件(如Alias，SoftImage)等。这些软件不仅提供多种风格的画笔、画刷，而且提供多种多样的纹理贴图，甚至能对图像进行雾化/变形等操作。很多功能是一个传统的艺术家无法实现也不可想象的。当然，传统艺术的一些效果也是上述软件所不能达到的。例如钢笔素描的效果，由于钢笔素描与传统的图形学绘制方法差别很大，所以研究起来难度也颇大，很多学者已在这方面做了卓有成效的工作，取得了一定的成果。计算机艺术可用于美术创作的软件很多，如二维平面的画笔程序(如96图形用户接口用户接口是人们使用计算机的第一观感。一个友好的图形化的用户界面能够大大提高软件的易用性，在DOS时代，计算机的易用性很差，编写一个图形化的界面要费去大量的劳动，过去软件中有60％的程序是用来处理与用户接口有关的问题和功能的。进入80年代后，随着Xwindow标准的面世，苹果公司图形化操作系统的推出，特别是微软公司Windows操作系统的普及，标志着图形学已经全面融入计算机的方方面面。目前几个大的软件公司都在研究下一代用户界面，开发面向主流应用的自然、高效多通道的用户界面。研究多通道语义模型、多通道整合算法及其软件结构和界面范式是当前用户界面和接口方面研究的主流方向，而图形学在其中起主导作用。图形用户接口用户接口是人们使用计算机的第一观感。一个友好的图97计算机图形学研究的基本问题图形描述基本几何：直线、圆弧等；高级几何：曲线、曲面等图形变换二、三维变换、三维到二维、观察流程、几何变换等图形运算基本几何间的计算、裁剪、布尔运算等图形显示/输出基本图形生成算法、消隐、绘图、光照模型等图形输入交互技术、参数化设计、造型技术等算法和算法复杂性分析空间和时间等计算机图形学研究的基本问题图形描述98两个核心问题如何建模交互技术曲线造型如何绘制光栅图形学光照模型裁剪计算颜色模型两个核心问题如何建模99图形描述一个物体的计算机描述叫做模型，它能被计算机所懂得，并在一定的条件下（变换和投影）被转换成相应的图形在显示屏幕或绘图机上输出；而图形是模型的一个具体可见像，是人们所看到的模型的表征。在三维空间，描述的是几何形体和几何曲面，只有在平面上，它才是人们通常所称的图形。图形描述一个物体的计算机描述叫做模型，它能被计算机所懂得，并100图形描述几何形体以封闭的表面表示，一般为一个由平面和曲面围成的多面体。一个几何形体在空间上应是完备的(几何性和拓扑性)，而且包含足够的用于推导的任何空间函数(如直线方程、平面方程、曲面构造等)以及进行各种形体运算与处理的信息。图形描述几何形体以封闭的表面表示，一般为一个由平面和曲面围成101图形描述在多面体表示中，有关的基本元素（体、面、环、棱和顶点）的信息分为二大类：几何信息：用以确定每个分量在欧氏空间中的几何位置(如点坐标)和描述(如平面方程系数)；拓扑信息：用来定义几何元素的数目及相互间的连接关系。几何信息只考虑点、线和无限面。拓扑信息将点看作顶点，将线限制为棱(线段)，由外环和内环定义出面和内孔。一个完全的三维几何体描述，几何信息和拓扑信息两者都是必要的图形描述在多面体表示中，有关的基本元素（体、面、环、棱和顶点102图形描述描述一个多面体各元素之间的拓扑关系可以互相推导。故理论上只需存储一种关系就行了，但由于关系的推导要付出代价，所以一般的系统常同时存储若于种拓扑关系。这些拓扑关系，既要足够地表示出几何形体的构造，又要尽量压缩信息的存储量，且要便于检索和修改，而十分重要的是要便于计算机的自动生成。图形描述描述一个多面体各元素之间的拓扑关系可以互相推导。故理103图形描述对于曲表面的几何形体，需分别研究自由曲线和自由曲面的建立；用于插值和数学放样的三次样条函数是应用得最早研究得最详尽的一种。Bezier曲线和曲面与B样条曲线和曲面是在计算机辅助几何设计应用最广的曲线和曲面几何构型方法。关于这些方面的研究，至今仍在继续发展中。图形描述对于曲表面的几何形体，需分别研究自由曲线和自由曲面的104图形描述平面上图形的描述是基于直线和圆弧的描述。仅用这两种基本几何元素就可构成平面上的任何图形。因而直线段和圆弧段也叫基本几何段，本课程将详加阐述。数据结构技术在图形描述中起着关键的作用。线性链接表、树结构、堆栈、队列等将广泛应用于几何模型的描述、运算和显示中。图形描述平面上图形的描述是基于直线和圆弧的描述。仅用这两种基105图形输入图形输入需要解决的问题是：交互输入的方法。工程设计图纸直接输入（矢量识别）的方法。将自由手书的立体构造或三视图重构的方法。计算机自动生成方法。从物体的多幅深度图像重建三维几何模型。通过三维激光扫描仪在物体表面测得一些离散点，再用重构算法生成网格模型等等。图形输入图形输入需要解决的问题是：106图形输入图形输入的常规方法是将事先写好的源程序(指令)在屏幕上输入，即所谓的编程输入，使得人、机之间的交互作用缓慢。对于工程上常用的一类规格化图形，可以编制一个通用程序，采用格式数据输入的办法得到图形。但是在处理三维的，或是形状复杂的物体时还有较多的困难，输入数据太多就是一个障碍。图形输入图形输入的常规方法是将事先写好的源程序(指令)在屏幕107图形输入除了这种图形的直接输入之外，通过对基本体元的构型产生新的、复杂的三维物体也是一种输入的手段，当然这需要涉及更多的研究。从计算机图形学的发展情况看，对图形输出的研究多于对图形输入的研究，许多人往往被计算机输出的美妙图形所迷惑，却看不到为得到这些图形所做的大量数据输入的准备工作。图形输入的工作量和难度并不亚于几何算法和图形输出。随着时间的推移，图形输入将越来越成为计算图形学应用中的主要障碍。图形输入除了这种图形的直接输入之外，通过对基本体元的构型产生108图形变换一个图形系统需具有图形变换的功能。这种变换包括二维变换、三维变换和三维向二维的变换三种。对应于几何元素及其选定的坐标系来说，则包括几何变换和坐标系变换两种。这些变换系统称为图形变换。在构造、产生、处理和输出图形的各个环节，图形变换起着重要的作用。图形变换一个图形系统需具有图形变换的功能。这种变换包括二维变109图形变换人们可以直接定义一个几何图形或几何体，也可通过对某些几何体的变换去构造新的几何体或其中的某个部份。这种变换可以是平移、放大(缩小)、旋转、反射、错切等。一个三维场景通常就是由一些基本几何元素通过上述操作构造的。例如，可以通过平移的办法装配一幢建筑物的大部份窗子，这使得图形输入大为简化。在进行图形处理的过程中，还可以放大一个图形以便使其某一部份能更清楚地显示；缩小图形以便看到图形更多的部份。图形变换人们可以直接定义一个几何图形或几何体，也可通过对某些110图形变换在显示或绘制一个环境的时候，需要将三维信息映射到二维屏幕上。轴测投影、平行投影和透视投影用于完成这项工作。在视点改变得非常快或物体相对运动的应用场合，变换必须反复运用。因此，找到一个有效的方法去实现图形变换是十分重要的。图形变换在显示或绘制一个环境的时候，需要将三维信息映射到二维111图形变换采用向量、矩阵和齐次坐标的形式去描述图形变换是一种比较好的办法，它允许将线性代数的一些基本理论应用到图形变换中。例如一个矩阵对应于一个变换，图形的连续变换可由矩阵的相乘实现，而逆矩阵对应于一个逆变换。所有的变换都基于点变换，例如对一条线段的变换只需考虑其两个端点的变换就可以了。基本几何元素描述的变换也和点的变换有密切的联系。例如描述一条直线的方程系数在不同坐标下的关系也可由点变换的相应变换矩阵求得。图形变换采用向量、矩阵和齐次坐标的形式去描述图形变换是一种比112图形运算在三维空间，图形的运算是一种几何形体的运算，它是CAGD的一个重要操作，这种操作通常叫做物体造型，或几何造型。设计人员可通过修改立方体，圆柱体之类的基本体元来生成形体。例如通过缩放，通过用集合论中的并、交、非、差等概念所进行的各种布尔运算把一些基本物体体元组合起来。设计人员的职责是把各体元正确地定位下来，使得这些运算能进行下去。另一方面几何造型系统还负责估计各体元之间的相互作用，各种相交出现的位置以及它们之间的相互关系，以确保生成法定的三维形体。系统还必须正确地、在计算机限制下内尽可能精确地完成相交分析。图形运算在三维空间，图形的运算是一种几何形体的运算，它是CA113图形运算几何造型系统常处理一些比较简单的体元：立方体、圆柱体、楔、嵌条，以直线或圆弧为边界的薄片等。所涉及的线和面在几何上是简单的直线、圆弧、平面和圆柱面，处理这些由一个正确的方式构造出来的物体的相交，从概念上是比较容易的。但主要困难在于：虽然几何简单，但多个元素的拼合却是复杂的。故对于确实复杂的形体的组合问题，所需的几何算法的效率就变得十分重要，需进行几何复杂性分析。图形运算几何造型系统常处理一些比较简单的体元：立方体、圆柱体114图形运算几何造型系统较之早期图形系统的显著优越之处在于：无需人为干预就能预定形体与执行一连串运算。即具有高度自动化的图形定义或构造、产生处理或演变功能。几何元素的定向在图形运算中起着相当大的作用。例如平面图形的几何运算就是建立在以向量为基本几何元素的环的基础上实现的。直线和圆弧这两种基本几何段的相贯运算是平面图形运算的基础，保证这些算法的准确性，提高这些算法的效率是计算机图形系统一项基础性的工作。图形运算几何造型系统较之早期图形系统的显著优越之处在于：无需115图形输出图形输出是人—机交互系统中人们能够得到的最直观的结果。它直接向人们显示出计算机图形系统的效果。相对而言，图形输出计算机图学中研究得最早、最深入、解决得最好的一部份工作。图形输出图形输出是人—机交互系统中人们能够得到的最直观的结116图形输出一个物体的制造者可以从一张多视图的图样里了解到许多内容。因此，一个能在二维参考平面里提供综合的，绘制直线和曲线的系统也就提供了画出一个复杂而详细的图形或物体的基础。但是，图形只是三维物体的某一个特定的不完整的表示。而物体有一种图里没有的，与众不同的特性——完全的三维定义。人们可以随意地在三维空间中把物体旋转和平移以及物体的综合，但一般不能用图形做到这一点。图形输出一个物体的制造者可以从一张多视图的图样里了解到许多内117图形输出基本几何（点、直线、圆及圆弧等）和文字的光栅化显示，几何裁剪算法基本几何的描述、相交算法，曲线拟合和双圆弧逼近算法，动态显示的插值算法。图形显示中的裁剪算法，通常称为窗口算法；隐藏线、隐藏面消除算法。光照模型及算法。纹理贴图；大规模场景显示算法；图形显示软件和打印机、绘图机等的图形输出后处理软件等等。图形输出基本几何（点、直线、圆及圆弧等）和文字的光栅化显示，118几何算法、几何复杂性和计算效率一个动画程序，一个游戏程序，用户的起码要求是“流畅”；支撑它的是几何算法，几何复杂性问题及计算的效率。许多通过交互设计各种形体的系统，其成功的主要断依据是凭视觉。例如套料问题，这在造船、服装等行业是极为有用的，然而至今存在的系统还是由人机交互作用来完成。而几何造型系统在相交问题的正确算法和处理组合比较复杂问题的能力，这种系统的发展表明，需要多多研究几何算法。几何算法、几何复杂性和计算效率一个动画程序，一个游戏程序，用119几何算法、几何复杂性和计算效率几何相交问题在几何算法中占有较大的比重，在平面上，它处理直线和直线，圆弧和直线，圆弧和圆弧等基本几何的相交，在三维空间则是处理直线和平面，平面和平面的相互关系。但是，并不是所有的处理直线和直线的相交都是简易的。例如，考虑两个平面多边形相交的状态，按照Shamos(1978)算法，如果这两个多边形是凸的，对于n条边的多边形可以用O(n)的时间解决这个问题。而对于两个任意非凸多边形，为解决这个问题要花O(n2)的时间，可能形成达n2/4个不相叠的凸多边形。几何算法、几何复杂性和计算效率几何相交问题在几何算法中占有较120几何算法、几何复杂性和计算效率观察一个时间复杂性的例子：问题：设给定n个已经排序的数的队列，现在要插入一个新的数到这个队列中，并保持队列原有的次序，几何复杂性为O(n)次主算。应用二分法，可降为O(log2n)次。如果不计检索到元素后对其处理所花费的计算时间，而只对n的步数计算时间，那末当n=60时：n：6×10-5秒N^2：36×10-4秒N^3：216×10-3秒N^5：13分钟2^n：366世纪3^n：1.3×1013世纪几何算法、几何复杂性和计算效率观察一个时间复杂性的例子：121几何算法、几何复杂性和计算效率降低几何复杂性是几何算法的一个努力目标，它可以提高算法的效率。过去开发仅仅能“工作”的算法就常常足够了，即使在某些情况下效率低也无妨。随着使用计算机进行几何设计的增加，以及要解决问题的范围之扩大，效率、精度和正确性的问题就变得非常重要了。几何算法、几何复杂性和计算效率降低几何复杂性是几何算法的一个122计算机图形学的相关开发技术计算机图形学经过几十年的发展，已经达到了比较高的水平，目前已有若干图形学软件开发技术。利用这些开发技术，编写图形程序就容易多了，不必从底层开始，而只需将精力集中到图形程序本身上。计算机图形学的相关开发技术计算机图形学经过几十年的发展，已经123OpenGLOpenGL：OpenGL是OpenGraphicsLib的缩写，是一套三维图形处理库，也是该领域的工业标准。OpenGL源于SGI公司为其图形工作站开发的IRISGL，在跨平台移植过程中发展成为OpenGL。OpenGL被设计成独立于硬件，独立于窗口系统的，在运行各种操作系统的各种计算机上都可用，并能在网络环境下以客户/服务器模式工作，是专业图形处理、科学计算等高端应用领域的标准图形库。OpenGLOpenGL：OpenGL是OpenGraph124OpenGLMicrosoft、SGI、IBM、DEC、SUN、HP等大公司都采用了OpenGL作为三维图形标准。许多软件厂商也纷纷以OpenGL为基础开发出自己的产品，包括动画制作软件SoftImage和3DStudioMAX、仿真软件OpenInventor、VR软件WorldToolKit、CAD软件Pro/Engineer、GIS软件ARC/INFO等等。OpenGL实际上是一个开放的三维图形软件包，它独立于窗口系统和操作系统，以它为基础开发的应用程序可以十分方便地在各种平台间移植；OpenGL与C++紧密接合，便于实现图形的相关算法，并可保证算法的正确性和可靠性；OpenGL使用简便，效率高。OpenGLMicrosoft、SGI、IBM、DEC、SU125ACISACIS是美国SpatialTechnology公司推出的三维几何引擎，为各种3D造型应用的开发提供了几何造型平台，目前的最高本版已经到了R13。ACIS能够安装在多种平台上，包括Windows,Linux,Unix,Solaris,AIX等。ACIS采用了软件组件技术，用C++技术构造，它包含一整套的C++类和函数，开发人员可以使用这些类和函数构造一个面向终端用户的2/3维软件系统。ACIS是一个基于边界表示法的造型引擎，集线框、曲面和实体造型于一体，并允许这三种表示共存于统一的数据结构中。ACISACIS是美国SpatialTechnology公126ACISACIS系统的造型方法有：覆盖技术(covering