Real-time Subdivision Surfaces on the GPU

A CS779 project by Thierry Delisle

Implementation in Vulkan based on the paper:

Efficient GPU rendering of subdivision surfaces using adaptive quadtrees

Wade Brainerd

Activision

NVIDIA

Stanford University

(Disclaimer: None of the content presented here is original, it is only a subset of the content presented in the paper by the authors.)

Project Goals

This project aims to implement and reproduce the paper "Efficient GPU rendering of subdivision surfaces using adaptive quadtrees". The goal being to make rendering of subdivision surfaces as fast and as easy as rendering triangles. Indeed, many subdivision schemes are either very hard process in parallel or require complicated pipelines that are hard to integrate with the normal rendering pipeline. The paper presents a method that is both efficient and does not intrude on many stages of the graphics pipeline. Making rendering subdivision surfaces fully encapsulated in the tessellation stage.

B-Spline patches

Catmull-Clark Subdivision is equivalent to using Tensor Product patches for regular quad faces, that is, faces where all vertices have both 4 adjacent edges and 4 adjacent faces. Therefore, quad-meshes can be efficiently rendered using B-Spline patches for each face, which allows independent processing of each face. This independence means both that the processing of each face can be done in parallel and that orthogonal rendering techniques (world to view transformation, animation, skinning, texturing) can be done on the subdivided mesh without needing to adapt the shader logic.

Subdivision Quadtrees

Catmull-Clark Subdivision can be used to subdivide irregular faces. Furthermore, the faces obtained will converge towards higher and higher proportions of regular faces. Such subdivision can be used to efficiently render irregular faces by pre-computing "Subdivision Plan" for irregular faces. These subdivisions can be expressed as weights on the original control points, which is effectively expressing Catmull-Clark Subdivision in matrix form.

These subdivision plans can be stored in a Quadtree, where leaf nodes (grey and blue in the picture) contains "Stencils": dense arrays of weights on the original control points. The surface can be evaluated simply by applying these stencils to the control points of the face (i.e., multiplying each control point by the corresponding weights) and then doing Bi-Cubic B-Spline evaluation. The difficulty here is that, while most of the subdivision itself uses the 4x4 Matrix from of Catmull-Clark, irregular faces do not align well with 4x4 Matrices and therefore vertices must be ordered so that which weight multiplies which vertex to calculate a control point can be found easily from the configuration data of the face. The data structure representing the configuration, valence, topology, etc. is the cornerstone of this subdivision scheme.

The result can be seen here, where faces sharing the same color uses the same stencils. Indeed, to reuse the same weights, faces do not need to share any control points, they simply need to have the same configuration. That is, the control points are given in the same relative order, the topology is equivalent, the vertices have the same valence, etc.

Note that in the case of irregular faces with a single extraordinary vertex, all other nodes can actually share several control points. Indeed, one level of Catmull-Clark Subdivision generates 25 control points from the 16 original control points of a single Bi-Cubic B-Spline patches. These control points correspond to 4 Bi-Cubic B-Spline patches which are exactly 1/4 of the original patch. Sharing control points can lead to requiring significantly less memory (and bandwidth). For example, leading to 30% increase in framerate when rendering the model "bigguy". This technique results in stencils similar to:

Semi-Smooth Creases

The subdivision scheme present paper also supports Semi-Sharp Creases, for this project the only case where a single edge is sharp was implemented; using the technique from [Niessner 2012]. This technique only works for otherwise regular faces with a single creased edge. Creases on other faces require subdividing the faces and correspondingly creating subdivision plans. This work has not been done by lack of time. Here is an example of various sharpness factors, the gaps in the mesh are due to the technique not handling the vertices which end a crease edge. Note that OBJ files do not support tagging semi-sharp edges, therefore the texture coordinates were used instead. Which prevents texturing meshes as both information are exclusive.

Sharpness: 0

Sharpness: 0.5

Sharpness: 1

Sharpness: 3

More Models

Tessellation factor: 1
(2 triangles for each original face)

Tessellation factor: 2
(8 triangles for each original face)

Tessellation factor: 8
(128 triangles for each original face)

The Viewer

All images and result were produced using a custom program built using :

This program handles loading and viewing .obj files as well as controlling subdivision parameters.

What I learned

The main thing I learned in this project is subdivision surfaces, more specifically Catmull-Clark Subdivision. It is a very nice scheme which happens to be simple yet have nice mathematical properties at the same time. I also learned various methods to handle corner cases like open meshes. This project was also particular in that it abstracted away a lot of the concepts of subdivision surfaces by applying subdivisions on abstracted face configurations rather than on actual mesh data. This made the techniques more reusable but much harder to implement, highlighting the importance of numbering schemes and good data structures to represent the configuration of a face. I also how important describing basic examples and relevant convenient can make significant differences for reproducibility.

Since this was the first time I used Vulkan, I learned many details and considerations that must be taken into account when implementing explicit graphics program. I also learned a lot on small but significant optimizations, often relying on equivalent matrix operations. This was also my first project using Tessellation Shaders which were surprisingly convenient to use for this project.