Dynamic nurbs with geometric constraints for interactive sculpting

forInteractiveSculpting

DemetriTerzopoulosandHongQin

DepartmentofComputerScience,UniversityofToronto

PublishedinACMTransactionsonGraphics,13(2),April,1994,103-136.

Abstract

ThisarticledevelopsadynamicgeneralizationofthenonuniformrationalB-spline(NURBS)model.NURBShavebecomeadefactostandardincommercialmodelingsystemsbecauseoftheirpowertorepresentfree-formshapesaswellascommonanalyticshapes.Todate,however,theyhavebeenviewedaspurelygeometricprim-itivesthatrequiretheusertomanuallyadjustmultiplecontrolpointsandassociatedweightsinordertodesignshapes.DynamicNURBS,orD-NURBS,arephysics-basedmodelsthatincorporatemassdistributions,inter-naldeformationenergies,andotherphysicalquantitiesintothepopularNURBSgeometricsubstrate.UsingD-NURBS,amodelercaninteractivelysculptcurvesandsurfacesanddesigncomplexshapestorequiredspecifi-cationsnotonlyinthetraditionalindirectfashion,byadjustingcontrolpointsandweights,butalsothroughdirectphysicalmanipulation,byapplyingsimulatedforcesandlocalandglobalshapeconstraints.D-NURBSmoveanddeforminaphysicallyintuitivemannerinresponsetotheuser’sdirectmanipulations.Theirdynamicbe-haviorresultsfromthenumericalintegrationofasetofnonlineardifferentialequationsthatautomaticallyevolvethecontrolpointsandweightsinresponsetotheappliedforcesandconstraints.Toderivetheseequations,weemployLagrangianmechanicsandafinite-element-likediscretization.OurapproachsupportsthetrimmingofD-NURBSsurfacesusingD-NURBScurves.WedemonstrateD-NURBSmodelsandconstraintsinapplicationsincludingtheroundingofsolids,optimalsurfacefittingtounstructureddata,surfacedesignfromcrosssections,andfree-formdeformation.Wealsointroduceanewtechniquefor2DshapemetamorphosisusingconstrainedD-NURBSsurfaces.

CRCategoriesandSubjectDescriptors:I.3.5[ComputerGraphics]:ComputationalGeometryandObjectModeling—Curve,Surface,solid,andobjectrepresentations;Physicallybasedmodeling;splines;I.3.6[Com-puterGraphics]:MethodologyandTechniques—Interactiontechniques.GeneralTerms:Algorithms,Design,Theory

AdditionalKeywordsandPhrases:CAGD,NURBS,DeformableModels,Dynamics,Constraints,FiniteEle-ments,Trimming,SolidRounding,OptimalCurveandSurfaceFitting,Cross-SectionalShapeDesign,Free-FormDeformation,ShapeMetamorphosis.

1

PublishedinACMTransactionsonGraphics,13(2),April,1994,103-136.2

1Introduction

In1975Versprille[40]proposedtheNon-UniformRationalB-SplinesorNURBS.ThisshaperepresentationforgeometricdesigngeneralizedRiesenfeld’sB-splines.NURBSquicklygainedpopularityandwereincorporatedintoseveralcommercialmodelingsystems[23].TheNURBSrepresentationhasseveralattractiveproperties.Itoffersaunifiedmathematicalformulationforrepresentingnotonlyfree-formcurvesandsurfaces,butalsostandardanalyticshapessuchasconics,quadrics,andsurfacesofrevolution.Byadjustingthepositionsofcontrolpointsandmanipulatingassociatedweights,onecandesignalargevarietyofshapesusingNURBS[10,12,24,21,22,23,39].

BecauseNURBSareapurelygeometricrepresentation,however,theirextraordinaryflexibilityhassomedraw-backs:

Thedesignerisfacedwiththetediumofindirectshapemanipulationthroughabewilderingvarietyofgeomet-ricparameters;i.e.,byrepositioningcontrolpoints,adjustingweights,andmodifyingknotvectors.Despitetherecentprevalenceofsophisticated3Dinteractiondevices,theindirectgeometricdesignprocessremainsclumsyandtimeconsumingingeneral.

Shapedesigntorequiredspecificationsbymanualadjustmentofavailablegeometricdegreesoffreedomisoftenelusive,becauserelevantdesigntolerancesaretypicallyshape-orientedandnotcontrolpoint/weightoriented.Thegeometric“redundancy”ofNURBStendstomakegeometricshaperefinementadhocandambiguous;forinstance,toadjustashapeshouldthedesignermoveacontrolpoint,orchangeaweight,ormovetwocontrolpoints,etc.?

Typicaldesignrequirementsmaybestatedinbothquantitativeandqualitativeterms,suchas“afairandpleasingsurfacewhichapproximatesscattereddataandinterpolatesacross-sectioncurve.”Suchrequirementsimposebothlocalandglobalconstraintsonshape.Theincrementalmanipulationoflocalshapeparameterstosatisfycomplexlocalandglobalshapeconstraintsisatbestcumbersomeandoftenunproductive.

Physics-basedmodelingprovidesameanstoovercomethesedrawbacks.Free-formdeformablemodels,whichwereintroducedtocomputergraphicsin[37]andfurtherdevelopedin[36,26,33,20,34,17]areparticularlyrelevantinthecontextofmodelingwithNURBS.Importantadvantagesaccruefromthedeformablemodelapproach[36]:

Thebehaviorofthedeformablemodelisgovernedbyphysicallaws.Throughacomputationalphysicssimu-lation,themodelrespondsdynamicallytoappliedsimulatedforcesinanaturalandpredictableway.Shapescanbesculptedinteractivelyusingavarietyofforce-based“tools.”

Theequilibriumstateofthedynamicmodelischaracterizedbyaminimumofthepotentialenergyofthemodelsubjecttoimposedconstraints[35].Itispossibletoformulatepotentialenergyfunctionalsthatsatisfylocalandglobaldesigncriteria,suchascurveorsurface(piecewise)smoothness,andtoimposegeometricconstraintsrelevanttoshapedesign.

Thephysicalmodelmaybebuiltuponastandardgeometricfoundation,suchasfree-formparametriccurveandsurfacerepresentations.Thismeansthatwhileshapedesignmayproceedinteractivelyorautomaticallyatthephysicallevel,existinggeometrictoolkitsareconcurrentlyapplicableatthegeometriclevel.

Inthisarticle,weproposeDynamicNURBS,orD-NURBS.D-NURBSarephysics-basedmodelsthatincor-poratemassdistributions,internaldeformationenergies,andotherphysicalquantitiesintotheNURBSgeometricsubstrate.Timeisfundamentaltothedynamicformulation.Themodelsaregovernedbydynamicdifferentialequationswhich,whenintegratednumericallythroughtime,continuouslyevolvethecontrolpointsandweightsinresponsetoappliedforces.TheD-NURBSformulationsupportsinteractivedirectmanipulationofNURBScurvesandsurfaces,whichresultsinphysicallymeaningfulhenceintuitivelypredictablemotionandshapevariation.

UsingD-NURBS,amodelercaninteractivelysculptcomplexshapesnotmerelybykinematicadjustmentofcontrolpointsandweights,but,dynamicallyaswell—byapplyingforces.Additionalcontroloverdynamicsculpting

PublishedinACMTransactionsonGraphics,13(2),April,1994,103-136.3

stemsfromthemodificationofphysicalparameterssuchasmass,damping,andelasticproperties.Elasticfunctionalsallowtheimpositionofqualitative“fairness”criteriathroughquantitativemeans.Linearornonlinearconstraintsmaybeimposedeitherashardconstraintsthatmustnottobeviolated,orassoftconstraintstobesatisfiedapproximately.Thelattermaybeinterpretedintuitivelyassimpleforces.OptimalshapedesignresultswhenD-NURBSareallowedtoachievestaticequilibriumsubjecttoshapeconstraints.Allofthesecapabilitiesaresubsumedunderanelegantformulationgroundedinphysics.

Section2discussesthesimilaritiesanddistinctivefeaturesofD-NURBSrelativetopriormodels.Section3brieflyreviewsNURBSgeometryanditsproperties.InSection4,weformulateD-NURBSandderivetheirequationsofmotion.Section5discussestheapplicationofforcesandconstraintsforphysics-baseddesign.WediscussthenumericalsimulationofD-NURBSinSection6.Section7describesourprototypeD-NURBSmodelingsystemandpresentsapplicationsandresults.Section8concludesthearticle.

2Background

DynamicNURBSaremotivatedbypriorresearchaimedatapplyingthedeformablemodelingapproachtoshapedesign.TerzopoulosandFleischer[36]demonstratedsimpleinteractivesculptingusingviscoelasticandplasticmodels.CelnikerandGossard[5]developedaninterestingprototypesystemforinteractivefree-formdesignbasedonthefinite-elementoptimizationofenergyfunctionalsproposedin[36].BloorandWilson[3]developedrelatedmodelsusingsimilarenergiesandnumericaloptimization,andin[2]theyproposedtheuseofB-splinesforthispurpose.Subsequently,CelnikerandWelch[6]investigateddeformableB-splineswithlinearconstraints.WelchandWitkin[42]extendedtheapproachtotrimmedhierarchicalB-splines(seealso[13]).ThingvoldandCohen[38]proposedadeformableB-splinewhosecontrolpointsaremasspointsconnectedbyelasticspringsandhinges.

In[2,6,42]deformableB-splinecurvesandsurfacesaredesignedbyimposingshapecriteriaviathemini-mizationofenergyfunctionalssubjecttohardorsoftgeometricconstraints.TheseconstraintsareimposedthroughLagrangemultipliersorpenaltymethods,respectively.ThesametechniquesareapplicabletoD-NURBS.ComparedtodeformableB-splines,however,D-NURBSarecapableofrepresentingawidervarietyoffree-formshapes,aswellasstandardanalyticshapes.Previousmodelssolvestaticequilibriumproblems,orinthecaseof[6]involvesimplelineardynamicswithdiagonal(arbitrarilylumped)massanddampingmatrices(apparentlyforefficiency).

D-NURBSareamoresophisticateddynamicmodel.Weadopttheapproachproposedin[17]forconvertingarbitrarygeometricmodelsintodynamicmodelsusingLagrangianmechanicsandfiniteelementanalysis.Ourapproachissystematic.Weformulatedeformablecurvesandsurfacesandreducethemtoalgorithmsinaprincipledway,withoutresortingtoanyoftheadhocassumptionsofpriorschemes(c.f.[38]).Becauseourdynamicmodelsallowfullycontinuousmassanddampingdistributions,weobtainbandedmassanddampingmatrices.Theseareknownasconsistentmatricesinthefiniteelementliterature[43].

TheD-NURBScontrolpointsandassociatedweightsbecomegeneralizedcoordinatesintheLagrangianequa-tionsofmotion.Fromaphysics-basedmodelingpointofview,theexistenceofweightsmakestheNURBSgeometrysubstantiallymorechallengingthanB-splinegeometry.SincetheNURBSrationalbasisfunctionsarefunctionallydependentontheweights,D-NURBSdynamicsaregenerallynonlinear,andthemass,damping,andstiffnessmatri-cesmustberecomputedateachsimulationtimestep.Fortunately,thisdoesnotprecludeinteractiveperformanceoncurrentgraphicsworkstations,atleastforthesizeofsurfacemodelsthatappearinourdemonstrations.WeproveseveralmathematicalresultsthatenableustosimplifythemotionequationsandapplynumericalquadraturetotheunderlyingNURBSbasisfunctionstocomputeefficientlytheintegralexpressionsforthematrixentries.

3NURBSGeometry

Inthissection,wereviewtheformulationofNURBScurvesandsurfaces.Wethendescribetheiranalyticandgeometricproperties.Moredetailedmaterialcanbefoundin[4,24,21,22,23,39].

Note,however,thatforstaticweights,thematricesbecometimeinvariantandthecomputationalcostisreducedsignificantly.

PublishedinACMTransactionsonGraphics,13(2),April,1994,103-136.4

3.1Curves

ANURBScurvegeneralizestheB-spline.Itisthecombinationofasetofpiecewiserationalfunctionswithcontrolpointsandassociatedweights:

(1)

whereistheparametricvariableand

,aNURBScurvehasknotsaredefinedrecursivelyas

areB-splinebasisfunctions.Assumingbasisfunctionsofdegreeinnondecreasingsequence:.Thebasisfunctions

for

otherwise

with

Theparametricdomainis.Inmanyapplications,theendknotsarerepeatedwithmultiplicityordertointerpolatetheinitialandfinalcontrolpointsand.

in

3.2Surfaces

ANURBSsurfaceisthegeneralizationofthetensor-productB-splinesurface.Itisdefinedovertheparametricvariablesandas

(2)

controlpointsandweights.AssumingbasisfunctionsalongtheANURBSsurfacehas

and,respectively,thenumberofknotsis.Thetwoparametricaxesofdegree

alongthe-axisandalongthe-axis.nondecreasingknotsequenceis

and.IftheendknotshavemultiplicityandintheTheparametricdomainis

andaxisrespectively,thesurfacepatchwillinterpolatethefourcornersoftheboundarycontrolpoints.

3.3Properties

NURBSgeneralizethenonrationalparametricform.LikenonrationalB-splines,therationalbasisfunctionsofNURBSsumtounity,theyareinfinitelysmoothintheinteriorofaknotspanprovidedthedenominatorisnotzero,

continuouswithknotmultiplicity,whichenablesthemtosatisfydifferentandataknottheyareatleast

smoothnessrequirements.TheyinheritmanyofthepropertiesofnonrationalB-splines,suchasthestrongconvexhullproperty,variationdiminishingproperty,localsupport,andinvarianceunderstandardgeometrictransformations(see[11]formoredetails).Moreover,theyhavesomeadditionalproperties:

NURBSofferacommonmathematicalframeworkforimplicitandparametricpolynomialforms.Inprinciple,theycanrepresentanalyticfunctionssuchasconicsandquadricsprecisely,aswellasfree-formshapes.NURBSincludeweightsasextradegreesoffreedomwhichinfluencelocalshape.Ifaparticularweightiszero,thenthecorrespondingrationalbasisfunctionisalsozeroanditscontrolpointdoesnoteffecttheNURBSshape.Thesplineisattractedtowardacontrolpointmoreifthecorrespondingweightisincreasedandlessiftheweightisdecreased.

ForamoredetaileddiscussionofNURBSproperties,see[23,24,39,12,21,22].

ThemostfrequentlyusedNURBSdesigntechniquesarethespecificationofacontrolpolygon,orinterpolationorapproximationofdatapointstogeneratetheinitialshape.Forsurfacesorsolids,cross-sectionaldesignincludingskinning,sweeping,andswingingoperationsisalsopopular.Theinitialshapeisthenrefinedintothefinaldesired

PublishedinACMTransactionsonGraphics,13(2),April,1994,103-136.5

shapethroughinteractiveadjustmentofcontrolpointsandweightsandpossiblytheadditionordeletionofknots.Therefinementprocessisadhocandoftentedious.Toameliorateit,weproposedynamicNURBS.

4FormulationofD-NURBS

Thissectionformulatesourphysics-basedD-NURBSmodel.TheshapeparametersofgeometricNURBS,whichweredescribedinSection3,playtheroleofgeneralized(physical)coordinatesindynamicNURBS.Weintroducetime,mass,anddeformationenergyintothestandardNURBSformulationandemployLagrangiandynamicstoarriveatthesystemofnonlinearordinarydifferentialequationsthatgoverntheshapeandmotionofD-NURBS.

4.1Curves

Forsimplicity,considerfirstaD-NURBSspacecurve.TheD-NURBScurveisdefinedasin(1),butitisalsoafunctionofthespatialparameterandtime:

(3)

andweights,whicharenowfunctionsoftime,comprisethegeneralizedcoordinatesThecontrolpoints

ofD-NURBS.Tosimplifynotation,weconcatenatethegeneralizedcoordinatesintothefollowingvectors:

wheredenotestransposition.Notethatwecanexpressthecurveasinordertoemphasizeitsdependenceonthevectorofgeneralizedcoordinateswhosecomponentsarefunctionsoftime.Thevelocityofthekinematicsplineis

(4)

istheJacobianmatrix.Becauseisa3-componentwhereanoverstruckdotdenotesatimederivativeand

dimensionalvector,isamatrixwhichistheconcatenationvector-valuedfunctionandisan

and,.Letusinvestigatethecontentsof.For,letofthevectors

beadiagonalmatrixwhosediagonalentriesaretherationalbasisfunctions

andletthe3-vector

Wecollectthe

into

andthe

into

asfollows

PublishedinACMTransactionsonGraphics,13(2),April,1994,103-136.TheJacobianmatrixmaythenbewrittenas

6

Usingtheforegoingnotation,wecanexpress

AppendixAshowsthat

(5)

sothatwecanexpresstheD-NURBSastheproductoftheJacobianmatrixandthegeneralizedcoordinatevector:

(6)

,anditwillenableustosimplifythediscretizedversionoftheD-NURBSAnotherinterestingrelationshipis

differentialequationsandarriveatanefficientnumericalimplementation.

4.2Surfaces

AD-NURBSsurfacehasasimilarstructuretothecurve.Proceedinganalogouslyfrom(2),wedefine

(7)

,Again,thecontrolpointsandweightscomprisethegeneralizedcoordinatesandareassembledintovectors,

and.Twosubscriptsarenowassociatedwiththegeneralizedcoordinates,reflectingthesurfaceparametersand.Forconcreteness,weorderthecomponentsinthesevectorssuchthatthesecondsubscriptvariesfasterthanthefirst,althoughthisconventiondoesnotaffectthederivedresults.

insteadof.Byanalogytoin(4)and(6),weobtainfortheD-Asbefore,wecanwrite

NURBSsurface

(8)

(9)

However,thecontentsoftheJacobiandifferfromthoseinthecurvecase.Toarriveatanexplicitexpressionfor,

,for,and,beadiagonalmatrixwhoseentriesarelet

andletthe3-vector

Asbefore,the

and

areassembledinto

and

,respectively.Hence,

Notethat

isnowa

matrix.

4.3D-NURBSEquationsofMotion

TheprevioustwosectionspresentedD-NURBScurveandsurfacegeometryinaunifiedway.D-NURBSphysics

beasetarebasedonthework-energyversionofLagrangiandynamics[14].Inanabstractphysicalsystem,let

PublishedinACMTransactionsonGraphics,13(2),April,1994,103-136.7

bethegeneralizedofgeneralizedcoordinates.Thesefunctionsoftimeareassembledintothevector.Let

appliedforcethatactson.Weassembletheintothevector.Wealsoassumethatistheconcatenationofvectors.

ToproceedwiththeLagrangianformulation,wewilldefinekineticenergy,potentialenergy,andRaleigh

whicharefunctionsofthegeneralizedcoordinatesandtheirderivatives.TheLagrangiandissipationenergy

equationsofmotionarethenexpressedas

(10)

Variantsofthisequationhaveservedasthebasisfordeformablemodelformulations[36].Using(10),wecantake

anarbitrarygeometricmodel,suchasaNURBS,introduceappropriatekinetic,potential,anddissipationenergies,andsystematicallyformulateaphysics-based,dynamicgeneralizationofthemodel[17].

Inthesequel,wewilldiscussonlyD-NURBSsurfaces(wecanconsiderD-NURBScurvesasaspecialcasewithasimplerexpressioninfewervariables).TodefineenergiesandderivetheD-NURBSequationsofmotion,let

bethemassdensityfunctiondefinedovertheparametricdomainofthesurface.Thekineticenergyofthe

surfaceis

(11)

where(using(9))

(12)

isan

massmatrix.Similarly,let

bethedampingdensityfunction.Thedissipationenergyis

(13)

where

(14)

isthedampingmatrix.

FortheelasticpotentialenergyofD-NURBS,wecanadoptthethin-plateundertensionenergymodel[35],whichwasalsousedin[5,42](otherenergiesarepossible,includingthenonquadratic,curvature-basedenergiesin[36,19]):

(15)

andareelasticityfunctionswhichcontrollocaltensionandrigidity,respectively,inthetwoThe

stiffnessmatrixisparametriccoordinatedirections.Inviewof(8),the

(16)

wherethesubscriptsondenoteparametricpartialderivatives.

InAppendixB,weshowthatbyapplying(10),theD-NURBSequationsofmotionaregivenby

(17)

InthecaseoftheD-NURBScurve,thereareonlytwotermsandtwoweightingfunctionsinthepotentialenergyformbecauseofthe

.singlespatialparameter:

PublishedinACMTransactionsonGraphics,13(2),April,1994,103-136.8

wherethegeneralizedforcevector,obtainedthroughtheprincipleofvirtualwork[14]donebytheappliedforce

,isdistribution

(18)

andwhere

5ForcesandConstraints

WehavederivedtheLagrangianequationsofmotionforD-NURBS.WhenworkingwithD-NURBS,amodeler

mayimposedesignrequirementsintermsofenergies,forces,andconstraints.Forinstance,themodelermayapplytime-varyingforcestosculptshapesinteractivelyortooptimallyapproximatedata.Certainaestheticconstraintssuchas“fairness”areexpressibleintermsofelasticenergiesthatgiverisetospecificstiffnessmatrices.Bybuildingthephysics-basedD-NURBSgeneralizationuponthestandardNURBSgeometry,weallowthemodelertocontinuetousethewholespectrumofadvancedgeometricdesigntoolsthathavebecomeprevalent,amongthem,theimpositionofgeometricconstraintsthatthefinalshapemustsatisfy.Forexample,iftheshapesofcertaincross-sectionalcurvesinaNURBSsurfacemustbecirculararcs,thecontrolpointsassociatedwiththesecurvesmustbeconstrainedgeometricallytoadmitonlycirculararcs.Otherconstraintsincludethespecificationofpositionsofsurfacepoints,thespecificationofsurfacenormalsatsurfacepoints,andcontinuityrequirementsbetweenadjacentsurfacepatchesorcurvearcs.

5.1AppliedForces

IntheD-NURBSdesignscenario,sculptingtoolsmaybeimplementedasappliedforces.TheforceintheD-NURBSequationofmotionrepresentstheneteffectofallappliedforces.Typicalforcefunctionsarespringforces,repulsionforces,gravitationalforces,inflationforces,etc.[36,6,34].

ofaD-NURBSsurfacetoapointinspacewithForexample,considerconnectingamaterialpoint

anidealHookeanspringofstiffness.Thenetappliedspringforceis

(19)

andvanisheswhereistheistheunitdeltafunction.Equation(19)impliesthat

elsewhereonthesurface,butwecangeneralizeitbyreplacingthefunctionwithasmoothkernel(e.g.,aunit

andGaussian)tospreadtheappliedforceoveragreaterportionofthesurface.Furthermore,thepoints

neednotbeconstant,ingeneral.Wecancontroleitherorbothusingamousetoobtainaninteractivespringforce.

5.2LinearConstraints

Lineargeometricconstraintssuchaspoint,curve,andsurfacenormalconstraintsareoftenuseful[6].ToincorporatelineargeometricconstraintsintoD-NURBS,wereducethematricesandvectorsin(17)toaminimalunconstrainedsetofgeneralizedcoordinates.Linearconstraintsaregenerallyexpressibleasfollows:

(20)

isamatrixofcoefficients.If(20)isanunderdeterminedlinearsystem,wecaneliminatevariablestowhere

expressthegeneralizedcoordinatevectoras

(21)

components.Here,isanwhereisanewgeneralizedcoordinatevectorwith

maybecomputedthroughGaussianeliminationorothermeans,andisaconstantvector.

matrix,which

PublishedinACMTransactionsonGraphics,13(2),April,1994,103-136.9

Thelower-dimensionalgeneralizedcoordinatevectorreplacesinthelinearlyconstrainedD-NURBSmodel.Toderivetheequationsofmotionwithconstraints,wecombine(8)and(9)with(21)asfollows:

where

isthenewJacobianmatrixofwithrespectto.NotethatHence,theenergyexpressionsbecome

consistsof

vectors

,for

.

Wealsodefinethe

mass,damping,andstiffnessmatricesoftheconstrainedD-NURBS:

InAppendixCweproveseveralidentitiesthatyieldthefollowingequationsofmotionforD-NURBSwithlinear

constraints:

(22)

wherethegeneralizedforcesare

(23)

andwhere

Although(22)looksmorecomplicatedthan(17),itsimplementationissurprisinglystraightforwardinviewofthesparsenessofandthereducedsizeof.

5.3NonlinearConstraints

Itispossibletoimposenonlineargeometric(equality)constraints

(24)

onD-NURBSthroughLagrangemultipliertechniques[32].Thisapproachincreasesthenumberofdegreesoffree-dom,hencethecomputationalcost,byaddingunknowns—alsoknownasLagrangemultipliers—whichdeterminethemagnitudesoftheconstraintforces.ThemethodisappliedtotheB-splinemodelin[6,42].TheaugmentedLagrangianmethod[18]combinestheLagrangemultiplierswiththesimplerpenaltymethod[26].

OneofthebestknowntechniquesforapplyingconstraintstodynamicmodelsistheBaumgartestabilizationmethod[1]whichsolvesconstrainedequationsofmotionthroughlinearfeedbackcontrol(seealso[17,25]).Weaugment(17)asfollows:

(25)

PublishedinACMTransactionsonGraphics,13(2),April,1994,103-136.10

aregeneralizedforcesstemmingfromtheholonomicconstraintequations.Thetermisthetrans-where

poseoftheconstraintJacobianmatrixandisavectorofLagrangemultipliersthatmustbedetermined.Wecanobtainthesamenumberofequationsasunknowns,bydifferentiating(24)twicewithrespectto

.Baumgart’smethodreplacestheseadditionalequationswithequationsthathavesimilarsolutions,time:

,wherebutwhichareasymptoticallystable;e.g.,thedampedsecond-orderdifferentialequations

andarestabilizationfactors.Foragivenvalueof,wecanchoosetoobtainthecriticallydampedsolution

whichhasthequickestasymptoticdecaytowardsconstraintsatisfaction(24).Takingthesecondtime

derivativeof(24)andrearrangingtermsyields

(26)

WearriveatthefollowingsystemofequationsfortheunknownconstrainedgeneralizedaccelerationsandLagrange

multipliers:

(27)

Thissystemcanbesolvedforandusingstandarddirectoriterativetechniques(orintheleastsquaressense

whenitisoverdeterminedbyconflictingconstraints).

5.4ConstrainingtheWeights

Thecomponentsofmaytakearbitraryfinitevaluesin,butthisisnotthecasefortheweights.Negative

maycausethedenominatortovanishatsomeevaluationpoints,causingthematricestodiverge.componentsof

Althoughnotforbidden,negativeweightsarenotuseful.WeincludeconstraintsinourD-NURBSwhichenforcepositivityofweightvalues.Suchaconstraintiseasilyimplementedbyestablishingapositivelowerboundontheweightvaluesandenforcingitinthenumericalsolutionusingaprojectionmethod.

tendtoflattenthesurfaceinthevicinityofthecontrolAnotherpotentialdifficultyisthatsmallervaluesof

willtendtomovetowardzero.Tocounteractpoints,whichlowersthedeformationenergy.Consequently,the

thistendency,wecanassociatewiththepotentialenergythepenaltyterm

inwhicharedesiredweightsandisscalingfactor.

Wehaveimplementedbothtechniques.Experimentsindicatethattheprojectionschemeworksverywell.Con-sequently,wedonotmakeuseofthepenaltyschemeinourcurrentmodelingsystem.Itmaybeuseful,however,ifthemodelerwantstoconstraintheweightstoassumevaluesnearcertaintargetvalues.

6NumericalImplementation

TheevolutionoftheD-NURBSgeneralizedcoordinatesisdeterminedbythesecond-ordernonlineardifferentialequations(17)or(22),withtime-varyingmass,damping,andstiffnessmatrices.Wecannotobtainananalyticalsolutioningeneral.AnefficientnumericalimplementationofD-NURBSispossible,however,throughtheuseoftechniquesfromfinite-elementanalysis[15].

Standardfiniteelementcodesassembleindividualelementmatricesintotheglobalmatricesthatappearinthediscreteequationsofmotion[43,15].Despitethefactthattheglobalmatricesarestoredusingefficientsparsematrixstorageschemes(whichmaintainonlytheentriesneededformatrixfactorization),matrixassemblyandmatrix-vectormultiplicationsquicklybecometoocostly,particularlyforD-NURBSsurfaceswithhighdimensional.

Inourimplementation,weuseaniterativematrixsolverthatenablesustoavoidthecostsofassemblingthe

matricesassociatedwiththewholeD-NURBScurveorsurface.Rather,weworkwiththeglobal,,and

PublishedinACMTransactionsonGraphics,13(2),April,1994,103-136.11

individualD-NURBSelementmatrices.Weconstructfiniteelementdatastructuresthatcontaintheinformationneededtocomputealloftheelementmatricesindependentlyandinparallel.

6.1DataStructuresforD-NURBSFiniteElements

WeconsideraD-NURBScurvearcorsurfacepatchdefinedbyconsecutiveknotsintheparametricdomaintobeatypeoffiniteelement.WedefineanelementdatastructurewhichcontainsthegeometricspecificationoftheD-NURBSelementalongwithitsphysicalproperties.AcompleteD-NURBScurveorsurfaceisthenimplementedasadatastructurewhichconsistsofanorderedarrayofD-NURBScurveorsurfaceelementswithadditionalinformation.

Theelementstructureincludespointerstotheassociatedgeneralizedcoordinates(controlpointsandweights).Forinstance,9controlpointsandassociatedweightsareneededtodescribeapatchofaquadraticD-NURBSsurface(thetotalnumberofdegreesoffreedomis36).ThegeneralizedcoordinatesassociatedwiththeentireD-NURBScurveorsurfacearestoredintheglobalvector.Notethatneighboringelementswillsharesomegeneralizedcoordinates.Thesharedvariableswillhavemultiplepointersimpingingonthem.

WealsoallocateineachD-NURBSelementanelementalmass,damping,andstiffnessmatrix,andincludeintheelementdatastructurethequantitiesneededtocomputethesematrices.Thesequantitiesincludethemass

,damping,andelasticity,densityfunctions,whichmayberepresentedasanalyticfunctionsorasparametricarraysofsamplevalues.

6.2CalculationofElementMatrices

Weevaluatetheintegralexpressionsforthematrices(12),(14),and(16)numericallyusingGaussianquadrature[27].Weshallexplainthecomputationoftheelementstiffnessmatrix;thecomputationofthemassanddamping

,theexpressionforentrymatricesfollowsuit.Assumingtheelement’sparametricdomainis

ofthestiffnessmatrixofaD-NURBSsurfaceelementtakestheintegralform

(28)

where,accordingto(16),

Here,thearethecolumnsoftheJacobianmatrixfortheD-NURBSsurfaceelement.

WeapplyGaussianquadraturetocomputetheaboveintegralapproximately.Theintegralisobtainedbyapplying

and,wecanfindGaussweights,andGaussianquadratureonthe1-Dintervaltwice.Giveninteger

canbeapproximatedby([27])abscissas,intwodirectionsoftheparametricdomainsuchthat

WeapplythedeBooralgorithm[9]toevaluate.

Generallyspeaking,forintegrandsthatarepolynomialofdegreeorless,Gaussianquadratureevaluatestheintegralexactlywithweightsandabscissas.ForD-NURBS,isnotpolynomialunlessthemodelisreduced

TheentriesoftheD-NURBScurveelementstiffnessmatrixareGiveninteger,wecanfindGaussquadratureabscissasandweights

.

,wheresuchthatcanbeapproximatedasfollows:

PublishedinACMTransactionsonGraphics,13(2),April,1994,103-136.andtobeintegersbetweentoaB-spline.Inoursystem,wechoose

matricescomputedinthiswayleadtostable,convergentsolutions.

12

and.Ourexperimentsrevealthat

6.3DiscreteDynamicsEquations

InordertointegratetheD-NURBSordinarydifferentialequationsofmotion(17)inaninteractivemodelingenviron-ment,itisimportanttoprovidethemodelerordesignerwithvisualfeedbackabouttheevolvingstateofthedynamicmodel.Ratherthanusingcostlytimeintegrationmethodsthattakethelargestpossibletimesteps,itismorecrucialtoprovideasmoothanimationbymaintainingthecontinuityofthedynamicsfromonesteptothenext.Hence,lesscostlyyetstabletimeintegrationmethodsthattakemodesttimestepsaredesirable.

,,and)aresymmetric,sparse,andbanded.SeveralalgorithmsareThematrices,,and(and

availableforthenumericalintegrationoftheD-NURBSordinarydifferentialequationsofmotion.Thesuitabilityofimplicitorexplicitintegrationalgorithmsisdependentonthebandwidthofthematrices,asdeterminedbythedimensionalityoftheparametricspaceandtheorderoftheNURBSbasisfunctions.ThematricesforaD-NURBScurvehaveasinglebandwhichhasahalf-bandwidthof,whereistheorderoftheNURBSbasis.ForD-NURBSsurfaces,thematricesbecomeblockbanded,witheachblockcontainingbandssimilartothoseofdynamiccurves,wheredependsontheorderoftheNURBSbasisintheoppositeparametricdirection.

Weintegratethedifferentialequations(17)throughtimebydiscretizingthederivativeofovertime-steps.

isintegratedusingpriorstatesattimeand.DependingonThestateoftheD-NURBSattime

thechoiceofphysicalparameters,(17)maybeastiffsystem.Weuseanimplicittimeintegrationmethodinordertomaintainthestabilityoftheintegrationscheme.Theimplicitmethodemploysdiscretederivativesofusingbackwarddifferences

Makinguseofthefactthat

,weobtainthetimeintegrationformula

(29)

wherethesuperscriptsdenoteevaluationofthequantitiesattheindicatedtimes,andwheretheremainingquantities

.Forexample,wecanextrapolatethemassmatrixusingtheformulaareevaluatedattime

(30)

,etc.,andlikewisefortheothermatricesandvectorsin(29).Thesimpler,constantextrapolations

([15]Section8.6)alsoworksatisfactorily.

Intheinterestofefficiency,wedonotfactorizethematrixexpressiononthelefthandsideof(29)inorderto

.Instead,weemploytheconjugategradientmethodtoobtainaniterativesolution[27,32].Tosolvefor

achieveinteractivesimulationrates,welimitthenumberofconjugategradientiterationspertimestepto10.We

.Morethan2iterationshaveobservedthat2iterationstypicallysufficetoconvergetoaresidualoflessthan

tendtobenecessarywhenthephysicalparameters(mass,damping,tension,stiffness,appliedforces)arechangeddramaticallyduringinteractivesculpting.

Notethatwhenphysicalparametervaluesarechosensuchthattheequations(17)arenotstiff,itismuchcheapertoemployanexplicittimeintegrationmethodusingforwarddifferences.AppendixDdiscussestheforwarddif-ferenceapproach.Notethattheexplicitmethodrequiresvaluesforthematricesonlyattime,hence(30)isnotneeded.

FortheD-NURBScurve,wesimplyreplacewithin(29)andeverythingproceedsasinthecaseofsurfaces.InthecaseofD-NURBSwithlinearconstraints,wediscretizethederivativesof(ratherthan).Analogousto

PublishedinACMTransactionsonGraphics,13(2),April,1994,103-136.(29),thediscreteversionof(22)is

13

(31)

Sincetherearefewerdegreesoffreedominthanin,fasternumericalimplementationofconstrainedD-NURBS

issparse.Notethatsincetheconjugategradientalgorithmrequiresispossible,providedtheconstraintmatrix

,andexplicitly.Theonlyextracostisthecomputationofonlygradientvectors,weneednotcompute

andthemultiplicationofwithseveralvectorsin(31).

Fornonlinearconstraints,ateachtimestepwecanapplytheconjugategradientalgorithmtosolve(27)fortheLagrangemultipliersandtheconstrainedgeneralizedaccelerations(givenknownand).Wethenintegrateandfromtotoobtaintheconstrainedgeneralizedvelocitiesandcoordinates(e.g.,usingthesimple

;).Eulermethod

6.4Simplifications

Theaboveimplementationstrategypermitsreal-timesimulationofthegeneralD-NURBSmodelonmidrangegraph-icsworkstations.Lengthycurvescanbesimulatedatinteractiverates,ascanquadraticandcubicsurfacesonthe

controlpoints.Itispossibletomakesimplificationsthatfurtherreducethecomputationalexpenseorderof

of(29)and(31),makingitpracticaltoworkwithlargerD-NURBSsurfaces.

First,itisseldomnecessarytosimulatethefullygeneralD-NURBSmodelthroughoutanentiresculptingses-sion.Oncewefreezethevaluesoftheweights,allofthematricesin(17)and(22)areconstantandtheirentriesneednolongerberecomputedateachtimestep.WiththisrestrictedrationalgeneralizationoftheB-splines,inter-activeratesarereadilyobtainedformuchlargersurfaceswithuptoanorderofmagnitudemoredegreesoffreedom.

are,inaddition,equalNotethatD-NURBSreducetodynamicB-splinesifallcomponentsofthefrozenvector

to.

Second,afullimplementationof(17)isappropriateifthemodelsmustrespondwithrealisticdynamics.How-ever,incertainCAGDandsurface-fittingapplicationswherethemodelerisinterestedonlyinthefinalequilibrium

tozero,soconfigurationofthemodel,itmakessensetosimplify(17)bysettingthemassdensityfunction

thattheinertialtermsvanish.Thiseconomizesonstorageandmakesthealgorithmmoreefficient.Withzeromassdensity,(17)reducesto

(32)

while(22)reducesto

(33)

Discretizingthederivativesof

and

in(32)and(33)withbackwarddifferences,weobtaintheintegrationformulas

(34)(35)

and

respectively.

7ModelingEnvironmentandApplications

ThissectiondescribesourD-NURBSmodelingenvironmentandpresentsseveralapplicationsofD-NURBSre-latingtotrimming,solidrounding,optimalcurveandsurfacefitting,cross-sectionaldesignofshapes,free-formdeformation,andshapemetamorphosis.

PublishedinACMTransactionsonGraphics,13(2),April,1994,103-136.14

7.1InteractiveModelingEnvironment

WehavedevelopedaprototypemodelingenvironmentbasedontheD-NURBSmodel.ThesystemiswritteninCanditcurrentlyrunsunderIrisExploreronSiliconGraphicsworkstations.Ourparallelizediterativenumericalalgorithmtakesadvantageofa4D/340VGXmultiprocessor.Todate,ourD-NURBSmodulesimplement3Dcurveandsurfaceobjectswithbasisfunctionordersof2,3,or4(i.e.,fromlineartocubicD-NURBS)withlineargeometricconstraints.TheymaybecombinedwithexistingExplorermodulesfordatainputandobjectrendering.

Usingoursystem,designerscansculptshapesinconventionalgeometricways,suchasbysketchingcontrolpolygons,repositioningcontrolpoints,andadjustingassociatedweights.TheycanalsosatisfydesignrequirementsbyadjustingtheD-NURBSinternalphysicalparameters,variousapplied-forceterms,andconstraints.Physicalparameterssuchasthemass,damping,andstiffnessdensities,andforcegainfactorsareinteractivelyadjustablethroughExplorercontrolpanels.

OurD-NURBSsystemalsoimplements,asspecialcases,rationalB-splines(fixedweightsvalues)andordinaryB-splines(unitweights),henceitencompassesthreerelatedfree-formmodelingschemesintooneunifiedphysics-basedimplementation.Thefollowingsectionsdescribeseveralapplications.

7.2TrimmingCurvesandSurfaces

ThephysicalbasisoftheD-NURBSmodelandournumericalquadratureapproachtocomputingthemass,damping,andstiffnessmatrices(Section6.2)suggestsastraightforwardtechniquefortrimmingD-NURBScurvesandsur-faces.Surfacesmaybetrimmedwitharbitrarycurvesdefinedintheparametricdomain,includingD-NURBScurves.ThetrimmingofD-NURBSisdirectlyanalogoustothetrimmingofexcessmaterialfromreal-worlddeformablewiresandsheets.

ConsideraD-NURBSpatchthatisintersectedbyatrimmingcurve.Thevaluesofmaterialproperties—mass,damping,elasticitydensities—overtheportionofthepatchthatextendsoutsidethetrimmingcurveshouldnotaffectthedynamicsofthetrimmedmodelandaresettozero.TheGaussquadratureproceedsnormally,butabscissasthatsamplezerophysicalparametersmakenocontributiontothesummation.Ofcourse,apatchmaybedisregardedifitfallscompletelyoutsidethetrimmingboundary.Notethattheintegrandsarediscontinuousattheboundaryduetothesuddentransitionofthethephysicalparametervalues.WhilethisdoesnotdestroythecorrectnessofGaussquadrature,wecanexpectreducedaccuracysincetheintegrandisnotsmooth.Thereisnoeasywayaroundthispotentialproblemforarbitraryboundarycurves,otherthantouseMonteCarlointegrationandpaythepenaltyofslowasymptoticconvergence[27].Fortunately,inpractice,theD-NURBSmodelappearstolerantofthereducedintegrationaccuracyinboundaryelements.

Fig.1illustratesthetrimmingofD-NURBSsurfacesusingD-NURBStrimmingcurvesintheparametricdo-main.Fig.1(a)showsthecreationofatriangularsurfacewiththreelinearcurveseachwith4controlpoints.Fig.1(b)showsatrimmedannularsurfacedefinedbytwocirculartrimmingcurveseachwith25controlpoints.Snapshotsareshownofthetrimmedsurfacesundergoingdynamicdeformationsinresponsetoappliedforces.

7.3SolidRounding

Theroundingofsolidsisacommonoperationforthedesignofmechanicalparts.Agoalofthisoperationistoconstructafilletsurfacethatsmoothsbyinterpolatingbetweentwoormoresurfaces.Ingeometricmodeling,thisisusuallydonebyenforcingparametricorgeometriccontinuityrequirementsonthefillet.

D-NURBSprovideanaturalsolutiontothesolidroundingproblem.Incontrasttothegeometricapproach,theD-NURBScanproduceasmoothfilletwiththepropercontinuityrequirementsbyminimizingitsinternaldeformationenergy.Additionalpositionandnormalconstraintsmaybeimposedacrosstheboundaryofthesurface.Thedynamicsimulationautomaticallyproducesthedesiredfinalshape.

Atpresent,oursoftwareassumesuniformmass,damping,andelasticitydensitiesovertheparametricdomain,exceptacrosstrimmingboundaries(seeSection7.2).Thisisstraightforwardlygeneralizabletoaccommodatethenonuniformdensityfunctionsinourformulation,althoughouruserinterfacewouldhavetobeextendedtoaffordtheuserfullcontrolinspecifyingthesefunctions.

PublishedinACMTransactionsonGraphics,13(2),April,1994,103-136.15

(a1)(a2)

(b1)(b2)

Figure1:TrimmingD-NURBSsurfaces:(a)triangularD-NURBSsurface;(b)annularD-NURBSsurface.(a1)Patchoutlinesandcontrolpoints(white)withlineartrimmingcurves.(a2)Interactivedynamicdeformationoftrimmedtriangularsurface.(b1)Patchoutlinesandcontrolpointswithconcentrictrimmingcurves.(b2)Interactivedynamicdeformationofannularsurface.

PublishedinACMTransactionsonGraphics,13(2),April,1994,103-136.16

Fig.2demonstratesedgeroundingusingD-NURBSsurfaces.InFig.2(a1),weroundanedgeattheintersection

controlpoints.Multipleoftwoplanarfaces.ThefacesareformedusingquadraticD-NURBSpatcheswith

controlpointsareusedtoproducethesharpcorner.Wefreethecontrolpointsnearthecornerandfixtheremainingcontrolpointsatthefarboundariestoimposepositionandsurfacenormalconstraints.Afterinitiatingthephysicalsimulation,theD-NURBSroundsthecornerasitachievestheminimalenergyequilibriumstateshowninFig.2(a2).

Fig.2(b1)illustratestheroundingofatrihedralcornerofacube.Thecornerisrepresentedusingaquadratic

controlpoints.ThecornerisroundedwithpositionandnormalconstraintsalongtheD-NURBSsurfacewith

farboundariesofthefaces(Fig.2(b2)).

Theaboveroundingtechniqueiseasilyextensibletoanynumberofsurfacesmeetingatarbitraryangles.Toroundacompletesolid,wecanapplythetechniquetoallofitsedges,corners,etc.

7.4OptimalSurfaceFitting

D-NURBSareapplicabletotheoptimalfittingofregularorscattereddata[28].Themostgeneralandoftenmostusefulcaseoccurswithscattereddata,whentherearefewerormoredatapointsthanunknowns—i.e.,whenthesolutionisunderdeterminedoroverdeterminedbythedata.Inthiscase,D-NURBScanyield“optimal”solutionsbyminimizingthethin-plateundertensiondeformationenergy[35,33].Thesurfacesareoptimalinthesensethattheyprovidethesmoothestcurveorsurface(asmeasuredbythedeformationenergy)whichinterpolatesorapproximatesthedata.

Thedatapointinterpolationproblemamountstoalinearconstraintproblemwhentheweightsarefixed,anditisamenabletotheconstrainttechniquespresentedinSection5.2.Theoptimalapproximationproblemcanbeapproachedinphysicalterms,bycouplingtheD-NURBStothedatathroughHookeanspringforces(19).Weinter-in(19)asthedatapoint(generallyin)andastheD-NURBSparametriccoordinatesassociatedpret

withthedatapoint(whichmaybethenearestmaterialpointtothedatapoint).Thespringconstantdeterminestheclosenessoffittothedatapoint.

WepresentthreeexamplesofsurfacefittingusingD-NURBScoupledtodatapointsthroughspringforces.Fig.3(a)shows19datapointssampledfromahemisphereandtheirinterpolationwithaquadraticD-NURBSsurfacewith49controlpoints.Fig.3(b)shows19datapointsandthereconstructionoftheimpliedconvex/concavesurfacebyaquadraticD-NURBSwith49controlpoints.Thespringforcesassociatedwiththedatapointsareappliedtothenearestpointsonthesurface.InFig.3(c)wereconstructawaveshapefrom25samplepointsusingspringswithfixedattachmentstoaquadraticD-NURBSsurfacewith25controlpoints.

7.5Cross-SectionalDesign

Cross-sectionaldesignisacommonapproachtoshapingsurfacesandsolidsusingcross-sectionalcurves.OurmodelingsystemprovidesthemodelerwithD-NURBSgeneratorcurvesalongwiththemostusefulsurfacegener-atoroperators—sweepingandswinging[23]—forgeneratingcommonsurfacessuchasextrudedsurfaces,naturalquadrics,generalquadrics,ruledsurfaces,andsurfacesofrevolution.Inourcurrentimplementation,themodelercanindirectlysculptthecompositesurfacesbydirectdynamicmanipulationoftheD-NURBSgeneratorcurvessubjecttoconstraints.GeometricconstraintssuchaspositionsandnormalsmaybeassociatedwithD-NURBScurves.

Wepresentthreeexamplesinthecross-sectionaldesignofsurfaces.First,Fig.4showsageneralizedcylinderwith30controlpointscreatedbysweepingagreenclosedcurvewith6controlpointsalongtheredcurvewith5controlpoints(Fig.4(a)).ThegeneralizedcylinderisinteractivelysculptedintovariousshapesbyapplyingspringforcesonthegreenandredcubicD-NURBScurves(Fig.4(b-d)).Second,Fig.5showsatoruswith49controlpointsgeneratedbyswingingthegreencurveovertheredcurve(Fig.5(a)).BothgeneratorsareclosedcubicD-NURBScurveswith7controlpoints.InFig.5(b-d),thetorusisdeformedinteractivelybyapplyingaspringforce.Third,Fig.6showsa35controlpoint“wineglass”shapeobtainedbysweepingthegreengeneratorcurve

Cross-validation[41]providesaprincipledapproachtochoosingtherelevantphysicalparameters—typicallytheratioofdataforcespringconstantstosurfacestiffnesses—forgivendatasets.Forthespecialcaseofzero-meanGaussiandataerrors,optimalapproximationintheleastsquaresresidualsenseresultswhenisproportionaltotheinversevarianceofdataerrors[35].

PublishedinACMTransactionsonGraphics,13(2),April,1994,103-136.17

(a1)(a2)

(b1)(b2)

Figure2:Solidrounding:(a)roundinganedgebetweenpolyhedralfaces;(b)roundingatrihedralvertex.(a1)Initialconfigurationofcontrolpointsandpatches.(a2)RoundedD-NURBSsurfaceinstaticequilibrium.(b1)Initialconfigurationofcontrolpointsandpatches.(b2)RoundedD-NURBSsurface.Inbothexamples,thecontrolpointsalongedgeshavemultiplicity.

PublishedinACMTransactionsonGraphics,13(2),April,1994,103-136.18

(a1)(a2)

(b1)(b2)

(c1)(c2)

Figure3:Optimalsurfacefitting:D-NURBSsurfacesfittosampleddatafrom(a)ahemisphere,(b)acon-vex/concavesurface,(c)asinusoidalsurface.(a–c1)D-NURBSpatchoutlinewithcontrolpoints(white)anddatapoints(red)shown.(a–c2)D-NURBSsurfaceatequilibriumfittedtoscattereddatapoints.Redlinesegmentsin(c2)representspringswithfixedattachmentpointsonsurface.

PublishedinACMTransactionsonGraphics,13(2),April,1994,103-136.19

ontheredgeneratorcurveinFig.6(a).TheredclosedD-NURBScurvehas7controlpointsandthegreenopenD-NURBScurvehas5controlpoints.Theglassisinteractivelysculptedintodifferentsweptshapesusingspringforces(Fig.6(b-d)).

7.6ShapeMetamorphosis

Metamorphosisistheblendingofoneshapeintoanother.Workon3Dshapeblendingincludes[8,16].Theblendingof2Dshapeshaswidespreadapplicationinillustration,animation,etc.,andsimple(e.g.,linear)interpolationtech-niquesusuallyproduceunsatisfactoryresults[29].ShinagawaandKunii[31]proposeanmethodwhichinterpolatesdifferentialpropertiesofthe2Dshapeusingtheelasticsurfacesof[37,36].Motivatedbytheirapproach,weproposeanewtechniquewhichexploitsthepropertiesofD-NURBSsurfaces.D-NURBSprovideminimal-energyblendswhicharemoregeneralthanlinearinterpolantsandwhichmaybecontrolledthroughvariousadditionalconstraintsspecifictotheNURBSgeometry.Forexample,sinceNURBScanrepresentconics,wecanexploittheirabilitytogeneratehelicalsurfacesinordertorepresentrotationalcomponentsofshapemetamorphoses.

OurtechniqueinterpolatesaD-NURBSgeneralizedcylinderbetweentwoormoreplanarshapeswithknowncorrespondence.Theinterpolantisaconstrainedskinnedsurfacebetweenthetwoendcurves.Weinterprettheparametriccoordinatealongthelengthofthesurface,say,asthe(temporal)shapeblendingparameter.Thecoordinatesofthecontrolpointsarefixed,whilethecoordinatesaresubjecttotheD-NURBSdeformationenergyandadditionalconstraints.Weobtainintermediateshapesbyevaluatingcylindercrosssectionsatarbitraryvaluesof.

Someexampleswillhelptoexplainourtechniqueinmoredetail.Fig.7showsminimal-energyD-NURBS

controlpoints(3controlpointsalong)interpolatingbetweentwoclosedellipticalcurves.surfaceswith

andFig.7(b)showsalineargeneralizedcylinderobtainedwithhighsurfacetensioninthedirection:

.Notethatthemorphingellipseshrinksasitrotates,atypicalartifactoflinearinterpolation[29].

Therotationalcomponentcanbepreserved,however,byimposingageometricconstraintontheD-NURBSwhichcreatesahelicalsurfaceinthedirectionofthecylinder,asshowninFig.7(c).Heretheonlynonzerodeformation

.Notethattheinterpolatingsurfacenowbulgesoutsidetheconvexenergyparameteristherigidity

hullbetweenthetwoellipses.Asaconsequencetheinterpolatedellipsesrotateinsteadofshrinking(Fig.7(d)).Ingeneral,wecanobtainafamilyofblendingsurfacesbetweenthesetwoextremesbyusingintermediatevaluesof

andrigidityparameters.Fig.8illustratesthemorphingbetweentwoplanarpolygonalshapes.Thetension

surface.Thepartsofthisfigurearesimilartothoseofthepreviousone.D-NURBSinterpolantisa

7.7Free-FormDeformation

Bezierintroducedtheideaofgloballydeformingashapethroughamappingimplementedasafree-form

(tensorproduct)spline.Theshapeisembeddedinthesplineanddeformedbymanipulatingthespline’scontrolpoints.SederbergandParry[30]popularizedthisconceptoffree-formdeformation(FFD)inthegraphicsliterature.

Wecanarriveataphysics-basedversionoftheFFDinwhichtheobjecttobedeformedisembeddedintheD-NURBS“material”anddeformsalongwiththedeformingD-NURBS.Thephysics-baseddeformationissimilarinmotivationtotheonedevisedin[7],butitoffersfullycontinuousdynamicsbyvirtueofthecontinuousnatureofD-NURBS.Inparticular,wecanapplyforcesatarbitrarypointsintheD-NURBSspacetocontrolthedeformationdirectly(ratherthanthroughindirectmanipulationviacontrolpoints).

8Conclusion

WehavedevelopeddynamicNURBS,aphysics-basedgeneralizationofthewell-knowngeometricNURBScurvesandsurfaces.D-NURBSwerederivedsystematicallythroughtheapplicationofLagrangianmechanicsandimple-mentedusingconceptsfromfiniteelementanalysisandefficientnumericalmethods.WegeneralizedourD-NURBSformulationtoincorporategeometricconstraints.Theformulationextendsnaturallytosolids,albeitatproportion-atelygreatercomputationalcost.

PublishedinACMTransactionsonGraphics,13(2),April,1994,103-136.20

(a)(b)

(c)(d)

Figure4:Interactivedeformationofgeneralizedcylinder.(a)PatchoutlineofgeneralizedcylindercreatedfromtwoD-NURBSgeneratingcurves(controlpointsshown)usingsweepoperation.(b–d)Interactivedynamicdeformationofeithergeneratingcurvecausesglobaldeformationofgeneralizedcylinder.

PublishedinACMTransactionsonGraphics,13(2),April,1994,103-136.21

(a)(b)

(c)(d)

Figure5:Interactivedeformationoftorus.(a)TwoD-NURBSgeneratingcurveswithcontrolpointsshownandpatchoutlineoftorusgeneratedbyswingoperation.(b–d)Interactivedynamicdeformationofeithergeneratingcurvecausesglobaldeformationoftorus.

PublishedinACMTransactionsonGraphics,13(2),April,1994,103-136.22

(a)(b)

(c)(d)

Figure6:Creationanddeformationof“wineglass.”(a)TwoD-NURBSgeneratingcurveswithcontrolpointsandpatchoutlinesofglassformedbyswingoperation.(b–d)DeformationofglasscausedbyinteractivedynamicdeformationofD-NURBSgenerators.

PublishedinACMTransactionsonGraphics,13(2),April,1994,103-136.23

(a)(b)

(c)(d)

Figure7:MetamorphosisbetweentwoplanarellipticalcurvesusingD-NURBSinterpolatingsurface.(a)Controlpointsandpatchoutlineofcylindricalsurfaceterminatedbythetwoplanarcurves.(b)Linearinterpolatingsur-face.(c)Constrainednonlinearinterpolatingsurfacecombinesrigidrotationwithnonrigiddeformation.(d)Anintermediatemorphedcurveobtainedascrosssectionofsurfacein(c).

PublishedinACMTransactionsonGraphics,13(2),April,1994,103-136.24

(a)(b)

(c)(d)

Figure8:MetamorphosisbetweentwoplanarpolygonalcurvesusingD-NURBSinterpolatingsurface.(a)Con-trolpointsandpatchoutlinesofcylindricalsurfaceterminatedbythetwoplanarcurves.(b)Linearinterpolatingsurface.(c)Constrainednonlinearinterpolatingsurfacecombinesrigidrotationwithnonrigiddeformation.(d)Anintermediatemorphedcurveobtainedascrosssectionofsurfacein(c).

PublishedinACMTransactionsonGraphics,13(2),April,1994,103-136.25

WedescribedaprototypeinteractivemodelingsystembasedonD-NURBSanddemonstratedtheflexibilityofourmodelsinavarietyofapplications.WhenworkingwithD-NURBS,adesignerneednotmanipulatetheindividualdegreesoffreedomofanobject.Instead,thedesignercanworkwithsculptingtoolsthatareimplementedintermsofforcesandgeometricconstraints.Sculptingforcesmaybeappliedinteractivelytomovetheobjectorrefineitsshape.TheinteractiveresponseoftheD-NURBSmaybemodifiedbyvaryingitsmassanddampingdistributions.Globaldesignrequirementsmayalsobeachievedbyvaryingphysicalparameterssuchaselasticenergies.

BecauseNURBShavebeenassimilatedintosuchindustrystandardssuchasIGES,PHIGS+,andOpenGL,ourdynamicNURBSmodelpromisestoforgestrongerlinksbetweenestablishedCAGDmethodologiesandnewtechniquesinphysics-basedmodeling.

Acknowledgements

FundingforthisresearchwasprovidedinpartbytheNaturalSciencesandEngineeringResearchCouncilofCanadaandtheInformationTechnologyResearchCenterofOntario.

PublishedinACMTransactionsonGraphics,13(2),April,1994,103-136.26

APositionEquation

Clearly,

and

Toprove(6),wemustshowthat(5)holdstrue.Bydefinition,

Exchangingthesummationorderandindexes,wehave

whichproves(5),hence(6).

Moreover,takingthetimederivativeof(6)yields

Given(4),itfollowsthat

.

BSimplificationofMotionEquations

Applying(10),theD-NURBSmotionequationsare

(36)

Thetwovectorsinvolving

ontherightsideof(36)maybebecombinedintoasinglevector:

(37)

Usingtheproductruleofdifferentiation,wehave

.For(37)tohold,wemusthave

(38)

Itisobviousfrom(11)thatthetwosidesof(38)areintegralsofthetwovectors,respectively.Thetwovectorsin

,(38)areequalwhen,for

(39)

Wenowprove(39).Therightsideisrepresentedas.BasedontheproductruleofdifferentiationandthepropertyoftheJacobianmatrix,weobtainthesimplerexpression

Furthermore,accordingtothepropertyoftheJacobianmatrixandtheobservationthatwecaninterchangetheorder

PublishedinACMTransactionsonGraphics,13(2),April,1994,103-136.ofthecrossderivatives

27

Combiningtheabovetwoexpressionsweobtain

Sinceisascalar,(39)isproved.

Next,wederiveanothermathematicalidentity:

(40)

Theleftsideof(40)istheintegralofthesummationofthefivetermsof(16).Eachofthesefivevectorsisthezerovector.Toseethis,notethatfor,wehave

AccordingtothedefinitionoftheJacobianmatrix,thelefthandsideis,

.Thus,wehave

Theorderofthesecondcrossderivativewithrespecttothevariables

and

isirrelevant,sowefurtherhave

(41)

Now,(41)isthethcomponentofthefirstvectorontheleftsideof(40).Similarly,theotherfourvectorsinsidetheintegraloperatoronthelefthandsideof(40)arezero.

CSimplificationofMotionEquationswithLinearConstraints

Applying(10),theD-NURBSmotionequationswithlinearconstraintsare

(42)

Tosimplify(42)wefirstshowthatitreducestothefollowing

(43)

AsinAppendixB,

.Hence,(43)isalsoexpressedas

(44)

Similarto(38),thetwosidesof(44)areintegralsoftwovectors,respectively.Hence,(44)holdsifcorresponding

,componentsofthetwovectorsareequal;i.e.,for

(45)

PublishedinACMTransactionsonGraphics,13(2),April,1994,103-136.Wenowprove(45).Denotingtherightsideas

28

,wefurtherexpanditusingtheproductruleofdifferentiation

Furthermore,accordingtothepropertyoftheJacobianmatrixandtheirrelevanceoftheorderofdifferentiation,wehave

Combiningtheabovetwoequations,wehave

Sinceisascalar,(45)follows.

Theproofof

(46)

parallelsthatinAppendixB,with

replacing

and

replacing.

DExplicitTimeIntegration

Wediscretizethemotionequationsusingthefollowingfinitedifferencesin

(inthecaseofgeometricconstraints):

Weobtainthediscreteformof(17)as

(47)

Inthisandthefollowingexplicittimeintegrationschemes,allthematricesareevaluatedattime(insteadoftime

asintheimplicitschemes).

ForD-NURBSsurfaceswithlineargeometricconstraints,(22)isdiscretizedas

(48)

FortheD-NURBScurve,wesubstitutewithin(47)and(48).

Thediscretizedformsofthesimplifiedfirstorderequationsofmotion(32)and(33)are

(49)(50)

and

PublishedinACMTransactionsonGraphics,13(2),April,1994,103-136.29

References

[1]J.Baumgarte.Stabilizationofconstraintsandintegralsofmotionindynamicalsystems.Comp.Meth.inAppl.

Mech.andEng.,1:1–16,1972.[2]M.I.G.BloorandM.J.Wilson.RepresentingPDEsurfacesintermsofB-splines.Computer-AidedDesign,

22(6):324–331,1990.[3]M.I.G.BloorandM.J.Wilson.Usingpartialdifferentialequationstogeneratefree-formsurfaces.Computer-AidedDesign,22(4):202–212,1990.[4]W.Bohm,G.Farin,andJ.Kahmann.AsurveyofcurveandsurfacemethodsinCAGD.ComputerAided

GeometricDesign,1(1):1–60,1984.[5]G.CelnikerandD.Gossard.Deformablecurveandsurfacefinite-elementsforfree-formshapedesign.Com-puterGraphics,25(4):257–266,1991.[6]G.CelnikerandW.Welch.LinearconstraintsfordeformableB-splinesurfaces.InProceedings,ACMSympo-siumonInteractive3DGraphics,pages165–170,1992.[7]J.E.Chadwick,D.R.Haumann,andR.E.Parent.Layeredconstructionforanimateddeformablecharacters.

ComputerGraphics,23(3):243–252,19.[8]S.E.ChenandR.Parent.Shapeaveraginganditsapplicationstoindustrialdesign.IEEEComputerGraphics

andApplications,9(1):47–,19.[9]C.deBoor.OncalculatingwithB-Splines.JournalofApproximationTheory,6(1):50–62,1972.[10]G.Farin.Trendsincurveandsurfacedesign.Computer-AidedDesign,21(5):293–296,19.

[11]G.Farin.CurvesandSurfacesforComputeraidedGeometricDesign:APracticalGuide.AcademicPress,

secondedition,1990.[12]G.Farin.FromconicstoNURBS:Atutorialandsurvey.IEEEComputerGraphicsandApplications,12(5):78–

86,Sept.1992.[13]D.R.ForseyandR.H.Bartels.HierarchicalB-splinerefinement.ComputerGraphics,22(4):205–212,1988.[14]B.R.Gossick.Hamilton’sPrincipleandPhysicalSystems.AcademicPress,NewYorkandLondon,1967.[15]H.Kardestuncer.FiniteElementHandbook.McGraw–Hill,NewYork,1987.

[16]A.KaulandJ.Rossignac.Solidinterpolatingdeformations:ConstructionandanimationofPIPs.InF.H.Post

andW.Barth,editors,Proc.Eurographics’91,pages493–505,Amsterdam,1991.NorthHolland.[17]D.MetaxasandD.Terzopoulos.Dynamicdeformationofsolidprimitiveswithconstraints.ComputerGraph-ics,26(2):309–312,1992.[18]M.Minoux.MathematicalProgramming.Wiley,NewYork,1986.[19]H.P.MoretonandC.H.Sequin.

26(2):167–176,1992.

Functionaloptimizationforfairsurfacedesign.

ComputerGraphics,

[20]A.PentlandandJ.Williams.Goodvibrations:Modaldynamicsforgraphicsandanimation.ComputerGraph-ics,23(3):215–222,19.[21]L.Piegl.ModifyingtheshapeofrationalB-splines.part1:curves.Computer-AidedDesign,21(8):509–518,

19.

PublishedinACMTransactionsonGraphics,13(2),April,1994,103-136.30

[22]L.Piegl.ModifyingtheshapeofrationalB-splines.part2:surfaces.Computer-AidedDesign,21(9):538–6,

19.[23]L.Piegl.OnNURBS:Asurvey.IEEEComputerGraphicsandApplications,11(1):55–71,Jan.1991.[24]L.PieglandW.Tiller.CurveandsurfaceconstructionsusingrationalB-splines.Computer-AidedDesign,

19(9):485–498,1987.[25]J.Platt.Ageneralizationofdynamicconstraints.CVGIP:GraphicalModelsandImageProcessing,(6):516–

525,1992.[26]J.PlattandA.Barr.Constraintsmethodsforflexiblemodels.ComputerGraphics,22(4):279–288,1988.[27]W.Press,B.Flanney,S.Teukolsky,andW.Verttering.NemericalRecipes:TheArtofScientificComputing.

CambridgeUniversityPress,Cambridge,UK,1986.[28]L.L.Schumaker.Fittingsurfacestoscattereddata.InG.G.Lorentz,C.K.Chui,andL.L.Schumaker,editors,

ApproximationTheoryII,pages203–267.AcademicPress,NewYork,1976.[29]T.W.Sederberg,P.Gao,G.Wang,andH.Mu.2-Dshapeblending:Anintrinsicsolutiontothevertexpath

problem.InComputerGraphicsProceedings,AnnualConferenceSeries,Proc.ACMSiggraph’93(Anaheim,CA,Aug.,1993),pages15–18,1993.[30]T.W.SederbergandS.R.Parry.Free-formdeformationofsolidgeometricprimitives.ComputerGraphics,

20(4):151–160,1986.[31]Y.ShinagawaandT.L.Kunii.Thedifferentialmodel:Amodelforanimatingtransformationofobjectsusing

differentialinformation.InT.L.Kunii,editor,ModelinginComputerGraphics,pages6–15.Springer-Verlag,Tokyo,1991.[32]G.Strang.IntroductiontoAppliedMathematics.Wellesley-CambridgePress,MA,1986.[33]R.SzeliskiandD.Terzopoulos.Fromsplinestofractals.ComputerGraphics,23(3):51–60,19.

[34]R.SzeliskiandD.Tonnesen.Surfacemodelingwithorientedparticlesystems.ComputerGraphics,26(2):185–

194,1992.[35]D.Terzopoulos.Regularizationofinversevisualproblemsinvolvingdiscontinuities.IEEETransactionson

PatternAnalysisandMachineIntelligence,8(4):413–424,1986.[36]D.TerzopoulosandK.Fleischer.Deformablemodels.TheVisualComputer,4(6):306–331,1988.

[37]D.Terzopoulos,J.Platt,A.Barr,andK.Fleischer.Elasticallydeformablemodels.ComputerGraphics,

21(4):205–214,1987.[38]J.A.ThingvoldandE.Cohen.PhysicalmodelingwithB-splinesurfacesforinteractivedesignandanimation.

ComputerGraphics,24(2):129–137,1990.Proceedings,1990ACMSymposiumonInteractive3DGraphics.[39]W.Tiller.RationalB-splinesforcurveandsurfacerepresentation.IEEEComputerGraphicsandApplications,

3(6):61–69,Sept.1983.[40]K.J.Versprille.Computer-AidedDesignApplicationsoftheRationalB-SplineApproximationform.PhD

thesis,SyracuseUniversity,1975.[41]G.Wahba.SplineModelsforObservationalData.SIAM,Philadelphia,PA,1990.

[42]W.WelchandA.Witkin.Variationalsurfacemodeling.ComputerGraphics,26(2):157–166,1992.[43]O.C.Zienkiewicz.TheFiniteElementMethod.McGraw-Hill,London,thirdedition,1977.