CGAL的三角网格曲面脊线和脐点的近似计算（需要微分几何学的知识）

????????脊线（Ridges）：在光滑曲面上，脊线是一种特殊的曲线。沿着这条曲线，曲面的一个主曲率在其曲率线上达到极值（最大或最小）。这意味着脊线是那些曲率发生突变的区域，它们在形状感知、物体识别和计算机图形学中都有重要的应用。

????????脐点（Umbilics）：脐点是光滑曲面上的一个特殊点，在该点上，曲面的两个主曲率相等。在脐点处，曲面的形状局部类似于一个球体或鞍点。脐点在曲面分析和计算机图形学中也很重要，因为它们代表了曲面形状的局部变化。

? ? ? ? 模型的山脊线，由数字米开朗基罗项目提供的模型。?

????????本章描述了用于近似由三角形网格离散化的光滑曲面的脊线和脐点的CGAL包。给定一个光滑曲面，脊是一条曲线，沿着这条曲线，其中一个主曲率沿着其曲率线具有极值。脐是一个点，两个主曲率相等。脊定义了一条奇异曲线，即一条自交曲线，脐是这条曲线上的特殊点。脊是极值曲线的曲线，因此编码了分割、配准、匹配和表面分析中使用的的重要信息。基于文章[2]的结果，我们提出了算法，以识别和提取三角网格曲面上的奇异脊曲线和脐的不同部分。与网格顶点相关的微分量被假设为这些算法的给定值；这些量可以通过点采样曲面的局部微分特性估计包来计算。

????????注意，此软件包需要第三方库Eigen进行线性代数运算。?

1、总览

????????光滑表面的脊和脐部分介绍了光滑表面上脊和脐理论的基础。

? ? ? ?近似三角形曲面网格上的脊和近似三角形曲面网络上的脐提供了从三角形网格近似（平滑曲面的）脊和脐的算法。

????????“软件设计”一节给出了软件包规范，而对软件包功能的示例调用在“示例”一节中提供。

2、光滑曲面的脊线和脐点

????????关于脊和相关主题的详细介绍，读者可以参考[3]、cgal:p-gd-01以及以下综述文章[1]。在接下来的内容中，我们只介绍基本概念，以解释我们的算法。考虑一个光滑的嵌入曲面，用k1和k2表示主曲率，k1≥k2。脐点是k1=k2的点。对于任何非脐点，相应的主曲率方向是明确的，我们将其表示为d1和d2。在局部坐标系中，我们用?,?表示由欧几里得空间诱导的内积，dk1和dk2表示主曲率的梯度。如图所示，标准椭球面的脊由以下公式定义：

????????释义非脐点被称为

????????如果极值系数b0=?dk1,d1?为零，即b0=0，则存在最大脊点。

????????如果极值系数b3=?dk2,d2?为零，则存在最小岭点，即b3=0；

????????之前对脊的特征描述涉及三阶微分性质。使用四阶微分量，如果脊点对应于k1的最大值或k2的最小值，则可以进一步将其定性为椭圆，否则为双曲线。因此，我们最终得到四种脊，即：MAX_ELLIPTIC_RIDGE、MAX_HYPERBOLIC_RIDGE、MIN_ELLIPTIC_RIDGE、MIN_HYPERBOLIC_RIDGE，如图所示。

????????同样有趣的是脊线，脊线是椭圆脊，是max(|k1|,|k2|)的最大值。脊线形成椭圆脊的子集，可以看作是表面上视觉上最突出的曲线。因此，我们提供了两种额外的脊类型MAX_CREST_RIDGE和MIN_CREST_RIDGE，如图1所示。

?

????????椭球上的脊，法线指向外部。颜色编码：MAX_ELLIPTIC_RIDGE为蓝色，MAX_HYPERBOLIC_RIDGE为绿色，MIN_ELLIPTIC_RIDGE为红色，MIN_HYPERBOLIC_RIDGE为黄色。红线也是MIN_CREST_RIDGE，这是椭球上唯一的峰脊。

????????在非脐点的曲面的任何点上，主方向d1、d2方向明确，这些（非定向）方向与法向量 n
定义两个直接正交坐标系。如果 v1 是方向 d1 的单位向量，则存在唯一的单位向量 v2，使得 (v1,v2,n) 是直接的，即与环境三维空间的规范基具有相同的方向（另一个可能的坐标系是 (?v1,?v2,n)）。在坐标系 (v1,v2,n) 中，曲面具有以下规范形式，称为蒙日形式

????????k1（resp.k2）沿着穿过原点并由x（resp.y）参数化的最大（resp.min）曲率线的泰勒展开式为：?

????????还要注意，从上述两个坐标系中的一个切换到另一个，会恢复曲面Monge形式上所有奇数系数的符号。

????????因此山脊类型的特点是：

????????b0=0时的最大山脊

????????如果b0=0，则最大_ LLITIC_RIDGE且P1＜0

????????如果b0=0，则最大_HYPERBOLIC_RIDGE且P1>0

????????最小山脊，如果b3=0

????????如果b3=0，则最小_ LLITIC_RIDGE且P2＜0

????????如果b3=0，则为MIN_HYPERBOLIC_RIDGE且P2>0

????????如果b0=0，则最大_CREST_RIDGE且P1＜0和|k1|>|k2|

????????如果b3=0，则MIN_CREST_RIDGE且P2＜0和|k2|>|k1|

????????如图所示，围绕脐线的曲率线形成的图案可以用与主方向相关的指数的概念来表征。

????????如图3所示，考虑围绕脐线的一个小回路C，以及点p∈C。从通过点p的曲率线的切向量的初始方向u开始，通过连续性沿电路传播该方向。该指数由u围绕该旋转扫过的角度定义，归一化为2π。在我们的例子中，该指数为1/2。如果主方向场的索引为 1/2，则称为 ELLIPTIC_UMBILIC，如果为 -1/2它被称为HYPERBOLIC_UMBILIC。否则，脐点被定义为NON_GENERIC_UMBILIC。

索引1/2脐或椭圆形脐。?

?椭圆和双曲脐。

3、三角形曲面网格上脊线的近似

????????我们的方法旨在将脊线报告为网格上的多边形线。它假设网格的每个顶点都有微分量（主曲率和方向以及三阶量b0、b3和可选的四阶量P1、P2）。这些微分量可以针对网格内切的平滑曲面进行计算（分析或使用近似方法），也可以在不参考底层平滑曲面的情况下对给定的网格进行估计。虽然脊线近似算法在这两种情况下都是相同的，但人们不能要求相同的证书。这种区别需要符合网格的概念。

????????光滑表面的脊是具有规定微分性质的点，从内接于该表面的网格报告它们需要对网格的几何形状进行精细的假设，以便得到经过认证的结果。

????????在本段中，我们假设提供的网格符合一系列假设，这些假设保证报告的脊的拓扑结构与光滑表面上的脊的拓扑结构相匹配。概括地说，一个兼容的网格是一个足够密集的网格，使得（i）脐点被正确隔离（ii）相互邻近的脊也被正确分离。

????????作为极值系数b0的0级集合和b3，通过行进三角形算法提取脊线。

????????由于这些极值系数的符号取决于主方向的取向，我们期望在网格的每个点顶点处给出极值和指向主方向的向量。除了在脐点附近，如果网格足够密集，则选择在边缘的两个端点处一致的主方向取向，使得两个向量之间的角度为锐角。这条规则，即锐角规则。此外，我们只寻找三角形中的脊，其中可以找到其三个顶点的取向，使得三条边通过锐角规则一致地取向。这样的三角形称为正三角形。这就是说，有两点要说明。

????????正三角形和脊线段。正三角形有0或2条边被最大（最小）脊线穿过，这相当于b0的符号变化（分别为b3）沿着相应的边缘。在后一种情况下，我们说三角形包含脊线段。提供了两种方法来计算其类型，无论是椭圆还是双曲线。首先，如果提供了四阶微分量，可以使用P1（P2) 值在?eqtaylor_along_line ( eqtaylor_along_red_line) 的方程，用于求最大（最小）脊。Pi 的值脊段Pi的平均值定义为边缘上的两个交叉点的值（而边缘上的交叉点的值是双端点处值的加权平均值）。或者，如果只有三阶微分量可用，可以使用[2]中开发的几何方法。

????????使用脊线段的概念，脊线被定义为相同类型且连接在一起的脊线段的最大连接序列。请注意，脊线的拓扑结构可以是区间或圆。

????????非规则三角形。在脐点附近，三角形不太可能是规则的，并且这种方法不能检测到脊。这就是为什么我们提出另一种方法来独立检测脐点的原因。

????????非符合性网格：对强度和锐度的脊线进行滤波???????。

????????对于处理粗网格、具有退化区域或尖锐特征的网格或带有一定量噪声的实际应用，合规假设无法满足。在这种情况下，仍然可以寻求具有估计主曲率极值的点的位置，但报告的脊线可能需要滤波。例如，如果主曲率是常数

????????这适用于平面或圆柱体的情况，则所有点都是脊点。在这种情况下，一个有吸引力的概念是尖锐脊或突出脊。由于脊线由b0和b3的零交叉见证，只要这些系数保持较小，就可以预期存在错误的检测。为了选择最突出的脊点，我们专注于沿着曲率线曲率变化迅速的点。可以观察到，在脊点处，根据方程eqtaylor_along_line，沿其曲率线的k1的二阶导数满足k′′1(0)=P1/(k1?k2)。利用这一观察结果，可以将脊线的锐度定义为沿脊线的P1/(k1?k2)的绝对值之和。由于曲率的二阶导数与长度立方倒数成正比，锐度与长度平方倒数成正比。将锐度乘以模型尺寸的平方可以得到一个阈值和一个与尺度无关的锐度过滤器。另一个滤波器与强度有关，强度是沿脊线的曲率积分。

4、三角形曲面网格上脐点的近似

????????该方法旨在将网格的某些顶点识别为脐点。它假设主曲率和方向在网格上的每个顶点都给定。

????????假设网格的每个顶点v周围都有一个补丁（拓扑圆盘）。检查顶点v是否是脐点是一个两阶段的过程，分别涉及补丁上函数k1-k2的变化，以及根据补丁边界计算的顶点的索引。更确切地说，如果满足以下两个条件，则将顶点v声明为脐点：

????????函数 k1?k2 在补丁的所有顶点中在 v 处具有最小值；

????????沿补丁边界逆时针（CCW）方向任何主方向的偏差δ具有规定的性质：

? ? ? ? δ∈]π/2,3π/2[，则该脐称为椭圆脐，

????????δ ∈ ]?3π/2,?π/2[, 则该脐点称为双曲脐点，

? ? ? ? 否则，脐带被称为非通用。

????????在顶点周围找到补丁。给定一个顶点v和一个参数t，我们的目标是定义一个围绕v的三角形集合，使得（i）这个集合在三角剖分T上定义了一个拓扑圆盘，并且（ii）它的尺寸取决于t。首先，我们收集1-环三角形。我们定义这个1-环补丁的尺寸s为从v到其最远的1-环顶点邻居的（欧几里得）距离。然后我们递归收集相邻三角形，使补丁保持为拓扑圆盘，并且这些三角形的距离小于s×t参数t是该算法的唯一参数。

????????脐带贴片与脐嵴。在一般的表面上，一般的脐被一个或三个脊穿过。对于柔顺网格，脐可以连接到位于其面片边界上的脊点。

5、软件设计

????????此包中的所有类都由参数TriangleMesh模板化，该参数定义了近似算法所操作的网格类型。

????????差分量通过属性映射在这个网格的顶点处提供，属性映射是 Boost 库中常用的概念。属性映射使用户能够在扩展的顶点内部或外部使用 std::map 结合 boost::associative_property_map 存储与顶点相关的标量和向量。

????????脊或脐的输出是通过输出迭代器提供的。

????????脊线和脐线的近似是通过两个独立的类来完成的，我们现在进一步描述。

5.1、脊线近似

????????主要类是 Ridge_approximation<TriangleMesh,VertexFTMap,VertexVectorMap>。它的构造需要网格和属性映射，定义主曲率 k1 和 k2 的微分量、三阶极值 b0 和 b3、主曲率方向 d1 和 d2，以及四阶量 P1 和 P2（如果使用多项式 P1 和 P2 将脊标记为椭圆或双曲线）.

????????三个函数（作为成员函数和全局函数提供）支持不同类型的脊线计算：

????????compute_max_ridges() (resp. compute_min_ridges()) 输出 MAX_ELLIPTIC_RIDGE 和 MAX_HYPERBOLIC_RIDGE (resp. MIN_ELLIPTIC_RIDGE 和 MIN_HYPERBOLIC_RIDGE) 类型的脊线。

????????compute_crest_ridges() 输出 MAX_CREST_RIDGE 和 MIN_CREST_RIDGE 类型的脊。

????????这些函数允许用户指定椭圆/双曲线标记是如何执行的。请注意，选择这三个函数的基本原理很简单：每个计算都需要在网格的三角形上单次通过。对于最小和最大脊，这一点应该是清楚的。对于峰，只需注意最大和最小峰不能在三角形上相交。

????????脊线存储在 Ridge_line 对象中，并通过迭代器输出。每条脊线表示为网格的半边列表，其中包含一个标量，该标量定义了交叉点相对于半边端点的重心坐标。每条脊线都有其类型 Ridge_type、强度和锐度。如果选择仅使用三阶量，则量Pi锐度将无法定义。

5.2、脐点近似

????????主类是Umbilic_approximation<TriangleMesh,VertexFTMap,VertexVectorMap>。它的构造需要网格和属性映射，定义主曲率k1和k2的微分量，以及主曲率方向d1和d2。成员函数compute()（或全局函数compute_umbilics()）有一个参数，用于定义脐点邻域的大小。

????????脐点存储在脐点对象中，它们具有自己的类型：ELLIPTIC_UMBILIC、HYPERBOLIC_UMBILIC 或 NON_ GENERIC_UMBILIC；它们关联到的网格顶点以及表示邻域轮廓的半边列表。

CGAL 5.6 - Approximation of Ridges and Umbilics on Triangulated Surface Meshes: User Manual