Synthesizing Patches using Vertex Shaders

Streamlining the calculations

However, the processing overhead can be greatly reduced with a bit of consideration. The first thing that we can do is cutout two thirds of the operations right off the bat. While complex surfaces would usually employ splines that interpolate vertex coordinates as the parameter, since we are using a uniform grid the X and Z of each control point will be implicit. Our splines will only need to control a 1-D parameter, the altitude.

To further optimize the calculation, we will look at ways that we can pre-calculate as much as possible. If we look back on Equation 1, you will see that the spline calculation contains a scalar constant as well as a constant basis matrix. By pre-multiplying these by the control points to form a 4D vector, the calculation for a a point on a spline segment can be reduced to a single dot product operation:

q(t) = (1,t,t²,t³) • (P₂, (P₃-P₁)/2, (2P₁-5P₂+4P₃-P₄)/2, (-P₁+3P₂-3P₃+P₄)/2)
Equation 4

Since we will be calculating multiple values from each spline segment, we can pre-calculate the second term of this equation as a 4D vector for each segment, using a function like this:

void preCalcCatmullRom(D3DXVECTOR4 *v,float p1,float p2,float p3,float p4)
{
    v->x=p2;
    v->y=(p3-p1)*0.5f;
    v->z=p1-2.5f*p2+2.0f*p3-0.5f*p4;
    v->w=-0.5f*p1+1.5f*p2-1.5f*p3+0.5f*p4;
}

Listing 1

for (int i=0;i<4;i++) { preCalcCatmullRom(pMatV, height[x+i][z], height[x+i][z+1], height[x+i][z+2], height[x+i][z+3]); pMatV++; }

P₁ P₂ P₃ P₄	* Basis Matrix * 0.5 ->	P'₁ P'₂ P'₃ P'₄
P₅ P₆ P₇ P₈	* Basis Matrix * 0.5 ->	P'₅ P'₆ P'₇ P'₈
P₉ P₁₀ P₁₁ P₁₂	* Basis Matrix * 0.5 ->	P'₉ P'₁₀' P'₁₁ P'₁₂
P₁₃ P₁₄ P₁₅ P₁₆	* Basis Matrix * 0.5 ->	P'₁₃ P'₁₄ P'₁₅ P'₁₆

D3DXMATRIX basisMat; basisMat._11=0.0; basisMat._12=1.0; basisMat._13=0.0; basisMat._14=0.0; basisMat._21=-0.5; basisMat._22=0.0; basisMat._23=0.5; basisMat._24=0.0; basisMat._31=1.0; basisMat._32=-2.5; basisMat._33=2.0; basisMat._34=-0.5; basisMat._41=-0.5; basisMat._42=1.5; basisMat._43=-1.5; basisMat._44=0.5; D3DXMatrixMultiply(&splineMat,&basisMat,&splineMat);

P₁ P₂ P₃ P₄	* Basis Matrix * 0.5 ->	P'₁ P'₂ P'₃ P'₄
P₅ P₆ P₇ P₈	* Basis Matrix * 0.5 ->	P'₅ P'₆ P'₇ P'₈
P₉ P₁₀ P₁₁ P₁₂	* Basis Matrix * 0.5 ->	P'₉ P'₁₀' P'₁₁ P'₁₂
P₁₃ P₁₄ P₁₅ P₁₆	* Basis Matrix * 0.5 ->	P'₁₃ P'₁₄ P'₁₅ P'₁₆
		* Basis Matrix * 0.5

Using Vertex Shaders to Render Patches

When handling very large landscapes, the size of the mesh involved often precludes loading of the entire mesh at one time. Instead, a local region is maintained, and as the viewer moves new sections are created for the region the viewer is approaching, while old sections are discarded as the viewer moves away from them. This can consume a considerable amount of bandwidth, and also means that the vertex buffers involved must be updated in video memory if hardware vertex processing is used.

Vertex shaders, as we will see, can provide an interesting alternative. By moving the calculations into the shader, we can strip our vertex format down to a point that allows reuse of vertex buffers to render all of the landscape quads using the a single vertex buffer containing the vertices necessary to render a single quad, without ever changing the vertices in the buffer!

Note that the implementation we will provide here uses a fixed LOD (Level of Detail), meaning that all quad patches are rendered using the same level of subdivision. Variable LOD is possible, we will discuss that in the Potential Improvements section later on.

Storage of Common Quad Data

To facilitate such reuse of vertices, the vertex format will contain only x and z coordinates, relative to the quad and normalized in the range of 0.0 to 1.0. These will be stored in a pair of 4D vectors, containing (1,x,x²,x³) and (1,z,z²,z³), providing pre-calculated powers of the coordinates. The vertex format is shown below:

typedef struct _SPLINEVERTEX
{
    D3DXVECTOR4 x;
    D3DXVECTOR4 z;

    _SPLINEVERTEX(float fX,float fZ) {
        x.x=1.0f; x.y=fX; x.z=fX*fX; x.w=fX*fX*fX;
        z.x=1.0f; z.y=fZ; z.z=fZ*fZ; z.w=fZ*fZ*fZ;
    }
    _SPLINEVERTEX() {}

} SPLINEVERTEX,*LPSPLINEVERTEX;

Listing 5

// Create the vertex buffer
if (FAILED(hr=m_pd3dDevice->CreateVertexBuffer(PATCH_WIDTH*PATCH_WIDTH*sizeof(SPLINEVERTEX),
                           0, 0, D3DPOOL_MANAGED, &m_pVB)))
    return DXTRACE_ERR_NOMSGBOX( "CreateVertexBuffer", hr );

// Lock the vertex buffer
SPLINEVERTEX* pVertices;
if (FAILED(hr=m_pVB->Lock(0, 0, (BYTE**)&pVertices, 0 ) ) )
    return DXTRACE_ERR_NOMSGBOX( "Lock VB", hr );

// loop through the vertices and create grid
int i,j;
for (i=0;i<PATCH_WIDTH;i++) {
    float x=i/(float) (PATCH_WIDTH-1);
    for (j=0;j<PATCH_WIDTH;j++) {
        float z=j/(float) (PATCH_WIDTH-1);
        *pVertices=SPLINEVERTEX(x,z);
        pVertices++;
    }
}

// unlock the vertex buffer
m_pVB->Unlock();

// Create the index buffer
if (FAILED(hr=m_pd3dDevice->CreateIndexBuffer((PATCH_WIDTH-1)*(PATCH_WIDTH-1)*2*3*sizeof(WORD),
                                              D3DUSAGE_WRITEONLY,
                                              D3DFMT_INDEX16,
                                              D3DPOOL_MANAGED,
                                              &m_pIB)))
    return DXTRACE_ERR_NOMSGBOX( "CreateIndexBuffer", hr );

// Lock the index buffer
WORD* pInd;
if (FAILED(hr=m_pIB->Lock(0, 0, (BYTE**)&pInd, 0 )))
    return DXTRACE_ERR_NOMSGBOX( "Lock IB", hr );

// loop through the quads and create triangle indices
for (i=0;i<PATCH_WIDTH-1;i++) {
    for (j=0;j<PATCH_WIDTH-1;j++) {
        int base=i*PATCH_WIDTH+j;
        *pInd=base; pInd++;
        *pInd=base+1; pInd++;
        *pInd=base+PATCH_WIDTH+1; pInd++;
        *pInd=base; pInd++;
        *pInd=base+PATCH_WIDTH+1; pInd++;
        *pInd=base+PATCH_WIDTH; pInd++;
    }
}

// unlock the index buffer
m_pIB->Unlock();

Listing 6