Face Adjacency

[petrasvestartas]

Hi,

I would like to ask is it possible to get adjacent faces to one face? And Is it possible to get neighbour faces to one edge.

Geometry : 3 closed polylines hexagons meeting at edges.

I know that half edge data structure is about edges and each edge has a property of 1 adjacent face but not both.

First I thought that I could take previous half edges and check adjacency. But what happens below is that when I take previous or next half edge it circulates around the same polyline, so it is always same adjacent face.

Do the duplicated points are causing this problem and probably very tiny floating point error? Is it possible then to weld plankton mesh?

private void RunScript(List<Polyline> x, object y, ref object A)
  {

    //Construct plankton mesh from two touching polylines
    Plankton.PlanktonMesh pm = new PlanktonMesh();

    int count = 0;

    for(int i = 0; i < x.Count; i++){
      for(int j = 0; j < x[i].Count - 1; j++)
        pm.Vertices.Add(x[i][j]);
      pm.Faces.AddFace(Enumerable.Range(count, x[i].Count - 1));
      count += x[i].Count - 1;
    }

    //Adjacency  

    List<List<int>> adj = new List<List<int>>();
    List<List<int>> adj2 = new List<List<int>>();

    //Loop through faces
    for(int i = 0; i < pm.Faces.Count; i++){

      int[] e = pm.Faces.GetHalfedges(i); //Get face edges
      List<int> storeAdj = new List<int>();//Store adjacent faces
      List<int> storeAdj2 = new List<int>();//Store prev adjacent faces

      //Loop through each face edges
      for(int j = 0; j < e.Length; j++){

       // int adjA = pm.Halfedges[e[j]].AdjacentFace; //Adj face same thing
        int prev = pm.Halfedges[e[j]].PrevHalfedge;
        //int adjB = pm.Halfedges[prev].AdjacentFace; //Adj face same thing

        storeAdj.Add(e[j]);
        storeAdj2.Add(prev);
      }
      adj.Add(storeAdj);
      adj2.Add(storeAdj2);

    }

    A = adj;
    B = adj2;
  }

[petrasvestartas]

Found this code which solves my problem:

Probably welding polylines to avoid floating point error ir another thing. But as long as my polylines are clean it is works well.

  PlanktonMesh PMeshFromPolylines(List<Polyline> faces)
  {
    var pMesh = new PlanktonMesh();
    //add n-gon faces
    var verts = new List<Point3d>();
    for (int i = 0; i < faces.Count; i++)
    {
      var currFace = new List<int>();

      for (int j = 0; j < faces[i].Count - 1; j++)
      {
        var currPt = faces[i].PointAt(j);
        var id = verts.IndexOf(currPt);
        if (id < 0)
        {
          //push a vertex to list
          //push that index to current face
          pMesh.Vertices.Add(currPt.X, currPt.Y, currPt.Z);
          verts.Add(currPt);
          currFace.Add(pMesh.Vertices.Count - 1);
        }
        else
        {
          //push this index to current face
          currFace.Add(id);
        }
      }

      if (pMesh.Faces.AddFace(currFace) < 0) // AddFace returns -1 if the face couldn't be added
        pMesh.Faces.AddFace(Enumerable.Reverse(currFace)); // try adding the opposite face

    }

    return pMesh;
  }

[pearswj]

Hey @petrasvestartas,

Firstly, sorry for taking so long to respond to this one. Secondly, I updated your description and comment above to add proper syntax highlighting to the code, making it easier to read :)

I've had success using Starling to generate face-vertex data from a set of close poly lines (see #16). Comparing Point3d in this way is, as you say, prone to error. It's much better to compare with a tolerance (perhaps with Point3d.EpsilonEquals()).

I've also run into the face-winding problem and have in the past used the same technique that you're using: if the face cannot be added, try adding it with the vertex indices reversed. The problem is that if you add a face that is disjoint from the rest of the mesh, it has no way of knowing what the correct winding should be. Later, your code might try to add a face that joins two faces with different winding directions... which will fail... You might never encounter this situation, but nevertheless, some food for thought!

[pearswj]

Actually, before I close this issue, did you manage to solve your original problem of finding faces adjacent to a face?

Perhaps this (untested) code snippet could help...

var faces = new List<int>();
foreach (int j in pmesh.Faces.GetHalfedges(i))
{
  int pair = pmesh.Halfedges.GetPairHalfedge(j);
  int f = pmesh.Halfedges[pair].AdjacentFace;
  faces.Add(f);
}

or if you prefer arrays...

int[] halfedges = pmesh.Faces.GetHalfedges(i);
var faces = new int[halfedges.Length];
for (int j = 0; j < halfedges.Length; j++)
{
  int pair = pmesh.Halfedges.GetPairHalfedge(halfedges[j]);
  int f = pmesh.Halfedges[pair].AdjacentFace;
  faces[j] = f;
}

[webotote]

Hi @petrasvestartas and @pearswj ,

I am doing my first steps with PlanktonMesh. I am trying to figure out how to find the adjacent faceCenters of a given vertex(or faceCenter). My try so far, frankensteining together from what I found above:

 PlanktonMesh pMesh = iMesh.ToPlanktonMesh();

    var faces = new List<int>();

    var verts = new List<Point3d>();

    for (int i = 0; i < 10; i++)//pMesh.Faces.Count
    {
      var currFace = new List<int>();

      foreach (int j in pMesh.Faces.GetHalfedges(i))
      {
        var currPt = pMesh.Faces.GetFaceCenter(j).ToPoint3d();
        var id = verts.IndexOf(currPt);

        int pair = pMesh.Halfedges.GetPairHalfedge(j);
        int f = pMesh.Halfedges[pair].AdjacentFace;
        faces.Add(f);
      }
    }
    A = faces;

My future aim, after understand more about the halfEdge logic would be to create a meshDual.

Maybe you could help me with some hints? Would be really appreciated.

Best Nico