3Dモデルをエッジループで分割

Question

次のようなものを表す 3D モデルがあります。

class Vertex
{
    double x, y, z;
}

class Edge
{
    Vertex *v1, *v2; // no particular order
    Face *f1, *f2; // no particular order. f2 may be null.
}

class Face
{
    List<Vertex*> vertices; // clockwise order
    List<Edge*> edges; // clockwise order
}

class Model
{
    List<Face*> faces;
    List<Vertex*> vertices;
    List<Edge*> edges;
}

もちろん、これは最も便利な表現に変換できます。

このモデルを、接続されたエッジの複数のループに沿っていくつかの切り離された部分に分割し、端をキャップする新しい面を作成したいと考えています。1 つのループの例:

新しい面は同じ位置にあり、他の面との接続を除けば同一である必要がありますが、この例ではそれらを離して移動しました。どうすればこんなことができるでしょうか？

接続されていないパーツ間で頂点が共有されているかどうかは問題ではありません。

すべてのエッジが 2 つの面に正確に接続しているため、各エッジを個別に 2 つのコピー (面ごとに 1 つ) に分割してみました。これにより、必要に応じてモデルが分離されますが、新しい面を正しく追加する方法がわかりません。

この問題はグラフ理論に何らかの形で関連しているように見えるため、この質問にはグラフ アルゴリズムのタグが付けられています。

Answer 1

• モデルを修正します。 class Edge へのポインタを保持する必要があります Face そして Vertex 価値観の代わりに。
• 何らかのものを使用したいと考えています。 set の代わりに List あなたの中で class Model. 。これは、項目の検索と削除に役立ち、重複がないことを確認できます。

• 関数のプロトタイプを考え出します。私は提案します

pair<Model*, Model*> split_model( const Model* mx, const List<Edge*>& loop );

• 2 つの新しい空のモデルを作成するとします。 ma そして mb. 。からエッジを追加します loop それぞれに。
• から 1 つのエッジを選択します loop. 。それに付けられた 2 つの顔を呼びましょう fa そして fb.
• 追加 fa モデルに ma. 。から始まる fa, に接続されているすべてのエッジをたどって完全なグラフ検索を実行します。 fa, 、およびそれらのエッジにアタッチされているすべての面など。検出されたすべての面とエッジをたどってモデルに追加する必要があります ma. 。すでに一部となっている面またはエッジに遭遇した場合は、 ma あなたは彼らに従いません。特に、以下に属するエッジに遭遇すると常にこれが起こります。 loop だから国境を越えることはありません。このようにして、片側のすべてのエッジと面を完全に検索し、完全なモデルが得られます。 ma. 。最後に、カットを表す面を追加します。ここでは頂点はほとんど無視できますが、もちろん最後には、追加した面に属するすべての頂点を追加することになるでしょう。
• 顔から始めてこの手順を繰り返します fb モデルを作成するには mb 他の部分を表します。