stl模型如何效率的檢測overlap面片？

stl模型中存在一些常見錯誤，如： 孔洞，反向法矢，縫隙，重合面片等。

重合面片是由於三角形的頂點在3D空間中是以浮點數表示的，而不是整數。如果圓整誤差範圍較大，就會導致面片的重疊。

而對於重合面片，如何效率的檢測到這些overlap面片呢？

目前的思路是通過計算面的法線，對stl的面片重新分組，將法線一致或相反的面片集中。然後基於法線的方向和頂點，建立平面群。之後一一比較各個三角面片和每個平面的關係，最後再對處於同一平面的三角面做重合判斷。

但是覺得這種方法過於複雜，且重複遍歷很多次，效率很低。有更效率的方法嗎？

處理stl模型採用的不是半邊結構的數據格式，但是已經建立好了點、邊、面的拓撲鄰接關係。

ps. 最近又把這個問題總結了一下，處理overlapping triangle meshes分為兩步：

1. 分層處理數據，常規理解，重疊面之間不具有拓撲連接形，所以每個三角面都要與其他面片做比較，討論是否重疊。也就是每個面片所要比較的樣本面，數據很大。所以第一步為縮小比較樣本。

2. 判斷重疊的演算法，通過三角形邊與另一三角面求交可以判斷，演算法可以有優化。

之前提該問題，沒有指出來主要的問題癥結在哪，我的問題是在第一步，如何通過一些分層方法來縮小每個面的比較樣本？

後面用了ANN查找最近鄰的方法，這種方法對重疊跨度比較多的三角形檢測可能會有遺漏。

然後用了kd-tree空間剖分，限於計算機內存，處理有50萬face的模型分割了500個bucket，最後運行效率在20s左右。

首先離提出問題已經有一段時間了，其實這個問題不難，只是當初不知道從哪下手，對每一個思路都有猶疑，其實這時候最好的辦法就是實現出來，再做比較。目前這個問題的處理效率還能接受，但期望的目標是在處理50萬face模型在5s左右，還需要進一步改進優化。考慮重疊演算法上能否再做改進。還是謝謝大神Milo的指點，給出好多思路。

如果三角形的面積比較均勻，一般的空間剖分方法都可以把接近的三角形分到同一組裡。例如八叉樹、散列空間等。亦可以使用相交測試中常用的演算法，例如sweep-and-prune。然後再做細緻的檢測。

另一個思路是把三角形的平面用Hough transform變換成三維Hough空間的點（三個維度可以用法線的球坐標兩角度，加上面與原點距離。然後把這些點分組，再細緻檢測同組及相鄰組。