algorithm - 如何计算盒子的法线？

Question

我正在尝试创建一种算法来计算模型/网格的法线。人们一直告诉我使用两个向量之间的叉积，起初这似乎是个好主意，直​​到我发现它可能并不总是有效。例如，想象一个盒子，其正面位于原点，背面位于 Z 轴下方。这是一张图片:

对于糟糕的笔迹，我深表歉意，但这应该没有任何意义。如您所见，我将 v 和 u 交叉以获得指向正 z 轴的法线。但是，如果我使用相同的计算来计算背面的法线，那么显然法线将是指向形状内部的矢量。结果是我用不准确的法线来计算光的亮度。我希望法线始终背对模型。

我知道一定有更好的方法来计算法线，但我不知道它是什么。任何人都可以向我建议另一种算法来计算可以摆脱这个问题的法线吗？如果不是，则必须有一种方法来检查法线是否面向对象/模型内部。如果是这样，那么您能否在答案中提出建议，我会在哪里找到有关它的解释，因为我很想对这些方法的工作原理有一个直觉。

Answer 1

大多数软件包都遵循三角形索引的可配置循环排序 - 顺时针或逆时针。因此，它们导出的所有网格都具有自洽的顺序，只要您的程序使用相同的约定，您就无需担心。

---

话虽如此，我想您想知道在索引排序不一致的假设(？)情况下该怎么做。

我们可以使用的一种方法是射线相交。重要的定理是，源在网格外的光线只会与网格相交偶数次，如果在内部，则为奇数次。

为此，我们可以执行以下操作:

• 如上所述使用叉积计算“正常”(并将其归一化)=> N
• 取三角形上的任意一点(最好是中点)
• 将此点沿法线增加一些小的 epsilon 值(取决于您的浮点格式和模型的大小 - 我会说 1e-4 用于单个和1e-8 表示 double ) => P
• 将这条射线 [dir = N, src = P] 与网格中的所有 三角形相交(一个好的算法是 Möller–Trumbore )
• 如果交点数为偶数，则光线从网格外开始；这意味着法线指向网格向外(因为您从表面上的一个点增加了它的源)。 - 当然，反之亦然。

---

次要(-ish？)题外话:对上面的一个天真的方法，循环遍历网格中的所有三角形，将是 O(n) - 因此整个过程将具有二次时间复杂度。这对于约 20 个三角形的非常小网格(例如一个盒子)来说非常好，但对于任何更大的网格都不理想!

您可以使用空间分割技术来降低这个相交步骤的成本:

• K-D 树/八叉树:这些需要 O(n log n)(最佳算法，即 - 请参阅 Ingo Wald's paper)来构造，但交叉点是如果操作正确，保证为 O(log n)。总体复杂度将是 O(n log n)，这几乎是您可以获得的最好结果
• 网格:这只是将搜索空间和三角形划分为更小的框。构造是 O(n) 并且内存效率更高。交集时间仍然是 O(n)，但常数因子比原始方法小很多。