Subdivision Surface

Yizhe Zeng

Objectives

Extras

Triangulation

I have implemented two triangulation methods. Here we make the assumption that all the faces on the mesh are convex.

First Method

For the first method, we connect the centroid of a face to all the vertices on the corner.
Triangulation Method 1

Second Method

For the second method, we randomly pick a vertex and connect to all the other vertices on the face.
Triangulation Method 2

Loop Subdivsion

Loop Subdivision applied on icosahedron


Loop Subdivision applied on Stanford Bunny
Original Mesh After Loop Subdivision

Butterfly Subdivsion

Butterfly subdivision is an interpolating scheme. As shown in the figure below, butterfly does not work very well in general.
Butterfly Subdivision on a Cheese King Mesh
Original Mesh First iteration with parameter .1 Second iteration with parameter .1

As we see from above images, butterfly did poorly on the Mesh. However, the original mesh is composed by faces with four vertices, since butterfly subdivision only applies on triangular faces. The way we tessellate the original meshes have huge impact on the quality of the butterfly subdivision scheme.


Butterfly Subdivision on a Cheese King Mesh with Different Tessellation Method
Original Mesh First iteration with parameter .1 Second iteration with parameter .1

√3 Subdivision

Compared with Loop Subdivision scheme, √3 Subdivision has a smaller growth on the number of triangular patches.

√3 Subdivision applied on helm mesh

Catmull-Clark Subdivsion

Unlike above subdivision scheme, Catmull-Clark Subdivison works on polygon meshes with arbitrary degree patches. Note that after applying Catmull-Clark subdivison, all the faces will have degree 4. Thus, if one want to keep applying other subdivision scheme, one may have to apply triangulation again.

Catmull-Clark Subdivsion on a Space Shuttle
Original Mesh
First Iteration
Second Iteration

Mechanismes

Integration with cglv

I have implemented a function to write the current mesh in memory into s3d file and viewed by cglv.
Integration with cglv
Read and Display from Terminal cglv

What I Learned

CS779 is my first course in computer graphics. Thus, through implementing my project I learned not only mathematical reasoning regarding those subdivision schemes, but also some basic knowledge regarding using openGL.

In addition, above subdivision schemes turns to be much more difficult when implementing with winged-edge data structure. It is better to write down what needs to be updated (faces, edges, vertices) and check every items on the list when you finish coding. In my implementation, I implement the basic winged-edge data structure, which store the pointers of end vertices and faces in each winged-edge, which is space efficient. For future improvement, one can implement a hash table which preserves vertex-face mapping, and it would be more efficient regarding processing speed.

At last, I learned that never bring your project into your holiday, DO YOUR DEMO BEFORE YOU LEAVE!!

Bibliography

E. Catmull,J. Clark. (1978). Recursively generated B-spline surfaces on arbitrary topological meshes. Computer-Aided Design 10(6), 350-355.

Holmes, R. (n.d.). Mesh-Man. Retrieved 5 8, 2013, from HOLMES 3D.NET: http://www.holmes3d.net/graphics/meshman/

Kobbelt, L. (2000). Root 3-Subdivision. SIGGRAPH '00 Proceedings of the 27th annual conference on Computer graphics and interactive techniques (pp. 103-112). New York: ACM Press/Addison-Wesley.

Loop, C. (1987). Smooth Subdivision Surfaces Based on Triangles. Mathematics thesis, University of Utah.

Nra Dyn, D. L. (1990). A Butterfly Subdivision Scheme for Surface Interpolation with Tension Control. ACM Transactions on Graphics, 160-169.

University, C. (2012). Subdivision Surfaces. Retrieved from Modeling for Computer Graphics: http://pages.cpsc.ucalgary.ca/~samavati/cpsc589/pdfs/nsubdiv2.pdf

University, S. (2010). Lecture Notes on Subdivision Surfaces. Retrieved from Stanford Graphics Lab: http://graphics.stanford.edu/courses/cs468-10-fall/LectureSlides/10_Subdivision.pdf

Wikipedia. (n.d.). Subdivision Surface. Retrieved 5 8, 2013, from Wikipedia: http://en.wikipedia.org/wiki/Subdivision_surface