頂點的繞線順序

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. 

首先，你可以定位（卷取）僅在三角面的法向量根據您的三角形。那麼只有兩個選擇離開 - 整個模型是好是翻轉;）

所以，你真的要只檢查ONE三角形，然後拉閘休息基礎上的結果最後的檢查，這基本上給你O（n）。

編輯：哦，我想我知道這種方法可能會失敗。我只記得例如Google Sketchup做得不好，有時你需要自己定位面部。但是，如果增加隨機光線的數量（對於隨機三角形），那麼確實會增加正確標記所有內容的機會。

EDIT2：和之前的一些50K +傢伙downvotes我在地上 - 如果模型完全混了（所有的三角形是隨機順序），沒有其他辦法正確定向所有的人，不是檢查他們所有這些都是相反的，凸模型是例外。