√3 Subdivision

 

The SQRT(3) subdivision algorithm is a geometric method used to create increasingly smooth surfaces from arbitrary triangular mesh topologies. It was devised by & documented in 2000 by Lief Kobbelt at the Max-Planck Institute for Computer Sciences in Saarbrücken, Germany.

The algorithm derives its name from the method of splitting a singular triangle face into three other faces during each refinement iteration; Kobbel justifies this with “Applying the subdivision operator twice causes a uniform refinement with tri-section of every original edge (hence the name √3-subdivision)”.

 

Uses:

Subdivision algorithms, such as SQRT(3) (and Catmull-Clark), are regularly used in computer graphics software (such as those used in the development of video games & animated movies) to produce smoother meshes at closer draw distances. Whilst other popular (and perhaps more widely used) subdivision algorithms exist, Kobbelt’s SQRT(3) is reasonably simple to implement and it still cited and built upon in today’s academic papers.

 

Step-by-Step Breakdown:

I’ve implemented SQRT(3) in the past and (mostly for future reference) have typed up a simple breakdown of the algorithm below. For simplicity’s sake, I’ll start with a brief run-down followed by some simple examples. Be aware, that I’m making the assumption that any edge in the mesh will be winged by only two faces here, so don’t consider this a definitive implementation for all input cases. I’ll add some screenshots from my 3D implementation of the algorithm towards the end of this post. First however, some definitions from the original paper…

 

Facepoint – this is the resulting vertex when you average all the vertices in a particular face.
Edge Midpoint – this is simply the average of an edge’s start & end vertices (i.e. the middle of that edge).
Valence – this is the number of edges that are connected to a particular vertex.
1. For every face in the original mesh, we insert a new facepoint vertex.
2. For each vertex in each face, calculate B (a function of the vertex’s valence) via the below function (where n is that vertex’s valence)…
 

    \[B = \frac{4-2cos(2\pi/n)}{9n}\]

 
3. Each original vertex in that face is then relaxed following the equation below where…

P is the original vertex, B is a function of the valence of P (see above), n is the valence of P, S is the resulting relaxed vertex, and M is the average of all the surrounding vertices that ring vertex S.

 

    \[S = (1-B)P + BM\]

 
4. Next we create three new faces for each original face; from the newly relaxed vertex to that edge’s midpoint, then to that edge’s end point.
5. Finally the old edges are flipped to connect pairs of midpoints, create the newly subdivided faces.

 

The newly generated mesh will generally look smoother and more refined than the original mesh as each original face, has been subdivided into three new faces. To put the above steps into perspective, running the algorithm on a 2D mesh would go a little like this…

Let’s start with a simple 2D mesh consisting of four triangles in a larger triangle pattern.

Now we calculate the facepoint for each face (shown here in red).

Next we relax each original vertex using Kobbelt’s relaxation formula (in green here).

Here we create new edges between the facepoints we calculated and the new relaxed vertices.

Now we remove the original edges and create new ones between each face’s midpoint.

 

 

When completed on a 3D mesh (a triangular-based unit cube in this instance), the new relaxed vertex points are pulled towards the centre of the object, smoothing the mesh. The result of the first two iterations of the Kobbelt’s algorithm applied to a 3D unit cube are shown below.

 

Triangulated unit cube (before any iterations).

First iteration the subdivision.

After two iterations of Kobbelt’s algorithm.

 

Source Code:

You can download the source code for my 3D implementation of the Catmull-Clark Algorithm as part of my larger ‘Liopleurodon’ library by cloning one of my GitHub repositories located here. The Liopleurodon library is a collection of Maven projects, utilities, and R&D snippets. If you have Maven setup correctly, simply run the ‘mvn install clean’ command from one of the project directories to build that project.

 


Image courtesy of Breiter via Flickr.