algorithm - 三角メッシュ内で四面体を検出しますか?

Question

四面体に分割できるように頂点を結ぶ線を持つメッシュがあるとします。頂点と線分から四面体の存在を検出するために使用できるアルゴリズムはありますか? (つまり、接続線を持つメッシュが与えられた場合、同じ形状と体積を持つ四面体のセットを出力します。)

編集: 四面体は交差できません。

Answer 1

グラフベースのアプローチがうまくいくと思います。

G1(V1,E1)まず、三角形の面のリストは、エッジのセットが幾何学的頂点間の接続性の無向グラフを定義することに注意することで復元できます。このグラフでは、三角形の面は任意の長さ3サイクルです。

for (i = all vertices in G1)
// form list of vertex triplets
    list = find all length 3 cycles from ith vertex
// push new faces onto output
    for (j = all triplets in list)
        [v1,v2,v3] = list(j)
        if ([v1,v2,v3] is not an existing face)
            push triplet [v1,v2,v3] as a new face
        endif
    endfor
endfor

次に、面間の接続を定義する無向グラフを作成することにより、四面体を復元できますG2(V2,E2)（つまり、面がエッジを共有している場合、面は接続されます）。このグラフでは、四面体は任意の長さの4サイクルです。

for (i = all vertices in G2)
// form a list of face tuples
    list = find all length 4 cycles from ith vertex
// push new tetrahedra onto output
    for (j = all tuples in list)
        [f1,f2,f3] = list(j)
        [v1,v2,v3,v4] = unique vertices in faces [f1,f2,f3]
        if ([v1,v2,v3,v4] is not an existing tetrahedra)
            push tuple [v1,v2,v3,v4] as a new tetrahedra
        endif
    endif
endfor

お役に立てれば。