CS 284: CAGD 
Lecture #10 -- Th 9/28, 2006.

Preparation:

Warm-Up:  Devise an interpolating subdivision scheme

Topics: Subdivision

Introduction to "General Subdivision (with modification)" Techniques

• Conceptual introduction via iterated refinement
• cutting a rounded shape from paper by "repeated corner cutting."
• carving a rounded object from wood by cutting away edges.
• adding extra "bulges" on the segments of a linear spline (see warm-up).
• re-adjusting the mid-points of all control segments (see warm-up).
• averaging vertices among their neighbors.
  
 
• Key points about useful subdivision schemes:
• There are two components to any subdivision scheme, a topological 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.
 
• Special case study: 
  Interpolating four points with a cubic polynomial to find a new mid point for subdivision
   is the same as averaging two quadratic interpolants through three points each.
• The subdivision approach failed with the circle splines, because there is no affine invariance.

Conceptual Bridges to Splines, Fractals, and Affine Transformations

• Iterated affine transformations (Warren+Weimer, p 9)
• Defined by the transformation of three non-collinear points to three other ones;
• everything is then referenced to these three points with barycentric coordinates.
• Fractals: a set of contractive transformations (distance between any two points shrinks). Examples:
• Sierpinski triangle
• Koch snowflake
• Bezier curve (iterated mid-point evaluation) based on de Casteljau  (handout WW pp 15-18)
• Subdivision as the limit of an increasingly faceted sequence of polygons (WW p 19)
• each is related to successor by a simple linear transformation.
• Subdivision as a multiresolution rendering algorithm that generates increasingly dense plots 
• by taking convex combinations of points used in previous plots (WW p 24).
• Importance of the subdivision matrix (WW p 25) -- becomes clearer later.
  

Topological Limitations of the B-spline Control Mesh

• A rectilinear mesh of quadrilaterals can be nicely mapped onto a torus.
• It cannot be mapped onto a sphere without either
• crunching the u-v-coordinates together at the N- and S- poles, or
• or introducing vertices with valences different from 4.
• It cannot be mapped nicely onto surfaces of genus higher than 1.
• For these kinds of surfaces, we need a different, more general scheme ==> Subdivision surfaces!
• Remarks on the Topology of Surfaces

The Classical Subdivision Surfaces by Catmull & Clark

• 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.

Another Subdivision Surface

• A more detailed analysis what happens at irregular points is in the paper by Doo and Sabin.
• this paper also introduces matrices into the subdivision process,
• and the analysis of the eigenstructure to understand the behavior of the limit surface.

Reading Assignments:

New Homework Assignment: Create a Subdivision Surface

PHASE II --DUE: Th. 10/5/2006, 2:10pm:

The final  surface: SLF file and captured image.