University of Texas at Austin CS384G - Computer Graphics Fall 2010 Don FussellSubdivision curvesUniversity of Texas at Austin CS384G - Computer Graphics Fall 2010 Don Fussell 2ReadingRecommended:Stollnitz, DeRose, and Salesin. Wavelets forComputer 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ΛUniversity of Texas at Austin CS384G - Computer Graphics Fall 2010 Don Fussell 3Subdivision curvesIdea:repeatedly refine the control polygoncurve is the limit of an infinite process ! P1" P2" P2"L! Q = limj "#PjUniversity of Texas at Austin CS384G - Computer Graphics Fall 2010 Don Fussell 4Chaikin’s algorithmChaikin introduced the following “corner-cutting” schemein 1974:Start with a piecewise linear curveInsert new vertices at the midpoints (the splitting step)Average each vertex with the “next” (clockwise) neighbor (theaveraging step)Go to the splitting stepUniversity of Texas at Austin CS384G - Computer Graphics Fall 2010 Don Fussell 5Averaging masksThe limit curve is a quadratic B-spline!Instead of averaging with the nearestneighbor, we can generalize by applying anaveraging mask during the averaging step:In the case of Chaikin’s algorithm: ! r = (K,r"1,r0,r1,K)! r =12,12" # $ % & 'University of Texas at Austin CS384G - Computer Graphics Fall 2010 Don Fussell 6Can we generate other B-splines?Answer: Yes Lane-Riesenfeld algorithm (1980)Use averaging masks from Pascal’s triangle:Gives B-splines of degree n+1.n=0: 1n=1: 1 1 1n=2: 1 1 1 1 2 1!!"#$$%&!"#$%&!"#$%&!"#$%&=nnnnrn,,1,021LUniversity of Texas at Austin CS384G - Computer Graphics Fall 2010 Don Fussell 7Subdivide ad nauseum?After each split-average step, we are closerto the limit curve.How many steps until we reach the final(limit) position?Can we push a vertex to its limit positionwithout infinite subdivision? Yes!University of Texas at Austin CS384G - Computer Graphics Fall 2010 Don Fussell 8One subdivision stepConsider the cubic B-spline subdivisionmask:Now consider what happens during splittingand averaging:A CBA CBsplitacaverageA CBacbacbrepeat! 141 2 1( )University of Texas at Austin CS384G - Computer Graphics Fall 2010 Don Fussell 9Math for one subdivision stepSubdivision mask:One subdivision step:Split:1( )2= +a A B1( )2= +c B CACBacA CBsplitaverageA CBa cbAverage: a and c do not change1( 2 )4B= + +b a c1( 6 )8= + +A B C! 141 2 1( )University of Texas at Austin CS384G - Computer Graphics Fall 2010 Don Fussell 10Consolidated math for one stepSubdivision mask:One subdivision step:Consolidated math for one subdivision step:A CBacbrepeat184 4 01 6 10 4 4! " ! " ! "# $ # $ # $=# $ # $ # $# $ # $ # $% & % & % &abcABCLocal subdivision matrix ‘S’jP1jP+! 141 2 1( )University of Texas at Austin CS384G - Computer Graphics Fall 2010 Don Fussell 11Local subdivision matrix, cont’dTracking the point’s value through subdivision:The limit position of the point is then:or as we’d say in calculus…OK, so how do we apply a matrix an infinitenumber of times??1 23 0j j jjjP SP S SP S S SP S P! !!= = " = " " = =L0P S P!!=0limjjP S P!"!=University of Texas at Austin CS384G - Computer Graphics Fall 2010 Don Fussell 12Eigenvectors and eigenvaluesTo solve this problem, we need to look at the eigenvectorsand eigenvalues of S. First, a review…Let v be a vector such that Sv = λvWe say that v is an eigenvector with eigenvalue λ.An n x n matrix can have n eigenvalues and eigenvectors:If the eigenvectors are linearly independent (which means that S isnon-defective), then they form a basis, and we can re-write P interms of the eigenvectors: ! Sv1="1v1MSvn="nvn! P = aivii=1n"University of Texas at Austin CS384G - Computer Graphics Fall 2010 Don Fussell 13To infinity, but not beyond…So, applying S to P:Applying it j times:Let’s assume the eigenvalues are non-negative and sortedso that:Now let j go to infinity:If λ1 > 1, then:If λ1 < 1, then:If λ1 = 1, then:1 0i i in n ni i i i i i iP SP S a v a Sv a v!= = = =" " "0ji i in n nj j j ji i i i i i iP S P S a v a S v a v!= = = =" " "0lim liminj ji i ij jP S P a v!"#" #"= =$ ! "1>"2#"3# L #"n# 0University of Texas at Austin CS384G - Computer Graphics Fall 2010 Don Fussell 14Evaluation masksWhat are the eigenvalues and eigenvectors of our cubicB-spline subdivision matrix?We’re OK!But what is the final position?Almost done… from earlier we know that wecan find ‘ai’, we but didn’t give specifics.( )1 1 1 2 2 2 3 3 3limj j jjP a v a v a v! ! !"#"= + +P!=! "1= 1 V1=111# $ % % % & ' ( ( ( ! "2=12V2=#101$ % & & & ' ( ) ) ) ! "3=14V3=2#12$ % & & & ' ( ) ) )University of Texas at Austin CS384G - Computer Graphics Fall 2010 Don Fussell 15Evaluation 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 basisfor representing the vector P).The solution is:Now we can compute the limit position:We call u1 the evaluation mask.0 1 1 2 2 n nP a v a v a v= + + +L01 1TP a u P!= =0011122TTTnnA PauauPau!=" #" #$ %$ %$ %$ %=$ %$ %$ %$ %$ %& '& 'VL LL LMML L120 1 2 nnaaP v v v Aa! "! "# $# $# $= =# $# $# $# $% &% &VM M MLMM M MUniversity of Texas at Austin CS384G - Computer Graphics Fall 2010 Don Fussell 16Evaluation masks, cont’dNote that we need not start with the 0th level control pointsand push them to the limit.If we subdivide and average the control polygon j times,we can push the vertices of the refined polygon to the limitas well:So far we’ve been looking at math for a subdivisionfunction 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.1j jTP S P u P!!= =University of Texas at Austin CS384G - Computer Graphics Fall 2010 Don Fussell 17Recipe for subdivision curvesThe evaluation mask for the cubic B-spline is:Now we can cook up a simple procedure forcreating subdivision curves:Subdivide (split+average) the control polygon a fewtimes. Use the averaging mask.Push the resulting points to the limit positions. Use
View Full Document
Unlocking...