计算机时代，无论是设计、制造，还是仿真，都依赖于模型。模型的主元是几何，点、线、圆、曲线、平面、曲面，这些几何按照一定的关系组合起来就构成几何模型，它们彼此之间具有特定的空间关系。几何元的表示、组织均被数字化而成为数字模型。这样的对象由两部分组成：数字信息，例如顶点坐标或平面方程；符号数据，指定表面和边缘边界、邻接和关联。几何模型贯穿于数字化制造各个环节。模型的表示、构造、转换和处理就是几何计算。几何算法的输入和输出通常都会同时包含数值数据和符号数据的数据结构。虽然可以认为符号数据是准确的，但数值数据通常是不准确的。因此，几何算法必须考虑到内部数据不一致的可能性，开发出能够得到准确结论的基本技术。图1和图2的两个几何计算不稳定的例子。表面上是显示及z缓冲冲突等引起的，但实际上是几何造型系统底层核心的稳定性，即依赖于几何计算的鲁棒性。![]()
图1 高亮显示的边穿透了面，这是不希望看到的
![]()
图2缓冲冲突导致的不良现象
http://en.wikipedia.org/wiki/Z-fighting
几乎所有几何算法的实现都会因为某些正确的输入而失败。即使在一些已被广泛使用的大型应用系统中，也存在几何计算的稳定性问题。这是为什么？
1 几何计算不稳定本质分析
模型由点、线、面的各种基本几何组合而成，基本几何由坐标等几何参数描述（几何信息），这是数值数据。几何组合表述几何间的关系（拓扑信息），这是符号数据。几何信息是实数，有误差和错误；拓扑信息是正整数，只有错误。信息有错误，计算结果也就错了；信息有误差，计算就不稳定，计算结果不定。“错误”引起的错，在明处，有结果；“误差”引起的错，在暗处，结果不确定。“正确”引起的错，更为可怕。例如几何间的共点、共线、共面是几何模型中的客观存在，这是正常的，所谓“正确”引起的错，这是最难的事，是解决几何计算稳定性的重点。一是代数误差，由数据输入误差、数字表示误差和由数字计算误差引起；
二是几何误差，由几何本身，因几何关系奇异引起，造成几何选择与几何重组的困难。
1.1 代数误差
数据误差。输入数据存在错误或误差，这是原始数据误差。工程上，描述零件的几何外形是外界输入的，输入的数据有错或有误差。原始人工输入的数据存在错误，这是不可避免的，需要仔细检查，逐个改正。还有一些输入源于其他算法或软件，如算法输出参数或文件转换误差，造成后续工序输入的模型描述误差，这就复杂一些。表示误差。现用的计算机浮点数制本身就是一种近似表示，几何体在浮点运算环境下的表示本身就是不精确的，几何计算也是近似的。因此，几何计算的不稳定是天然的。由于顶点在3D空间中以浮点数表示的，计算时舍入误差引起顶点的不正确表示。如图3，由于顶点A与B不重合引起缝隙和孔洞的产生（图3左），需要将A与B合并在一起（图3右）。![]()
图3顶点误差引起缝隙和孔洞
计算误差。在上述数据误差上进行的是近似计算，引起计算误差及误差的积累与扩散。即使数据是由计算机内部计算传递得到的，经过大量的浮点运算使所得结果的有效数字不能得到有效的保证。
Dobkin和Silver【1】 曾经用一个非常简单的例子说明浮点数下精确计算的困难（图5）。![]()
Figure 5
设计一个操作，考虑平面上一个五边形A，画出A的五条对角线，它们的交点定义了一个内含的五边形B。称从A到B的操作为IN，并象征性地记为B=in（A）。类似地，设计一个反操作，将五条边C延伸到它们的外交点，从而得到一个外接五边形D，称这个操作为OUT，记为D=out（C）。A= out（in（A）） （1）
取一个五边形A，执行上述两个操作（1）和（2），即B= in（A），然后计算C= out（B）。比较C和A的顶点坐标，理论上，它们应该相等，即C=A。这样一个来回算一次，记为m=1。考虑一个顶点为(0,0)，(1,0)，(0,1)，(1+p, 1)和(1,1 +p)的五边形，所有计算都是在单精度IEEE标准浮点算法中执行的。对于m和p的几个值，表1生动展示了实践中，即使对于小至2或3的m值，它们也可能会产生很大的误差。![]()
上述在五边形上迭代的两个操作，主要计算就是求两条直线相交的交点：
a1x+b1y+c1=0
a2x+b2y+c2=0
简单的场景，少量的数据，常用的计算，引起不可预见的错误，让人唏嘘。1.2 几何奇异
现在针对计算稳定性的理论与算法的研究大部分集中于数据表示误差与数字计算误差上。Christer Ericso【2】曾对那些只偏重速度、忽视稳定性的研究方法表示担心，他认为现在的算法研究常出现2个偏向，一是只偏重速度而忽视稳定性（robustness），偏重速度的研究方法只是减少了浮点运算，是令人担心的。二是采用一些大规模没有理论分析的随机测试去验证算法的稳定性，很难检测到影响算法的特殊状况。除了代数计算引起的不稳定以外，另一个引起几何计算不稳定的是几何关系引起的不稳定。源于几何关系的不稳定。构造模型的几何元素不是数学上的直线、圆等，而是有限的线段、圆弧，这就会造成几何间的重叠（共点、共线、共面等）现象。这不是因为几何参数误差而引起，而是两个几何元素或几何模型位置的重合原因引起几何奇异造成几何计算中出现几何元的选择性错误，例如，对这两个图形进行布尔运算时边界走向的选择就会不确定，造成计算的不稳定。而因为几何参数的误差，可能随机地判定边界为奇异或非奇异接触，这更造成了布尔运算的不可控。半射线交点计数判别法【3】，其基本原理是：以被测试点P为起点作任何方向的半射线（为方便，采用水平向右半射线），当该半射线和多角形的交点个数为奇数时，点P在多角形的内部；当交点个数为偶数或为零时，点P在多角形的外部（图5）。例如图5中点P1与边界交点计数是1个，奇数，P1在边界内部，点P2与边界交点计数是2个，偶数，P2在边界外部。但这种测试办法是原理性的，不能投入实际使用。但当所选择的半射线通过多边形顶点P3，与边界交点计数是3个，奇数，判断出错。![]()
图5
需要解决半射线通过多边形顶点或者与多边的边重合时，交点应如何记数的问题（图6）。![]()
图6
这是特殊几何关系造成算法的错误，而出现半射线通过边界顶点或与边界重合是正常现象。半射线交点计数判别法进行包容性测试只是几何计算的简单例子。几何内核算法的情况远比它复杂。图7中两个边界（其中一个用了矩形且用细线表示）中处于奇异状态的位置关系到处存在（打○点者，例如①、②、③、④）。足以作为测试题，去检验对这两个边界所包含的图形进行布尔运算算法的检验。
如果没有一个从理论去解决这些问题，而只是常常采用的“群举法”和“个性化”处理策略。有一个处理一个，那些商业软件的稳定性就靠长期的运行，碰到的类型多了，出现的错误就减少了，但也只是仅此而已。
2 形计算
“形计算”，一个对“形学”长达50年研究所积累的、经过CAD软件系统开发和应用检验的、专门为解决几何计算不稳定问题而提出的基础理论与计算机制【4-6】，用于解决数字化模型中几何计算的稳健性问题。它基于下列认知。一切应对策略均源于几何计算不稳定的两个根本原因：几何参数的数据误差和几何关系奇异现象。主导形表示的是几何元间关系而非几何参数，形重构的难点也在于根据参与源去重构一个几何间的新关系；背后显现出的另一个问题是加强拓扑信息在模型表示中的作用，因为拓扑信息更容易表述空间概念；形是空间的，代数计算是线性的。几何代数化将对几何的图形认知转化成基于参考系的数字表述形式，缺少必要的过渡和衔接。人的空间思维优势难以发挥，对算法的掌控能力下降。几何问题几何化、降维计算都是好的思路；计算机浮点数的表示误差是客观存在的，但是，工程应用是容忍“误差”的，对“误差”的要求也是不同的，因此，根据工程类型设置零域误差可以降低误差对计算稳定性的影响。2.1 总体方案
从数字误差和几何关系两个方面剖析引起几何模型的构造缺陷和计算不稳定性的根本原因。厘清几何关系和数字误差两者引起的几何模型的构造缺陷和计算不稳定性的根本原因，制定相应的对策（表2）2.2 基础理论
下面是形计算【4-6】中的一些基本理论和策略（参考本号形计算的相关理论）。（5）构建一个基于“几何基”的稳定几何计算算法库。1）计算坐标系
基于几何的本质是某些属性具有不变性，不依赖于参考坐标系，所以建立计算坐标系，往往可化简几何的表示。例如，圆心在(xc,yc)的圆的解析式是(x-xc)2+(y-yc)2=R2，而圆心在坐标原点的圆的表示是x2+y2=R2。显然，如果求圆与直线的交点，以圆作为主元，建立以圆心作为原点的参考坐标系，求交公式会简单一些。2）引入几何数（geometric number）
协助表征几何的定义与几何间关系的表示，并辅助整个计算过程。例如，根据两向量交点的几何数可以得到处理几何奇异的方法。下面阐述如何依据“交点几何数”概念简洁、有效地去解决几何奇异问题。设两向量的交点的几何数取“入点”为“-1”，“出点”为“+1”，那么就有如下重交点与重边交点处理规则。重交点取舍规则（图7）：将重交点的几何数累加，若几何数的代数和为0，则取消形成此重点的各交点；否则，合并为一个交点，并以代数和的符号作为其几何数。重边交点的取舍规则（图8）：如果在同一向量上有连续两个交点的几何数相同，则若几何数均为+1，删除后一个交点；若几何数均为-1，删除前一个交点。两个规则都只需对交点几何数作简单运算，从理论上解决了已知几何关系的奇异问题。3）引入几何基（primary geometric basis）
作为形计算的基本单元。几何基运用公理去诱导几何推理计算，处理几何元之间的几何关系，而非用纯代数计算去解决几何问题。4）变换的几何化
基于同一几何在不同坐标系下有不同的表述，但几何是不变的，实现变换的几何化。这就可以方便构建合适的计算坐标系，也意味着可以任选投影平面，达到简化计算。5）降维计算
实现空间几何的降维，使几何的表述更简洁，几何奇异关系的处理更简单与直观，计算复杂度也常会降低。6）设置“零域”
工程应用是容忍“误差”的，对“误差”的要求也是不同的，因此，根据工程类型及应用设置不同的“零域”，特别用于解决数字误差，几何奇异的判定。3 解决计算稳定性问题
3.1 代数化方法的计算稳定性策略
设有半径为R=70的圆柱体，用30等分的多面体逼近（图9），若用通过点3、2、1三点求取该圆柱体顶平面的方程系数，这在理论上是对的。但是，如果用此平面方程系数去计算点A到该顶平面的距离，将是1.2569430E-3。若设几何误差ε=1.0E-5（这已经很精确了！），将得到点“A不在该圆柱体顶平面上”的结论，这显然是错的。原因很简单，点1、2、3三点很接近，浮点数计算的不准确被放大，造成以此3点求取的平面表示不准确。这种不稳定常需要从算法上作出调整，如果图9中用A、3、1三点求取该圆柱体顶平面的方程系数，事情会好许多。3.2 几何化方法的计算稳定性策略
几何化方法解决计算稳定性策略主要是解决几何奇异问题，从类型和层次上可以分为两个方面（表3）。
![]()
图10是解决几何奇异问题的总体框架。
![]()
图10 解决几何奇异问题的总体方案
图11给出了用几何化方法解决的“半射线交点计数判别法”包容性测试算法。![]()
注：只是用于交点计数，这两步还可以简单一些。
图11 “半射线交点计数判别法”包容性测试算法
4 结 语
剖析几何计算不稳定的根源：源于几何参数的数据误差导致的计算不稳定，以及几何关系奇异引起几何选择与几何重组的不稳定，一切应对策略均源于这两个根本原因。
现有数字化模型的计算基础主要建立在解析几何基础上，因过度依赖代数计算，难以完备表述正确的几何关系；对模型缺陷的修补则更加重了计算过程的复杂性和计算结果的难以预判性，导致造型和仿真过程常出现不可控的问题。
研究几何模型的计算稳定性的理论依据和实施方法，从基础及根源上解决数字化制造中几何计算不稳定问题，打造稳健的计算基础。由此建立数字化模型中几何计算稳健性问题的基本理论与工程解决方案。
本质上，几何参数只是数，基于数的计算属于代数一维计算；拓扑信息表示空间概念，属于几何空间思考。几何与代数是保证几何模型正确描述和正确计算的理论基础，如人的两条腿，使几何模型的构造和处理过程能顺利行进。因此，如何发挥人的空间思维能力，由人指挥两条腿走好路。
主导形表示的是几何元素之间关系而非几何参数，几何计算的难点是重构一个新的几何关系。背后显现出的是拓扑信息在模型表示中的作用，因为拓扑信息更容易表述空间概念。形的表示是空间的，代数计算是线性的。几何代数化将对几何的图形认知转化成基于参考系的数字表述形式，缺少必要的过渡和衔接。人的空间思维优势难以发挥，对算法的掌控能力下降。计算机浮点数的表示误差是客观存在的，但是，工程应用是容忍“误差”的，对“误差”的要求也是不同的，因此，根据工程类型设置零域误差可以降低误差对计算稳定性的影响。要注意发挥画法几何等经典几何在几何的表示、构造及求解中的几何化原理，发挥人的直觉优势，在人的空间思维掌控下，依据人的图形认知方式，分别发挥几何的空间概念和代数线性计算的特长，用几何的思路去寻求一个全局、直观的解决方案，分离给计算机的只是枯燥的数字与重复的代数计算。构建一套比较完整的提高几何计算稳定性的理论和实施方法。形计算基于几何问题几何化思想，引入几何数、几何基、变换几何化、降维计算、零域等一系列概念，符合自然规律，也符合人的认知体系，它的引入将能更好的表述几何的属性，使几何间的关系也更清晰，从理论上解决了几何奇异问题。形计算理论和计算机制审视了几何建模与仿真中的空间不统一问题，改变“用一维计算处理二维甚至三维问题”的研究思路。改变了现在的几何计算周旋于“形-数-数计算-数-形”不同空间的频繁转换问题，克服了实体空间与表示空间不统一、思维空间与计算空间不统一等矛盾，提高了几何计算的稳定性，提升了计算效率。参考文献
【1】 Christoph M. Hoffmann，The
Problem of Accuracy and Robustness in Geometric Computation，Purdue
University，Purdue e-Pubs，Department of Computer Science Technical
Reports Department of Computer Science，1988
【2】Christer Ericson. Triangle-triangle tests, plus the
art of benchmarking [EB/OL]. (2007-09-12)[2024-03-16] http://realtimecollisiondetection. net/blog/?p=29
【3】何援军，计算机图形学[M]，北京：机械工业出版社，2006年1月第1版第1次
【4】何援军，几何计算及其理论研究[J]，上海交通大学学报，2010,44(3):513-517.
【5】何援军，几何计算[M]，北京：高等教育出版社, 2013,3.
【6】何援军. 一种基于几何的形计算机制[J]. 图学学报, 2015, 36(3): 1-10.
![]()
