计算机图形学

本书采用一种全新的计算机图形学架构，阐述清楚、文字浅显、图示精细、教案完整。从宏观上构建一个计算机图形学的清晰框架与认知体系，给计算机图形学以正确的定位、合理的定义；以“基础”、“绘制”、“几何”和“交互”四篇形式阐述计算机图形学的目的、内容、任务、理论与实践；明确计算机图形学“绘制”与“造型”两个主要任务，使教者易、学者清。在微观上精致编织、准确表述具体的知识点，注重理论的系统性、算法的完整性；用明晰的分析、浅显的解释、精细的图示使问题的表述简洁、叙述准确、举重若轻、化繁为简，将复杂问题简单化；努力保证基础理论、基本算法、几何模型与数据结构的正确性。本书最后提供了该课程的教学建议书、课程设计指导书和颜色表，方便教师的教学与学生的学习和研究。

何援军，上海交通大学计算机系教授、博士生导师。主要研究方向：CAD，计算机图形学。几何计算的理论、算法和软件等。1992年7月被中国船舶工业总公司授予“有突出贡献中青年专家称号”。同年10月起享受政府特殊津贴。“九五”期间任上海市CAD应用工程专家组成员，曾任中国图学学会副理事长、计算机图形学专业委员会主任委员、上海市工程图学学会理事长和上海市科协委员等。基于计算与几何两个最核心要素。提出了“计算机图形学=造型+绘制”的观点。从宏观上构建了一个计算机图形学的清晰框架与认知体系。针对图形/图像正越来越成为计算的目标和结果，通过引入“几何基”与“几何数”，提出了一个“形计算”机制。创立了“基于几何问题几何化的几何计算理论体系与实施框架”。主持过有国家自然科学基金、863等项目以及上海市、中国船舶工业总公司的重点和重大课题等27项。获全国科学大会、省部级及以上科技进步奖14项。主研的CAD软件曾获全国评测第一名。登记计算机软件著作权1项。著有《计算机图形学算法与实践》、《CAD图形开发工具》、《几何计算》和《计算机图形学》等。发表论文120余篇。

前言
第一篇基础
第1章导论
1.1计算机图形学的定位和定义
1.1.1国内外对计算机图形学的定义
1.1.2“大图学”下计算机图形学的定位与定义
1.1.3图形、图像、模型与几何
1.1.4计算机图形学的总体架构
1.2计算机图形学与其他学科的关系
1.3计算机图形学的发展简史
1.3.1硬件平台
1.3.2基础理论
1.3.3实际应用
1.3.4SIGGRAPH
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
1.6本章要点
1.7本章作业
第2章计算基础
2.1计算
2.1.1计算及其作用
2.1.2计算的理论基础
2.1.3计算的对象与结果
2.1.4计算的关键
2.1.5计算的方法论
2.2图学计算的内涵分析
2.2.1图、形、几何与几何计算
2.2.2模型与图形的本质
2.2.3图学计算的矛盾与关键
2.3形计算机制
2.3.1形计算的基本概念
2.3.2形计算的理论基础
2.3.3形计算的基本架构
2.3.4形计算的实施形式
2.4本章要点
2.5本章作业
第3章基本几何
3.1向量
3.1.1向量及其性质
3.1.2向量点积
3.1.3向量叉积
3.2二维基本几何
3.2.1点
3.2.2直线
3.2.3圆
3.2.4圆弧
3.2.5基本几何的统一表示
3.2.6圆弧曲线
3.3基本几何的几何数
3.4图形边界的几何数
3.5辅助几何的几何数
3.6向量交点几何数
3.6.1交点几何数的定义
3.6.2交点几何数的几何意义
3.6.3交点几何数的求取
3.6.4圆弧交点的几何数
3.7平面基本几何
3.7.1直线的建立
3.7.2圆和圆弧的建立
3.8三维基本几何
3.8.1空间直线
3.8.2平面
3.8.3三维交点几何数
3.9本章要点
3.10本章作业
第4章几何变换
4.1几何变换的基本描述
4.1.1齐次坐标
4.1.2齐次变换矩阵
4.1.3变换的几何化表示
4.2二维变换
4.2.1二维基本变换
4.2.2一般二维旋转变换
4.2.3坐标系的旋转
4.2.4以向量及其中垂线构建坐标系
4.2.5二维对称变换
4.2.6不同坐标系下直线系数的变换
4.3三维变换
4.3.1六视图变换矩阵
4.3.2三维基本旋转变换
4.3.3以空间一向量为坐标轴建立坐标系
4.3.4绕空间任意轴的旋转变换
4.3.5向任意平面的投影
4.3.6轴测变换
4.3.7透视变换
4.4视图变换
4.4.1视图变换的基本原理
4.4.2视图变换的实施
4.5本章要点
4.6本章作业
第5章几何计算
5.1处理几何奇异的基本策略
5.1.1重交点的取舍规则
5.1.2重边交点的取舍规则
5.1.3圆弧重交点的求取
5.2判断计算
5.2.1拐向判断
5.2.2凸包算法
5.2.3包容性测试
5.2.4最小最大判定法
5.2.5线与线的关系（深度测试）
5.2.6线与面的关系
5.3距离与面积计算
5.3.1点到平面直线的距离
5.3.2点到空间直线的垂足
5.3.3点到空间直线的距离
5.3.4点到平面的距离
5.3.5空间两直线的距离
5.3.6直线与平面的距离
5.3.7空间两平面的距离
5.3.8平面多角形面积
5.4二维相交计算
5.4.1直线与直线的相交
5.4.2直线与圆的相交
5.4.3圆与圆的相交
5.4.4二维几何交切的复杂例子
5.5三维相交计算
5.5.1直线与平面的相交
5.5.2平面与平面的相交
5.5.3直线与球面的相交
5.6本章要点
5.7本章作业
第二篇绘制
第6章光栅计算
6.1直线光栅化算法
6.1.1直线DDA光栅化算法
6.1.2直线Bresenham光栅化算法
6.2圆光栅化算法
6.2.1圆的八方对称光栅化算法
6.2.2圆方程光栅化算法
6.2.3Bresenham圆光栅化算法
6.2.4中点圆光栅化算法
6.3多边形填充算法
6.3.1扫描线填充算法
6.3.2边填充算法
6.3.3种子填充算法
6.4字符和汉字显示
6.4.1点阵字符
6.4.2矢量字符
6.5反走样
6.5.1图形走样
6.5.2超采样
6.5.3区域采样方法
6.6本章要点
6.7本章作业
第7章裁剪计算
7.1一维线性窗口裁剪
7.2二维窗口裁剪
7.2.1Cohen-Sutherland二维矩形窗口裁剪
7.2.2Cyrus-Beck二维凸多边窗口裁剪
7.2.3Liang-Barsky二维矩形窗口裁剪
7.2.4基于一维裁剪的二维矩形窗口裁剪
7.2.5四种矩形窗口裁剪效果分析
7.3二维矩形窗口对多边形的裁剪
7.4多边形窗口对线的裁剪
7.5三维Box裁剪
7.5.1Cohen-Sutherland三维Box裁剪
7.5.2Liang-Barsky三维Box裁剪
7.5.3基于一维裁剪的三维Box裁剪
7.6三维视锥体裁剪
7.6.1线面求交视锥体裁剪
7.6.2Liang-Barsky视锥体裁剪
7.6.3基于投影降维的视锥体裁剪
7.7本章要点
7.8本章作业
第8章消隐计算
8.1凸多面体的隐藏线消除
8.1.1凸多面体的自消隐
8.1.2凸多面体消隐的基本原理
8.1.3凸多面体对其他物体的遮挡计算
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.3一般多面体的隐藏面消除
8.3.1隐藏面消除的基本原理
8.3.2隐藏面消除的实施
8.4本章要点
8.5本章作业
第9章颜色模型
9.1光和颜色
9.1.1人对世界的视觉感知
9.1.2光源的种类
9.1.3物体的表面性质
9.2颜色论
9.2.1三色学说
9.2.2颜色特性与参数
9.2.3CIE色度图
9.3颜色模型
9.3.1原色系统
9.3.2RGB颜色模型
9.3.3CMY颜色模型
9.3.4HSV颜色模型
9.4本章要点
9.5本章作业
第10章光照计算
10.1光照模型
10.1.1光照模型的基本要素
10.1.2环境光
10.1.3漫反射和Lambert模型
10.1.4镜面反射和Phong模型
10.1.5更多光的因素
10.1.6透明模型
10.1.7简单局部光照模型
10.2插值算法
10.2.1恒定明暗处理
10.2.2Gouraud明暗处理——光强插值算法
10.2.3Phong明暗处理——法向插值算法
10.3光线跟踪
10.3.1Whitted整体光照模型
10.3.2光线跟踪的基本原理
10.3.3光线跟踪算法
10.3.4光线跟踪计算中的关键技术
10.3.5光线跟踪的反走样
10.4阴影计算
10.4.1阴影的定义
10.4.2自身阴影
10.4.3投射阴影
10.4.4阴影算法的基本原理
10.4.5阴影算法
10.5纹理计算
10.5.1纹理的定义
10.5.2颜色纹理
10.5.3几何纹理
10.6本章要点
10.7本章作业
第三篇造型
第11章二维造型
11.1二维布尔运算
11.1.1数据结构
11.1.2基本原理
11.1.3环运算的实施
11.1.4奇异情况处理
11.1.5环运算算法
11.1.6算法复杂度分析
11.2变形造型
11.3本章要点
11.4本章作业
第12章三维造型
12.1物体描述
12.1.1构造表示
12.1.2边界表示
12.1.3分解表示
12.2平移扫掠造型
12.2.1平移扫掠算法的输入参数
12.2.2平移扫掠算法的顶点编号和坐标定值
12.2.3平移扫掠算法的构造过程
12.2.4平移扫掠造型的扩展
12.2.5平移扫掠造型的实施
12.3旋转扫掠造型
12.3.1旋转体的输入参数
12.3.2旋转体的顶点编号与坐标定值
12.3.3旋转体的构造过程
12.3.4旋转体造型的扩展
12.3.5旋转体造型的实施
12.3.6旋转体造型示例
12.4场景装配
12.5本章要点
12.6本章作业
第13章曲线曲面
13.1Bezier曲线
13.1.1一次Bezier曲线
13.1.2二次Bezier曲线
13.1.3三次Bezier曲线
13.1.4高次Bezier曲线
13.1.5Bezier曲线生成算法
13.1.6Bezier曲线的拼接
13.2Bezier曲面
13.3B样条曲线
13.3.1二次B样条曲线
13.3.2三次B样条曲线
13.3.3deBoor算法与B样条曲线的离散生成
13.4B样条曲面
13.4.1均匀二次B样条曲面
13.4.2均匀三次B样条曲面
13.5曲面的三角化表示
13.6本章要点
13.7本章作业
第14章曲线拟合
14.1小挠度样条曲线拟合
14.1.1小挠度样条函数的基本方程
14.1.2小挠度样条函数的插值公式
14.1.3小挠度样条函数的边界条件
14.1.4小挠度样条曲线拟合算法
14.2大挠度样条曲线拟合
14.2.1大挠度样条函数的基本原理
14.2.2大挠度样条曲线拟合算法
14.3双圆弧逼近
14.3.1平均切线法
14.3.2双圆弧公切点的轨迹
14.3.3双圆弧的求法
14.3.4一般函数曲线的双圆弧逼近
14.4直线逼近
14.4.1样条曲线的直线逼近
14.4.2圆的直线逼近
14.5本章要点
14.6本章作业
第四篇交互
第15章交互技术
15.1交互系统的设计原则
15.2交互设计的基本技术
15.2.1定位技术
15.2.2橡皮筋技术
15.2.3拖曳技术
15.2.4选择技术
15.3数据结构设计
15.3.1图形的数据结构设计
15.3.2层的数据结构设计
15.3.3基本图元的数据结构设计
15.3.4辅助图元的数据结构设计
15.3.5其他数据结构设计
15.4UNDO和REDO技术
15.5本章要点
15.6本章作业
附录A教学建议书
附录B课程设计指导书
附录C颜色表
参考文献

图书图书，左图右书。地理之学，非图不明。图与书、诗与画是研究社会之发展、创新和实践的载体，持续不断地记录着人类文明进步的轨迹。图与语言、文字、数字和声音一样，是人类描述思想、交流知识的基本工具。图样更是科学、技术和工程界的语言，用于传递设计与加工的构想。它既是人类语言的补充，也是人类智慧和语言在更高一级发展阶段上的具体体现，在人类生活中有不可替代的作用。在当今社会，图更显现出在人类思维、活动与交流中的巨大作用。“曾向沧江看不真，却因图画见精神。”在以计算机和数据为代表的信息时代，图与图学已如同文字与文学、数字与数学一样，成为人类活动最基本的工具和必须掌握的学问。因此，编制经典的图学教材，支撑图学学科的发展，使图学能够与文学、数学一起共同支撑科学与工程的发展，促进社会的进步，是图学工作者的责任和义务。 计算机图形学是图学的杰出代表与引领者，其地位稳固，几乎所有领域都可涉及，相关教材数百种，千奇百怪。新的理论、方法乃至硬件日新月异。这就需要静下心来思考： 计算机图形学最基础、最本质的是什么？作为一门课程，它的基本任务是什么？作为一本教材，它需要包含哪些最基本的内容？科学的发展十分迅速，一些方法与技术可能随硬件的更新而发展，但是它们的基础与特定硬件、网络协议以及一些短暂的事物并不相关。 因此，一本计算机图形学的教材需要回答的最基本问题有两个：在宏观上，绘制一个计算机图形学的清晰框架与认知体系，回答“计算机图形学是什么”；在微观上，精致编织、准确表述计算机图形学具体而细节的知识点，回答“计算机图形学有什么”。基于这个认识，本版对第2版的修改工作主要包括对学科的认知和教材的组织两个方面。 图与图学的认知方面。包含对图与图学总体上的定位、定义的认知和对计算机图形学的计算基础的认知两个方面。从“形”的角度认识与表述图与图学，认为世界由形构造，形由图在画面上显示，因此，形是图之源，图是形的载体，图学就是研究“形一图”和“图一形”之间的转换。在这个整体上分析图形、图像、工程图的本质属性和它们的共性，给出统一的图学之定位和定义：“图学是以图为对象，研究在将形演绎到图的过程中，关于图的表达、产生、处理与传播的理论、技术和应用的科学。”全局性地考虑计算机图形学、计算机图像学、工程图学在科学上的同一性，以及它们在学科上的分工。在这个总的定义下，计算机图形学的学科地位将得到加强，计算机图形学的根本任务将更为明确。在“第1章导论”中，给出了这个学科的基本内容及逻辑关系。 加强了对图学计算基础的阐述，专门增加了“第2章计算基础”。阐述了图学计算的内涵，分析了几何与几何计算在图学中的地位和作用，指出图学最根本的理论基础是几何学，它的计算基础是几何计算。介绍了一种基于几何问题几何化的“形计算”机制，以寻求一种合适的几何计算方法与机制，从而更有利于形的表述和图的生成。“形计算”机制补充了常规的“数计算”机制，可以从更宏观的角度构建算法框架，使图学计算的过程更加结构化、直观化、简单化。 教材的组织方面。这次修订的宗旨是向读者提供一本更科学、更浅显易懂的计算机图形学教材，努力使理论更统一、更系统，实施更规范、更简单。 在基本理论的叙述方面，更宏观、更具条理性。从“形”的角度去统一、阐述和研究，去发展图学的基础理论、基本方法和典型算法，明晰图学的计算基础和应用基础。从构造的角度阐述模型的几何品质，认识几何计算在计算机图形学中的地位和作用。从几何奇异是造成几何造型系统不稳定性的本源人手，给出了处理几何奇异的基本原则。 在实施方面，更易实践、资源更多。一是增加了一些算法的实施描述，二是为了教师上课需要，也是为方便学生，在最后的附录中给出了一系列的教学资源。 本版教材包括导论（1章）、4篇正文（14章）和3个附录。每章的最后均有一个小结，列出本章的基础理论和知识要点，并附加了一些习题、思考题和课程设计题等。教材的结构如下： 第1章导论在章节的次序上，与上版不同，将绘制篇安排在造型篇的前面，即按照“基础一绘制一造型一交互”4篇的次序编排。这是考虑到绘制是关于图的内容，如光栅计算、裁剪计算、消隐计算和光照计算等，是计算机图形学公认的也是最基本的内容，是必需的。造型是关于“形”的内容，如二／三维造型、曲线曲面和曲线拟合等，是服务于绘制的，因而是可以选择的。 编制一个完整的代码并实现它，可能是对理论和算法认知的最高境界，本版不惜篇幅给出了一些经典算法的代码，便于读者从这些算法的实施过程中更深入地理解那些经典算法的原理。有些原理上看起来很复杂，实施却很简单，而有些看上去很简单的原理，实施时却并非易事。但是，作为一本教材，还是应该注重在理论上的阐述，不可能将这些算法都展开。希望对书中算法的理论进行深入了解的读者，可以参考笔者的另一本专著《几何计算》‘181，它详细给出了300余个常用几何算法的理论、原理、方法和源代码，这些算法几乎在计算机图形学中都会用到。它与本教材的思想体系是一致的，所述的算法简洁、稳定、实用。 为了教学和读者实施的方便，本书给出了3个附录，作为本书的教学资源。 教学建议书按照“36学时教学+18学时课程设计”的教学内容与时间安排，教师可根据所教专业与实际需求自行增删相关内容。 课程设计指导书帮助读者在一个交互系统总体框架下选择性地实现其中的一些算法题或者稍微难一些的课程设计题。在课程设计题的前面参考性地给出了该题目的“难度系数”，有些题目甚至可以作为研究题。这样的安排可以满足不同层次的学校、专业及学生的需求。 计算机图形学的一项主要任务是得到绚丽多彩的图形图像，颜色的选择与配置是其中的重要一环。本版新增了一个颜色表，它给出了一些颜色数字模型的计算机表示，方便读者的应用。 教程的每章最后给出了一些习题、思考题和课程设计题，教师可以从中选择一些题目用于平时布置作业或在课程结束时形成试卷，也可以阶段性地布置课程设计。学生则可以预先选择自己感兴趣的题目作为项目进行训练。 这些教学资源的安排希望不仅有利于教师教学，也可以协助教师和学生在一个总体架构下进行有条不紊、累进性的工作，形成有自己特色的课程资源或工作资源。积跬步以至千里，积小流以成江海。 除了参考文献已经列出的以外，撰写本书时还参考与采用了其他一些图书及网上资源，无法一一列出，谨向那些作者们表达谢意。 书中不当之处，欢迎读者、专家和同行勿吝指正。 2016年6月5日于上海