Quickly building an edge list for an arbitrary mesh

The following code builds a list of edges for an arbitrary triangle mesh and has O(n) running time in the number of triangles n in the mesh. This is a high-powered version of the simpler snippet that was previously posted. This code came from http://www.terathon.com/code/edges.html.

The edgeArray parameter must point to a previously allocated array of Edge structures large enough to hold all of the mesh's edges.

struct Edge
{
    unsigned short      vertexIndex[2];
    unsigned short      triangleIndex[2];
};


struct Triangle
{
    unsigned short      index[3];
};


long BuildEdges(long vertexCount, long triangleCount,
                const Triangle *triangleArray, Edge *edgeArray)
{
    long maxEdgeCount = triangleCount * 3;
    unsigned short *firstEdge = new unsigned short[vertexCount + maxEdgeCount];
    unsigned short *nextEdge = firstEdge + vertexCount;
    
    for (long a = 0; a < vertexCount; a++) firstEdge[a] = 0xFFFF;
    
    // First pass over all triangles. This finds all the edges satisfying the
    // condition that the first vertex index is less than the second vertex index
    // when the direction from the first vertex to the second vertex represents
    // a counterclockwise winding around the triangle to which the edge belongs.
    // For each edge found, the edge index is stored in a linked list of edges
    // belonging to the lower-numbered vertex index <I>i</I>. This allows us to quickly
    // find an edge in the second pass whose higher-numbered vertex index is <I>i</I>.
    
    long edgeCount = 0;
    const Triangle *triangle = triangleArray;
    for (long a = 0; a < triangleCount; a++)
    {
        long i1 = triangle->index[2];
        for (long b = 0; b < 3; b++)
        {
            long i2 = triangle->index[b];
            if (i1 < i2)
            {
                Edge *edge = &edgeArray[edgeCount];
                
                edge->vertexIndex[0] = (unsigned short) i1;
                edge->vertexIndex[1] = (unsigned short) i2;
                edge->faceIndex[0] = (unsigned short) a;
                edge->faceIndex[1] = (unsigned short) a;
                
                long edgeIndex = firstEdge[i1];
                if (edgeIndex == 0xFFFF)
                {
                    firstEdge[i1] = edgeCount;
                }
                else
                {
                    for (;;)
                    {
                        long index = nextEdge[edgeIndex];
                        if (index == 0xFFFF)
                        {
                            nextEdge[edgeIndex] = edgeCount;
                            break;
                        }
                        
                        edgeIndex = index;
                    }
                }
                
                nextEdge[edgeCount] = 0xFFFF;
                edgeCount++;
            }
            
            i1 = i2;
        }
        
        triangle++;
    }
    
    // Second pass over all triangles. This finds all the edges satisfying the
    // condition that the first vertex index is greater than the second vertex index
    // when the direction from the first vertex to the second vertex represents
    // a counterclockwise winding around the triangle to which the edge belongs.
    // For each of these edges, the same edge should have already been found in
    // the first pass for a different triangle. So we search the list of edges
    // for the higher-numbered vertex index for the matching edge and fill in the
    // second triangle index. The maximum number of comparisons in this search for
    // any vertex is the number of edges having that vertex as an endpoint.
    
    triangle = triangleArray;
    for (long a = 0; a < triangleCount; a++)
    {
        long i1 = triangle->index[2];
        for (long b = 0; b < 3; b++)
        {
            long i2 = triangle->index[b];
            if (i1 > i2)
            {
                for (long edgeIndex = firstEdge[i2]; edgeIndex != 0xFFFF; edgeIndex = nextEdge[edgeIndex])
                {
                    Edge *edge = &edgeArray[edgeIndex];
                    if ((edge->vertexIndex[1] == i1) && (edge->faceIndex[0] == edge->faceIndex[1]))
                    {
                        edge->faceIndex[1] = (unsigned short) a;
                        break;
                    }
                }
            }
            
            i1 = i2;
        }
        
        triangle++;
    }
    
    delete[] firstEdge;
    return (edgeCount);
}

Nice. I must say I'm very sceptical about the assumption:
..For each of these edges, the same edge should have already been found in the first pass for a different triangle ..

but it is easily fixed (even though the models have no border you sometimes get meshes with border since the model might use several materials/shaders).
I will not comment on the theoretical O(n^2) worst case, since most meshes probably have low valency at each vertex anyway.

I might put up my O(NlogN) edge finder (which is somewhat nicer since it also checks that we have a 2-manifold for free, and fast since it's linear except for a sort), but I'm lazy and hate computers so I probably won't.

Edit: Urgh, any edge finder can assure we have a 2-manifold for free... Time to go to bed..

-Si

Originally Posted by SigKILL

Nice. I must say I'm very sceptical about the assumption:
..For each of these edges, the same edge should have already been found in the first pass for a different triangle ..

Ah, yes. I should probably have said that in a closed 2-manifold mesh, this is true.