图学计算基础

    书籍
    计算机书籍
本书是图学的公共基础教程，结合作者30余年的图学研究和教学经验，力求从勾勒图学知识框架的角度组织内容，在内容选材、章节组织、问题描述等多个方面考虑。在编写中，遵循将问题抽象化，揭示问题的本质；兼顾传统理论，以公认的数学、计算机方法描述解决问题的思路，综合多学科的思想；充分发挥学生的主体作用，激发学生的学习热情；注重从框架上进行算法设计，不细究实现的细节。本书内容包括形计算、几何基础、几何变换、几何计算、几何裁剪、几何造型、曲线曲面，这些都是现代工程图学、计算机图形学、计算机图像处理、CAD等课程的基础，因此可作为这些课程的教材和参考书。

前言
第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

　　图形图像在人们生活中的应用已经极大地普及，人类社会已经进入一个图形图像时代。统一图形图像的研究顺应了这个形势，符合社会和科学发展的规律，图与研究图的图学科学的作用将会日益增大。中国图学学会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条共点不共面的单位向量就构成一个坐标系。得到的齐次矩阵可以统一描述平移、旋转、错切、对称和比例等变换，而且它的矩阵元素可由基本几何（向量）的定义和求解系统得到。
　　投影机理。画法几何中讲解轴测投影的目的是绘制轴测图，但是与正投影完全不同的是，轴测图的绘制并不是从“投影”这个定义出发去实现的，而是以轴测轴的定义决定的，按照“沿轴量画”的原则确定空间点在轴测图中的位置。因此建议在画法几何中讲解轴测图绘制时，不强调轴测投影的定义，而是认为轴测图是以二维图形的形式去表现三维立体，使其具有立体感。本书从数学上统一解决了画法几何的各类投影问题，包含正轴测、斜轴测、正等测等轴测的统一表示。