Lawrence D’Oliveiro
F + V = E + 2

Herewith some musings on mesh modelling, specifically on mathematical constraints that must apply.

First of all, let me say I’m not really an artist, I’m more a techie programmer type with some grounding in science and maths. I’ve been reading lots of tutorials and discussions on the topology of modelling, whether to make all your meshes out of quads and avoid triangles or not, and this business about poles and what they’re for.

(To recap for those unfamiliar with the concept, in a mesh made entirely out of quads, a pole is a vertex with some number of edges other than 4 connected to it.)

Anyway, I don’t think I’ve seen this pointed out in any of the tutorials yet, but it is mathematically impossible to model any quads-only mesh that is topologically equivalent to a sphere (i.e. any mesh that encloses a single connected volume without holes in it) without having poles somewhere. This follows from Euler’s formula that relates the number of faces (F), vertices (V) and edges (E) on the surface; for a sphere, the formula is

F + V = E + 2

To see how this applies, imagine that you do have a sphere-equivalent mesh that is covered entirely with quads without poles. This means that

  1. Every vertex is connected to 4 edges
  2. Every edge is shared between 2 faces
  3. Every face has 4 edges.
If you look at some part of this mesh, it might look like this:

Consider the coloured portion in the middle, which represents a “tile” that is replicated to make up the entire mesh: this consists of one vertex (the blue spot), two edges (the green lines) and one face (the yellow square). If you replicate this horizontally and vertically across the adjacent squares, you will see that the tiles match up to exactly fill in the right number of faces, vertices and edges, without overlaps or gaps. If you do this a total of N times to make up the complete mesh, then the following equations hold:

F = N
V = N
E = 2N

But if you try substituting the above N-based values into F + V = E + 2, you get

N + N = 2N + 2

which doesn’t work, because it means that 0 = 2. In other words, the assumption that it is possible to tile a sphere with quads pole-free leads to a contradiction, therefore the assumption is false. (Proof by reductio ad absurdum.)

So, you can’t have a sphere-equivalent mesh without poles. But what sort of poles must you have?

What is the simplest sphere-equivalent quad-based mesh? Answer: a cube. Start up Blender, and contemplate the default cube (or insert one if you’ve taken it out:)) it has F = 6 faces, V = 8 vertices and E = 12 edges. Plugging these back into the Euler formula, F + V = 14, and E + 2 = 14, so the equality holds, no big surprise there. But note also that every vertex has 3 edges connected to it: all eight vertices are 3-poles.

Can you make an even simpler quad-based mesh? Try it, and you will find that quad faces turn into triangles, or other weird things happen. So no, the cube really is the simplest.

What about making more complicated meshes starting from this? One obvious thing is to apply Blender’s Subdivision Surface modifier; do this enough times, and you start to get a pretty good approximation to a sphere:

Notice that, no matter how many vertices, edges and faces this adds to the mesh, there are always those eight 3-poles (highlighted), and no other poles are introduced.

How else can you make changes to the topology of the mesh, without leaving holes open or otherwise changing the sphere-equivalence topology? Well, you could join two vertices into one, or split one vertex into two. You could do this by merging two vertices that are connected by an edge:

but as you can see, this introduces triangles and 6-poles into the mesh, so perhaps we’d better avoid that.

The only other way I can think of to merge two vertices is do it to two that are diagonally opposite corners of a face. Suppose we try it with two non-pole vertices:

So again we get a 6-pole, which is probably best avoided.

But notice also in this example that merging two opposing vertices in this way not only reduces the number of vertices by one, it also makes one face disappear. And the four edges of the face that disappeared become two edges connected to the new merged vertex—a net loss of two edges. Going back to the Euler formula, F decreases by 1, V decreases by 1, therefore F + V decreases by 2. On the other side, E also decreases by 2, therefore the Euler relation F + V = E + 2 is still just as true afterwards as it was before—it is an invariant of this particular operation.

Suppose the number of edges connected to the first vertex being merged is E1, and the number connected to the second vertex is E2. Then the number of edges connected to the merged vertex is E1 + E2 - 2. So if you were to merge a 3-pole and a non-pole vertex, the resulting vertex would have 3 + 4 - 2 = 5 edges—it would be a 5-pole:

So, can you turn a 3-pole into a 5-pole this way? However, that’s not all that happens—if you look closely, you can see it creates two new 3-poles connected to the 5-pole as well. And going the other way, if you have a 5-pole adjacent to two 3-poles, you can rip (the “V” key in Blender) the 5-pole in such a way that you can fill in the gap with a new quad face, getting rid of one 5-pole and one 3-pole, leaving just one 3-pole.

I won’t bother to prove it mathematically, but this is what seems to happen with a sphere-equivalent quad-based mesh: you always have a minimum of eight 3-poles (and no 5-poles), and (ignoring the possibilities for higher-order poles) you can add and remove 3-poles and 5-poles, but always in pairs: one 3-pole must appear or disappear along with one 5-pole. Or, to put it mathematically, if V3 is the number of vertices which are 3-poles and V5 is the number of vertices which are 5-poles:

V3 - V5 = 8

Blender offers another way to create spherical meshes containing quads, and that is by adding a “UV Sphere” primitve. Such a mesh has just two poles, one each at the, ahem, north and south poles of the sphere (is this where the term “pole” originated?). So does this violate the rule I stated above that such a mesh must always have at least 8 poles?

Let’s try creating such a mesh. Let’s give it just 5 segments, because that governs the order of the poles, and I wdon’t want anything more than a 5-pole:

Yes, there really are just 2 poles, but unfortunately there are a bunch of triangular faces as well. Luckily, we can get rid of these by applying at least one level of our good old Subdivision Surface modifier:

and the triangles have disappeared. But in their place, we have five 3-poles surrounding each 5-pole—in other words, we have a total of ten 3-poles to go with our two 5-poles. Thus the above formula, V3 - V5 = 8, still holds.

What happens if you create the UV sphere with fewer than 5 segments and then subsurf? With 4 segments, the north and south “poles” are no longer poles, since they are each just vertices with 4 connected edges, but each one has 4 adjacent 3-poles, for a total of 8. With 3 segments, the north and south poles are 3-poles, each with 3 other 3-poles connected, again for a total of 8.

So the V3 - V5. = 8 formula still holds in each case.

So what about non-sphere-equivalent meshes? It turns out, a mesh with one hole (a torus) can be constructed out of quads without any poles at all. You can still add (and remove) poles in pairs, as with a sphere mesh, so for a torus-equivalent the equation.relating the numbers of 3-poles and 5-poles (in the absence of any higher-order ones) becomes

V3 - V5 = 0

It is also interesting that, for such a topology, the Euler relationship F + V = E + 2 no longer holds; in fact the relationship becomes F + V = E.

In fact, we can replace the Euler equation with the question:“what is the value of the formula F + V - E?” For a sphere-equivalent mesh (no holes), the answer is 2, for a torus-equivalent one (one hole), the answer is 0. We might call this number the “Euler characteristic” of the mesh.

So what if the object has two holes? Here’s one I made earlier, by duplicating a simple torus mesh, deleting one quad face from each, and joining the vertices that the deleted faces were on:

For such an object, the value of F + V - E is -2. And notice that this object has eight 5-poles (four visible at the front) and no 3-poles, so the 3-pole-versus-5-pole relationship becomes

V3 - V5 = - 8

See a pattern here? There seems in fact to be a general formula:

V3 - V5 = 4(F + V - E)
  1. cybermancy reblogged this from ldo17
  2. ldo17 posted this