Introduction

DirectX 8 Graphics introduced programmable vertex shaders, which allows the vertex processing of Direct3D to be replaced by application specific code.  This code, known as a vertex shader, performs the transformation and lighting of vertices, determining their final position, color parameters, and texture coordinates.

In this article, we will examine a novel method for rendering landscapes, which uses a vertex shader to perform real-time modeling of bicubic patches in the 3D pipeline.

Catmull-Rom Splines

Splines are a mathematical means of representing a curve, by specifying a series of points at intervals along the curve and defining a function that allows additional points within an interval to be calculated.  There are various functions available to approximate a curve, but in this article we will focus on the Catmull-Rom spline.

The points that define the curve are known as "Control Points".  One of the features of the Catmull-Rom spline is that the specified curve will pass through all of the control points - this is not true of all types of splines. 

Given the control points P₀, P₁, P₂, and P₃, and the value t, the location of the point can be calculated as (assuming uniform spacing of control points):

To put that another way:

This formula gives Catmull-Rom spline the following characteristics:

While a spline segment is defined using four control points, a spline may have any number of additional control points.  This results in a continuous chain of segments, each defined by the two control points that form the endpoints of the segments, plus an additional control point on either side of the endpoints.  Thus for a given segment with endpoints Pn and Pn+1, the segment would be calculated using [P_n-1, P_n, P_n+1, P_n+2].

Because a segment requires control points to the outside of the segment endpoints, the segments at the extreme ends of the spline cannot be calculated.  Thus, for a spline with control points 1 through N, the minimum segment that can be formulated is P₂<->P₃, and the maximum segment is P_N-2<->P_N-1.   Thus, to define S segments, S+3 control points are required.

Surface Representation with Splines

To express this algebraically, given function f(t,P_A,P_B,P_C,P_D) which calculates a point in a spline segment, then the calculation of a point (u,v) on a surface from control points P₁...P₁₆ would be:

f( v, f(u,P₁,P₂,P₃,P₄), f(u,P₅,P₆,P₇,P₈), f(u,P₉,P₁₀,P₁₁,P₁₂), f(u,P₁₃,P₁₄,P₁₅,P₁₆) )
                    Equation 3

Figure 5, below, illustrates the complete flow of data that occurs when calculating a point in a patch.

The processing cost of that operation is quite high to be performed every frame - even given the simplified form presented in Equation 2, the operation would require around 330 floating point operations for each generated 3D vertex.  Because of this, landscape meshes are typically created at load time.  In a large scene, memory footprint can become an issue, so it is may be necessary to store a local area and re-generate portions of a landscape on the fly as the viewer moves into them.  Doing so while maintaining a steady frame rate can require a bit of finesses, so as not to suffer periodic frame rate drops due to processing overhead.

Downloadable demo for this article
landshader.zip