1114. Subdivision curves2ReadingRecommended: Stollnitz, DeRose, and Salesin. Wavelets for Computer Graphics: Theory and Applications, 1996, section 6.1-6.3, A.5.Note: there is an error in Stollnitz, et al., section A.5. Equation A.3 should read:MV = VΛ23Subdivision curvesIdea: repeatedly refine the control polygon curve is the limit of an infinite process123PPP→→→L→∞= limjjQP4Chaikin’s algorithmChakin introduced the following “corner-cutting”scheme in 1974: Start with a piecewise linear curve Insert new vertices at the midpoints (the splitting step) Average each vertex with the “next”(clockwise) neighbor (the averaging step) Go to the splitting step35Averaging masksThe limit curve is a quadratic B-spline!Instead of averaging with the nearest neighbor, we can generalize by applying an averaging mask during the averaging step:In the case of Chaikin’s algorithm:r =−= KK101(,,,,)rrrr6Can we generate other B-splines?Answer: YesLane-Riesenfeld algorithm (1980)Use averaging masks from Pascal’s triangle:Gives B-splines of degree n+1.n=0: 1n=1: 11 1n=2: 11 11 2 1⎟⎟⎠⎞⎜⎜⎝⎛⎟⎠⎞⎜⎝⎛⎟⎠⎞⎜⎝⎛⎟⎠⎞⎜⎝⎛=nnnnrn,,1,021L47Subdivide ad nauseum?After each split-average step, we are closer to the limit curve. How many steps until we reach the final (limit) position?Can we push a vertex to its limit position without infinite subdivision? Yes!8One subdivision stepConsider the cubic B-spline subdivision mask:Now consider what happens during splitting and averaging:ACBACBsplitacaverageACBacbacbrepeat()1121459Math for one subdivision stepSubdivision mask:One subdivision step:ACBacACBsplitSplit:1()2=+a AB1()2=+c BC()11214averageACBacbAverage:a and c do not change1(2 )4B=++ba c1(6 )8=++ABC10Consolidated math for one stepSubdivision mask:One subdivision step:Consolidated math for one subdivision step:ACBacbrepeat()1121418440161044⎡⎤ ⎡ ⎤⎡ ⎤⎢⎥ ⎢ ⎥⎢ ⎥=⎢⎥ ⎢ ⎥⎢ ⎥⎢⎥ ⎢ ⎥⎢ ⎥⎣⎦ ⎣ ⎦⎣ ⎦abcABCLocal subdivisionmatrix ‘S’jP1jP+611Local subdivision matrix, cont’dTracking just the x components through subdivision:The limit position of the x’s is then:or as we’d say in calculus…OK, so how do we apply a matrix an infinite number of times??1230jj jjjP SP S SP S S SP S P−−−==⋅=⋅⋅==L0PSP∞∞=0limjjPSP∞→∞=12Eigenvectors and eigenvaluesTo solve this problem, we need to look at the eigenvectors and eigenvalues of S. First, a review…Let v be a vector such that:Sv = λvWe say that v is an eigenvector with eigenvalueλ.An nxn matrix can have n eigenvalues and eigenvectors:If the eigenvectors are linearly independent (which means that S is non-defective), then they form a basis, and we can re-write P in terms of the eigenvectors:iiinPav=∑λλ==M111nnnSv vSv v713To infinity, but not beyond…Now let’s apply the matrix to the vector X:Applying it j times:Let’s assume the eigenvalues are non-negative and sorted so that:Now let j go to infinity:If λ1> 1, then:If λ1< 1, then:If λ1= 1, then:10ii inn nii i i iiiPSP S a v a Sv a vλ== = =∑∑ ∑0jii inn njj j jii i i i i iPSP S av aSv a vλ== = =∑∑ ∑1230nλλλ λ>≥≥≥> L0lim liminjjii ijjPSP a vλ∞→∞ →∞==∑14Evaluation masksWhat are the eigenvalues and eigenvectors of our cubic B-spline subdivision matrix?We’re OK!But what is the final position?Almost done… from earlier we know that wecan find ‘a’, we but didn’t give specifics.λ=⎛⎞⎜⎟=⎜⎟⎝⎠111111vλ=−⎛⎞⎜⎟=⎜⎟⎝⎠2212101vλ=⎛⎞⎜⎟=−⎜⎟⎝⎠3314212v()11 1 2 2 2 33 3limjjjjPavavavλλλ∞→∞=++P∞=815Evaluation masks, cont’dTo finish up, we need to compute a1.Remember:Rewrite as:We need to solve for the vector ‘A’.(This is really just a change of basis for representing the vector P). The solution is:Now we can compute the limit position:We call u1 the evaluation mask.01122 nnPavav av=+ ++L011TPauP∞==0011122TTTnnAPauauPau−=⎡⎤⎡⎤⎢⎥⎢⎥⎢⎥⎢⎥=⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦VLLLLMMLL12012 nnaaPvv v Aa⎡⎤⎡⎤⎢⎥⎢⎥⎢⎥==⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦VMM MLMMM M16Evaluation masks, cont’dNote that we need not start with the 0thlevel control points and push them to the limit. If we subdivide and average the control polygon jtimes, we can push the vertices of the refined polygon to the limit as well:So far we’ve been looking at math for a subdivision function f(x).For a 2D parametric subdivision curve, (x(u), y(u)),just apply these formulas separately for the x(u) and y(u) functions.1jjTPSP uP∞∞==917Recipe for subdivision curvesThe evaluation mask for the cubic B-spline is:Now we can cook up a simple procedure for creating subdivision curves: Subdivide (split+average) the control polygon a few times. Use the averaging mask. Push the resulting points to the limit positions. Use the evaluation mask.()1141618Derivative of subdiv. functionWhat is the tangent to the cubic B-spline function?Consider the formula for P again:Where:Derivative is just:11 1 2 2 2 33 3jjjjPavavavλλλ=+ +jleftPcenterright⎡⎤⎢⎥=⎢⎥⎢⎥⎣⎦'lim lim12jjjcenter left center leftPx→∞ →∞−−==∆12 311211(1) 1 ( ) 0 ( ) 12411 2jj jjPa a a−⎛⎞ ⎛ ⎞ ⎛ ⎞⎜⎟ ⎜ ⎟ ⎜ ⎟=+ +−⎜⎟ ⎜ ⎟ ⎜ ⎟⎜⎟ ⎜ ⎟ ⎜ ⎟⎝⎠ ⎝ ⎠ ⎝ ⎠2220101'lim122jTjjPaauP→∞⎛⎞⎜⎟+⎛⎞===⎜⎟⎜⎟⎝⎠⎜⎟⎝⎠1019Tangent analysis for 2D curveWhat is the tangent to a parametric cubic B-spline2D curve? Using a similar derivation to what we just did for a 1D function (but omitting details):Thus, we can compute the tangent using the second left eigenvector! This analysis holds for general subdivision curves and gives us the tangent mask.,,,,limCenter j Left jCenter j Left jjPPPP→∞−=−t2020TTuPuP=20Approximation vs. Interpolation of Control PointsPrevious subdivision scheme approximated control points. Can we interpolate them?Yes: DLG interpolating scheme (1987)Slight modification to subdivision algorithm: splitting step introduces midpoints averaging step only changes midpointsFor DLG (Dyn-Levin-Gregory), use:Since we are only changing the midpoints, the points after the averaging step do not move. 1(2,5,10,5,2)16r=−−1121Next time: Animation PrinciplesTopic:How does an artist makea “good” animation?Read:• John Lasseter. Principles of
View Full Document
Unlocking...