Optimized rendering of edges for Quest

On Quest, rendering edges around faces is very costly (much more so than on PC): it can sometimes reduce the frame rate by a factor of two. In VR Sketch 16.0 we added a new mode for rendering them. The result is of slightly lower quality in some respects, but much faster.

This is a technical post about how it works. I am going to assume you know the basics about programming shaders and algorithms in Unity. So our target audience for this post is quite a bit different than usual :slight_smile:

The standard way to draw edges is to set up meshes as the “line” type. Even if they are edges of faces, the face is a regular “triangle” type mesh and we had to set up a different mesh (or submesh) of the “line” type that draws the edges. Now, in VR Sketch 16 on Quest, “line” type meshes are still used for standalone edges, but edges of faces are done differently: we are drawing only the faces as triangles, and the shader we use contains logic to alter the color drawn on some of the borders of these triangles—it becomes black near the border, smoothly from the regular face color that is drawn anywhere else.

For the shader part, see for example the great detailed explanations of https://catlikecoding.com/unity/tutorials/advanced-rendering/flat-and-wireframe-shading/. See also https://stackoverflow.com/questions/18035719/drawing-a-border-on-a-2d-polygon-with-a-fragment-shader for OpenGL ES devices (like the Quest)—you can’t have geometry shaders on the Quest, but you can store “colors” in your vertices, one red one green one blue per triangle; then the interpolated “colors” in the middle of the triangle give you the barycentric coordinates.

This gives the wireframe: all triangles drawn get their edges shown. But when faces are more than 3-sided, they are internally split into more than one triangle (that’s called triangulation), and we must not draw all the resulting edges. The second part is thus about tweaking the approach to let some edges be drawn and others not.

The simple, but manual, solution is to have one side of the triangle drawn as an edge, but not the other two sides. If you have that, then you can subdivide the triangulation manually. For example, you add a vertex in the middle of the face, and then you triangulate that face with triangles that always have that extra vertex as summit, and one of the outer edges as base. In this setting, all triangles need exactly one edge drawn. A simple tweak does it: in the shader, compute the distance to only one of the edges. You can do it using only one number instead of the barycentric coordinates: put the value 0 on the two base vertices and the value 1 on the summit, and then when the interpolated value is very close to 0 you know you are very close to the base and must draw black.

VR Sketch 16 uses a more advanced scheme that avoids creating an extra vertex in the middle (because in general it can be hard to do, if the face is not convex). Also, some random subset of the edges can be hidden by the user (“soft” edges, in SketchUp). So its solution is to not add any vertex in the middle. We keep its regular triangulation logic, and then look at each triangle, and find out which of its three borders must be shown as edges. We now need a slightly more complex shader, and (again) more than a single value per vertex, in order to support all cases—we are using a full “color”, i.e. R, G, B and A values. Furthermore, doing so might require duplication of some vertices: this is the case if a vertex needs different “colors” when considered as part of different triangles. The chosen scheme tries to be flexible in the sense that there are many color combinations that give the same result, which improves the chances that we don’t need to duplicate any vertex; still, it doesn’t work in all cases.

So, the final solution assigns a full RGBA “color” to every vertex, and computes the blackening factor in the fragment shader as follows, where colstem is the interpolated color from the vertices:

    /* 'ccut' is a non-negative value that evolves continuously across the triangle,
       and that reaches zero on the edges if they must be drawn as black. */
    float ccut = min(min(colstem.r, colstem.g), colstem.b);

This means that the RGB values are chosen so that if two of the three vertices of the triangle have both R=0 or both G=0 or both B=0, then that edge is drawn black. Moreover, neither R nor G nor B is zero across all three vertices of the triangle, otherwise the whole triangle would be rendered black. The exact assignments of RGB values are flexible, as explained above. For example, if we want a triangle with only one edge visible (say between vertices 1 and 2), then we could choose RGB=011 for the first vertex, RGB=011 again for the second vertex, and RGB=110 for example for the third vertex; but many other combinations work too. And if we want the edge between vertices 1 and 2 and the edge between vertices 2 and 3 visibles, but not the edge between vertices 1 and 3, then we can pick for example RGB=011/001/101. The details are a rather complicated algorithm, in order to minimize the number of vertices that need to be duplicated because of color conflicts between adjacent triangles. Of course as a first solution it is fine to always duplicate the vertices; then you are free to assign to each of them its own RGB “color”, and you have just 4 cases to consider: each triangle needs between 0 and 3 edges visible.

The shader logic is not finished, though. Once we have the value ccut, we use the “magical” function fwidth() to compute the real value cut that we’re using to multiply the final pixel color. The fwidth() function computes how much the value we pass in actually changes between adjacent pixels. This is how we get a black effect that is about 2 pixels wide, whatever the size of the triangle, and smoothly:

    /* `cut` is what to multiply the color with, between 1 (normal) and 0 (black). */
    const float EDGE_WIDTH = 2;
    float cut = smoothstep(0, fwidth(ccut) * EDGE_WIDTH, ccut);

In practice, we have found two more problems which required additional fixes:

  1. In some very flat triangles, edges “bleed”. For example, imagine a very flat triangle with a summit A and a long base B-C, with A being close to the middle of B and C. Say that we happen to want to draw the edge A-B and none of the others. The logic above computes the distance of a point to the edge A-B, and if it is smaller than EDGE_WIDTH then it will be drawn in black. However, many points that are in the wrong half of the triangle are still close to the infinite line A-B, even if they are not close to the segment A-B. The result is that the black edge is extended far into the wrong half of the triangle. To fix that, we use the alpha (A) component of the vertex “colors” (RGBA): in very flat triangles, we give alpha=0 to B, alpha=0.25 to A, and alpha=0.5 to C. For all non-very-flat triangles we just use alpha=0 for every vertex. Then we modify the computation like this, which forces all points in the “wrong half” of the triangle to have cut=1 and thus not show any black vertex:

     float cut = colstem.a > 0.25 ? 1 : smoothstep(0, fwidth(ccut) * EDGE_WIDTH, ccut);
    
  2. There are some very heavy aliasing issues when we’re viewing very small triangles or a dense grid of squares or a pile of very thin rectangles. The computed cut value is mostly a random value between one screen pixel and the next one, because almost every pixel is from a different triangle. This is mostly fixed by making all edges disappear in that case, instead of showing up with very heavy aliasing. We check fwidth() again: if it says the rate of change of ccut is just too large, then we increase the value of cut a lot. This fades the edges off:

    const float ATTENUATION = 2.4;
    float cut = colstem.a > 0.25 ? 1 :
         min(smoothstep(0, fwidth(ccut) * EDGE_WIDTH, ccut)
             + ATTENUATION * fwidth(ccut), 1);
    

That’s it! This is the algorithm like it is in VR Sketch. You can see in practice how well it renders… and when it doesn’t render so well. If you can find corner cases where the results are really bad, we would love to hear about them so that we can try to tweak the algorithm more!

A bientôt,

Armin Rigo