Fast and intuitive generation of geometric shape t

Konrad-Zuse-Zentrumfu¨rInformationstechnikBerlinTakustraße7D-14195Berlin-DahlemGermanyMALTEZO¨CKLER,DETLEVSTALLING,HANS-CHRISTIANHEGEFastandIntuitiveGenerationofGeometricShapeTransitionsPreprintSC99-33(September1999)FastandIntuitiveGenerationofGeometricShapeTransitionsMalteZo¨ckler,DetlevStalling,Hans-ChristianHegeSeptember1999AbstractWedescribeanovelmethodforcontinuouslytransformingtwotriangu­latedmodelsofarbitrarytopologyintoeachother.Equalglobaltopologyforbothobjectsisassumed,extensionsforgenuschangesduringmetamorpho­sisareprovided.Theproposedmethodaddressesthemajorchallengein3Dmetamorphosis,namelyspecifyingthemorphingprocessintuitivelywithminimaluserinteractionandsufficientdetail.Correspondingregionsandpointfeaturesareinteractivelyidentified.Theseregionsareparametrizedautomaticallyandconsistently,providingabasisforsmoothinterpolation.Utilizingsuitable3Dinteractiontechniquesasimpleandintuitivecontroloverthewholemorphingprocessisoffered.Keywords:morphing,metamorphosis,surfaceparametrization1IntroductionMorphingorwarpingalgorithmshavereceivedconsiderableattentionincomputergraphicsandimageprocessing.Morphinghasbecomeastandardtechniqueinmovieandentertainmentindustry.Althoughcomputergeneratedimageswhicharerenderedfromtrue3Dmodelsarecommontoday,themajorityofmethodsdevelopedsofarfocusesontheproblemofinterpolatingbetween2Dimages.Forcomputeranimationtheinterpolationofthreedimensionalmodelsisanattractivealternativeto2Dmorphing.Usingtrue3Dmethodsmorphingsequencescanbecomputedindependentlyofe.g.lightandcamerapositions.Also,ingeneralmorerealisticresultswillbeobtained,sinceshapeinformationnotvisibleinthestartorendimagecanbetakenintoaccount.1Propertiesofagoodmorph.Amorphdefinesthetransitionofanobjectintoanotherobject.Thistransformationshouldmeetseveralcriteria.First,itshouldbecontinuousandsmooth,uptoadiscretesetoftransitionpointswhereintendedtopologychangeshappen.Second,theintermediateobjectsshouldlook“realistic”insomesense.Third,prominentfeaturesofobjectshouldtransformintofeaturesofthatcorrespondinsomesemanticsense.Especiallytomeetthelattercriterium,manualinteractionisrequiredasamatterofprinciple.Specificcontributions.Inthispaperwepresentamethodfortransformingthree-dimensionalgeometricmodelsintoeachother.Themodelsaresupposedtobegiveninapolygonalboundaryrepresentation.Specifically,weassumethatthesurfacesaretriangulated,butthevertex/edge/facestructuresdonotneedtobeidentical.Ouralgorithmallowstheusertoidentifycorrespondingregionsaswellascor­respondingpointsinbothmodelsinteractively.Duringthisprocessbothmodelsaredecomposedintoasetoftopologicallyequivalentpatches,whichafterwardsareparametrizedautomatically.Inthiswayacompleteone-to-onecorrespon­dencebetweenbothmodelsisachieved.Incontrasttootherapproachesindividualpatchescanbeofdisk-likeaswellascylinder-liketopology.Thewholemethodischaracterizedbythefollowingitems:featurecorrespondencescanbedefinedinanintuitiveandveryflexiblewaynorestrictionsofanytypeapplytothedefinitionofcorrespondingpointfeaturestimerequirementsforuserinteractionarelowcomparedtootherapproachesthemethodisveryfast;morphsequencesarecomputedwithinafewsec­onds.Althoughweprimarilyassumethatthemodelstobemorphedhavethesametopol­ogy,wealsodiscussmethodsfortakingintoaccounttopologychangesofvariouskinds.Themajordesigngoalwastodevelopandcombinealgorithmiccomponentsinsuchawaythatallsteps,includingtheparametrization,arecompletelycontrolledbytheanimator’saims.Usingsuitable3Dinteractiontechniquesmanualinputisgreatlyfacilitated.Theimplementationprovesthatourmethodoffersasimpleandintuitivecontroloverthewholemorphingprocessandenablestheanimatortocreatemorphingsequencesinamazinglyshorttime.1.1PreviousworkThetypeofobjectrepresentationhasastrongimpactonalgorithmsforobjecttransformation.Themajorcategoriesemployedincomputergraphicsarevol-2umeandsurfacebasedrepresentations.Correspondingly,existingmorphingtech­niquesfor3Dobjectscanbedividedintotwomajorclasses:volumebasedmeth­odsthatinterpolatetwovolumetricrepresentationsoftheobjects,oftenbyusingsomekindoftransformationfunctionwhichisdefinedcontinouslyinR3,andsur­facebasedmethodsthatfirstestablishandthenevaluateacorrespondencefunctiondefinedonthemodels’boundaryrepresentations.Volumebasedmethods[22,12,11,3,5]offertheadvantagethattopologydoesnotmatter.Furthermore,nosurfacemodelsareneededwhosegeneration,e.g.fromsegmentedimagevolumes,mightbecostly.Drawbacksarethatthemorphingsequencesareoftenexpensivetocompute,andthattopologicalaspectslikeconnectivityofintermediatemodelsarehardtocontrol.Surfacebasedmethodsusuallyconsistoftwosteps[15]:first,establishingcorrespondencesbyassigningtoeachpointofthesourcesurfaceapointonthetargetsurface,theninterpolatingbetweeneachpairofcorrespondingpoints.Differentapproacheshavebeentakenforestablishingcorrespondences,see[19].Ifthetopologyofbothobjectsisthesame,thecorrespondenceproblemcanbesolvedusingparametrizations,i.e.continuousbijectivefunctionsthatmapbothobjectstoastandarddomain.Pointswhoseimagescoincideunderthesemappingsaresaidtocorrespond.Alotofworkhasbe