Approximate Subdivision Shading

Subdivision Shading is a new approach to compute normal fields of subdivision surfaces that was presented at SIGGRAPH Asia 2008.

Subdivision Shading

It’s a very simple idea that provides surprisingly good results. The idea is to interpolate the subdivision surface normals using the same procedure used for positions. The resulting normal field is not the actual surface normal, but looks smooth and doesn’t exhibit some of the artifacts characteristic of subdivision surfaces at the extraordinary vertices.

The main disadvantage is that it looks too smooth compared to the real surface normal, but I’m not sure that’s necessarily bad. To avoid that problem the paper suggests blending the surface normals and the interpolated vertex normals so that the interpolated normals are used only in the proximity of extraordinary vertices.

The same idea can also be applied to the Approximate Catmull-Clark Subdivision Surfaces (Bezier ACC) proposed by Loop and Schaefer. Instead of constructing the normal from the cross product of the tangent patches, the normal can be interpolated directly using the same approximation used to evaluate positions. The resulting surface has G1 discontinuities around extraordinary vertices in both the geometry and the normal field. However, I haven’t been able to notice any artifact due to that in any of our test models.

This approach is quite efficient. It requires the same number of control points as Bezier ACC, but only one half of the stencil weights, because positions and normals are evaluated exactly the same way. The evaluation of the surface normal itself is also more efficient; evaluating a single 4×4 Bezier patch is faster than evaluating two 3×4 Bezier patches and computing a cross product.

However, the nicest thing about this scheme is that it facilitates watertightness when using displacement maps.

At Gamefest 2008 I mentioned that in order to achieve watertight surfaces when using displacement maps it was necessary to:

a) Sample textures in a watertight way.
b) Construct a watertight normal field.

[[acc tangents]] (right aligned)

In order to obtain a watertight normal field, adjacent patches need to compute the normals along their edges consistently.

The approach proposed in the ACC paper produces a smooth and continuous normal field, but the normals at extraordinary vertices and along the edges that surround them are not consistent. Patches around the extraordinary vertices have tangents that lie on the same plane, but their cross product does not yield exactly the same normal.

There are several ways of to solve that problem, but all of them too complicated to cover them in this post. On the other side, the normal interpolation approach does not suffer from that problem and provides a much more simple solution.

Watertight Texture Sampling

One of the problems when implementing displacement mapping is dealing with texture seams.

Texture seams are discontinuities in the parameterization. These discontinuities are always necessary unless the mesh has the topology of a disk, but in general meshes need to be partitioned into charts that are then parameterized independently.

[missing image]

This problem is not new. When using color and normal maps, texture seams usually cause color and lighting discontinuities. Artists usually deal with these artifacts by placing the seams on areas of the model, where they are less visible, so that the artifacts become less noticeable. However, when using displacement maps, the seams cause holes in the mesh, which produce much more visible artifacts that are harder to hide.

A Simple Solution

A simple solution to this problem is to manually alter the geometry along the seams to make it self intersect. While that does not result in watertight surfaces, the resulting holes are not visible. The main problem of this approach is that it requires artist intervention, creates open meshes, and only works for opaque surfaces; it would be nice to have more robust solutions.

Seamless Parameterization Methods

Fortunately this problem has been studied extensively and seamless parameterization methods have been developed. These are automatic parameterizations in which the chart texels are properly aligned across boundaries.

Displacement maps are generally not painted using traditional image editing applications, but created in specialized sculpting tools (such us ZBrush and Mudbox) or generated procedurally in attribute capture tools like xNormal. That means that it’s possible to store displacements using automatic parameterizations, since the artist does not need to edit the texture manually.

The most straightforward seamless parameterization method is the one used by ZBrush, which is very similar to the ones proposed in Meshed Atlases for Real-Time Procedural Solid Texturing. ZBrush maps every face of the mesh to a quad in texture space, so that all edges are either vertical or horizontal, and have the same length.
This method is very easy to implement, but has several problems:

  • It introduces a large number of seams in the mesh, which increments the number of vertex transforms.
  • It does not make efficient use of the texture space, because all faces, independently of their area, are mapped to quads of the same size.

ZBrush provides an option to group faces into larger charts while preserving the edge length and orientation, which helps reducing the number of vertex transforms. It also has an option to scale the charts in proportion to their surface area, but that breaks the seamlessness.

[missing image]

In order to alleviate these problems, another solution is to use rectangular charts (instead of single faces) to map them to texture-space quads.

That was first proposed in Seamless Texture Atlases, where rectangular charts are created by first clustering polygons into arbitrary sided charts and then partitioning them into quadrilaterals using a Catmull-Clark-inspired scheme:

[missing image]

An entirely different approach is described in Spectral Surface Quadrangulation. In this paper a quadrangulation is constructed from the optimized Morse-Smale complex of the natural harmonics of the surface. The main limitation of this approach is that it only handles closed surfaces, and requires manual selection of the eigenfunction to produce charts of the desired size. Spectral Quadrangulation with Orientation and Alignment Control solves these problems and also adds support for explicit constraints.

[missing image]

These two methods create quadrangulations without T-Junctions. That seems like a nice property, but Rectangular Multi-Chart Geometry Images shows that it’s possible to remove that constraint and still achieve smooth parameterizations, resulting in better parameterizations with less distortion.

The most interesting method is probably the one described in Designing Quadrangulations with Discrete Harmonic Forms. This method is even more flexible; instead of defining charts before the parameterization, it introduces singularity points in the mesh and computes the parameterization globally. Then the mesh can be cut connecting the singularity points arbitrarily.

Other methods try to achieve continuity between patches using constraints and parameterizing adjacent patches simultaneously. That’s for example the case of Matchmaker: Constructing Constrained Texture Maps, but it only minimizes the discontinuities and does not fully remove them.

For more information about parameterization methods these two surveys are a great resource:

Watertightness and Floating Point Precision

Modern hardware uses a floating point representation to interpolate texture coordinates. However, when using programmable tessellation hardware as specified by Direct3D11, interpolation is performed explicitly in the domain shader (or in the vertex shader when using instanced tessellation on pre-Direct3D11 GPUs). This is done to enable the use of higher order interpolation, but also allows the use of fixed point interpolation.

[missing image]

That’s important, because the use of floating point for interpolation causes some problems. Floating point values have more precision closer to the origin than farther from it. As a result, interpolation of texture coordinates along an edge closer to the origin will produce a different set of samples than interpolation along an edge that is farther from it. This is exactly what happens on texture seams and will result in small cracks in the mesh even when using a seamless parameterization.

If that seems surprising, then I’d recommend reading What Every Computer Scientist Should Know About Floating-Point Arithmetic.

It’s also important to note that a seamless parameterization and fixed point interpolation are not sufficient conditions to achieve watertightness. It’s also necessary to generate the displacement maps appropriately so that the values of the texels along the chart boundaries match exactly along both sides of the seams.

Zippering Methods

A different approach is to introduce a triangle strip connecting the vertices along the seam. These strips can be generated with the same tessellation unit used to generate the patches, by setting the tessellation level equal to 1 in one of the parametric directions. This solves the problem nicely, but requires rendering more patches, and introduces additional triangles that are almost degenerate.

[missing image]

Another interesting solution is the zippering method proposed in the Multi-Chart Geometry Images paper. The idea that the paper proposes is to sample the displacement (or the geometry image) on both sides of the seam and to use the average of the two samples.

The main problem of this approach is that it requires two texture samples along the seams, which means you have to take two samples in all cases, or use branching to take an extra sample on the seam vertices only.

The averaging method does not work for corners. Along the edges there are only two possible displacement values, one for each side of the seam. However, on corners there are more than two. Storing an arbitrary number of texture coordinates, and taking an arbitrary number of texture samples would be too expensive. A simple solution is to snap the corner texture coordinates to the nearest texel, and make sure that the displacement value for that vertex is the same for all patches that meet at that corner.

A cheaper solution that only requires a single texture sample, and that handles corners more gracefully is to define patch ownership of the seams. This is what I have proposed at Gamefest and SIGGRAPH last year.

By designating the patch owner for every edge and corner, all patches can agree what texture coordinate to use when sampling the displacement at those locations. That means that for every edge and for every corner we need to store the texture coordinates of the owner of those features. That’s a total of 4 texture coordinates per vertex, (16 for quads and 12 for triangles).

At runtime, only a single texture sample is needed; the corresponding texture coordinate can be selected with a simple calculation:

// Compute texture coordinate indices (0: interior, 1,2: edges, 3: corner)
int idx0 = 2 * (uv.x == 1) + (uv.y == 1);
int idx1 = 2 * (uv.y == 1) + (uv.x == 0);
int idx2 = 2 * (uv.x == 0) + (uv.y == 0);
int idx3 = 2 * (uv.y == 0) + (uv.x == 1);

// Barycentric interpolation of texture coordinates
float2 tc = bar.x * texCoord[0][idx0] +
            bar.y * texCoord[1][idx1] +
            bar.z * texCoord[2][idx2] +
            bar.w * texCoord[3][idx3];

Partition of Unity

The zippering methods produce watertight results independently of the parameterization. However, if the parameterization is not seamless or if the features of the displacement map are different on each side of the seam, then that will result in sharp discontinuities, not holes, but undesirable creases along the seams.

[missing image]

These problems can be avoided using a seamless parameterization and generating the displacement maps making sure that the displacements match along the seams. However, another solution is to use a partition of unity.

A partition unity is a method to combine multiple texture parameterizations to produce smooth transitions between them. The idea is to define transition regions around the seams, so that on those regions both parameterizations are used to sample the texture and the results are blended smoothly.

The zippering methods described before are just a special case of a partition of unity in which the blend function is just the unit step function.


There are many different solutions to achieve watertightness when sampling of displacement maps. I personally prefer the zippering methods, since they don’t impose any restriction on the parameterization of the mesh, and work with arbitrary displacement maps. They are easy to implement, and do not add much overhead to the shaders, even though they increase the number of texture coordinates. Note that even when using zippering methods to guarantee watertightness, the use of seamless (or nearly seamless) parameterizations is still useful, because they eliminate any visible crease or discontinuity along the seams.

Posted 1/1/2009 at 12:51 pm | Permalink
Very awesome post !!

It’s a shame that texture coordinates are true floats and not something like 16.16 fixed point. It basically forces you to use zippering. If you had fixed point you could make quadrilateral charts and put the corners exactly on pixels and make the edges the same length and I believe that would work.

Posted 1/1/2009 at 4:07 pm | Permalink
There’s actually nothing stopping you from representing texture coordinates using fixed point. The floating point precision problems only matter in the domain shader, where two instances of the same vertex at opposite sides of the seam must sample the same value from the texture. In the domain shader interpolation is done explicitly, and the math can be done in fixed point.

However, the problem is a bit more complicated than what I’ve described in the article. Hardware bilinear interpolation of texels is not symmetric. Sampling at 0.7 between A and B is not the same as sampling at 0.3 between B and A. Nearest filtering is not symmetric either, the result of sampling at 0.5 is undefined.

For this reason mapping the faces to equal-sized texture-space quads does not solve the problem entirely. It would also be necessary to make sure that seam edge vectors have the same sense.

All that is doable, but the zippering method is so much more simple and robust that I think is in most cases preferable.

Posted 1/1/2009 at 4:29 pm | Permalink
BTW, all that becomes even more complicated if you take mipmapping into account.

Posted 2/1/2009 at 5:29 pm | Permalink
Urg I wrote something but didn’t answer the challenge and when I hit back my comment was gone. >:|

Posted 2/1/2009 at 7:16 pm | Permalink
Ouch, that sucks. Posts that fail the challenge are discarded and do not go to the moderation queue, so I have no way of recovering it…

The foie gras parable

I loved this talk from Blue Hill’s Chef Dan Barber.

I’m not convinced that what the organic/ethical/slow food movement advocates is the most sustainable way of producing food and feed the world. For example, I’m not necessarily opposed to the use of technology to produce food, as long as it’s done responsibly. It’s the use of technology by profit driven food corporations what I’m concerned about.

Anyway, the talk made me feel saudades. I have this fantasy that one day I’d go back to Spain, buy a small farm, and live in a rural home raising pigs, hens, and sheeps. I’d then spend the rest of my days working in the farm, cooking, hiking in the area, and coding in my spare time.


I just published the immediate mode user interface (IMGUI) toolkit that we are using in our latest OpenGL SDK examples.

The purpose of the SDK examples is to show how to implement certain techniques using OpenGL. We did not want to spend too much time writing UI code, and we did not want the UI code to end up occupying more space than the code dedicated to the technique we are trying to showcase. IMGUI allowed us to accomplish these goals in an elegant way.

Here’s a simple example with two widgets:


static bool showButton = false;
ui.doCheckButton(none, "Show exit button", &showButton);

if (showButton) {
    if (ui.doButton(none, "Quit")) exit(0);


And this is what the result looks like:

[missing image]

One of the nice things is that, since the UI is being rendered in immediate mode, it’s very easy to create/modify widgets dynamically. For example, this is what happens when the check box is activated:

[missing image]

You can get the whole source code at the nvidia-widgets google project, and feel free to drop by the Molly Rocket IMGUI forums to share your feedback!


My better half has been accepted to UC Davis, and we’ll be moving there in the next few days. We are pretty excited; I think Davis will be a better place to raise our son. It’s also closer to the Sierra, so I’ll have the chance to spend more time in the backcountry.