I’ve spent the past couple of days refactoring a tonne of code. That’s the problem with writing prototype/proof of concept code … eventually you need to go back and make sure it all works! With that out of the way (and the code looking pretty spiffy), I focused my attention on dynamic tessellation. I haven’t come up with an optimal solution yet, but I’ve made some good progress.

First, what the heck is tessellation, and why is my approach dynamic? Tessellation is breaking up smooth paths (in our case, Bézier curves) into a number of smaller lines. The more lines we use, the closer the approximation is to the actual curve, and as a result, the smoother the lines appear to be. Videocards are unable to render Bézier curves, they can only render points, lines and triangles. As a result, tessellation is critical to rendering curves on hardware.

Now the “dynamic” bit. This has to do with how we perceive smoothness. Basically, the bigger a curve appears on screen, the more lines are required to make it appear smooth. By scaling the amount of tessellation we use on the curves, we can ensure that we always have smooth looking curves using a minimal amount of lines.

Let’s take a look at the different approaches I took to solving this problem. I used three paths which I will creatively call (from left to right) Path 1, Path 2 and Path 3. The screenshot on the left shows the paths rendered in debug mode. Each line is coloured differently to make the tessellation obvious. The screenshot on the right shows how it would actually appear.

The naive approach

When I started off with my prototype, I simply used 16 edges for every curve regardless of it’s size or complexity. As you can see, some paths work out better than others. In particular, Path 1 looks terrible.

Length by control points

This method scales the tessellation by using the length of the curve. The longer the curve, the more tessellation required. We calculate the length by finding the distance between p0, c0, c1, p1 and multiplying by the scaling factors.

It then uses this rather arbitrary formula to figure out tessellation:

number of edges = 16 * (quicklength / 10000.0f) + 1
(quicklength is defined as the length sans the square root part … it’s an extra operation I save, and I’m not terribly interested in the actual length, just some form of measuring relative distances)

While Path 2 & 3 are look quite nice, Path 1 has visible edges. This is because the more extreme the shape of the path, the further the control points are from the actual curve. Take a look at the debug screenshot below to see what I mean.

Length by coarse sampling

I solve the issue above by using coarse sampling. Instead of using the control points I sample the curve at t=0.00, 0.25, 0.50, 0.75, 1.00 and find the “quicklength”. This yields better results, but there are still problems.

The middle of Path 1 is too finely tessellated whereas Path 3 isn’t well tessellated at all. The reason for this is that we are uniformly tessellating the curve. Slope plays a big role in how finely tessellated a path should be, and we aren’t taking this into consideration.

What’s next

My next algorithm will non-uniformly tessellate the curve by taking it’s slope into account. Wish me luck!