Implementing subdivision surface schemes

The project aimed at implementing subdivision surface schemes to obtain smoother polygonal meshes. The schemes targeted included Loop Subdivision, Butterfly Subdivision, Doo-Sabin Subdivision and Catmull-Clark Subdivision. The University of Washington [1] base code was used to implement the schemes. Although the schemes were not successfully implemented, progress was made towards understanding the implementation issues and with more time, correct implementations seem possible.

Project Description:

In order to produce realistic shapes, one solution is to create polygon meshes with higher resolutions. This shifts the load of the work to the designers of the meshes who have to create denser meshes. Another consequence is once an object has been defined using a mesh, all the faces have to be rendered regardless of the abilities of the underlying hardware. This means that a high resolution shape would be drawn very slowly on a low-end hardware system even though the end user might be willing to sacrifice smoothness for performance. A better alternate would be to have an adaptive process which would take a low resolution mesh and produce smooth surfaces depending on the requirements of the end system. The solution is to use subdivision surfaces. Subdivision surfaces have provided the animation industry with the tools necessary to produce realistic shapes without painstakingly detailed polygonal meshes by creating smooth surfaces from polygonal meshes. The impressive results of subdivision surfaces were first demonstrated by Pixar in ÒGeriÕs adventureÓ [4], and have been used extensively in nearly all their production since then. The project goals were to implement four of the more popular subdivision schemes; a natural extension of the course material. The surfaces targeted were mostly convex, initially simple regular polygons and then towards more complex irregular polygons. Upon completion, a rich user-interface for editing the polygon meshes while observing the final surface in real time was to be developed.

Understanding Subdivision Surfaces:

Now we briefly look into the schemes prior to focusing on the implementation details. For a more detailed overview, SIGGRAPH course notes [2][3] are highly recommended. A subdivision is a process by which a polygon is subdivided into smaller polygons based on the schemes characteristics. A scheme can be classified as follows:

v    Interpolating vs. approximating

A polygon mesh is defined by a set of control points. At each level, a subdivision scheme would smooth the shape by introducing new vertices. If the scheme moves the original control points it is said to be approximating, otherwise it is interpolating since the smoothed surface would always pass through the original control points. An approximating scheme provides a more flexible and hence smoother scheme however it is difficult to modify the control points to get the desired shape since the final shape does not pass through the original control points.

v    Tri-mesh vs. quad mesh

Some subdivision schemes are defined for triangular meshes (where each face has 3 vertices) where as some are defined for quad meshes. A quad mesh can be pre-processed to reveal a tri-mesh which can be used with a tri-mesh scheme. However the pre-processing step can lead to artefacts since splitting of each quad face cannot be generalized.

v    Face splitting vs. vertex splitting

A face splitting scheme, also known as a primal scheme, would split the face of a polygon into many (usually four) new faces by introducing a new vertex in between a face and then splitting the face by introducing new edges from original vertices to the new vertex. A vertex splitting scheme, also known as a dual scheme, introduces new vertices for each face.

Understanding the base code

The base code consists of an MFC SDI application developed on the document/view architecture in Microsoft Visual C++ 6.0. Besides the classes required for the application framework, the mesh is represented in a Cell class. The Cell class uses Edge, Vertex and Face classes to associate vertices, edges and faces. One of the key features of the data structure is the ability to move about in a controlled manner.

á       Given the cell structure, a CellVertexIterator can be used to iterate over all the vertices by successive calls of next function of the iterator instance.

á       Given a vertex, a VertexEdgeIterator can be used to iterate over all the edges by successive calls to the next function of the iterator instance.

á       Given the edge e from A to B, the reverse edge can be obtained by e.Sym()

á       Given an edge, the next counter-clockwise edge at that vertex can be found by the Onext function of the edge instance, and similarly, the clockwise edge can be obtained by the Oprev function.

á       The location of a vertex can be obtained by the pos member variable of type Vec3.

In order to differentiate between graph elements (edges, vertices, faces) originally present at a level with those introduced by subdivision at that level, the data structure maintains an EVEN-ODD tagging scheme. In this scheme, all the original elements are tagged as EVEN, and the new elements are tagged ODD. At the start of each level of subdivision, elements present at that level are tagged as EVEN, new elements are added, and these are tagged as ODD. The elements are modified according to the schemes specification and the next level is started similarly.

As for the application structure, there is one drop down box for controlling the subdivision scheme to be used and a slider to control the level of subdivision. To add a subdivision scheme, you just add it to the strings in the drop down boxÕs properties, and modify the function void CControl::OnSelchangeSubstyle() to handle the new case by creating an instance of the class that implements that subdivision scheme.

Each time the subdivision scheme is changed, or the level of subdivision is changed, the CSubDoc ::Resubdivide function is invoked. It calls subdivideOnce, which marks all the graph elements as EVEN and divides the mesh once by introducing vertices in between each edge (splitting the edges) and faces. The new vertices are placed halfway between the original vertices at that level.

After the new graph elements labelled ODD have been introduced, the parenthesis operator of the subdivision class currently selected is invoked to move the graph elements according to the scheme.

Implementation

á       The butterfly scheme was implemented by creating a class CBSubdiv. The class implements the butterfly subdivision by iterating through all the ODD vertices of the cell. For each ODD vertex oV, the two EVEN vertices eV1 and eV2 used to create this new vertex are determined by iterating over all the edges of this vertex.

For each EVEN endpoint eV, the butterfly mask is applied and the result is used to place the new ODD vertex based. The application of the mask at each endpoint requires traversing because the neighbours of an EVEN vertex are not EVEN themselves as the edges have been split by addition of ODD vertices. This is solved by noticing the fact that each ODD vertex has only two immediate EVEN neighbours. So for each edge along eV we determine the other EVEN vertex along that edge, and use the its weighted position to determine its contribution to oV position.

á       The loop scheme was implemented by creating a class CLoopSubDiv. Since the loop scheme is approximating, we have to move both EVEN and ODD vertices. Since the vertices cannot be moved dynamically, we calculate the new positions and store them in an auxiliary array by their IDs. Once we have done all the computation, we can iterate through all the vertices and update the positions of each vertex. The traversals required to implement the loop mask are quite similar to those for the butterfly scheme.

Alternates to implementing!

Since implementing the subdivision schemes requires implementing an elaborate data structure to efficiently represent the mesh as well as provide a convenient access to processing it. An alternate is to use existing well implementations, such as the CGAL[5] which is a very extensive library of geometric tools. The CGAL provides an extensive set of subdivision surface methods as well as the required data structures. The methods used to implement subdivision surfaces are CatmullClark_subdivision, Loop_subdivision and DooSabin_subdivision. For instance, the code to perform Catmull Clark Subdivision on a polygon (Doo-Sabin and Loop are commented)specified by the user is given below :

Polyhedron P;

cin >> P; // read the .off

Subdivision_method_3::CatmullClark_subdivision(P,levels);

//Subdivision_method_3::DooSabin_subdivision(P, levels);

//Subdivision_method_3::Loop_subdivision(P, levels);

cout << P; // write the .off

 

Recommendations

A considerable effort was spent in understanding the Cell data structure. However it would have been much more yielding to have spent time on a standardized library such as the CGAL which has been thoroughly tested and extensively documented as well. This would have saved considerable time and effort as well as provide access to a large collection of algorithms already implemented in CGAL.

References:

1.     Assignment P3: Subdivision Surfaces, http://www.cs.cmu.edu/afs/andrew/scs/cs/15-463/99/pub/src/p3/p3.html

2.     Subdivision for Modeling and Animation tutorial, SIGGRAPH 1999 course notes, http://www.multires.caltech.edu/pubs/sig99notes.pdf

3.     Subdivision for Modeling and Animation tutorial, SIGGRAPH 2000 course notes, http://www.mrl.nyu.edu/dzorin/sig00course/

4.     T DeRose, M Kass, T Truong - "Subdivision surfaces in character animation", Proceedings of SIGGRAPH 1998, http://www.cs.rutgers.edu/~decarlo/readings/derose98.pdf

5.     Computational Geometry Algorithms Library, www.cgal.org.

6.     RyanÕs OFF Viewer, http://www.holmes3d.net/graphics/roffview/

Artefacts

Corner.off

The following images were generated by using CGAL to subdivide polygons in Object File Format (OFF) and use ROFFViewGL[6] to render the resultant OFF files.

1Original Corner Mesh

 

Figure 2Loop - Subdivision, 2 iterations.

 

Figure 3 Loop Subdivision, 4 iterations.

Figure 4 Catmull-Clark, 2 iterations

 

Figure 5 Catmull-Clark, 4 iterations.

Figure 6 Doo-Sabin, 2 iterations

Figure 7 Doo Sabin, 4 iterations

Cross.off

8Original Corner Mesh

 

Figure 9Loop - Subdivision, 2 iterations.

 

Figure 10 Loop Subdivision, 4 iterations.

Figure 11 Catmull-Clark, 2 iterations

 

Figure 12 Catmull-Clark, 4 iterations.

Figure 13 Doo Sabin, 2 iterations

Figure 14Doo Sabin, 4 iterations