前言:
图形是传递信息*主要的媒体之一,计算机图形学的发展和应用在某种意义上已成为计算机软、硬件发展水平的标志。它已成为一门成熟的学科,是信息技术中不可缺少的重要内容和发展基石。“计算机图形学”课程也已成为大学计算机、机械等相关学科的一门主干课程。
本书对一些被普遍认同的计算机图形学领域的理论、技术和算法作了介绍,主要定位于作为计算机图形学(Computer Graphics,CG)课程的教材,兼作计算机辅助设计(Computer Aided Design,CAD)的科研参考书。
理论教学与应用实践应各有自己的定位和目标,前者培养学生解决问题的思维方式,后者提高学生解决问题的能力。本书强调了对基础理论、算法、几何模型与数据结构等内容的叙述,并努力保证它们的正确性,尽可能使叙述准确、清晰。
基础理论。计算机图形学理论与计算机科学中的算法设计、算法分析、数据结构等学科密切相关。本书强调了对理论核心思想的阐述,用通俗易懂的语言,简明、透彻地阐明这些理论*本质的思想,附以精心设计的图示形式,力图使读者在较短的时间内掌握这些基本理论。
算法。本书重视原理上的阐述,从理论上分析各种算法的原理、可行性及几何复杂性。对各种典型的算法尽可能比较多种可能的方案,分别指出它们的优缺点和应用场合(某些关键思想将被反复运用)。在如何提高算法的效率,保证算法的准确性、可靠性,怎样处理好多值问题以及如何组织好数据结构,提高程序设计的技巧等各方面都进行了仔细推敲。精心设计算法用例,提高算法的正确性、示范性和适应性。采用通用的、规范的描述形式,例如近于自然语言的算法描述、伪代码形式和全局性较好的框图形式等。
几何模型与数据结构。本书重视几何模型与数据结构的描述,便于读者更好地理解其背后的理论依据,也是对数据结构、程序设计等主干课程的一次深化和应用。
本书由13章正文和3篇附录构成。
第1章绪论。阐述了计算机图形学的学科定位;与其他学科CAD(及计算机绘图)、计算几何(Computer Geometry)、图像(Image)等的关系;叙述了计算机图形学中的一些基本概念、基本任务和它们在计算机图形学中的作用和地位;根据计算机图形学理论和技术的发展情况,简单地介绍了当前计算机图形学的相关开发技术。
第2章光栅图形学。对基本几何(直线、圆、椭圆等)光栅化的理论和算法,以及多边形填充、字符和汉字显示、反走样等计算机图形学的基本理论和算法作了详细的讲解。本章是计算机图形学的“入门”章,努力用浅显的语言和直观的图示形式阐述各种变量的几何意义,引导读者“入门”计算机图形学。这是吸引读者学好计算机图形学的关键。
第3章图形裁剪。本质上,图形裁剪应是一种几何计算问题,它与基本几何的光栅化算法不同,因此单列一章。
第4~8章涉及基本几何、二维几何、图形变换、三维几何和几何造型等各个方面。这些内容全部基于一套以向量几何为理论、以“方向性”概念为基础的几何计算理论体系。这套理论不仅统一了点、线(向量)、圆(弧)等基本几何及曲线和图形等的表示,并将基本几何与角度、距离、面积、分比、几何元素连接时的方向、封闭图形的边界走向等辅助几何(属性)有机地联系在一起。同时,引入“交点特征”的概念,有效地将二维布尔运算下降为一维向量计算、将三维布尔运算下降为二维布尔运算、将三维消隐算法*终归结为一维交集算法等等,从而使几何计算的复杂性大为简化,极大地提高了布尔运算、几何造型以及参数化设计等重大几何计算的稳定性和计算效率。
由此构筑了一种全新的、统一各种图形变换的坐标几何变换新机制,将平移、旋转、错切等坐标变换统一于基本几何体系,使基本几何与几何变换有机联系起来。阐明了“投影”和所谓“投影变换”的机理。研究了透视变换矩阵系数的意义和构造方法,使透视变换矩阵“量化”,以寻求在给定“灭点”的情况下定量求取透视变换系数的方法。
基本几何点、线(向量)、圆(弧)和面的定义以及它们之间的相互关系虽然并不复杂,但是作为描述所有图形和几何体的基础,其定义的严密性和算法的强壮性以及处理的效率却至关重要。需要深入地研究这些基本几何的有关问题,研究几何计算的稳定性和算法的复杂性理论,探索基本几何的方向定义以及它对几何计算效率的影响,建立对角度、距离、面积、分比、几何连接、封闭图形的边界走向等几何和属性概念的新涵义、新体系。
根据这套几何计算的理论体系,在第5章“二维几何”、第7章“三维几何”和第8章“几何造型”中叙述的经典几何算法:凸包算法、包容性测试算法、图形填充算法、2D和3D布尔运算算法、一维交集算法、消隐算法和三维几何造型算法等等,“交点特征”和“几何方向”的优越性发挥得****,使这些在基本几何新体系上构筑的典型几何算法变得出奇的简单。
整个体系显得较为完整、相对完善、使用方便。所有引入的理论和算法均提供了详细的例证,相信能被读者与同行接受和应用。
第9章讨论的光照模型是当前计算机图形学学科发展*快、*引人注目的方向,也是目前计算机图形学应用*广的部分。本书介绍了产生真实感图形的基本理论、原理、模型和算法。
先简单地介绍了光和颜色的基本概念,增加了“色彩应用”一节,供实现算法的读者构造出或热情、欢快、激动、奔放,或恬静、低沉、淡雅、严肃,或沉思、幽静、柔和,或朝气蓬勃、向上的作品来。
接着采用从简到繁,逐步深化的叙述方式,以环境光、漫反射和Lambert模型、镜面反射和Phong模型、透明模型的次序,自然地引出简单局部光照模型。
Gouraud明暗处理——光强插值算法和Phong明暗处理——法向插值算法从本质上讲是一种几何算法,本书将它单独列为“插值算法”一节。
光线跟踪是整体光照模型的基础,也是计算机图形学中典型的、较难的算法。本书强调了光线跟踪算法原理的叙述,配以插图,使读者更易理解。光线跟踪算法中的关键技术则强调了可能采用的策略,并未展开。例如几何求交的问题,在有些书中列举了直线与立方体、球和二次曲面等的求交算法,其实,这种求交工作是几何计算或数学问题,无法一一枚举,倒不如将它的本质列出,给读者一个自由发挥的天地。
阴影算法,本书强调了自身阴影和投射阴影的概念。
纹理问题,将颜色纹理和几何纹理概念分别予以讨论。
从工程应用的角度讲,曲线曲面可分成两大应用需求:设计型和拟合型。“设计型”往往是设计人员对其所设计的曲线(曲面)并无定量概念情况下于设计过程中的即兴发挥。“拟合型”曲线则是对已经存在的离散点列(例如通过测量或实验得到的一系列有序点列)构造出尽可能光滑的曲线或曲面,用以直观(而忠实)地反映出实验特性、变化规律和趋势等。
第10章介绍的由Bézier提出的一种由控制多边形定义曲线和曲面的方法是“设计型”曲线曲面的典型代表。曲线、曲面本身的基础理论和进一步的研究与发展应该属于计算机辅助几何设计(Computer Aided Geometric Design)的范畴,在计算机图形学中讲授曲线、曲面知识的目的是更好地在计算机上显示曲线曲面,以计算机图形学的优势更好地展示多彩的世界。
第11章详细介绍的曲线拟合和双圆弧逼近属于“拟合型”曲线,它是计算机辅助制造(Computer Aided Manufacturing,CAM)中的常用算法,包括“小挠度样条函数”和“大挠度样条函数”以及“双圆弧逼近算法”和“直线逼近算法”等。
CAD常常是与计算机图形学联系在一起的,第12章和第13章讨论了计算机图形学*密切的应用——CAD中的一些问题。
第12章讨论了交互式图形系统的设计问题,简要介绍了交互式图形系统设计中的几个关键问题:交互系统的设计原则、界面和菜单设计、交互设计的基本技术,例如定位技术、橡皮筋技术、拖拉技术和选择技术等。对交互式图形系统的数据结构设计也作了原则性的介绍。UNDO和REDO功能虽然是交互系统的重要而必需的技术,而且在计算机应用系统中均有应用,但很少见到这方面的介绍。本书介绍了一种实现UNDO和REDO功能的方法,包括UNDO和REDO功能的数据结构设计、命令执行时的操作、交互应用系统中的命令接口和UNDO或REDO时的动作流程等,希望能对读者有所启发。
第13章介绍的是CAD系统中的一个难点——参数设计问题。先讨论了几何约束满足问题(Geometric Constraint Satisfaction Problem,GCSP),给定一组几何元素和一组描述几何元素间关系的约束条件,求解这组几何元素以满足这组约束。GCSP的求解是智能CAD系统中参数化设计的核心问题,也是人工智能、软件工程、工程设计等领域的研究课题。而后介绍一种参数化的二维图形的输入方法,这种方法采用文本文件输入,但是是一种具有“计算功能”的文本文件。它可以由基本几何直接构造“图元”,也可以采用图形陈列、旋转、平移、对称、比例等图形操作定义新的“图元”。这种“图元”可以是已经构造或即将构造的“图元”组合,用宏调用的方法,实现图形的递归构造。它提供了比较灵活的图形构造手段,既使图形生成简化,又减少了图库的存储量。
*后的附录实际上是对正文的一个很好补充,涵盖了如何将理论和算法付诸实践的范例,有助于读者更好地理解本书的一些基本思想。同时,这些简洁明了、构思巧妙、久经考验的图形处理工具也给广大从事工程设计的科研人员和研究生提供了一个图形开发平台。
本书附录C介绍的教学网http://cgsjtueducn提供的主要内容有:
●本书理论教学的多媒体教材。
●本书附录所列的是计算机图形处理程序的实体以及在此基础上开发的交互式应用系统。这个应用系统不仅可以直接实际使用,也可作为研究生和CAD设计人员的图形开发平台。
●一个简单的、基于C++的计算机图形学实验平台及其运行环境和计算机图形学经典算法的演示系统。
●部分学生作业等等。
●特别是,网站中收录了一些大众化的、以计算机图形学理论应用为主的知识性样板课题。这些样板课题具有知识性、抽象性、应用性和综合性。它向读者展示了如何从原始问题开始,从问题抽象→找出难点→理论基础→项目实施(数据结构和程序设计等)→应用检验(系统化、产品化)直至理论升华(设计书、论文等)的全过程。相信会激发读者的探索欲望。
“伤其十指,不如断其一指。” 本书没有也不可能对计算机图形学许多精彩的理论和算法面面俱到,而是着重对一些典型的算法作了详细介绍。例如,对三维造型装配几何计算消隐的全过程描述得十分详尽,读者几可直接按此编程实现。而且,在这条主线的叙述中,又将本书的几何计算的理论体系完整、充分地体现出来。
当然,只有在对算法真正实现并作了大量的考证以后才能对其有深刻的理解,才能对算法的枝梢末节有所体会,享受到其中的奥妙和乐趣。
本书的1~9章应该是计算机图形学课程的基本教学内容,而有条件的学校可以介绍或补充一些第10~11章中关于曲线、曲面的内容,第12~13章及附录会对从事CAD工作和有关的研究生有所帮助。
柳伟、徐建明、李震霄等分别参与了第1章、第10章和第9章的起草工作,何一江对前言作了润色,一些本科生及研究生参与了上海交通大学计算机图形学教学网站的制作,提供了他们的习作,特向他们表示感谢。
上海交通大学计算机系高手林立,也是一个和谐的集体,同事们对我的工作一直给予大力协助和支持,感谢他们的帮助。
*后,感谢夫人许剑秋为我创造了良好的生活环境。
书中不当之处,希望读者、专家和同行勿吝指正。