Article electronically published on December 22, 2

MATHEMATICSOFCOMPUTATIONVolume73,Number248,Pages1913{1935S0025-5718(03)01623-5ArticleelectronicallypublishedonDecember22,2003MULTIVARIATEREFINABLEHERMITEINTERPOLANTBINHAN,THOMASP.-Y.YU,ANDBRUCEPIPERAbstract.WeintroduceageneraldenitionofrenableHermiteinterpolantsandinvestigatetheirgeneralproperties.Wealsostudyanotionofsymmetryoftheserenableinterpolants.ResultsandideasfromtheextensivetheoryofgeneralrenementequationsareappliedtoobtainresultsonrenableHermiteinterpolants.Thetheorydevelopedhereisconstructiveandyieldsaneasy-to-useconstructionmethodformultivariaterenableHermiteinterpolants.Usingthismethod,severalnewrenableHermiteinterpolantswithrespecttodierentdilationmatricesandsymmetrygroupsareconstructedandanalyzed.SomeoftheHermiteinterpolantsconstructedherearerelatedtowell-knownsplineinterpolationschemesdevelopedinthecomputer-aidedgeometricdesigncommunity(e.g.,thePowell-Sabinscheme).Wemakesomeoftheseconnec-tionsprecise.AsplineconnectionallowsustodeterminecriticalHolderreg-ularityinatrivialway(asopposedtothecaseofgeneralrenablefunctions,whosecriticalHolderregularityexponentsareoftendiculttocompute).Whileitisoftenmentionedinpublishedarticlesthat\renablefunctionsareimportantforsubdivisionsurfacesinCAGDapplications,itisratherunclearwhetheranarbitraryrenablefunctionvectorcanbemeaningfullyappliedtobuildfree-formsubdivisionsurfaces.Thebivariatesymmetricren-ableHermiteinterpolantsconstructedinthisarticle,alongwithalgorithmicdevelopmentselsewhere,giveanapplicationofvectorrenabilitytosubdivi-sionsurfaces.WebrieydiscussseveralpotentialadvantagesoeredbysuchHermitesubdivisionsurfaces.1.MotivationandintroductionLet=(i)mi=1beacolumnvectoroffunctionsdenedonRs.WesaythatisrenablewithrespecttothedilationmatrixMifthereexistsanitelysupportedsequenceaofmmmatricessuchthat=X2Zsa()(M
):(1.1)Renabilityisimportantforatleasttwo|notimmediatelyrelated|reasons.Ontheonehand,itallowsforthedenitionofanestedsequenceofshift-invariantspacesVj:=spanf(Mj
):2Zsg.Thisso-calledmulti-resolutionanalysis(MRA)isthekeytowaveletconstructionsandtheirassociatedfastlter-bankalgorithms[3].Ontheotherhand,functionscomposedfromlinearcombinationsReceivedbytheeditorJanuary,22,2002and,inrevisedform,March27,2003.2000MathematicsSubjectClassication.Primary41A05,41A15,41A63,42C40,65T60,65F15.Keywordsandphrases.Hermiteinterpolation,renablefunction,vectorrenability,subdivi-sionscheme,shiftinvariantsubspace,multivariatespline,Bernstein-Bezierform,wavelet,subdi-visionsurface.c2003AmericanMathematicalSociety19131914BINHAN,THOMASP.-Y.YU,ANDBRUCEPIPERofshiftsofarenablecanbecomputedusingasimplesubdivisionalgorithm.Consequently,suchfunctionscanbecomputedatanydesiredresolutionandanydesiredposition.Suchanadaptive\zoom-inpropertymakessubdivisioncurvesandsurfacesveryattractiveforinteractivegeometricmodellingapplications.Itisprobablyhardtoperceivehowfunctionslike(1.1),constructedonaregu-largridin\at-spaceRs,canactuallybeusedtomodelthekindof\free-formsurfacesofarbitrarytopologicaltypeencounteredingeometricmodellingandcom-putergraphicsapplications.Thisisanadvancerstmadeinthe1970'sinthecomputergraphicscommunitybyCatmull-Clark[9]andDoo-Sabin[14].Wecan-notaordthespacetorevieweventhebasicideaofsubdivisionsurfaceshere,butsimplymentionthattheconstructionofasubdivisionsurfaceistypicallybasedonrstconstructingwhatwenowcallarenablefunctionintheregulargridsettingfollowedbydesigningadditionalsubdivisionrulesattheso-calledextraordinaryvertices.Werefertotherecentbook[35]forthissubject.Thispaperfocusesontherststepmentionedabove:constructionofren-ablefunctions.Butinsteadofscalarrenablefunctions(i.e.,m=1in(1.1)),whichunderlieallexistingmethodsofsubdivisionsurfaces(e.g.,Catmull-Clark,Loop,Buttery),weareinterestedhereinthemoregeneralrenablefunctionvec-tors.Whiletheconceptofvectorrenabilityisextensivelystudiedbyanumberofresearchers|mainlyinconjunctionwiththeideaofmultiwavelets(see,e.g.,[2],[5]),toourknowledgethereisnoformalpublicationonanyattemptsofapplyingrenablefunctionvectorstothesettingofsubdivisionsurfaces.Someinitialat-temptsinthisdirection,basedontheresultsofthispaper,canbefoundintherecentconferencepaper[36].Itiswellknownthatsmoothnessofa(scalar)renablefunctionandshortnessofthesupportsizeofitsmaskaretwocontradictingrequirements.Forexample,itwasprovedin[21]thatnoC2interpolatingdyadicrenablefunctioncanbesupportedon[3;3]sandnoC1dyadicrenablefunctioncanbesupportedon[1;1]sinanydimensions.Therefore,toobtainsmootherrenableinterpolantswehavetomakecertaintradeossomewhere;vectorrenability,whichisbasedonincreasingthenumberofgeneratingfunctions,isoneinterestingapproach.Thisideaseemsparticularlyappealinginthesettingofsubdivisionsurfaceswhere,asmentionedearlier,oneneedstobeconcernedabouttheconstructionofspecialsubdivisionrulesatextraordinaryverticesand(consequently)onewouldliketokeepthesupportsizeoftheunderlyingrenablefunctionsassmallaspossible.AnothermotivationofourstudyofmultivariaterenableHermiteinterpolantsisperhapsmorefarfetched:existinginterpolat