一种基于几何的形计算机制

何援军

（上海交通大学计算机系，上海 200240）

一种基于几何的形计算机制

何援军

（上海交通大学计算机系，上海 200240）

提出一种几何问题几何化的形计算机制。它综合了几何、代数、画法几何及现代计算工具等理论、方法与技术，实现“三维思维，二维图解，一维计算”多维空间的融合。从更宏观的几何角度构筑算法框架，是对常规数计算的补充，可用于相当宽泛的一类几何计算。

几何；几何计算；数计算；形计算

中国图学学会2013年发布《图学学科发展报告》[1]，认为需要在已有的工程图学、计算机图形学和计算机图像学学科基础上建立大“图学”学科。这个结论是基于“形”的概念——它们研究的对象都是形，形的表示与表现。该报告详细阐述了“图”和“形”的关系，认为形是客观世界与虚拟世界的表示和构造，图是形在画面上展现。形的属性是表示，图的属性是表现。形是图之源，图展示形，是形的载体、形之表现。在计算机背景下，图学的主要工作就是由图显示形，由图构造形，以及由一张图变成另一张图。这是对图学科学与图学学科表述与定位的首次尝试。在这个基础上，《图学学科发展报告》对图学科学的理论基础、计算基础、应用基础以及近期的研究方向等重大问题作了阐述。其中，揭示形的几何品质，认识几何与几何计算在图学中的地位和作用的根本性，从形的角度去统一、去研究、去发展图学的基础理论和基本方法的研究是最基础性的论述。

根据《图学学科发展报告》的观点，图学的基本工作是研究“形→图”和“图→形”之间的转换，因此，其本质是几何，最根本的理论基础是几何学。基于此，本文提出一种基于几何概念的“形计算”机制，以更好适应于对形的处理，它的核心思想是几何问题几何化。相对于现有的“数计算”机制是基于数的运算，形计算是一种基于几何的运算机制，更有利于形的表述、图的生成，更能发挥人的空间概念在构建算法中的主导作用，从更宏观的角度去构建算法框架，使计算过程更加结构化、直观化、简单化。既可比较明显地改善数计算的非可读性，也有利于降低计算的复杂度、提升计算的稳定性。

本文将简述这种形计算机制的理论基础、基本框架、实施方法与执行效果。还将论述一些计算在社会发展中的地位、计算的基础、计算方法学、计算方式与解的表述等。讨论图、形、几何与几何计算的关系问题，揭示几何计算的本质与关键，关注问题空间与计算空间的不统一问题等等，作为提出形计算机制的支撑。

1 计算

1.1 计算与它的作用

在人类的社会进步、经济建设和科技发展过程中，“计算”始终都扮演着非常重要的角色。“X计算”已是计算机广为应用的一个概念，例如，科学计算、网格计算、平行计算、智能计算、云计算等。

计算主义者指出“生命的本质不在于具体的物质，而在于物质的组织形式；这种组织完全可以用算法或程序表达出来，所以，只要能将物质按着正确的形式构建起来，这个新的系统就可以表现出生命。”[2]而这种所谓的“正确的形式”就是生命的算法或程序。所以，算法是把非生命和生命连接起来的桥梁，是生命的灵魂。这足以说明计算在社会生活与社会发展中的重要作用。

1.2 计算的理论基础

计算的基础是数学。数学是永恒的！好的数学思想很少会过时，虽然运用方式会发生很大变化。数学上主要有两种推理：符号推理与直观推理，前者源于计数制，后者源于图形制。继数之后，图形将数学的第二个主要概念引入了数学，这就是形，形能充分发挥人的空间思维特长。欧几里德[3]在几何著作中首次系统地使用了图形，少量使用符号，大量使用逻辑。他的著作结合了两种创新：图形的使用和证明的逻辑结构。因此，计算的对象有2种：数和形，它们分别基于数学的2个基础科学——代数与几何。

代数是研究数的科学。代数计算以数为计算对象，常需要公式推导、表达式的化简、函数的微分及积分、精确地解各种方程等。17-18世纪中期，代数学被理解为在代数符号上进行计算的科学，用来研究与解方程有关的问题。到 19世纪末，代数学从方程理论转向代数运算的研究。

几何是研究形的科学。其用人们公认的一些事实列成一些定义和公理，以形式逻辑的方法，用这些定义和公理来研究各种几何图形的性质，从而建立了一套从公理、定义出发，论证命题得到定理的几何学论证方法，形成了一个严密的逻辑体系——几何学。几何学原来的论证方法一直是纯几何的。

代数学者更是一个形式主义者，要的是公理化、形式化，追求严格的、形式的描述。几何与物理学者以几何与拓扑的思想作为基本洞察工具，更关心物理内蕴的表现形式。很清楚，两者属于不同的传统。

当然，计算与工具有关，当今的计算工具主要是计算机，因此，与计算机有关的硬件、软件以及应用理论也都是计算的基础。但是，主要的应该是代数与几何。

1.3 计算对象与结果

计算的对象与结果实质上与计算的性质、实体和工具等有关，不同的计算层面，有不一样的计算对象，需要不同的计算结果。

以往，人们习惯于得到一个明确的数字为解。一般的计算均是基于数的，其计算源与计算结果都是数，可称为数计算，数计算曾是科学计算的主要计算机制。数计算涉及到一个数的机制。最常用的是十进制，但也有例外，例如早期一市斤是16两，这是16进制。计算机的设计是基于电路的开/关机制，表达成数字就是0/1，这导出了2进制、8进制等。目前在计算机中采用的是冯·诺依曼[4](John von Neumann, 1903-1957年)的二进制数制表示浮点数，基于这样的浮点数实现数的计算。

下棋、指挥打仗等也都需要计算，但这些计算本质上已经变成“算计”了，其计算对象和计算结果与常规意义上的数计算大相径庭。

现在，图形、图像在人们生活中的应用大有普及趋势，计算的结果是希望得到一幅由图形或图像表示的画面。这样的计算，遍地都是。图形，不管是静态的还是动态的，都作为解的一种表现形式去追求，对图或者形作为计算源与计算结果的需求大大增加。

计算机作为主要计算工具以后，计算方式与解的表述更是起了革命性的变化。例如，“算法”常作为计算机时代解的一种表述方式被认可、被追求，相应的计算理论与计算方法也产生了。

现代意义上的计算，它不仅可以是常规意义上的一次“算”，也可能是一个过程，搜索过程、决策过程等。因此，计算对象可能并非一个，结果也不一定是一个，甚至是不确定的。但是，万变不离其宗，用于表述计算对象与结果的，主要的还是两种：数和图。

1.4 数计算与形计算

代数管数，几何管形。数引出数计算，形可否引出形计算？

其实，形计算早已有之，在希腊科学中几何学是占统治地位的，其威力之大，以致于纯算术或纯代数的问题都被转译为几何语言：量被解释为长度，两个量之积解释为矩形、面积等。现代数学中仍保留的称二次幂为平方，三次幂为立方就源于此[5-7]。在欧几里德《几何原本》[3]中有五条公理和五条公设作为形计算的基础，人们在公理体系内对几何关系进行推理和计算。画法几何的尺规作图方法也是只用了几种最基本的作图方法就可完成一大类图形的作图。这些，本质上就是一种形计算。

由此，计算不应该只是数计算，还应该有形计算。

1.5 计算的关键

一种计算方法的提出，一个算法的设计首先要考虑的因素就是较高的稳定性，较低的复杂性，再考虑易读性、可交流性等伴随要求。计算的复杂度与稳定性是计算的两个关键问题，也是图形计算中的关键问题。

计算复杂度包括空间复杂性和时间复杂性。空间复杂性一般指表述对象所需要的空间，时间复杂性则是指计算的工作量问题。常从量与质两个方面去降低计算的复杂度，或减少计算对象的数目，或降低参与计算对象的复杂度。随着计算机硬件的发展，质的问题更严重、更重要。

计算稳定性问题是一个长期的难题，本质是计算正(准)确性问题。即使在一些已被广泛使用的大型应用系统中，也存在几何引擎的稳定性问题。这里有理论问题，也有实施问题。导致几何计算不稳定主要有两个原因：一是由数字计算误差引起，通常与数制及计算方法有关；二是由几何本身原因引起，因几何间的重叠(共点、共线、共面等)引起的几何奇异而造成判断的不确定性。Christer Ericson[8]曾对那些只偏重速度、忽视稳定性的研究方法表示担心，觉得“这只是减少了浮点运算”。并认为用一些大规模随机测试很难检测到影响算法鲁棒性的状况。

1.6 计算的方法论

数学是研究现实世界的“数”与“形”的科学，一般认为几何研究形，代数研究数。作为数学的两个重要基本组成部分，几何与代数各有其自己的发展空间和问题域，对应的也有其自己的理论基础和方法学[5-7]。

白马非马，画法几何一直作为工程设计的理论基础，与传统的几何好像相离甚远，也似乎没有人将他列入几何的范畴。其实，画法几何研究的基本对象也是几何，也是研究形的学科。因此，在讨论几何计算时，也应该将画法几何列入几何计算的基础理论与基本工具，构建“大几何”概念。

1.6.1 几何代数化之路

宇宙，一切空间和时间的综合。宇是空间，宙是时间，合为宇宙。

代数涉及的是时间的操作[6]。代数的目标总是想建立一个公式，就是拿来一个有意义的东西，把它化成一个公式，然后得到答案。采用线性、有序的方式去处理问题，一连串的运算被一个接着一个地进行。它更偏重于定量地去得到结果，本质上不会再思考其含义，停止用几何、图形或物理的观念去考虑问题。求解过程一般不直观、不可读，常使得人的空间思维特长荡然无存，计算常常会变得不可掌控。

几何涉及的是空间问题[7]。几何更多的是从空间概念形象地去审视问题，常用几何间的相互关系处理问题。人们努力将一些问题归结为几何形式，借助于图形(模型)的直观，从总体上去构建一个总体框架，去寻求一个全局、直观的解决方案。它更偏重于定性地去得到一个结果，而将枯燥的数字与反复的代数计算分离给计算机去做，求解过程更宏观、更直观。使复杂问题简单化，抽象问题具体化，化难为易，获得简便易行的成功方案。

17世纪初，笛卡儿[9]将坐标引入几何，把代数中形式化符号体系的表示方法引进到几何学中，实现了数与形的紧密结合，使得几何间的计算也能用代数的形式实现，人称“几何代数化”。这是数学史上最丰富和最有效的创造之一，但也使几何与代数之间出现了一种令人感到不太自然的关系。

在笛卡儿把代数中形式化符号体系的表示方法引进到几何学之后，走的基本上是几何代数化之路。纵观历史，几何与代数原本分别考虑“形”和“数”的问题，理论上应该各占半壁江山，然而，历史并不是这样，两者并不平衡。我们不能改变历史，但是，我们是不是应该能从历史中学到一些什么？

1.6.2 代数化还是几何化

先看一个简单的例子，求通过P1、P2和P3三点的圆。可以通过解三元二次方程得到所求圆圆心为：

两式不足之处十分明显：算式十分复杂，而当两式的分母为0时，要轮换点再算，即给出的3点是共点、共线的奇异情况的排除并非显而易见。

但是，如果上面的问题改用几何方法就变为：

(1) 作 P1P2的垂直平分线 L1，作 P1P3的垂直平分线L2。共点的情况可在这一步排除。

(2) 求L1与L2的交点即为圆心。如果无交点，则说明三点共线，无圆可生成。

(3) 圆心和三点中任一点的距离即为半径。

可以看到，从几何的角度，用模拟原始的尺规作图方法解决几何计算问题直观性强、效率很高，奇异情况表现明显、排除简洁。

其实，还有一些问题困扰着纯代数方法，如不必要的复杂度、需要较复杂的数学计算工具、算法时间性能低下、无法完美处理奇异性问题等。

面对一个几何问题，是首先考虑如何将它化成一个代数方程(公式)，送到计算机里，“摇一摇”就得到结果，而不管过程如何复杂；还是顺其自然，回归几何，设法发挥人的直觉，先从空间的角度审视一个几何问题，寻求一个全局、直观地解决方案？这将挑战数百年来大部分人们的思考习惯。

1.6.3 以“形”统一几何与画法几何理论

画法几何研究的基本对象也是几何，也是研究形的科学。17世纪一些几何学家将它的方法与结论视为欧几里德几何学的一部分，直到 1799年法国几何学家蒙日[10](Gaspard Monge, 1746-1818年)非数学地阐述了投影理论，才使画法几何(descriptive geometry)成为一门独立学科。应该从形的角度去揭示画法几何与几何的共性问题，将其应用于几何计算。反过来，这又为画法几何计算化提供了一条新途径。

2 形与形的计算

由于一般的计算都是采用数计算机制，至少，计算的实施过程是基于数计算机制。这使得对形的计算过程变得有点复杂：“形→数”→“数计算”→“数→形”。这样，人的大量工作就会花在“形→数”和“数→形”的转换上，这不符合人的思维习惯。其实，数学主要发生于幕后，起关键作用的是人，人的思维、人的逻辑。“交互”系统的产生，就是充分考虑了在计算机快速中发挥人的直观感知能力的作用，这是一个很大地进步。张景中[11]认为，“几何解题是十分有吸引力的智力活动之一。图形的直观简明，推理的曲折严谨，思路的新颖巧妙，常给人以科学美的享受。”这是符合事实的。

在许多应用领域，对一个问题的求解可描述为如图1所示的过程。

图1 问题的求解过程

(1) 提出问题；

(2) 通过建模表达问题，使问题抽象化；

(3) 用一个几何模型去表示问题；

(4) 将几何模型生成图形/图像，使问题可视化；

(5) 根据生成的图形/图像进一步理解问题，从中思考解决方法。

人们常利用自己的空间直觉(spatial intuition)或者空间知觉(spatial perception)从总体上去考虑问题的解决方案，习惯于从几何的角度去考虑几何问题。努力将一些问题归结为几何形式，因为这样可以使用人的直觉，直觉是人类最有力的武器。

引入形计算机制，最核心的思想就是几何问题几何化。形计算机制是一种基于几何的计算概念与机制，它以几何作为计算单元，以求取几何间的关系作为计算目标。从形的角度去揭示画法几何与几何的共性问题，将其应用于几何计算中。探索以形为核心，将几何、画法几何、代数和计算机等多学科理论与方法的长处融合在一起，实现“从形思考、以数实施”，更好发挥人的思维与计算机计算各自的特长。

2.1 图、形、几何与几何计算

世界由形构造，形由图在画面上显示，因此，形是图之源。在计算机中，形与图均由几何描述，这里的几何是点、线、面，常被称为“几何元”，不同的几何元依照一定的拓扑关系构造成不同的场景，在空间构造形；通过投影在平面显示图，此时，点、线常被称为“图元”，不同属性图元的组合构造了所有的图形或图像。

用两个典型的例子说明图、形、几何与几何计算的关系。

隐藏线消除是将形显示为图的典型算法。消隐过程是一条一条线的输出，每条线需与场景中所有物体（面）进行比较，线的各可见部分的交集即为此线的最终可见部分。因此，整个场景的输出（显示）过程就是一条一条地去确定场景中所有线条的哪些部分该显示，哪些部分不该显示。这本质上是对几何——一条条线段的分割工作。

真实感图形绘制则是将形显示为图像的典型算法。这是一个光强与色彩的量化、纹理映射、图像合成、帧缓存等基于物理、光学、色彩理论和技术的复杂计算过程。这里，贯穿整个算法的关键计算是从光源发出的每一条光线与景物表面的空间线面的求交，包括反射和折射计算。这些，也都是几何间的求交、比较工作。

基于以上分析，本质上，图、形、几何与几何计算的关系可以简单地表述为：形是表示、是输入，图是展现、是输出；形与图的基本元素是几何，形构造与图形成的本质都是几何的定义、构造、度量和显示。

2.2 模型与图形的本质

模型与图形的本质也决定于几何之间的相互关系。下面用两个简单例子说明这个论点。

图2(a)表示平面上由4个点构造的矩形，它们的拓扑关系为1-2-3-4-1。图2(b)是保持拓扑关系而改变其中一个点P3的几何参数，它仍能揭示原图的基本构图形状。而图2(c)的4个图形仅改变了4个点之间的连接关系，几何参数相同的点因拓扑关系的不同而构成了完全不同的图形。

图3左上角12条线段显示的是一个三维空间框架，如果对这些线段施以不同的裁剪，就得到图3中不同的图(这里列举了5个)。这些图反映在人们大脑中是不同的形，或是实心的、或是空心的、或是盒子等。这里，空间线的几何参数并没有改变，只是用线的不同部分去构成图形而已，本质上也是几何间的拓扑关系改变了，导致展现出不同的形。

图2 几何参数和拓扑关系的改变对图的影响

图3 几何元的不同部分展现了不同的形

因此，模型与图形的本质不是构成它们的几何本身，而在于几何间的组织形式，决定于几何之间的相互关系。

2.3 图形计算的矛盾与关键

2.3.1 图形计算的基础是几何求交

图形生成、几何造型，那怕是直线、曲线，平面、曲面，最基本的操作是几何的定义与求交。在一个典型的几何造型系统中，用到的几何元素通常有25种，为了建立一个通用的定义与求交函数库，所要完成的求交函数约为种！几何的构造、定位和度量工作虽然千变万化，但都基于这些少量的基本几何函数，它们是几何计算的基石，起了“基”的作用。

2.3.2 几何空间与计算空间的不统一

工程技术人员都有过用三视图表示空间物体以及从三视图得到立体图这样训练的经历，这是由于实体空间(三维)与表示空间(平面)的不统一。人们知道，形是二维及以上的，图是二维的，而计算是一维的。因此在设计一个算法时存在这种不统一，即算法的思维空间与实施(计算)空间是不一致的。这增加了在设计算法时思维的复杂性，甚至会出现某些混乱。显然，直接从二维乃至三维去考虑问题无疑会减少算法设计的复杂性，因为，算法的设计与最后的数字计算并不一定非要捆绑的。

遗憾的是，人们常常忽视这个几何空间与计算空间不统一的矛盾，长期以来人们大多使用的方式——“用一维计算处理二维甚至三维问题”。正如吴文俊[12]总结数学机械化的实质是“把质的困难转化为量的复杂”一样，人们习惯于这样的复杂。

2.3.3 几何奇异是几何计算不稳定性的主要原因

几何计算的不稳定主要由数字计算误差或几何本身引起。由于所处理的模型通常是有界的，几何元素也变成有界的，两几何间的交点会处于共点、共线、共面等奇异状态。这会导致几何计算的错误，造成几何造型系统的不稳定，这是几何计算的主要困难，处理不好往往导致系统的崩溃。几何奇异的处理涉及到两个问题：一是几何奇异的判定；二是对已知几何奇异的处理。现在对几何奇异的判定常由数计算实现，依赖于某个公差 ε，这涉及计算数学近似计算理论以及计算机的浮点运算。对已判定的几何奇异，因为几何奇异的本质是几何关系的奇异，从几何角度去判定反而会直观些。

2.3.4 降维计算是降低几何复杂性的有效手段

在一些大型、实时的应用场合，计算效率会影响到系统的应用。形计算将探索采用画法几何投影理论与2D/3D对应理论实现降维计算。建立解的空间与平面的映射关系，将空间问题转化为2个或3个平面问题，分而治之。计算机图形学中的梁-Barsky裁剪算法[13]的本质就是采用降维方法把二维裁剪分解为2次一维裁剪，将三维裁剪分解为2次二维裁剪，既降低了几何复杂度，也增加计算的稳定性。

3 形计算机制

3.1 形计算的基本概念

不能完全按照数计算机制常规概念去理解形计算，即不能严格的照搬数计算机制的模式一样去定义、去理解形计算。形计算更多的是在思考层面，而不是在实施层面。它以直线、圆等几何元的定义、相交等基本运算作为基础，考虑、规划几何问题的求解策略。引入了“几何数(geometric number)”和“几何基(geometric basis)”两个概念，在这个基础上构建形计算的基本架构如下[14-16]：

(1) 引入几何数，协助表征几何定义与几何间的关系，并辅助整个计算过程。

(2) 对变换实施几何化，尽量使计算在相关几何的“标准坐标系(计算坐标系)”下实施。

(3) 引入几何基，构建基本几何的定义、相交等的基本工具，作为形计算的初始几何基(它将繁复的代数计算隐藏在几何基中)。

(4) 对平面问题，对图形进行构造性求解(参考尺规作图)，求得的几何基序列记录了构造过程，也得到了以“几何基序列表述”的平面解(这同时构成了一个更高一级几何基)。

(5) 对空间问题，根据主几何元建立相应的计算坐标系，参考2D/3D对应理论，在三维整体概念下建立空间几何与平面图形间的映射关系，得到三维形的二维图表示，将空间问题降为平面问题。在平面上求得几何基序列解，最后反变换返回到空间问题的最终解(最后也构成一个三维几何基)。

相对于数计算，这种形计算机制尽可能的用几何方法去处理几何问题，更偏重于从形的整体角度去构建一个算法框架。在简化问题的描述、降维计算以及降低计算复杂度等方面能补充数计算的不足。对数计算的非可读性、几何奇异引起的计算不稳定性等方面也有较大的改善。这是对数计算机制的一种很好的辅助，是在人的思维掌控下，能将几何、代数及计算机理论、方法与技术更好结合的新计算方法(机制)的一种探索。

3.2 形计算的理论基础

下面简述在图形/几何计算中引入形计算的主要理论基础，一些最基本、最基础的常用理论。

(1) 画法几何的理论。画法几何研究的基本对象是几何，它的理论基础是投影几何，也是研究形的科学。不同于数学上的几何偏重于解析方法，它以综合法得到一些定性的关系，用几种最基本的作图方法就可完成平面上一类图形的作图，这就是所谓的“尺规作图”理论。尺规作图本质上是用几何方法处理几何问题，而且这种原始的尺规作图的基本工具很少，一般认为只有8种：作一条线段等于已知线段、作一个角等于已知角、作已知线段的垂直平分线、作已知角的角平分线、过一点作已知直线的垂线、已知一角/一边做等腰三角形、已知两角/一边做三角形以及已知一角/两边做三角形等。它最朴素的思想是将复杂的几何问题分解成有序的、简单的基本几何问题。这是一个很好的思想，引入几何基的原始想法就出于此。

画法几何常采用正投影办法，用3个平面视图去表述一个三维物体，由尺规作图得到其视图。反之，也可由3个平面视图还原三维物体，即所谓的“2D/3D对应”理论。尺规作图走的是几何化之路，偏重于定性而不是定量地考虑问题。2D/3D对应等理论使空间问题降为平面问题，有可能降低空间问题计算的复杂性。形计算的降维充分利用了画法几何的投影。

(2) 向量理论。形或者图形的本质不是几何元本身而是几何元的组织形式。因此，仅仅用几何信息去表示几何元是不够的，因为这只能表述几何本身，不能表述几何间的相互关系。这就需要一些属性信息去补充几何元之间关系的表述。例如，图形的一条边界应该有外边界与内边界之分，即需要有一个属性信息去表出该边界的哪一侧是图形的内部、哪一侧是外部？而在三维空间，属性信息能表达出物体的内部或外部、平面的正面或反面等。更甚，对交点，关心的不仅仅只是它的几何位置信息，更关心交点在两个几何关系中的作用，例如，这个交点对另一边界是“入点”还是“出点”，因为这直接关系到图形运算的过程与结果。

引入向量去表示线段是很有效的：向量有方向，使边界能很好地区分出左右，两向量的旋向能决定它是入点还是出点等。这是在形计算中引入几何数的基础。

向量理论在形计算中的另一个应用是变换的几何化。平面上任意2条不共线相交向量构成了一个坐标系(在空间则是 3条不共面向量构成一个坐标系)，而笛卡尔将几何代数化以后，使向量也可用数字的方式表出和运算。利用这2个性质以及矩阵论，可对变换实施几何化。

(3) 高等代数理论。高等代数线性空间理论中的“任一向量可以用它的基底线性表出”思想也是引入几何基的一个理由之一。

利用齐次坐标与矩阵理论实施几何变换也源于高等代数理论。

(4) 算法理论。计算机的发展使解的结果表述出现了很大的变化，例如，一个算法就是解的表述形式，而且，在一个算法中，可能还得到了多个希望的结果。包含一个算法之中可有许多计算，几何运算、代数运算、逻辑运算等。这正是需要的结果：一个算法对外就是一个几何基，但是，它将复杂的过程包含在其中了，而对外(对设计者或应用者而言)，只是一个极其简单的结果——一个几何基而已。这使得解决一个复杂问题的框架变得相当简单、十分清晰。

另一方面，随着几何基的层层构建、逐渐扩展，形计算的基础也变得越来越扎实，工具越来越多，解决问题的方法会变得越来越多。

3.3 形计算的框架

形计算的核心是几何问题几何化，需要厘清几何与代数、计算机、画法几何等的关系，综合这些理论与知识、思想和方法去构建形计算的理论架构，采用合适的表示与结构去构建形计算的实施框架。简化求解过程，便于解的表述与传递，形成统一、规范的形计算体系。探索一种发挥几何直观、简洁特点的几何化求解方法，追求形、数结合的新突破。形计算的基本框架如下：

(1) 在几何定义与几何关系的表述中引入几何数。天地万物，阴阳而已。一个阳爻符号“－”与一个阴爻符号“--”书写了一部易经，“0”与“1”构建了整个计算机体系，物理中电之“正/负”、电路之“开/关”，……，均乃阴/阳之分也。几何定义之“左/右(向量)”、“内/外(边界)”、“进/出(交点)”，几何关系之“离/交/切/含”、几何度量之“正/负(面积)”、“逆/顺(角度)”等何尝不只是阴阳之分？借用了莱布尼茨“如果存在这样一种代数，它可被称为‘几何代数’，它的元素可被称为‘几何数’”而用几何语言进行几何计算”[5]的宏伟设想中的“几何数”一词。在形计算中引入几何数表示几何的阴/阳两极，它涉及几何的表示、构造、定位、度量及几何间的关系处理各个方面，如：

· 对基本几何元直线、圆(弧)、面等引入方向(左/右、顺/逆、前/后)；

· 对几何的长度、面积、体积等引入正负(正/负)；

· 将几何边界分成外边界与内边界(左/右)；

· 对几何间的交点区分“入点/出点(负/正)”；

· 对描述直线、平面等的系数进行规格化(单位法向量)；

· 几何间的连接遵照“皮带轮法则”；

· 强调几何在“标准坐标系(计算坐标系)”下描述与运算；

· 等等。

几何数的定义符合自然规律，也符合人的认知体系，它的引入将能更好地表述几何的属性，使几何间的关系更清晰。

(2) 在几何求解中引入几何基。几何基的引入吸取了画法几何尺规作图、高等代数线性空间关于向量可用它的基底线性表出以及计算机算法的思想。由此，对几何问题解的新解读就变成：“几何问题的解可由几何基的序列表述”。几何基的原始模型可以作以下抽象化的表述：几何基是几何元操作的抽象表示，一种对几何元的原子操作，也是几何关系的表现，它构建了几何解的基础。

幸运的是，在最底层的几何基数量很少，一般的几何关系主要包括以下6种类型：相交、相切、平行、垂直、分比、内含，这就可以使几何基的构建做到“精致、精确、简单”。而且，由于对几何误差、几何奇异的处理分散到这些原子操作之中，这会提升几何引擎的稳定性。由于几何问题的解是用几何基的序列标出的，这增加了解的可读性。最后，还可以用已有几何基序列构建高一层次的几何基。这样，几何基构建了几何问题解的基础——算法基础和工具基础。

最后，引出的另一个问题是，如何将一个几何问题归纳成为几何基的序列，甚至能够自动或半自动的求取这个序列？也给这个思想提供了又一个发展空间。

(3) 几何变换采用几何化方法。几何变换包括同维变换及降维变换，形计算中对几何变换也实施几何化[17]。

平面上任意两条相交(不共线)的单位向量构成一个新坐标系，新、旧坐标系间的坐标变换可由两条相交向量在原坐标系下的直线方程系数及齐次项表出。

空间任意3个相交平面的单位法向量构成一个新坐标系，新、旧坐标系间的坐标变换齐次矩阵由3个相交平面的规格化方程系数及齐次表出。

变换的几何化表示方法所得到的齐次矩阵统一描述平移、旋转、错切、对称和比例等变换，而且它的矩阵元素可由基本几何(向量、平面)的定义求解系统得到。

(4) 计算时引入计算坐标系。计算坐标系的引入使点、线、圆、面，以及三角形、球面、锥面、柱面等基本几何能在它们所谓的“标准坐标系”下解析描述，这使几何的表述与相交关系的求取更为简单，空间几何的降维也一般可在正投影下进行，表述简洁，计算复杂度也常会降低。

3.4 形计算的实施

3.4.1 形计算的实施框架

形计算在空间层面整体考虑几何问题的求解方案，实施框架如图4所示。

(1) 几何数协助表述二维和三维几何及几何间的关系，简化求解过程；

(2) 二维图形寻求由几何基序列表述的解；

(3) 三维物体经降维后化为1～2个二维图形，在二维面上求解，最后将交点反变换得到三维解；

(4) 在几何层面上考虑几何奇异问题，通过对几何数的简单运算，解决之；

(5) 形计算实施过程中的所有变换实现几何化。

图4 形计算的实施框架

3.4.2 几何基的构筑

下面以一个最基础、最简单、最常用的几何操作说明几何基的设计(图5)。

例：过两点作直线的几何基lpp()。两点：P1(x1, y1)、P2(x2, y2)，直线L：ax+by+c=0。

图5 过两点作直线的几何基

从画法几何角度看，这是一次通过2点作直线的尺规作图。

从几何角度看，这是基本几何元(直线)的产生工具。

从代数角度看，这是一系列数字(值)运算，由一些已知变量得到另一些需求变量。

从计算机角度看，这是用计算机语言实现的一个算法(子程序)。

几何基的构造本身也是基于几何化思路，具有几何意义的，且以几何操作的面目呈现。

3.4.3 变换几何化的实施

以“向任意平面的投影”的例子来阐述变换几何化的实施方法[18]。

在坐标系Oxyz下任意给定有一共点的3个相交平面，a1x+b1y+c1z+d1=0，a2x+b2y+c2z+d2=0，和a3x+b3y+c3z+d3=0，且单位法向量分别是：n1=(a1, b1, c1)，n2=(a2, b2, c2)和n3=(a3, b3, c3)，这3个空间单位向量构成一个新坐标系O*x*y*z*（互相垂直时构成直角坐标系）。那么，新、旧坐标系的坐标变换矩阵分别为：

新、旧坐标的变换式为：

(X*Y*Z*H*)=(x y z 1)Txyz_x*y*z*

(X Y Z H)=(x*y*z*1)Tx*y*z*_xyz

由于 3个向量是可以任意定义的(两两互相垂直仍是直角坐标系)，这就可以任意构建合适的计算坐标系，也意味着可以任选投影平面，达到简化计算。计算坐标系的选取往往依赖于相关几何元的性质，可以参考某一个几何为主建立(也决定了投影平面)，该几何可作为“主元”，例如直线与球相交，以球为主元，圆锥与球求交，以圆锥为主元，等等。

3.4.4 平面形计算的实施

用一个“求取过平面上3点的圆”例子来阐述平面上形计算的实施过程。如果将“作 2点的垂直平分线”的几何基命名为“LPPN()”(表述时只对名字感兴趣而省略参数)，将“求两直线的交点”的几何基命名为“PLL()”，“CPPP()”表述为3点所求的圆。解的过程如表1。

表1 用几何基序列表述求解过平面上3点的圆

用几何基序列表示就是 CPPP()={LPPN，LPPN，PLL}。而CPPP()又构建了新的求圆几何基。

这是从几何的角度去描述求解过程，使算法设计的思考过程变得直观，也更宏观，更可喜的是求取交点的代数实施过程被省略了。因此，引入几何基是企图，或者可以淡化(或隐藏)代数表述和代数运算，这强调了用空间的思维去构建与描述整个求解过程。

3.4.5 空间形计算的实施

空间问题的形计算尽量采用降维计算，通常会利用画法几何的投影与2D/3D对应理论。空间两几何的求交算法可简单表述如下(参考图 6中空间直线与球面求交的实施过程)。

空间形计算求交算法：

步骤1. 根据参与运算几何元的的性质，构造计算坐标系(以球心为原点，直线方向为x轴方向构建计算坐标系)，建立V/W/H绝对投影体系。将参与计算的两个几何元的参数(点的坐标，球中心与直线的两端点)变换到计算坐标系下。

步骤2. 应用2D/3D对应理论建立空间几何元降维前后的计算关系，形成投影面上的计算方案（在2个投影面上分别求直线投影与圆①与圆②的交点）。在两投影平面各自构造几何基序列，分别得到两几何元交点在两投影面上的坐标参数，并将它们合成为三维交点参数。

步骤3. 如果有交点，将得到的交点参数逆变换回原始坐标系。

算法包括预处理(步骤1，构建计算坐标系并作正向变换)、实施(步骤 2，在新坐标系下的坐标平面上求取交点，这是用几何基的序列表述的)和后处理(步骤 3，将交点坐标逆变换)三步。其中，求交过程在二维平面上进行，例中用了 2次“直线与圆求交”几何基。

图6 空间直线与球面求交形计算的实施过程

3.5 形计算的执行效果

通过几何数引入及降维处理两个方面说明形计算的执行效果。

(1) 几何数在形计算中的作用。几何数在形计算中作用是多方面的，表2列出了它在几何表示、简化计算、解的选择等方面的例子。

表2 几何数在几何表示、简化计算、解的选择中作用的例子

(2) 基于几何数的二维布尔运算。平面上的布尔运算是对两个图形进行交、并、差操作，由两个图形产生新的图形。图形由边界描述，运算也只要通过边界进行，新边界由原图形双方的部分边界组合构成。关键点是边界的改变在原图形双方边界的相交处，求取这些交点，根据布尔运算的类型得到新边界的走向。

文献[19]叙述了一种基于几何数的十分简单的二维布尔运算算法。根据边界的几何数引入环表示边界(外边界与内边界分别由外环与内环表示)，这样，图形边界就具有方向，边变成向量，图形也就有了内、外之分。交点的几何数决定交点是“入点”还是“出点”。

算法十分简单：从某一个交点出发，对并(交、差)运算，若交点几何数为负(正)，则转向另一环(顶点则按原走向搜索下去)，直至回到出发时的首交点，就得到一个新边界(环)。一旦所有交点均被遍历，算法结束。

这里，交点的几何数能够根据运算的性质协助决定环的走向，新边界的内外性质在求解过程中同时被确定，也避免了从顶点出发需要进行繁琐的包容性测试，计算工作量较少。运算中的几何奇异问题也可由交点的几何数简单的予以解决。

图7展示了对两个图形A与B求并集的形运算过程，分别从交点10和交点13出发得到A与B并集的2条边界(图7(b)，圆圈里的数字为交点，方框里的数字为顶点)。

图7 对两个图形A与B求并集的形运算

(3) 基于几何数的几何奇异处理。几何计算不稳定的主要原因是“几何奇异”(属于理论层面)和“计算误差”(属于实施层面)。即判定是否几何奇异(未知问题变成已知问题)与处理几何奇异问题(解决一个已知问题)是计算稳定性(共性问题)的2个方面。如何在理论上(整体)解决几何奇异问题一直没有很好解决。可以依据“交点几何数”概念，可简洁、有效地解决几何奇异问题。设两向量交点的几何数取“入点”为“-1”，“出点”为“+1”，那么就有以下重交点与重边交点处理规则。

重交点取舍规则(图 8)：将重交点的几何数累加，若几何数的代数和为0，则取消形成此重点的各交点；否则，合并为一个交点，并以代数和的符号作为其几何数。

重边交点的取舍规则(图 9)：如果在同一向量上有连续两个交点的几何数相同，则若几何数均为+1，删除后一个交点；若几何数均为-1，删除前一个交点。

两个规则只是对交点几何数的简单运算，但它从理论层面上解决了几何的已知奇异问题。

形计算中解决几何计算奇异问题的方案框架如图10所示。

图8 重交点的取舍

图9 重边交点的选择

图10 形计算中解决几何奇异问题的总体方案

(4) 三维求交中的降维处理。给出2个比较典型的三维求交例子，说明通过降维处理后形计算中的执行效果。

空间两三角形关系。文献[20]用这种形计算机制基于投影降维对空间两三角形A与B的求交计算进行了测试。基本思想是：以 A所在平面作为 xy坐标平面，该平面的法向作为z轴，并以A的一条边作为x轴建立计算坐标系(图11)。在这个坐标系下，2个三角形的表述与关系变得十分简单：空间两三角形的关系变为平面上线段-线段(图12(a))、线段-三角形(图 12(b))间的关系，几何奇异问题也可以在平面上考虑了。

对40对空间三角形进行重复1百万次相交计算，分别在笔记本电脑与台式电脑两类机器上进行测试，结果如下：在笔记本电脑上，0.95 s可处理1百万对三角形的相交计算(关系判别)；在台式电脑上，0.70 s可处理1百万对三角形的相交计算。

视锥体裁剪。文献[14]给出了一个视锥体裁剪的例子。视锥体裁剪是3D显示系统的基础技术之一，对算法效率的要求较高。视锥体是一个观测金字塔(图 13)，用代数办法求取直线(线段)在视锥体内的可见部分，通常要在3D空间计算直线与6个面的交点(最多6次)，每次求交后还要做交点在6个面(2个矩形、4个梯形)上的包容性测试。

图11 两空间三角形求交时的计算坐标系

形计算方法是以视锥体的两个对称平面及视锥体的下底平面作为坐标平面，视锥体下底中心到上底中心的向量作为z轴，建立视锥体的计算坐标系与V/W/H投影体系(图14)。在这个计算坐标系下，视锥体在V面上的投影Tv与在W面上的投影Tw均为等腰梯形。空间直线投影在V面与W面上分2次二维裁剪，合成其结果即得三维裁剪结果，且无包容性测试。

图12 计算坐标系下空间两三角形在投影面上的关系

图13 视锥体与计算坐标系

图14 视锥体裁剪化成2次平面裁剪

在文献[14]中可以看到“直线与圆柱面相交”、“直线与圆锥面相交”等更多的例子。

4 总 结

讨论了一种基于几何的“形计算”机制。它以几何作为计算元，以求取几何间的关系作为计算目标。引入几何数协助表征几何关系，引入几何基构建几何计算的基本工具，将繁复的代数运算分解到这些基本原子操作中，寻求解的表述与传递的新方法。

形计算机制的核心思想是“回归几何”，扩大几何的自然属性在几何问题求解中的作用，淡化代数化的实施过程，弱化“用一维的代数方法去决定二维几何关系”的矛盾；探索一种“从定性、直观的角度去思考，以定量、有序的方式去求解”的几何计算理论和方法，达到“形思考、数计算”或“定性思考、定量求解”的境界；寻求“三维思维，二维图解，一维计算”的多维空间融合。

相对于常规的数计算，形计算更偏重于从更宏观的形整体几何角度去考虑与设计几何问题的解决方案，使计算过程结构化、直观化、简单化。对数计算的非可读性、几何奇异引起的计算不稳定性以及降低计算复杂度等方面有较大的改善。这是对数计算机制的一种很好的辅助，也是对人、几何、代数及计算机相结合的新计算机制的一种探索。

[1] 中国图学学会. 2012-2013图学学科发展报告[M]. 北京: 中国科学技术出版社, 2014: 3-30.

[2] Piccinini G. Computationalism in the philosophy of mind [J]. Philosophy Compass, 2009, 4(3): 515-532.

[3] Euc1id(欧几里德). 几何原本[EB/OL]. [2015-01-12]. http://baike.baidu.com/view/44606.htm.

[4] 百度百科. 冯·诺依曼体系结构[EB/OL]. [2015-01-12]. http://baike.baidu.com/view/7719.htm.

[5] Michael Atiyah. 二十世纪的数学[J]. 数学译林, 2002, (1): 1-24.

[6] 百 度 百 科 . 代 数 学 [EB/OL]. [2015-01-12]. http://baike.baidu.com/view /556393.htm.

[7] 百 度 百 科 . 几 何 学 [EB/OL]. [2015-01-12]. http://zh.wikipedia.org/wiki/%E5%87%A0%E4%BD% 95%E5%AD%A6.

[8] Christer Ericson. Triangle-triangle tests, plus the art of benchmarking [EB/OL]. (2007-09-12). http://realtimecollisiondetection.net/blog/?p=29.

[9] 将几何代数化的数学家——笛卡儿[EB/OL]. [2015-01-12]. http://bbs.matwav.com/archiver/? tid-137115.html.

[10] 刘克明, 杨叔子. 画法几何学的历史及其现代意义——纪念蒙日画法几何学公开发表 200周年[J]. 数学的实践与认识, 1998, 28(3): 281-288.

[11] 张景中. 几何问题的机器求解[J]. 科学, 2001, 53(2): 1-4.

[12] 吴文俊. 数学机械化——回顾与展望[EB/OL]. [2015-01-12]. http://tieba.baidu.com/p/177537298.

[13] 何援军. 计算机图形学[M]. 2版. 北京: 机械工业出版社, 2009: 180-183.

[14] 何援军. 几何计算[M]. 北京: 高等教育出版社, 2013: 1-26, 226-240.

[15] 何援军. 对几何计算的一些思考[J]. 上海交通大学学报, 2012, 46(2): 18-22.

[16] 何援军. 几何计算及其理论研究[J]. 上海交通大学学报, 2010, 44(3): 407-412.

[17] 何援军. 图形变换的几何化表示——论图形变换和投影的若干问题之一[J]. 计算机辅助设计和图形学学报, 2005, 17(4): 723-728.

[18] 何援军. 投影与任意轴测图的生成——论图形变换和投影的若干问题之二[J]. 计算机辅助设计和图形学学报, 2005, 17(4): 729-733.

[19] 章 义, 于海燕, 何援军. 二维布尔运算[J]. 上海交通大学学报, 2010, (11): 1486-1490.

[20] 于海燕, 何援军. 空间两三角形的相交问题[J]. 图学学报, 2013, 34(4): 54-62.

A Shape Computing Mechanism Based on Geometry

He Yuanjun

(Department of Computer Science & Engineering, Shanghai Jiaotong University, Shanghai 200240, China)

Proposed a new computing mechanism called shape computing to treat a geometric problem in a geometric way. In this computing mechanism, theory and methods in geometry, algebra, descriptive geometry and modern computing tools are synthesized. A new paradigm of multi-dimensional integration is proposed, i.e. 3D thinking, 2D diagrams and linear computing. It is apt to build an algorithm framework in a macro geometric perspective. It will provide a much more efficient supplement to normal numeric computing to solve a very wide class of problems in geometric computation.

geometry; geometric computing; algebraic computing; graphic computing

TP 391

A

2095-302X(2015)03-0319-12

2015-01-25；定稿日期：2015-03-25

何援军(1945-)，男，浙江诸暨人，教授，博士生导师。主要研究方向为CAD/CG、几何计算。E-mail：yjhe@sjtu.edu.cn