检测三角网格内的四面体？

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)回收。在这个图中，四面体是任何长度的四个周期。

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 

希望这会有所帮助。