Detect tetrahedra within a triangulated mesh?

Question

Let's say I have a mesh that has lines connecting the vertices in a way that would allow it to be split into tetrahedra. Is there an algorithm I can use to detect the presence of the tetrahedra given the vertices and lines? (I.e., given the mesh with connecting lines, output a set of tetrahedra that have the same shape and volume.)

Edit: Tetrahedra are not allowed to intersect.

So are you saying that all of the edges necessary to form the tetrahedra are already present as the set of lines?? — Darren Engwirda
There is an array for vertices [x, y] and an array for lines [index of start point in verticies array, index of end point in verticies array]. — Conner Ruhl
the vertices are [x,y,z] right? we cannot talk about a tetrahedra in 2D. — meyumer

Darren Engwirda Darren Engwirda · Accepted Answer · 2013-01-16T22:51:05

I think a graph-based approach may work.

First, the list of triangular faces can be recovered by noting that the set of edges define an undirected graph G1(V1,E1) for connectivity between the geometric vertices. A triangular face is any length 3 cycle in this graph.

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

Next, the tetrahedra can be recovered by forming the undirected graph G2(V2,E2) defining the connectivity between faces (i.e. faces are connected if they share an edge). A tetrahedra is any length 4 cycle in this graph.

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

Hope this helps.

Detect tetrahedra within a triangulated mesh?

1 Answers