4

我了解缠绕顺序是什么，以及它如何用于背面剔除。

但是，我不确定像 Blender 这样的 3D 建模程序如何能够获取任意一组三角形并将它们全部正确缠绕。

我试着用谷歌搜索答案，这是我发现的最好的：

http://www.gamedev.net/topic/550481-vertex-winding-order-逆时针-oder-vertex---算法/

基本上，对于每个三角形，您可以找到它的中心（准确地说是质心），然后从该三角形计算出一个法线向量，从而为您提供一条射线。你取这条射线并测试它与其他所有三角形的交点。如果它是偶数，那么你的绕组是正确的，如果它是一个奇数，你的绕组是不正确的（我想这取决于你如何准确地生成法线向量，但你以某种方式使用奇数/偶数策略）。无论如何，这意味着整个过程通常是 O(n^2)。如果您有 1000 个三角形，那么对于每个三角形，您必须针对 999 个其他三角形的交集来测试它。是否有一种不太明显的方法来正确缠绕顶点，更有效？

4

1 回答 1

4

你确实理解错了。它没有

test it against intersection against every other triangle.

首先，您可以仅根据三角形表面的法线向量来定向（缠绕）三角形。那么就只剩下两个选项了——整个模型要么好要么被翻转；）

所以你真的只需要检查一个三角形，然后根据最后一次检查的结果结束其余的检查，这基本上给你 O(n)。

编辑：哦，我想我知道这种方法什么时候会失败。我只记得例如 Google Sketchup 做的不是很好，有时你需要自己定位面孔。但是，如果您增加随机光线的数量（对于随机三角形），您确实会增加正确标记所有内容的机会。

EDIT2：在一些 50k+ 的人投票反对我之前 - 如果模型完全混淆（所有三角形都是随机顺序），没有其他方法可以正确定位它们，而不是检查它们与另一个凸面模型是例外。

于 2012-05-21T08:52:05.543 回答