So Boston is being remarkably stupid, and New York is being remarkably stupid, and I just can’t bring myself to give a shit. These places are the centroid of grass-eater activity in the United States — the centre of grass, if you will — so the fact that they’re freaking out over inanimate objects is not only unsurprising, but entirely expected.
Instead, I’m going to talk about graphics programming. To wit: how do you build a data structure to store triangle meshes?
The first thing that comes to mind may be something along the lines of:
typedef struct {
float x, y, z;
} vertex;
typedef struct {
vertex a, b, c;
} triangle;
typedef struct {
size_t n_tris;
triangle* tris;
} mesh;
This is basically a triangle soup — a huge wad of independent triangles. But that’s not really such a hot idea.
For one thing, each vertex can appear on any number of triangles. By representing a mesh as a blob of independent triangles, you’re duplicating vertices for no good reason. This doesn’t just cost you storage space — it also makes your life miserable when you’re trying to do stuff to vertices (like, say, animate your mesh). Rather than modify each vertex once, you have to track down every triangle containing that vertex and modify the copies.
This is, as they say, a pain in the ass.
Furthermore, the mesh file from which you’re getting your data probably stores it in a different — more sensible — format: namely, a list of vertices, followed by a list of faces. Each face is defined by indexes into the vertex list, not by explicit vertices. This is what we call a vertex-face list mesh representation.
By amazing coincidence, vertex-face lists are also quite convenient to draw quickly with OpenGL (and, I presume, DirectX).
Let’s do that instead:
typedef struct {
float x, y, z;
} vertex;
typedef struct {
size_t a, b, c; /* indices into vertex list */
} triangle;
typedef struct {
size_t n_verts;
vertex* verts;
size_t n_tris;
triangle* tris;
} mesh;
/* ... */
void
draw_mesh(mesh* m)
{
glVertexPointer(3, GL_FLOAT, 0, m->verts);
glDrawElements(GL_TRIANGLES, 3*m->n_tris, GL_UNSIGNED_INT, m->tris);
}
There’s a little bit of subtlety going on in that draw_mesh call: I’m assuming that arrays of vertex and triangle structs will behave like arrays of floats and size_ts. This is generally true for C code, but probably false for C++ if you add any extra crap to vertex and triangle (for instance, if you inherit from one of them, thus forcing C++ to give you a vtable). It may also break on 64-bit machines if they insist on lining up structs on 8-byte boundaries.
Note that modifying vertices is now straightforward: change the appropriate vertex, and all of its adjacent triangles reflect that change. In fact, it’s now easy to store (say) animated Quake 2 character models: you keep one vertex list for each keyframe, interpolate between them as you please, and render the interpolated frame using the single triangle list.
This brings up a matter of terminology. When we describe a mesh, we need to describe its geometry (the position in space of its elements) and its connectivity (which elements are adjacent to which). In this case, the vertex list describes the mesh’s geometry, and the face list describes its connectivity. In theory, all we need to do stuff to this mesh are these two chunks of data.
However, look back at our first attempt. We can also (in theory) do everything we need with a triangle soup — it’s just more annoying. Vertex-face lists are more convenient structures to manipulate than triangle soups, but they also have their annoyances — for instance, any operation on a mesh’s edges is a pain in the ass on a vertex-face list. However, if all you need to do to a mesh is draw it (really fast, even) and maybe change its geometry, the vertex-face list is just the ticket.