Simple Compute Shader Example

The other big side of DirectX 11 is the Compute Shader. I thought I would write up a very simple example along the same lines as my tessellation example.

First let me say that the Compute Shader is awesome! It opens up so many possibilities. My mind is just reeling with new ideas to try out. Also I must mention that SlimDX really does a great job of minimalizing the code necessary to use the Compute Shader.

This example shows how to create a Compute Shader and then use it to launch threads that simply output the thread ID to a texture.

Device device = new Device(DriverType.Hardware, DeviceCreationFlags.Debug, FeatureLevel.Level_11_0);

ComputeShader compute = Helper.LoadComputeShader(device, "SimpleCompute.hlsl", "main");

Texture2D uavTexture;

UnorderedAccessView computeResult = Helper.CreateUnorderedAccessView(device, 1024, 1024, Format.R8G8B8A8_UNorm, out uavTexture);

device.ImmediateContext.ComputeShader.Set(compute);

device.ImmediateContext.ComputeShader.SetUnorderedAccessView(computeResult, 0);

device.ImmediateContext.Dispatch(32, 32, 1);

Texture2D.ToFile(device.ImmediateContext, uavTexture, ImageFileFormat.Png, "uav.png");

Believe it or not, but that is the entirety of my CPU code.

Here is what is going on in the code:
1) Create a feature level 11 Device, in order to use Compute Shader 5.0
2) Load/Compile the HLSL code into a ComputeShader object.
3) Create a 1024x1024 UnorderedAccesdView (UAV) object which will be used to store the output.
4) Set the ComputeShader and UAV on the device.
5) Run the Compute Shader by calling Dispatch (32x32x1 thread groups are dispatched).
6) Save the output texture out to disk.

My HLSL code is even simpler:

RWTexture2D<float4> Output;

[numthreads(32, 32, 1)]
void main( uint3 threadID : SV_DispatchThreadID )
{
    Output[threadID.xy] = float4(threadID.xy / 1024.0f, 0, 1);
}

As you can see a RWTexture2D object is used to store the output (this is the UAV). The shader is setup to run 32x32x1 threads. This means that since the CPU is launching 32x32x1 thread groups, then there are 1024x1024x1 separate threads being run. This equates to 1 thread per pixel in the output UAV. So, in the UAV, the color is just set based upon the thread ID.

This code results in the following output image:


Quite simple, eh? But not that interesting. We could easily do something like that with a pixel shader (although we would have to rasterize a full-screen quad to do it).

We should try to do something that shows the power of the compute shader; something you couldn't do in a pixel shader before. How about drawing some primitives like lines and circles?

For drawing lines, let's use the Digital Differential Analyzer algorithm. It translates to HLSL very easily.

void Plot(int x, int y)
{
   Output[uint2(x, y)] = float4(0, 0, 1, 1);
}

void DrawLine(float2 start, float2 end)
{
    float dydx = (end.y - start.y) / (end.x - start.x);
    float y = start.y;
    for (int x = start.x; x <= end.x; x++) 
    {
        Plot(x, round(y));
        y = y + dydx;
    }
}

For drawing circles let's use the Midpoint Circle algorithm. For brevity I won't list it here now.

Then, in my Compute Shader main function, I simply add this code:

if (threadID.x == 1023 && threadID.y == 1023)
{
DrawLine(float2(0, 0), float2(1024, 1024));
DrawLine(float2(0, 1023), float2(1023, 0));

DrawCircle(512, 512, 250);
DrawCircle(0, 512, 250);
}


The if check is just done to prevent the lines and circles from being drawn for every thread. This code results in the following image:


I must admit it seems quite odd writing a shader that draws primitives. It's like some strange recursive loop. But it definitely helps to illustrate the features of the Compute Shader and how powerful it is.

You may download the source code to this example here:
ComputeShader11.zip

My next goal is to setup a standard DX11 Swap Chain and use the Compute Shader to write directly to the backbuffer. Well that's all for now.

FYI: This is my 50th blog post! I never thought I would continue on this long. I think I should crack open a beer to celebrate.

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

Perlin Noise in DirectX 10 (Shader Model 4.0)

This is somewhat similar to the classic problem of Good, Cheap, and Fast where you can only have two of them at the same time.

I implemented Perlin Noise entirely on the GPU, meaning no textures are precomputed and no parameters are set on the GPU. The shader is simply loaded and ran. It is a very clean solution and it is incredibly simple to add to any project.

Unfortunately, it is slow. Mind you, it is still much faster than the CPU implementation, but it is slow compared to my original precomputed texture implementation.

I always run my tests using 12 octaves of 3D fBm Perlin Noise summations at a resolution of 1024x1024. It yields much more stable results than just 1 calculation of Perlin Noise. My original implementation ran at about 85 fps. At first, my new simple implementation was running at about 3 fps! Even though the documentation states that HLSL automatically marks all global variables as const, if I put the const keyword before my permutation array my frame-rate jumped up to 19 fps.

I added a gradient lookup table and changed the gradient calculation functions to just index into the table. However, this basically had no impact on the speed. I then reduced the permutation array from 512 to 256 and performed a modulus operation on any indexing into the array. This gave my about a 30% speed increase and got it up to about 25 fps.

I tried various other tweaks, and I was able to get it to go a bit faster, but it was always at the expense of the quality of the noise (wouldn't work with negative values, would look blocky, etc). The fastest I was able to get it and still maintain the high quality Perlin Noise was 25 fps.

I must say that I'm rather disappointed with these results. I had thought that constant memory indexing would be faster than texture lookups, however the texture lookup version was over 3 times faster than the memory indexing version. Perhaps I'm just missing something or I'm implementing the memory indexing incorrectly, but I don't know what I could possibly do to speed it up anymore AND keep the same quality.

For the time being, it looks like texture lookups are the way to go. I've decided to upload 2 versions of the noise code. The first version is a direct port of Ken Perlin's Java code to HLSL(19 fps). The second includes the tweaks to the gradients and permutation array (25 fps).

First Version
Tweaked Version

As I have said, the major advantage to this implementation is the simplicity. All you have to do is include the header in your HLSL code and you can call the noise() and fBm() functions. That's it! You don't have to do anything else. So if you just want to drag and drop some Perlin Noise into a shader, this is the best way to do it, if you don't care about speed.

Byte Order Mark - The Invisible Enemy

Alternate Title:
EF BB BF - The Three Bytes of Doom

Last night I decided to whip out a quick SlimDX / DirectX 10 project implementing Perlin Noise using Shader Model 4.0. In my Perlin Noise on the GPU article, I mentioned how much easier it would be to implement Perlin Noise using SM4.0+ vs SM3.0. I had done a quick port of Ken Perlin's Java example implementation in FX Composer a couple months back, so I thought I would be able to implement the stand-alone version in less than an hour.

I wanted to test it first in a pixel shader, so I made my own custom vertex as well as a class that would build a fullscreen quad vertex buffer. I took the Perlin Noise HLSL code and put it into a header file, and made a simple two-technique shader that included the header.

I fired up the code, but I quickly got an exception (E_FAIL: An undetermined error occurred (-2147467259)) at the point where I was trying to set the InputLayout of the vertex buffer to the shader signature. Not a very useful exception.

At first, I thought it might have been a problem with my custom vertex format. After looking it over and comparing against other custom vertex formats I've made in the past, I determined the issue wasn't there.

Next I looked at how I was creating the vertex buffer and index buffer for the fullscreen quad. That all appeared in order too.

After determining that the issue was not in my custom vertex format or my fullscreen quad, I slowly stepped through the code keeping a close eye on all of the variables. I didn't think there was a problem with my shader because no errors were being output from the compiler, and it was spitting out a valid Effect. However, when stepping through and watching the variables, I saw that even though it created an Effect and the IsValid property was true, it said the TechniqueCount was zero! In fact, all of the counts were saying zero. It was as if the compiler was seeing it as an empty file.

So, I next looked at my shader in detail. I thought maybe something funky was happening with the included header file, so I inlined all of the header code. I still got the exception. I thought it might be some random issue in one of my noise functions, so I changed them to all return 1.0. Exception. I triple checked all of my input and output structures. I looked over my technique description. I changed my vertex shader to be a simple pass-through and the pixel shader to just return white. Exception.

What the heck was going on? I had other shaders that were compiling just fine. So, just as a "stupid" test, I copied one of the my other working shaders and pasted all of the code into my fx file, overwriting everything in it. I still got the exception!

Now I knew something was really messed up somewhere. Here I had two fx files with the exact same HLSL code in them, but one was compiling while the other was not.

I opened both files up using the Binary Editor in Visual Studio to see byte by byte. The file that was not compiling had three extra bytes at the beginning - EF BB BF. I deleted these three bytes, and everything worked!

It turns out that that byte sequence is the Byte Order Mark. It is specifying that the file is UTF-8 encoded. Apparently this is the default for all files created in Visual Studio 2008. Unfortunately, the FX compiler in DirectX can't read UTF-8 files and just dies and returns an empty Effect.

I did a quick Google search after fixing the problem and I saw that several other people had the same problem and eventually came to the same solution. I really wish the compiler would return an error in a situation like this.

What I find very interesting is the fact that I have been programming shaders for over two and a half years, and I have never run into this problem before.

Hopefully this post helps someone else if they encounter this same problem.

Until next time...

Infinite Depth Buffer

I've been planning out how I'm going to rewrite my planet algorithm once DirectX 11 is out. I've decided to focus on problems I have now that will still be a problem in DX11. One such problem that I've always been having in the past is the depth buffer.

My planet is Earth-sized so in order to keep it visible as you fly away from it, I pushed the far clipping plane way out. Obviously this destroyed the precision of my depth buffer and I had big problems with Z-fighting (far off mountains were being drawn in front of closer ones).

Rant: Why the heck are most GPUs these days still stuck with a 24-bit depth buffer? The Xbox 360 and my GeForce 9800M GT both only support up to a 24-bit depth buffer. DX11 level GPUs will have 64-bit floating point (double) support in shaders, so why not a 64-bit depth buffer?

In the videos and screenshots I have posted in the past, I did two different things to try and fix my problem with the depth buffer. First, I had a "sliding" far clipping plane that would have a minimum value, but as you flew away from the planet, it would extend out in order to continually show the planet. My second solution was to just disable the depth buffer. Both of these solutions only worked because I was drawing only 1 planet and there were no other objects being rendered. Obviously I want to keep my depth buffer around, keep the high precision for any near objects, but continue to draw far off planets (not have them clipped by the far clipping plane).

In order to fully understand my problem, I read about how exactly the depth buffer works and how a position is transfomed and then clipped. I found this article very informative about the inner workings of the GPU in terms of the depth buffer. I did not change my depth buffer to be linear like he does though. The article helped me to understand the relationship between the Z component and W component of the transformed vertex position.

Between the vertex shader and the pixel shader, the Z component is divided by W in order to "normalize" the depth (range 0-1). If the Z value is greater than 1 then it is clipped. So, I needed to make it so that the normalized Z value never exceeded 1. This was a very simple thing to fix, once I understood it. In my vertex shader I check the Z value to see if it is greater than the far clipping plane value (which I pass into the shader). If it is greater, then I simply set the W component equal to the Z component. This means that the Z / W calculation thus becomes Z / Z = 1. Now I can have good depth buffer precision for things close to the camera, but I will continue to draw things even if they are an infinite (theoretically) distance away!

Obviously this solution isn't perfect and there are some "gotchas". If I am drawing a planet and a moon, and the moon is behind the planet, and I am flying away from the planet, AND the moon is being drawn after the planet in the C# code, then the moon will suddenly pop in front of the planet once the planet exceeds the far clipping plane. That means I'll have to have a manager of large objects in the "local system" to make sure they are drawn in back to front order. That should be really easy to implement.

Hopefully this all makes sense and it helps someone else struggling with the same problem.

Until next time...

Update: I would now strongly encourage people to use a Logarithmic Depth Buffer to solve all of your depth buffer precision issues. You can read about it here:

http://www.gamasutra.com/blogs/BranoKemen/20090812/2725/Logarithmic_Depth_Buffer.php

Perlin Noise on the GPU

I've written a tutorial on how to implement Perlin Noise in both a pixel shader and a vertex shader. The tutorial is available over at Ziggyware.

http://www.ziggyware.com/readarticle.php?article_id=246

Check it out! I welcome any feedback.

UPDATE
http://www.ziggyware.com/news.php?readmore=1125
I found out I have won first place in the Ziggyware contest! I'm very happy that my first XNA tutorial was such a success. Perhaps I will write up more in the future.

UPDATE 2
It appears that Ziggyware no longer exists, so I have shared the article, screenshots, and sample code on my server.  You can download it all here:
http://re-creationstudios.com/shared/PerlinNoiseGPU/

Craters

Another quick update. I have been working on adding craters to the procedural moon. I implemented a Voronoi diagram shader in HLSL and then I tweak it with quite a few different parameters to generate conical pits that are distorted slightly with fBm noise.









I tried for quite a while to get rims around the edges of the craters, but I couldn't get it to work. I tried using a colormap to alter the Voronoi results, but I was having issues with the it. I will continue to tinker around with it because I think having rims would add quite a bit.

Interesting fact: If I add even more fBm noise to the crater distortions, it forms pretty cool canyons:

Switching Gears

So I was chatting with one of my friends about what was up next on the todo list for my procedural planet. I explained that I was working on fog and that after that I would focus on water. He suggested that I get HDR and Depth of Field put in next. I then mentioned how I want to get Atmospheric Scattering in as well.

With all of these features laid out, the project seems rather daunting. That is easily several months worth of work right there. (I still do have a full time job!) I started thinking about how to make it easier, yet still make it stand out. I mean no matter how many awesome looking things I put in, I will never even come close to the level of Crysis. I am only one guy! So, I decided I should focus more on something that would be feasible for a team of one to accomplish in a lifetime.

Time for a personal history lesson!

Back when I first started fiddling around with XNA (over 2 years ago now), I also started looking into shaders for the first time. I have always been interested in Non-Photorealistic Rendering (cel shading, painterly rendering, hatching, etc), so I thought that might be a good subject to test with shaders. In my research, I came across a great paper about doing real-time pencil sketch rendering. http://cg.postech.ac.kr/research/pencil_rendering/

In January 2007, I began work on my own pencil shader. I actually started with 4 separate shaders that would require all models to be rendered 4 times. Fairly quickly I realised that I could speed things up greatly by having 1 shader with 4 passes. I tinkered around with it, and other things, for several months before I found out about using multiple render targets. Using this, I was able to get it down to 3 passes. Not long after that, I demoed the shader in a job interview and I actually got a job as an XNA Game Developer! That job lasted until the company got bought out by a larger company. Toward the end of my employment there, I started getting into procedural generatation, and that's how I came to have the procedural planet that I have today.

As you know, I have a new laptop now, and during the transfer of files from my old laptop, I saw my old pencil shader again. It had gone untouched since the day I demoed it in my job interview. Yesterday I finally decided to take all of the code and update it to XNA 2.0 and clean up what I could. I realized that I had learned quite a bit over the last year about both XNA and C#, so I was able to make the code much cleaner. Not only that, but I was also able to get the shader down to 2 passes! This gave me a 100fps speed boost. (On my GeForce 9800 GT, the 4 pass = 470fps, 3 pass = 480fps, 2 pass = 580fps.)

This has really given me a desire to work on NPR stuff again. So, currently my next goal is to have a procedural planet that is rendered using my pencil shader.

Procedural Texturing

Well I am now producing what in my opinion are decent procedural textures for the planetary terrain. They are generated per pixel every frame. This has the advantage of allowing infinite resolution as well as eliminating any texture coordinate warpings around a sphere, since the textures are actually 3D.

As I mentioned before, this does require a significant performance hit. I have managed to simplify the texture generation to the point of having reasonable framerates while maintaining decent texture quality. What I am doing is calculating 4 separate textures using 2 octaves of turbulence noise at different scales for each one. These 4 textures represent sand, grass, rock, and snow. They are then blended together based upon the terrain height to generate a final texture.

I am getting anywhere between 25-50 frames per second depending upon how many pixels of the terrain are taking up the viewport. The average for normal travel is 35 frames per second.

Here are some screenshots of the results.