Watertight Adaptive Tessellation

The next obvious step for tessellation is to make it adaptive based upon the distance to the camera. It is important to keep the tessellated mesh watertight in order to prevent cracks from appearing between separate quads.

There are five different ways (that I can think of) to address this problem.

1) Do absolutely nothing

For the longest time with my original LOD algorithm this is the path I followed. If you are okay with having nasty cracks in your mesh, then this is definitely the way to go. But that is no longer acceptable to me.

2) Cheap fix (force all edges to be 1)

If all quad edges are not subdivided at all, then there will be no cracks and it will be fast. The problem is there will be no detail at the edges, and this quickly becomes very obvious and ugly.

3) Expensive fix (force all edges to be 64)

Here is the flip-side to the previous option. All quad edges are subdivided to the maximum level. This ensures that the best detail will be used at each edge. However this is too expensive to do for all quads.

4) Be smart about it (use adjacency information)

This is the method that Jack Hoxley uses and describes here. Basically he builds a vertex buffer that contains the 4 vertices of the quad plus another 8 vertices representing the 4 adjacent quads. In the hull shader, he calculates the midpoint of each quad and then calculates the distance (and thus a tessellation factor) from the midpoint to the camera. He chooses the minimum factor for each edge in order to have the quads match.

This is a pretty good solution, but it requires building a large vertex buffer containing adjacency information, as well as the additional midpoint calculation in the hull shader.

5) Do it right (calc factors from each vertex)

The next question is, can we do efficient watertight adaptive tessellation without adjacency information or the midpoint calculation? The answer is yes! If we calculate the tessellation factors from the vertices themselves, then we can guarantee that the surrounding quads will use the same factors (because they are using the same vertices).

The basic algorithm is this:
- Calculate the tessellation factor based on camera distance for each of the 4 vertices

float distanceRange = maxDistance - minDistance;
float vertex0 = lerp(minLOD, maxLOD, (1.0f - (saturate((distance(cameraPosition, op[0].position) - minDistance) / distanceRange))));
float vertex1 = lerp(minLOD, maxLOD, (1.0f - (saturate((distance(cameraPosition, op[1].position) - minDistance) / distanceRange))));
float vertex2 = lerp(minLOD, maxLOD, (1.0f - (saturate((distance(cameraPosition, op[2].position) - minDistance) / distanceRange))));
float vertex3 = lerp(minLOD, maxLOD, (1.0f - (saturate((distance(cameraPosition, op[3].position) - minDistance) / distanceRange))));

- Use the minimum value for each edge factor (pair of vertices)

output.edges[0] = min(vertex0, vertex3);
output.edges[1] = min(vertex0, vertex1);
output.edges[2] = min(vertex1, vertex2);
output.edges[3] = min(vertex2, vertex3);

- Use the overall minimum value for the inside tessellation factor

float minTess = min(output.edges[1], output.edges[3]);
output.inside[0] = minTess;
output.inside[1] = minTess;


Note: I originally thought the inside factor should be the maximum of the 4 vertices, but I after viewing it in action, I felt that the minimum was better.

That's it! Simple, fast, and easy watertight adaptive tessellation.

Check out the video of it in action: (I recorded the video at 1280x720, so be sure to view it at 720 to see the little details.)

Cube to Sphere Tessellation

My previous tessellation example was just a 2D, screen-space quad. My latest example steps into the world of 3D.

No code to share, just a pretty little video. It shows a cube being tessellated on the fly to form a sphere. What's being done is each quad is being tessellated and then the vertex position is normalized.

I was lazy and instead of making an entire cube with 6 sides, I only built a vertex/index buffer for 3 sides. You can only tell when I move the camera around at the end of the video.

I was getting about 1500 fps for the cube and about 900 fps for the fully tessellated sphere. 63*63*3*2 = 23,814 triangles!

Here ya go:

Simple Tessellation Example

I have finally got my computer all setup with the Radeon 5450 and started doing some DirectX 11 development. Obviously the first thing I tried out was the tessellation.

There are some nice sample projects included in the DirectX SDK that cover tessellation, but I felt that they were a little too ... complex. Don't get me wrong, I feel that they are great samples of doing things like model subdivision, detail tessellation, and bezier curves. I just felt that there should be a very simple demonstration of tessellation in the most basic sense. I decided to write one myself and share it here.

I should note that this was written using SlimDX. I love having the power of DirectX in C#!

As I stated, this is pretty much the most basic example of tessellation I could think of. It has one single quad with vertices defined in screen-space, which allows us to skip any transformation. The shader then tessellates the quad by using hard-coded tessellation factors. That's it!



The main application code isn't that important. It just creates the vertex buffer consisting of 4 vertices. It then draws using the new "4 control point patch" primitive. All the rest of the magic happens in the HLSL code.

The vertex shader isn't that impressive. It is simply a pass-through shader and passes the vertex position through to the hull shader.

VS_OUTPUT VS( VS_INPUT input )
{
 VS_OUTPUT output;
 
 output.position = input.position;
 
 return output;
}

The hull shader constant fuction simply sets the hard-coded tessellation factors for the edges and inside. Currently I have it hard-coded to a factor of 32. You may manually change this value to be anywhere from 1-64.

HS_CONSTANT_OUTPUT HSConstant( InputPatch<VS_OUTPUT, 4> ip, uint pid : SV_PrimitiveID )
{
 HS_CONSTANT_OUTPUT output;
 
 float edge = 32.0f;
 float inside = 32.0f;

 output.edges[0] = edge;
 output.edges[1] = edge;
 output.edges[2] = edge;
 output.edges[3] = edge;

 output.inside[0] = inside;
 output.inside[1] = inside;

 return output;
}

The hull shader itself does not perform a basis change, and therefore it passes through all 4 of the input points to the output. As you can see from the attributes, it is operating on the quad domain and it uses the standard clockwise winding.

[domain("quad")]
[partitioning("integer")]
[outputtopology("triangle_cw")]
[outputcontrolpoints(4)]
[patchconstantfunc("HSConstant")]
HS_OUTPUT HS( InputPatch<VS_OUTPUT, 4> ip, uint cpid : SV_OutputControlPointID, uint pid : SV_PrimitiveID )
{
    HS_OUTPUT Output;
    Output.position = ip[cpid].position;
    return Output;
}

Before explaining the domain shader, let me first explain the orientation of the UV coordinates coming from the tessellator.

Let's assume your vertices are defined in this manner:

   u
 0-----1
v|     |
 |     |
 3-----2

The U dimension ranges from [0-1] in the direction of vertex 0 to vertex 1.
The V dimension ranges from [0-1] in the direction of vertex 0 to vertex 3.

I specifically state this now because I had wrongly assumed that it was oriented such that the U and V coordinates were reversed, like so:

  WRONG!
 1-----2
 |     |
v|     |
 0-----3
   u

Now, about the domain shader itself. This is normally where the samples got rather complex calculating bezier curves and such. This is the simplest algorithm I could come up with. It uses three linear interpolations to calculate the vertex position. I visualize it as sliding two lines along the the quad and marking where they intersect as the vertex.

The first lerp finds the "midpoint" between vertex 0 and 1 by a factor of U.
The second lerp finds the "midpoint" between vertex 3 and 2 by a factor of U.
The third lerp finds the "midpoint" between the first and second calulated midpoints by a factor of V.

This is rather hard to "draw" a diagram for, but hopefully this makes some sense:

  lerp1
 0--|--1
 |  _  | lerp3
 |     |
 3--|--2
  lerp2

The color of the vertex is set based upon the tessellation UV coordinates.

[domain("quad")]
DS_OUTPUT DS( HS_CONSTANT_OUTPUT input, float2 UV : SV_DomainLocation, const OutputPatch<HS_OUTPUT, 4> patch )
{
    DS_OUTPUT Output;
    
    float3 topMidpoint = lerp(patch[0].position, patch[1].position, UV.x);
    float3 bottomMidpoint = lerp(patch[3].position, patch[2].position, UV.x);
    
    Output.position = float4(lerp(topMidpoint, bottomMidpoint, UV.y), 1);
    Output.color = float4(UV.yx, 1-UV.x, 1);
    
    return Output;    
}

The pixel shader just writes out the color.

float4 PS( DS_OUTPUT input ) : SV_Target
{
 return input.color;
}

There you have it! Hopefully this simple example of tessellating a single quad will be useful to other people and help to illustrate how the tessellator works.

You can download the full source to this example here: Tessellation.zip