计算机图形学是随着计算机及其外围设备而产生和发展起来的,作为计算机科学与技术学科的一个独立分支已经历了近40年的发展历程。一方面,作为一个学科,计算机图形学在图形基础算法、图形软件与图形硬件三方面取得了长足的进步,成为当代几乎所有科学和工程技术领域用来加强信息理解和传递的技术和工具。另一方面,计算机图形学的硬件和软件本身已发展成为一个巨大的产业。1.计算机图形学活跃理论及技术(1)分形理论及应用分形理论是当今世界十分活跃的新理论。作为前沿学科的分形理论认为,大自然是分形构成的。大千世界,对称、均衡的对象和状态是少数和暂时的,而不对称、不均衡的对象和状态才是多数和长期的,分形几何是描述大自然的几何学。作为人类探索复杂事物的新的认知方法,分形对于一切涉及组织结构和形态发生的领域,均有实际应用意义,并在石油勘探、地震预测、城市建设、癌症研究、经济分析等方面取得了不少突破性的进展。分形的概念是美籍数学家曼德布罗特()率先提出的。1967年他在美国《科学》杂志上发表了题为《英国的海岸线有多长?》的著名论文。??海岸线作为曲线,其特征是极不规则、极不光滑的,呈现极其蜿蜒复杂的变化。它无法用常规的、传统的几何方法描述。我们不能从形状和结构上区分这部分海岸与那部分海岸有什么本质的不同,这种几乎同样程度的不规则性和复杂性,说明海岸线在形貌上是自相似的,也就是部局形态和整体形态的相似。在没有建筑物或其他东西作为参照物时,在空中拍摄的100公里长的海岸线与放大了的10公里长海岸线的两张照片,看上去十分相似。??曾有人提出了这样一个显然是荒谬的命题:“英国的海岸线的长度是无穷大。”其论证思路是这样的:海岸线是破碎曲折的,我们测量时总是以一定的尺度去量得某个近似值,例如,每隔100米立一个标杆,这样,我们测得的是一个近似值,是沿着一条折线计算而得出的近似值,这条折线中的每一段是一条长为100米的直线线段。如果改为每10米立一个标杆,那么实际量出的是另一条折线的长度,它的每一个片段长10米。显然,后一次量出的长度将大于前一次量出的长度。如果我们不断缩小尺度,所量出的长度将会越来越大。这样一来,海岸线的长度不就成为无穷大了吗???为什么会出现这样的结论呢?曼德布罗特提出了一个重要的概念:分数维,又称分维。一般来说,维数都是整数,直线线段是一维的图形,正方形是二维的图形。在数学上,把欧氏空间的几何对象连续地拉伸、压缩、扭曲,维数也不变,这就是拓扑维数。然而,这种维数观并不能解决海岸线的长度问题。曼德布罗特是这样描述一个绳球的维数的:从很远的距离观察这个绳球,可看作一点(零维);从较近的距离观察,它充满了一个球形空间(三维);再近一些,就看到了绳子(一维);再向微观深入,绳子又变成了三维的柱,三维的柱又可分解成一维的纤维。那么,介于这些观察点之间的中间状态又如何呢?显然,并没有绳球从三维对象变成一维对象的确切界限。英国的海岸线为什么测不准?因为欧氏一维测度与海岸线的维数不一致。根据曼德布罗特的计算,英国海岸线的维数为。有了分维的概念,海岸线的长度就可以确定了。??1975年,曼德布罗特发现:具有自相似性的形态广泛存在于自然界中,如连绵的山川、飘浮的云朵、岩石的断裂口、布朗粒子运动的轨迹、树冠、花菜、大脑皮层……曼德布罗特把这些部分与整体以某种方式相似的形体称为分形(Fractal),这个单词由拉丁语Frangere衍生而成,该词本身具有“破碎”、“不规则”等含义。??曼德布罗特的研究中最精彩的部分是1980年他发现的并以他的名字命名的集合,他发现整个宇宙以一种出人意料的方式构成自相似的结构。Mandelbrot集合图形的边界处,具有无限复杂和精细的结构。在此基础上,形成了研究分形性质及其应用的科学,称为分形理论(Fractal theory)或分形几何学(Fractal geometry)。分形的特点和理论贡献??数学上的分形有以下几个特点: ??(1)具有无限精细的结构; ??(2)比例自相似性;??(3)一般它的分数维大于它的拓扑维数;??(4)可以由非常简单的方法定义,并由递归、迭代产生等。 ??(1)(2)两项说明分形在结构上的内在规律性。自相似性是分形的灵魂,它使得分形的任何一个片段都包含了整个分形的信息。第(3)项说明了分形的复杂性,第(4)项则说明了分形的生成机制。??我们把传统几何的代表欧氏几何与以分形为研究对象的分形几何做一比较,可以得到这样的结论:欧氏几何是建立在公理之上的逻辑体系,其研究的是在旋转、平移、对称变换下各种不变的量,如角度、长度、面积、体积,其适用范围主要是人造的物体;而分形由递归、迭代生成,主要适用于自然界中形态复杂的物体,分形几何不再以分离的眼光看待分形中的点、线、面,而是把它们看成一个整体。??我们可以从分形图案的特点去理解分形几何。分形图案有一系列有趣的特点,如自相似性、对某些变换的不变性、内部结构的无限性等。此外,分形图案往往和一定的几何变换相联系,在一些变化下,图案保持不变,从任意的初始状态出发,经过若干次的几何变换,图形将固定在这个特定的分形图案上,而不再发生变化。自相似原则和迭代生成原则是分形理论的重要原则。 ??分形理论发展了维数的概念。在发现分数维以前,人们习惯于将点定义为零维,直线为一维,平面为二维,空间为三维,爱因斯坦在相对论中引入时间维,就形成四维时空。对某一问题给予多方面的考虑,可建立高维空间,但都是整数维。??分形是20世纪涌现出的新的科学思想和对世界认识的新视角。从理论上讲,它是数学思想的新发展,是人类对于维数、点集等概念的理解的深化与推广。同时它又与现实的物理世界紧密相连,成为研究混沌(Chaos)现象的重要工具。众所周知,对混沌现象的研究正是现代理论物理学的前沿和热点之一。??由于分形的研究,人们对于随机性和确定性的辩证关系有了进一步的理解。同样对于过程和状态的联系,对于宏观和微观的联系,对于层次之间的转化,对于无限性的丰富多采,也都产生了有益的影响。??分形理论还是非线性科学的前沿和重要分支,作为一种方法论和认识论,其启示是多方面的:一是分形整体与局部形态的相似,启发人们通过认识局部来认识整体,从有限中认识无限;二是分形揭示了介于整体与部分、有序与无序、复杂与简单之间的新形态和秩序;三是分形从特定层面揭示了世界普遍联系和统一的图景。分形学的应用领域??除了理论上的意义之外,在实际应用中,分形也显示了巨大的潜力,它已经在许多领域中得到有效的应用,其应用范围之广、效益之明显远远超过了十几年前的任何预测。目前大量分形方法的应用案例层出不穷。这些案例涉及的领域包括:生命过程进化,生态系统,数字编码和解码,数论,动力系统,理论物理(如流体力学和湍流) 等方面,此外,还有人利用分形学做城市规则和地震预报。??分形技术在数据压缩中的应用是一个非常典型的例子。美国数学会会刊在1996年6月的刊物上发表了巴斯利的文章《利用分形进行图形压缩》,他把分形用于光盘制作的图形压缩中。一般来说,我们总是把一个图形作为像素的集合来加以存储和处理。一张最普通的图片也常常涉及几十万乃至上百万像素,从而占据大量的存储空间,传输速度也大大受到限制。巴斯利运用了分形中的一个重要思想:分形图案是与某种变换相联系的,我们可以把任何一个图形看作是某种变换反复迭代的产物。因此,存储一个图形,只需存储有关这些变换过程的信息,而无需存储图形的全部像素信息。只要找到这个变换过程,图形就可以准确地再现出来,而不必去存储大量的像素信息。使用这种方法,在实际的应用中,已经达到了压缩存储空间至原来1/8的效果。??近年来,由分形理论发展起来的分形艺术(Fractal Art,FA),在表现形式和分形几何的理解等方面亦取得了突破性的进展。分形艺术是二维可视艺术,在许多方面类似于摄影。分形图像作品一般是通过计算机屏幕和打印机来展现的。分形艺术中的另一个重要部分便是分形音乐,分形音乐是由一个算法的多重迭代产生的。自相似是分形几何的本质,有人利用这一原理来建构一些带有自相似小段的合成音乐,主题在带有小调的三番五次的反复循环中重复,在节奏方面可以加上一些随机变化。我们常见的计算机屏幕保护程序,许多也是通过分形计算而得来的。进入1990年代以来,人们开始越来越多地利用这一理论研究经济领域的一些问题,主要集中在对金融市场(如股票市场、外汇市场等)的研究。操纵者可以通过在若干时间点上的操纵使股价在微观尺度上发生所希望的变化;从时间的宏观尺度上来看,要使股价发生所希望的变化,就要求操纵者具有相当的经济实力。从分形的角度来看,股票价格具有分形特征。一方面,股价具有复杂的微观结构;另一方面,它具有对时间的标度不变性,即在不同的观测尺度下具有相似的结构,其结构是复杂和简单、不规则和有序的统一。对股价操纵者来说,要在单个时间点上影响股价并不难,即使是在大的时间尺度上影响股价也是有可能的,但是要想通过人为的操纵,在影响股价的同时,保持股价在时间的微观和宏观尺度上的一致性,在技术上就会显得非常困难。(2) 曲面造型技术。它是计算机图形学和计算机辅助几何设计(Computer Aided Geometric Design)的一项重要内容,主要研究在计算机图象系统的环境下对曲面的表示、设计、显示和分析。它肇源于飞机、船舶的外形放样工艺,由Coons、Bezier等大师于六十年代奠定理论基础。经三十多年发展,现在它已经形成了以Bezier和B样条方法为代表的参数化特征设计和隐式代数曲面表示这两类方法为主体,以插值(Interpolation) 、拟合(Fitting) 、逼近(Approximation)这三种手段为骨架的几何理论体系。随着计算机图形显示对于真实性、实时性和交互性要求的日益增强,随着几何设计对象向着多样性、特殊性和拓扑结构复杂性靠拢的趋势的日益明显,随着图形工业和制造工业迈向一体化、集成化和网络化步伐的日益加快,随着激光测距扫描等三维数据采样技术和硬件设备的日益完善,曲面造型在近几年来得到了长足的发展。这主要表现在研究领域的急剧扩展和表示方法的开拓创新。一.从研究领域来看,曲面造型技术已从传统的研究曲面表示、曲面求交和曲面拼接,扩充到曲面变形、曲面重建、曲面简化、曲面转换和曲面位差。曲面变形(Deformation or Shape Blending): 传统的非均匀有理B样条(NURBS)曲面模型,仅允许调整控制顶点或权因子来局部改变曲面形状,至多利用层次细化模型在曲面特定点进行直接操作;一些简单的基于参数曲线的曲面设计方法,如扫掠法(Sweeping),蒙皮法(Skinning),旋转法和拉伸法,也仅允许调整生成曲线来改变曲面形状。计算机动画业和实体造型业迫切需要发展与曲面表示方式无关的变形方法或形状调配方法,于是产生了自由变形(FFD)法,基于弹性变形或热弹性力学等物理模型(原理)的变形法,基于求解约束的变形法,基于几何约束的变形法等曲面变形技术和基于多面体对应关系或基于图象形态学中Minkowski和操作的曲面形状调配技术。最近,笔者及其学生刘利刚首创活动局部球面坐标插值的新思想,给出了空间点集内在变量的完整数学描述,从几何内在解的角度,设计了三维多面体和自由曲面形状调配的一整套快速有效的算法,画面流畅,交互实时,对三维曲面变形的技术难题实现了突破。 曲面重建(Reconstruction):在精致的轿车车身设计或人脸-类雕塑曲面的动画制作中,常用油泥制模,再作三维型值点采样。在医学图象可视化中,也常用CT切片来得到人体脏器表面的三维数据点。从曲面上的部分采样信息来恢复原始曲面的几何模型,称为曲面重建。采样工具为:激光测距扫描器,医学成象仪,接触探测数字转换器,雷达或地震勘探仪器等。根据重建曲面的形式,它可分为函数型曲面重建和离散型曲面重建这两类。 曲面简化(Simplification):与曲面重建一样,这一研究领域目前也是国际热点之一。其基本思想在于从三维重建后的离散曲面或造型软件的输出结果(主要是三角网格)中去除冗余信息而又保证模型的准确度,以利于图形显示的实时性、数据存储的经济性和数据传输的快速性。对于多分辨率曲面模型而言,这一技术还有利于建立曲面的层次逼近模型,进行曲面的分层显示,分层传输和分层编辑。具体的曲面简化方法有:网格顶点剔除法,网格边界删除法,网格优化法,最大平面逼近多边形法以及参数化重新采样法。曲面转换(Conversion):同一张曲面可以表为不同的数学形式,这一思想不仅具有理论意义,而且具有工业应用的现实意义。例如,NURBS这种参数有理多项式曲面虽然包括了参数多项式曲面的一切优点,但也存在着微分运算繁琐费时、积分运算无法控制误差的局限性。而在曲面拼接及物性计算中,这两种运算是不可避免的。这就提出了把一张NURBS曲面转化成近似的多项式曲面的问题。同样的要求更体现在NURBS曲面设计系统与多项式曲面设计系统之间的数据传递和无纸化生产的工艺过程中。再如,在两张参数曲面的求交运算中,如果把其中一张曲面的NURBS形式转化为隐式,就容易得到方程的数值解。近几年来,国际图形界对曲面转换的研究主要集中在以下几方面:NURBS曲面用多项式曲面来逼近的算法及收敛性;Bezier曲线曲面的隐式化及其反问题;CONSURF飞机设计系统的Ball曲线向高维的各种推广形式的比较及互化;有理Bezier曲线曲面的降阶逼近算法及误差估计;NURBS曲面在三角域上与矩形域上的互相快速转化等。曲面位差(Offset):也称为曲面等距性,它在计算机图形及加工中有广泛应用,因而成为这几年的热门课题之一。例如,数控机床的刀具路径设计就要研究曲线的等距性。但从数学表达式容易看出,一般而言,一条平面参数曲线的等距曲线不再是有理曲线,这就越出了通用的NURBS系统的使用范围,造成了软件设计的复杂性和数值计算的不稳定。二.从表示方法来看,以网格细分(Subdivision)为特征的离散造型与传统的连续造型相比,大有后来居上的创新之势。而且,这种曲面造型方法在生动逼真的特征动画和雕塑曲面的设计加工中如鱼得水,得到了高度的运用。 在1998年荣获奥斯卡大奖的电影作品中,有一个短片赫然在列,这就是美国著名的Pixar动画电影制片厂选送的作品"Geri's Game"。动画片描述了一个名叫Geri的老头,在公园里自己与自己下国际象棋,千方百计想取胜的诙谐故事。画面中人物和景色的造型细致生动,与故事情节浑然一体,使观众得到真正的美学享受。而这部动画片制作中的设计者,就是以上论文的作者,著名的计算机图形学家。DeRose在SIGGRAPH'98大会上报告的论文讲到了选用C-C细分曲面作为Geri老头特征造型模型的背景。他指出,NURBS尽管早已被国际标准组织ISO作为定义工业产品数据交换的STEP标准,在工业造型和动画制作中得到了广泛的应用,但仍然存在着局限性。单一的NURBS曲面,如其他参数曲面一样,限于表示在拓扑上等价于一张纸,一个圆柱面或一个圆环面的曲面,不能表示任意拓扑结构的曲面。为了表达特征动画中更复杂的形状,如人的头,人的手或人的服饰,我们面临着一场技术挑战。当然,我们可以用最普通的复杂光滑曲面的造型方法,例如对NURBS的修剪(Trimming)来对付。确实,目前已经存在一些商用系统,诸如Alias-Wavefront和SoftImage等可以做到这一点,但是它们至少会遭遇到以下的困难:第一,修剪是昂贵的,而且有数值误差;第二,要在曲面的接缝处保持光滑,即使是近似的平滑也是困难的,因为模型是活动的。而细分曲面有潜力克服以上两个困难,它们无须修剪,没有缝,活动模型的平滑度被自动地保证。DeRose成功地应用了C-C的细分曲面造型法,同时发明了构造光滑的变半径的轮廓线及合成物的实际技术,提出了在服饰模型中碰撞检测的有效新算法,构造了关于细分曲面的光滑因子场方法。凭借这些数学和软件基础,他形象逼真地表现了Geri老头的头壳,手指和衣服,包括茄克衫,裤子,领带和鞋子。这些都是传统的NURBS连续曲面造型所不易做到的。那么,C-C细分曲面是怎样构造的呢?它与传统的Doo-Sabin细分曲面异曲同工,都是从一个称之为控制网格(网格多半可用激光从手工模型上输入)的多面体开始,递归地计算新网格上的每个顶点,这些顶点都是原网格上某几个顶点的加权平均。如果多面体的一个面有n条边,细分一次后,这个面就会变成n个四边形。随着细分的不断进行,控制网格就被逐渐磨光,其极限状态就是一张自由曲面。它是无缝的,因而是平滑的,即使模型是活动的。这种方法显著地压缩了设计和建立一个原始模型的时间。更重要的,允许原始模型局部地精制化。这就是它优于连续曲面造型方法之处. C-C细分是基于四边形的,而Loop曲面(1987年),蝶形曲面(1990年)是基于三角形的。它们都一样受到当今图形工作者的重用。(3)计算机辅助设计与制造(CAD/CAM)。 这是一个最广泛,最活跃的应用领域。计算机辅助设计(Computer Aided Design,CAD)是利用计算机强有力的计算功能和高效率的图形处理能力,辅助知识劳动者进行工程和产品的设计与分析,以达到理想的目的或取得创新成果的一种技术。它是综合了计算机科学与工程设计方法的最新发展而形成的一门新兴学科。计算机辅助设计技术的发展是与计算机软件、硬件技术的发展和完善,与工程设计方法的革新紧密相关的。采用计算机辅助设计已是现代工程设计的迫切需要。CAD技术目前已广泛应用于国民经济的各个方面,其主要的应用领域有以下几个方面。1.制造业中的应用CAD技术已在制造业中广泛应用,其中以机床、汽车、飞机、船舶、航天器等制造业应用最为广泛、深入。众所周知,一个产品的设计过程要经过概念设计、详细设计、结构分析和优化、仿真模拟等几个主要阶段。 同时,现代设计技术将并行工程的概念引入到整个设计过程中,在设计阶段就对产品整个生命周期进行综合考虑。当前先进的CAD应用系统已经将设计、绘图、分析、仿真、加工等一系列功能集成于一个系统内。现在较常用的软件有UG II、I-DEAS、CATIA、PRO/E、Euclid等CAD应用系统,这些系统主要运行在图形工作站平台上。在PC平台上运行的CAD应用软件主要有Cimatron、Solidwork、MDT、SolidEdge等。由于各种因素,目前在二维CAD系统中Autodesk公司的AutoCAD占据了相当的市场。2.工程设计中的应用 CAD技术在工程领域中的应用有以下几个方面: (1)建筑设计,包括方案设计、三维造型、建筑渲染图设计、平面布景、建筑构造设计、小区规划、日照分析、室内装潢等各类CAD应用软件。(2)结构设计,包括有限元分析、结构平面设计、框/排架结构计算和分析、高层结构分析、地基及基础设计、钢结构设计与加工等。(3)设备设计,包括水、电、暖各种设备及管道设计。(4)城市规划、城市交通设计,如城市道路、高架、轻轨、地铁等市政工程设计。(5)市政管线设计,如自来水、污水排放、煤气、电力、暖气、通信(包括电话、有线电视、数据通信等)各类市政管道线路设计。(6)交通工程设计,如公路、桥梁、铁路、航空、机场、港口、码头等。 (7)水利工程设计,如大坝、水渠、河海工程等。(8)其他工程设计和管理,如房地产开发及物业管理、工程概预算、施工过程控制与管理、旅游景点设计与布置、智能大厦设计等。3.电气和电子电路方面的应用 CAD技术最早曾用于电路原理图和布线图的设计工作。目前,CAD技术已扩展到印刷电路板的设计(布线及元器件布局),并在集成电路、大规模集成电路和超大规模集成电路的设计制造中大显身手,并由此大大推动了微电子技术和计算及技术的发展。4.仿真模拟和动画制作 应用CAD技术可以真实地模拟机械零件的加工处理过程、飞机起降、船舶进出港口、物体受力破坏分析、飞行训练环境、作战方针系统、事故现场重现等现象。在文化娱乐界已大量利用计算机造型仿真出逼真的现实世界中没有的原始动物、外星人以及各种场景等,并将动画和实际背景以及演员的表演天衣无缝地合在一起,在电影制作技术上大放异彩,拍制出一个个激动人心的巨片。5.其他应用CAD技术除了在上述领域中的应用外,在轻工、纺织、家电、服装、制鞋、医疗和医药乃至体育方面都会用到CAD技术 CAD标准化体系进一步完善;系统智能化成为又一个技术热点;集成化成为CAD技术发展的一大趋势;科学计算可视化、虚拟设计、虚拟制造技术是20世纪90年代CAD技术发展的新趋向。经过了一阶段计算机图形学的学习,对于图形学中基本图形的生成算法有了一定的了解。深度研究图形学,需要高深的数学知识,且每一个细化的方向需要的知识也不一样。图形学是计算机科学与技术学科的活跃前沿学科,被广泛的应用到生物学、物理学、化学、天文学、地球物理学、材料科学等领域。我深深感到这门学科涉及的领域之广是惊人的,可以说博大精深。