本书课程链接 http://cg.sjtu.edu.cn/　　


　　计算机图形学在众多领域扮演着越来越重要的角色，其主要作用就是研究如何在计算机中表示以及利用计算机进行图形的计算、处理和显示的相关原理与算法，也即将抽象的模型用最为形象的方式表述出来。
　　本书重在清晰而准确地讲解计算机图形学的基础理论、算法、几何模型与数据结构等内容，包括光栅图形学、图形裁剪、基本几何、二维几何、图形变换、三维几何、几何造型、光照模型、曲线和曲面、曲线拟合和双圆弧逼近、交互式图形系统的设计问题以及CAD系统中的一个难点－－参数设计问题。

本书特色：
　　本书对一些被普遍认同的计算机图形学领域的理论、技术和算法作介绍，重在对基础理论、算法、几何模型与数据结构等的基本理论和技术的叙述，努力保证它们的正确性，尽可能使叙述准确、清晰。
　　●基础理论。计算机图形学理论与计算机科学中的算法设计、算法分析、数据结构等学科密切相关。强调对理论核心思想的阐述，用通俗易懂的语言，简明、透彻地阐明这些理论最本质的思想，附以精心设计的图示形式，力图使读者在较短的时间内掌握这些基本理论。
　　●算法。精心设计算法用例，提高算法的正确性、示范性和适应性。从理论上分析各种算法的原理、可行性及几何复杂性。对各种典型的算法尽可能比较多种可能的方案，分别指出它们的优缺点和应用场合，某些关键思想将被反复运用。在如何提高算法的效率，保证算法的准确性、可靠性，怎样处理好多值问题以及如何组织好数据结构，提高程序设计的技巧等各方面都仔细推敲。
　　●几何模型与数据结构。重视几何模型与数据结构的描述，便于读者更好的理解其背后的理论依据。也是对数据结构、程序设计等主干课程的一次深化和应用。

　　本书第2版将于2008年下半年与读者见面，新版采用了一种全新的计算机图形学架构，以“基础”、“几何”、“绘制”和“交互”四大篇为基本结构框架，叙述了计算机图形学的目标、内容、任务、理论与实践。
　　本书第2版通过揭示“图形=图元+属性”与“计算机图形学=几何+绘制”的本质属性，对计算机图形学进行了准确的定位、合理的定义，明确计算机图形学“几何”与“绘制”两大任务，使教者易、学者清。
　　全书模块化的架构、明晰的讲解、浅显的文字、精细的图示，力求帮助读者尽可能正确、通俗地阐述计算机图形学的理论体系、几何模型、基本算法与数据结构等根本要素，并努力保证它们的准确、简单、直观、清晰。举重若轻、化繁为简，将复杂问题简单化，是本书的突出特色。

　　对本书感兴趣的读者可登陆上海交通大学“计算机图形学精品课程网站”http://cg.sjtu.edu.cn，网站提供了电子教案、实验基础、算法案例、学生作品、相关课题、算法库及课程设计等广泛的内容，读者可以免费下载。

无

图形是传递信息最主要的媒体之一，计算机图形学的发展和应用在某种意义上已成为计算机软、硬件发展水平的标志。它已成为一门成熟的学科，是信息技术中不可缺少的重要内容和发展基石。“计算机图形学”课程也已成为大学计算机、机械等相关学科的一门主干课程。
　　本书对一些被普遍认同的计算机图形学领域的理论、技术和算法作了介绍，主要定位于作为计算机图形学（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://cgsjtueducn提供的主要内容有：
 ●本书理论教学的多媒体教材。
 ●本书附录所列的是计算机图形处理程序的实体以及在此基础上开发的交互式应用系统。这个应用系统不仅可以直接实际使用，也可作为研究生和CAD设计人员的图形开发平台。
 ●一个简单的、基于C++的计算机图形学实验平台及其运行环境和计算机图形学经典算法的演示系统。
 ●部分学生作业等等。
 ●特别是，网站中收录了一些大众化的、以计算机图形学理论应用为主的知识性样板课题。这些样板课题具有知识性、抽象性、应用性和综合性。它向读者展示了如何从原始问题开始，从问题抽象→找出难点→理论基础→项目实施（数据结构和程序设计等）→应用检验（系统化、产品化）直至理论升华（设计书、论文等）的全过程。相信会激发读者的探索欲望。
　　“伤其十指，不如断其一指。” 本书没有也不可能对计算机图形学许多精彩的理论和算法面面俱到，而是着重对一些典型的算法作了详细介绍。例如，对三维造型装配几何计算消隐的全过程描述得十分详尽，读者几可直接按此编程实现。而且，在这条主线的叙述中，又将本书的几何计算的理论体系完整、充分地体现出来。
　　当然，只有在对算法真正实现并作了大量的考证以后才能对其有深刻的理解，才能对算法的枝梢末节有所体会，享受到其中的奥妙和乐趣。
　　本书的1～9章应该是计算机图形学课程的基本教学内容，而有条件的学校可以介绍或补充一些第10～11章中关于曲线、曲面的内容，第12～13章及附录会对从事CAD工作和有关的研究生有所帮助。
　　柳伟、徐建明、李震霄等分别参与了第1章、第10章和第9章的起草工作，何一江对前言作了润色，一些本科生及研究生参与了上海交通大学计算机图形学教学网站的制作，提供了他们的习作，特向他们表示感谢。
　　上海交通大学计算机系高手林立，也是一个和谐的集体，同事们对我的工作一直给予大力协助和支持，感谢他们的帮助。
　　最后，感谢夫人许剑秋为我创造了良好的生活环境。
　　书中不当之处，希望读者、专家和同行勿吝指正。


何援军
2005年7月5日
于上海交通大学计算机系

无

何援军：暂无简介

无

第1章绪论
11计算机图形学及它与其他学科的关系
12计算机图形学发展简史
13计算机图形学的应用领域
131计算机辅助设计与制造
132科学计算可视化
133虚拟现实
134计算机艺术
135计算机动画
136图形用户接口
14计算机图形学研究的基本问题
141图形输入
142图形描述
143图形变换
144图形运算
145图形输出
146几何算法、几何复杂性和计算效率
15计算机图形学的相关开发技术
151OpenGL
152ACIS
153DirectX
154Java3D
155VRML
第2章光栅图形学
21直线光栅化显示算法
211直线光栅化显示的数字微分分析法(DDA)
212直线光栅化显示的Bresenham算法
22圆光栅化算法
221利用圆的八方对称性画圆
222简单的方程画圆方法
223Bresenham画圆算法
224中点圆算法
23椭圆光栅化算法
24多边形填充
241扫描线填充算法
242边填充算法
243种子填充算法
25字符和汉字显示
251点阵字符
252矢量字符
26反走样
261图形走样
262超采样
27本章要点
28本章作业
第3章图形裁剪
31线裁剪算法
311CohenSutherland算法
312LiangBarsky算法
32多边形裁剪
321SutherlandHodgon多边形裁剪算法
322图形求交集多边形裁剪法
33本章要点
34本章作业
第4章基本几何
41基本几何的描述
411直线的描述
412圆的描述
413圆弧的描述
414基本几何的统一描述
415圆弧曲线
42基本几何及图形边界的方向
421基本几何及其方向的定义
422几何元素定向的优点
43直线和圆弧的相交
431坐标系变换求交
432几何计算求交
44曲线和曲线的相交
441劣弧段最小外接矩形求取
442圆弧曲线的相交算法
45本章要点
46本章作业
第5章二维几何
51向量和向量的交点
52包容性测试
521符号判别法
522角度判别法
523半射线交点计数判别法
524Griffiths判别法
53直线段和图形公共部分的求取
54一般图形的填充算法
541一般图形的描述
542一般图形的填充算法
55二维布尔运算
551环
552二维几何构型中的图形描述
553两个环的交、并、差几何运算
554两个环运算的数据结构
555两个环运算的算法
556扩展到圆弧
557含有多个内环图形的运算
558算法复杂度分析
56平面多角形面积的求取
57本章要点
58本章作业
第6章图形变换
61图形变换的理论基础
611坐标系、基底、坐标行
612基底变换
613线性变换及其乘积
614不同基底下的线性变换
62图形变换的基本描述
621齐次坐标
622齐次坐标变换矩阵
623二维图形变换
624三维图形变换
63图形变换的几何化表示
631几何化表示的基本理论
632图形变换的几何化表示
633图形变换几何化表示的实施
634图形变换几何化表示的应用
635三维变换的几何化表示
636图形变换几何化表示与基本几何
64投影与投影变换
641平行投影
642投影变换、深度坐标与三维观测流水线
643投影示意图
65轴测变换
651轴测变换的定义
652正轴测变换
653轴测投影变换的一般公式
654斜二测变换
66罗盘变换
661罗盘变换的基本原理
662罗盘变换公式
663屏幕轴三角架的实时产生
67透视变换
671透视变换的基本原理
672透视变换矩阵
673透视投影转化为平行投影
674灭点及其产生
68坐标变换矩阵小结
69视图变换
691视图变换的基本原理
692视图变换的实施
610本章要点
611本章作业
第7章三维几何
71坐标系统
72物体的描述
73几何计算
731最小最大判定法
732标准平面方程的建立
733通过N个顶点求取平面方程
734深度测试
735面对棱的遮挡
736隐藏线的表示
737一维交集算法
74凸多面体的隐藏线消除
741凸多面体的描述
742全体凸多面体的数据结构
743棱的表示与输出
744凸多面体消隐算法的基本原理
745凸多面体落影区的求取
746凸多面体对其他物体的遮挡计算
747凸多面体的自消隐
748凸多面体场景消隐算法的实施
75一般多面体的隐藏线消除
751物体的描述和面的构造
752棱分类——一般多面体的自消隐
753面对棱的遮挡
754面消隐时特殊情况的处理
755消隐算法的数据结构
756一般多面体消隐算法的实施
76一般多面体的隐藏面消除
761隐藏面消除的基本原理
762隐藏面消除的实施
77本章要点
78本章作业
第8章几何造型
81垂直扫掠物体生成算法
811垂直扫掠算法的输入参数
812垂直扫掠算法的顶点编号与坐标值定值
813垂直扫掠算法的构造过程
814垂直扫掠算法的三维物体记录
815垂直扫掠算法边的重复显示处理
816垂直扫掠算法的扩展
817垂直扫掠物体产生程序
818进一步扩展
82旋转物体的生成算法
821旋转体的输入参数
822旋转体的顶点编号与坐标定值
823旋转体的构造过程
824旋转体的三维物体记录
825旋转体边的重复显示处理
826特殊情况处理
827旋转体算法的扩展
828旋转体的物体产生程序
829旋转体产生示例
83物体装配
831基本构件的输入
832装配数据的输入
84布尔运算
841布尔运算的基本原理——拓扑重构
842布尔运算的几何信息重构——误差处理
85本章要点
86本章作业
第9章光照模型
91光和颜色
911人对世界的视觉感知
912光源的种类
913物体表面的种类
914颜色论
915三色学说
916CIE色度图
917色彩应用
92颜色模型
921原色系统
922RGB颜色模型
923CMY颜色模型
924HSV颜色模型
93光照模型
931环境光
932漫反射和Lambert模型
933镜面反射和Phong模型
934透明模型
935简单局部光照模型
94插值算法
941恒定明暗处理
942Gouraud明暗处理（光强插值算法）
943Phong明暗处理（法向插值算法）
95光线跟踪
951Whitted整体光照模型
952光线跟踪基本原理
953光线跟踪算法
954光线跟踪算法中的关键技术
955光线跟踪的反走样
96阴影
961自身阴影
962投射阴影
963阴影算法
97纹理
971纹理的定义
972颜色纹理
973几何纹理
98本章要点
99本章作业
第10章曲线和曲面
101曲线曲面的基本理论
1011曲线与曲面的参数表示
1012曲线的切矢及自然参数表示
1013曲面论
102参数三次曲线曲面
1021参数三次曲线方程
1022参数三次曲面
1023参数连续性和几何连续性
103Bézier曲线和曲面
1031Bézier曲线方程
1032Bernstein基函数的性质
1033Bézier曲线的性质
1034Bézier曲线的升阶
1035Bézier曲线的拼接
1036Bézier曲面
104B样条曲线和曲面
1041B样条曲线方程及其与Bézier曲线的比较
1042B样条基函数的递推定义及其性质
1043B样条曲线的类型划分
1044一般非均匀B样条曲线
1045B样条曲面方程及其性质
1046B样条曲面的矩阵表示和常见的B样条曲面
105NURBS曲线和曲面
1051NURBS的提出
1052NURBS曲线方程及其性质
1053NURBS曲面方程及其性质
106Coons曲面
107曲面的三角化表示
1071曲面三角化描述
1072曲面三角化遍历
1073三角形曲面的简化
1074三角形曲面的压缩
108本章要点
109本章作业
第11章曲线拟合与双圆弧逼近
111小挠度样条函数的建立
1111小挠度样条函数基本方程的导出
1112小挠度样条函数的边界条件
112大挠度分段三次样条函数的建立
1121大挠度样条函数基本方程组的导出
1122大挠度样条基本方程组的解法
113双圆弧逼近
1131平均切线法
1132双圆弧公切点的轨迹
1133公切点的确定
1134双圆弧的求法
1135样条曲线的直线逼近
1136一般函数曲线的双圆弧逼近
114圆的直线逼近
115本章要点
116本章作业
第12章交互技术
121设计原则
122界面和菜单设计
1221建立一个新应用
1222定义主菜单
1223定义一个执行菜单
1224添加源代码
1225C语言（*c）程序文件的加入
1226加标题
123交互设计的基本技术
1231定位技术
1232橡皮筋技术
1233拖拉技术
1234选择技术
124数据结构设计
1241图形的数据结构设计
1242层的数据结构设计
1243基本图元的数据结构设计
1244辅助图元的数据结构设计
1245其他数据结构设计
125UNDO和REDO技术
1251UNDO和REDO功能的数据结构设计
1252UNDO和REDO功能命令执行时的操作
1253交互应用系统中的命令接口
1254UNDO或REDO时的动作流程
126本章要点
127本章作业
第13章参数设计
131几何约束满足问题
132基于点簇归约的几何推理算法
1321基于点簇的几何推理算法原理
1322基于点簇的几何推理算法
133基于图形构造模型的参数设计方法
1331基本模型
1332表示点的各种节点
1333表示直线的各种节点
1334表示圆的各种节点
1335模型扩展
1336模型求解
134参数化图库建库工具
1341文件转换器
1342图形校正
1343用户界面
135本章要点
136本章作业
附录A基础算法程序
附录B图形接口
附录C教学网站
参考文献