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

希望这可以帮助。