a pde-based fast local level set method

JournalofComputationalPhysics155,410–438(1999)ArticleIDjcph.1999.6345,availableonlineat(1988,J.Comput.Phys.79,12)andaddresstwoimportantissuesthatareintrinsictothelevelsetmethod:(a)howtoextendaquantitythatisgivenonlyontheinterfacetoaneighborhoodoftheinterface;(b)howtoresetthelevelsetfunctiontobeasigneddistancefunctiontotheinterfaceefficientlywithoutappreciablymovingtheinterface.Thisfastlocallevelsetmethodreducesthecomputationaleffortbyoneorderofmagnitude,worksinasmuchgeneralityastheoriginalone,andisconceptuallysimpleandeasytoimplement.Ourapproachdiffersfrompreviousrelatedworksinthatweextractalltheinformationneededfromthelevelsetfunction(orfunctionsinmultiphaseflow)anddonotneedtofindexplicitlythelocationoftheinterfaceinthespacedomain.ThecomplexityofourmethodtodotaskssuchasextensionanddistancereinitializationisO.N/,whereNisthenumberofpointsinspace,notO.NlogN/asinworksbySethian(1996,Proc.Nat.Acad.Sci.93,1591)andHelmsenandco-workers(1996,SPIEMicrolithographyIX,p.253).Thiscomplexityestimationisalsovalidforquitegeneralgeometricallybasedfrontmotionforourlocalizedmethod.c°1999AcademicPress1.INTRODUCTIONSinceitsinceptionin[20],thelevelsetmethodhasbeenusedtocaptureratherthantrackinterfaces.Theadvantagesofthiscapturingapproacharewellknownbynow.Themethodisstable,theequationsarenotunnecessarilystiff,geometricquantitiessuchascurvaturebecomeeasytocompute,andthree-dimensionalproblemspresentnodifficulties.See[22,18,16]forasurveyandreferences.Recentimprovementsincludethecomputationofmultiphaseflowsin[27,28]andunstablefrontsin[10,11].Aspointedoutin[1],“onedrawbackofthetechniquestemsfromtheexpense;byembeddingtheinterfaceasthelevelsetofahigherdimensionalfunction,aonedimensional1ResearchsupportedbyDARPA/NSFGrantonthinfilms,NSFGrantDMS9706827,andAROGrantDAAG55-98-1-0323.2Currentaddress:DepartmentofMathematics,UniversityofCalifornia,Irvine,CA92697.E-mail:[e-mail].4100021-9991/99$30.00Copyrightc°1999byAcademicPressAllrightsofreproductioninanyformreserved.APDE-BASEDFASTLOCALLEVELSETMETHOD411interfaceproblemhasbeentransformedintoatwodimensionalproblem.Inthreespacedimensions,considerablecomputationallabor.O.n3//isrequiredpertimestep.”Weremarkthattherearephysicalproblems,e.g.,multiphaseincompressiblefluiddy-namics[26,5],compressiblefluiddynamics[17],andmeltingiceproblems[7],inwhichtheadditionallevelsetequationaddsonlyafractionofextracomputingtime.Thisisbecausetheunderlyingfieldequationsmustalsobesolvedthroughoutallspace.Inthispaperwelocalizethelevelsetmethod.Ourlocalizationworksinasmuchgeneralityasdoestheoriginalmethodandallofitsrecentvariants[27,28],butrequiresanorderofmagnitudelesscomputingeffort.EarlierworkonlocalizationwasdonebyAdalsteinssonandSethian[1].Ourapproachdiffersfromtheirsinthatweuseonlythevaluesofthelevelsetfunction(orfunctions,formultiphaseflow)andnottheexplicitlocationofpointsinthedomain.Ourimplementationiseasyandstraightforwardandhasbeenusedin[9,14,27,28].Ourapproachispartialdifferentialequation(PDE)based,inthesensethatourlocal-ization,extension,andreinitializationareallbasedonsolvingdifferentPDEs.Thisleadstoasimple,accurate,andflexiblemethod.Equations(10)and(11)ofSection2enableustoupdatethelevelsetfunction(orfunctionsinthemultiphasecase)withoutanystabilityproblemsattheboundaryofthetubeusedtolocalizetheevolution.Suchequationsarenewanddonotappearin[1].Infact,thetechniqueusedin[1]hasboundarystabilityproblemsbecauseEq.(2)or(3)(theevolutionequationofthelevelsetfunction)issolvedrightuptothisboundary.Incontrast,inourmethod,thespeedofevolutiondegeneratessmoothlyto0atthisboundary.Thisisachievedbymodifyingtheevolutionofthelevelsetfunctionnearthetubeboundarybutawayfromtheinterface.Thismodificationeffectivelyeliminatestheboundarystabilityissuesin[1]andhasnoimpactonthecorrectevolutionoftheinterface.Thereinitializationstepwillresetthelevelsetfunctiontobeasigneddistancefunctiontothefront.Therearenoboundaryissuesinourdistancereinitializationorextensionofve-locityfieldofftheinterface.Bothofthesetasksinvolvesimplehyperbolicequationswherecharacteristicsflowoutofthetubeboundary;thus,upwindschemesremoveallboundarydifficulties.Wemakeuseofthestate-of-the-arthighorderENO[20,21]andWENO[13]schemestodoupdates,wheneveritisappropriatetodoso.Thelocallevelsetalgorithmpresentedhereisalmostaseasytoprogramasthegloballevelsetmethod,in-anynumberofdimensions.OurtechniqueasdescribedinSection2requiresnocomplicateddatastructurestostoretheinformationaboutthetubesaroundtheinterfaceotherthantheordinaryarray;thus,weeliminatethecomplexityandoverheadofupdatingsuchdatastructures.Anotherveryinterestingfastmethodwasrecentlydevisedin[23]and[12]inthespecialcasewhenthenormalvelocityofthefrontisagivennonnegativefunctionofposition.Thekeyobservationthereisthatth