將實心盒的點映射到四面體網格盒

給定一個帶有點的三維實心盒。給定一個與四面體網格相連的盒子。兩個盒子的尺寸都是一樣的。將實心盒的點映射到四面體網格盒

我需要找到一個算法，它將實體的點映射到網格中相應的四面體。

我使用的下一個算法：

縮小固體，八叉樹
遍歷網格中的四面體，並檢查是否有分支機構或八叉樹的葉相交。（Ratschek & Rockne算法）
如果相交，將八叉樹中的點映射到四面體。

但算法很慢，而且我在檢查盒子和四面體之間的交叉點時遇到了很大的問題。

我仍然可以堅持八叉樹，但我絕對需要一些合理的檢查交叉點。任何評論將不勝感激。

更新：我有200萬固體分和20萬個四面體

更新2：我想實現走在三角

來源

2014-03-13 Vyacheslav Korchagin

一個標準的簡化將首先計算使用軸近似八叉樹四面體十字路口對齊的邊界框。由此產生的相交測試非常簡單。

然後，一旦遍歷樹的葉級，可以使用精確測試來確定給定四面體中包含哪些點。

總結：

Form an octree T for your points X 

for (all tetrahedrons ti in mesh M) 

    Form a minimal axis-aligned bounding-box Bi for tetrahedron ti 

    Traverse T from root, accumulating a list Li of all leaf nodes 
    that overlap with box Bi 

    for (all leaf nodes li in list L) 
     for (all points pi in leaf node li) 

      if (point pi is inside tetrahedron ti /*exact test*/) 
       Associate point pi with tetrahedron ti 
      endif 

     endfor 
    endfor 

endfor

此算法是有效的，如果：(i)在M點X被網狀M內均勻分佈，並且(ii)四面體有合理的長寬比。

實現良好性能的關鍵是確保樹遍歷步驟儘可能高效地實現。

可以通過檢查給定點pi是否位於四面體的4個面的「內」側來完成四面體中點測試。如果給定四面體[i,j,k,l]，則點pi位於面[i,j,k]的「內」側，如果它位於與「相反」頂點l平面[i,j,k]相同的一側。

這些定向測試可以使用自適應精度算法來穩健執行。 Jonathan Shewchuk提供了這樣的實現here。

來源

2014-03-13 19:40:51

假設你知道四面體的頂點，可以通過檢查它是否位於每個平面的left或right一側來檢查一個點是否位於四面體內，例如左邊是指向正常。

用於確定點是在飛機的左側還是右側的數學方法是straight forward。

還有另一個method我找到了，但看起來像我的答案的變種。

當然，如果一個點位於tet內部，它將被映射到tet。該方法可以作爲頂點着色器或OpenCL/CUDA內核來實現，這將使其高度平行。

來源

2014-03-14 18:36:19

將實心盒的點映射到四面體網格盒

回答

相關問題