# A Fast and Hardware-Friendly Surface Tessellation Method

Here is some tessellation code I've written in 2002. At that time, I didn't find any useful resource so I had to probably reinvent the wheel. Anyway, it might save you some time if you found this blog while searching for «*example tessellation code*». This is adapted from the method I used in my Catmull-Rom subdivision surfaces code.

Consider the following patch which has been tesselated to a 3x4 regular grid and turned into a triangle strip:

I define each patch to be a quad that covers the [0..1]x[0..1] region of (u,v)=R². So it's bound by 0<=u<=1 and 0<=v<1. Let's call this the Grid Space.

Here is a linearized version showing each vertex's index:

I use a vertex buffer containing all my vertices, and an index buffer referencing those vertices.

So, if we put [0, 4, 1, 5, 2, 6, 3, 7, 11, 7, 10, 6, 9, 5, 8, 4, 8, 12, 9, 13, 10, 14, 11, 15, ...] in an index buffer, we can use it to reference our grid as a triangle strip.

Here are some pre-declarations:

// vector_t holds vertex coordinates in whatever format you may like // (I use a GL_T2F_V3F interleaved format for mine) class vector_t; // A vertex Buffer class (basically an array of vector_t) class vertex_buffer_t; // An index Buffer class (basically an array of unsigned ints) class index_buffer_t;

And this is some pseudo code for filling the buffers:

fill_vertex_buffer(vertex_buffer, u_segments, v_segments) { for (v=0; v<v_segments; ++v) { for (u=0; u<u_segments; ++u) { with vertex_buffer[u + v*(u_segments+1)] { // define a quad in model space: .x = (float)u/(float)u_segments; .y = (float)v/(float)v_segments; .z = .0f; } } } } fill_index_buffer(index_buffer, u_segments, v_segments) { // For u_segments = 3 and v_segments>3, the result will be: // [0, 4, 1, 5, 2, 6, 3, 7, 11, 7, 10, 6, 9, 5, 8, 4, 8, 12, 9, 13, 10, 14, 11, 15, ...] // local variables: u_vertex_stride = u_segments+1; // =4: if x is the Nth vertex of a row, x+4 is the Nth vertex on the next. index_count = (u_vertex_stride*v_segments)*2; // = we will generate an index buffer with 32 indices. u_twice_vertex_stride = u_vertex_stride*2; // fill the index buffer: for (index=0; index<index_count; ++index) { // x-coordinate in tesselated grid-space: x = (index/2)%u_twice_vertex_stride; if (x>=u_vertex_stride) x=(u_twice_vertex_stride-1)-x; // y-coordinate in tesselated grid-space: y = index/u_twice_vertex_stride; if (index&1 ^ y&1) ++y; // Index of the vertex in the vertex buffer: index_buffer[index] = y*u_vertex_stride + x; } }

Now, this `fill_vertex_buffer()`

function is quite useless, since we do not want to tesselate a single quad, but more likely a subdivision surface described by some function.

Here is a surface function declaration:

// A function of surface_function_t type returns a vector_t // which is function of two parameters u and v, whose value is between 0 and 1. // In order to be called a surface, such function must be continuous in [0 .. 1]². typedef vector_t (*surface_function_t)(float u, float v);

Ok, now here is the tesselator that subdivides and samples a *surface* along a *u_segments* x *v_segments* grid in [0..1] x [0..1] range and produces a triangle strip representing the resulting sampled surface in the given vertex/index buffers:

void tesselate( surface_function_t surface, vertex_buffer_t& vertex_buffer, index_buffer_t& index_buffer, unsigned short u_segments, unsigned short v_segments) { // Reserve enough space vertex_buffer.reserve((u_segments+1)*(v_segments+1)); // Declare loop increments const float u_inc(1.f / (float)u_segments)); const float v_inc(1.f / (float)v_segments)); // Compute surface points float v=.0f; for (unsigned short v_step=0; v_step<=v_segments; ++v_step) { float u=.0f; for (unsigned short u_step=0; u_step<=u_segments; ++u_step) { vertex_buffer[v_step*(u_segments+1) + u_step] = surface(u,v); u += u_inc; } v += v_inc; } // Fill the index buffer with indices automagically forming a single triangle strip: unsigned int u_vertex_stride = ((unsigned int)u_segments)+1; unsigned int index_count = (unsigned int)(u_vertex_stride*v_segments<<1); unsigned int u_twice_vertex_stride = u_vertex_stride<<1; index_buffer.reserve(index_count); for (unsigned int index=0; index<index_count; ++index) { unsigned int x,y; x = (index>>1)%u_twice_vertex_stride; if (x>=u_vertex_stride) x=(u_twice_vertex_stride-1)-x; y = index/u_twice_vertex_stride; if (index&1 ^ y&1) ++y; index_buffer[index] = y*u_vertex_stride + x; } }

## Leave a Comment