本书从对图形图像本质的认知开始，梳理图形图像的表达机制与产生机理，指出图形图像的源头是形，基础是几何，由此认识图学与几何的关系，揭示图学计算的内涵，从几何与计算两个基本要素分析图学计算的若干关键问题，给出图学的计算基础。本书可作为工程图学、计算机图形学、计算机图像处理及CAD等课程的先修课程教材或教学参考书，凡从事与图形图像处理相关工作的研究人员、工程设计人员、教师与学生等都可直接使用本书所阐述的思想、方法和算法。

前　　言图形图像在人们生活中的应用已经极大地普及，人类社会已经进入一个图形图像时代。统一图形图像的研究顺应了这个形势，符合社会和科学发展的规律，图与研究图的图学科学的作用将会日益增大。中国图学学会2013年发布《图学学科报告》，提出建立“大图学”学科。本书是在大图学的概念下，根据“图学是研究形和图，它们的表示、表现以及互相之间转换的科学，它的核心是形，本质是几何”的基本定位，编写本书作为图学的公共教材和参考书，阐述目前分散于工程图学、画法几何、计算机图形学和计算机图像处理等图学分支共同的计算基础，使图学有一个统一的、较高的公共平台。
图形图像的形象性、直观性、准确性和简洁性使得人们可以通过图形来认识未知，探索真理。图形图像已成为重要的计算源、计算对象和计算结果，已被作为解的一种表现形式去追求，这样的计算遍及各个领域。
图学的公共计算基础是什么？本书的回答是：一是几何，二是计算。本书从几何与计算两个基本要素全面论述了形、图、几何与图学计算间的关系。
先说几何。图源于形而展现形，图与图学的基础是几何。形是输入，有个构造问题；图是输出，有个绘制问题。它们的基元是几何元，形的构造与图的绘制通过几何计算实现。
James R. Miller说过：Computer graphics and modeling rely on mathematical operations on points and vectors. I advocate using vector geometric analysis to simplify required derivations.（计算机图形学和造型依赖于点和向量的数学运算，我认为应使用向量几何分析去简化推导。）简短的表述揭示了计算机图形学和造型的基础是点与向量的运算，也充分揭示了图学与几何的紧密关系。国际几何学与图学学会（International Society for Geometry and Graphics，ISGG)每两年召开一次国际几何学与图学会议(ICGG)，是将图学与几何定位得最紧密也是最贴切的国际学术组织与国际会议。
图形图像由几何组成。图形，由“图”和“形”两个字组成。其一，图描述形，是形在画面上的展现，本质是表达形；其二，图源于形，由形而来，形是图之源。因此，在计算机上模拟现实世界、构建虚拟世界时，先要造型，而后得图。追溯图形图像的来源，不管是拍摄的照片还是计算机生成的图形图像，它们都是自然景象、计算机模型（可以抽象地通称为“形”）在某一视角下在特殊位置画面上的显示。揭示图形图像的本质是：它们同是具有颜色、宽度、线型等属性的一系列点、线等基本几何按照一定的关系组合起来构成各种色彩斑斓的图片（picture）而已。
图学研究的对象是几何元。图形图像的构造、产生、传输和处理就是围绕这些点、线、面等几何元及几何元间的关系、组合展开的。这些不同的几何元依照一定的拓扑关系组织起来构造成不同的几何形体；通过投影在画面上显示成图——图形或图像，无论是位图还是矢量图，终极处理对象是点、线等图元，它们都属于几何。
图学的理论基础是几何。图学研究造型理论与方法、形→图的理论与方法、图的处理理论与方法、图→形的理论与方法以及图的传输理论与方法等，其理论、方法和技术基础是几何学，也会借助于代数学、计算机等其他学科或是学科交叉。本书特别讨论了画法几何的地位及其理论。画法几何原本属于几何的一部分，在法国几何学家蒙日非数学地阐述了投影理论后才成为一门独立于几何的学科，与笛卡儿的几何代数化偏重于解析方法走了不同的路。回归画法几何的几何学地位，充分发挥画法几何给出的结论，充分看到它所用的方法更偏重于几何化的特点并将其进一步发扬光大，关注非数学化的画法几何的“计算化”问题——本书认识到并充分讨论了这些问题。
再说计算。图学计算是对几何的定义、构造、度量和显示，它的重点是处理几何间的关系，而不是几何元的参数。关键是解决几何奇异、维度差距、计算稳定性、计算方式与解的表述等。
最基础的学科是数学，数学的本质不是“数”，而是“算”。计算的学问应该叫“算学”，算学抓住了计算的本质，更能体现计算的神韵。而且，从某种意义上说算学的范围似乎比数学更大，例如，在计算机时代，至少算学还包括算法，我国古代就有算经、算术之说，术就是算法。
图形图像已成为新的计算对象和目标。早先的计算源、计算对象和计算目标都是数，现在更多的领域需要将图形图像作为计算对象和目标，以图形图像作为输入源，经过计算，转化成另外一种形式的图形图像。数由数字表达，图形图像由几何元表达。不同的几何元依照一定的拓扑关系构造成不同的场景，在空间构造形；通过投影将不同属性的图元按一定的形式组织起来并加上属性，在平面上显示图。这里，找出图元间的组织形式的过程就是图学计算。
图学计算的空间维度是不统一的。实体空间与表示空间不统一，思维空间与计算空间不统一。图学计算的工作都是人按空间思维设计，计算机则是按线性的数计算实施的。这里，三维的形被直接跨越到一维的数计算，缺少必要的过渡和衔接，几何属性被“打”得面目全非，形的关系和变化难以完备地获得和表达。人的思维被用于适应这种转换，空间思维优势就难以发挥，造成在某种程度上对算法的掌控能力下降。
几何问题几何化。数学主要发生于幕后，起关键作用的是人，包括人的思维、人的逻辑、人的规划，因此计算的模式需要改变，以适应这种新的计算对象和目标。为此，本书全面阐述了一个基于“几何问题几何化”的几何计算理论体系与实施框架，为了交流的方便，命名为“形计算”机制。从形的整体去主导算法设计，构建算法框架，使它更有利于形的表述、图的生成，使图学计算的过程更加结构化、直观化、简单化。形计算引入“几何数”，协助表征几何的定义与几何间关系的表示并辅助整个计算过程，在理论上给出了解决几何奇异问题的整体方案。引入“几何基”作为形计算的基本单元，淡化代数表述和代数运算，更好地发挥人的空间思维能力去构建算法的设计框架、宏观地描述整个求解过程。形计算补充常规的“数计算”机制。书中阐述了形计算在计算中的地位、作用和应用领域，给出了它的理论基础、计算基础和实施方案及众多的实例。这是几何代数化发展到图形图像时代的必然趋势——加强图形认知方式在计算中的作用。
计算稳定性是算法的主要考量。本书特别强调算法的稳定性，从根源上分析了引起几何计算不稳定的原因并提出了相应的对策。导致几何计算不稳定主要有两个原因：一是由数字误差引起，几何参数的数据误差和计算过程中误差的积累导致计算错误；二是由几何关系引起，共点、共线和共面导致几何关系奇异而引起几何选择与几何重组错误。几何信息错误，在局部；几何关系错误，于全局。在计算机中，几何信息是实数，有误差和错误；几何关系的拓扑信息是正整数，只有错误。信息有错误，计算结果也就错了，信息有误差，计算就不稳定，两者性质不同。“错误”引起的错在明处，有结果；“误差”引起的错在暗处，结果不确定。更为可怕的是，几何间的共点、共线、共面是几何模型的客观存在，这种“正常现象”引起的错，现在还没有一套理论去处理。本书提供了这个支撑，指出几何计算的不稳定源于数据的误差和几何关系奇异两个根本原因，并提出了相应的对策，书中的几何算法都考虑了这些引起计算不稳定的因素。
下面谈一下本书在写作上的一些考虑。试图作为图学的公共基础教程与参考书，比专业基础教程要难写得多。何谓“公共”？何谓“基础”？内容如何挑选？章节怎样组织？问题从哪个角度叙述？等等。教学应该是基于思路的培养而不仅仅是传播知识，本书对这些都进行了精心的设计与安排。本书定下了几个写作原则：一是将问题抽象化，揭示问题的本质；二是既要兼顾到传统理论，又要以公认的基础理论如数学、计算机方法叙述解决问题的思路，尽量将多学科的思想综合起来；三是充分发挥人的主导作用，人脑善于空间思维，因此多从几何的角度考虑问题，注重先从整体进行算法的框架设计，最后才追究具体的细节，将繁复的计算付诸代数的实施。
下面列举几个例子来阐述一下本书的一些写作思路。
还画法几何的几何历史地位，并尝试画法几何的计算化进程。本书将画法几何作为几何的一个分支并确立画法几何在图学中的地位，在这个认知上去阐述画法几何的基本理论，包括投影理论、2D/3D对应理论和尺规作图方法等。画法几何的核心思想是几何问题几何化。本书将画法几何投影作图思想与现代计算技术相结合，综合图解法和解析法的优势，探索画法几何投影理论的计算化问题，最后构造出画法几何投影计算的基本工具和算法，这是图学计算化，特别是画法几何计算化的一个重要部分。
几何表示问题。解决一个问题首先是描述清楚问题本身。几何表示包括两个方面：单个几何元的表示以及多个几何元之间的关系描述。几何代数化的关键是引入坐标系，使几何可以在这个坐标系下实现解析化。这意味着对某一几何引入不同的坐标系，该几何就有不同的解析表示，但几何本身是不变的。因此，对任一几何元，如何设法找到一组最佳向量构建坐标系，在这个坐标系下，几何的表述、求解以及几何间相交关系的求取是最简单的。本书引入“计算坐标系”简化几何表示与几何间求交计算。多个几何元之间的关系描述也是几何表示的一个重要问题。形体，通常是由边界描述的；图形，除了一些辅助线以外，一般也是由边界描述的。本书利用向量概念，对几何元、几何边界进行有向表述，有利于区分图形和形体的内外，简化了二维和三维布尔运算及奇异情况的处理。这一思想统一在“几何数”中表述。
变换机制。“图形变换”的说法并不确切，变换有两种：一种是对图形或几何形体本身的变换，如比例变换、错切变换；另一种是坐标系的变换，导致几何的解析表述的改变，如平移变换、旋转变换。本书采用一种“变换的几何化表示”方法，其理论基础是平面上任意两条共点不共线的单位向量或空间任意3条共点不共面的单位向量就构成一个坐标系。得到的齐次矩阵可以统一描述平移、旋转、错切、对称和比例等变换，而且它的矩阵元素可由基本几何（向量）的定义和求解系统得到。
投影机理。画法几何中讲解轴测投影的目的是绘制轴测图，但是与正投影完全不同的是，轴测图的绘制并不是从“投影”这个定义出发去实现的，而是以轴测轴的定义决定的，按照“沿轴量画”的原则确定空间点在轴测图中的位置。因此建议在画法几何中讲解轴测图绘制时，不强调轴测投影的定义，而是认为轴测图是以二维图形的形式去表现三维立体，使其具有立体感。本书从数学上统一解决了画法几何的各类投影问题，包含正轴测、斜轴测、正等测等轴测的统一表示。
透视参数计算。本书给出了定量求取透视变换参数的通用方法。证明了对一个空间物体，一定存在另一个空间物体，使前者在画面上的透视投影与后者的平行投影是一样的，且保留了深度方向的对应关系。这个性质可使复杂的透视投影转化成简单的平行投影，使图形处理简化。
形计算。形计算是本书的主线，是本书图学计算采用方法的代名词。本书通过一些典型的实例剖析了形计算的内涵，并将形计算引入的几何数、几何基等概念贯穿于全书的算法实例中。对于它们在图学计算中的作用以及如何应用，本书都有独特的阐述。
全书包括导论、形计算、计算策略、几何变换、几何基础、二维计算、三维计算等7章和一个算法索引附录。“导论”部分在大图学的概念下比较完整地阐述了图与图学、图学计算的核心问题；“形计算”部分提出了一种更适合于图学计算的形计算机制，这是本书给出的图学计算的理论体系与实施框架；“计算策略”部分阐述了形计算的实施策略，阐述了保证图学计算的稳定性、几何奇异处理和降维计算的基本思想和实施方法；“几何变换”和“几何基础”两章给出了实现形计算的基础和基本工具；最后，在“二维计算”和“三维计算”两章中，通过一些典型例子给出了形计算的实际应用，展示了图学计算中的一些常用计算策略——如降维计算（含计算坐标系建立、向任意面投影）、几何奇异问题处理等如何在实际中应用，这在图学计算中有引领作用。
本书兼顾了工程制图、计算机图形学和计算机图像处理等图学课程的相关需求，可以作为工程图学、计算机图形学、计算机图像处理、CAD等课程的教材或教学参考书。凡从事与几何信息的获取、表示、处理和分析相关的工作的广大研究人员、工程设计人员、教师和学生等都可直接使用本书提供的思想、理论、方法和技术。
除了已经发表的论文以外，本书的一些观点与内容还在ICGG、中国图学大会等国内外学术会议上作过演讲，与同行进行过不少的交流。本书还得到了国家自然科学基金项目“几何问题几何化及计算稳定性研究（61073086，2011—2013）”的资助。
除了已经列出的参考文献以外，本书还参考或采用了一些图书及网上的资源，不可能一一列出，谨向那些作者表达谢意。
书中不当之处，欢迎读者、专家和同行勿吝指正。
2017年6月5日于上海

目　　录
前言
第1章　导论1
　1.1　图学相关学科1
　　1.1.1　工程图学1
　　1.1.2　画法几何2
　　1.1.3　计算机图形学3
　　1.1.4　计算机图像处理4
　1.2　图学4
　　1.2.1　图形图像的基元是几何5
　　1.2.2　图学的本质是几何5
　　1.2.3　图学计算与几何计算6
　　1.2.4　图学计算基础分析7
　1.3　图学计算中的若干问题8
　　1.3.1　主导形和图的是几何关系而非几何参数8
　　1.3.2　图学计算的重点在于求取几何间的关系9
　　1.3.3　图学计算中的维度不统一9
　　1.3.4　图学计算中的计算稳定性10
　1.4　图学计算模式选择10
　　1.4.1　计算方式与解的表述11
　　1.4.2　数计算与形计算12
　　1.4.3　几何化计算的总体思想13
　1.5　本章总结13
第2章　形计算14
　2.1　形计算的基本概念14
　　2.1.1　形计算在计算中的地位14
　　2.1.2　形计算理论基础15
　　2.1.3　形计算基本架构16
　2.2　几何数17
　　2.2.1　几何数的基本概念17
　　2.2.2　基本几何的几何数18
　　2.2.3　几何连接及几何边界的几何数19
　　2.2.4　几何度量的几何数20
　　2.2.5　向量交点的几何数21
　　2.2.6　交点几何数扩展到圆弧22
　　2.2.7　三维几何数24
　2.3　几何基26
　　2.3.1　几何基的基本概念27
　　2.3.2　几何基的构建28
　　2.3.3　基于几何基的几何求解29
　2.4　变换几何化30
　2.5　降维计算31
　2.6　零域误差32
　2.7　本章总结32
第3章　计算策略34
　3.1　稳定计算34
　　3.1.1　源于数字误差的不稳定34
　　3.1.2　源于几何关系的不稳定35
　　3.1.3　数字误差与几何关系对计算稳定性的影响分析36
　　3.1.4　解决计算不稳定性的方案37
　3.2　几何奇异处理39
　　3.2.1　重交点的取舍规则39
　　3.2.2　重边交点的取舍规则40
　　3.2.3　几何奇异处理算法41
　　3.2.4　三维几何奇异的处理42
　3.3　计算坐标系43
　　3.3.1　二维计算坐标系43
　　3.3.2　三维计算坐标系45
　3.4　向任意面投影46
　　3.4.1　向任意面投影原理46
　　3.4.2　向任意面投影算法47
　3.5　降维计算48
　　3.5.1　降维计算的总体框架48
　　3.5.2　降维计算算法49
　3.6　本章总结49
第4章　几何变换50
　4.1　几何变换的传统理论51
　　4.1.1　齐次坐标及齐次矩阵51
　　4.1.2　几何变换的一般形式52
　　4.1.3　变换及其乘积52
　　4.1.4　二维变换53
　　4.1.5　三维变换53
　4.2　变换的几何化理论54
　　4.2.1　变换几何化的基本理论54
　　4.2.2　常规变换的几何化实现57
　4.3　正投影59
　　4.3.1　投影体系59
　　4.3.2　正投影的基本理论60
　　4.3.3　点的正投影61
　4.4　轴测变换62
　　4.4.1　轴测投影的基本概念63
　　4.4.2　轴向系数与轴间角64
　　4.4.3　轴测投影与轴测图的若干问题66
　　4.4.4　轴测投影变换的一般公式70
　4.5　透视变换72
　　4.5.1　透视变换的基本原理72
　　4.5.2　透视变换矩阵73
　　4.5.3　透视投影转化为平行投影73
　　4.5.4　通过旋转方法生成透视图75
　　4.5.5　通过倾斜画面方法生成透视图78
　4.6　本章总结80
第5章　几何基础82
　5.1　数学基础82
　　5.1.1　向量的表示82
　　5.1.2　向量的基本运算83
　　5.1.3　向量点积83
　　5.1.4　向量叉积84
　　5.1.5　两向量的旋向84
　5.2　基本几何85
　　5.2.1　点85
　　5.2.2　直线85
　　5.2.3　圆87
　　5.2.4　圆弧87
　　5.2.5　平面87
　5.3　基础计算88
　　5.3.1　过平面上两点建立直线88
　　5.3.2　求与已知直线相距为定长的平行线89
　　5.3.3　求两直线正方向的角平分线89
　　5.3.4　以已知半径作圆，与两已知直线相切90
　　5.3.5　已知劣弧段的起点、终点及有向半径，求劣弧段的圆心坐标90
　　5.3.6　求直线与圆的交点91
　　5.3.7　求两圆的交点92
　　5.3.8　求两个已知圆的外公切线或内公切线93
　　5.3.9　过圆外一点作圆的切线94
　　5.3.10　以已知半径作圆，与已知直线和圆相切94
　　5.3.11　空间线与面的关系95
　　5.3.12　平面与平面相交96
　5.4　几何度量96
　　5.4.1　点到直线的有向距离97
　　5.4.2　点到平面的有向距离97
　　5.4.3　点到一条空间直线的距离97
　　5.4.4　点到一空间直线的垂足97
　　5.4.5　直线与平面的距离98
　　5.4.6　空间两直线的距离99
　　5.4.7　三角形的有向面积99
　　5.4.8　平面多角形面积100
　5.5　本章总结100
第6章　二维计算101
　6.1　二维布尔运算101
　　6.1.1　基本原理101
　　6.1.2　两个环的几何运算的实施102
　　6.1.3　两个环运算时奇异情况处理104
　　6.1.4　两个环运算的算法107
　　6.1.5　算法复杂性分析108
　6.2　二维几何裁剪108
　　6.2.1　线性裁剪108
　　6.2.2　Cohen-Sutherland线裁剪110
　　6.2.3　Cyrus-Beck任意凸多边形参数化线裁剪112
　　6.2.4　Liang-Barsky裁剪算法118
　　6.2.5　基于降维的二维裁剪121
　　6.2.6　四种矩形窗口裁剪效果分析1