Computer Laboratory

Adaptive Subdivision

As part of the undergraduate Computer Science course at the University of Cambridge, all third year students are required to complete a substantial project. I chose to do my project on the topic of subdivision: my dissertation title was, "Adaptive General-Degree Subdivision for 3D Surfaces".

Subdivision

Subdivision is the process or taking a coarse set of vertices representing a shape, and adding more vertices to make the shape smoother. Subdivision can be applied to both 2D and 3D shapes. The method works by iteratively calculating the weighted averages of positions of neighbouring vertices: a vertex may then be moved to a new position, or a new vertex may be placed at the average position. Here is an example of a cube undergoing five iterations of a subdivision algorithm:

Step 0 Step 1 Step 2 Step 3 Step 4 Step 5

General-Degree

The degree of a surface tells you how smooth (continuous) it is, in strict mathematical terms. A surface with degree n continuity can be represented as a function f, of which the first n-1 derivatives are continuous. My subdivision implementation was general-degree, meaning that the continuity of the surfaces generated could be specified by the user.

Degree 1 Degree 3 Degree 5 Degree 7
Degree 1 Degree 3 Degree 5 Degree 7

Adaptivity

In general, an adaptive technique tailors itself to the input, either to give a better output, or to give the same output more quickly. In the case of subdivision, this means that no more vertices are added to regions which are already considered to have been subdivided enough. I identified two different ways of determining whether or not a region has been subdivided enough: size of polygons - if a polygon is very small, it will not make much visual difference if it is divided again; and curvature of the surface - a very flat region can be approximated by very few polygons.

Unadaptive    Adaptive
  
  

Bounded Curvature

Bounded curvature simply means that the curvature never collapses to zero, creating flat regions, or diverges to infinity, creating sharp corners. This has traditionally been hard to achieve, but since my supervisor had recently gained some useful results in his own research, I added the extra functionality to my project too. Bounded curvature can greatly increase the roundness of surfaces produced:

Without bounded curvature
  
With bounded curvature
Without bounded curvature      With bounded curvature

Footnote
This project wouldn't have been at all possible without my supervisor, Tom Cashman. His page has more advanced details about subdivision, and about this algorithm in particular. If you found this page at all useful, or have any questions, feel free to contact me at Daniel.Bates at cl.cam.ac.uk.