Building an Edge List for an Arbitrary MeshThe 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.
The An edge list is useful for many geometric algorithms in computer graphics. In particular, an edge list is necessary for stencil shadows. 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. This allows us to quickly // find an edge in the second pass whose higher-numbered vertex index is 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); } How to cite this articleLengyel, Eric. “Building an Edge List for an Arbitrary Mesh”. Terathon Software 3D Graphics Library, 2005. http://www.terathon.com/code/edges.html |