3d - 3D シェイプ上にサンプル ポイントを作成する

Question

三角形で表される 3D ソリッドからポイント サンプルを作成するアルゴリズムを推奨できますか? ポイント サンプルはサーフェス上にほぼ均一に分布している必要があり、特定の半径のボールがポイント サンプルを通過しないことが保証されている必要があります。

Answer 1

最適なパフォーマンスを必要とせず (またはポイントを事前計算できる)、多くのコードを記述したくない場合は、モンテカルロのバリエーションを使用できます。

モデルのバウンディング ボックス内の多数のランダム ポイントから開始するか、ボールの半径の密度でグリッドに編成することができます。

次に、すべてのポイントについて：

• 最も近い三角形と距離を見つける
• 遠すぎる場合は破棄します
• そうでない場合は、三角形に投影します

かなり重いことは承知していますが、コードは比較的シンプルにする必要があります。

---

もう一度考えてみると、別の簡単な方法があります。

• すべての三角形について、その辺の長さを計算します。
• エッジが長すぎる場合 - 三角形を分割します (2 つまたは 4 つに - 必要に応じて異なります)。
• 結果の分割頂点 (頂点) をポイント リストに追加します。
• 結果の三角形で同じことを行います。
• 最後に、メッシュの頂点もリストに追加します。

理想的なディストリビューションにはなりませんが、書くのは非常に簡単で、動作するはずです :) .

Answer 2

The simplest method that I know of for doing this is a two stage process. 1) unfold the mesh back to a two dimensional representation, and 2) use a sampling technique that results in approximately uniformly distributed points on the surface.

The unfolding process is most likely going to be the most challenging step if you need to implement everything yourself. Tools like blender and meshlab include tools to do this because the problem is related to generation of UV texture co-ordinates in 3D graphics. I believe there are a number of algorithms and techniques for approaching such problems, but selecting the best may be a case of trial and error depending on how degenerate your triangles are.

The uniform distribution of points on the resultant unfolded mesh is then easy - you can use a low discrepancy sampling sequence (such as the Halton or Hammersly sequence) to produce an almost uniform distribution of points over your space, and rejection sampling to remove any points that don't fall within the unfolded mesh.

You'll need to do some extra checks that the seams of your mesh in the unfolding retain an appropriate level of sampling to ensure that your requirements of the minimal ball are met, when it is refolded.

From past experience the caveat of this approach is that if your mesh isn't manifold (ie/ it has cracks, self intersections or t-junctions), you'll almost certainly have to clean these up before you start. For very large data sets this can be prohibitively time consuming.