Mesh Subdivision with the Loop Algorithm

Recently I have been learning more about Polygonal meshes and operations you can perform on them. One of the first operations that can be done on a mesh, that is a kind of cool, is subdivision. The basic idea is that you have a mesh that is very course (few polygons, rough) and we want a method that can construct a smoother mesh from this course mesh. This has been a popular method for constructing extremely smooth meshes for movies for many years.






This is an example very course mesh of a Camel. This mesh was not constructed this way by chance. An artist spent many hours adjusting verticies (points) and faces (polygons or triangles) on this mesh in order for subdivision to work well.

The Loop algorithm is a popular algorithm to perform mesh subdivision. One reason for its popularity is that it ensures that after subdivision the mesh is C2 continuous (smooth second derivative on surface) everywhere on the mesh except for at extreme points.

After lots of careful thought I decided to implement the algorithm in 3 steps.
  1. Add all of the new verticies for the mesh (easy)
    1. Take every edge and add a new point between the two points that define the edge
  2. Construct/fix all of the polygons in the mesh (not so easy)
    1. Add edges between all of the new points and update the face/polygon labels for these edges
    2. Most bugs came from this step
  3. Compute the new positions of the verticies on a copy of the mesh from 2 (almost easy)
    1. Simply use the old mesh to compute all of the neighbours for old points. 
    2. Computed the weighted sum of positions from neighbours and selected point (See loop Algorithm) and assign this position on the mesh copy
    3. For new points I used the new mesh to get the neighbours of each new point that was in the old mesh
    4. Last I had to run a query to get the edge between the points from (3). This got me the edge I should use to find the last two neighbour points for the Loop Algorithm
The coding also assumes some knowledge of how to work with a half-edge data structure for the mesh.

original mesh



After one subdivision



After two

After three



final mesh

Camel mesh after simplifaction




References:
  1. http://www.cs.ubc.ca/labs/imager/tr/2014/CartelModeling/Cartel_website/
  2. https://www.graphics.rwth-aachen.de/media/papers/sqrt31.pdf
  3. http://research.microsoft.com/en-us/um/people/cloop/thesis.pdf