Mesh Edge Construction

Summary

In this post I will present three equivalent algorithms to compute the edges of a polygonal mesh. The algorithms are subsequent optimization steps to produce the exact same result with progressively increased efficiency. In the first part of this text, I will describe the typical representation of a mesh topology, distinguish between different concepts of edges. To better define the subject, picture the wireframe of a polygonal mesh. Assuming there is no overlapping geometry in the scene, if you’d have to draw each single segment once, you would be drawing edges. That would be different than drawing polygons outline, because in drawing adjacent polygons you would end up drawing some, if not most of the segments twice. What this post is not This post is not about topological acceleration structure, like half-edges, winged-mesh, corner table, vertex-vertex, or similar. I borrow some of the terms though. I will refer to half-edges throughout the text, to distinguish from unique edges, I describe the input mesh in the very common face-vertex mesh format. Introduction Most of 3D graphics revolves around polygons in one way or another. The cool kids today work with distance fields and Gaussian splats. But let’s forget about that, and NURBS and parametric surfaces for a moment. Chances are, if you’re working on a graphics project, you’re dealing with polygonal meshes. The standard way to describe a mesh is through a set of points connected in a specific winding order, often referred to as the topology. The simplest possible representation is called triangle soup, where a set of point triplets is defined, with each triplet representing the vertices of a triangle. That’s it. It’s the simplest but also the most wasteful and impractical way to describe a mesh, so let’s skip a few history pages (forget about fans and strips). The next and more useful way to describe a mesh is via a set of points and indices referencing those points. Let’s define a square: float3 points[] = {(0,...