How to detect and save cyclic connectivity in edge

Question

thanks for taking the time to read my question.

I am working on detecting holes in a triangular mesh and fill them with new triangles. I have done some of the parts that are, to get a list of edge vertices, etc. Following are the vertices/edges that make holes, please have a look at the image.

(9, 62)         => vertex # 9  and 62 makes an edge (left hole)
(66, 9)         => vertex # 66 and 9  makes an edge (left hole)
(70, 66)        => vertex # 70 and 66 makes an edge (left hole)
(62, 70)        => vertex # 62 and 70 makes an edge (left hole)

(147, 63)       => vertex # 147 and 63 makes an edge (right hole)
(55, 148)
(63, 149)
(149, 55)
(148, 147)

The first thing that I need to do is to check which vertices make a cycle (means a hole is detected), and then save in a separate set of cyclic vertices.

The issue is to write such an algorithm that checks whether the given graph(vertices/edges) contains how many cycles? and then save into separate sets.

Please write me some simple and optimized algorithm to solve this problem.

Thank you.

Answer 1

1. mesh

   Let assume your STL mesh got n triangles you need to convert it into indexed format. So extract all triangle points and convert to two separate tables. one holding all the points and second holding 3 indexes of points per each triangle. Let assume you got m points and n triangles.

   You should have the point table (index) sorted and using binary search to speed this up from O(n.m) to O(m.log(n)).

2. _edge structure

   create structure that holds all the edges of your mesh. Something like:

   struct _edge
    {
    int p0,p1; // used vertexes index
    int cnt;   // count of edge usage
    };
   

   where p0<p1.

3. create _edge edge[] table O(n)

   It should be a list holding all the edges (3n) so loop through all the triangles and add 3 edges per each. The count set to cnt=1 This is O(n).

   Now sort the list by p0,p1 which is O(n.log(n)). After that just join all the edges with the same p0,p1 by summing their cnt and deleting one of them. If coded right then this is O(n).

4. detect hole

   In regular STL each edge must have cnt=2. If cnt=1 then triangle is missing and you found your hole. if cnt>2 you got geometric error in your mesh.

   So delete all edges with cnt>=2 from your edge[] table which is O(n).

5. detect loops

   let assume we got k edges left in our edge[] table. Now for each 2 edges that are sharing a point create triangle. Something like:

   for (i=0;i<k;i++)
    for (j=i+1;j<k;j++)
     {
     if ((edge[i].p0==edge[j].p0)||(edge[i].p1==edge[j].p0)) add_triangle(edge[i].p0,edge[i].p1,edge[j].p1);
     if ((edge[i].p0==edge[j].p1)||(edge[i].p1==edge[j].p1)) add_triangle(edge[i].p0,edge[i].p1,edge[j].p0);
     }
   

   If you use binary search for the inner loop then this will be O(k.log(k)). Also you should avoid to add duplicate triangles and correct the winding of them so first add the triangles to separate table (or remember starting index) and then remove duplicates (or you can do it directly in add_triangle).

   Also to handle bigger holes do not forget to add new edges to your edge[] table. You can either update the edges after current edges are processed and repeat #4 or incorporate the changes on the run.

[Edit1] C++ example

recently I was doing some coding for STL for this QA:

• Generating outside supporters into mesh for 3D printing

So as I got all the infrastructure already coded I chose to give this a shot and here the result:

struct STL3D_edge
    {
    int p0,p1,cnt,dir;
    STL3D_edge()    {}
    STL3D_edge(STL3D_edge& a) { *this=a; }
    ~STL3D_edge()   {}
    STL3D_edge* operator = (const STL3D_edge *a) { *this=*a; return this; }
    //STL3D_edge* operator = (const STL3D_edge &a) { ...copy... return this; }
    int operator == (const STL3D_edge &a) { return ((p0==a.p0)&&(p1==a.p1)); }
    int operator != (const STL3D_edge &a) { return ((p0!=a.p0)||(p1!=a.p1)); }
    void ld(int a,int b) { cnt=1; if (a<=b) { dir=0; p0=a; p1=b; } else { dir=1; p0=b; p1=a; }}
    };
List<STL3D_edge> edge;
List<float> pnt;
void edge_draw()
    {
    int i; STL3D_edge *e;
    glBegin(GL_LINES);
    for (e=edge.dat,i=0;i<edge.num;i++,e++)
        {
        glVertex3fv(pnt.dat+e->p0);
        glVertex3fv(pnt.dat+e->p1);
        }
    glEnd();
    }
void STL3D::holes()
    {
    //  https://stackoverflow.com/a/45541861/2521214
    int i,j,i0,i1,i2,j0,j1,j2;
    float q[3];
    _fac        *f,ff;
    STL3D_edge  *e,ee,*e0,*e1,*e2;
    ff.attr=31<<5;                          // patched triangles color/id

    // create some holes for testing
    if (fac.num<100) return;
    for (i=0;i<10;i++) fac.del(Random(fac.num));

    // compute edge table
    edge.allocate(fac.num*3); edge.num=0;
    for (f=fac.dat,i=0;i<fac.num;i++,f++)
        {
        // add/find points to/in pnt[]
        for (i0=-1,j=0;j<pnt.num;j+=3){ vectorf_sub(q,pnt.dat+j,f->p[0]); if (vectorf_len2(q)<1e-6) { i0=j; break; }} if (i0<0) { i0=pnt.num; for (j=0;j<3;j++) pnt.add(f->p[0][j]); }
        for (i1=-1,j=0;j<pnt.num;j+=3){ vectorf_sub(q,pnt.dat+j,f->p[1]); if (vectorf_len2(q)<1e-6) { i1=j; break; }} if (i1<0) { i1=pnt.num; for (j=0;j<3;j++) pnt.add(f->p[1][j]); }
        for (i2=-1,j=0;j<pnt.num;j+=3){ vectorf_sub(q,pnt.dat+j,f->p[2]); if (vectorf_len2(q)<1e-6) { i2=j; break; }} if (i2<0) { i2=pnt.num; for (j=0;j<3;j++) pnt.add(f->p[2][j]); }
        // add edges
        ee.ld(i0,i1); for (e=edge.dat,j=0;j<edge.num;j++,e++) if (*e==ee) { e->cnt++; j=-1; break; } if (j>=0) edge.add(ee);
        ee.ld(i1,i2); for (e=edge.dat,j=0;j<edge.num;j++,e++) if (*e==ee) { e->cnt++; j=-1; break; } if (j>=0) edge.add(ee);
        ee.ld(i2,i0); for (e=edge.dat,j=0;j<edge.num;j++,e++) if (*e==ee) { e->cnt++; j=-1; break; } if (j>=0) edge.add(ee);
        }

    // delete even times used edges (to speed up the loops finding)
    for (i0=i1=0,e0=e1=edge.dat;i0<edge.num;i0++,e0++)
     if (int(e0->cnt&1)==1) { *e1=*e0; i1++; e1++; } edge.num=i1;
    // find 2 edges with one comon point (j1)
    for (e0=edge.dat,i0=0;i0<edge.num;i0++,e0++) if (int(e0->cnt&1)==1)
     for (e1=e0+1,i1=i0+1;i1<edge.num;i1++,e1++) if (int(e1->cnt&1)==1)
        {
        // decide which points to use
        j0=-1; j1=-1; j2=-1;
        if (e0->p0==e1->p0) { j0=e0->p1; j1=e0->p0; j2=e1->p1; }
        if (e0->p0==e1->p1) { j0=e0->p1; j1=e0->p0; j2=e1->p0; }
        if (e0->p1==e1->p0) { j0=e0->p0; j1=e0->p1; j2=e1->p1; }
        if (e0->p1==e1->p1) { j0=e0->p0; j1=e0->p1; j2=e1->p0; }
        if (j2<0) continue;
        // add missin triangle
        if (e0->dir)
            {
            vectorf_copy(ff.p[0],pnt.dat+j1);
            vectorf_copy(ff.p[1],pnt.dat+j0);
            vectorf_copy(ff.p[2],pnt.dat+j2);
            }
        else{
            vectorf_copy(ff.p[0],pnt.dat+j0);
            vectorf_copy(ff.p[1],pnt.dat+j1);
            vectorf_copy(ff.p[2],pnt.dat+j2);
            }
        ff.compute();
        fac.add(ff);
        // update edges
        e0->cnt++;
        e1->cnt++;
        ee.ld(j0,j2); for (e=edge.dat,j=0;j<edge.num;j++,e++) if (*e==ee) { e->cnt++; j=-1; break; } if (j>=0) edge.add(ee);
        break;
        }
    }

The full C++ code and description for the STL3D class is in the link above. I used some sphere STL mesh I found in my archive and color the hole patching triangles in green to recognize them. Here the result:

The black lines are wireframe and red ones are just debug draw of the edge[],pnt[] arrays for debug ...

As you can see it works even for holes bigger than just single triangle :) ...