Get border edges of mesh - in winding order

Question

I have a triangulated mesh. Assume it looks like an bumpy surface. I want to be able to find all edges that fall on the surrounding border of the mesh. (forget about inner vertices)

I know I have to find edges that are only connected to one triangle, and collect all these together and that is the answer. But I want to be sure that the vertices of these edges are ordered clockwise around the shape.

I want to do this because I would like to get a polygon line around the outside of mesh.

I hope this is clear enough to understand. In a sense i am trying to "De-Triangulate" the mesh. ha! if there is such a term.

Norbertonorbie

ok, Imagine if my surface had a big dent in the side of it reaching into the inner part of it's shape, but with a thin neck to it - . Would the convex hull follow that dent around? or would it skip right over it because it is only considering the maximum extents of the shape? Hard to explain without a picture. – Norbertonorbie

Answer 1

Boundary edges are only referenced by a single triangle in the mesh, so to find them you need to scan through all triangles in the mesh and take the edges with a single reference count. You can do this efficiently (in O(N)) by making use of a hash table.

To convert the edge set to an ordered polygon loop you can use a traversal method:

1. Pick any unvisited edge segment [v_start,v_next] and add these vertices to the polygon loop.
2. Find the unvisited edge segment [v_i,v_j] that has either v_i = v_next or v_j = v_next and add the other vertex (the one not equal to v_next) to the polygon loop. Reset v_next as this newly added vertex, mark the edge as visited and continue from 2.
3. Traversal is done when we get back to v_start.

The traversal will give a polygon loop that could have either clock-wise or counter-clock-wise ordering. A consistent ordering can be established by considering the signed area of the polygon. If the traversal results in the wrong orientation you simply need to reverse the order of the polygon loop vertices.

Maximilian

Hi Darren, I followed the algorithm you suggested above. And it worked first time! Thank you. It is completely logical how it works so thanks for the precise description you gave me. I have already found the edges that exist in one triangle only on the mesh. So all i needed was the traversal algorithm to order the vertices correctly. – Norbertonorbie

How would you efficiently make a hash that collides? i.e. an edges hash should be the same even if their start and end are flipped. – Plumcot

@TJHeuvel: one way is to call the hash function on a copy of the edge in which the indices are first sorted. – Maximilian

Answer 2

Well as the saying goes - get it working - then get it working better. I noticed on my above example it assumes all the edges in the edges array do in fact link up in a nice border. This may not be the case in the real world (as I have discovered from my input files i am using!) In fact some of my input files actually have many polygons and all need borders detected. I also wanted to make sure the winding order is correct. So I have fixed that up as well. see below. (Feel I am making headway at last!)

    private static List<int> OrganizeEdges(List<int> edges, List<Point> positions)
    {
        var visited = new Dictionary<int, bool>();
        var edgeList = new List<int>();
        var resultList = new List<int>();
        var nextIndex = -1;
        while (resultList.Count < edges.Count)
        {
            if (nextIndex < 0)
            {
                for (int i = 0; i < edges.Count; i += 2)
                {
                    if (!visited.ContainsKey(i))
                    {
                        nextIndex = edges[i];
                        break;
                    }
                }
            }

            for (int i = 0; i < edges.Count; i += 2)
            {
                if (visited.ContainsKey(i))
                    continue;

                int j = i + 1;
                int k = -1;
                if (edges[i] == nextIndex)
                    k = j;
                else if (edges[j] == nextIndex)
                    k = i;

                if (k >= 0)
                {
                    var edge = edges[k];
                    visited[i] = true;
                    edgeList.Add(nextIndex);
                    edgeList.Add(edge);
                    nextIndex = edge;
                    i = 0;
                }
            }

            // calculate winding order - then add to final result.
            var borderPoints = new List<Point>();
            edgeList.ForEach(ei => borderPoints.Add(positions[ei]));
            var winding = CalculateWindingOrder(borderPoints);
            if (winding > 0)
                edgeList.Reverse();

            resultList.AddRange(edgeList);
            edgeList = new List<int>();
            nextIndex = -1;
        }

        return resultList;
    }




    /// <summary>
    /// returns 1 for CW, -1 for CCW, 0 for unknown.
    /// </summary>
    public static int CalculateWindingOrder(IList<Point> points)
    {
        // the sign of the 'area' of the polygon is all we are interested in.
        var area = CalculateSignedArea(points);
        if (area < 0.0)
            return 1;
        else if (area > 0.0)
            return - 1;        
        return 0; // error condition - not even verts to calculate, non-simple poly, etc.
    }

    public static double CalculateSignedArea(IList<Point> points)
    {
        double area = 0.0;
        for (int i = 0; i < points.Count; i++)
        {
            int j = (i + 1) % points.Count;
            area += points[i].X * points[j].Y;
            area -= points[i].Y * points[j].X;
        }
        area /= 2.0f;

        return area;
    }

Norbertonorbie

Answer 3

Traversal Code (not efficient - needs to be tidied up, will get to that at some point) Please Note: I store each segment in the chain as 2 indices - rather than 1 as suggested by Darren. This is purely for my own implementation / rendering needs.

        // okay now lets sort the segments so that they make a chain.

        var sorted = new List<int>();
        var visited = new Dictionary<int, bool>();

        var startIndex = edges[0];
        var nextIndex = edges[1];

        sorted.Add(startIndex);
        sorted.Add(nextIndex);

        visited[0] = true;
        visited[1] = true;

        while (nextIndex != startIndex)
        {
            for (int i = 0; i < edges.Count - 1; i += 2)
            {
                var j = i + 1;
                if (visited.ContainsKey(i) || visited.ContainsKey(j))
                    continue;

                var iIndex = edges[i];
                var jIndex = edges[j];

                if (iIndex == nextIndex)
                {
                    sorted.Add(nextIndex);
                    sorted.Add(jIndex);
                    nextIndex = jIndex;
                    visited[j] = true;
                    break;
                }
                else if (jIndex == nextIndex)
                {
                    sorted.Add(nextIndex);
                    sorted.Add(iIndex);
                    nextIndex = iIndex;
                    visited[i] = true;
                    break;
                }
            }
        }

        return sorted;

Norbertonorbie

Answer 4

The answer to your question depends actually on how triangular mesh is represented in memory. If you use Half-edge data structure, then the algorithm is extremely simple, since everything was already done during Half-edge data structure construction.

1. Start from any boundary half-edge HE_edge* edge0 (it can be found by linear search over all half-edges as the first edge without valid face). Set the current half-edge HE_edge* edge = edge0.
2. Output the destination edge->vert of the current edge.
3. The next edge in clockwise order around the shape (and counter-clockwise order around the surrounding "hole") will be edge->next.
4. Stop when you reach edge0.

To efficiently enumerate the boundary edges in the opposite (counter-clockwise order) the data structure needs to have prev data field, which many existing implementations of Half-edge data structure do provide in addition to next, e.g. MeshLib

Alleman