Triangle Tessellation with Clamped Parallelograms

Hardware tessellation as we know it today (Dx11-style) had its origins on the Xbox 360, which released in 2005. Time flies, right? It was a natural step in the evolution toward film-quality realtime rendering. After all, tessellation was a key component of the original Pixar Reyes paper [7].Now that it’s 20+ years later, we have more experience with the algorithm, and hardware tessellation has not become the solution for these use cases. But the core ideas in Dx11-style tessellation are still good ones, and they’re worth revisiting on their own terms. With the benefit of hindsight, we can take those ideas, make different decisions along the way, and see if we can land on an algorithm that satisfies the same constraints with some more desirable properties.The final algorithm, once we get there, is going to look like this. It allows us to transition among all the patterns in the header image without popping.The code is stored as JavaScript, so feel free to use it as you wish (it’s MIT licensed). I essentially took my existing C++ code and said “Mr. Claude, turn this into a JavaScript viewer, GLHF.”How does Dx11 tessellation work, exactly?Each edge of a triangle has a tessellation factor that roughly describes how many segments the edge has. In the case of Dx11, this value is in the range [1,64]. The key design decision is that each tess factor is a float value, and we can lerp between any values without a visible pop. From that perspective, we can split tessellation into two subproblems. Given a tessellation factor, split the edge into line segments. Given those edge line segments, split the interior of the triangle. There are overviews online [3][4][5], as well as Fabian Giesen’s writeup of the Dx11 tessellator stage [6]. But for this exercise, we’re going to dive into the nitty-gritty details, and derive them as we go.How should we tessellate a line segment? The most obvious solution would be to use subdivision, splitting each edge in half at each power of two.

Note: Tess factors in Dx11 are from [1,64], but I’ll be using ranges starting at 0 to simplify the formulas.This gives us an ideal tessellation level at each power of two. Tess factors of 8 and 16 look great, but how should we handle a value of 11? Instead of going straight from 8 to 16, we can add those points one at a time. Conceptually, if we want a value of, say 11, we can think of the last added point as a “pivot”. At a tess factor of 11, 8 should be taken by the previous power of two, 3 of those new slots should be taken, and 5 are remaining. You can derive the formula yourself (or look at the code) but the results look like this:That uses the same points as raw subdivision, but transitions them one at a time instead of introducing all of them at a power of two. But how could we modify the algorithm to have a clean transition without pops? All points stay the same, except the pivot point. For a value of 10.3, we round up to 11 segments. 8 points are locked from the previous subdivision, 2 points have already transitioned in, and the last point has a 30% lerp from the previous point and where it is going to.Now it’s getting more interesting, and the next problem is the distribution. We want an evenly spaced tessellation, but in our current iteration we have dense spacing below the pivot and sparse spacing above it. Dx11 solves this problem by making all points the same length except the one that is sliding in.This change is both good and bad. The good news is that we get a more evenly spaced tessellation. The bad news is that it introduces a lot of movement. Before, only the pivot point was moving. But now, all points are moving all the time.We have one more practical problem: Symmetry. If we have two triangles next to each other, cracks will form if the tessellation is moving in opposite directions. Fortunately, we can fix this by mirroring the tessellation across the bottom. And that gives our Dx11 result.This is, AFAICT, the algorithm for fractional even tessellation in Dx11.

We have solved the first problem (given three tess factors, split the edges). Now we need to find an algorithm that splits a triangle internally according to these tess factors, without causing popping.As a first step, let’s start with our original triangle, and split it into 6 smaller triangles.Using the internal tess factor, we can create a tessellated triangle using regular “triforce” tessellation. This gives us 6 tessellated triangle regions.The obvious problem is that now all 3 edges have the exact same tess factor. We can solve that by simply discarding the outermost strip of triangles.All we have to do now is connect the internal tessellation to our edge tessellation, without actually causing a pop. The trick is that we should think in terms of the original powers of two. Let’s show a line down the middle which is the smallest power of two greater than or equal to the two tess factors. Then let’s match the lhs and rhs sides to the middle. The lhs tess factor here is the internal tessellation and the rhs tess factor is the edge tessellation on the other side of the gap.Then we can match from lhs to rhs, noting that multiple points of lhs might point to the same rhs point. For each point on the right, we can find its reverse match by walking back and connecting to the lhs points.To fill the gap with triangles, for each lhs point, we can find the current and next rhs match. Then add a triangle fan to connect to rhs, and then add one extra reversed triangle to fill it in. But note that we will want to skip the very last triangle. The blue triangles show the triangle fan from the current rhs match to the next rhs match. Then the red triangle closes the strip.And finally, we can use this matching algorithm to fill in the gaps for all 6 triangles.The Good and the BadThis algorithm has several very interesting properties. The primary advantage of this approach is the flexibility. We can choose any function for calculating tess factors for an edge, and then the tessellation just works. And since the transition is continuous, we never have to pop.On the other side, this flexibility results in less-than-ideal patterns. So we’ll go through them and how we can improve them with the clamped parallelogram approach.Varied Tess Factors: Suppose that we have two edges with a high tess factor and one with a low tess factor.

This is quite common with thin triangles. Ideally we would like a tessellation pattern that can directly connect the left and right side together. But since we only have a single internal tess factor, it will either be under-tessellated or over-tessellated.Instead, we can solve this problem by making a tess pattern that allows us to directly connect between the two high tess-factor edges.Inefficient Patterns: By splitting the triangle into 6 similar triangle regions we use more triangles than we need.In contrast, with the clamped parallelogram approach, any time all three tess factors are the same, it will be topologically equivalent to triforce tessellation. Although the spacing may be uneven, which is necessary to allow lerping tess factors without pops.Bending: If we are using tessellation for deformation (which is one of the most compelling uses of tessellation) we generally want to maintain straight edge loops to avoid sharp bends in the resulting tessellated mesh. If the original mesh was quads, we would want clean edge loops from left to right. Note that theoretically we could use the Dx11 quad primitive tessellation, but that opens a whole new set of issues with mixed triangle/quad meshes which are quite common (i.e. Suzanne from Blender).Instead, the clamped parallelogram pattern makes regular quads with clean edge loops that degrade gracefully as the tess factors deviate from each other.Minimum triangles: Fractional even has a minimum tessellation of 6 triangles, causing a sudden jump in cost by just “turning it on”.On the other side, clamped parallelogram tessellation can transition all the way from a single triangle.Movement: The Dx11 pattern is very “bouncy”. When this is used for actual displacement mapping, sharp edges cause visible back and forth wobbling as the tess factors move. The new function is significantly more stable at the expense of more unequal distribution.For simplicity, I’m focusing on fractional even. We can avoid the minimum triangles issue by using fractional odd, but that would greatly increase the amount of movement, while leaving the bending and inefficient patterns unchanged. While I don’t have an implementation of fractional odd tessellation, the algorithm essentially removes the midpoint of each edge, and any point that would have “slid out” from the midpoint now “slides in” from the outside.

Tessellating a LineBut before we try to improve the actual pattern, let’s revisit tessellating a line. The algorithm in Dx11 makes the spacing even except for the one sliding in. It sounds beneficial in theory, but the movement causes practical issues.The first thing we are going to do is actually take a step backwards. We’ll revert to the previous subdivision algorithm, where we add points one at a time and lerp the new point in. Here is a comparison of the two. You can really feel the amount of “bouncy” movement.As an interesting note, Dx11 tessellation does not converge. In particular, look at the path of the middle point. At a tessellation value of 4, the midpoint is 0.5. But as we tessellate, the next two points slide in below pushing the midpoint to 0.6667. Then the next two points slide in above that point which pushes it back down to 0.5 by the time we have 8 points. During each transition from one power of two to the next, this middle point goes from 0.5 to 0.667 and back to 0.5, never converging. The graph below shows the tess pattern as it lerps over the range.Here is the reverted version. Despite the poorer distribution of points, the stability is worth it. This is our new starting point.Let’s take a different approach. Instead of adding in points one at a time, let’s insert all the odd points before adding any of the even points. The distribution of edge sizes is the same, but the large and small edges are more evenly balanced.To further improve this, we can split the higher tessellations into blocks. When we go from, say, 64 to 128, new points will be added so quickly that they will look like popping even though it’s technically continuous. The solution is to divide our region into blocks, so that each power of two has 4 regions of different topology. We have multiple points sliding simultaneously, but the motions are slower and less likely to have a sudden movement that “feels” like a pop.As a final tweak, we want to have a clean transition from a tess factor of a plain line segment to the initial tess factor.