## Wednesday, 8 May 2013

### Geometry Generation (Fast)

Ok so first post here, let's start by something fun :)

One common thing needed in computer graphics is some form of geometry.

Some can come from 3d software and you use an importer (like Assimp, or your own), some geometries can be generated on the fly (Grid/Spheres/Box/Torus...)

Geometry generation is generally done as follow:

• Build a bulk of vertices in CPU (some for loop)
• Build an IndexBuffer in CPU (some for loop)
• Copy your buffers in GPU
• Use it !
Pretty simple uh?

Only issue is now it you want to modify your geometry parameters in real time (and you have decently high resolution geometry), you need to:
• Rebuild the bulk of vertices
• Copy again
• Eventually do the same for index buffer
That can get pretty slow, so let's look how to pimp that a tad.

Our friend DirectX 10 brings a feature called Stream Output, which allows you to render to buffers. This buffer can be either an Index Buffer or a Vertex Buffer, oh, that sounds quite convenient.

So let's say we want to build a grid (pretty simple example, but grids are decently used around as bezier/surfaces/heightfields...), resolution being 512*512

Here is our vertex shader input:

Code Snippet
1. struct vsInput
2. {
3.     uint iv : SV_VertexID;
4. };

And our desired output:

Code Snippet
1. struct vsOutput
2. {
3.     float3 pos  : POSITION;
4.     float3 norm  : NORMAL;
5.     float2 uv : TEXCOORD0;
6. };

Since we don't provide input geometry, we set IA stage to null (we don't send any geometry as input), and Assign the VertexBuffer as StreamOutput target.

Then the following lines of code generate vertices:

Code Snippet
1. vsOutput VS_Vertices(vsInput input)
2. {
3.     vsOutput o;
4.     int colindex = input.iv % colcount;
5.     int rowindex = input.iv / colcount;
6.     float2 uv = float2(input.iv % colcount,input.iv / colcount) * invgridsize;
7.     float2 pos = uv;
8.
9.     uv.y = 1.0f - uv.y;
10.     pos.xy = (pos.xy - 0.5f) * size;
11.     o.pos = float3(pos,0.0f);
12.     o.norm = float3(0,0,-1);
13.     o.uv = uv;
14.     return o;
15. }

Pretty simple:

• From the vertex id (simple GPU counter), we retrieve the cell position.
• To normalize it (eg: fit in 0/1), we simply multiply by inverse resolution
• We flip Y axis (for uv only)
• Recenter positition (so our grid center is in 0,0 not in 0.5,0.5)
• Done, that was so hard... :)
Now we need to generate our indices (since some vertices are shared).
We have few options here:
• Set our Stream Output as triangle: This is not convenient at all, since grid geometry is quad based, so we'll need to replicate a lot of calculations, and flip triangle depending on vertex id, which is not very friendly.
• Set our Stream Output as Quad: Instead of generating one triangle at a time in Vertex Shader, we will generate 2, which fits perfectly a cell expansion, and reuse calculations.
So obvious choice, quads

Here is our Vertex Shader output:

Code Snippet
1. struct vsOutputIndices
2. {
3.     int3 t1 : TRIANGLE0;
4.     int3 t2 : TRIANGLE1;
5. };

And the (extremely) hardcore Vertex Shader:

Code Snippet
1. vsOutputIndices VS_Indices(vsInput input)
2. {
3.     vsOutputIndices o;
4.     int j = input.iv / (colcount-1);
5.     int i = input.iv % (colcount-1);
6.     int rowlow = j * (colcount);
7.     int rowup = (j+1) * (colcount);
8.
9.     o.t1 = int3(rowlow + i, rowup + i, rowlow + i + 1);
10.     o.t2 = int3(rowlow + i + 1, rowup + i, rowup + i + 1);
11.     return o;
12. }

Here we do more or less the same as generating positions, excluding we need to take care or row/column indices stride.

Here we are, generating a Grid without CPU.

Nice thing about it is since other geometries can also be interpreted as a parametric surface, we can easily modify shader to generate them (only shader to generate vertices needs modifications, index buffer builder is the same).

Here is how to build a sphere:

Code Snippet
1. float3 sphere(float u, float v)
2. {
3.     float3 p;
4.     u = (u + 0.5) * PI * 2.0f;
5.     v = (v + 0.5) * PI * 2.0f;
6.     float su = sin(u); float sv = sin(v); float cu = cos(u); float cv = cos(v);
7.     p.x = su*sv;
8.     p.y = cu*sv;
9.     p.z = cv;
10.     return p;
11. }
12.
13. vsOutput VS_Vertices(vsInput input)
14. {
15.     vsOutput o;
16.     int colindex = input.iv % colcount;
17.     int rowindex = input.iv / colcount;
18.     float2 uv = float2(input.iv % colcount,input.iv / colcount) * invgridsize;
19.     float2 pos = uv;
20.     uv.y = 1.0f - uv.y;
21.     o.pos = sphere(uv.x * CyclesU,uv.y*CyclesV)*radius;
22.     o.norm = normalize(o.pos);
23.     o.uv = uv;
24.     return o;
25. }

Many other surfaces can be built same style (ideally if you can have partial derivatives for normals that helps)

Grid deformation was quite decently used in vvvv (deforming in vertex shader and then shading it), obvious win by using StreamOut is geometry is also reusable (shadow/forward...)

That's it for now, stay tuned.