Hi,

I am exploring mesh data structures and came across the directed edge data structure. I have managed to get the data structure working but I am looking to detect something like a hole in the mesh. I am trying to find a boundary edge and then follow the hole to find all edges forming this hole. I tried looking for some examples and explanation lectures on boundary edge detection and following the hole but I was not able to find much.

I was wondering if someone could help me understand how you implement something like this?

void Mesh::FindBoundaryHole()
{
    std::vector<int> boundary_edges;

    for(uint32_t edge = 0; edge < vertices.size(); edge++)
    {
        int startEdge = FirstDirectedEdge[edge]; // start of the edge
        int currentEdge = startEdge;
        do
        {     
            if(otherHalf[currentEdge] == -1)
            {
                boundary_edges.push_back(otherHalf[currentEdge]);
                currentEdge = otherHalf[next(currentEdge)];
            } else 
            {
                currentEdge = next(otherHalf[currentEdge]);
            }

        } while (currentEdge != startEdge);
    }

}

I'm using the half edge data structure, but code looks similar. To find a boundary cycle i can just follow the next pointer until i get back to the initial open edge. (following the next pointer either describes a polygon or a boundary loop, which in many aspects is the same thing)

			std::vector<bool> processed (mm.GetEdgeCount(), false);
			for (int h=0; h<mm.GetEdgeCount(); h++)
			{
				int poly = mm.GetEdgePoly(h);
				if (poly != -1) continue; // skip if edge not open

				if (processed[h]) continue; // skip if edge was already part of a formerly found loop

				int pair = mm.GetEdgePair(h);
				if (pair == -1) continue; // any edge must have a pair, so this is actually an edg that has been disconnected from former mesh editing, but is still in the mesh

				std::vector<int> loop;
				int lH = h;
				do
				{
					assert (mm.GetEdgePoly(lH) != -1); // if the intial edge is open, the entire loop must be open. Otherwise we have already corrupted the data structure with some mesh editing 
					loop.push_back(lH);
					processed[lH] = true;
					lH = mm.GetEdgeNext(lH);
				} while (lH != h);
				
				// to close the hole i create a new polygon from the loop, triangulate it, and do voronoi edgeflips on the internal edges for mesh quality.
				// if we had a hole we're done, but if we had an overlap, we now have folds / pockets, and i'm currently working on removing them...
			}

If you think mesh editing is frustrating an difficult, you are on the right track. It's just much worse than that.
If you think it's interesting and fun, you have been warned. :D

@joej Thanks for the reply and Merry Christmas! I'm finding it difficult to understand the code you provided, it feels quite different. Currently I am doing the following:

for(int edge = 0; edge < vertices.size(); edge++)
{
    int startEdge = FirstDirectedEdge[edge]; // start edge
    int currentEdge = startEdge;
    do
    {
        if(otherHalf[currentEdge] == -1)
        {
            boundary_edges.push_back(currentEdge);
            currentEdge = next(currentEdge);
            while(otherHalf[currentEdge] != -1)
            {
                currentEdge = otherHalf[currentEdge];
                currentEdge = next(currentEdge);
            }
        } else
        {
            currentEdge = next(currentEdge);
        }

    } while (currentEdge != startEdge);
}

This seems to work with a basic triangle but with a cube with missing triangles, it seems to detect some but miss out on some others and I am not sure why.

snoken said:
I'm finding it difficult to understand the code you provided, it feels quite different.

I assume differences between data structures are pretty small. Here is my related code to compare better:

	class HEMesh
	{
	public:

		typedef int32_t Index;

		// edges
		struct HalfEdge
		{
			Index pair;
			Index next;
			Index poly;
			Index vertex;

			HalfEdge ()
			{
				pair = -1;
				next = -1;
				poly = -1;
				vertex = -1;
			}

		};
		std::vector<HalfEdge> mEdge;

		// vertices
		std::vector<Index> mVertexEdge;
		std::vector<vec> mVertexPosition;
		
		// polys
		std::vector<Index> mPolyEdge;

	};

It's a directed graph too, but it always goes both ways. The pair of an half edge goes the other direction.
Following the next pointer always gives clockwise ordered edges to form a polygon or boundary.
I guess it's the same to you.

I assume your problem is here:

for(int edge = 0; edge < vertices.size(); edge++)
{
    int startEdge = FirstDirectedEdge[edge]; // start edge
    
    

If i would do it this way, i would miss many edges.
A vertex points to only one edge out of many, so you can't iterate all edges this way i guess.
That's why i iterate all edges directly and do not use vertices in my code.

I also use a processed flag to prevent redundant work. Otherwise i would find (and process) a boundary made of 10 edges 10 times.

Another option could be that you have corrupted the data structure when deleting some triangles from the cube.
A key problem with mesh editing is to prevent such corruption. For me the basic functions are edge collapse and edge rotation. My code checks if such operations can be done without messing the mesh up.
If we get this wrong, we'll likely get an infinite loop some time later, when we try to traverse the corrupted data. Unfortunately the guarantee for correctness isn't trivial, but rather the sum of lots of non obvious special cases.
But likely that's not yet your problem.

@JoeJ Thanks for getting back.

I think I have it working, seems to correctly find the boundary edges. Could you confirm if this is the right approach and if so, how could I improve it to speed it up?

for(int edge = 0; edge < triangles.size(); edge++)
{
    int startEdge = edge; 
    int currentEdge = startEdge;
    do
    {
        if(otherHalf[currentEdge] == -1)
        {
            boundary_edges.push_back(currentEdge);
            currentEdge = next(currentEdge);
        } else
        {
            currentEdge = next(currentEdge);
        }   

    } while (currentEdge != startEdge);
}

Here triangles is an array storing index to face vertices. E.g.

triangles:

0, 1, 2 → forms a triangle face.

The mesh is hard to see and tell if it has a hole so this is how it looks in blender.

snoken said:
Could you confirm if this is the right approach and if so, how could I improve it to speed it up?

Not really. I see you use triangle index lists, which hints your data structure is likely very different. With half edge there is no need for any index lists, you get all of that only by traversing the data structure.

But i still have the same doubts here:

for(int edge = 0; edge < triangles.size(); edge++)
{
    int startEdge = edge; 

Why do you iterate over triangle count to process edges? And why do you think there's guarantee this way you will process all edges?

And what's your goal? I assumed you want to close holes, but if you only want to visualize open edges, there is no need to from a boundary loop or cycle.

@undefined Thanks for the reply! The goal is to do texture parameterisation, the boundary edges are needed as you need to get their lengths.