1. 首頁
  2. 問答
  3. 切片網格的算法或軟件

切片網格的算法或軟件

2012-03-14 61 views
10

切片3D網格的正確方法是什麼？網格都是封閉曲面，切片需要是網格內部的二值圖像。例如，表示球和切片圖像的網格是實心圓的網格。切片網格的算法或軟件

我正在尋找一個軟件庫或算法，我可以將其集成到我當前的C++項目中。

來源

2012-03-14 dr_rk

+2

一種可能性是呈現用OpenGL的網格，並且用一個剪取平面做了「切片」。 – 2012-03-14 20:57:03

回答

16

我的開源遊戲庫包含網格切片的實現。它可以與Irrlicht api協同工作，但可以通過適度的努力重新編寫使用不同的API。您可以根據BSD許可證的條款使用代碼，或從中學習您自己的實現。

請參閱this file for an implementation of mesh slicing中的MeshTools :: splitMeshZ。

如果你只是想知道的算法，這裏是什麼，我做了一個高層次的描述：

我最初以爲使用軸對齊的邊界框指定到哪裏可以削減目。這是有問題的，因爲它引入了許多特殊情況。例如，穿過盒子角落的邊緣可能會被分成三塊，而不僅僅是兩塊。

使用平面將網格切割爲左網格和右網格減少了特殊情況的數量，因爲邊緣位於平面的一側或另一側，或者它穿過平面，所以切成兩塊。

可以簡單地通過切割一次，取出所得到的網格之一併在另一個位置將其再次切割等來進行任何期望的切割配置。具體來說，在本節中描述的情況下，可以通過將球的一半切下來，從一個球體上切下一個圓圈，移動一小部分飛機並切掉另一半，只留下一個薄帶。 （你不能用我編寫的代碼將網格劃分爲幾乎沒有深度的網格，但是可以將網格劃分爲任何你設置了浮點平等閾值的網格，我認爲我在我的代碼中任意選擇了0.001）。

使用類似的邏輯，可以使用固定平面實現任何所需的切割角度;您只需要轉換網格以相對於固定切割平面旋轉網格，然後再將結果轉換回來。 （對於我的遊戲，我只需要垂直於XY平面的切割，所以爲了簡單起見，我只允許設置切割的Z值，並假定切割位於Z位置。）

OK，現在我們已經簡化了問題，該算法並沒有那麼糟糕：

啓動條件：您有一個切割平面。你有一組源三角形。您有兩個目的地集多邊形（不是三角形;四邊形可能通過切割三角形生成）。這兩個目標集稱爲左和右。

過程：迭代三個三角形的點。計算小於切割平面的點數。我會將那些比割平面左側更低的那些以及比割平面右側更大的那些稱爲。只有對很少幾個案件：

  • 所有的三角點上左：把三角形的左側設置
  • 所有的點都在右：把三角形的右側設置
  • 一點是左的，其他的是右的：如果你在兩條邊上切出一個三角形，並且你拿着其中一個點，那麼最終會保持一個更小的三角形。在由左點組成的左集合中放置一個三角形，並在邊線穿過平面的兩個點上放置一個三角形。在Right集中放置一個四元組（參見下一個案例）。

  • 兩點是左，一點是右。如果您拿着一個三角形的邊緣並將其切成另外兩條邊，則您將留下一個梯形。在由你手中的兩個點組成的左側組中放置一個四邊形，再加上穿過切割的兩個點。在右邊放置一個三角形（上面情況的鏡像）。

  • 完成後，通過在最短部分之間添加鏈接將四邊形變成三角形。

就是這樣。這是基本算法。實際的代碼處理了一些情況，比如如果邊與切割完全相同，如果三角形恰好在邊上，不添加簡併多邊形（例如，沒有物體的點）等等。

其他問題（涵蓋的所有鏈接的代碼）：

  • 不要過於複雜的數學爲LERP'ing在邊越過切割平面的地方。它不需要完整的線性插值，它實際上只是Highschool代數II：上升超過運行，乘以比率

  • 緩存生成的（LERP）點是有利的，以便共享頂點的三角形未切割網格將在切割網格中共享相應的新頂點。

  • 如果您要保留頂點共享，並且您正在使用三角形索引緩衝區，那麼當您第一次生成放置左右集合的形狀時，您不幸不知道索引。我使用名爲「PossibleVertex」的類來表示未來的三角形索引號。

  • 如果打算顯示網格，則排列順序很重要。仔細想想你如何編碼它可以確保生成的多邊形使用與它們來自的三角形相同的繞線順序。在對四邊形進行三角測量時，這會變得特別棘手。我不記得細節，但它都在鏈接的代碼中處理。

  • 對於我的遊戲，我想製作連接兩個切割網格的扁平緞帶。這就是爲什麼splitMeshZ會產生3個網格，而不僅僅是兩個網格。您可以使用中間網格，或者只是忽略它。

來源

2012-04-24 06:24:31 Dennis

+0

你寫了一個類似的代碼來獲得剛好與網格相交的平面，而不是結果切片？ – user1365836 2012-11-27 15:51:27

1

我假設你在談論三角網格？

什麼是「正確」方法在很大程度上取決於您的用例的具體情況。

傑裏建議的OpenGL方法可能適合你。

另一種方法是顯式計算切割。你可以通過CGAL。更具體地說，它的3D內核。它具有一個function，可以計算各種基元之間的交集，包括平面和三角形。使用此功能，您可以精確計算交叉點輪廓並將其渲染爲圖像。 - 這樣你就不會依賴於OpenGL，而是依賴於CGAL。

來源

2012-03-14 22:15:27

+0

CGAL函數很有意思，所以x-y平面和多面體網格的交點會返回什麼？ – 2012-03-15 02:14:20

+1

你將不得不單獨與每個三角形相交。在常見情況下，如果沒有交點或線段，'intersection'將返回'0'。還有一種情況是三角形完全位於飛機上，或者只在一個角落觸及三角形，在這種情況下，交叉點分別返回三角形或單個點。 – 2012-03-15 08:18:16

2

我已經列出了在this answer中計算平面體積交點的算法。提供了Java中的實現。

來源

2012-03-15 09:25:55 ryanm

0

，如果你自己實現，那將是更快（爲自己，而不是在運行時間）：這是你需要做的簡單步驟：

1，提取網格

的所有三角形

2-對於每個三角形，

2-1-檢查，如果任何的三角形點在切片平面，

2-2-如果沒有，則對於每個其三個邊緣的，發現相交離子與你的切片平面（如果有的話）。你必須有兩個與飛機相交或沒有。

2-2-1如果兩條邊與平面相交，則在平面上的這兩點之間添加一條直線。

來源

2017-01-19 12:05:58

相關問題

 相關問題