使用受限平行四边形的三角形细分

# 使用钳位平行四边形的三角形曲面细分 来源：https://filmicworlds.com/blog/compute-tessellation-with-clamped-parallelograms/ 我们今天所熟知的硬件曲面细分（Dx11风格）起源于2005年发布的Xbox 360。时光飞逝，对吧？这是向电影级实时渲染演进的必然一步。毕竟，曲面细分是原始皮克斯Reyes论文\[7\]的关键组成部分。 如今20多年过去了，我们对这个算法有了更多经验，而硬件曲面细分并未成为这些用例的解决方案。但Dx11风格曲面细分的核心思想仍然是好想法，值得重新审视其本身。借助后见之明，我们可以接纳这些想法，沿途做出不同的决策，看看能否找到一种算法，在满足相同约束的同时具备一些更理想的特性。 最终的算法，当我们构建完成时，将如下图所示。它允许我们在文章头图的所有模式之间无缝过渡，而不会出现跳动。 代码以JavaScript形式存储，欢迎随意使用（采用MIT许可证）。我基本上是拿现有的C++代码对Claude说：“把这个变成JavaScript查看器，祝你好运。” **Dx11曲面细分具体是如何工作的？** 三角形的每条边都有一个细分因子，粗略描述该边被分成多少段。在Dx11中，该值范围为\[1,64\]。关键设计决策是每个细分因子是一个浮点值，我们可以在任意值之间进行线性插值而不会出现可见的跳动。从这个角度来看，我们可以将曲面细分为两个子问题。 1. 给定一个细分因子，将边分割成线段。 2. 给定这些边线段，分割三角形的内部。 网上有一些概述\[3\]\[4\]\[5\]，以及Fabian Giesen对Dx11曲面细分阶段的描述\[6\]。但在本次练习中，我们将深入细节，并逐步推导。 我们应该如何对线段进行曲面细分？最显而易见的方案是使用细分，在每个2的幂处将每条边对半分割。 *注：Dx11中的细分因子范围为\[1,64\]，但为了简化公式，我将使用从0开始的范围。* 这样我们在每个2的幂处得到理想的细分级别。细分因子8和16看起来很棒，但如何处理11这样的值？我们可以一次添加一个点，而不是直接从8跳到16。从概念上讲，如果我们想要一个值，比如11，可以将最后添加的点视为一个“枢轴”。在细分因子为11时，前一个2的幂应占用8个点，新槽位中应有3个被占用，剩下5个。你可以自行推导公式（或查看代码），结果如下： 这与原始细分使用相同的点，但一次只过渡一个点，而不是在2的幂处全部引入。但我们如何修改算法才能实现无跳动的干净过渡？所有点保持不变，除了枢轴点。对于值10.3，我们向上取整为11段。前一次细分锁定了8个点，已有2个点过渡进来，最后一个点根据前一个点和目标位置进行30%的线性插值。 现在变得更有趣了，下一个问题是分布。我们想要均匀间隔的细分，但在当前迭代中，枢轴下方密度大，上方密度稀疏。Dx11通过使所有点长度相同（除了滑入的那个点）来解决这个问题。 这个变化有好有坏。好消息是我们得到了更均匀的细分。坏消息是它引入了大量移动。之前只有枢轴点在移动。但现在，所有点都在不断移动。 我们还有一个实际问题：对称性。如果两个三角形相邻，而细分以相反方向移动，就会形成裂缝。幸运的是，我们可以通过在底部镜像细分来解决这个问题。这样就得到了我们的Dx11结果。 据我所知，这就是Dx11中分数偶数细分的算法。我们已经解决了第一个问题（给定三个细分因子，分割边）。现在我们需要找到一种算法，根据这些细分因子在三角形内部进行分割，而不会引起跳动。 作为第一步，我们从原始三角形开始，将其分割成6个较小的三角形。 使用内部细分因子，我们可以使用常规的“三角力量”细分创建一个细分三角形。这样我们得到6个细分三角形区域。 明显的问题是，现在所有3条边的细分因子完全相同。我们可以通过简单地丢弃最外层的三角形环来解决这个问题。 现在我们要做的就是将内部细分连接到边缘细分，同时不引起跳动。诀窍是，我们应该以原始的2的幂为单位来思考。让我们在中间画一条线，它是大于或等于两个细分因子的最小2的幂。然后将左右两侧与中间匹配。左侧的细分因子是内部细分，右侧的细分因子是间隙另一侧的边缘细分。 然后我们可以从左到右进行匹配，注意左侧的多个点可能指向右侧的同一个点。对于右侧的每个点，我们可以通过回溯并连接到左侧的点来找到其反向匹配。 为了用三角形填充间隙，对于左侧的每个点，我们可以找到当前和下一个右侧匹配点。然后添加一个三角形扇形连接到右侧，再添加一个额外的反向三角形来填充。但注意我们要跳过最后一个三角形。蓝色三角形显示从当前右侧匹配点到下一个右侧匹配点的三角形扇形。然后红色三角形闭合条带。 最后，我们可以使用这个匹配算法为所有6个三角形填充间隙。 **好的与坏的** 这个算法有几个非常有趣的特性。这种方法的主要优势是灵活性。我们可以选择任意函数来计算边的细分因子，然后细分就能正常工作。由于过渡是连续的，我们永远不需要跳动。 另一方面，这种灵活性导致了不太理想的模式。所以我们将逐一介绍它们，以及如何通过钳位平行四边形方法来改进。 **不同的细分因子：** 假设我们有两条边具有高细分因子，一条边具有低细分因子。这在薄三角形中很常见。理想情况下，我们希望得到一个能直接连接左右两侧的细分模式。但由于我们只有一个内部细分因子，它要么细分不足，要么细分过度。 相反，我们可以通过创建一种允许直接连接两条高细分因子边的细分模式来解决这个问题。 **低效的模式：** 通过将三角形分割成6个相似的三角形区域，我们使用了比实际需要更多的三角形。 相比之下，使用钳位平行四边形方法，只要所有三个细分因子相同，它在拓扑上就等价于三角力量细分。尽管间距可能不均匀，但这是允许在细分因子之间进行线性插值而不发生跳动所必需的。 **弯曲：** 如果我们将曲面细分用于变形（这是曲面细分最引人注目的用途之一），我们通常希望保持直的边缘循环，以避免在生成的细分网格中出现尖锐弯曲。如果原始网格是四边形，我们希望从左到右有清晰的边缘循环。注意，理论上我们可以使用Dx11四边形图元细分，但这会带来一系列与混合三角形/四边形网格（非常常见，例如Blender的Suzanne）相关的新问题。 相反，钳位平行四边形模式生成具有清晰边缘循环的规则四边形，并且当细分因子彼此偏离时能优雅地降级。 **最小三角形数：** 分数偶数模式的最小细分是6个三角形，仅仅“打开”它就会导致计算成本的突然跳跃。 另一方面，钳位平行四边形细分可以从单个三角形一直过渡。 **移动：** Dx11模式非常“有弹性”。当用于实际的位移贴图时，尖锐的边缘会导致随着细分因子的移动而出现明显的前后摇摆。新函数显著更稳定，代价是分布更不均匀。 为简单起见，我专注于分数偶数模式。我们可以通过使用分数奇数模式来避免最小三角形数问题，但这会大大增加移动量，同时弯曲和低效模式保持不变。虽然我没有实现分数奇数细分，但该算法本质上移除了每条边的中点，任何原本会从中点“滑出”的点现在从外部“滑入”。 **对一条线进行曲面细分** 但在我们尝试改进实际模式之前，让我们重新审视对一条线进行曲面细分的问题。Dx11中的算法使间距均匀，除了滑入的那个点外。理论上听起来不错，但移动带来了实际问题。 我们首先要做的是实际上退一步。我们将恢复到之前的细分算法，即一次添加一个点并对新点进行线性插值。以下是两者的比较。你真的能感觉到“有弹性”的移动程度。 一个有趣的注记：Dx11曲面细分不会收敛。特别是，观察中点的路径。在细分值为4时，中点是0.5。但随着我们细分，接下来的两个点从下方滑入，将中点推至0.6667。然后接下来的两个点从该点上方滑入，到我们有8个点时又将其推回0.5。在从每个2的幂到下一个的过渡期间，这个中点从0.5到0.667再回到0.5，从未收敛。下面的图表显示了细分模式在范围内线性插值时的变化。 这是恢复后的版本。尽管点分布较差，但稳定性是值得的。这是我们新的起点。 让我们采取不同的方法。不是一次添加一个点，而是先插入所有奇数点，再添加任何偶数点。边缘大小的分布相同，但大边和小边更平衡。 为了进一步改进，我们可以将更高的细分级别分成块。当我们从例如64过渡到128时，新点添加得非常快，即使从技术上是连续的，它们看起来也像跳动。解决方案是将我们的区域分成块，这样每个2的幂有4个不同拓扑的区域。我们有多个点同时滑动，但运动更慢，不太可能出现突然的移动而“感觉”像跳动。 作为最后的调整，我们希望对一条普通线段的细分因子到初始细分因子有一个干净的过渡。当从细分因子1过渡到2时，分数偶数模式简单地将你钳位到最小细分因子2。相反，我们可以从两个端点滑入，在中点相遇。你可以通过拖动下面的滑块在1.0和2.0之间看到。 这就是最终的线段细分算法。接下来，我们将专注于内部三角形细分模式。 **间隙与钳位平行四边形** 我们应该如何实际细分三角形？我在这问题上花了很多时间，最终找到的解决方案是钳位平行四边形。让我们从使用底边和左边细分因子的普通平行四边形开始。对于平行四边形中的每个点，重心坐标为： `` float u = EdgeT(i, n0); float v = EdgeT(j, n2); `` 它看起来相当不错。分布是直的。没有什么比平行四边形更直的了！但平行四边形不是三角形。幸运的是，有一个简单的方法可以将这个平行四边形变成三角形：钳位。 `` float u = EdgeT(i, n0); float v = EdgeT(j, n2); u = min(u, 1 - v); `` 现在我们得到了一个非常直的模式，而且它是一个三角形（进步！），但左右两侧被约束为相同。我们需要修改这个算法，以允许左右边缘具有不同的细分因子。 幸运的是，我们可以使用与Dx11相同的技巧：跳过间隙并单独匹配。我们可以将间隙确定为左边和底边间隙的最大值，并调整钳位线。 `` float u = EdgeT(i, n0); float v = EdgeT(j, n2); u = min(u, 1 - (gap + v)); `` 我们应该如何匹配间隙？实际上相当简单。我们可以从左到右匹配，使用大致与之前相同的算法。只不过，不是镜像顶部和底部，我们需要略有不同的版本。关键洞察是，随着细分因子的增加，新点从中部滑出。对于下半部分，这意味着新点来自上方，对于上半部分，新点来自下方。注意，当从左到右匹配时，我们总是希望第一个三角形沿着右侧向上，这样我们就可以创建三角力量细分。 最后，这里是转换为三角形的相同匹配模式。 一个最后的细节：我们需要处理普通三角形和这个新模式之间的过渡。我发现最简单的方法是从v2开始有一个内部点。然后随着细分因子增加，这个点向v0/v1的中点滑动。在这个过渡期间，模式本质上是一个三角形扇形，除了v2处的一个三角形。v2处的三角形不得接触质心点，以便它可以无缝过渡到三角力量细分。 因此我们有三种“类型”的三角形。类型0只是一个三角形。类型1是三角形扇形，类型2是完整的细分算法。 作为附注，我们应该提一下索引的顺序。由于此算法面向WebGPU，SV\_PrimitiveID支持不保证，且Mesh着色器不可行，因此我们需要一个一致的激发顶点。这意味着我们必须加倍内部点，但间隙两侧的顶点仅使用一次。在图中，较暗的边是激发顶点。 这样就得到了最终算法： **四边形和边缘循环** 我们还可以为四边形做一个特例。当源图元是四边形时，我们需要将其分割成两个三角形。然后我们可以选择每个三角形三条边的细分因子，并按我们想要的方式进行细分。然而，如果我们知道源是四边形，我们可以作弊，使对角线使用两条边之一的细分因子。在这种情况下，对角线的细分因子被强制为左边的边。 由于对角线左边具有相同的细分因子，水平边缘循环保持笔直。大多数水平线通过对角线保持笔直，而垂直线也大多是直的。 **旋转对称性** 我们实际上失去的Dx11曲面细分的一个属性是旋转对称性。使用Dx11，你可以将三角形从v0/v1/v2切换到v1/v2/v0，模式看起来相同。然而，我们失去了这个属性，因为钳位平行四边形始终沿着v0/v1和v0/v2边，间隙始终沿着v1/v2边。最简单的方法是始终确保最小的边是v0/v2。 **实现** 本文中使用的两个交互式查看器是自包含的HTML页面。你可以直接打开它们，查看，修改，做你想做的事。代码采用宽松的MIT许可证。 tess\_visualizer\.html (https://filmicworlds.com/downloads/2026-05-02-compute-tessella