algorithm - 3Dメッシュを2Dネットに分解する

Question

一般的なファイル形式で3Dメッシュとして表される3次元オブジェクトがあるとします。メッシュを1つ以上の2D'ネット'に分解するアルゴリズムをどのように考案しますか？つまり、元の3Dオブジェクトを作成するために切り取って折りたたむことができる2次元表現です。

特に、アルゴリズムは以下を考慮する必要があります。

• 任意のオブジェクトに対して可能な複数の分解
• メッシュを固定サイズのキャンバス（紙のシート）にフィットさせる処理。
• ネット内の2つのパネルがいつオーバーラップするか（したがって無効になるか）を認識します。
• オーバーラップまたはページサイズの制約のためにメッシュを単一のネットとして表現できない場合は、メッシュを複数のネットに分割します。
• 隣接する面を取り付けるために、適切な場所にタブを生成します。

明らかな縮退のケースは、エッジの半分にタブが付いた、面ごとに1つのネットを作成することです。これは明らかに理想的ではありません。理想的なケースは、単一の連続ネットです。複雑な形状の現実は、中間のどこかにある可能性があります。

最適なネット（最小のネット/最小のページ）を見つけることはおそらく計算コストがかかることを理解していますが、「十分に良い」ネットを見つけるための優れたヒューリスティックで十分です。

Answer 1

あなたの質問を読んだとき、「自動ペーパークラフトアルゴリズム」という言葉が出てきました。それで私はそれをグーグルで検索し、Massarwiらによる一般化されたシリンダー（pdf）を使用したペーパークラフトモデルを見つけました。

ストリップベースの近似を使用して、三角形のメッシュから丸みを帯びたおもちゃの動物像の展開されたペーパークラフトパターンを生成するための新しい方法を提案します。原則として、三角形化されたモデルは、展開された平面で交差する三角形をチェックしながら、その接続性を可能な限り保持するだけで展開できますが、数万の三角形でパターンを作成することは非現実的です。私たちのアプローチは、内部頂点のない連続した三角ストリップのセットでメッシュモデルを近似することです。最初に、メッシュをモデルの機能に対応するパーツに分割します。各パーツをゾーン領域にセグメント化し、パーツ境界からのトポロジー距離が類似している三角形をグループ化します。ゾーン領域の境界と追加のカットラインを保持しながらメッシュを単純化することにより、三角ストリップを生成します。次に、ストリップのセットを展開するだけでパターンが作成されます。この方法の際立った特徴は、円錐や円柱の一部などの他の線織面ではなく、一連の連続したストリップでメッシュモデルを近似することです。したがって、近似された展開パターンは、メッシュ操作と単純な展開アルゴリズムのみを使用して生成できます。さらに、紙を曲げるだけで（エッジを壊さずに）ストリップのセットを作成でき、元のメッシュモデルの滑らかな特徴を表すことができます。この方法の際立った特徴は、円錐や円柱の一部などの他の線織面ではなく、一連の連続したストリップでメッシュモデルを近似することです。したがって、近似された展開パターンは、メッシュ操作と単純な展開アルゴリズムのみを使用して生成できます。さらに、紙を曲げるだけで（エッジを壊さずに）ストリップのセットを作成でき、元のメッシュモデルの滑らかな特徴を表すことができます。この方法の際立った特徴は、円錐や円柱の一部などの他の線織面ではなく、一連の連続したストリップでメッシュモデルを近似することです。したがって、近似された展開パターンは、メッシュ操作と単純な展開アルゴリズムのみを使用して生成できます。さらに、紙を曲げるだけで（エッジを壊さずに）ストリップのセットを作成でき、元のメッシュモデルの滑らかな特徴を表すことができます。

Shatzらによるメッシュからのペーパークラフトモデル（9MB pdf）と呼ばれる以前の関連論文もあります。

この論文では、メッシュを可展面にセグメント化するためのアルゴリズムを紹介します。このアルゴリズムは、CADやコンピュータグラフィックスのさまざまなアプリケーションで使用できます。このペーパーはペーパークラフトに焦点を当てており、アルゴリズムが開発可能で、カットしやすく、接着できる近似を生成することを示しています。また、与えられたモデルと紙のモデルの間の誤差が小さいことも示されています。

出典：http ：//www.ee.technion.ac.il/~ayellet/images/sel-papers-pic-5.jpg

Answer 2

リンクされたアルゴリズムeed3si9nは、複雑なジオメトリから適切なペーパークラフトメッシュを生成します。多面体モデルのように、モデル化されたとおりにメッシュを展開したい場合は、メッシュをそのまま展開するための比較的簡単な手法を次に示します。

ソースメッシュからグラフを作成します。各面はグラフの頂点であり、2つの頂点がメッシュ内の共通のエッジを共有している場合はそれらが接続されます。これらのグラフの1つは、ループがない場合、つまりツリーである場合にのみ、展開可能なメッシュを表します。

各フォールドは完成したモデルに蓄積されるエラーを表すため、適切なツリーは、開始点から最も遠い面に到達するための最も少ないフォールドラインを表します。ここではダイクストラのアルゴリズムは優れていますが、最小スパニングツリーは機能しません。各エッジが均等に重み付けされているため、すべてのツリーは最小スパニングツリーであり、メッシュを1つの大きなスパイラルに展開するツリーも含まれます。モデルを接着すると、最後のいくつかの面がまったく合わなくなるまでエラーが発生します。

木ができたら、原点に開始面を描くことから始めます。次に、ツリーを歩き、元のメッシュのエッジの長さに対応する半径を持つ2つの円の交点として新しい頂点を計算することにより、新しい面を追加します。タブの位置は、元のメッシュにはあったが、平坦化可能なツリーにはないエッジに対応しています。

ユーザー指定のカットは、ツリーステップの前のエッジ削除として処理できます。

この手法のいくつかの欠点は、フラットパターンで重なり合うパーツを喜んで作成することであり、適切な開始面を見つけることに依存しています。Floyd-Warshalを試して、最初に最小直径の面を見つけましたが、そのO（n ^ 3）動作により、コーヒーブレイクが長すぎました。重複する部分は、ツリーのそのブランチを「不完全」としてマークし、それをスキップして、すべての不完全な面でアルゴリズムを再実行することで処理できます。

Answer 3

私はこれが答えではないことを知っていますが、それは関連しています。元SGIグラフィックスの男PaulHaeberliのLaminaプログラムは、この問題の解決策です。