## Monday, April 15, 2013

### Introduction

This tutorial is one part of a series of tutorials about generating procedural meshes. See here for an outline.

We already created the vertices in the last tutorial. In order to triangulate the mesh, we need to create the index buffer, set it in the input assembler stage, change the primitive topology from point list to triangle list and change the draw call to draw indexed primitives.

### VertexBuffer and IndexBuffer

There are two ways to draw triangles:

1. explicitly listing every vertex of each triangle of a mesh
2. having a list of vertices and describe each triangle by the indices in the vertex buffer
The first approach is useful for very small meshes like a rectangle. The second way is used to consume less memory for a mesh. Consider the size of a vertex with only the information for its position x,y,z: these are already three floats and you need to use 12 byte (as one float is 4 bytes). Having more complex vertices with position, color, normal, texture coordinates and what ever information you need for you shaders, the size of a  single vertex can grow significantly. In contrast to this, you need some sort of integer data type (byte (1), short (2), int (4), long (8) - with size in bytes in brackets) to point to an index in the vertex buffer.

Let's take a look at this rectangle, defined by four points p0, p1, p2 and p3:

Following the approach to explicitly list the vertices, we can triangulate the rectangle by creating a list of vertices: v0, v1, v2, v3 ,v4, v5

This results in the two triangles v0, v1, v2 (red) and v3, v4, v5 (blue):

Now we have a list of 6 vertices that have the according positions of the points. As you can see, we have to duplicate the positions p1 and p3 in our list of vertices. In this example I created the triangles clockwise by enumerating the vertices of a triangle in a clockwise manner (p0, p1, p3). In contrast to this the enumeration (p0, p3, p1) is counterclockwise. This list of 6 vertices would be our vertex buffer and we would tell the device to draw two triangles.

In order to avoid duplication of vertices when triangulating a mesh, we can use an index buffer. Again we need to set up a vertex buffer, but this holds this time just four vertices:

Vertex Buffer: v0, v1, v2, v3

Now, this picture does not look too much different from the picture above. Essential is the content of the index buffer, which points at the indices of the vertex buffer:

Now we can create the index buffer of the grid mesh.

### Grid Mesh Source Code

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using SlimDX.D3DCompiler;
using SlimDX;
using SlimDX.Direct3D11;
using SlimDX.DXGI;

namespace Apparat.Renderables
{
public class GridMesh2 : Renderable
{
SlimDX.Direct3D11.Buffer vertexBuffer;
DataStream vertices;
int numVertices = 0;

SlimDX.Direct3D11.Buffer indexBuffer;
DataStream indices;
int numIndices = 0;

InputLayout layout;

int stride;

EffectTechnique technique;
EffectPass pass;

Effect effect;
EffectMatrixVariable tmat;

float stepSize;

public GridMesh2(int witdh, int height, float stepSize)
{
int numVerticesWidth = witdh + 1;
int numVerticesHeight = height + 1;

this.stepSize = stepSize;

numVertices = numVerticesWidth * numVerticesHeight;

try
{
"transformEffect.fx",
"Render",
"fx_5_0",
EffectFlags.None))
{
effect = new Effect(DeviceManager.Instance.device, effectByteCode);
technique = effect.GetTechniqueByIndex(0);
pass = technique.GetPassByIndex(0);
inputSignature = pass.Description.Signature;
}
}
catch (Exception ex)
{
Console.WriteLine(ex.ToString());
}

tmat = effect.GetVariableByName("gWVP").AsMatrix();

stride = 12;
int sizeInBytes = stride * numVertices;
vertices = new DataStream(sizeInBytes, true, true);

float posX, posY;
float startX = -witdh * stepSize / 2.0f;
float startY = height * stepSize / 2.0f;

for (int y = 0; y < numVerticesHeight; y++)
{
for (int x = 0; x < numVerticesWidth; x++)
{
posX = startX + x * stepSize;
posY = startY - y * stepSize;

vertices.Write(new Vector3(posX, posY, 0));
}
}

vertices.Position = 0;

// create the vertex layout and buffer
var elements = new[] { new InputElement("POSITION", 0, Format.R32G32B32_Float, 0) };
layout = new InputLayout(DeviceManager.Instance.device, inputSignature, elements);
vertexBuffer = new SlimDX.Direct3D11.Buffer(DeviceManager.Instance.device, vertices, sizeInBytes, ResourceUsage.Default, BindFlags.VertexBuffer, CpuAccessFlags.None, ResourceOptionFlags.None, 0);

// create the index buffer
int numPatches = (numVerticesWidth - 1) * (numVerticesHeight - 1);
numIndices = numPatches * 6;
indices = new DataStream(2 * numIndices, true, true);

for (int y = 0; y < numVerticesHeight-1; y++)
{
for (int x = 0; x < numVerticesWidth-1; x++)
{
short lu = (short)(x + (y * (numVerticesWidth)));
short ru = (short)((x + 1) + (y * (numVerticesWidth)));
short rb = (short)((x + 1) + ((y + 1) * (numVerticesWidth)));
short lb = (short)(x + ((y + 1) * (numVerticesWidth)));

// clockwise
indices.Write(lu);
indices.Write(ru);
indices.Write(lb);

indices.Write(ru);
indices.Write(rb);
indices.Write(lb);
}
}

indices.Position = 0;

indexBuffer = new SlimDX.Direct3D11.Buffer(
DeviceManager.Instance.device,
indices,
2 * numIndices,
ResourceUsage.Default,
BindFlags.IndexBuffer,
CpuAccessFlags.None,
ResourceOptionFlags.None,
0);

}

public override void render()
{
Matrix ViewPerspective = CameraManager.Instance.ViewPerspective;
tmat.SetMatrix(ViewPerspective);

// configure the Input Assembler portion of the pipeline with the vertex data
DeviceManager.Instance.context.InputAssembler.InputLayout = layout;
DeviceManager.Instance.context.InputAssembler.PrimitiveTopology = PrimitiveTopology.TriangleList;
DeviceManager.Instance.context.InputAssembler.SetVertexBuffers(0, new VertexBufferBinding(vertexBuffer, stride, 0));
DeviceManager.Instance.context.InputAssembler.SetIndexBuffer(indexBuffer, Format.R16_UInt, 0);

technique = effect.GetTechniqueByName("Render");

EffectTechniqueDescription techDesc;
techDesc = technique.Description;

for (int p = 0; p < techDesc.PassCount; ++p)
{
technique.GetPassByIndex(p).Apply(DeviceManager.Instance.context);
DeviceManager.Instance.context.DrawIndexed(numIndices, 0, 0);
}
}

public override void dispose()
{
}
}
}



### Creating the IndexBuffer

As we created the vertex buffer with a double nested for loop, so we create the index buffer with a double nested for loop. To give you an intuition how I create the index buffer, take a look at this picture:

I start at vertex v0 and look at a patch of four vertices. Two from the current column (v0 and v1) and two from the next column (v5 and v6). From these four vertices I create two triangles by adding six indices to the index buffer. This way I iterate to vertex v3 and create the last two triangles for this column and then move to the next column and so on ...

SlimDX.Direct3D11.Buffer indexBuffer;
DataStream indices;
int numIndices = 0;


// create the index buffer
int numPatches = (numVerticesWidth - 1) * (numVerticesHeight - 1);
numIndices = numPatches * 6;
indices = new DataStream(2 * numIndices, true, true);

for (int y = 0; y < numVerticesHeight-1; y++)
{
for (int x = 0; x < numVerticesWidth-1; x++)
{
short lu = (short)(x + (y * (numVerticesWidth)));
short ru = (short)((x + 1) + (y * (numVerticesWidth)));
short rb = (short)((x + 1) + ((y + 1) * (numVerticesWidth)));
short lb = (short)(x + ((y + 1) * (numVerticesWidth)));

// clockwise
indices.Write(lu);
indices.Write(ru);
indices.Write(lb);

indices.Write(ru);
indices.Write(rb);
indices.Write(lb);
}
}

indices.Position = 0;

indexBuffer = new SlimDX.Direct3D11.Buffer(
DeviceManager.Instance.device,
indices,
2 * numIndices,
ResourceUsage.Default,
BindFlags.IndexBuffer,
CpuAccessFlags.None,
ResourceOptionFlags.None,
0);


Let's compare the memory used for this approach and the example depicted in the picture above to the memory used for explicitly listing the vertices for triangulation:

#### The Explicit Case

We have 4 x 3 = 12 cells in the grid. Each cell consists of two triangles, so we get 12 x 2 = 24 triangles. For each triangle we need three vertices: 24 x 3 = 72 vertices. As we use the cheapest vertice type with position x,y,z only, one vertice costs 12 bytes. This results in 72 x 12 = 864 bytes.

#### Using an Index Buffer

We have 5 x 4 = 20 vertices, which cost 20 x 12 = 240 byte. As we still have to describe the triangles in the index buffer, we need 72 indices. We use shorts, so one index costs 2 bytes: 72 x 2 = 144 bytes. Summing the costs for vertex and index buffer, we get  240 + 144 = 384 bytes.

This effect of saving space for vertex data amplifies with the number of triangles one vertice is used for. The four vertices at the corner of the mesh are just used once for a triangle, the other vertices on the border of the grid are used twice for triangles and each vertice inside of the grid is used for four triangles. Some meshes have an even higher connectivity (meaning the use for triangles, for example on vertex is used for six triangles).

### Rendering the GridMesh

The next thing we have to adjust is the code in the render method. First we have to change the primitive typology to TriangleList. Next we have to set the index buffer with SetIndexBuffer. Finally we have to switch the Draw call to DrawIndexed.

public override void render()
{
Matrix ViewPerspective = CameraManager.Instance.ViewPerspective;
tmat.SetMatrix(ViewPerspective);

// configure the Input Assembler portion of the pipeline with the vertex data
DeviceManager.Instance.context.InputAssembler.InputLayout = layout;
DeviceManager.Instance.context.InputAssembler.PrimitiveTopology = PrimitiveTopology.TriangleList;
DeviceManager.Instance.context.InputAssembler.SetVertexBuffers(0, new VertexBufferBinding(vertexBuffer, stride, 0));
DeviceManager.Instance.context.InputAssembler.SetIndexBuffer(indexBuffer, Format.R16_UInt, 0);

technique = effect.GetTechniqueByName("Render");

EffectTechniqueDescription techDesc;
techDesc = technique.Description;

for (int p = 0; p < techDesc.PassCount; ++p)
{
technique.GetPassByIndex(p).Apply(DeviceManager.Instance.context);
DeviceManager.Instance.context.DrawIndexed(numIndices, 0, 0);
}
}


As a result we get a tessellated (triangulated) mesh:

### Rendering as Wireframe

In order to see the triangulation of the mesh, we have to extend the shader with a RasterizerState. You can play around with FillMode, CullMode and FrontCounterClockwise to see what effects they have.

See MSDN for the reference of the RasterizerState. Interesting are the default values for these states: FillMode (Solid), CullMode (Back) and FrontCouterClockwise (false). If you do not set the RasterizerState, Directx assumes, you want to fill your triangles, the front of your triangle is defined clockwise (like I did in my code above) and the back of the triangle will not be rendered.

matrix gWVP;

float4 VShader(float4 position : POSITION) : SV_POSITION
{
return mul( position, gWVP);
}

float4 PShader(float4 position : SV_POSITION) : SV_Target
{
return float4(0.0f, 1.0f, 0.0f, 1.0f);
}

RasterizerState WireframeState
{
FillMode = Wireframe;
//CullMode = Front;
//FrontCounterClockwise = true;
};

technique10 Render
{
pass P0
{
SetRasterizerState(WireframeState);
}
}


Using this shader, we get this wireframe of the grid mesh: