Generalized Barycentric Coordinates in Computer Graphics and

800_3GBC.pdf

KaiHorma nn,N.Sukumar

GeneralizedBarycentric

Coordinatesin

ComputerGraphics and

ComputationalMechanics

ii! Thisisapre-p ublicat ion versionofcontenttoappearinGeneralizedBarycent ric CoordinatesinComputerGraphicsan dComput ationalMechanics(CRCPres s, forthcoming2017.Allrightsreserved. )

Contents

Chapter1

!

Maximum-entropymeshfreecoordinatesincomputa-

tionalmechanics3

MarinoArroyo

1.1INTRODUCTION 4

1.2SELECTINGBAR YCENTRICCOORDINATES THROUGHEN-

TROPYMAXIMIZATION5

1.3INTRODUCING LOCALITY:LOCALMAXIMUM-ENTROPY AP-

PROXIMANTS9

1.4FURTHER EXTENSIONS12

1.5APPLICATIONS 14

1.5.1High-order partialdi

! erentialequations16

1.5.2Manifolda pproximation16

1.6OUTLOOK 16

iii

CHAPTER1

Maximum-entropy

meshfreecoordinatesin computationalmechanics

MarinoArroyo

LaC`aN,DepartmentofCivila ndEnvironmentalEngineeri ng

UniversitatPolit`ecnicadeCatal unya-BarcelonaTech

CarrerJordiGiron a1-3,08034Ba rcelona,Spain

CONTENTS

1.1Intr oduction.................................................4

1.2Select ingbarycentriccoor dinatesthroughentropy

maximization...............................................5

1.3Intr oducinglocality:localmaximum-ent ropyapproximants9

1.4Furthe rextensions..........................................12

1.5Applicatio ns.................................................14

1.5.1High-order partialdi

! erentialequations............14

1.5.2Manifolda pproximation............................16

1.6Outlo ok.....................................................16

C ONVENTIONALBARYCENTRICCOORDINATES aredefin edrela- tivetovertic esdefin ingtheboundaryofapolytope.Her e,wedevelopbarycen- triccoordinat esrelativetoacloudofverticess amplingnotonlytheboundary , butalsothe interiorofa regioninR d ,wi ththeobjectiv eofusingt hesebarycen- triccoordinat esasbasisfunctionstoapproximate part ialdi ! erentialequationsor parametrizesurfaces.Weshowthat entropymaximizationprovidesa rational way todefin esmoothbarycentri ccoordinates,but fortheresultingbasisfunctionsto belocal ized,andhenceleadtosparsematri cesinc omputationalmechani cs,en- tropymaximizat ionneedstobebiasedbyasuitable notionoflocality.Th ebasis functionsthatresultfromthi sapproachares mooth,reproducepoly nomials,are localizedaroundtheircorresp ondingvertex, andtheirdefiniti ondoesnotrelyon 1

2!GeneralizedBarycentricCoordinatesinComputerGr aphicsandComputationalMechanics

anun derlyingmeshorgridbutratheronless structuredne igh borhoodrel ations betweenvertices.Thus ,theycanbeviewedasmeshfreebas isfunctions[12,21,37] . Thetheoryan dpracticalevaluation behin dthesebasisfunctionsis reviewednext, andsele ctedapplicationsincomputation almechanicsarepresented.

1.1INTRODUCTION

Ast andardapproachtonumeri callyrepresenta functi onuoveradomainin"!R d istoex panditi ntermsofafinites etofbasi sfunct ions,thatis u h (x)= n ! i=1 ! i (x)u i ,(1.1) where! i : ¯ ""#Risthei"thbasi sfunctionandu i itscorres pondingcoe # cient. Sucharepres ent ationisthebasisofGalerkinmethodstosolvepar tialdi ! erential equations(PDEs),see[15]and alsoChapter??.Here,rathe rthanchoos ingapr iori thesetofb asisfuncti ons, suchaspiecew isepolynomialsdefinedoveramesh ,we initiallyleavetheirdefini tionopen,andthenm otivateandmakeexpli citthespecific choicesleadingtomaxim um-entropymeshfree basisfu nctions. Toshow convergenceofnu mericalsolutionsobtainedbyaGaler ki nmethodto theexactsol ution,thebasis functionsneedtosatisfy theso-call edreproducib ility conditions.Theseconditionsensu rethatpolynomialsup todegreepareexact ly representedbythebasisfunctions.For second- orderPDEss uchastheheate quation andthe mostcommonsy stemsarisi nginfluidands olidmechanics,consisten cy conditionsuptop=1ar ere quired atallpointsx$" n ! i=1 ! i (x)=1,(1.2a) n ! i=1 ! i (x)v i =x,(1.2b) forsomev ectorcoe # cientsv i $R d .If thesec onditionsaremet,t henanya # ne functionw(x)=a·x+b,whereaisave ctor inR d and·denotesthescalarprod uct, canbeex actlyre presentedin " asw(x)= " n i=1 ! i (x)(a·v i +b).

Interpretingthecoe

# cientsv i asth ecoordinat esofpointsorvertices,wecan naturallyassociateeachbasi sfunctiontoavertex,and viewthese tofvertices V={v 1 ,v 2 ,...,v n }aspoi ntssamplingthed omain".Wi ththisinter pretation, weonly needtoreq uirethebasisf uncti onstobenon-negative ! i (x)%0&x$",i=1,2,...,n(1.3) andrec all(1.2)torealizeth atthefunc tions! i (x),i=1,2,...,ndefineaset ofgen eralizedbarycentriccoordinates relativetoV.Adi!erencewithrespectto previouschaptersisthatn owweallowforinteriorver ticest othedomain, andfor multipleverticesalongaface ofthedomain. Maximum-entropymeshfreecoordinatesincomputationalmechanics!3 Figure1.1Setofve rtices Vintw odimensions,alo ngwiththeconvexhullP. Becausegeneralizedbar ycentriccoordinatesatxarecoe#cientsofaconvex combinationoftheverticesres ult inginx,se e(1.2b),it immediatelyfollow sthat suchbasisfunc tionscanonlybed efinedintheconvexhullofV,and there fore "!convV.Fu rtherexploitingelement aryfactsofconvexgeometry,itisposs ibleto characterizethebehaviorofconvexapproxim ationschemesofV,th atisbaryce ntric coordinatesdefinedinthevertex setV,ont heb oundaryofthe polytopeP= convV[4].Inparti cular, itcanbeshownthatifFdenotesafaceofPinthes ens e ofcon vexgeometry(inR 3

0-dimensionalfacesareextremepoints, 1-dimensional

facesareedges,an d2-dime nsionalfacesareapr operface s)andv i /$F,thenthe correspondingbasisfunction! i vanishesonF[4]. Immediateconsequencesofthis factarethat:(1)basisfunctionsofinterior ver - tices(redverte xinFigure1.1)van ishattheboundaryofP,(2) thebasi sfunctions ofex tremepointsv i ofPsatisfytheKronecker- deltaprop erty,! i (v j )=" ij ,and (3) onagi ven faceF(inbluei nFigure1.1),only thebasi sfunctionsofvert iceslying on

Farenon-z eroinF.Asa re sul tof(3),ifwedenotebyI

F thesetofin dicesofnod es lyingonF,th en(1.2a,1.2b)becom e " i!I F ! i (x)=1 and " i!I F ! i (x)v i =xforall x$F,th atisthebasi sfunct ionsofnode sonafacemaintain thefullapproximation propertiesonthatface.Furthermor e,( 3)alsoimpli esthatthebasi sfunctionsona facecanbede finedwi thoutre ferencetoinformation inthehigher-dimens ionalam- bientspace.Thes epropertiescanbe referredtoasaweak Kronecker-deltaproperty, whichfacilitateth eimpositionofboundarycondition sinthenum ericalapproxima- tionofPDEs .

1.2SELECTINGBAR YCENTRICCOORDINATES THROUGHEN-

TROPYMAXIMIZATION

Onexam ining(1.2a,1.3),itisclearthatfor eachpointx$P,th ebarycentr ic coordinates{! 1 (x),! 2 (x),...,! n (x)}canbevi ewedasa discreteprobability dis - tributionfornevents.Definingthebaryc entriccoordinatesthenb ecomesaprob lem ofs tatisticalinference.Intheabse nceofadditionalinformationandifonetrie sto avoidanybias,Lap lace'sp rincipleofin su # cientreasonwouldsu ggestselectin g

4!GeneralizedBarycentricCoordinatesinComputerGr aphicsandComputationalMechanics

! i (x)=1/nfori=1,...,n.Ye t,wedohaveadd itionali nformat ion,since(1.2b) statesthattheaver ageofthever texposition sisx.How toinc orporatet hispiece ofin formation,whilemakingachoiceofth eprobabilities(bar ycentriccoordin ates ) asun biasedaspossible? Oneclassi calanswertothisquestion ininformationtheory isJayn es'principl eof maximumentropy[17].Let usfirstintroduceth einformation entropy associ atedto afin iteprobabilitydis tributionbyconsideringacointos s.Inthiscase,therearetwo events(headsortails) thatforaperfectly bal ancedcoinhaveequal probabilit ies, p 1 =p 2 =1/2.In stead,wecouldconceiveane xtrem elyunbalancedc oinwith probabilitiesq 1 =0.99,q 2 =0.01.Af und amentalquestionininformationtheor y ishowt oquantifyt heunce rtaintyofaprobabilitydis tribution ,orinotherwords, howtoquant ifythe amountofinformationgainedbyr ealizingac ointoss.Itis obviousthatthebalanc edcoinlead stoamuchm oreuncertainoutcome,w hereas, fortheu nbalancedone ,wewilllearnverylittleby throwing itsinc eweknowthat theoutcomew illmostlikelybe heads.Itcanbes hownthatac anonicalmeasure ofun certaintyorinformationisgivenbytheS hann onentropyfunction H(p 1 ,p 2 ,...,p n )=" n ! i=1 p i logp i ,(1.4) wherethefunction xlogxisext endedbycontinuityatzero,i. e.0log0 =0.See[18] foradet ail edmotivationofthismeasureof informationanditspropert ies .By evaluatingShannonentropyonthep revioustwoprobabi litydistributions, wefi nd thatthefir stcoinisabou t12timesmoreun certainth anthese condone.Inf act ,it canbesh ownthat thefunctionin(1. 4)isstrict lyconcave withamaximumatthe uniformdistribution p i =1/n,i=1,2,...,n.Th islastfactsho wsthatmaxim izing theentrop yisconsistentwithLapl ace'sp rincipleofinsu # cientreason. Letusno wintro duceJayn es'principleusinganothersimp leexample,thatof adi cewithsixfac es,A 1 ,A 2 ,...,A 6 .Con sidertherandomfunctiont hatassigns toagive nfac eitsnumerical value,f(A i )=i.For aperf ect lybalanceddice,the averageoffis " 6 i=1 i/6=7/2.Su ppose,however,thatanaccu ratesamplemeanis computedforthisquantity afteral argenumberoftr ials,givingaresultof4.Cl early, thisnewpiec eofinformati onisinconsistent wit htheuniformprobabilitiesth atwe expectforaperfectly balanced di ce.Wewouldliketoincorporatethi sinformation inthe inference oftheprobabilitiesp 1 ,p 2 ,...,p 6 associatedtoeachfaceofthedic e, butclearl yitisnotsu # cienttouniquel ydeter minetheseprobabilities.Ja ynes' recipeistoconsider themost uncert ainprobabilitydistribut ion,thatis theone thatmaximi zesentropy,whilebeingconsi stentwiththeknownpart ialinformation [17].Mathemat ically,thisstatementcanbeformulatedasanopt imizationprogram withconstrain ts max p1,...,p6 " 6 ! i=1 p i logp i subjecttop i %0, 6 ! i=1 p i =1, 6 ! i=1 ip i =4, Maximum-entropymeshfreecoordinatesincomputationalmechanics!5 wherethelastcons traintenco destheadd itionalinformationaboutthesyste m. Thesolution tothisconstrainedopt imizati onproblemisp 1 =0.103,p 2 =0.123, p 3 =0.146,p 4 =0.174,p 5 =0.207,and p 6 =0.247,sh owingthatthehigher expectedvalueforfbiasestheprobabili tiestoward sfaceswithahighernumerical value. Goingbacktothe problemofin ferri ngthegener alizedbarycentricco ordi nates, itisno wclear thatapplicat ionofJaynes'p rincipleof maximumentropyleadsto anopt imizationprogramateachpointx$Pandgiven by max !1,...,!n " n ! i=1 ! i log! i subjectto! i %0, n ! i=1 ! i =1, n ! i=1 ! i v i =x, (1.5) wherethedepend enceonxonlyenters throughthelastvectori alconstraint.The solutiontotheprogramist hevalue ofthebaryc entriccoordin atessel ectedby entropymaximizationatx,! i (x),i=1,2,...,n.Be causetheentropyfunc tionis strictlyconcave,thisprogram hasauniquesolutionifandonl yifitisfeasi ble,that iswhene verx$ ¯ P[8].Thisme thod,review edinSection??,w asintro ducedin[35] togener atebasisfunctionsinp olygons. Figure1.2showsth ebasisf unctionsdefinedb yentropymax imizationforase tof verticesthatnotonlydefinesa polygon,butal sosampl esitsint erioranditsfaces.It canbeobs ervedt hatinagreementwiththegen eralresult sforcon vexapproximation schemesmentionedearlier ,thebasisfunctionassociated totheextremevertexv 1 is1atv 1 ,and theref oreallotherbasisfunctionsarez eroatth ispoint.Alsoi n agreementwiththegeneralr esults,theb asisfuncti onoftheinteriorve rtexv 3 vanishesontheboundaryofP,and thebasi sfunction! 2 doesnotsatisfy the

Kronecker-deltapropertybecausev

2 isonth ebou ndarybutis notanextreme point.Yet,thiss etofbasisfunct ionspresents asignificant dis advantagewhenus ed toappr oximatefunctionsingeneral,orsolu tionsofPDEsinparticular:the basis functionsarecompletelynonlo cal.The mostdramaticcaseisthatofbasisfunc tions ofin teriornodes,suchas! 3 ,wh ichspreadthrought heentiredomainand areas uniformasallowedbyth econ vexstructureoftheop timizat ionprogram.Th isis notade sir ablefeaturetoapproximatefun ctionsoverPbecausewithsuchabasi s itisn otpossib letode finealocalizedfeature,s ayaround vertexv i ,and correl ate thisfeaturew iththenodalvalueu i in(1.1) .Besidesthel ackoflocalresolution, suchaglobalsetof basi sfunction sleadstoad ens esti ! nessmatrixwhe nusedina

Galerkinmethodtoapprox imatepartialdi

! erentialequations[15]. Thisdiscussi onsuggeststhatindefiningthegener alizedcoordinatesbym ere entropymaximization,w ehavebeen"toounbiased".Wehaveign oredthe funda- mentalrequiremen toflocality,bywhichtheapproximationin (1. 1)atagivenpoint xshouldmorestrongly dependonco e#cientsu i associatedtoverticescloseto x. Localbasisf unctionsshould concentratetheir"mass"inthe vicinityoftheir asso- ciatevertex, wheretheirvalueshouldbe closerto1thanfori nstance! 3 inFigu re 1.2.

6!GeneralizedBarycentricCoordinatesinComputerGr aphicsandComputationalMechanics

0.080(a)(d)(b)(c)111000Figure1.2Basisfunctionssele ctedbyentropyma ximizationforthesetof

verticesshownin(a).Select edbasisfunctionsf orv erticesatextr emepositions ofP(b),alongaf aceofP(c),andintheinte riorofP(d). Maximum-entropymeshfreecoordinatesincomputationalmechanics!7

1.3INTRODUCING LOCALITY:LOCALMAXIMUM-ENTROPY AP-

PROXIMANTS

Clearly,localityandentr opymaximizationareconflicti ngobjec tives;atanygiven pointxtheformert riesthatonlyafewb asisfunctions,th oseofvertic escloser tox,ha vevaluessigni ficantlylargerthan0 whileallothersarecloseto0,while thelattert riestohaveasunif ormvaluesof! i (x)asp ossi ble.Interestingly,there isanothe rfamilyofgeneralize dbarycentriccoor din atesassociatedtoVthatcan becharac terizedthroughanoptimizationprogramanalogousto thatin(1.5):the piecewiselinearbasisfunctions associatedtotheD elaunaytriangul ationofV.In- deed,ifthevertices inVareingeneralposition s(therearenod+1c osp herical verticesinV),then thereisauniq ueDelaunaytriangu lationwi thv erticesVand thesoluti ontotheconstrainedopti mizati onproblem min !1,...,!n n ! i=1 ! i |x"v i | 2 subjectto! i %0, n ! i=1 ! i =1, n ! i=1 ! i v i =x, (1.6) aretheb arycentri ccoordinatesofthesimplexinthed-dimensionalDelaunaytrian- gulationwherexbelongs[30].Thus,at eachpointth ereareatmostd+1non-z ero basisfunction s.See[30,4]foradiscussionaboutthe situationin whicht he ver- ticesarenotingener alpositi ons.Argu ably,th esearethemostloc algeneralized barycentriccoordinatesassociatedto V. Comparisonof(1.5)and(1.6)suggest sc ombiningbot hobject ivefunct ionsto definethefollowin goptimizati onproblem min !1,...,!n # n ! i=1 ! i |x"v i | 2 + n ! i=1 ! i log! i subjectto! i %0, n ! i=1 ! i =1, n ! i=1 ! i v i =x, (1.7) whichdefinesPare tooptimaharmonizingt hetwoconflictingob jectives:inform ation theoryoptimalityan dlocality.Dependingon#,ori tsn on-dimensi onalcounterpart $=#h 2 wherehisthet ypicalspaci ngbetweenvertices ,thebasisfunctionswi ll moreclosel yresemblenonlocalappr oximantssuchasthoseshownin Figure1.2 orhi ghlylocalpiecewis ea # nebaryc entriccoordinatessupportedonaDelau nay triangulation.Infact,thelocalityparam eter#,con trollingtheaspectratioofthe basisfunctions ,canbedefinedlocallybyconsider ingthe follow ingobjectivefunction in(1.7) n ! i=1 # i ! i |x"v i | 2 + n ! i=1 ! i log! i , where# i istheas pectratiop arameterassociated tovertexi.W ecallth esetofbasis

8!GeneralizedBarycentricCoordinatesinComputerGr aphicsandComputationalMechanics

0 0.5 1 1.5 2 2.5 3 0

0.20.40.60.8

1 ! = [0.6 1.2 1.8 2.4 3 3.6 4.2 4.8 5.4 6] (a)(b)(c)Figure1.3Localmaximum-entrop y(LME)basisfunctions.(a)Selectedba- sisfunctio nsforaone-dimensionalv ertexset, wit hvaryingnondimensional aspectratioparameter ! i =" i h 2 ,se emaintext. (b)Basis functionsforan interiornodeinatwo-dimensio nalseto fve rt icesanddi ! erentaspectrat io parameters,and(c)representative basisfunc tionsofboundar ynodes. functionsobtainedthroughtheopt imizationprogram(1.7),! i (x),i=1,2,...,n, localmaximum-en tropy(LME)approximan ts.Figure1.3illustratestheLMEba- sisfuncti onsinoneandtwodimensions,alt houghthe formulat ioncanb eimple- mentedinprinciple inanydi mension.Thesmoothbasisfunction sclosel yrese mble othermeshfre ebasisfunctions,suchasthose generatedbythe movingleast-squares method[37].Thecruci aldi ! erence,however,isthat suchalternativemethodsdon ot produceingeneralgenerali zedbary centriccoordinat esbecausethebasisfunctions canben egative. ThefactthatLMEfunctionsar enon-negativ e,andthusc onvex approximantswithaweakKronecker-d eltaproperty, faci litatesth eimpositionof essentialboundaryconditionsi nthenumericalsoluti onofPDEs. Notethatw hile(1.6)is alinearprogramwith uniquesolu tiononl ywh envertices areingen eralpos itions,theone-param eterfamilyofoptimizationprogram sin(1.7) Maximum-entropymeshfreecoordinatesincomputationalmechanics!9 isnonli nearandstrictlyconvexasa resul toftheentropyfunction.Thus, sinceit isfeas ibleforallx$ ¯ P,it hasauni quesolu tion .Thus,theentropyfu nctional regularizesinsomesensetheline arprogrami n(1.6).Inf act,asshownin[4],t he entropyregularizationle adstoauniquewell-definedsetofgen eralizedDelaun ay barycentriccoordinatesinthelimi t##+'. Anotherimportantcon sequenceoftheentropyfu nctionalin(1.7)isthesmooth- nessoftheresu lti ngLMEbaryc entriccoordinates,ascomparedtot hoseres ulting from(1.6).Wh iletheDelauna ybarycentriccoor dinatesareon lyC 0 inP,since theyhavedis continuousderi vativesalongthefacesoftheDelaunaysimp lices,it canbes hownus ingtheimplicitf unctiontheoremth attheLMEappr oximantsare C " inPwithresp ecttox(alsowithresp ectto# i ). TheLMEbasis functi onshavebeend efinedsofarimplicitlythrou ghacon- vexconstrai nedoptimizationprogramwithasmanyun knownsasverticesinV. Throughstandarddual itymethods,however ,itispossibletoobtai nanalmostex- plicitformofthebasisf unctions. Fort his,letus firstdefineth epartitionfunction

Z(x,!)=

n ! i=1 exp # "# i |x"v i | 2 +!·(x"v i ) $ .(1.8) Then,theLMEbasisf unctionscan beexp ressedatanypoin tx$Pas ! i (x)= 1 Z(x,! # (x)) exp # "# i |x"v i | 2 +! # (x)·(x"v i ) $ .(1.9) Thisexpressi onisnotfullyexplicitbecauseto compute ! # (x)anu ncon strained optimizationmustbesolved:themi ninizationofthe strict lyconvexfunction logZ(x,!).Itcan beobser vedthat thefu nctionscanbeviewedasthe product ofaG auss ianfunctionaroundvert exv i ,an ormal izingfactor(Z)so thatallf unc- tionsadduptoone ,andanex ponent ialfactor thatdepend sonthe Lagrange mul- tiplier! # enforcingthelinearreprodu cingcondi tion.Examinationof(1. 9)shows that,strictly speaking,thesebasisfunction shaveglobalsupport.Howeve r,thanks tothef astdecayoft heGaussian function,forallprac tic alpurposes theycanbe consideredascompactlysupported. Fur thermore,thesumincalcu lationofZin (1.8)e ! ectivelyinvolvesonlyahandf uloftermscorrespondingt overtices in the neighborhoodofx,wh ichmakestheevaluat ionofthebasisf unctionse#cient.

Weemph asizethedependenceof!

# onp ositiontohighlightthef actthat at eachevaluat ionpoint,anunconstrainednon linearoptimization prob lemmustbe solved.Thisproblem,h owever,isonl yd-dimensional,hasauniquesolution,and canbee # cientlysolvednumerical lyusingNewton'sme thod.See[4,32,23]for mathematicalandcomputationaldetails ,aswel lasfortheexplicitexpressionst o computefirstandseconds patialderivati vesofth ebasisfunctions, andsee[13]for thecalcul ationofthegradientsofthebasisf unc tionsontheb oundaryofP. Weend thissecti onbypresentin ganalternativemethod tointr oducelocality intothemaxim um-entropy framework,whichinadditionprovidesameanstode - finestrict lycompactlysupportedbasisfu nctions.Itisveryeasyto defineaset ofnon -negativesmoothbasisfunctions% i (x)re lativetoV,lo calizedaroundthe

10!GeneralizedBarycentricCoordinatesinComputerGr aphicsandComputationalMechanics

correspondingvertex,andsatisfyingonly thezeroth-orderreprodu cingcon dition, " n i=1 % i (x)=1. Ind eed ,considerforinstanceasc alar,non-negativeandsmooth windowfunctionw:[0,+')"#R,wh ichdecayswhent heargumentislargecom- paredto1andsati sfiesth atall oddde rivativesuptokat0v anis h(toguarantee thattheeve nextensi onofwtoRisC k ).Then ,foralargeenough&thefuncti ons % i (x)= w(|x"v i |/&) " n j=1 w(|x"v j |/&) arecle arlynon-negative,locali zedaroundtheircorrespondingvertex v i withtypical width',sm ooth,andadduptoone.Fu rtherm oreifwiscompac tlysupported,then thefuncti ons% i (x)are alsocomp actlysuppor ted.Thus,ateachpoint,th enumbers % 1 (x),% 2 (x),...,% n (x)de fineadiscretepr obabi litydistribution,whichcon tains informationaboutlocality(% i (x)is largerif xisclose rtov i )bu tdoesnotsat isfythe first-orderreproducingconstrai nt(1.2b).Thisconstraintcanberecovered usingthe conceptofrelativeentropy,al socalledKu llback-Leiblerdis tance,whichmeasures theamountofi nformationrequ ire dtoobtainadiscreteprobabili tydistribution fromapriord ist ribution.Viewi ng% i (x),i=1,...,nasap rior distribution, the relativeentropycanbewrit tenas

D("|#(x))=

n ! i=1 ! i log ! i % i (x) .(1.10)

Minimizationofthisfunctionwithres pe ctto!

i ,i=1,...,n,su bjectto(1.2) and(1.3)w illproduc etheclosests etofbarycentriccoordinat estothepr iorfrom anin formationtheoreticalviewpoint ,i.e.introducingtheleastext rainformation [5,37].A direct calc ulationusingdualitym ethodsshowsthattheresult ingbasis function! i canbew ritten astheproductof% i andanothe rfactorenforcingt he linearreproducin gcondition,andthusthepriorandtherelati vemaximum-entropy functionshavethesamesuppor t.Inparticul ar,ifw(r)=e $r 2 and&=1/ ( #,then thesefunctionscoi ncidewiththeLMEbasisfunct ions.

1.4FURTHER EXTENSIONS

Wesum marizenextextensionstothe meshfreeandcon vexbasisfunctionsgen- eratedbytheLMEopti mizati onprogram.Anobv iousque stioniswhetherthese approximantscanbeextendedtohigher -order, thatis, ifinadditiontoexactlyre- producinga # nefunc tionsdueto(1.2),theycanbede signedtoe xactlyr eproduce higher-orderpolynomials.Thiswouldle adtoahigherrateofconvergencewhen approximatingPDEs.Focusingin1Dforsim plicity,anaiveex tensionwouldbeto maximizetheLMEobjective functions ubject to n ! i=1 ! i =1, n ! i=1 ! i v i =x, n ! i=1 ! i v 2 i =x 2 ,(1.11) ase tofconditi onsm etforinstancebyquadraticfini teelement spaces. However, asid entifiedin[4],conditionsin(1.11)t ogetherw iththenon- negativityconstraint Maximum-entropymeshfreecoordinatesincomputationalmechanics!11

(a)Maximum-entropy second order basis functionMoving-least-squares second order basis function(b)LME functionCell-maxent function(c)Figure1.4Extensionsofmaximum-entropy approximat ions.(a)Representa-

tivesecond-o rdermaximumentropybasisfunction,compar edtoamoving- least-squaresfunction,whichiswigglyandnegative atsomepoints.(b)C om- parisonofastandard LMEbasis funct ionandacell-basedmaximume ntropy basisfunction supportedonatriangula tion,whichresultsinastructure dad- jacencyrelationandmoree " cientcalculations toapproximatePDEsfora comparableaccuracy.(c) CombinationofLMEapproximantswith abound- aryrepres entationbasedonB-splines. ! i %0are unfeas ibleforalmostallpointsinP.Th ismayseemcon tradictoryat first sight,sincethere areexamplesofnon-n egativeapproximant sthatc anreproduce quadraticandhigher-orderf unction s,notablyB-splines.Oneoptionisthe giveup non-negativityandconsideranotionofentropy forsigne dprobabilitydistributi ons, whichhoweverdes troystheconvexstructu reoftheapproximationscheme, doesnot producegeneralizedbaryce ntriccoordinates,andcanleadtowi gglybasisfunctions [36,6].In sistin gonnon-negativity,theapparentcont radi ctionreferredtoabove isresol vedbynotingthatforthese cond-or derconsistencycon ditiontohol d,the coe # cientsthatmultiplyt hegenerali zedbarycentriccoordinatesdo notneedto bev 2 i .By designi ngappropriatecoe # cients,itispossibleto restore feasib ility,and thusdefinesec ond-ordermaximume ntropyapproximantsinmultipledime nsions [9,33],se eFigur e1.4(a).Thec onstructionoffeasi bleconstraints forhigher-or der reproducingconditions,however,isanop enquestion.

12!GeneralizedBarycentricCoordinatesinComputerGr aphicsandComputationalMechanics

Whenappliedto thenumericalsolution ofPDEsw ithGalerki nmethods,one aspectcomplicating theimplementationanddiminishingt hee # ciencyofLMEap- proximationsisthe"uncontrolled"sup portofth ebasisfunc tions.Thisisimportant becauseanytwobasisfun ctions withoverl appingsupportw illgenerateanentryin thesti ! nessmatrixres ultingfromtheGal erkinmethod.BecausetheLMEbasi s functionshavecompletelyun structuredsu pport,theunderlyingadjacencys truc- turesettingt hematrixstructureisqu itedense, butwithmanyvery smallentries [28].Toallev iateth is,amodificationoftheLMEbas isfunctionswaspr opose d,and calledcell-based maximumentropyapproximations,in whichpriorfunctions (% i (x) inthep reviousse ction)weredesignedtobe supportedontheak-ringofsimplice s aroundv i ofat ri angulation,seeFigure1.4(b).Inthisway ,theadjacen cystructure ofth esti ! nessmatrixisgi vendirectlybyt hetopology ofthetriangulat ionandis muchsparser,l eadingtomoree # cientcalculationsw ithoutnearlyanydegradation inaccur acy[25].Inthisrefere nce,thesm oothandc ompactlysuppor tedpriorfunc- tionswerecompu tedusingappro ximatedistancefunctions andR-functions,b ut othertechniq uesmayresultinbetterpriors. Wefinal lyreportonamethod thatusesLMEapprox iman tst orepresentdo- mainswithcomp lexgeometryands moothboundaries.Asdes cribeduptonow,the naturaldomainwheret heLMEapproxim antsaredefinedisth econvexhu llofthe Pofth esetofvert ices,orsub se tsofP,bu tinthisc asetheap proximantsdon ot satisfytheweakdelta-K roneckeron theboundary .However,thereisanincreasing awarenessontheimportanceofgeom etr icfidelit yinengineeringcalculations[ 16]. Infact, itisquitenatu raltob lendmax imum-entropyappro ximationswithany otherconvexapp roximationscheme, suchasmostapproximationmethodsused in computergraphics.Itissu # cienttoconsideran optimiz ationprogramsuchasthat in(1.7), inwhichsomeoft hebary centriccoordinate saretakenas data (theknown convexscheme)and therestaretheunknowns ofthepr oblem[31].For instance,in Figure1.4(c)onelaye roftensorprod uctB-s plinebasisfunct ions extrudedfroma B-splineboundaryrepresentat ionwasblendedwithLME functions.

1.5APPLICATIONS

TheLMEappro ximants andtheirextensionshavebeenadopted astrial andtest functionsinGalerkinmethod stosolv evariousPDEs,including linearandnonlinear elasticity[31,4,32,33],incompressib lesolid s[27] ,and fluidfl owproblems[19,26,

29].Inth esepr oblems,whichoften exhibitsmoothsolutions,LMEap proximations

providehighlyaccuratenum ericalapproximati onswithrelativelycoar sesetsof points,ascomparedtost andar dC 0 finiteelements. Furthermore,themeshfree basisfunctions canaccommodateverylargegriddis tortions inLagrangianlarge deformationsimulations[19,29].How ever,someapplicationstrulybene fitfrom the smoothnessoftheLMEapproximantsf orgen eralunstru ctured setsofpoints.We outlinenexttwoexamp le:thenumeri calapproxi mationofhigh-orderPDEsand theapprox imationofmanifoldsdefinedbyscattered set sofpoints. Maximum-entropymeshfreecoordinatesincomputationalmechanics!13 (a)(b)Figure1.5ApplicationoftheLMEappro ximants tohigh-or derPDEs.(a )In phase-fieldmodelsofbiomembranes ,theunknownfie lddefiningthes hapeof amov inginterfac eisgovernedbyafourth-orderPD E.T herefore,aGalerkin methodrequiressmo othbasisfunctions(withsq uareintegrableseco ndderiva- tives).Thephasefielddevelo pssharpg radients,c allingfora nadaptivesolu- tionandanappr oximations schemedev oidofGibbsphenomenon.Allthese conditionsaremetbyLME approximations .(b)show stwosna pshotsina dynamicalsimulationtrac kingtheshapeofadeformingv esiclemadeoutof afluidme mbra newithcurvatureelast icity,toge therwiththehydrodynamics ofthesur roundingfluid.The resolutionoftheset ofv ertices followsthesharp variationsofthephase-field.

14!GeneralizedBarycentricCoordinatesinComputerGr aphicsandComputationalMechanics

1.5.1High-orderpar tialdifferential equations

Manyphysic alphenomenaofinterestin scienceandengineeringaremo del edusing higher-orderPDEs.Forinstance,theK irchho ! -Loveequations ofthinshellsare fourth-orderPDEs.Similarly,manypr oblemsinvolvingev olvingdiscontinuitiescan bemode ledusingphase-fieldmod els,wherethedis continuityissmearedoutand trackedbyafieldgovern edbya PDE .Inmanycases,s uchaPDEisoffourth order,includingm odelsforcrackpropagation[7],forcrys talgrowth[38],orfor themechani csoffluidmembranes[10].Thenu mer icaltreatment ofsuchproblems withC 0 finiteelementsis cumbersomeandinvolvesinter polating independently thefieldand itsgradient[11] .Incont rast,aGaler kinapproachisstraightf orwardif smoothbasisfuncti onsareused.LME arenotonlysmooth,butalsoeasil yamenabl e toadapti vemethodsandhavemon otonicitypropertiesthathe lpthe maccurately describethesharpvariationsc haracterist icofphase-fiel dsolutions.SeeFigure1.5 foranill us trationofLMEapproximantsappliedtoaph ase- fieldmo delofvesicle dynamics[34,29].LMEapproximan tshav ealsobe enappli edtophase-fieldmodels offr acture[20],andtootherhigh- orderPDEss uchast hosearis inginthemech anics ofth inshells[24]ori nthecoupledelectrom echanic soffl exoel ectricmate rials[2,1].

1.5.2Manifold approximation

Finally,LMEapproximations havebe enusedtosmoothlyparametrizemanifolds sampledbycloudsofpoint sinanau tomatedwayandwithou tth eneedforamesh, usinganatlasofpartial lyo verlappin gch arts[24].See[22]forrecentw orkalong theselines,with areviewofsimilarappr oachesincompute rgr aphics.Figure1.6(a) illustratestheprocedure,inwhic hthepoint- setd-dimensionalmanifoldissystemat- icallypartitioned untileachpartitionishomeomorphic toanopensetinR d .Then, eachpartiti onisembeddedinR d usingnonlineardi mensionalityreductionme thods, andthis embeddingisu sedasaparametricdomainforalocalpar ametri zationof thepartiti on.Parametrizationsofadjacentpar titionsare"glued"withpartition-of- unityfunctions. Thisnaturalbutpowerfulproced urehasbeenuse dtomodelthin shellsofcomplexgeomet ryF igure1.6(b),toparametr izethegaitofmicroscopi c swimmingcells[3],ortodefine collectivevariabl esformolecu lar system sbasedon parametrizingtheso-calledintrinsicm anifoldunde rlyingmolecularflexibil ity[14], seeFigure1. 6(b).

1.6OUTLOOK

Insum mary,theprincipleofmaxim umentropy isaconceptuallyappealingand computationallypracticalapproachtodefinegen eralizedbarycentriccoor dinates forcloud sofpoints.Theres ult ingbarycentriccoord inatescanbe viewedasmeshfree basisfunctions andusedincomputationalmechani cs,exp loitingtheir smoothn ess andthee asetoimpl ementadapti vestrat egies.Thefactthatthesebasisfun ctions arebaryc entriccoordinatesmakesiteasiertoi mposeboundaryconditions,but alsoprovid esanaturalframeworktocoupled maxi mumentropybasisf unctions Maximum-entropymeshfreecoordinatesincomputationalmechanics!15

Nonlinear dimensionality reduction of each partition2D embedding of partition (*), where smooth parametrization using LME approximants is defined.(a)(b)Partitioned point-set surface(*)(c)Figure1.6Approximationofmanifoldsusinganatla sofsmoo thLME

parametrizations.(a)Methodologytodefinelocalpara metrizationsma pping partitionsofasurfacedefine dbyase tof points.(b)Applicationofthis methodtosolvet hehigh-orde rPDEforanonlinea rKirchho ! -Loveshell. (c)Applicationo fthemethodtodescrib ethemolec ularconfo rmationsof alaninedipeptide,a smallmolecule.Anensemble ofc onformationso fthis moleculesamplesanunde rlyingconfigurational manifoldhome omorphictoa torus.Withthemethodpr esente din(a), thismanifoldispartit ionedintofour pieces,eachofwhichis parametrizedwit hLMEappr oximants.This metho d allowsustodefinesmoo thc ollectiv evariable sforthissystem,re quiredto enhancesamplinginmolec ulardynamicssimula tions .

16!GeneralizedBarycentricCoordinatesinComputerGr aphicsandComputationalMechanics

withmultivari atesplinetechniques.Wehavedemon stratedthisbyblend ingmax- imumentropyapp roximationstoB-spli neboundaryrepresentations,butanother attractiveideaisusingsuch blendingtor esolvet heissuesassociate dwithirregu- larver ticesinsplinepatches[22].O peniss uesincludethesyst ematicformulation offe asiblehigher-orderconsis tencyconditionsinmultipledimens ions(seethedis- cussionfollowing(1.11) ),andtheaccurateande # cientnumericalqu adratureof theintegral sappearinginGalerkinmet hods,whichinvolveprod uctsofd erivatives ofth enon-polynom ialLMEbasisfunctions.Finally,theapp licabi lityoftheLME approachinanyspaced imensi onhasnoty etbeenexploi tedinapplications.

Bibliography

[1]A.Abdol lahi ,D.Mill´an,C.Peco,M.Arr oyo,andI .Arias.Revisitingpyrami d compressiontoquantifyflexoelec tricit y:Athree-dimensionalsi mulationstudy.

Phys.Rev.B,91:104103, Mar2015.

[2]A.Abdol lah i,C.Peco,D.Mill´an,M.Arr oyo,G. Catalan,andI.Arias .Fractu re tougheningandtoughnessasymmet ryind ucedbyflexoelectricity .Phys.Rev.

B,92:094101, Sep2015.

[3]M.Ar royo,L.He ltai,D.Mill´an,an dA.D eSimone.Reversee nginee ringthe euglenoidmovement.ProcNatlAca dSciUSA,109:17874-17879, 2012. [4]M.Arr oyoand M.Ortiz.Localmaxim um-ent ropyapp roximationschemes:a seamlessbridgebetweenfi niteelementsand meshfreemethods.International JournalforNumericalM ethodsinE ngineering,65( 13):2167-2202,2006. [5]M.Arr oyoand M.Ortiz.MeshfreeMethodsforParti alDi!erentialEqua- tionsIII,vol ume57ofLectureNotesinCompu tationalScienc eandE ngineer- ing,ch apterLocalMaximum-Entr opyApproxi mationSchemes,pages1-16.

Springer,2007.

[6]A.Bom padr e,L.E.Perotti,C.J.Cyron ,and M.Orti z.Convergentmeshfree approximationschemesofarbitraryorder andsmoothness.ComputerMethods inApp liedMechanicsandEngineeri ng,221-222: 83-103,2012. [7]M.J. Borden, T.J.R. Hughes,C.M.Landis,andC .V.Verh oosel. Ahigher - orderphase-fiel dmodelforbrittlefracture:Form ulationandanalysisw ithin theisogeomet ricanalysisframework.ComputerMethodsinAppli edMechanics andEngineer ing,273:100-118, 2014. [8]S.Bo ydandL. Vandenberghe.ConvexOptimiza tion.Cam bridgeUniversity

Press:Cambridge,UK,2004.

[9]C.C yron,M. Arroyo,andM.Ortiz .Smooth ,secondorder,non-n egative mesh- freeapproximan tsselectedbymaximumentropy.InternationalJournalfor NumericalMethodsinEngineeri ng,79(13) :1605-1632,2009. [10]Q.Du ,C.Liu, andX.Wang.Ap hasefiel dapproachint henume ri calstudyof theelastic bendingenergyforves iclemembranes.JournalofComputatio nal

Physics,198:450-468, 2004.

17

18!Bibliography

[11]Q.Du andL.Zhu .Analysi sofami xed finiteelement methodforaphase fieldbendinge lasticitymodelofvesicl emembranedeformation.Journalof

ComputationalMathematics,24:265-280, 2006.

[12]T.Fr iesandH. Matthies.Classifi cationand ove rviewofmeshfreemeth- ods.Technical report,InstituteofScienti ficComputing,Technic alUniversity

Braunschweig,Germany,July2004.

[13]F.Gr ecoand N.Sukumar.Derivati vesofmax im um-entropybasisfunctions on theboundary :Theoryandcomputations.InternationalJournalforNumerical

MethodsinEngineering,94:1123-1149, 2013.

[14]B.Hash emian,D .Mill´an,andM.Arroyo.Char tingmol ecularfree-energyland- scapeswithanatlasof collectivevari able s.TheJournal ofChemicalPhysics,

145(17),2016.

[15]T.Hugh es.TheFinite ElementMethod:Lineal StaticandDynamic Finite

ElementAnalysis.Do verPublications,2000.

[16]T.Hugh es,J.C ottrell,andY.Bazil evs.Is ogeometricanalysis:CAD,finite elements,NURBS,exactgeometryandm eshrefinement .ComputerMethods inApp liedMechanicsandEngineeri ng,194: 4135-4195,2005. [17]E.Ja ynes.I nformationtheoryandstatist icalmechanics.PhysicsReviews,

106:620-630,1957.

[18]A.Khi nch in.MathematicalFoundationsofInformat ionTheory.Do ver,New

York,1957.

[19]B.Li, F.Habbal, andM.Or tiz.O ptimaltransport ationmes hfree approxima- tionscheme sforfluidandplasticflows. InternationalJournalforNumerical

MethodsinEngineering,83( 12):1541-1579,2010.

[20]B.Li, C.Pec o,D.Mil l´an,I. Arias,andM.Arro yo.Phase -fieldmodelingand simulationoffractureinbritt lem aterialswithstronglyanisot ropicsu rface energy.InternationalJournalforNumericalMethods inEngineering,102(3-

4):711-727,2015.

[21]S.Lian dW.Liu. Mes hfree andparti clemethod sandtheirapplications.

AppliedMechanicsReviews,55(1) :1-34,2002.

[22]M.Ma jeedan dF.Cirak.Isogeometrican alysis usingm anifold-basedsmooth basisfunction s.ComputerMethodsinApplie dMechanicsandEngineer ing, pages-,2016. [23]D.Mi ll´an, A.Rosolen,andM.Arroyo.Thins he llanalysisfromscattere dpoint s withmaximum-e ntropyapproximants.InternationalJournalforNumerical

MethodsinEngineering,85( 6):723-751,2011.

Bibliography!19

[24]D.Mi ll´an, A.Rosolen,andM.Arroyo.Nonline arm anifoldlearningformesh - freefinitede formationthinshell analysis.InternationalJournalforNumerical

MethodsinEngineering,93( 7):685-713,2013.

[25]D.Mi llan,N.S ukumar,andM.Arroyo.Ce ll- basedmaximum-entropyappr ox- imants.ComputerMethodsinAppli edMechanicsandEngine ering,284:712-

731,2015.

[26]K.Nis sen,C. J.Cyron,V.Gravemeie r,andW. A.Wall.I nformation-flux method:ameshfreemaximu m- entropypetrov-galerkinmethod includingsta- bilisedfiniteeleme ntm ethods.ComputerMethodsinApplie dMechanicsand

Engineering,241-244:225 -237,2012.

[27]A.Or tiz ,M.Puso,andN.Sukumar.M aximum -entropymeshf reemet ho dfor compressibleandnear-incompressiblee lastici ty.ComputerMethodsinApplie d MechanicsandEngineering,199(25-28) :1859-1871,2010. [28]C.Pe co,D.M illan,A.Rosolen, andM.Arr oyo.E # cientimplementat ion ofgale rkinmeshfreemethod sforlarge-scaleproblemswithan emphasison maximumentropyapproxi mants.ComputersandStructures,150:52-62, 2015. [29]C.Pe co,A.Rosol en,andM.Arroy o.Anad aptivemeshfreemeth odforph ase- fieldmodelsofb iomembranes.PartII:a Lagrangi anapproachformembranes invisc ousfluids.JournalofComputatio nalPh ysics,249:320-336, 2013. [30]V.Raj an.O ptimalityoftheDe launaytriangulationinR d .Discreteand

ComputationalGeometry,12(2) :189-202,1994.

[31]A.Rosol enan dM.Arroyo.Blendi ngisogeom etrican alysisandmaximum entropymeshfreeappr oximants.ComputerMethodsinApplie dMechanicsand

Engineering,264:95-107, 2013.

[32]A.Rosol en, D.Mill´an,andM.Arroy o.Onthe optimumsupportsizein meshfreemethods:avariation aladaptivityapproachwithmaximu men tropy approximants.InternationalJournalforNumericalMethod sinEngineering,

82(7):868-895,2010.

[33]A.Rosol en, D.Mill´an,andM.Arroy o.Second orderconvexmaximumentropy approximantswithapplicationstohighor derPDE.InternationalJournalfor NumericalMethodsinEngineeri ng,94(2) :150-182,2013. [34]A.Rosol en, C.Peco,andM.Arroyo.Anad aptivem eshfreemeth odforph ase- fieldmodelsofb iomembranes.PartI:app rox imationwithmaximum-entropy approximants.JournalofComputatio nalPh ysics,249:303-319, 2013. [35]N.Suk umar .Constructionofpolygonalint erpolants:amaximumentropy approach.InternationalJournalforNumericalMethods inEngineering,

61(12):2159-2181,2004.

20!Bibliography

[36]N.Suk umar .Quadraticmaximum-entrop yserendipityshapefunc tionsfor arbitraryplanarpolygons.ComputerMethodsinAppli edMechanicsandEn- gineering,263:27-41, 2013. [37]N.Suk umar andR.Wright.Overvie wandcons tructi onofmeshfreebasis functions:Frommovingleastsquar estoentrop yapproximants.International JournalforNumericalM ethodsinE ngineering,70( 2):181-205,2007. [38]S.Tor abiandJ. Lowengrub.Sim ulating interf acialanisotropyinthin- filmgrowthu singanextendedCah n-Hilliardmodel. PhysicalReviewE,

85(4):041603,2012.