Tessellation Simplified

I have implemented tessellation + displacement map for my game Shoe String Shooter.
To decide how much to tessellate a triangle I calculated it’s screen space area. The more screen space area it takes, the more I tessellated it.

This would theoretically make the triangles uniformly sized across the screen space. It made sense to me, but it has some major issues.

The displacement occurs along the triangle’s normal. If the triangle is facing the camera, its normal is facing the camera as well.
There is very little visible effect when the geometry is displaced towards the viewer. A flat triangle with a normal mapped texture would be just as good(almost).

Another thing is that triangles which  are 90 degrees from the camera will almost disappear in screen space and will have a very small area in screen space.
However, when displacing those triangles the geometry is very much visible since the normal is tangential to the screen space.

The simpler approach

The new approach I have taken is simpler and give better results. It also requires only 3 control points instead of 6.

The first step is to tessellate every edge of the triangle according to how long the maximum displacement vector(at the direction of the normal) is on the screen space.
This metric will have the facing and farther triangles tessellate less, and the conspicuous and closer triangles tessellate more.

This is not enough. Some triangles are very big in world space and we don’t modulate the tessellation with the triangle’s area any more. So large triangles will appear more coarse.

The solution is to modulate the displacement vector tessellation with world space edge length. This will achieve spatial uniformity in world space.
Tessellating according to edge length has some advantages compared to tessellating according to triangle area.
First, we only need 3 control points instead of 6.
Second, we tessellate more along the longer edges and tessellate less along the shorter edges. Area calculation will not differ between a golden triangle and a very narrow but long triangle.

The last step is to bound the tessellation amount since we don’t want unnecessary triangles on the geometry that is up close. We don’t set a constant tessellation bound, but instead set a bound modulated with the world space edge length.

Code

PatchTess ScreenSpaceTessellator(float3 w[3], float4 p[3], float4 q[3])
{
	PatchTess pt;
	float Res = 768.0;
	float Cell1 = 16.0;
	float Cell2 = 8.0;
	float MaxTes = 10.0;

	unsigned int i=0;
	for (i=0; i<3; i++)
		pt.EdgeTess[i] = 1;
	pt.InsideTess = 1;
	float Tess[3] = {0, 0, 0};
	if (IsScreenCull (p[0], p[1], p[2]))
		return pt;
	for (i=0; i<3; i++)
		p[i]/=p[i].w;
	for (i=0; i<3; i++)
		q[i]/=q[i].w;
	for (i=0; i<3; i++)
	{
		float3 a1 = (w[(i+1)%3]-w[(i+2)%3]);
		Tess[i] = length(a1)/Cell1;
//		Tess[i] = max(Tess[i], 1);
		float2 a2 = (q[(i+1)%3].xy-p[(i+1)%3].xy)*Res*0.5;
		float2 b2 = (q[(i+2)%3].xy-p[(i+2)%3].xy)*Res*0.5;
		Tess[i] *= 0.5*(length(a2)+length(b2))/Cell2;
		Tess[i] = min(max(Tess[i], 1), MaxTes*length(a1)/Cell1);
	}
	for (i=0; i<3; i++)
		pt.EdgeTess[i] = Tess[i];
	pt.InsideTess = (Tess[0]+Tess[1]+Tess[2])/3.0;
	return pt;
}

2 thoughts on “Tessellation Simplified

  1. That’s awesome. I’ve been wishing for an adaptive tessellator that focuses on adding detail to the silhouettes/side views, while letting bump/offset mapping handle the front-on stuff, ever since the Displacement Mapping craze back in 2002.

    Yes, I know my wish was very specific – I designed an algorithm to do it, but it was inconceivable to run it on the GPU in the SM2.0 days; and upon starting a software implementation, I quickly got distracted by attempting to directly rasterize perfect N-Patches.

    Any chance for an executable demo? I’d love to be able to examine some close-ups, without the distraction of YouTube’s MPEG artifacts.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s