Free-form deformations with lattices of arbitrary topology

WithLatticesofArbitraryTopology

RonMacCrackenKennethI.Joy

ComputerGraphicsResearchLaboratory

DepartmentofComputerScienceUniversityofCalifornia,Davis

Abstract

Anewfree-formdeformationtechniqueispresentedthatgeneral-izespreviousmethodsbyallowing3-dimensionaldeformationlat-ticesofarbitrarytopology.ThetechniqueusesanextensionoftheCatmull-Clarksubdivisionmethodologythatsuccessivelyrefinesa3-dimensionallatticeintoasequenceoflatticesthatconvergeuni-formlytoaregionof3-dimensionalspace.Deformationofthelat-ticethenimplicitlydefinesadeformationofthespace.Anunderly-ingmodelcanbedeformedbyestablishingpositionsofthepointsofthemodelwithintheconvergingsequenceoflatticesandthentrack-ingthenewpositionsofthesepointswithinthedeformedsequenceoflattices.Thistechniqueallowsagreatervarietyofdeformablere-gionstobedefined,andthusabroaderrangeofshapedeformationscanbegenerated.

1Introduction

Efficientandintuitivemethodsforthree-dimensionalshapedesign,modification,andanimationarebecomingincreasinglyimportantareasincomputergraphics.Themodel-dependenttechniquesini-tiallyusedbydesignerstomodifysurfacesrequiredeachprimitivetypetohavedifferentparametersand/orcontrolpointsthatdefineditsshape.Modeldesignershadtoconsiderthismathematicalmodelwhenmakingthedesiredmodifications,andshapedesigncouldbedifficult–makingsimplechangestothesurfacerequiredthemod-ificationofmanysurfaceparameters.Theprocessgrewmorediffi-cultwhenlocalchanges,suchasaddingarbitrarilyshapedbumps,orglobalchanges,suchasbending,twisting,ortaperingwerenec-essary.

Thefree-formdeformations[5,6,9,19]weredesignedtodealwithsomeoftheseproblems.Thesemethodsembedanobjectinadeformableregionofspacesuchthateachpointoftheobjecthasauniqueparameterizationthatdefinesitspositionintheregion.Theregionisthenaltered,causingrecalculationofthepositionsbasedupontheirinitialparameterization.Ifadeformablespacecanbede-finedwithgreatflexibilityandwithfewcontrolpointsrelativeto

DepartmentofComputerScience,UniversityofCalifornia,DavisCA95616.Email:maccrack,joy@cs.ucdavis.edu

Permission to make digital or hard copies of part or all of this work or personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or a fee.

© 1996 ACM-0-791-746-4/96/008...$3.50

thenumberinthesurfacemodel,thencomplexmodelscomprisedofthousandsofcontrolpointscanbedeformedinmanyinterestingwayswithverylittleuser-interaction.

Barr[1]firstintroduceddeformationsbycreatingoperationsforstretching,twisting,bendingandtaperingsurfacesaroundacentralaxis(,,or).Operationsthatinvolvedmovingmanycontrolpointscouldnowbeaccomplishedwiththealteringofaslittleasoneparameter.However,thistechniquelimitsthepossibledefini-tionsofthedeformablespacetothatofasinglecoordinatesystemaboutanaxis,andrestrictsthewaysinwhichthespacecanbeal-tered-theaxiscannotbemodifiedandthedeformablespacecanonlybemodifiedbyafewparameters.

Barr’sdeformationswerefollowedbyamoregeneralizedap-proachtotheproblem,theFree-FormDeformations(FFDs)ofSederbergandParry[19].Thismethodimposesaninitialdeforma-tionlatticeonaparallelepiped,anddefinesthedeformablespaceasthetrivariateB´eziervolumedefinedbythelatticepoints.Theparal-lelepipedformofthelatticeallowspointsofanembeddedobjecttobequicklyparameterizedinthespaceofthelattice,andasthelatticeisdeformed,thedeformedpointscanbecalculatedbysimplesub-stitutionintothedefiningequationsofthetrivariatevolume.Thismethodiswidelyusedbecauseofitseaseofuseandpowertocreatemanytypesofdeformationswithlittleuser-interaction.GriessmairandPurgathofer[9]extendedthistechniquebyutilizingatrivari-ateB-Splinerepresentation.Althoughbothmethodsgivetheusermanycontrolstoalterthedeformablespace,bothSederbergandParry’sFFDsandGriessmairandPurgathofer’sdeformationtech-niqueshandleonlyaspecifictypeofspacedefinition,thatdefinedinitiallybyaparallelepipedlattice.

Inordertogeneratefree-formdeformationsforamoregenerallatticestructure,CoquillartintroducedExtendedFree-FormDefor-mations(EFFD)[5,6].ThismethodusestheinitiallatticepointstodefineanarbitrarytrivariateB´eziervolume,andallowsthecombin-ingofmanylatticestoformarbitraryshapedspaces.Modifyingthepointsofthedefininglatticecreatesadeformationofspacewhereonetrivariatevolumeisdeformedintoanother.Thisextensional-lowsagreaterinventoryofdeformablespaces,butlosessomeoftheflexibilityandstabilityofSederbergandParry’sFFDs:Whilethecornercontrolpointsofthejoinedlatticesareuser-controllable,theinternalcontrolpointsareconstrainedtopreservecontinuity;and,calculatingtheparameterizationofapointembeddedintheinitialtrivariatevolumerequiresnumericaltechniques.

ArecentdeformationtechniquedevelopedbyChangandRock-wood[4]generalizesBarr’stechniqueinadifferentmanner.In-steadofdefiningthespaceinafree-formmanner,Chang’sapproachdealswithincreasingtheflexibilityofanaxis-basedapproachbyal-lowingmodificationstotheaxisduringthedeformation.Thetech-niqueallowstheusertodefinetheaxisasaB´eziercurvewithtwouser-definedaxesateachcontrolpointofthecurve.RepeatedaffinetransformationsusingageneralizeddeCasteljauapproachareusedtodefinethedeformablespace.Thistechniqueisverypowerful,in-181

tuitive,andefficient,butagainrestrictsthewaysinwhichthespacesurroundingthecurvecanbealtered.

Thispaperintroducesafurtherextensiontothesetechniquesbyestablishingdeformationmethodsdefinedonlatticesofarbitrarytopology.Inthiscase,thedeformablespaceisdefinedbyusingavolumeanalogyofsubdivisionsurfaces[2,7,8].Inthesesubdivi-sionmethods,thelatticeisrepeatedlyrefined,creatingasequenceoflatticesthatconvergetoaregioninthree-dimensionalspace.Thisrefinementprocedureisusedtodefineapseudo-parameterizationofanembeddedpoint.Asthepointsofthelatticearemodifiedade-formationofthespaceiscreated,andtheembeddedpointscanberelocatedwithinthedeformedspace.

Thismethodhasbeenfoundtobequiteintuitiveforthedesigneranddramaticallyincreasestheinventoryoflatticesthatcanbecon-sideredinafree-formdeformation.ThetwistsandbendsofBarr[1]andthecylindricallatticesofCoquillart[5]canbeeasilysimulated.Byallowingmeshesofarbitrarytopology,thecontinuityproblemsofadjoininglatticesvirtuallydisappear.

Insection2,wegiveanoverviewofthesubdivisionmethodsthatareusedtodefinethedeformablespacefromthelattice.InourcasethesemethodsarebaseduponanextensionoftheCatmull-Clarkre-finementrulesforsurfaces[2].Insection3,wemodifytheCatmull-Clarkproceduretocontroltheboundarysurfacesandcurvesofthedeformableregion.Thisproducesadeformableregionthatcanbeintuitivelydefinedfromthelattice.Insection4wediscussthemeth-odsthatgiveacorrespondencebetweenapointembeddedinthede-formablespaceandthesequenceoflatticesgeneratedbytherefine-mentprocedure.Insection5wepresentanoverviewofthecom-pletedeformationprocedure.Implementationdetailsofthealgo-rithmarediscussedinsection6andresultsaregiveninsection7.

figures/fig1.tif

Figure1:LatticeStructures

Weallowlatticesofarbitrarytopologywiththefollowingprop-erties:

Thelatticeiswell-connected,i.e.novertexliesonanedgenotcontainingthatvertex.

Allcellsareclosed,meaningthefacescomprisingthecellsdonotformanyholes.Forexample,acubewithonefacemissingisnotavalidcell.

Notwocellsofthelatticeintersect–thatis,wewillnotcon-siderself-intersectinglattices.

2

DefiningtheDeformableSpacefromtheLattice

Alatticeisdefinedtobeasetofverticesandanassociatedsimplicialcomplexwhichspecifiestheconnectivityofthevertices.Asubdivisionmethodappliedtoalatticeisafunctionfromthesetoflatticesintoitself.Asubdivisionmethodisusuallyimplementedasasetofrefinementruleswhichdefinehowtogen-eratetheverticesoftheresultinglattice,andalsohowtoconnectthesenewvertices.Asetofrefinementrulescanberepeatedlyap-pliedtoalattice,creatingasequenceoflattices.Inmanycases,thissequencecanbemadetoconvergetoaregionof3-dimensionalspace.

Todescribethecomponentsofalattice,wewillusethefollowingterms:

Anedgeofthelatticeisdefinedbytwoverticesthatarecon-nectedinthesimplicialcomplexofthelattice.

Afaceofthelatticeisdefinedbyaminimalconnectedloopofvertices.

acellofthelatticeistheregionofspaceboundedbyasetoffaces.

Acontrolpolygonhasverticesandedges,acontrolmeshhasver-tices,edgesandfaces,andacontrollatticehasvertices,edges,facesandcells.InthebivariateB-splinecase,eachfaceofthecontrolmeshisdefinedbyfourvertices,andeachvertexofthemeshhasconnectivityfour(fouredgesradiatingfromthevertex).Inthetrivariatecase,eachcellofthecontrollatticeisdefinedbysixfacesandeachfacebyfourvertices.Eachvertexhasconnectivitysix.

Forconsistency,wewillrefertoasetofpointsthatgeneratesavolumeasalattice.Thesetofpointsgeneratingasurfacewillbecalledamesh.Thesetofpointsgeneratingacurvewillbecalledacontrolpolygon.

Figure1illustratestwosamplelattices,onebaseduponaparal-lelepipedstructureandonebaseduponacylindricalstructure.TheuniformB-splinecurves,surfacesandvolumescanbede-finedbysubdivisionmethods.Inthecurvecase,therefinementruleswerefirstpresentedbyGeorgeChaikin[3].Riesenfeld[18]proceededtoshowthatChaikin’scurveswereuniformquadraticB-splinecurves.DooandSabin[7,8]extendedChaikin’smethodtouniformquadraticB-splinesurfacesandthenextendedtherefine-mentrulesforthequadraticcasetomeshesofanarbitrarytopol-ogy.CatmullandClark[2]developedasimilartechniquefortheuniformcubicB-splinecase.Thesemethodshavenowcomeintowidespreaduseingeometricmodeling.Theyhavebeenusedforinterpolationandfairing[10],approximation[12],andmultireso-lutiondesign[16].

Inthispaper,weconsiderlatticesofarbitrarytopologyandde-velopasetofrefinementrulesthatsubdividethislatticetogener-ateadeformableregioninthree-dimensionalspace.Togeneratethedeformableregions,weutilizeanextensionoftheCatmull-Clarksubdivisionmethodtovolumes.Inthefollowingsections,wesum-marizetheCatmull-ClarkrefinementrulesfortheuniformB-splinevolume,alongwiththeextensionsofthesemethodstolatticesofar-bitrarytopology.Thecompletedetailsofthedevelopmentoftheserefinementrulescanbefoundin[13].

2.1SubdivisionMethodsforTrivariateCubicUni-formB-SplineVolumes

GivenacontrollatticethatdefinesatrivariateuniformB-splinevolume,thesubdivisionmethodgeneratesanewcontrollatticewhichconsistsoftheunionofalltheverticesgeneratedbyabinary

182

figures/fig2.tiffigures/fig3.tif

Figure2:Type-3,4and5cellsgeneratedbythesubdivisionprocess.subdivisionofthetrivariatevolume.Thesepointscanbeclassifiedinto

1.cellpoints–thesepointsaretheaverageoftheverticesinthelatticethatmakeupthecell.2.facepoints–thesepointscanbewrittenas

Figure3:Thetype-cellsgeneratedbyrepeatedsubdivision.

2.2Catmull-ClarkVolumes

Extensionoftheaboverulestolatticesofarbitrarytopologyisstraightforward,usinganextensionofthebivariateCatmull-Clarksubdivisionstrategy[2].Wecanclassifythepointsoftherefinementintofourtypes:

1.cellpoints–thesepointsaretheaverageoftheverticesofthelatticethatboundthecell.2.facepoints–thesepointscanbewrittenas

whereandarethecellpointsofthetwoadjacenthex-ahedralcellsthatcontainthefaceandisthefacecentroid(theaverageoftheverticesthatsurroundtheface).

3.edgepoints–thesepointscanbewrittenas

whereandarethecellpointsofthetwocellsthatcon-tainthefaceandisthefacecentroid.

3.edgepoints–thesepointscanbewrittenas

whereistheaverageofthecellpointsforthosehexa-hedralcellsthatcontainthisedge,istheaverageofthe

facecentroidsforthosefacesthatcontainthisedge,andisthemidpointoftheedge.

4.vertexpoints–thesepointscanbewrittenas

whereistheaverageofthecellpointsforthosecellsthatcontainthisedge,istheaverageofthefacecentroidsforthosefacescontainthisedge,andisthemidpointoftheedge.isthenumberoffacesthatcontaintheedge.

whereistheaverageofthecellpointsforeachofthehexahedralcellsthatcontainthisvertex,istheaver-ageofthefacecentroidsforthefacesthatcontainthisvertex,

istheaverageofthemidpointsfortheedgesthatradiatefromthevertex,andisthevertexitself.

4.vertexpoints–thesepointscanbewrittenas

Ateachsubdivisionstep,acellpointisinsertedintothelatticeforeachcellaccordingtothefirstrule,afacepointisinsertedforeachfaceaccordingtothesecondrule,anedgepointisinsertedforeachedgeaccordingtothethirdrule,andeachvertex’spositionisrecalculatedaccordingtothefourthrule.Toreconnectthelatticeaftertheseruleshavebeenapplied,wefirstconnecteachnewcellpointtothenewfacepointsgeneratedforthefacesdefiningthecell.Eachnewfacepointisconnectedtothenewedgepointsoftheedgesdefiningtheoriginalface.Eachnewedgepointisconnectedtothetwovertexpointsdefiningtheoriginaledge.

whereistheaverageofthecellpointsforeachofthecellsthatcontainthisvertex,istheaverageoftheface

istheav-centroidsforthefacesthatcontainthisvertex,

erageofthemidpointsfortheedgesthatradiatefromthever-tex,andisthevertexitself.

Theserefinementrulescanbeappliedtoalatticeofarbitrarytopol-ogycreatinganewsetofvertexpoints,edgepoints,facepointsandcellpoints.ThereconnectionstrategyisidenticaltothatofthetrivariateuniformB-splinelattice:thenewcellpointareconnectedtothenewfacepointsgeneratedforthefacesdefiningthecell;thenewfacepointsareconnectedtothenewedgepointsfromtheedges

183

figures/fig4.tiffigures/fig5.tif

Figure4:Catmull-ClarkVolumesdefinedbyarectangularandcylindricallattice.

Figure5:Catmull-Clarkvolumeswithboundaryandedgecontrol.Thecornerverticesareyellow,thesharpedgesarered,theboundaryedgesaregreenandtheinternaledgesareblue.

Cornerverticesareidentifiedasthoseincidenttoonlyonecellofthelattice.Intherefinementprocedure,thepositionofacornervertexdoesnotchange.

Sharpedgesarethoseedgesjoiningverticesthatareincidenttoonlyoneortwocellsofthelattice,includingcornervertices.TheedgeandvertexpointsalongthesharpedgesofthelatticearecalculatedaccordingtosubdivisionrulesforuniformcubicB-splinecurves[13].

Allothervertex,edge,andfacepointsontheboundaryaregeneratedaccordingtotheCatmull-Clarkrulesforsurfaces[2].

AllinternalpointsarecalculatedusingtheCatmull-Clarkrulesforvolumes.

definingtheoriginalface;and,eachnewedgepointisconnectedtothetwonewvertexpointsfromtheoriginaledge.

Todescribethecellstructureofthesubdividedlattice,wedefinethevalenceofavertexwithinacelltobethenumberofedgesinthatcontainthevertex.Givenacellofalattice,con-sideravertexofthecellofvalence.Therefinementprocesscreatesanewcellfromthatcontains4-sidedfaces,verticesofvalenceandverticesofvalence(seefigure2).Wecallthesecharacteristiccellstype-cells.Afterthefirstsubdivision,allcellscanbeclassifiedastype-cells.

Inthesubdivisionprocess,atype-cellisrefinedintotwotype-cellsandtype-cells.Thetype-cellisahexahedralcellwith4-sidedfacesand3-valencevertices.Afterafewsubdivisions,thebulkofthelatticewillconsistoftype-cellsarrangedinareg-ularpattern–thatofthetrivariateuniformB-splinecase–exceptaroundafinitenumberoftype-cellswherethisregularityisdis-turbed.For,thenumberoftype-cellsdoublesineachap-plicationofthesubdivisionalgorithm(seefigure3).

Figure4illustratestheCatmull-Clarkvolumesgeneratedfromthelatticesshowninfigure1.

3

BoundaryControloftheSubdivisionVolume

Designingalatticethatrepresentsaparticularregionofspaceisadifficulttask.Thefree-formdeformationsofSederbergandParry[19]werebaseduponaninitiallatticethatwasformedonaparal-lelepiped,withthedeformablespacefillingthelatticecompletely.Inourcase,theregionofspaceresultingfromapplyingthetrivari-ateCatmull-Clarksubdivisionmethodtoanarbitrarylatticedoesnotconformcloselytothegeneralshapeofthelattice–shrinkingawayfromtheboundarysubstantially.Infigure4forexample,thecylindricallatticedoesnotrefineintoacylindricalregionofspace.Thisfeaturecreatesanunusualburdenonthedesignerandlimitstheusefulnessofthetechnique.

Tosolvethisproblemandcreateatoolthatwillconstructregionsofspacethatareintuitivetothedesigner,wemodifytherefinementrulesforthoseareasofthelatticethatcorrespondtoboundarysur-faces,sharpedges,andcornervertices.Theserulesaresummarizedasfollows:

Givenalatticebasedonacube,thesemethodswillgeneratearegionofspacethatisthecube.Inthecaseofthelatticeapproximatingacylinder,theregionisflatateitherendofthecylinderandroundedalongthelengthofthecylinderasonewouldexpect.Theseareshowninfigure5.Thecornerverticesareyellow,thesharpedgesarered,theboundaryedgesaregreenandtheinternaledgesareblue.ThesetechniqueshavebeenpreviouslyusedbyNasri[17]forDoo-Sabinsurfaces,andaresimilartothetechniquesusedbyHoppeetal.[12]indefiningedges,creases,cornersanddartsonLoopSur-faces[15].Whenaddedtothesubdivisionprocedure,thesenewrulesgeneratedeformableregionsofspacethatcloselyrepresenttheirlattice.

4CalculatingtheLocationofVertices

EmbeddedintheDeformableSpace

SederbergandParry[19]imposetheinitiallatticeonaparal-lelepipedinspaceandcalculatetheparameterizationofapointwithinthedeformablespacebyusingthelocalcoordinatesofapointwithintheparallelepiped.Thelocationofthepointunderthede-formationiscalculatedbysubstitutingtheselocalcoordinatevaluesintothedefiningequationforthetrivariateB´eziervolume.Coquil-lart[5]usesasimilarmethod,butnumericaliterationisrequiredto

184

calculatethelocalcoordinate,asherinitiallatticesarenotformedasparallelepipeds.Inboththesecases,thecellsofthelatticearehex-ahedral.Inthecasethatthelatticeisofanarbitrarytopologyandtheabovesubdivisionprocedureisused,asimpletrivariateparam-eterizationisnotavailable.Fortunately,thesubdivisionprocedureitselfcanbeusedtoestablishacorrespondencebetweenpointsinthedeformableregionandpointsinthedeformedregion.

Givenaninitiallattice,thesubdivisionproceduregeneratesa

thatconvergetothede-sequenceoflattices

formableregion.Eachlatticeinthesequenceinducesapartitioningofthedeformablespacebyitscells.Weselectalattice,say,thathasthepropertythatthemaximumvolumeoftheindividualcellsofissmall.Wethenidentifythecellofthatcontainsagivenpointandassumethatisdeformedtoapositionwithinthecor-respondingcellofthedeformedlattice–inthesamerelativeposi-tioninthecell.Whereasthisisanapproximation,itcanbemadearbitrarilyclosetotheactualdeformation.

Todeterminetherelativepositionofapointinthecell,wetakeadvantageofthefactthatafterthefirstrefinementallcellsaretype-cells,andmostaretype-(hexahedral).Inthetype-casewecancalculateatrilinearapproximationofthepositionofthepointinthecellandusethistrilinearparameterizationtoadjustthepositionofthepointinthedeformedcell.Inthetype-case,wecancalculateapiecewisetrilinearapproximation,bypartitioningthecellintotetra-hedra,andusethistoadjustthepositioninthedeformedcell.

figures/fig6.tif

Figure6:Partitioningofatype-cellforapproximation.Thegreenedgesrepresenttheoriginaledgesofthecell.Theblueedgesaregeneratedbythetetrahedralpartition.

6ImplementationDetails

5

TheDeformationProcess

Todeformanobject,wefollowthe4-stepprocedureoutlinedbyCo-quillartin[5].First,theusermustconstructthelattice.Thisisnor-mallydonebyutilizinganinventoryoflatticesandasetoftoolstomergeandbuildnewlatticesfromthisinventory.Acommontoolistheextrusiontoolthattakesameshandextrudesitinaspecifieddirectiontobecomealattice(thecylinderoffigure1wasgeneratedinthismanner.)Atthelowestlevel,theuserisallowedtotocre-atecellsonebyone,attachingthemfacebyfacetoformthelattice.Boundarysurfaces,sharpedgesandcornerverticescanbemarkedautomatically(asinsection3),oramanualmarkingprocedurecandeterminethem.Oncethelatticehasbeenconstructed,theusermustplacethelatticearoundtheobject,orthepartoftheobject,tobede-formed.

Whenthelatticeisorientedproperly,itisfrozentotheobject.Atthistime,thelatticeisrefined,andthenumberofrefinementstepsisretained.

Eachpointembeddedinthedeformableregioncanbe“tagged”withapointertothecelloftherefinedlatticethatcontainsthepoint,andafinitenumberofparametersthatdefinesitspositioninthecell.

Thedatastructureholdingthelatticeisimplementedasanexten-sionofthehalf-edgedatastructureforsurfaces–muchliketheradial-edgestructureofWeiler[20].Theprimarydifferencebe-tweenhalfedgestructureforameshrepresentingasurfaceandalat-ticerepresentingavolumeisthatthelatticestructuremayhavesev-eralfacesthatcontaineachedge–themeshstructurewillhaveatmosttwo.Inaddition,areal-timedeformationalgorithmrequiresthatthesequenceoflatticesbestoredhierarchically.Thesub-divisionstepsarethenexecutedonlyonceduringtheinitialization(orfreezing)phaseofthedeformation.Subsequentdeformationsofthelatticethenrequireonlytherecalculationoftherefinementrulesfortheverticesinlatticesto,withoutrecreatingthelatticestructure.Witheachsubdivision,thesizeofthedatastructurenearlytriplesandsodeformationswheretheuserdesiresaverysmallcellsizecanbequitememoryintensive.

Manynumericalalgorithmsexisttogeneratethetrilinearapprox-imationofapointinatype-cell.WehaveutilizedanadaptationofanalgorithmpresentedbyHamann,etal.[11].Givenapointinacell,wegenerateapointasthetrilinearpointdefinedby

.Wethenobtain

Foratype-hexahedralcell,theparametersconsistofa

triplewhichdefinesthepoint’strilinearparameter-izationwithinthecell.

Foratype-cell,anewcellpointiscalculatedandthecellispartitionedintotetrahedraaboutthiscellpoint,eachfacecontributingtwotetrahedratothepartition(seefigure6).Theparametersconsistofanindexintothetetrahedracontainingthepointandatriplewhichdefinesthepoint’spa-rameterizationwithinthetetrahedra.

isthetransposeofalocalapproximateoftheJacobianat

obtainedbyinterpolatingtheestimatesoftheJacobians

attheverticesofthecell.Ingeneral,where

Finally,theoriginallatticeisdeformedbymovingoneormoreofitsvertices.Thedeformedlatticeisthenrefinedtimesandthetagoneachpointisusedtoobtainthecorrespondingcellinthede-formedlattice.Theverticesofthiscellareusedtocalculateaposi-tionforthedeformedpointaccordingtotheparametersassociatedwiththeoriginal.

isobtainedbyperformingtrilinearinterpolationat

oftheJacobiansattheverticesofthecell.

Theprocedureisrepeateduntilthedistancebetweenandissufficientlysmall.Wefoundthatfewiterationswereneededasthealgorithmconvergesquicklyandthecellsaregenerallysmall.Inthecaseofatype-cell,wepartitionthecellintotetrahe-drabyutilizingthecellpoint(averageoftheverticesofthecell).Asimpleinterpolationfunctionfortetrahedralcellscanbewrittenas

where

185

where,,,and,arethefourverticesofthetetrahedra.Thiscanbeputintomatrixformandsolveddirectly[14].

Withthisimplementation,wehavefoundthatthealgorithmex-ecutesinrealtimeonanSGIIndigoExtreme.

9Acknowledgments

Weareverygratefultotheanonymousrefereesfortheirmanyhelp-fulcommentsonthefirstversionofthispaper.WewouldalsoliketothankBerndHamannforpointingustowardthesimpletrivari-ateschemesthatmakethisalgorithmpossible.SpecialthanksgotoJustinLegakisformanyusefulcritiquesoftheresearch,andwhoassistedusintheproductionofourfinalimages.Thedataforthe”mobster”infigure9wascontributedviatheavalonciteatwww.viewpoint.com.Theresearchreportedherewaspartiallysup-portedbyagrantthroughtheUniversityofCaliforniaMICROPro-gram.

7Results

TheprimarymotivationformovingfromthehexahedraltopologicallatticesofthetrivariateB´ezierandB-splinerepresentationsof[5,9,19]wastoincreasetheinventoryofavailablelatticesandthusthenumberofpossibledeformations.Figures7through9showtheresultsofthisalgorithmwithavarietyofmeshesandshapes.

Figure7exhibitsadeformationbyacylindricallattice,resultinginasurfacedeformationintheformofastar.

Figure8illustratesacomplexlatticeintheshapeofabarbell.Thislatticewasgeneratedbycreatingameshintheshapeofabar-bellandextrudingtheshapetoformthelattice.Thesubdivisionmethodologyautomaticallyhandlesthecontinuitybetweentheseg-mentsofthelattice.

Figure9showsadeformationappliedtothearmofthe“mobster”whichcausesthearmtoliftupward,andthehandtotwisttowardtheviewer.Thisisanexcellentexampleofourtechnique,asitwasnecessarytoconstructthelatticeabouttheappendagethatwastobemoved.

References

[1]AlanH.Barr.Globalandlocaldeformationsofsolidprimi-tives.InComputerGraphics(SIGGRAPH’84Proceedings),volume18,pages21–30,July1984.[2]E.CatmullandJ.Clark.RecursivelygeneratedB-splinesur-facesonarbitrarytopologicalmeshes.Computer-AidedDe-sign,10:350–355,September1978.[3]G.Chaikin.Analgorithmforhighspeedcurvegeneration.

ComputerGraphicsandImageProcessing,3:346–349,1974.[4]Yu–KuangChangandAlynP.Rockwood.Ageneralizedde

Casteljauapproachto3Dfree–Formdeformation.InProceed-ingsofSIGGRAPH’94(Orlando,Florida,July24–29,1994),ComputerGraphicsProceedings,AnnualConferenceSeries,pages257–260.[5]SabineCoquillart.Extendedfree-formdeformation:Asculp-turingtoolfor3Dgeometricmodeling.InComputerGraphics(SIGGRAPH’90Proceedings),volume24,pages187–196,August1990.[6]SabineCoquillartandPierreJanc´ene.Animatedfree-formde-formation:Aninteractiveanimationtechnique.InComputer

Graphics(SIGGRAPH’91Proceedings),volume25,pages23–26,July1991.[7]D.Doo.Asubdivisionalgorithmforsmoothingdownirreg-ularlyshapedpolyhedrons.InProceedingsoftheInt’lConf.InteractiveTechniquesinComputerAidedDesign,pages157–165,1978.[8]D.DooandM.Sabin.Behaviourofrecursivedivisionsurfaces

nearextraordinarypoints.Computer-AidedDesign,10:356–360,September1978.[9]JosefGriessmairandWernerPurgathofer.Deformationof

solidswithtrivariateB-splines.InEurographics’,pages137–148.North-Holland,September19.[10]MarkHalstead,MichaelKass,andTonyDeRose.Efficient,

fairinterpolationusingCatmull-Clarksurfaces.InComputerGraphics(SIGGRAPH’93Proceedings),volume27,pages35–44,August1993.[11]BerndHamann,DonhuaWu,andRobertJ.MoorheadII.On

particlepathgenerationbasedonquadrilinearinterpolationandBernstein-B´ezierpolynomials.IEEETransactionsonVi-sualizationandComputerGraphics,1(3):210–217,1995.[12]HuguesHoppe,TonyDeRose,TomDuchamp,MarkHalstead,HubertJin,JohnMcDonald,JeanSchweitzer,andWernerStuetzle.Piecewisesmoothsurfacereconstruction.InPro-ceedingsofSIGGRAPH’94(Orlando,Florida,July24–29,

8Conclusions

Wehavedescribedanewfree-formdeformationtechniquethatgen-eralizespreviousmethodsbyallowing3-dimensionaldeformationlatticesofarbitrarytopology.ThetechniqueusesanextensionoftheCatmull-Clarksubdivisionmethodologytosuccessivelyrefinea3-dimensionallatticeintoasequenceoflatticesthatconvergeuni-formlytoaregionof3-dimensionalspace.Deformationofthelat-ticethenimplicitlydefinesadeformationofthisregion.Anunder-lyingmodelcanbedeformedbyestablishingpositionsofthepointsofthemodelwithintheconvergingsequenceoflattices,establishingthecellofthelatticethatcontainsthepoint,establishinganapprox-imationofthepositionofthepointwithinthecell,andusingthisinformationtoestablishthenewpositionsofthesepointswithinthedeformedlattice.

Thismethodisverypowerfulinthatitcanbeappliedtovirtuallyanygeometricmodel,asitdirectlymodifiestheverticesthatdefinethemodel.Thevarietyoflatticesthatcanbeusedwiththistech-niquegreatlyincreasesthenumberofdeformationsthatcanbeac-complished.

Wehaveonlydiscussedpositionaldataoftheembeddedobjectinthispaper.Itisclearthatthelatticecouldholdadditionalparam-eters.Forexample,wecouldstore,inthelatticepointstheparame-tersofasolidtexture.Asthelatticeisdeformed,thetexturewouldbedeformedalongwiththeobject.

Thecarefulreaderwillnoticethat,forthevertexpointsoftheCatmull-Clarkvolume,weutilizetheform

whichdoesnotcontainanadjustmentforthenumberofedgesra-diatingfromavertex.WefoundthattheCatmull-Clarksurfacemethodologydirectlygeneralizestoedgepoints,butnottothever-texpointsoftherefinementrules.Itwasourpurposetousethisre-finementtogenerateapartitioningofthedeformablespacebyitscells,andforthispurpose,thiscalculationappearstoworkverywell.Adetailedtheoreticalanalysisofthecontinuityofthederiva-tivesofthesevolumesattheextraordinarypoints[2,8].willhavetobeaddressedinafuturepaper.

186

1994),ComputerGraphicsProceedings,AnnualConferenceSeries,pages295–302.

[13]KennethI.JoyandRonMacCracken.Therefinementrules

forCatmull-Clarksolids.TechnicalReportCSE-96-1,Depart-mentofComputerScience,UniversityofCalifornia,Davis,January1996.[14]DavidN.KenwrightandDavisA.Lane.Optimizationoftime-dependentparticletracingusingtetrahedraldecomposition.InProceedingsofVisualization’95,pages321–328.IEEECom-puterSociety,1985.[15]CharlesLoop.Smoothsubdivisionsurfacesbasedontrian-gles.Master’sthesis,DepartmentofMathematics,UniversityofUtah,August1987.[16]MikeLounsbery.MultiresolutionAnalysisforSurfacesofAr-bitraryTopologicalType.PhDthesis,DepartmentofCom-puterScienceandEngineering,UniversityofWashington,Seattle,WA,June1994.[17]A.Nasri.Polyhedralsubdivisionmethodsforfree-formsur-faces.ACMTransactionsonGraphics,6:29–73,1987.[18]R.Riesenfeld.OnChaikin’salgorithm.ComputerGraphics

andImageProcessing,4(3):304–310,1975.[19]ThomasW.SederbergandScottR.Parry.Free-formdeforma-tionofsolidgeometricmodels.InComputerGraphics(SIG-GRAPH’86Proceedings),volume20,pages151–160,August1986.[20]KevinJ.Weiler.Topologicalstructuresforgeometricmod-eling.PhDthesis,RensselaerPolytechnicInstitute,August1986.

187

figures/fig7a.tif

figures/fig7b.tiffigures/fig7c.tif

Figure7:Deformingadiskwithastar-shapedlattice.

Figure 1: Lattice Structures

Figure 4: Catmull-Clark Volumes defined by a rectangular and

cylindrical lattice.

Figure 2: Type-3, 4 and 5 cells generated by the subdivision process.

Figure 5: Catmull-Clark volumes with boundary and edge control.The corner vertices are yellow, the sharp edges are red, theboundary edges are green and the internal edges are blue.

Figure 3: The type-4 cells generated by repeated subdivision.

Figure 6: Partitioning of a type-n cell for approximation.The green edges represent the original edges of the cell.The blue edges are generated by the tetrahedral partition.

High-resolution TIFF versions of these images can be found on the CD-ROM in:

S96PR/papers/joy

188

Figure 7: Deforming a disk with a star-shaped lattice.

High-resolution TIFF versions of these images can be found on the CD-ROM in:

S96PR/papers/joy

1

Figure 8: Deforming a block with a barbell-shaped lattice.Figure 9: Deforming the mobster’s arm.

High-resolution TIFF versions of these images can be found on the CD-ROM in:

S96PR/papers/joy

190