opengl - 顶点的缠绕顺序

Question

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

但是，我不太确定像 Blender 这样的 3d 建模程序如何可以采用任意一组三角形并将它们全部正确缠绕。

我尝试在谷歌上搜索答案，这是我找到的最好的答案:

http://www.gamedev.net/topic/550481-vertex-winding-order-counter-clockwise-oder-vertex---algorithm/

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

Answer 1

你理解错了。它没有

test it against intersection against every other triangle.

首先，您可以仅根据三角形表面的法向量来定向(卷起)三角形。那么只剩下两个选项了 - 全模型是好的还是翻转的 ;)

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

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

EDIT2:在一些 50k+ 的家伙将我贬低之前 - 如果模型完全混淆(所有三角形都按随机顺序排列)， 没有其他办法正确定位所有这些，而不是将它们全部与其他模型进行比较，凸模型是异常(exception)。