用於從雲點生成三角形網格的算法

Question

在一些仿真程序中，我們根據點生成物體表面，每個點都具有3D座標以及代表該點表面法線的向量。爲了可視化目的，我們希望生成由三角形組成的網格;每三個關閉點與正常點形成一個三角形。然後，我們可以將這些信息發送給一些標準的可視化程序，使VMD（視覺分子動力學）等表面呈現出來。

我們不知道哪個是最快/可用的算法。

Answer 1

看看Jonathan Shewchuk的工作，特別是對他（與他的同事一起）著名的論文和實現：

• Streaming Computation of Delaunay Triangulations

• A Two-Dimensional Quality Mesh Generator and Delaunay Triangulator

有也是點雲庫（PCL）中實現的未分類點雲的快速實現。請在Fast triangulation of unordered point clouds上查看他們的介紹。

Answer 2

Misha Kazhdan的泊松算法可能適用於您的數據。其軟件頁面爲here。請注意，還有一個CGAL版本。手冊是here並準備使用Windows演示here（假設您安裝了這些dlls）。

Answer 3

請注意，Delaunay三角剖分可能不適合您的應用，因爲Delaunay三角剖分不適合真正的3D問題（即點在R3中分佈均勻）。它們更適合二維流形問題（即地形等）。

要在R3中生成曲面，請查看Hugues Hoppe和他的「曲面重建」工作。

表面重建用於找到網格表面以適應點雲;然而，這種方法產生高三角形數量。如果這是一個問題，那麼可以應用網格縮減技術來減少多邊形數量，從而最大限度地減少錯誤。作爲一個例子，你可以看看OpenMesh的抽取方法。

Hugues Hoppe

OpenMesh