# How much to tessellate?

## Recommended Posts

cephalo    739

Ok, I have the current distance based LOD scheme set up in my hull shader. It works pretty well, but has some non-optimal aspects. cp[0], cp[1] and cp[2] are the corners of my triangle patch.

PatchConstants PatchHS(InputPatch<VertexOutput,10> cp, uint patchID : SV_PrimitiveID)
{
PatchConstants pt;

float3 mid0 = lerp(cp[1].PositionWorld,cp[2].PositionWorld,0.5f);
float3 mid1 = lerp(cp[2].PositionWorld,cp[0].PositionWorld,0.5f);
float3 mid2 = lerp(cp[0].PositionWorld,cp[1].PositionWorld,0.5f);

const float dMax = 250.0f;

float d = distance(mid0,vecEye.xyz);
pt.EdgeTess[0] = 12.0f * pow(saturate((dMax - d)/dMax),3);

d = distance(mid1,vecEye.xyz);
pt.EdgeTess[1] = 12.0f * pow(saturate((dMax - d)/dMax),3);

d = distance(mid2,vecEye.xyz);
pt.EdgeTess[2] = 12.0f * pow(saturate((dMax - d)/dMax),3);

d = distance(cp[9].PositionWorld,vecEye.xyz);
pt.InsideTess = 16.0f * pow(saturate((dMax - d)/dMax),2);

return pt;
}



I'm using the midpoint of my triangle patch edges to calculate distance to the camera. Visually, the need for more or less triangles is nowhere near linear in it's relationship to distance, so I am also applying an exponential curve that sort-of, kind-of helps. This scheme is an improvement over simply using fixed tessellation factors, but it seems that it should be possible to come up with something better. The following screenshot shows one of the weaknesses of a distance based scheme.

[attachment=15203:TessFactors.jpg]

You can see a mountain in the foreground and a valley between this mountain and other mountains in the background. The tiles in the valley are both relatively flat and also oblique to the camera so that they need very little tessellation, yet they are being rendered with more triangles than the mountains in the background that could actually use some extra triangles. Wasteful in the former case and sort of ugly in the latter.

Before I tried the distance scheme, I tried to tessellate based on the screen length of the respective patch edges, but I couldn't figure out how to get it working. Such a scheme would be much more efficient and would also preserve water tight stitching since neighbor edges would have the exact same length. Does anybody know how I can calculate that in the hull shader? I tried multiplying my corner vertices by my ProjectionView matrix and then measuring length, but I couldn't figure out what to do with the results of that calculation. How long is a pixel in my world? I have no idea. If an edge goes from one corner of the screen to the other, how long is that? 100? 0.01? I couldnt find a useful context for the distance between my transformed corner control points.

##### Share on other sites
Jason Z    6434

How about preprocessing your control points to indicate where the 'sharp' areas of the heightmap are?  That way you can efficiently put more detail where it will be most needed before you load your control points, and then you can always apply a scaling of that starting point based on the distance from the viewer.

About the screen space length - you need to project the vertices (as you did), then divide the result by its w-value.  This will put you in clip space, which is in the ranges of [-1,1] for x and y and [0,1] for z.  Then you just need to remap the x and y coordinates to your screen size (i.e. render target height and width).  Finally, you can take the length of the vector between the two points to find out the screen space distance between them in pixels...

That seems like a lot of steps, so you may want to find something that approximates this somehow.  For example, you can just directly use the clip space representation, which will give you a roughly proportional distance that doesn't depend directly on the screen resolution.

##### Share on other sites
cephalo    739

Thanks for the reply Jason. I did my best to implement your screen space method, and it almost works except I have one or two bugs that seem impossible. It's one of those times I really wish I could debug my shader. Here is my new hull shader:

PatchConstants PatchHS(InputPatch<VertexOutput,10> cp, uint patchID : SV_PrimitiveID)
{
PatchConstants pt;

float4 corner0 = mul(float4(cp[0].PositionWorld,1.0f),ViewProjection);
float4 corner1 = mul(float4(cp[1].PositionWorld,1.0f),ViewProjection);
float4 corner2 = mul(float4(cp[2].PositionWorld,1.0f),ViewProjection);

corner0 = corner0/(corner0.w + 0.00001f);
corner1 = corner1/(corner1.w + 0.00001f);
corner2 = corner2/(corner2.w + 0.00001f);

const float dMax = 1.5f;

float d0 = abs(distance(corner1.xy,corner2.xy));
pt.EdgeTess[0] = 64.0f * saturate(d0/dMax);

float d1 = abs(distance(corner2.xy,corner0.xy));
pt.EdgeTess[1] = 64.0f * saturate(d1/dMax);

float d2 = abs(distance(corner0.xy,corner1.xy));
pt.EdgeTess[2] = 64.0f * saturate(d2/dMax);

float d3 = min(d0,min(d1,d2));
pt.InsideTess = 64.0f * saturate(d3/dMax);

return pt;
}


I have two problems that I can see in the following screen shot that are probably related somehow. The most obvious problem is that no matter how much space a triangle takes up on screen, my inside tess factor is computing to 2 or less even though I'm clearly trying to use the smallest edge length for the calculation. The second problem I am having is that I can see that the bottom and left sides of the triangles are matching up with their neighbor, but the right side is not! How can only one side not match up? If I switched them there should be two sides not matching up. It would seem that my d2 value is bad or NaN or something, but I can't imagine why that would be, also it seems to almost be right, while NaN values usually jump out at you.

[attachment=15215:TessProb.png]

I almost wonder if my code is being optimized away or something. Here is a picture of the resulting gaps. You can see they are only on the one diagonal.

[attachment=15217:TessProb2.jpg]

##### Share on other sites

So, do you have multiple LODs at the same time on screen ?

if so, did you consider you have to connect them via some intermediary patch that has High detail on one side and low on the other one ? Hunting for those bugs is no fun, though...

##### Share on other sites
cephalo    739

So, do you have multiple LODs at the same time on screen ?

if so, did you consider you have to connect them via some intermediary patch that has High detail on one side and low on the other one ? Hunting for those bugs is no fun, though...

LOD in this sense only applies to the edge. There is no problem for each edge to have a different tess factor as long as they line up with their neighbors. There's no need for an  intermediary patch.

On another note, when I simply use pt.EdgeTess[2] = 4.0, the gaps go away and the opposing triangles line up on all sides. That means that for some reason, the distance calculation is giving different results going backwards or forwards, e.i. the distance from corner0 to corner1 is different than the distance from corner1 to corner0. I can't imagine how it ends up that way. For the other edges everything lines up!

##### Share on other sites

And that's why God invented the Breakpoint

Seriously, if the code works in 80% of the cases, it is you who has to figure out why remaining 20% doesn't.

If, for some reason, you cannot debug the shader, use colors of vertices to determine the computed results (e.g. assing a color for each range of the values -> Black (0-63), Red (64-127), Green (128-191), Blue (192-223), White (224-255).

Also, you could use a texture as an output from the pixel shader, if the method above does not yield the desired results.

##### Share on other sites
cephalo    739

I went ahead and lowered the max tessellation from 64 to 12 in order to make the problem more obvious. Another thing that is really stumping me is that the inside tessellation result makes no sense at all, even with the problem on edge 2.

[attachment=15220:TessProb3.jpg]

I used this code to change it, and it works much more as intended: (Note that changed d0,d1 etc. to dist0, dist1 in case I was using some register name by accident)

	float dist3 = min(dist0,min(dist1,dist2));
//	pt.InsideTess = 12.0f * saturate(dist3/dMax);
pt.InsideTess = min(pt.EdgeTess[0],min(pt.EdgeTess[1],pt.EdgeTess[2]));



But I can't imagine why this line would give a different result than the line commented out line! The edge factors are calculated the same way as the inside factor! If the bad edge is wrong but close to the others, why would the inside edge be zeroed out when I am using the same distance? The inside factor should match one of the three edges, and the commented out line it matches none of them.

Edited by cephalo

##### Share on other sites
cephalo    739

Here is another observation that I did not expect. On the triangle patch in the center of the image, even though the edge nearest to the camera is nearly twice as long as the other two edges, all the edges appear to have the same tess factor! I know I can set them independently, so the three edges must be calculating to the same clip space length. That also explains why one edge is not lining up with its neighbor. It looks like my clip space calculations are wrong, because the distance between the edge points are always the same which is not the case.

Actually this consequence is visible in the above example as well. All of the edges of a single triangle have the same tess factor. What am I doing wrong?

EDIT: wrong again actually. Only the 1 and 2 edges are always the same, the 0 edge appears to be independent. I have no idea what's going on.

[attachment=15221:TessProb4.jpg]

Edited by cephalo

##### Share on other sites
Jason Z    6434

Very interesting problem...  Can you post your declarations for the tessellation factor structure (PatchConstants) and your input control point structure (VertexOutput)?  I'm curious to see how they are declared.  Also, have you tried to run the program with the reference device instead of the hardware device?  I recall when I was working on tessellation a while back that there is huge variability from driver to driver, and you may find that the issue is something to do with a problem in that area...

I will go back through my notes on tessellation and see if I can find anything related to similar issues, and I'll post here if I am able to find anything.

EDIT: One other thing - can you post the attributes of your tessellation setup as well?  For example, the domain, partitioning, etc...  I would also like to take a look at those if possible.

Edited by Jason Z

##### Share on other sites
MJP    19755

At work we used to do something very similar to what's described in this presentation, back when we were planning on using a lot of tessellation. It seemed to work well enough, although it was never battle-tested in a production setting.

##### Share on other sites
cephalo    739

Here are the requested structures:

struct VertexOutput
{
float3 PositionWorld    : POSITION;
float2 MainTexCoord        : TEXCOORD;
};

struct PatchConstants
{
float EdgeTess[3]    : SV_TessFactor;
float InsideTess    : SV_InsideTessFactor;

};
struct HullOut
{
float3 PositionWorld	: POSITION;
float2 MainTexCoord		: TEXCOORD;
};

[domain("tri")]
[partitioning("fractional_even")]
[outputtopology("triangle_cw")]
[outputcontrolpoints(10)]
[patchconstantfunc("PatchHS")]
HullOut HS(InputPatch<VertexOutput,10> p, uint i : SV_OutputControlPointID, uint patchId : SV_PrimitiveID)
{
HullOut hout;

hout = p[i];

return hout;
}


I've never used the ref device. I'm not even sure exactly what that is. I'd almost give my left foot to peek into my variables in the shader, (but not \$500!). I think its one of those things that seems to be partially working, but is really not working at all except in creating an illusion of working.

Edited by cephalo

##### Share on other sites
Jason Z    6434

Ok, that stuff all looks fine, and your calculation looks fine to me too.  If you think that there is a low level fundamental problem, then I would recommend to temporarily modify your drawing routine to only render a single control patch, and then you can work on that directly before moving on to the large scale issue.

Next I would suggest getting the tessellation to respond directly to your changes.  So start out with manually setting the tessellation factors, then switch back to your calculated value with the max factor set to something simple like 4.

Similarly, I would set your inside tessellation factor manually first to ensure that it is changeable/controllable, and then make it a function that can't end up with a zero value.  For example, take your saturated result and use that as the interpolant to the lerp function, and use two positive values for the min and max tessellation factor.  It seems that there is some values going to zero, and that is cooking your inside tessellation factor.

##### Share on other sites
cephalo    739

Yeah, I've been playing around with it a lot today. Anytime I do anything differently, it works fine. For example I set edge[0] to 4.0, edge[1] to 6.0 and edge[2] to 8.0 and I got what you would expect with no mismatched edges. I can set the inside tess factor to anything and it works fine.

The only thing I changed from my original distance based hull shader is the bit that I displayed. I wonder if there is something wrong with my ProjectionView matrix that for some reason I didn't notice before, or if there is some automatic fix in later stages that eliminates whatever problem it might have.

##### Share on other sites
Jason Z    6434

Did you try the lerp function to ensure you don't end up with zero as a tessellation factor?  Also, did you isolate down to a single triangle patch in your rendering?  I think both of those can give you more confidence in your code.

Also, since you are working from within the patch constant function, it can be difficult to output an appropriate diagnostic information.  If your manual setting of the tessellation factors works, then try using if / then statements to test the data in the patch constant function.  For example, you could do something like this:

PatchConstants PatchHS(InputPatch<VertexOutput,10> cp, uint patchID : SV_PrimitiveID)
{
PatchConstants pt;

float4 corner0 = mul(float4(cp[0].PositionWorld,1.0f),ViewProjection);
float4 corner1 = mul(float4(cp[1].PositionWorld,1.0f),ViewProjection);
float4 corner2 = mul(float4(cp[2].PositionWorld,1.0f),ViewProjection);

corner0 = corner0/(corner0.w + 0.00001f);
corner1 = corner1/(corner1.w + 0.00001f);
corner2 = corner2/(corner2.w + 0.00001f);

const float dMax = 1.5f;

float d0 = abs(distance(corner1.xy,corner2.xy));
pt.EdgeTess[0] = 64.0f * saturate(d0/dMax);

float d1 = abs(distance(corner2.xy,corner0.xy));
pt.EdgeTess[1] = 64.0f * saturate(d1/dMax);

float d2 = abs(distance(corner0.xy,corner1.xy));
pt.EdgeTess[2] = 64.0f * saturate(d2/dMax);

float d3 = min(d0,min(d1,d2));
if ( d3 < 2.0 )
pt.InsideTess = 2.0;
else
pt.InsideTess = 4.0;

return pt;
}



That should give you some way to interrogate different values within that function.

##### Share on other sites
cephalo    739

Ok, I'd like to report on the first couple of experiments for today. I flipped my dist1 and dist2 values to see what would happen, and interestingly this did not change the bad edge. Even with the values swapped the bad edge is still edge 2.

PatchConstants PatchHS(InputPatch<VertexOutput,10> cp, uint patchID : SV_PrimitiveID)
{
PatchConstants pt;

float4 corner0 = mul(float4(cp[0].PositionWorld,1.0f),ViewProjection);
float4 corner1 = mul(float4(cp[1].PositionWorld,1.0f),ViewProjection);
float4 corner2 = mul(float4(cp[2].PositionWorld,1.0f),ViewProjection);

corner0 = corner0/(corner0.w + 0.00001f);
corner1 = corner1/(corner1.w + 0.00001f);
corner2 = corner2/(corner2.w + 0.00001f);

const float dMax = 1.5f;

float dist0 = distance(corner1.xy,corner2.xy);
float dist1 = distance(corner2.xy,corner0.xy);
float dist2 = distance(corner0.xy,corner1.xy);

pt.EdgeTess[0] = 12.0f * saturate(dist0/dMax);
//	pt.EdgeTess[0] = 4.0;

pt.EdgeTess[1] = 12.0f * saturate(dist2/dMax);
//	pt.EdgeTess[1] = 6.0;

pt.EdgeTess[2] = 12.0f * saturate(dist1/dMax);
//	pt.EdgeTess[2] = 8.0;

float dist3 = min(dist0,min(dist1,dist2));
pt.InsideTess = 12.0f * saturate(dist3/dMax);
//	pt.InsideTess = min(pt.EdgeTess[0],min(pt.EdgeTess[1],pt.EdgeTess[2]));

return pt;
}



[attachment=15227:TessProb5.jpg]

I also did a test to see if dist1 and dist2 are equal, and they are not equal. Floating point numbers are rarely equal, but I still wanted to test for it.

##### Share on other sites
cephalo    739

Ok, here is the most interesting experiment yet. See the following code: When I comment out the 'saturate' line and put a specific tess factor in an edge, it works fine for edge[0] and edge[2], but when I do the exact same thing for edge[1], I get a compiler exception!

Also, when I comment out all the 'saturate' lines and put in all fixed values, all the edges display as defined and the inside tess factor calculation begins to work as I intended!

Can I deduce from this that there is a compiler bug that I have to work around somehow? I giggle at myself for saying that, because whenever I accuse 'the system' of being broken, it's always my fault and I don't remember a time in my life where that wasn't the case.

Anyway, the following code does not compile! Edit: I tried turning off optimization with ShaderFlags None, OptimizationLevel0 and Debug and changing the shader flags does not allow compilation.

PatchConstants PatchHS(InputPatch<VertexOutput,10> cp, uint patchID : SV_PrimitiveID)
{
PatchConstants pt;

float4 corner0 = mul(float4(cp[0].PositionWorld,1.0f),ViewProjection);
float4 corner1 = mul(float4(cp[1].PositionWorld,1.0f),ViewProjection);
float4 corner2 = mul(float4(cp[2].PositionWorld,1.0f),ViewProjection);

corner0 = corner0/(corner0.w + 0.00001f);
corner1 = corner1/(corner1.w + 0.00001f);
corner2 = corner2/(corner2.w + 0.00001f);

const float dMax = 1.5f;

float dist0 = distance(corner1.xy,corner2.xy);
float dist1 = distance(corner2.xy,corner0.xy);
float dist2 = distance(corner0.xy,corner1.xy);

pt.EdgeTess[0] = 12.0f * saturate(dist0/dMax);
//	pt.EdgeTess[0] = 4.0f;

//	pt.EdgeTess[1] = 12.0f * saturate(dist1/dMax);
pt.EdgeTess[1] = 4.0f;

pt.EdgeTess[2] = 12.0f * saturate(dist2/dMax);
//	pt.EdgeTess[2] = 0.01;

float dist3 = min(dist0,min(dist1,dist2));
pt.InsideTess = 12.0f * saturate(dist3/dMax);
//	pt.InsideTess = min(pt.EdgeTess[0],min(pt.EdgeTess[1],pt.EdgeTess[2]));

return pt;
}


EDIT2: I'm going to post the whole shader if anyone would like to confirm this on their machine:

#define p300 0
#define p030 1
#define p003 2
#define p210 3
#define p201 4
#define p120 5
#define p021 6
#define p012 7
#define p102 8
#define p111 9

cbuffer PerFrameBuffer : register(b0)
{
//float4x4 World; This is just the identity matrix, so not needed
float4x4 ViewProjection;
float4 vecEye;
float4 LightDirection;
float4 LightColor;
};

struct VertexOutput
{
float3 PositionWorld	: POSITION;
float2 MainTexCoord		: TEXCOORD;
};

struct PatchConstants
{
float EdgeTess[3]	: SV_TessFactor;
float InsideTess	: SV_InsideTessFactor;

};

PatchConstants PatchHS(InputPatch<VertexOutput,10> cp, uint patchID : SV_PrimitiveID)
{
PatchConstants pt;

float4 corner0 = mul(float4(cp[0].PositionWorld,1.0f),ViewProjection);
float4 corner1 = mul(float4(cp[1].PositionWorld,1.0f),ViewProjection);
float4 corner2 = mul(float4(cp[2].PositionWorld,1.0f),ViewProjection);

corner0 = corner0/(corner0.w + 0.00001f);
corner1 = corner1/(corner1.w + 0.00001f);
corner2 = corner2/(corner2.w + 0.00001f);

const float dMax = 1.5f;

float dist0 = distance(corner1.xy,corner2.xy);
float dist1 = distance(corner2.xy,corner0.xy);
float dist2 = distance(corner0.xy,corner1.xy);

pt.EdgeTess[0] = 12.0f * saturate(dist0/dMax);
//	pt.EdgeTess[0] = 4.0f;

//	pt.EdgeTess[1] = 12.0f * saturate(dist1/dMax);
pt.EdgeTess[1] = 4.0f;

pt.EdgeTess[2] = 12.0f * saturate(dist2/dMax);
//	pt.EdgeTess[2] = 0.01;

float dist3 = min(dist0,min(dist1,dist2));
pt.InsideTess = 12.0f * saturate(dist3/dMax);
//	pt.InsideTess = min(pt.EdgeTess[0],min(pt.EdgeTess[1],pt.EdgeTess[2]));

return pt;
}

struct HullOut
{
float3 PositionWorld	: POSITION;
float2 MainTexCoord		: TEXCOORD;
};

[domain("tri")]
[partitioning("fractional_even")]
[outputtopology("triangle_cw")]
[outputcontrolpoints(10)]
[patchconstantfunc("PatchHS")]
HullOut HS(InputPatch<VertexOutput,10> p, uint i : SV_OutputControlPointID, uint patchId : SV_PrimitiveID)
{
HullOut hout;

hout = p[i];

return hout;
}

Edited by cephalo

##### Share on other sites
unbird    8336
June 2010 SDK compiler (version 9.29.952.3111) ? Yeah, same result here.

I should have mentioned earlier that this compiler has troubles with tesselation. You were more "lucky" to trigger a compiler crash. I only found out the hard way: Compiled but produced some funny results.

With the compiler coming with the Windows 8 SDK, version 9.30.960.8229, your shader compiles fine.

##### Share on other sites
cephalo    739

June 2010 SDK compiler (version 9.29.952.3111) ? Yeah, same result here.

I should have mentioned earlier that this compiler has troubles with tesselation. You were more "lucky" to trigger a compiler crash. I only found out the hard way: Compiled but produced some funny results.

With the compiler coming with the Windows 8 SDK, version 9.30.960.8229, your shader compiles fine.

How do I check which compiler I am using? What files are involved? I do have the June 2010 SDK because I needed PIX, but I thought I also have the Windows 8 SDK as well. I have no idea what's compiling my shader code. I wonder if the new compiler will allow my code to work properly.

##### Share on other sites
unbird    8336
The command line compiler dumps its version when calling [tt]fxc /?[/tt]. Compiling through the runtime is done through D3DCompile (or rather the SharpDX/SlimDX managed version thereof). The June 2010 SDK then uses the d3dcompiler_43.dll (the File Version actually is the compiler version), the Windows 8 SDK the d3dcompiler_44.dll.Hmmm, I'm currently digging the docs if one can grab that version through shader reflection.

Anyway: If you write your compiled binaries to a file (shader.fxo, see below) then fxc can grab the assembly from them with

The version is at the second line in shader.asm.

Edit: Ok, there is a Version field in ShaderDescription, but even the docs are enigmatic here. The field Creator, a string, is more informative:

[tt]Microsoft (R) HLSL Shader Compiler 9.30.960.8229[/tt]

Edit2: Yeah, forget about that Version field, it does not change when switching compilers. My bet it's rather shader type (VS, HS, etc). Edited by unbird

##### Share on other sites
cephalo    739

Ok, I installed the Windows 8 SDK on my home computer, and doing a search tells me that I have about 100 versions of this dll on my computer. The highest number goes up to d3dcompiler_46.dll. The one in my new SDK is 9.30.9200.20546. My SharpDX.D3DCompiler.ShaderBytecode.CompileFromFile method is still using 9.29.952.3111 according the Creator field. How do I coax SharpDX to use the new shader compiler?

##### Share on other sites
Jason Z    6434

I'm not sure how to get SharpDX to do it, but in general the first instance of a DLL that can be found either in the application's directory or the path will get loaded.  So I would start out with putting it into your executable directory and see if that works for you.

Even for the native C++ side I have to copy that DLL to the executable folder, so it isn't a problem limited to SharpDX.

##### Share on other sites
MJP    19755

You might be able to just directly call D3DCompile from that DLL using p/invoke.

##### Share on other sites
unbird    8336
An alternative is to use the command line compiler (that's how I checked your shader), i.e. generate binaries offline and load them in your app.

[tt]fxc.exe /E HS /T hs_5_0 /Fo hs.fxo /Fx hs.asm hs.hlsl[/tt]

Hmmm, can't seem to force SlimDX to load the newer DLL with that copy trick. I hope your thread in the SharpDX forum will reveal something.

##### Share on other sites
cephalo    739
Hmm, I'm not having much luck with the command line compiler. Here is my result.

C:\Users\rjm\Documents\Visual Studio 2012\Projects\HexMapDemo\HexMapDemo\bin\Deb
ug\Content\Effects\HexVertTri_HS.fx(1,1): error X3000: Illegal character in shad
er file

Here is the exact command I used:
C:\Users\rjm\Documents\Visual Studio 2012\Projects\HexMapDemo\HexMapDemo\bin\Deb
ug\Content\Effects>fxc /E HS /T hs_5_0 /Fo HexVertTri_HS.fxo /Fx HexVertTri_HS.a
sm HexVertTri_HS.fx

EDIT: Ooh, just got a reply from xoofx over at SharpDX. I'm going to try to change over my SharpDX build. Hopefully that will make everything as easy as before.
Edited by cephalo

##### Share on other sites
cephalo    739

Ok, I have that squared away and I'm back in business! My algorithm works great, I just have to tweak it so that both low detail and high detail aren't so quick to appear. I can handle that.

After this I'll need to see some performance info of some kind, so I need to print text. I'll open a new thread for that. My research on that topic has given me some conflicting info.