CS 284: CAGD 
Lecture #11 -- We 10/1, 2003.

Take-home Quiz on Curves.

DUE: WEDNESDAY, October 1, 9:10am

---

Preparation:

Topic: Subdivision Surfaces

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 introducing vertices with valences different from 4.
• It cannot be mapped nicely onto surfaces of genus higher than 1.
• For these knds of surfaces, we need a different, more general scheme!

Remarks on the Topology of Surfaces

• Genus = an integer that indicates the number of handles (or tunnels) on a body bounded by a closed surface.
• Examples:

- - sphere has genus 0;
- - torus (doughnut) has genus 1;
- - a "figure-8 shaped pretzel" has genus 2.
- - Exercise: Determine the genus of various objects ...
• Integrating Gaussian curvature over a closed surface will yield a result that is equal to (1-genus)*720 degrees.
• In particular, if we consider a polyhedral surface and we sum the angle deficits/excesses at each of its vertices, we will get the same formula.

Angle deficit at a vertex is equal to: (360 degrees - sum of all angles of all the facets that come together at that vertex).
• Examples:

- - polyhedra of genus 0 will have an angle deficit of 720 degrees
     (e.g., a cube has 8 corners with angle sums of only 270 degrees);
- - polyhedra of genus 1 will have an angle deficit of 0 degrees;
- - polyhedra of genus 2 will have an angle excess of 720 degrees;
- - polyhedra of genus 3 will have an angle excess of 1440 degrees;
• The topology of a control mesh will have to match the topology of the desired surface.
• Consequences for the topology of control meshes:

Quadrilateral control meshes of genus 0 will have a "valence deficit" of 8 links;
- i.e., they may have 8 vertices with valence 3 (like a cube).
Quadrilateral control meshes of genus 1 will have a "valence deficit" of 0;
- i.e., they can be formed with regular recangular B-spline control meshes.
Quadrilateral control meshes of genus 2 will have a "valence excess" of 8 links;
- i.e., they may have 8 vertices with valence 5,
- - or perhaps, 4 vertices of valence 6,
- - or any combination of extraordinary points that produce an extra 8 links.
• Euler's rule concerning polyhedral (or meshed) objects.
  - - for genus 0:   V + F = E + 2
  - - generalization to objects of arbitrary dimension and arbitrary genus
  - - it tells us how many and what kind of extraordinary vertices our control mesh should have;
  - - this allows us to make "better", more regular, more symmetrical meshes that converge more quickly and more smoothly.

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 center of faces,
2.) new vertices at 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, there will only be quadrilateral meshes;
• there will also 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.

 
• 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.
• More on subdivision expressed in matrix form is in Chapter 2 of Warren & Weimer.

Current Homework Assignment: (to be done individually)

Experimenting with Curve Subdivision Schemes

• For instance, form an approximating curve by repeatedly chopping off the corners of the control polygon (as demonstrated in class).
• To make an interpolating curve, repeatedly subdivide the polygon edges by introducing a new vertex somewhere near its middle (or perhaps ratioed by the lengths of the adjacent segments of the control polygon -- or by the cube root of that ratio), then move that point to a place that will help to make an overall smooth curve (perhaps place on best-fitting circle).

Also submit a window capture for each applet, showing an interesting case of a control polygon with rather irregularly spaced points and sharp angles in the control polygon. Add to each one a description of how you chose to place the new subdivision vertices.

For more information see the instructional pages.

DUE: WED 10/8/03, 9:10am.

On line: Follow submission instructions on the instructional pages.

Hand in: Pictures of two interesting curves and descriptions of your subdivision schemes.

Next Reading Assignment: