11

我出于好奇而问这个问题，出于性能原因，在使用 GLU 之前首先尝试实现这样的算法。

我研究了常见的算法（经常提到 Delaunay、Ear Clipping），但我似乎无法理解 GLU 是如何一直如此出色地完成工作的。

你们有没有关于这些主题的有趣论文或文章？

4

1 回答 1

18

源代码旁边有一些注释：

这只是一个非常简短的概述。源代码本身有相当多的附加文档。

稳健的细分目标

镶嵌算法本质上是一种二维算法。我们最初将所有数据投影到一个平面中；我们的目标是对预测数据进行稳健的细分。然后将相同的拓扑细分应用于输入数据。

从拓扑上讲，输出应该始终是曲面细分。如果输入甚至稍微不平面，那么从某些角度看时，一些三角形必然是背面的，但目标是尽量减少这种影响。

该算法需要一些清理输入数据以及其自身计算中的数值误差的能力。一种方法是指定上面定义的容差，并在行扫描过程中清理输入和输出。至少，该算法必须处理重合顶点、入射到边的顶点和重合边。

算法的阶段

  1. 求多边形法线 N。
  2. 将顶点数据投影到平面上。它不需要垂直于法线，例如。我们可以投影到
    垂直于坐标轴的平面上，该平面与 N 的点积最大。
  3. 使用线扫描算法，将平面划分为 x 单调区域。任何垂直线最多与一个 x 单调区域相交。
  4. 对 x 单调区域进行三角测量。
  5. 将三角形分组为条形和扇形。

寻找法线向量

找到多边形法线的常用方法是计算多边形沿三个坐标轴投影时的带符号面积。我们不能这样做，因为轮廓可以具有零面积而不会退化（例如领结）。

我们将平面拟合到顶点数据，忽略它们如何连接到轮廓中。理想情况下，这将是最小二乘拟合；然而，就我们的目的而言，法线的准确性并不重要。相反，我们找到三个相距很远的顶点，并计算它们形成的三角形的法线。选择顶点以使三角形的面积至少是使用输入顶点形成的任何三角形的最大面积的 1/sqrt(3) 倍。

轮廓确实会影响法线的方向。在计算法线后，我们检查有符号轮廓区域的总和是否为非负数，并在必要时反转法线。

投影顶点

我们将顶点投影到垂直于三个坐标轴之一的平面上。通过消除原始输入数据和算法处理的数据之间的转换步骤，这有助于提高数值准确性。投影还压缩了输入数据；投影后顶点之间的二维距离可能小于原始二维距离。但是，通过选择与法线的点积最大的坐标轴，压缩因子最多为 1/sqrt(3)。

尽管法线的准确性并不那么重要（因为无论如何我们都是垂直于坐标轴投影），但计算的 鲁棒性很重要。例如，如果有许多顶点几乎沿着一条直线，并且有一个顶点 V 与直线很好地分开，那么我们的正常计算应该涉及 V，否则结果将是垃圾。

垂直于多边形法线投影的优点是计算出的交点将尽可能靠近它们的理想位置。要获得此行为，请定义 TRUE_PROJECT。

线扫

共有三种数据结构：网格、事件队列和边缘字典。

网格是一种“四边形”数据结构，记录了当前分解的拓扑结构；有关详细信息，请参阅包含文件“mesh.h”。

事件队列简单地保存所有顶点（原始的和计算的），组织起来以便我们可以快速提取具有最小 x 坐标的顶点（其中包括具有最小 y 坐标的那个）。

边缘字典描述了扫描线与多边形区域的当前交点。这只是与扫描线相交的边缘的排序，按它们当前的相交顺序排序。对于每一对边，我们存储一些关于它们之间单调区域的信息——这些被称为“活动区域”（因为它们被当前扫描线穿过）。

基本算法是从左到右扫描，处理每个顶点。网格的处理部分（扫描线左侧）是平面分解。当我们穿过每个顶点时，我们更新网格和边字典，然后我们检查任何新相邻的边对以查看它们是否相交。

一个顶点可以有任意数量的边。随着顶点的合并和交叉点的计算，可以创建具有许多边的顶点。对于未处理的顶点（扫描线的右侧），这些边在顶点周围没有特定的顺序；对于已处理的顶点，拓扑排序应与几何排序匹配。

顶点处理分两个阶段进行：首先我们处理的是向左的边（所有这些边当前都在边字典中）。这涉及：

  • 从字典中删除左行边；
  • 如有必要，重新链接网格，以便事件顶点周围的这些边的顺序与字典中的顺序相匹配；
  • 根据绕组数将任何终止区域（位于两个左向边缘之间的区域）标记为“内部”或“外部”。

当没有左行边，并且事件顶点在“内部”区域中时，我们需要添加一条边（将区域分割成单调块）。为此，我们只需将事件顶点连接到包含区域的上边缘或下边缘的最右端点。

然后我们处理向右的边缘。这涉及：

  • 在边缘字典中插入边缘；
  • 计算任何新创建的活动区域的缠绕数。
    我们可以在遍历字典时使用我们穿过的每条边的缠绕来增量计算。
  • 如有必要，重新链接网格，以便事件顶点周围的这些边的顺序与字典中的顺序相匹配；
  • 检查任何新相邻的边缘是否相交和/或合并。

如果没有右向边缘，我们需要再次添加一个以将包含区域分成单调块。在我们的例子中，将一条边添加到任一包含边的最左端点是最方便的；但是我们可能需要稍后更改它（有关详细信息，请参阅代码）。

不变量

这些是在扫描期间保持的最重要的不变量。我们定义了一个函数 VertLeq(v1,v2)，它定义了顶点穿过扫描线的顺序，以及一个函数 EdgeLeq(e1,e2; loc)，它表示 e1 在扫描事件位置“loc”处是否低于 e2。此函数仅在位于 {e1,e2} 的最右端点和 {e1,e2} 的最左端点之间的扫描事件位置定义。

边缘词典的不变量。

  • 每对相邻边 e2=Succ(e1) 在扫描事件的任何有效位置都满足 EdgeLeq(e1,e2)。
  • 如果 EdgeLeq(e2,e1) 也是如此（在任何有效的扫描事件中），则 e1 和 e2 共享一个公共端点。
  • 对于字典中的每个 e，e->Dst 已被处理，但 e->Org 未处理。
  • 每个边 e 满足 VertLeq(e->Dst,event) && VertLeq(event,e->Org) 其中“event”是当前扫描线事件。
  • 没有边 e 的长度为零。

  • 没有两条边具有相同的左右端点。网格（已处理部分）的不变量。

  • 扫描线左侧的网格部分是平面图，即。有一些方法可以将其嵌入平面中。

  • 没有处理过的边的长度为零。
  • 没有两个处理过的顶点具有相同的坐标。
  • 每个“内部”区域都是单调的，即。根据 VertLeq(v1,v2) 可以分成两条单调递增的顶点链
    • a non-invariant：由于数值错误，这些链可能（略微）相交，但这不会影响算法的操作。

扫描的不变量。

  • 如果顶点有任何向左的边，那么在处理顶点时这些边必须在边字典中。
  • 如果一条边被标记为“fixUpperEdge”（它是由 ConnectRightVertex 引入的临时边），那么它是从其关联顶点开始的唯一右向边。（这表示这些边仅在必要时才存在。）

鲁棒性

算法鲁棒性的关键是保持上述不变量，尤其是边缘字典的正确排序。我们通过以下方式实现这一目标：

  1. 编写数值计算以获得最大精度而不是最大速度。

  2. 对边缘交点计算的结果完全不做任何假设——对于足够退化的输入，计算的位置并不比随机数好多少。

  3. 当数值错误违反不变量时，通过在必要时进行拓扑更改（即重新链接网格结构）来恢复它们。

三角测量和分组

我们在进行任何三角测量之前完成线扫描。这是因为即使在单调区域完成之后，由于进一步的顶点合并，它的顶点数据也可能会发生进一步的变化。

在对所有单调区域进行三角剖分后，我们要将三角形分组为扇形和条形。我们使用贪婪的方法来做到这一点。三角测量本身并未优化以减少基元的数量；我们只是尝试对计算的三角剖分进行合理的分解。

于 2012-10-12T04:58:44.377 回答