How can I connect two parallel 2d polygons to create a seamless 3d mesh?

Question

Suppose I have two polygons, one just above the other like this:

I'd like to connect up their vertices to create a 3d mesh out of triangles around their perimeters. This picture shows one way you might do this (orange lines represent triangle edges):

This sort of thing can be done intuitively by a human, but I'm having real trouble translating it into a working algorithm.

The polygons are stored as a List<Vector2>. They will always be simple, and may be concave.

Answer 1

I would do it like this:

1. find two closest points in each polygons

   this will be used as start point

2. reorder vertexes from this two start points

   with the same winding rule for example CW like on image

3. find 'center' points for each polygon

   for example average of all vertexes or mid point of bounding box or whatever. It does not need to be precise but on complex concave shapes wrongly selected center position will cause errors in output mesh.

4. add angular info for each vertex

   angle is easy just use

   a=atan2(vertex-center)
   

After all this it should looks like this:

for angle angle [deg]

index: 0   1   2   3   4
green: 355 085 135 170 230 
 blue: 020 135 255

Now you just match 2 closest vertexes from one polygon to the other

do not forget that angle difference is max +/-180 deg and also if you use radians then convert constants 180,360 to PI,2.0*PI

da=ang1-ang0;
while (da<-180.0) da+=360.0;
while (da>+180.0) da-=360.0;
if (da<0.0) da=-da;

for next text line(i,j) will mean i-th vertex from green and j-th vertex from blue polygon

Now the joining:

1. join closest vertexes

   just process all green vertexes and join them to closest blue vertex (black lines on image)

   line(0,0)
   line(1,1)
   line(2,1)
   line(3,1)
   line(4,2)
   

2. fill the holes

   mesh triangulation need at least 2 joints per vertex so process points that have less connections:

               index: 0 1 2 3 4
   green connections: 1 1 1 1 1
    blue connections: 1 3 1
   

   so now process less then 2 times used blue vertexes (0,2) and join them to closest green vertex (yellow lines on image) ignoring already used connection (chose next one in that case)

   line(1,0)
   line(3,2)
   

   so:

               index: 0 1 2 3 4
   green connections: 1 2 1 2 1
    blue connections: 2 3 2
   

   now process the rest of green less then 2 times used vertexes joined to less then 3 times used blue vertex. Chose just the next point to already used connection if it has less then 3 connections and if there are more then 1 option use the closest one (red lines on image).

line(0,2) green 0 is connected to blue 0 so choose from blue 1,2 (1 is too used so 2)
line(2,-) green 2 is connected to blue 1 which is 3 times used so ignore this vertex
line(4,-) green 4 is connected to blue 2 which is 3 times used so ignore this vertex

                index: 0 1 2 3 4
    green connections: 2 2 1 2 1
     blue connections: 2 3 3

and that is it all. Now you should have the tesselation done like this:

[notes]

• you can also use perimeter position / perimeter length instead of angle (sometimes it have better results)
• concave polygons can mess this up a lot so there should be added some triangle intersection checks to avoid problems.
• also the number of vertexes should not differ too much between polygons in that case you can still divide some lines to add missing points otherwise that 3 times usage conditions will be wrong (if the vertex count differs 2 or more times)
• if you want to be safe you should cut polygons to convex parts and tesselate them separately and only after that join the meshes back together

[Edit1] new approach less susceptible to concavity and points density

Its slower but looks its working for more complex shapes. As example I took the modified star and plus sign from the comments.

1. find two closest points in each polygons

   this will be used as start point

2. reorder vertexes from this two start points

   with the same winding rule for example CW like on image

3. prepare edge lists

   we will need a structure holding all the connections between polygons. I decided to something like this:

   List< List<int> > edg0,edg1;
   

   where edg0[point0][i] is holding i-th point1 connected to point0. Beware in the code array index is the point index and the actual value n the array is point index in a global point table pnt where I can transform between the two like this:

   point0 = (pnt_index - ix0)/3 
   point1 = (pnt_index - ix1)/3 
   pnt_index = ix0 + 3*point0
   pnt_index = ix1 + 3*point1
   

   where ix0,ix1 are start indexes in pnt for each polygon.

4. join close points

   Instead of joining to the closest points I added thresholding so the point distance must be smaller than threshold minll. This threshold is a multiply of the distance of the 2 start points (min distance). In code:

   minll=2.5*l0;
   

   but beware I am comparing distance^2 for speed so if you got distance it would be

   minl=sqrt(2.5)*l0;
   

   The multiply coefficient can be tweaked ...

   

   as you can see the distant point on star is not connected due thresholding.

5. fill unused holes in points0

   simply find sequence of unused points0 and then interpolate the join from start to end with first neighbors that are connected. so if points0 i0 .. i1 are unconnected and their closest neighbors are connected take their closest connected points1 j0 .. j1 and simply linearly connect point i with j where:

   i = i0 + t*(i1-i0)
   j = j0 + t*(j1-j0)
   

   where t is parameter t=<0.0,1.0> going through all "integer" point indexes. (use DDA).

   

6. fill unused holes in points1

   its the same as #5 but look for the unconnected points1 in the other polygon.

   

7. find&connect singular connection lines

   both endpoints are used just once. So simply find such edge and connect it to neighboring points.

   

8. find singular poinst0 that form QUAD hole and triangulate it

   so find point0 that is connected just once and then test its neighbors if the are connected back to the point1 the first one was connected to. If no you found QUAD hole so triangulate it.

   

9. now just extract triangles and lines from the edg0,edg1

   line are simple as they are already encoded directly, for triangles simply search neighboring point0 for connection to the same point1. If found form a triangle. the triangles should be formed also in the other edge list so search neighboring point1 that are connected to the same point0 too.

Here GL/C++ example

List<double> pnt;
List<int> lin,tri;
int iy0=0,iy1=0,iy2=0,iy3=0;// pol0<iy0,iy1),pol1<iy1,iy2),merge<iy2,iy3)
int ix0=0,ix1=0,ix2=0;      // points1<ix0,ix1), points2<ix1,ix2)
//---------------------------------------------------------------------------
void obj_init()
    {
    // input data
    const double d=0.5;             // distance between polygons
    const double pol0[]={0.0,2.0, 1.0,2.0, 1.0,3.0, 2.00,3.0, 2.0,2.0, 3.00,2.0, 3.0,1.0, 2.0,1.0, 2.0,0.0, 1.0,0.0, 1.0,1.0, 0.0,1.0, 0.0,2.0};
//  const double pol1[]={0.0,0.0, 1.0,1.0, 0.0,2.0, 1.25,1.5, 1.5,2.5, 1.75,1.5, 3.0,2.0, 2.0,1.0, 3.0,0.0, 1.5,0.7};
    const double pol1[]={0.0,0.0, 1.0,1.0, 0.0,2.0, 1.25,1.5, 1.5,5.0, 1.75,1.5, 3.0,2.0, 2.0,1.0, 3.0,0.0, 1.5,0.7};
//                                                                ***
    // variables
    List<double> tmp;
    List< List<int> > edg0,edg1;    // edge table

    double minll;                   // max distance to points that will join automatically
    double p[3],l0,l;
    int i,i0,i1,ii,ii0,ii1,di;
    int j,j0,j1,jj,jj0,jj1,dj;
    int k,n0,n1,e,de;
    pnt.num=0;
    lin.num=0;

    // copy pol0 to point list pnt[]
    ix0=pnt.num;
    n0=sizeof(pol0)/sizeof(pol0[0]);
    for (j=pnt.num,i=0;i<n0;)
        {
        pnt.add(pol0[i]); i++;
        pnt.add(pol0[i]); i++;
        pnt.add(-d);
        } ix1=pnt.num; n0/=2;

    // copy pol1 to point list pnt[]
    n1=sizeof(pol1)/sizeof(pol1[0]);
    for (j=pnt.num,i=0;i<n1;)
        {
        pnt.add(pol1[i]); i++;
        pnt.add(pol1[i]); i++;
        pnt.add(+d);
        } ix2=pnt.num; n1/=2;

    // add polygon edges
    iy0=lin.num;
    for (j=ix1-3,i=ix0;i<ix1;j=i,i+=3){ lin.add(j); lin.add(i); } iy1=lin.num;
    for (j=ix2-3,i=ix1;i<ix2;j=i,i+=3){ lin.add(j); lin.add(i); } iy2=lin.num;

    // find closest points -> start points i0,j0
    i0=-1; j0=-1; l0=0.0; minll=0.0;
    for (i=ix0;i<ix1;i+=3)
     for (j=ix1;j<ix2;j+=3)
        {
        vector_sub(p,pnt.dat+i,pnt.dat+j);
        l=vector_len2(p);
        if ((i0<0)||(l<l0)){ l0=l; i0=i; j0=j; }
        } minll=2.5*l0;
    // reorder points so closest ones are first
    if (i0!=ix0)
        {
        tmp.num=0;  for (i=ix0;i<ix1;i++) tmp.add(pnt.dat[i]);                          // copy to temp
        for (j=i0,i=ix0;i<ix1;i++,j++,(j>=ix1)?j=ix0:j=j) pnt.dat[i]=tmp.dat[j-ix0];    // reorder
        }
    if (j0!=ix1)
        {
        tmp.num=0;  for (i=ix1;i<ix2;i++) tmp.add(pnt.dat[i]);                          // copy to temp
        for (j=j0,i=ix1;i<ix2;i++,j++,(j>=ix2)?j=ix1:j=j) pnt.dat[i]=tmp.dat[j-ix1];    // reorder
        }

    // init edge lists
    edg0.allocate(n0); edg0.num=n0; for (i=0;i<n0;i++) edg0[i].num=0;
    edg1.allocate(n1); edg1.num=n1; for (i=0;i<n1;i++) edg1[i].num=0;

    // join close points
    for (ii=0,i=ix0;i<ix1;i+=3,ii++)
        {
        j0=-1; jj0=-1; l0=0.0;
        for (jj=0,j=ix1;j<ix2;j+=3,jj++)
            {
            vector_sub(p,pnt.dat+i,pnt.dat+j);
            l=vector_len2(p);
            if ((j0<0)||(l<l0)){ l0=l; j0=j; jj0=jj; }
            }
        if ((j0>=0)&&(l0<minll))
            {
            edg0.dat[ii ].add(j0);
            edg1.dat[jj0].add(i);
            }
        }

    // fill unused holes in points0
    for (e=1,i=0;e;)
        {
        e=0;
        // find last used point0 -> i0
        i0=-1; i1=-1;
        for (j=0;j<n0;j++,i++,(i==n0)?i=0:i=i) if (edg0.dat[i].num) i0=i; else if (i0>=0) break;
        // find next used point0 -> i1
        if (i0>=0) if (edg0.dat[i].num==0)
         for (j=0;j<n0;j++,i++,(i==n0)?i=0:i=i) if (edg0.dat[i].num){ i1=i; break; }
        if (i1>=0)
            {
            // find last used point1 joined to i0 -> j0
            j0=-1; jj0=-1; l0=0.0;
            i=i0+1; if (i>=n0) i=0; ii=ix0+i+i+i;
            for (j=0;j<edg0.dat[i0].num;j++)
                {
                jj=edg0.dat[i0].dat[j];
                vector_sub(p,pnt.dat+ii,pnt.dat+jj);
                l=vector_len2(p);
                if ((j0<0)||(l<l0)){ l0=l; j0=(jj-ix1)/3; jj0=jj; }
                } i0=i;
            // find next used point1 joined to i1 -> j1
            j1=-1; jj1=-1; l0=0.0;
            i=i1-1; if (i<0) i=n0-1; ii=ix0+i+i+i;
            for (j=0;j<edg0.dat[i1].num;j++)
                {
                jj=edg0.dat[i1].dat[j];
                vector_sub(p,pnt.dat+ii,pnt.dat+jj);
                l=vector_len2(p);
                if ((j1<0)||(l<l0)){ l0=l; j1=(jj-ix1)/3; jj1=jj; }
                } i1=i;
            // join i0..i1 <-> j0..j1
            di=i1-i0; if (di<0) di+=n0; // point0 to join
            dj=j1-j0; if (dj<0) dj+=n1; // point1 to join
            de=di; if (de<dj) de=dj;    // max(points0,point1)
            for (e=0;e<=de;e++)
                {
                i=i0+((e*di)/de); if (i>=n0) i-=n0; ii=ix0+i+i+i;
                j=j0+((e*di)/de); if (j>=n1) j-=n1; jj=ix1+j+j+j;
                for (k=0;k<edg0.dat[i].num;k++) // avoid duplicate edges
                 if (edg0.dat[i].dat[k]==jj)
                  { k=-1; break; }
                if (k>=0)
                    {
                    edg0.dat[i].add(jj);
                    edg1.dat[j].add(ii);
                    }
                }
            e=1;
            }
        }

    // fill unused holes in points1
    for (e=1,i=0;e;)
        {
        e=0;
        // find last used point1 -> i0
        i0=-1; i1=-1;
        for (j=0;j<n1;j++,i++,(i==n1)?i=0:i=i) if (edg1.dat[i].num) i0=i; else if (i0>=0) break;
        // find next used point1 -> i1
        if (i0>=0) if (edg1.dat[i].num==0)
         for (j=0;j<n1;j++,i++,(i==n1)?i=0:i=i) if (edg1.dat[i].num){ i1=i; break; }
        if (i1>=0)
            {
            // find last used point0 joined to i0 -> j0
            j0=-1; jj0=-1; l0=0.0;
            i=i0+1; if (i>=n1) i=0; ii=ix1+i+i+i;
            for (j=0;j<edg1.dat[i0].num;j++)
                {
                jj=edg1.dat[i0].dat[j];
                vector_sub(p,pnt.dat+ii,pnt.dat+jj);
                l=vector_len2(p);
                if ((j0<0)||(l<l0)){ l0=l; j0=(jj-ix0)/3; jj0=jj; }
                } i0=i;
            // find next used point0 joined to i1 -> j1
            j1=-1; jj1=-1; l0=0.0;
            i=i1-1; if (i<0) i=n1-1; ii=ix1+i+i+i;
            for (j=0;j<edg1.dat[i1].num;j++)
                {
                jj=edg1.dat[i1].dat[j];
                vector_sub(p,pnt.dat+ii,pnt.dat+jj);
                l=vector_len2(p);
                if ((j1<0)||(l<l0)){ l0=l; j1=(jj-ix0)/3; jj1=jj; }
                } i1=i;
            // join i0..i1 <-> j0..j1
            di=i1-i0; if (di<0) di+=n1; // point1 to join
            dj=j1-j0; if (dj<0) dj+=n0; // point0 to join
            de=di; if (de<dj) de=dj;    // max(points0,point1)
            for (e=0;e<=de;e++)
                {
                i=i0+((e*di)/de); if (i>=n1) i-=n1; ii=ix1+i+i+i;
                j=j0+((e*di)/de); if (j>=n0) j-=n0; jj=ix0+j+j+j;
                for (k=0;k<edg1.dat[i].num;k++) // avoid duplicate edges
                 if (edg1.dat[i].dat[k]==jj)
                  { k=-1; break; }
                if (k>=0)
                    {
                    edg1.dat[i].add(jj);
                    edg0.dat[j].add(ii);
                    }
                }
            e=1;
            }
        }

    // find&connect singular connection lines (both endpoints are used just once)
    for (i=0;i<n0;i++)
     if (edg0.dat[i].num==1)    // point0 used once
        {
        jj=edg0.dat[i].dat[0];  // connected to
        j=(jj-ix1)/3;
        if (edg1.dat[j].num==1) // point1 used once
            {
            i0=i-1; if (i<  0) i+=n0;   // point0 neighbors
            i1=i+1; if (i>=n0) i-=n0;
            ii =ix0+i +i +i;
            ii0=ix0+i0+i0+i0;
            ii1=ix0+i1+i1+i1;
            if (edg1.dat[j].dat[0]!=ii0)    // avoid duplicate edges
                {
                edg1.dat[j].add(ii0);
                edg0.dat[i0].add(jj);
                }
            if (edg1.dat[j].dat[0]!=ii1)    // avoid duplicate edges
                {
                edg1.dat[j].add(ii1);
                edg0.dat[i1].add(jj);
                }
            }
        }

    // find singular poinst0 that form QUAD hole and triangulate it
    for (i=0;i<n0;i++)
     if (edg0.dat[i].num==1)    // point0 used once
        {
        jj=edg0.dat[i].dat[0];  // connected to
        j=(jj-ix1)/3;
        i0=i-1; if (i<  0) i+=n0;   // point0 neighbors
        i1=i+1; if (i>=n0) i-=n0;
        j0=j-1; if (j<  0) j+=n1;   // point1 neighbors
        j1=j+1; if (j>=n1) j-=n1;
        ii =ix0+i +i +i;
        ii0=ix0+i0+i0+i0;
        ii1=ix0+i1+i1+i1;
        jj0=ix1+j0+j0+j0;
        jj1=ix1+j1+j1+j1;
        for (k=0;k<edg1.dat[j].num;k++) // avoid duplicate edges
            {
            if (edg1.dat[j].dat[k]==ii0) i0=-1;
            if (edg1.dat[j].dat[k]==ii1) i1=-1;
            }
        if (i0>=0)
            {
            edg1.dat[j ].add(ii0);
            edg0.dat[i0].add(jj );
            }
        if (i1>=0)
            {
            edg1.dat[j ].add(ii1);
            edg0.dat[i1].add(jj );
            }
        }

    // extract merge triangles from edge0
    for (i0=0,i1=1;i0<n0;i0++,i1++,(i1>=n0)?i1=0:i1=i1)
        {
        ii0=ix0+i0+i0+i0;
        ii1=ix0+i1+i1+i1;
        // find point1 joined to both points0 i0,i1
        for (i=0;i<edg0.dat[i0].num;i++)
         for (j=0;j<edg0.dat[i1].num;j++)
          if (edg0.dat[i0].dat[i]==edg0.dat[i1].dat[j])
            {
            jj=edg0.dat[i0].dat[i];
            tri.add(ii0);
            tri.add(ii1);
            tri.add(jj);
            }
        }
    // extract merge triangles from edge1
    for (i0=0,i1=1;i0<n1;i0++,i1++,(i1>=n1)?i1=0:i1=i1)
        {
        ii0=ix1+i0+i0+i0;
        ii1=ix1+i1+i1+i1;
        // find point1 joined to both points0 i0,i1
        for (i=0;i<edg1.dat[i0].num;i++)
         for (j=0;j<edg1.dat[i1].num;j++)
          if (edg1.dat[i0].dat[i]==edg1.dat[i1].dat[j])
            {
            jj=edg1.dat[i0].dat[i];
            tri.add(ii0);
            tri.add(ii1);
            tri.add(jj);
            }
        }

    // extract merge edges
    for (i=ix0,ii=0;ii<n0;ii++,i+=3)
     for (j=0;j<edg0.dat[ii].num;j++)
        {
        lin.add(i);
        lin.add(edg0.dat[ii].dat[j]);
        }
    iy3=lin.num;

/*
    // [debug]
    AnsiString txt="";
    for (txt+="[edg0]\r\n",i=0;i<n0;i++,txt+="\r\n")
     for (txt+=AnsiString().sprintf("%2i:",i),j=0;j<edg0.dat[i].num;j++)
      txt+=AnsiString().sprintf("%2i ",(edg0.dat[i].dat[j]-ix1)/3);
    for (txt+="\r\n[edg1]\r\n",i=0;i<n1;i++,txt+="\r\n")
     for (txt+=AnsiString().sprintf("%2i:",i),j=0;j<edg1.dat[i].num;j++)
      txt+=AnsiString().sprintf("%2i ",(edg1.dat[i].dat[j]-ix0)/3);
    e=FileCreate("debug.txt");
    FileWrite(e,txt.c_str(),txt.Length());
    FileClose(e);
*/
    }
//---------------------------------------------------------------------------
void obj_draw()
    {
    int i,j;
    glLineWidth(2.0);
    glColor3f(0.1,0.1,0.1); glBegin(GL_LINES); for (i=0;(i<iy0)&&(i<lin.num);i++) glVertex3dv(pnt.dat+lin.dat[i]); glEnd(); // aux
    glColor3f(0.1,0.1,0.9); glBegin(GL_LINES); for (   ;(i<iy1)&&(i<lin.num);i++) glVertex3dv(pnt.dat+lin.dat[i]); glEnd(); // polygon 0
    glColor3f(0.9,0.1,0.1); glBegin(GL_LINES); for (   ;(i<iy2)&&(i<lin.num);i++) glVertex3dv(pnt.dat+lin.dat[i]); glEnd(); // polygon 1
    glColor3f(0.1,0.9,0.1); glBegin(GL_LINES); for (   ;(i<iy3)&&(i<lin.num);i++) glVertex3dv(pnt.dat+lin.dat[i]); glEnd(); // merge
    glColor3f(0.1,0.1,0.1); glBegin(GL_LINES); for (   ;         (i<lin.num);i++) glVertex3dv(pnt.dat+lin.dat[i]); glEnd(); // aux
    glLineWidth(1.0);

    glPointSize(5.0);
    glColor3f(0.9,0.9,0.1); glBegin(GL_POINTS); glVertex3dv(pnt.dat+ix0+0); glVertex3dv(pnt.dat+ix1+0); glEnd();    // 1st points
    glColor3f(0.1,0.9,0.9); glBegin(GL_POINTS); glVertex3dv(pnt.dat+ix0+3); glVertex3dv(pnt.dat+ix1+3); glEnd();    // 2nd points
    glColor3f(0.3,0.3,0.3); glBegin(GL_POINTS); for (i=0;i<pnt.num;i+=3) glVertex3dv(pnt.dat+i); glEnd();           // points
    glPointSize(1.0);

    glDisable(GL_CULL_FACE);
    glColor3f(0.2,0.2,0.2); glBegin(GL_TRIANGLES); for (i=0;i<tri.num;i++) glVertex3dv(pnt.dat+tri.dat[i]); glEnd();    // faces
    }
//---------------------------------------------------------------------------

I also use mine dynamic list template so:

List<double> xxx; is the same as double xxx[];
xxx.add(5); adds 5 to end of the list
xxx[7] access array element (safe)
xxx.dat[7] access array element (unsafe but fast direct access)
xxx.num is the actual used size of the array
xxx.reset() clears the array and set xxx.num=0
xxx.allocate(100) preallocate space for 100 items