Pyramid algorithms for curves and surfaces_Ron Goldman

《Pyramid algorithms for curves and surfaces_Ron Goldman》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、PyramidAlgorithmsRonGoldmanDepartmentofComputerScienceRiceUniversityReferenceR,Goldman,PyramidAlgorithms:ADynamicProgrammingApproachtoCurvesandSurfacesforGeometricModeling,MorganKaufmannPublishers,AcademicPress,SanDiego,2002.LinearityThemes•MathematicsisEas

2、y•RepresentComplicatedCurvesandSurfacesby(Successive)LinearInterpolationsPolynomialCurvesandSurfaces•LagrangeInterpolation--Neville’sAlgorithm•BezierApproximation--deCasteljau’sAlgorithm•B-Splines--deBoor’sAlgorithm•Blossoming--BlossomingRecurrenceI.Lagrang

3、eInterpolationandNeville’sAlgorithmStraightLines•QP•Equation=?LinearInterpolationStraightLine•P(t)=P+t(Q−P)•P(t)=(1−t)P+tQObservations•P(0)=P•P(1)=Q•Q=P(1)P(t)•P=P(0)LinearInterpolation•Q=P(1)P(t)•P=P(0)•Q=P(t1)P(t)•P=P(t0)LinearInterpolationRevisitedStra

4、ightLine•P01(t)=(1−f(t))P0+f(t)P1•f(t0)=0andf(t1)=1y−axis(t1,1)•t−t0y=t1−t0•t−axis(t0,0)LinearInterpolationRevisitedLinearInterpolation(t−t0)•f(t)=(t1−t0)•f(t0)=0andf(t1)=1.StraightLinet1−tt−t0•P01(t)=P0+P1t1−t0t1−t0•P(t0)=PP(t1)=Q•Q=P(t1)P01(t)•P=P(t0)Line

5、arInterpolationP01(t)P01(t)t1−tt−t0t1−t0t1−t0t1−tt−t0P0P1P0P1NormalizedUnnormalizedt1−tt−t0P01(t)=P0+P1t1−t0t1−t0P01(t0)=P0P01(t1)=P1QuadraticInterpolationP0•P1P01(t)•P012(t)P12(t)•P2ProblemFindasmoothcurveP012(t)suchthat:P012(t0)=P0P012(t1)=P1P012(t2)=P2Qu

6、adraticInterpolationLinearInterpolationt1−tt−t0•P01(t)=P0+P1t1−t0t1−t0t2−tt−t1•P12(t)=P1+P2t2−t1t2−t1QuadraticInterpolationt2−tt−t0•P012(t)=P01(t)+P12(t)t2−t0t2−t0VerificationofQuadraticInterpolationt2−tt−t0P012(t)=P01(t)+P12(t)t2−t0t2−t0i.P012(t0)=P01(t0)=

7、P0ii.P012(t2)=P12(t2)=P2t2−t1t1−t0iii.P012(t1)=P01(t1)+P12(t1)t2−t0t2−t0t2−t1t1−t0=P1+P1=P1t2−t0t2−t0P0=P012(t0)•P1=P012(t1)•P012(t)•P2=P012(t2)Neville’sAlgorithmforQuadraticInterpolationP012(t)t2−tt−t0P01(t)P12(t)t1−tt−t0t2−tt−t1P0PP21P012(tk)=PkCubicInter

8、polationP1P3P0P2ProblemFindasmoothfunctionP0123(t)suchthat:P0123(t0)=P0P0123(t1)=P1P0123(t2)=P2P0123(t3)=P3Neville’sAlgorithmforTwoQuadraticCurvesP012(t)P123(t)t2−tt−t0t3−tt−t1P01(t)PP12(t)P23(t)12(t)t