gluTess函数背后的算法是什么？

Question

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

我已经研究过常见的算法(Delaunay,经常会提到Ear Clipping),但我似乎无法理解GLU如何一直这么做.

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

Answer 1

来源旁边有一些注意事项:

这只是一个非常简短的概述.源代码本身还有很多其他文档.

坚固的细分目标

细分算法基本上是2D算法.我们最初将所有数据投影到一个平面上; 我们的目标是稳健地计算预测数据.然后将相同的拓扑结构应用于输入数据.

在拓扑上,输出应始终是一个细分.如果输入甚至略微是非平面的,那么当从某些角度观察时,一些三角形必然是背面的,但目标是使这种效果最小化.

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

算法的阶段

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

找到法向量

查找多边形法线的常用方法是在沿三个坐标轴投影多边形时计算有符号区域.我们不能这样做,因为轮廓可以具有零区域而不会退化(例如,领结).

我们将平面拟合到顶点数据,忽略它们如何连接到轮廓.理想情况下,这将是最小二乘拟合; 然而,就我们的目的而言,正常的准确性并不重要.相反,我们找到三个被广泛分离的顶点,并计算它们形成的三角形的法线.选择顶点使得三角形的面积至少是使用输入顶点形成的任何三角形的最大面积的1/sqrt(3)倍.

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

投影顶点

我们将顶点投影到垂直于三个坐标轴之一的平面上.这通过去除原始输入数据和算法处理的数据之间的转换步骤来帮助数字精确度.投影还压缩输入数据; 投影后顶点之间的2D距离可以小于原始2D距离.但是,通过选择具有法线的点积最大的坐标轴,压缩因子最多为1/sqrt(3).

即使法线的精度不那么重要(因为我们无论如何垂直于坐标轴投影),计算的 鲁棒性也很重要.例如,如果有许多顶点几乎沿着一条线放置,并且一个顶点V与该线完全分离,那么我们的正常计算应该涉及V,否则结果将是垃圾.

垂直于多边形法线投影的优点是计算的交叉点将尽可能接近其理想位置.要获得此行为,请定义TRUE_PROJECT.

线清扫

有三种数据结构:网格,事件队列和边缘字典.

网格是一个"四边"数据结构,记录当前分解的拓扑; 有关详细信息,请参阅包含文件"mesh.h".

事件队列简单地保存所有顶点(包括原始顶点和计算顶点),组织起来以便我们可以快速提取具有最小x-coord的顶点(其中,具有最小y-coord的顶点).

边缘字典描述扫描线与多边形区域的当前交叉点.这只是与扫描线相交的边的排序,按其当前交叉顺序排序.对于每对边缘,我们存储关于它们之间的单调区域的一些信息 - 这些是称为"活动区域"(因为它们被当前扫描线交叉).

基本算法是从左向右扫描,处理每个顶点.网格的处理部分(扫描线的左侧)是平面分解.当我们穿过每个顶点时,我们更新网格和边缘字典,然后我们检查任何新邻近的边对,看它们是否相交.

顶点可以有任意数量的边.当合并顶点并计算交叉点时,可以创建具有许多边的顶点.对于未处理的顶点(扫描线的右侧),这些边缘在顶点周围没有特定的顺序; 对于已处理的顶点,拓扑排序应与几何排序匹配.

顶点处理分两个阶段进行:首先我们处理的是左边缘(所有这些边缘当前都在边缘字典中).这包括:

• 从字典中删除左边缘;
• 必要时重新链接网格,以便事件顶点周围的这些边的顺序与字典中的顺序匹配;
• 根据它们的绕组号将任何终止区域(位于两个左边缘之间的区域)标记为"内部"或"外部".

当没有左边缘,并且事件顶点位于"内部"区域时,我们需要添加边缘(将区域分割成单调的片段).为此,我们只需将事件顶点连接到包含区域的上边缘或下边缘的最右端点.

然后我们处理正确的边缘.这包括:

• 在边缘字典中插入边缘;
• 计算任何新创建的活动区域的匝数.
  当我们浏览字典时,我们可以使用我们交叉的每条边的缠绕来递增地计算它.
• 必要时重新链接网格,以便事件顶点周围的这些边的顺序与字典中的顺序匹配;
• 检查任何新的相邻边缘以进行交叉和/或合并.

如果没有右边缘,我们还需要添加一个将包含区域分割成单调的块.在我们的例子中,最方便的是将边添加到任一包含边的最左端点; 但是我们可能需要稍后更改它(有关详细信息,请参阅代码).

不变

这些是扫描期间保持的最重要的不变量.我们定义了一个函数VertLeq(v1,v2),它定义了顶点穿过扫描线的顺序,以及一个函数EdgeLeq(e1,e2; loc),它表示在扫描事件位置"loc"处e1是否低于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)分成两个单调增加顶点的链
  • 非不变量:由于数值误差,这些链可能会(稍微)交叉,但这不会影响算法的操作.

扫描的不变量.

• 如果顶点具有任何左边缘,则在处理顶点时这些边缘必须位于边缘字典中.
• 如果边缘被标记为"fixUpperEdge"(它是由ConnectRightVertex引入的临时边缘),那么它是其关联顶点的唯一右边缘.(这表示只有在必要时才存在这些边缘.)

稳健性

算法鲁棒性的关键是保持上面的不变量,尤其是边缘字典的正确排序.我们实现这个目标:

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

2. 对边缘交叉计算的结果完全没有假设 - 对于充分退化的输入,计算的位置并不比随机数好多少.

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

三角测量和分组

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

在对所有单调区域进行三角测量后,我们希望将三角形分组为扇形和条形.我们使用贪婪的方法来做到这一点.三角测量本身并未进行优化以减少原语的数量; 我们只是试图对计算的三角测量进行合理的分解.