名词概念¶
Predicates谓词
在计算几何中，Predicates 表示一类判断函数，用于判断几何基元（primitive, 即点、线、面等）之间的拓扑关系和几何状态。这些函数通常返回布尔值或有限的离散值，为几何算法提供可靠的几何判断基础。
典型例子：
- 方向判断：三个点的相对方向（顺时针/逆时针/共线）
- 包含性判断：点是否在多边形内部
- 相交判断：线段是否相交
- 相对位置判断：点在直线的哪一侧
BSP subdivision
BSP指Binary Space Partitioning
四边形化方法
基本CDT(Constrained Delaunay tetrahedrization)方法能够生成四边形化，但不鲁棒，需要通过加入一定的Steiner Points来保证生成。
tetgen方法可以在得到四边形化的同时，让这些Steiner Points尽可能的少。
tetwild方法通过混合坐标表示首次将thingi10k数据集的所有数据都进行了四边形化。它在计算相交的时候使用精确数，在其他时候使用浮点数。后续有一个快速的版本，但这个版本不能保证一定成功。这两个版本可以得到一个与输入接近的网格，用户可以设置一个ε误差让结果在这个误差以内。
Exact arithmetic精确算术
精确算术用于处理浮点数精度的问题。CGAL中定义了NEF polyhedra，将一组多边形所包裹的空间表示为显式的体积。
网格修复
网格修复分为全局的方法和局部的方法。前者基于输入进行完全的重建，鲁棒，但不够精确。后者是精确的，但在顶点坐标舍入到浮点数的时候，可能会无效。
环绕数
环绕数的主要功能是判断"element"的内外。点\(\mathbf{p}\)处关于封闭Lipschitz曲线\(\mathcal{C}\)的环绕数是一个有符号的整数值： $$ w(\mathbf{p}) = \frac{1}{2\pi} \oint_C d\theta = \frac{1}{2\pi} \oint_C \frac{(x - p_x)dy - (y - p_y)dx}{(x - p_x)^2 + (y - p_y)^2} $$ 直观上来看，一个观察者站在\(\mathbf{p}\)处注视着\(\mathcal{C}\)上的一个点绕一圈的时候，其转动的圈数。
也可以解释为，\(\mathcal{C}\)上的点投影到以\(\mathbf{p}\)为中心的单位圆后，得到的有向长度。
如果\(\mathbf{p}=0\)，表示\(\mathbf{p}\)在\(\mathcal{C}\)外部；如果\(\mathbf{p}=1\)则在内部。
如果\(\mathbf{p}\)位于\(\mathcal{C}\)的边界上，此处环绕数无定义。
通过solid angle，可以将环绕数的概念推广到3d空间。三维空间的环绕数为solid angle的值除以\(4\pi\)
立体角 solid angle
\(\mathbf{p}\)关于一个Lipschitz表面\(\mathcal{S}\)的立体角\(\Omega\)定义为 $$ \Omega(p) = \oint_S \frac{\mathbf{r} \cdot \mathbf{n}}{r^3} dS $$
其中：
- \(\mathbf{r}\) 是从点\(\mathbf{p}\)到曲面\(\mathcal{S}\)上某点的向量
- \(r = \|\mathbf{r}\|\) 是向量的模长
- \(\mathbf{n}\) 是曲面\(\mathcal{S}\)在该点处的单位法向量
- \(dS\) 是曲面上的面积微元
立体角表示点\(\mathbf{p}\)"看到"曲面\(\mathcal{S}\)所张的角度大小，单位是球面度（steradian）。
Nef Polyhedra
调和函数
调和函数（Harmonic Function）是满足拉普拉斯方程的函数。在二维平面中，函数\(u(x,y)\)是调和的当且仅当： $$ \nabla^2 u = \frac{\partial^2 u}{\partial x^2} + \frac{\partial^2 u}{\partial y^2} = 0 $$
性质：
- 线性性：调和函数的和仍是调和函数
- 平均值性质：在任意圆上的平均值等于圆心处的函数值
- 极值原理：在区域内不能有局部极大值或极小值
为什么调和函数的和是调和的？ 由于拉普拉斯算子\(\nabla^2\)是线性算子： $$ \nabla^2(u + v) = \nabla^2 u + \nabla^2 v $$ 如果\(u\)和\(v\)都是调和函数（即\(\nabla^2 u = 0\)且\(\nabla^2 v = 0\)），那么： $$ \nabla^2(u + v) = 0 + 0 = 0 $$ 所以\(u + v\)也是调和函数。
snap rounding
Snap Rounding是用于几何关系计算的一种舍入方法，核心目标是保证舍入的时候，几何拓扑关系不变。但这个算法的时间复杂度很高，以至于实用性有限。