Various solid wireframe modes in Maya, Mesh Lab, and our WebGL Model Viewer (from left to right).
About solid wireframes
In order to spot problems in a mesh it is sometimes useful to look at the shape of its triangles or polygons. That’s what wireframe modes are for. But if there are too many lines it can be confusing to look at. That’s why it’s also useful in 3D CAD software to have a solid wireframe mode, that is, a mode where you only see front lines, and the rest are occluded by the triangles of the solid mesh. See the figure on top.
Because I use my WebGL Model Viewer to preview models quite often, I thought it would be a good idea to add a solid wireframe mode to it. Instead of attempting to draw actual line primitives, I thought it would be more fun to draw the lines directly from the triangles in a pixel shader. And that’s what I will describe in this blog post.
Barycentric coordinates
There’s a very easy way to know whether a point inside a triangle is at the edge of that triangle, i.e. the line we want to draw, or not. If we convert the coordinates of the point to barycentric coordinates, the point will be expressed as a 3D tuple (α, β, γ), where the 3 vertices of the triangle correspond to coordinates (1, 0, 0), (0, 1, 0), and (0, 0, 1). Any point where one of the coordinates is zero lies on one of the edges of the triangle. See illustration below.
In barycentric coordinates, one of the coordinates is zero for points in an edge
If we label each vertex with its equivalent barycentric coordinate, then the rasteriser can do the dirty work of computing the exact (α, β, γ) coordinates for every single pixel inside the triangle. Then, to draw white lines we can simply paint white pixels where one of the coordinates is zero, and paint black otherwise.
That works for a single triangle, but what happens when triangles share one or more vertices?
Graph colouring
In the triangle strip of the illustration below we need to assign barycentric coordinates in a way such that not two adjacent vertices share the same coordinate label. This problem is known as graph colouring in Graph Theory. The 3 barycentric at the vertices can be seen as 3 distinct colours, and then the question we want to answer is:
can we colour the graph (the mesh) with just 3 colours?
Barycentric coordinates on a triangle strip
Unfortunately the general answer to this question is NO. So, spoilers ahead, this shader I implemented doesn’t work for all meshes. But it turns out that many meshes are indeed 3-colourable. Let’s not get too deep into graph theory, but let’s check some examples instead.
Planar graphs are 4-colourable
The Four Colour Theorem states that a planar graph can be painted with no more than 4 colours. The proof of that is quite complicated, so let us just believe the result. However, it is NP-complete in complexity to decide whether an arbitrary planar map can be coloured with just three colours.
Moreover, 3D meshes aren’t planar graphs in general. A graph is planar if you can draw it on a plane without any 2 edges intersecting. I think this is related to the UV-unwrapping problem: if the graph is planar, you can unwrap the texture coordinates (UVs) of a mesh continuously on a plane, without having to break the UVs in pieces. Note that the opposite may not be true. For instance, in the examples below the cube isn’t planar, because no matter how we draw it, there will always be edges that cross. However, the UVs can be unwrapped on a plane, and it can be coloured with only 2 colours. On the other hand, the tetrahedron may seem not planar either, but if you draw it from above, its edges do not cross. So it’s planar, but it needs the maximum number of colours of a planar graph to be painted, 4.
The cube isn’t planar, but it’s 2-colorable. The tetrahedron is planar but 4-colorable.
Open quad strips are 2-colourable
Quads are used often for modelling. An open quad strip, as illustrated below, is 2-colourable. But quads are rarely supported by GPUs, so usually the quads need to be triangulated before rendering. By adding that extra edge, the new triangle strip becomes 3-colourable.
A 2-colourable quad strip, and a 3-colourable triangle strip
Quad strip loops are 3-colourable
If the quad strip “loops”, that is, if we close the strip so the mesh has a hole, we may need an extra colour to paint it. See below. If we triangulate that, we will need an extra colour, making the triangle strip loop 4-colourable.
A 3-colourable quad loop, and a 4-colourable triangle loop
Vertex colouring algorithms for meshes
It is NP-hard to compute the chromatic number of a graph, and the 3-colouring problem is still NP-complete on 4-regular planar graphs. But there are different algorithms we can use to colour a graph in polynomial time.
One of such algorithms is Gregory Chaitin‘s, which I implemented in the Model Viewer. If the mesh is 3-colourable, it seems to work well. However, it seems a more naive approach based on the inherent order of the vertices of the mesh works better for meshes that are not 3-colourable. See the examples below.
Graph colouring comparison through wireframe. The left column uses Gregory Chaitin’s algorithm, whereas the right images follow the vertex ordering of the data.
In the example above, white areas appear white because 2 or more vertices share the same colour, so our wireframe shader that’s based in barycentric coordinates fails to paint just the edge. The mesh is not 3-colourable, so it can’t be helped. But, as it can be seen in the images on the right, we can do better if we paint the vertices in a different order. In this case, we simply follow the ordering given by the index number of the vertices in the mesh. The painting algorithm is simply:
- For each triangle, sort its vertices by vertex index. E.g. [3, 0, 2] becomes [0, 2, 3].
- Sort all the triangles in the mesh by “most significant” vertex index, i.e. we look at the first index of each triangle and if they are the same, we look at the next index. E.g. Given a = [2, 4, 20], b = [3, 4, 12], and c= [3, 5, 1], they will be sorted [a, b, c].
- Then, for each triangle,
- Start with 3 available labels/colours.
- Remove vertices already painted, and labels already used by those vertices.
- For the remaining vertices, assign the remaining labels in order. If we run out of available labels, the mesh may not be 3-colourable. Skip vertex.
That’s all.
The wireframe shader
It turns out that many meshes have a very regular structure and are indeed 3-colourable. So I thought it was still valuable to implement this shader, even if it doesn’t work for any arbitrary mesh. The shader is extremely simple:
vec4 lines = 1.0 / clamp(64.0 * vertexColor, 0.0001, 64.0); float line = max(lines.r, max(lines.g, lines.b)); gl_FragColor = vec4(line, line, line, 1.0);
Rasterisation examples to illustrate the shader output given different vertex colours as input. Only pure Red, Green, Blue inputs result in a wireframed triangle.
Solid wireframe on a close-up of one of our models
In terms of implementation complexity, it was harder for me to enable vertex colouring than the actual shader. If you are curious, check this pull request: Model Viewer / Memory Layout. I refactored my old code so I could define the memory layout of the vertex data that I send to the GPU in a tidier way. I stored the colours as 32-bit RGBA values, so it’s just an extra 4 bytes per vertex.
Conclusion
This was a fun exercise to learn a bit about graph colouring, barycentric coordinates, and wireframe shaders, and how all those 3 things can relate together. Although the resulting rendering algorithm may create undesirable white patches in arbitrary geometries, it works for regular topologies like the ones in our models. Because lines are rendered using a distance function in a pixel shader, lines can look thick when you zoom in, an effect that may be desirable when you want to emphasise certain areas of the wireframe.
