CS 284: CAGD 
Lecture #12 -- Tue 10/02, 2012.

Preparation:

Evaluation / Analysis of Subdivision Schemes

Testing / Evaluation by Visual Inspection

• Any new subdivision scheme should be subjected to many tough test cases.
  Ideally the control points should be moved around interactively and continuously,
  because "transition cases" (e.g., extra inflection points) often show the weaknesses of a scheme.

Formal Analysis of Blending / Subdivision Methods

• If curve is formed with analytical functions (e.g., for Bezier, Lagrange, Circle Splines ...)
• Cⁿ continuity can readily be inferred form behavior of the polynomial or trigonometric functions.
• Gⁿ continuity needs a separate analysis; perhpas a bound on curvature can be established;
  or it may be sufficient to show that the velocity cannot get to zero (Circle Spline paper, section 3.4)


• Subdivision curves/surfaces are harder to analyze:
• How do you prove that final curve points do not have small fractal oscillations ?
• or that the tangents converge to a well-defined value at every point ?


• Doo & Sabin, extraorinary points in quadratic B-spline surfaces:
• Do not analyze the behavior of individual points, but of the whole ring of vertices around an extraordinary point.
• Do a discrete Fourier analysis of this ring of vertices; needs frequencies from w=0 to n/2 (n=valence) to capture all DoF.
• Repeated application of the subdivision matrix converges to an eigenvector corresponding to largest eigenvalue of the matrix.
• For the regular (valence 4) vertex we observe this behavior:
• Largest eigenvalue for w=0 is 1.0;
  
this guarantees translation invariance of the process (i.e., does not "slide away").
• Largest eigenvalue for w=1 is 0.5;
  
this implies that the region around this vertex shrinks towards an affinely distorted regular n-gon;
this n-gon is used to define a reference plane (= tangent plane).
• Second eigenvalue for w=0 is 0.25; describes hill/bowl-like behavior at this point.
• Largest eigenvalue for w=2 is 0.25; describes the amount of warping (into a saddle) at this point.
• Doo&Sabin found subdivision coefficients for the extraordinary cases that also give these same eigenvalues,
  
and thus also guarantee tangent plane continuity at these points (page 360): w_ij = (3+2cos(2p(i-j)/n))/4n
• Loop thesis, triangular spline N²²², (chapter 4):
• New extraordinary vertex V^k+1 = a_nV^k + (1-a_n)Q^k, where Q^k is the centroid of the surrounding vertices P^k_i
• Pick a_n for best performance; convergence occurs for -5/8 <  a_n < 11/8.
• Convergence proof in two steps: Show:  V^k  --> Q^k,  and also for each i:  P^k_i --> Q^k
• The explicit point of convergence is:  Q^k = b_nV⁰ + (1-b_n)Q⁰, where b_n = 3 / (11 - 8a_n ).
• Tangent Plane Continuity -- gives narrower bounds on a_n : -0.25 cos 2p/N < a_n  <  0.75 + 0.25 cos 2p/N.
• Again, use discrete Fourier transform to capture the behavior of all edges converging in V⁰.
• Tangent plane is defined by ring of neighbors only !
• Curvature Continuity --
• Rather than explicitly develop the periodic normal-curvature function around an extraordinary vertex,
  study the rate of change of the tangent function with respect to the subdivision process !
• Analysis shows: No choice of a_n can assure a well-defined curvature function around an extraordinary point !   :-(
• I.e., well-defined Gaussian curvature does not exist at extraordinary points !
• A reasonable choice that gives good-looking surfaces:  a_n = (3/8 + 0.25 cos(2p/N))² + 3/8

Discussion of: "Root-3 Subdivision" by Leif Kobbelt (SIGGRAPH 2000).

Discussion of: "Interpolatory Root-3 Subdivision" by Labsik and Greiner.

Mesh Data Structures

Winged-edge data structure for orientable 2-manifolds (Baumgart)

Half-edge data structure (e.g. http://www.flipcode.com/articles/article_halfedge.shtml)

A lean triangle hierarchy: just enough to do the dyadic Triangle subdivision for your homework

Assignments for Thu. Oct. 4, 2012:

1. What subdivision scheme are they using ?
2. What are the key additions to the basic scheme that they have made ?
3. Why do they prefer quadrilaterals ?
4. What is the basic approach to creating semi-sharp edges ?
5. What is the underlying model for cloth simulation ?
6. How is excessive wrinkling of the cloth avoided ?
7. What are virtual threads ? -- and what is their purpose ?
8. What is the data structure to make collision detection efficient ?
9. How is it made possible to apply texture maps and procedural shaders ?
10. What was one of the general implementation requirements for the Pixar production environment ?