Free-Form Deformation of Solid Geometric ModelsScott SchaeferDeformationDeformationDeformation ApplicationsToy Story © Disney / PixarChallenges in DeformationLarge meshes Large meshes ––millions of polygonsmillions of polygonsNeed efficient techniques for computing and Need efficient techniques for computing and specifying the deformationspecifying the deformationDigital Michelangelo ProjectFFD ContributionsSmooth deformations of arbitrary shapesSmooth deformations of arbitrary shapesLocal control of deformationLocal control of deformationPerforming deformation is fastPerforming deformation is fastWidely usedWidely usedGame/Movie industryGame/Movie industryPart of nearly every 3D modelerPart of nearly every 3D modelerBernstein PolynomialsDifferent polynomial basisDifferent polynomial basisArbitrary degree polynomialsArbitrary degree polynomials322332)1(3)1(3)1(1ttttttttt−−−M322322)1(3)1(3)1()1(2)1()1(tttttttttttt−−−−−−Properties of Bernstein PolynomialsAll polynomials can be written as Bernstein All polynomials can be written as Bernstein polynomialspolynomialsPolynomials sum to onePolynomials sum to one∑∑=−−=−=niiiniinniniiittbta0!)!(!0)1(nniiiniinntttt ))1(()1(0!)!(!+−=−∑=−−Geometric Properties of Bernstein PolynomialsInterpolates its endInterpolates its end--pointspointsEndEnd--point derivatives given by differencespoint derivatives given by differences∑=−−−=niiiniinnittbtF0!)!(!)1()(nbFbF == )1()0(0)()1(')()0('101 −−=−=nnbbnFbbnFBezier CurvesParametric curves defined by Bernstein Parametric curves defined by Bernstein polynomialspolynomials∑=−−−=niiiniinniittyxtytx0!)!(!)1(),())(),((The Tensor Product Operationuu)1(−)1( vv−)1()1)(1()1(vuvuuvvu−−−−∑∑====njjjiiniijijvByvyuBxux0,0,)()()()(∑∑= ==ninjjijijivBuByxvup0 0,,)()(),(),(Free-Form DeformationsEmbed object in uniform gridEmbed object in uniform gridRepresent every point in space as a weighted Represent every point in space as a weighted combination of the control pointscombination of the control points1D Example1D Example0x1x2x3xv∑=−−−==303!)!3(!3)1()(iiiiiittxtxvFree-Form DeformationsEmbed object in uniform gridEmbed object in uniform gridRepresent every point in space as a weighted Represent every point in space as a weighted combination of the control pointscombination of the control points1D Example1D Example∑=−−−+==303!)!3(!330)1()()(iiiiiittxtxv0x310+x320+x10+xvFree-Form DeformationsEmbed object in uniform gridEmbed object in uniform gridRepresent every point in space as a weighted Represent every point in space as a weighted combination of the control pointscombination of the control points1D Example1D Exampletxttxtxviiiiii+=−+==∑=−−0303!)!3(!330)1()()(0x310+x320+x10+xvFree-Form DeformationsEmbed object in uniform gridEmbed object in uniform gridRepresent every point in space as a weighted Represent every point in space as a weighted combination of the control pointscombination of the control points1D Example1D Example∑∑==−−=−−−=3030030!)!3(!3)())(1(iiiiiiiiixxvxvxvα0x310+x320+x10+xv2D Example()3254,00112D Example()3254,00113254==vu2D Example()3254,22)1()1( vu −−3254==vuvvu )1()1(22−−22)1( vu−2)1(2 uvu−22vu2)1()1(2 vuu −−22)1( vu −vvu )1(22−vvuu )1()1(4−−2D Example()3254,25513254==vu2558255162554255642554255322556425532Applying the Deformationjip,v∑∑=i jjijipv,,αApplying the Deformationjip,v∑∑=i jjijipv,,αjip,ˆApplying the Deformationjip,v∑∑=i jjijipv,,αjip,ˆvˆ∑∑=i jjijipv,,ˆˆαExamplesExamplesExamplesExamplesExamplesExamplesExamplesSmoothness of deformation: Smoothness of deformation: CC--11, , CC00, , CC11, , CC22Creates conditions on Bezier control pointsCreates conditions on Bezier control pointsVolume PreservationEnsure that the Ensure that the JacobianJacobianof the FFD is 1of the FFD is 11=∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂zHyHxHzGyGxGzFyFxF)),,(),,,(),,,(()ˆ,ˆ,ˆ( zyxHzyxGzyxFzyx=AdvantagesSmooth deformations of arbitrary shapesSmooth deformations of arbitrary shapesLocal control of deformationLocal control of deformationComputing the deformationsComputing the deformationsis easyis easyDeformations are very fastDeformations are very fastDisadvantagesMust use cubical cells for deformationMust use cubical cells for deformationRestricted to uniform gridRestricted to uniform gridSpace warpingSpace warpingDeformations do not take into account Deformations do not take into account structure of surfacestructure of surfaceMay need many May need many FFD’sFFD’sto achieve a simple to achieve a simple deformationdeformationSummaryWidely used deformation techniqueWidely used deformation techniqueFast, easy to computeFast, easy to computeSome control over volume preservationSome control over volume preservationControllable degrees of smoothnessControllable degrees of smoothnessUniform grids are restrictiveUniform grids are
View Full Document