Triangle Tessellation with Clamped Parallelograms – Filmic Worlds

Your browser is quite old! Why not upgrade to a different browser to better enjoy this site?

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<br>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].<br>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,<br>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<br>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?<br>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,<br>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<br>and sparse spacing above it. Dx11 solves this problem by making all points<br>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.<br>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<br>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...