Unformatted text preview:

BlossomingRon GoldmanDepartment of Computer ScienceRice UniversityApplications• Subdivision• Differentiation• Conversion Between Bezier and Monomial FormMotivationLinear Functions -- SimpleL(t) = at ⇒ L(µs +λt) =µL(s) +λL(t){Linear}L(t) = at + b ⇒ L (1−λ)s +λt( )= (1−λ)L(s) +λL(t){Affine}Polynomial Functions -- Complicated P(t) = antn+ L+ a0⇒ P(µs +λt) ≠µP(s) +λP(t) ⇒ P (1−λ)s +λt( )≠ (1 −λ)P(s) +λP(t)Blossoming -- Key IdeaReplace complicated function P(t) in one variable by simple function p(u1,K,un) of many variables.Blossoming AxiomsNotationP(t) = polynomial of degree n in one variable t p(u1,K,un) = polynomial of degree one in n variables u1,K, unBlossoming Axiomsi. Symmetry p(u1,K,un) = p(uσ(1),K, uσ(n)) for any permutation σ of {1,K,n}.ii. Multiaffine p(u1,K,(1−α)uk+αwk,K, un) = (1 −α)p(u1,K,uk,K, un) +αp(u1,K, wk,K, un)iii. Diagonal p(t,K,tn1 2 3 ) = P(t)Terminology p(u1,K,un) is called the blossom of P(t)Properties of the BlossomExistence and UniquenessPower Law• Each Parameter u1,..., un Appears to at Most the First Power• Equivalent to Multiaffine AxiomDual Functional Property•P(t) = Bezier Curve of Degree n a ≤ t ≤ b• p(a,K,an −k1 2 3 ,b,K,bk1 2 3 ) = Pk= kth Bezier Control Point• Equivalent to Diagonal AxiomExamples (Existence)MonomialsP(t) = 1 ⇒ p(u1,u2,u3) = 1P(t) = t ⇒ p(u1,u2,u3) =u1+ u2+ u33P(t) = t2 ⇒ p(u1,u2,u3) =u1u2+ u2u3+ u3u13P(t) = t3 ⇒ p(u1,u2,u3) = u1u2u3CubicsP(t) = a3t3+ a2t2+ a1t + a0p(u1,u2,u3) = a3u1u2u3+ a2u1u2+ u2u3+ u3u13+ a1u1+ u2+ u33+ a0Basic Facts1. Every polynomial can be represented as a Bezier curve. (Today) Every polynomial can be generated by the de Casteljau algorithm for some control point € P0,K,Pn.2. The Bezier control points of a polynomial curve are unique. (Next Time)If € P0,K,Pn and € Q0,K,Qn are control points for the same Bezier curve € B(t) over the same parameter interval € [a,b], then € Pk= Qk, € k = 0,K,n.de Casteljau’s Algorithm012P(t)b − tb − tb − t∇∇∇t − at − at − aP0P1P2P3t − ab − tt − ab − tt − ab − t♦♦de Casteljau’s Algorithm -- Revisitedb–tb–tb–tb–tb–tt–at–at–at–at–at–atttb − tb − tb − tb − tb − tb − tt − at − at − at − at − at − aaaaaababbbbbaatabtbbtattbtt aLai1 2 3 bLbj1 2 3 tLtk{= p(a,K, ai1 2 3 ,b,K,bj1 2 3 ,t,K, tk1 2 3 )t =b − tb − aa +t − ab − abBezier Curve∇♦•••t–aaaaaabbbbtttaatattbttbbtabb••••••••••abtde Casteljau’s Algorithm -- Blossomed (Uniqueness)b–tb–tb–tb–tb–tt–at–at–at–at–at–au1u2u3b − u3b − u2b − u1u3− au2− au1− au2− aaaaaababbbbbaau1abu1bbu1au1u2bu1u2b − u2b − u1b − u1u1− au1− a aLai1 2 3 bLbj1 2 3 u1Lukk1 2 3 = p(a,K, ai1 2 3 ,b,K, bj1 2 3 ,u1,K,ukk1 2 4 3 4 )u =b − ub − aa +u − ab − abApplications• Subdivision• Degree Elevation• Differentiation• Conversion Between Bezier and Monomial Form• B-splinesSubdivisionSubdivision AlgorithmTake the Control Points Off the Two Lateral Edges of the Triangle.Dual Functional Property Pk= p(a,K, an −k1 2 3 ,b,K,bk1 2 3 ) Lk= p(a,K, an−k1 2 3 ,t,K,tk1 2 3 ) Rk= p(t,K, tn−k1 2 3 , b,K, bk1 2 3 )b–tb–tb–tb–tb–tt–at–at–at–at–at–atttb − tb − tb − tb − tb − tb − tt − at − at − at − at − at − aaaaaababbbbbaatabtbbtattbttDegree ElevationBlossom pn+1(u1,K, un+1) =pn(u1,K, ui−1,ui+1,K,un +1)i =1n+1∑n + 1Bezier Curve Pk= pn(a,K,an −k1 2 3 ,b,K, bk1 2 3 ) Qk= pn +1(a,K, an+1−k1 2 3 ,b,K,bk1 2 3 ) pn+1(a,K, an +1−k1 2 3 ,b,K,bk1 2 3 ) =n + 1 − kn + 1pn(a,K, an−k1 2 3 ,b,K,bk1 2 3 ) +kn + 1pn(a,K, an +1−k1 2 3 , b,K, bk −11 2 3 )Qk=n + 1 − kn +1Pk+kn + 1Pk −1Degree ElevationB(t)Q0= P0Q1Q2Q3Q4= P3P1P2•••••••HomogenizationPolynomial Functions -- ComplicatedP(t) = aktkk=0n∑⇒ P(ct) ≠ cnP(t) p(u1,K,cuk,K,un) ≠ cp(u1,K,uk,K,un)Homogenization -- Main IdeaSimplify P(t) and p(u1,K,uk,K,un) by introducing homogenizing variables.•P(t,w) = aktkwn−kk =0n∑⇒ P c(t,w)( )= cnP(t,w)• p (u1, v1),K,c(uk,vk),K,(un,vn)( )= cp (u1,v1),K,(uk,vk),K,(un,vn)( )Dehomogenization• P(t,1) = P(t) = p(t,K,t )• p (u1,1),K,(un,1)( )= p(u1,K,un)Homogeneous Blossoming AxiomsBlossoming Axiomsi. Symmetry p (u1, v1),K,(uk, vk),K,(un,vn)( )= p (uσ(1), vσ(1)),K,(uσ(n),vσ(n))( ) for any permutation σ of {1,K,n}.ii. Multilinear p (u1, v1),K,(uk, vk) + (rk,sk),K,(un, vn)( ) = p (u1,v1),K,(uk,vk),K,(un,vn)( )+ p (u1,v1),K,(rk, sk),K,(un,vn)( )p (u1, v1),K,c(uk,vk),K,(un,vn)( )= cp (u1,v1),K,(uk,vk),K,(un,vn)( )iii. Diagonal p (t,w),K,(t,wn1 2 4 4 3 4 4 )      = P(t, w)Cubic ExamplesP(t) = 1 ⇒ P(t, w) = w3p(u1,u2,u3) = 1 ⇒ p (u1,v1),(u2,v2),(u3,v3)( )= v1v2v3P(t) = t ⇒ P(t,w) = tw2 p(u1,u2,u3) =u1+ u2+ u33 ⇒ p (u1,v1), (u2,v2), (u3,v3)( )=u1v2v3+ u2v1v3+ u3v1v23P(t) = t2 ⇒ P(t,w) = t2w p(u1,u2,u3) =u1u2+ u2u3+ u3u13 ⇒ p (u1,v1),(u2, v2), (u3, v3)( )=u1u2v3+ u2u3v1+ u3u1v23P(t) = t3 ⇒ P(t,w) = t3 p(u1,u2,u3) = u1u2u3⇒ p (u1,v1),(u2,v2),(u3,v3)( )= u1u2u3Blossoming and Homogenization Commuteblossomhomogenizeck(kn)tkk∑ck(kn)tkk∑wn−k ckk∑ui1Luik∑ ckk∑ui1Luikvik +1Lvin∑blossomhomogenizede Casteljau’s Algorithm -- Homogenizedb–t˜ t ˜ t ˜ t bw − tbw − tbw − tbw − tbw − tbw − tt − awt − awt − awt − awt − awt − awaaaaababbbbbaa˜ t ab˜ t bb˜ t a˜ t ˜ t b˜ t ˜ t ˜ t = (t,w), a = (a,1), b = (b,1)(t, w) =bw − tb − a(a,1) +t − awb − a(b,1)Blossoming and Homogenization Commuteattaat abtabbaaa aabbbbbbtbttb–tb–tb–tb–tb–t b–tt–at–at–at–at–at–atttabbaaa aabbbbbw–tbw–tbw–tbw–tbw–tbw–tt–awt–awt–awt–awt–aw t–awt*t*t*aat*abt*bbt*at*t*bt*t*aaaaababbbbbaau*1bbu*1au*u*12 bu*u*1 2u*u*u*1 2 3bv –u11bv –u11bv –u11u –av11u –av1 1bv –u22bv –u33u –av11u –av22u –av33bv –u22u –av221abu*abubbuaaau –a3b–u3u –a2b–u2b–u1u –a1u –a1u –a1aab abbbbbaau111au u1 2bu u1 2u u u1 2 3b–u1b–u1u –a2b–u2blossomhomogenizehomogenizeblossomDifferentiation and the Homogeneous BlossomTaylor Expansion for Polynomials (Taylor’s Theorem)P(t + h) =P(k )(t)k!hkk =0n∑Binomial Expansion of Blossom (Multilinear Property) p(t + hδ,K,t + hδ) = (kn)p(t,K,tn −k1 2 3 ,δ,K,δk1 2 3 )hkk =0n∑t = (t,1), δ= (1, 0) and


View Full Document

Rice COMP 360 - Lecture Notes

Documents in this Course
Radiosity

Radiosity

42 pages

Radiosity

Radiosity

22 pages

Load more
Download Lecture Notes
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 Lecture Notes 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 Lecture Notes 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?