CS 284: CAGD 
Lecture #10 -- Tue 9/25, 2012.

Preparation: Read:

1.)  The seminal paper by E. Catmull and J. Clark:"Recursively generated B-spline surfaces on arbitrary topological meshes"

2.)  Paper by D. Doo and M. Sabin: "Behavior of recursive division surfaces near extraordinary points"

3.)  Chapters 2 and 3 from: C. Loop, "Smooth Subdivision Surfaces Based on Triangles" --  Some errata found in this thesis.

Warm-up: Understanding Subdivision and Its Analysis

Recursive Subdivision (cont.)

Key points about useful subdivision schemes:

• There are two components to any subdivision scheme, a topological one and a geometrical one:
• topology:  In a fixed way split the parametric domain of an edge or a face;
• geometry:  Move some of the old and newly created vertices to new locations (that promise to yield a smoother shape).
• The number of points (line segments) must grow at a geometrical rate with each generation.
• The newly introduced points should have a smoothing effect and converge towards a  limit function.
• This can typically be achieved with affine mapping schemes described with a subdivision matrix.
• The infinite application of this matrix then leads directly to a point on the curve or surface.
  
• The scheme should be independent of any coordinate system.
  
  

The Classical Subdivision Surfaces by Catmull & Clark

Presentation by: Laura and Eric

• This is a foundation for most modern subdivision algorithms
  
• A generalization of the B-spline scheme
• Can handle vertices with valences different from 4
• Can handle meshes with facets other than quadrilaterals
• One subdivision iteration calculates:
1. new vertices at the centers of all faces, 
2. new vertices "below" the centers of all edges, 
3. a new vertex position for each old vertex.
   
(This could be described as a matrix transformation on all the old vertices.)
• After the first iteration step, there will only be quadrilateral mesh facets;
• and from then on, there will be a constant number of extraordinary points:
• vertices of valence <>4 for each such original vertex.
• vertices of valence <>4 for each non quadrilateral mesh in the original control polyhedron.
• After the second iteration, any facet contains at most one extraordinary vertex.
• The extraordinary points will not disappear, but they will become more and more "isolated",
• being surrounded by ever shrinking irregular regions,
• and being separated by more and more quadrilateral meshes joining in valence-4 vertices,
• In these ever more dominating "regular" regions, the surface will approach a B-spline.
  
  

Doo, Sabin Paper: Focus on a Quadratic Subdivision Surface

Presentation by: Michael

• Extension of Chaikin's Corner Cutting algorithm (1974) to surfaces.
• For rectangular quad meshes this results in quadratic B-spline surface.
• Gain an understanding of the role of the subdivision matrix and its eigenvalues.
  
• Careful analysis and treatment of irregular points and convergence behavior around it.
• A more detailed analysis of what happens at irregular points and of the convergence behavior around it;
• this paper also introduces matrices into the subdivision process,
• and the analysis of the eigenstructure to understand the behavior of the limit surface.
• Discrete Fourier transform of the oscillations of the rings of neighboring vertices.

Charles Loop, Master Thesis: A Triangle-based Subdivision Scheme

Presentation by: Soham and Brandon

• Also allows to cover arbitrary topologies,
  
•   but now with the more flexible triangle meshes.
• An approximating scheme, based on triangular spline N²²²;
•   the resulting polynomials are of degree 4 (quartic).
  
• Also gives curvature continuity, except at the extraordinary points;
•   but still yields a well-defined tangent plane (G1-continuity) at these points.
  

How to efficiently and effectively read a paper to prepare for these discussions:

• Read: "Introduction" and "Conclusions;" look at figures and read captions.
  This should typically tell you WHAT the authors have done, and WHY.
• Now try to find out HOW they did it:
  Look for the appropriate sections that describe the key techniques.
• Also try to get an understanding what the limitations and caveats are of the described approach.
  Might there be things that the authors do NOT tell you ?
• You can probably skip the section on "Previous Work" or just skim it.
  
  
• Write down a few of the key points that you have learned,
  as well as some questions that are good for discussion in class.

Reading Assignments for Thu. Sep. 27, 2012: