几何算法——10.欧拉操作

1 欧拉操作

欧拉操作，是由 B.G. Baumgart 于1972年提出，目的是提供有效、正确地建立三维物体复杂的边界数据结构的方法（保证有效性、保证通用性）。

1.1 欧拉操作的设计思想

（1） 提供少数几个公用的边界数据结构生成操作，使得三维物体复杂的边界数据结构可通过这些公用操作逐步构造完成。
（2） 基于欧拉公式保证使用公用数据结构生成操作所生成的边界数据结构具有拓扑有效性。

欧拉公式： v(点数)－e(边数) + f(面数) ＝ 2（s(分离体数) – h（通孔数））+ r(内环数)

以一个立方体为例：

有8个顶点，12条边，6个面，只有1个体，0个通孔，0个内环。

再以一个带孔的立方体为例：

有16个顶点，24条边，6个面，只有1个体，1个通孔，2个内环。也满足欧拉公式。

对于圆环，可以看作是这个带洞立方体的拓扑同胚，也满足欧拉公式：
如果将绿色当作一条真实的边：2 - 4 + 2 = 2（1 - 1） + 0。
如果绿色不当作真实的边：1 - 2 + 1 = 2 （1 - 1） + 0。

对于圆柱体，也满足欧拉公式（4 - 6 + 4 = 2 *（1 - 0） + 0）。

1.2 欧拉操作的选取

原则：取具有明显几何意义的基：造点、造边、造环、造面、造体

本文中使用的名称的关键字如下:

For instance, the name “mev” translates as “Make Edge, vertex”.

C.Braid 所取了一组基：
mvfs，mev，mef，kemr，kfmrh

1.3 几个典型的欧拉操作

对于拓扑的操作分为三大类，若干小类。
三大类是：Skeletal Primitives，Local Manipulations和Global Manipulations。
Skeletal Primitives是指构造一个skeletal plane model，它是从无到有构造更复杂模型的基础，对应拓扑操作就是MVFS。
局部拓扑操作又分为若干小类：在skeletal plane model的基础上，其他的各种不改变亏格的模型都可以在此基础上，通过Local Manipulations生成出来。
全局拓扑操作：由于skeletal plane model是一个亏格为0的模型（如下图9.2，类似立方体，亏格为0，没有洞）。想构造亏格大于0的模型（如下图9.3），如甜甜圈（亏格为1的模型），或者多个甜甜圈粘合在一起的（亏格大于1的模型），就需要Global Manipulations。

1.3.1 Skeletal Primitives

MVFS
功能：定义一个体、一个面(含一个外环)、一个点。
其对应的反操作为：KVFS，功能与MVFS刚好相反。

1.3.2 Local Manipulations

1.3.2.1 MEV

MEV
功能：定义一个新点，同时定义一条连接新点与另一给定点的边。
其对应的反操作为：KEV

1.3.2.2 MEF

MEF
功能：以两给定点为端点定义一条新的边，同时定义一个新的面(含一个新的环)。
其对应的反操作为：KEF

1.3.2.3 KEMR

KEMR
功能：消去环中的一条边，定义一个内环。
其对应的反操作为：MEKR

1.3.3 Global Manipulations

KEMRH
功能：删除一个面，并将其定义为另一个面的内环，进而在体中生成一个通孔或将两物体合并成一个物体。
其对应的反操作为：MFKRH

1.4 一个欧拉操作的实例

用欧拉操作构造右侧物体（长方体内带方形通孔）

1.5 欧拉操作的三点结论

Mantyla从理论上得到了以下结果：
（1） 所有流形体的边界表示都可由欧拉操作构造出来；
（2） 由欧拉操作构造出的边界表示在拓扑结构上一定是有效的;
（3） 将这种表示正确地嵌入欧几里德空间结果一定是流形体。

2. 非流形体

2.1 非流形模型（non-manifold model）

非流形体引起集合运算算法上的困难，因此传统的实体造型系统都限定处理正常的情况，即要求形体是正规集，它的边界必须拓扑等价于流形。

实体造型技术从流形转向非流形，一方面有理论研究上的意义，但更重要的是出于工程应用上的实际需要。

2.2 扩展的欧拉公式

V – E + F = 2(S - H) + R

(V - Vr) – (E – Er) + (F - Fr) – I = 2(S - H)

Vr: 与迷向点相连的伞数－1
Fr：内环数
Er: 与迷向边相连的楔数－1
I: 孤立的几何元素的数目