Rice COMP 360 - Subdivision Matrices and Iterated Function Systems - D2350984

Home> Schools> Rice University> Computer Science (COMP) > COMP 360> Subdivision Matrices and Iterated Function Systems

Rice COMP 360 - Subdivision Matrices and Iterated Function Systems

Pages 22

Download Save

Unformatted text preview:

Subdivision Matrices and Iterated Function SystemsRon GoldmanDepartment of Computer ScienceRice UniversityPart I: Lagrange SubdivisionLagrange Interpolation€ P1€ P2€ P0€ P3€ P(t) = Lkn(t)Pkk=0n∑ € L0n(t),K,Lnn(t) = Lagrange Basis FunctionsLagrange SubdivisionLagrange Subdivision Matrices -- Integer Nodes € L =L0n(0) L1n(0) L Ln−1n(0) Lnn(0)L0n(1/2) L1n(1/ 2) L Ln−1n(1/2) Lnn(1/ 2)L0n(1) L1n(1) L Ln−1n(1) Lnn(1)M M M M ML0n(n / 2) L1n(n /2) L Ln−1n(n /2) Lnn(n / 2)                =1 0 L 0 0L0n(1/2) L1n(1/2) L Ln−1n(1/ 2) Lnn(1/2)0 1 0 L 0M M M M ML0n(n /2) L1n(n / 2) L Ln−1n(n / 2) Lnn(n / 2)                € R =L0n(n / 2) L1n(n /2) L Ln−1n(n /2) Lnn(n /2)0 L 1 L 0M M M M ML0n2n −12      L1n2n−12      L Ln−1n2n−12      Lnn2n−12      0 0 L 0 1                (n odd)Lagrange Subdivision € P =P(0)MP(n)          = control points L,R = subdivision matrices € L∗ P =1 0 L 0 0L0n(1/ 2) L1n(1/2) L Ln−1n(1/ 2) Lnn(1/2)0 1 0 L 0M M M M ML0n(n /2) L1n(n / 2) L Ln−1n(n / 2) Lnn(n /2)                P(0)MP(n)          =P(0)P(1/2)P(1)MP(n / 2)                € R∗ P =L0n(n /2) L1n(n / 2) L Ln−1n(n / 2) Lnn(n / 2)0 L 1 L 0M M M M ML0n2n−12      L1n2n −12      L Ln−1n2n −12      Lnn2n −12      0 0 L 0 1                P(0)MP(n)          =Pn2      Pn+12      MP2n −12      P(n)                   Lagrange Subdivision by Iterated Function SystemsControl Points and Subdivision Matrices• € P =P0MPn          = control points• L,R = subdivision matricesIterated Function System•€ LP= P−1∗ L ∗ P•€ RP= P−1∗ R∗ PSubdivision•€ P∗ LP= P∗(P−1∗ L ∗ P) = L ∗ P•€ P∗ RP= P ∗(P−1∗ R∗ P) = R ∗ PPart II: Bezier SubdivisionDe Casteljau’s Algorithm012B(t)1− t∇∇∇P0P1P2P3♦♦1− t1− t1− t1− t1− tttttttB(t) = Bezier Curve 0 ≤ t ≤1 P0,K, Pn = Control PointsBezier Curve∇♦••b–tP0P1P2P3B(r)•••••Bezier Subdivision∇♦••t–aP0= Q0P1P2P3= R3Q3= R0Q1Q2R1R2•••••••••Q(t)R(t) Problem: Given P0,K, Pn, find Q0,K, Qn and R0,K, Rn.De Casteljau’s Subdivision Algorithm0121− rQ1∇Q0= P0P1P2R3= P31− r1− r1− r1− r1− rrrrrrrQ2Q3= R0R1R2B(t) = Bezier Curve 0 ≤ t ≤1 P0,K, Pn = Original Control PointsDe Casteljau’s Subdivision Algorithm0121/ 2Q1∇Q0= P0P1P2R3= P31/ 2Q2Q3= R0R1R21/ 21/ 21/ 21/ 21/ 21/ 21/ 21/ 21/ 21/ 2€ Qk= Bjk(1/2)Pjj=0k∑ € Rk= Bn− jn−k(1/2)Pk +n− jj=kn∑Bezier Subdivision Matrices € L =B00(1/2) 0 L 0B01(1/ 2) B11(1/2) L 0M M M MB0n(1/2) B1n(1/2) L Bnn(1/ 2)            =1 0 L 01212L 0M M M M12nn2nL12n              =kj( )2j        € R =B0n(1/ 2) B1n(1/2) L Bnn(1/ 2)0 B0n−1(1/2) L Bn−1n−1(1/2)M M M M0 0 L B00(1/ 2)            =12nn2nL12n012n−1L12n−1M M M M0 0 L 1                =€ n−kn− j( )2n− j       Bezier Subdivision € P =P0MPn          = control points L,R = subdivision matrices € L∗ P =B00(1/ 2) 0 L 0B01(1/2) B11(1/ 2) L 0M M M MB0n(1/ 2) B1n(1/ 2) L Bnn(1/2)            P0MPn          =Q0MQn          € R∗ P =B0n(1/2) B1n(1/ 2) L Bnn(1/2)0 B0n−1(1/ 2) L Bn−1n−1(1/ 2)M M M M0 0 L B00(1/2)            P0MPn          =R0MRn         Bezier Subdivision by Iterated Function SystemsControl Points and Subdivision Matrices• € P =P0MPn          = control points• L,R = subdivision matricesIterated Function System€ • LP= P−1∗ L ∗ P• RP= P−1∗ R∗ PSubdivision•€ P∗ LP= P∗(P−1∗ L ∗ P) = L ∗ P•€ P∗ RP= P ∗(P−1∗ R∗ P) = R ∗ PRecursive SubdivisionP01P0P00P01P001P000P010P0112P1P11P111P10P100P101P110 M€ L€ L€ L€ L€ L€ L€ L€ R€ R€ R€ R€ R€ R€ RControl Polygons Generated by Recursive SubdivisionSummarySubdivision Matrices• Lagrange -- Lagrange Basis Functions of Fixed DegreeEvaluated at the Half Integers• Bezier -- Bernstein Basis Functions of Degrees≤n Evaluated at € t = 1 / 2Iterated Function Systems• € P =P0MPn          = Control Points• L,R = Subdivision Matrices€ • LP= P−1∗ L ∗ P• RP= P−1∗ R∗ P = Iterated Function SystemFour Approaches To SubdivisionSubdivision Algorithms• Neville’s Algorithm• De Casteljau’s AlgorithmSubdivision Formulas• Lagrange Polynomials• Bernstein PolynomialsSubdivision Matrices• Lagrange Basis Functions• Bernstein Basis FunctionsSubdivision by Iterated Function Systems (N–Dimensions)€ • LP= P−1∗ L ∗ P• RP= P−1∗ R∗ PLifting the Control Points to Higher DimensionsQuadratics€ P*=P1P2P3 111          =x1y11x2y21x3y31          Cubics€ P*=P1P2P3P4 1111 0001            =x1y11 0x2y21 0x3y31 0x4y41 1            Quartics€ P*=P11 0 0P21 0 0P31 0 0P41 1 0P51 1 1                =x1y11 0 0x2y21 0 0x3y31 0 0x4y41 1 0x5y51 1 1               Iterated Function SystemsObservations•€ DetP1P2P3 111          = Detx1y11x2y21x3y31          = 2 Area(ΔP1P2P3)•€ P1,P2,P3 not collinear € ⇔ DetP1P2P3 111          ≠ 0 ⇔ (P*)−1

View Full Document


School:
Email:
New Password:
Confirm Password:

Rice COMP 360 - Subdivision Matrices and Iterated Function Systems

Sign up for free to view:

Please select your school