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.
因篇幅问题不能全部显示,请点此查看更多更全内容
Copyright © 2019- igat.cn 版权所有 赣ICP备2024042791号-1
违法及侵权请联系:TEL:199 1889 7713 E-MAIL:2724546146@qq.com
本站由北京市万商天勤律师事务所王兴未律师提供法律服务