Unformatted text preview:

Subdivision curvesReadingSlide 3Chaikin’s algorithmAveraging masksCan we generate other B-splines?Subdivide ad nauseum?One subdivision stepMath for one subdivision stepConsolidated math for one stepLocal subdivision matrix, cont’dEigenvectors and eigenvaluesTo infinity, but not beyond…Evaluation masksEvaluation masks, cont’dSlide 16Recipe for subdivision curvesDerivative of subdiv. functionTangent analysis for 2D curveApproximation vs. Interpolation of Control PointsUniversity of Texas at Austin CS384G - Computer Graphics Fall 2008 Don FussellSubdivision curvesUniversity of Texas at Austin CS384G - Computer Graphics Fall 2008 Don Fussell 2ReadingRecommended: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University of Texas at Austin CS384G - Computer Graphics Fall 2008 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 2008 Don Fussell 4Chaikin’s algorithmChaikin introduced the following “corner-cutting” scheme in 1974:Start with a piecewise linear curveInsert new vertices at the midpoints (the splitting step)Average each vertex with the “next” (clockwise) neighbor (the averaging step)Go to the splitting stepUniversity of Texas at Austin CS384G - Computer Graphics Fall 2008 Don Fussell 5Averaging 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 = (K ,r−1,r0,r1,K )€ r =12,12 ⎛ ⎝ ⎜ ⎞ ⎠ ⎟University of Texas at Austin CS384G - Computer Graphics Fall 2008 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 2008 Don Fussell 7Subdivide 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!University of Texas at Austin CS384G - Computer Graphics Fall 2008 Don Fussell 8One subdivision stepConsider the cubic B-spline subdivision mask:Now consider what happens during splitting and averaging:ACBACBsplitacaverageACBacbacbrepeat€ 141 2 1( )University of Texas at Austin CS384G - Computer Graphics Fall 2008 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 2008 Don Fussell 10Consolidated math for one stepSubdivision mask:One subdivision step:Consolidated math for one subdivision step:ACBacbrepeat184 4 01 6 10 4 4⎡ ⎤ ⎡ ⎤⎡ ⎤⎢ ⎥ ⎢ ⎥⎢ ⎥=⎢ ⎥ ⎢ ⎥⎢ ⎥⎢ ⎥ ⎢ ⎥⎢ ⎥⎣ ⎦ ⎣ ⎦⎣ ⎦abcABCLocal subdivision matrix ‘S’ jP1jP+€ 141 2 1( )University of Texas at Austin CS384G - Computer Graphics Fall 2008 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 infinite number 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 2008 Don Fussell 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 n x n 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: € Sv1= λ1v1MSvn= λnvn€ P = aivii=1n∑University of Texas at Austin CS384G - Computer Graphics Fall 2008 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 sorted so 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 2008 Don Fussell 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 ‘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 2008 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 2008 Don Fussell 16Evaluation masks, cont’dNote that we need not start with the 0th


View Full Document

UT CS 384G - Subdivision curves

Documents in this Course
Shading

Shading

27 pages

Shading

Shading

27 pages

Load more
Download Subdivision curves
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Subdivision curves and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Subdivision curves 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?