rendered constraint solving

https://arachnoid.com/latex/?equ=%3Cp%3EA%20%3Cem%3Econstraint%3C%2Fem%3E%20is%20a%20restriction%20upon%20a%20physically%20modeled%20object%20within%20a%20simulation.%20In%20general%2C%20an%20object%20starts%20with%20six%20%3Cem%3Edegrees%20of%20freedom%3C%2Fem%3E%2C%20representing%20its%20ability%20to%20move%20about%20and%20rotate%20within%20the%20simulated%20world%3B%20by%20restricting%20these%20degrees%20of%20freedom%20in%20various%20ways%2C%20we%20can%20achieve%20many%20interesting%20and%20appealing%20effects.%3C%2Fp%3E%0A%3Cp%3EAs%20the%20CPU%20of%20modern%20computers%20becomes%20more%20and%20more%20powerful%2C%20computations%20can%20be%20put%20towards%20the%20modelling%20and%20solving%20of%20many%20interesting%20physical%20scenarios.%20Constraints%20are%20a%20generalized%20and%20mathematically%20backed%20way%20of%20producing%20such%20scenarios.%20We%20can%20all%20thank%20Erin%20Catto%20for%20his%20initial%20paper%20on%20this%20topic%3A%20%3Ca%20href%3D%22https%3A%2F%2Fcode.google.com%2Fp%2Fbox2d%2Fdownloads%2Fdetail%3Fname%3DGDC2005_ErinCatto.zip%26amp%3Bcan%3D2%26amp%3Bq%3D%22%3EIterative%20Dynamics%20with%20Temporal%20Coherence%3C%2Fa%3E.%20I%20will%20be%20using%20this%20paper%20as%20a%20reference%20when%20writing%20this%20post%2C%20so%20I%20suggest%20you%20at%20least%20take%20a%20peek%20before%20reading%20on%2C%20even%20if%20only%20out%20of%20respect%20for%20Erin's%20work%20(and%20his%20listed%20resource%20works%20and%20special%20thanks%20by%20each%20of%20their%20contributors).%3C%2Fp%3E%0A%3Chr%3E%0A%3Ch2%20class%3D%22nolinks%22%3EGlossary%3C%2Fh2%3E%0A%3Cp%3EThere%20are%20a%20few%20different%20terms%20commonly%20used%20when%20talking%20about%20physics%20engines.%20For%20clarity%2C%20here%20is%20a%20short%20glossary%20to%20use%20as%20a%20reference%20when%20reading%20this%20post%3A%3C%2Fp%3E%0A%3Cul%3E%0A%3Cli%3E%0A%3Cem%3ERigid%20Body%3C%2Fem%3E%3A%20An%20object%20simulated%20within%20a%20physics%20engine.%20The%20object%20is%20assumed%20to%20be%20completely%20rigid%2C%20like%20a%20diamond.%20Most%20of%20the%20time%2C%20rigid%20bodies%20bounce%20around%2C%20slide%20on%20each%20other%2C%20and%20make%20up%20the%20physical%20world%20of%20a%20game.%3C%2Fli%3E%0A%3Cli%3E%0A%3Cem%3EDegree%20of%20Freedom%3C%2Fem%3E%3A%20One%20of%20the%20six%20scalar%20values%20used%20to%20represent%20a%20rigid%20body's%20position%20and%20orientation%20within%20the%20world.%20Three%20scalar%20values%20represent%20position%2C%20and%20three%20represent%20orientation.%3C%2Fli%3E%0A%3Cli%3E%0A%3Cem%3EConstraint%3C%2Fem%3E%3A%20A%20limitation%20placed%20upon%20one%20or%20more%20degrees%20of%20freedom%20of%20a%20rigid%20body.%20Almost%20all%20constraints%20are%20pairwise%2C%20meaning%20they%20affect%20two%20rigid%20bodies%20in%20tandem.%3C%2Fli%3E%0A%3Cli%3E%0A%3Cem%3EJoint%3C%2Fem%3E%3A%20A%20joint%20is%20a%20pairwise%20constraint%2C%20although%20the%20type%20of%20constraint%20is%20%3Cem%3Enot%3C%2Fem%3E%20an%20interpenetration%20constraint.%20All%20other%20types%20of%20constraints%20are%20referred%20to%20as%20a%20joint.%3C%2Fli%3E%0A%3Cli%3E%0A%3Cem%3EContact%20Constraint%3C%2Fem%3E%3A%20A%20pairwise%20constraint%20that%20is%20not%20a%20joint%2C%20meaning%20it%20is%20an%20interpenetration%20constraint.%3C%2Fli%3E%0A%3Cli%3E%0A%3Cem%3EContact%20Normal%3C%2Fem%3E%3A%20The%20direction%20in%20which%20to%20solve%20an%20interpenetration%20constraint.%20This%20is%20usually%20determined%20by%20collision%20detection.%3C%2Fli%3E%0A%3C%2Ful%3E%0A%3Chr%3E%0A%3Ch2%20class%3D%22nolinks%22%3EPrerequisites%3C%2Fh2%3E%0A%3Cp%3EA%20few%20prerequisites%20are%20required%20to%20take%20full%20advantage%20of%20this%20article.%20However%2C%20the%20general%20reader%20can%20still%20enjoy%20much%20the%20material%2C%20although%20it%20is%20best%20to%20have%20a%20basic%20understanding%20of%3A%3C%2Fp%3E%0A%3Cul%3E%0A%3Cli%3EAlgebra%3C%2Fli%3E%0A%3Cli%3ECalculus%3C%2Fli%3E%0A%3Cli%3EVector%20calculus%3C%2Fli%3E%0A%3Cli%3EIntermediate%20to%20advanced%20programming%20skills%20(in%20order%20to%20write%20the%20code)%3C%2Fli%3E%0A%3C%2Ful%3E%0A%3Chr%3E%0A%3Cdiv%20class%3D%22post__inarticle-ad-template%22%20style%3D%22margin-top%3A%2030px%3B%22%3E%3Cdiv%20class%3D%22avert%20fuse-ad%22%3E%3Cdiv%20class%3D%22avert__wrapper%22%3E%3Cdiv%20class%3D%22avert__content%22%3E%3Cdiv%20data-fuse%3D%2221764347426%22%20data-fuse-code%3D%22fuse-slot-21764347426-1%22%20data-fuse-slot%3D%22%2F71161633%2FENV_envato%2Farticle_mid_1%22%3E%3Cdiv%20id%3D%22fuse-slot-21764347426-1%22%20class%3D%22fuse-slot%22%20style%3D%22display%3A%20none%3B%22%20data-google-query-id%3D%22CNDRsZz_1-ECFUxkFQgdCMYMNg%22%3E%3Cdiv%20id%3D%22google_ads_iframe_%2F71161633%2FENV_envato%2Farticle_mid_1_0__container__%22%20style%3D%22border%3A%200pt%20none%3B%20margin%3A%20auto%3B%20text-align%3A%20center%3B%20width%3A%20300px%3B%20height%3A%20250px%3B%22%3E%3C%2Fdiv%3E%3C%2Fdiv%3E%3C%2Fdiv%3E%3C%2Fdiv%3E%3Cdiv%20class%3D%22avert__label%22%3EAdvertisement%3C%2Fdiv%3E%3C%2Fdiv%3E%3C%2Fdiv%3E%3C%2Fdiv%3E%3Ch2%20class%3D%22nolinks%22%3ETypes%20of%20Constraints%3C%2Fh2%3E%0A%3Cp%3ESince%20a%20constraint%20limits%20degrees%20of%20freedom%2C%20let's%20check%20out%20what%20a%20rigid%20body%20does%20when%20utilizing%20six%20at%20once%3A%3C%2Fp%3E%0A%3Cfigure%3E%0A%3Ciframe%20src%3D%22%2F%2Fwww.youtube.com%2Fembed%2Fz5FBESRLOt8%22%20width%3D%22600%22%20height%3D%22450%22%20frameborder%3D%220%22%3E%3C%2Fiframe%3E%3Cbr%3E%0A%3C%2Ffigure%3E%0A%3Cp%3EThe%20above%20rigid%20body%20is%20using%20three%20degrees%20of%20freedom%20to%20translate%20itself%20through%20the%20world.%20The%20last%20three%20are%20used%20to%20constantly%20change%20orientation%20of%20all%20three%20rotational%20axes.%3C%2Fp%3E%0A%3Cp%3ELet's%20now%20look%20at%20a%20couple%20different%20examples%20of%20what%20constraints%20actually%20are.%20The%20most%20familiar%20constraint%20would%20be%20one%20that%20prevents%20two%20rigid%20bodies%20from%20penetrating.%20This%20type%20of%20constraint%20is%20only%20active%20when%20two%20bodies%20are%20penetrating%20one%20another%2C%20and%20drives%20the%20two%20bodies%20apart.%20Once%20this%20interpenetration%20constraint%20is%20active%2C%20it%20is%20easy%20to%20see%20that%20the%20degrees%20of%20freedom%20of%20the%20rigid%20bodies%20become%20limited%20and%20affected%20in%20such%20a%20way%20so%20as%20to%20produce%20an%20interesting%20result%20(the%20interesting%20result%20being%20that%20the%20two%20objects%20can%20collide%20with%20one%20another)%3A%3C%2Fp%3E%0A%3Cfigure%3E%0A%3Ciframe%20src%3D%22%2F%2Fwww.youtube.com%2Fembed%2F_Ziuj50JTD0%22%20width%3D%22600%22%20height%3D%22450%22%20frameborder%3D%220%22%3E%3C%2Fiframe%3E%3Cbr%3E%0A%3C%2Ffigure%3E%0A%3Cp%3EThe%20%3Ca%20href%3D%22http%3A%2F%2Fen.wikipedia.org%2Fwiki%2FHello_world_program%22%3EHello%20World%3C%2Fa%3E%20of%20constraints%20would%20be%20the%20%3Cem%3Edistance%20constraint%3C%2Fem%3E%2C%20where%20two%20points%20on%20two%20rigid%20bodies%20are%20constrained%20to%20be%20an%20exact%20distance%20from%20one%20another.%20You%20can%20imagine%20a%20massless%20rod%20connecting%20two%20points%20together%2C%20where%20this%20rod%20cannot%20be%20stretched%20or%20compressed%3A%3C%2Fp%3E%0A%3Cfigure%3E%0A%3Ciframe%20src%3D%22%2F%2Fwww.youtube.com%2Fembed%2F2zCta1mXuF8%22%20width%3D%22600%22%20height%3D%22450%22%20frameborder%3D%220%22%3E%3C%2Fiframe%3E%3Cbr%3E%0A%3C%2Ffigure%3E%0A%3Cp%3EMany%20types%20of%20constraints%20exist%20for%20all%20sorts%20of%20interesting%20behaviors%2C%20including%3A%20friction%2C%20prismatic%2C%20revolute%2C%20weld%2C%20angle%2C%20and%20more.%3C%2Fp%3E%0A%3Chr%3E%0A%3Ch2%20class%3D%22nolinks%22%3EUnderstanding%20Constraint%20Equations%3C%2Fh2%3E%0A%3Cp%3EIn%20general%20form%2C%20a%20constraint%20is%20a%20scalar%20equation%20equal%20to%20some%20value%20(usually%20zero).%3C%2Fp%3E%0A%3Cp%3E%5Cbegin%7Bequation%7D%3Cbr%3E%0AC(%20l_1%2C%20a_1%2C%20l_2%2C%20a_2%20)%20%3D%200%3Cbr%3E%0A%5Clabel%7Beq1%7D%3Cbr%3E%0A%5Cend%7Bequation%7D%3C%2Fp%3E%0A%3Cp%3EThe%20%5C(l%5C)%20and%20%5C(a%5C)%20terms%20in%20%5Ceqref%7Beq1%7D%20are%20my%20own%20notation%3A%20%5C(l%5C)%20refers%20to%20%3Cem%3Elinear%3C%2Fem%3E%20while%20%5C(a%5C)%20refers%20to%20%3Cem%3Eangular%3C%2Fem%3E.%20The%20subscripts%201%20and%202%20refer%20to%20the%20two%20objects%20within%20the%20constraint.%20As%20you%20can%20see%2C%20there%20exist%20linear%20and%20angular%20inputs%20to%20a%20constraint%20equation%2C%20and%20each%20must%20be%20a%20scalar%20value.%3C%2Fp%3E%0A%3Cp%3ELet's%20take%20a%20step%20back%20to%20look%20at%20the%20distance%20constraint.%20The%20distance%20constraint%20wants%20to%20drive%20the%20distance%20between%20two%20anchor%20points%20on%20two%20bodies%20to%20be%20equal%20to%20some%20scalar%20value%3A%3C%2Fp%3E%0A%3Cp%3E%5Cbegin%7Bequation%7D%3Cbr%3E%0AC(%20l_1%2C%20a_1%2C%20l_2%2C%20a_2%20)%20%3D%20%5Cfrac%7B1%7D%7B2%7D%5B(P_2%20-%20P_1)%5E2%20-%20L%5E2%5D%20%3D%200%3Cbr%3E%0A%5Clabel%7Beq2%7D%3Cbr%3E%0A%5Cend%7Bequation%7D%3C%2Fp%3E%0A%3Cp%3E%5C(L%5C)%20is%20the%20length%20of%20the%20rod%20connecting%20both%20bodies%3B%20%5C(P_1%5C)%20and%20%5C(P_2%5C)%20are%20the%20positions%20of%20the%20two%20bodies.%3C%2Fp%3E%0A%3Cp%3EIn%20its%20current%20form%2C%20this%20constraint%20is%20an%20equation%20of%20position.%20This%20sort%20of%20position%20equation%20is%20%3Ca%20href%3D%22http%3A%2F%2Fen.wikipedia.org%2Fwiki%2FNonlinear_system%22%3Enon-linear%3C%2Fa%3E%2C%26nbsp%3Bwhich%20makes%20solving%20it%20very%20hard.%20A%20method%20of%20solving%20this%20equation%20can%20be%20to%20instead%20derive%20the%20position%20constraint%20(with%20respect%20to%20time)%20and%20use%20a%20velocity%20constraint.%20Resulting%20velocity%20equations%20are%20linear%2C%20making%20them%20solvable.%20Solutions%20can%20then%20be%20integrated%20using%20some%20sort%20of%20integrator%20back%20into%20positional%20form.%3C%2Fp%3E%0A%3Cp%3EIn%20general%20form%2C%20a%20velocity%20constraint%20is%20of%20the%20form%3A%3C%2Fp%3E%0A%3Cp%3E%5Cbegin%7Bequation%7D%3Cbr%3E%0A%5Cdot%7BC%7D(%20l_1%2C%20a_1%2C%20l_2%2C%20a_2%20)%20%3D%200%3Cbr%3E%0A%5Clabel%7Beq3%7D%3Cbr%3E%0A%5Cend%7Bequation%7D%3C%2Fp%3E%0A%3Cdiv%3EThe%20dot%20above%20the%20%5C(C%5C)%26nbsp%3Bin%20%5Ceqref%7Beq3%7D%20refers%20to%20the%20derivative%20of%20%5C(C%5C)%26nbsp%3Bwith%20respect%20to%20time.%20This%20is%20common%20notation%20when%20dealing%20with%20the%20study%20of%20physics.%3C%2Fdiv%3E%0A%3Cp%3EDuring%20the%20derivative%2C%20a%20new%20term%20%5C(J%5C)%20appears%20via%20%3Ca%20href%3D%22http%3A%2F%2Fen.wikipedia.org%2Fwiki%2FChain_rule%22%3Echain%20rule%3C%2Fa%3E%3A%3C%2Fp%3E%0A%3Cp%3E%5Cbegin%7Bequation%7D%3Cbr%3E%0A%5Cdot%7BC%7D(%20l_1%2C%20a_1%2C%20l_2%2C%20a_2%20)%20%3D%20JV%20%3D%200%3Cbr%3E%0A%5Clabel%7Beq4%7D%3Cbr%3E%0A%5Cend%7Bequation%7D%3C%2Fp%3E%0A%3Cp%3EThe%20time%20derivative%20of%20%5C(C%5C)%20creates%20a%20velocity%20vector%20and%20a%20%3Ca%20href%3D%22http%3A%2F%2Fen.wikipedia.org%2Fwiki%2FJacobian_matrix_and_determinant%22%3EJacobian%3C%2Fa%3E.%20The%20Jacobian%20is%20a%201x6%20matrix%20containing%20scalar%20values%20corresponding%20to%20each%20degree%20of%20freedom.%20In%20a%20pairwise%20constraint%2C%20a%20Jacobian%20will%20typically%20contain%2012%20elements%20(enough%20to%20contain%20the%20%5C(l%5C)%20and%20%5C(a%5C)%20terms%20for%20both%20bodies%20%5C(A%5C)%20and%20%5C(B%5C).%3C%2Fp%3E%0A%3Cp%3EA%20system%20of%20constraints%20can%20form%20a%20%3Cem%3Ejoint%3C%2Fem%3E.%20A%20joint%20can%20contain%20many%20constraints%20restricting%20degrees%20of%20freedom%20in%20various%20ways.%20In%20this%20case%2C%20the%20Jacobian%20will%20be%20a%20matrix%20where%20the%20number%20of%20rows%20is%20equal%20to%20the%20number%20of%20constraints%20active%20in%20the%20system.%3C%2Fp%3E%0A%3Cp%3EThe%20Jacobian%20is%20derived%20offline%2C%20by%20hand.%20Once%20a%20Jacobian%20is%20acquired%2C%20code%20to%20compute%20and%20use%20the%20Jacobian%20can%20be%20created.%20As%20you%20can%20see%20from%20%5Ceqref%7Beq4%7D%2C%20the%20velocity%20%5C(V%5C)%20is%20transformed%20from%20%3Ca%20href%3D%22http%3A%2F%2Fen.wikipedia.org%2Fwiki%2FCartesian_coordinate_system%22%3ECartesian%3C%2Fa%3E%20space%20to%20constraint%20space.%20This%20is%20important%20because%20in%20constraint%20space%20the%20origin%20is%20known.%20In%20fact%2C%20any%20target%20can%20be%20known.%20This%20means%20that%20any%20constraint%20can%20be%20derived%20to%20yield%20a%20Jacobian%20that%20can%20transform%20forces%20from%20Cartesian%20space%20to%20constraint%20space.%3C%2Fp%3E%0A%3Cp%3EIn%20constraint%20space%2C%20given%20a%20target%20scalar%2C%20the%20equation%20can%20move%20either%20towards%20or%20away%20from%20the%20target.%20Solutions%20can%20easily%20be%20obtained%20in%20constraint%20space%20to%20move%20the%20current%20state%20of%20a%20rigid%20body%20towards%20a%20target%20state.%20These%20solutions%20can%20then%20be%20transformed%20out%20of%20constraint%20space%20back%20into%20Cartesian%20space%20like%20so%3A%3C%2Fp%3E%0A%3Cp%3E%5Cbegin%7Bequation%7D%3Cbr%3E%0AF%20%3D%20%5Clambda%20J%5ET%3Cbr%3E%0A%5Clabel%7Beq5%7D%3Cbr%3E%0A%5Cend%7Bequation%7D%3C%2Fp%3E%0A%3Cp%3E%5C(F%5C)%20is%20a%20force%20in%20Cartesian%20space%2C%20where%20%5C(J%5ET%5C)%20is%20the%20inverse%20(transposed)%20Jacobian.%20%5C(%5Clambda%5C)%20(lambda)%20is%20a%20scalar%20multiplier.%3C%2Fp%3E%0A%3Cp%3EThink%20of%20the%20Jacobian%20as%20a%20velocity%20vector%2C%20where%20each%20row%20is%20a%20vector%20itself%20(of%20two%20scalar%20values%20in%202D%2C%20and%20three%20scalar%20values%20in%203D)%3A%3C%2Fp%3E%0A%3Cp%3E%5Cbegin%7Bequation%7D%3Cbr%3E%0AJ%20%3D%20%5Cbegin%7Bbmatrix%7D%3Cbr%3E%0Al_1%20%5C%5C%3Cbr%3E%0Aa_1%20%5C%5C%3Cbr%3E%0Al_2%20%5C%5C%3Cbr%3E%0Aa_2%20%5C%5C%3Cbr%3E%0A%5Cend%7Bbmatrix%7D%3Cbr%3E%0A%5Clabel%7Beq6%7D%3Cbr%3E%0A%5Cend%7Bequation%7D%3C%2Fp%3E%0A%3Cp%3ETo%20multiply%20%5C(V%5C)%20by%20%5C(J%5C)%20mathematically%20would%20involve%20matrix%20multiplication.%20However%2C%20most%20elements%20are%20zero%2C%20and%20this%20is%20why%20we%20treat%20the%20Jacobian%20as%20a%20vector.%20This%20allows%20us%20to%20define%20our%20own%20operation%20for%20computing%20%5C(JV%5C)%2C%20as%20in%20%5Ceqref%7Beq4%7D.%3C%2Fp%3E%0A%3Cp%3E%5Cbegin%7Bequation%7D%3Cbr%3E%0AJV%20%3D%20%5Cbegin%7Bbmatrix%7D%3Cbr%3E%0Al_1%20%26amp%3B%20a_1%20%26amp%3B%20l_2%20%26amp%3B%20a_2%3Cbr%3E%0A%5Cend%7Bbmatrix%7D%3Cbr%3E%0A%5Cbegin%7Bbmatrix%7D%3Cbr%3E%0Av_1%20%5C%5C%3Cbr%3E%0A%CF%89_1%20%5C%5C%3Cbr%3E%0Av_2%20%5C%5C%3Cbr%3E%0A%CF%89_2%20%5C%5C%3Cbr%3E%0A%5Cend%7Bbmatrix%7D%3Cbr%3E%0A%5Clabel%7Beq7%7D%3Cbr%3E%0A%5Cend%7Bequation%7D%3C%2Fp%3E%0A%3Cp%3EHere%2C%20%5C(v%5C)%20represents%20linear%20velocity%2C%20and%20%5C(%CF%89%5C)%20(omega)%20represents%20angular%20velocity.%20%5Ceqref%7Beq7%7D%20can%20be%20written%20down%20as%20a%20few%20dot%20products%20and%20multiplications%20in%20order%20to%20provide%20a%20more%20efficient%20computation%20compared%20to%20full%20matrix%20multiplication%3A%3C%2Fp%3E%0A%3Cp%3E%5Cbegin%7Bequation%7D%3Cbr%3E%0AJV%20%3D%20l_1%20%5Ccdot%20v_1%20%2B%20a_1%20%5Ccdot%20%CF%89_1%20%2B%20l_2%20%5Ccdot%20v_2%20%2B%20a_2%20%5Ccdot%20%CF%89_2%3Cbr%3E%0A%5Clabel%7Beq8%7D%3Cbr%3E%0A%5Cend%7Bequation%7D%3C%2Fp%3E%0A%3Cp%3EThe%20Jacobian%20can%20be%20thought%20of%20as%20a%20direction%20vector%20in%20constraint%20space.%20This%20direction%20always%20points%20towards%20the%20target%20in%20the%20direction%20that%20requires%20the%20least%20work%20to%20be%20done.%20Since%20this%20%22direction%22%20Jacobian%20is%20derived%20offline%2C%20all%20that%20needs%20to%20be%20solved%20for%20is%20the%20magnitude%20of%20the%20force%20to%20be%20applied%20in%20order%20to%20uphold%20the%20constraint.%20This%20magnitude%20is%20called%20%5C(%5Clambda%5C).%20%5C(%5Clambda%5C)%20can%20be%20known%20as%20the%20%3Ca%20href%3D%22http%3A%2F%2Fen.wikipedia.org%2Fwiki%2FLagrange_multiplier%22%3ELagrange%20Multiplier%3C%2Fa%3E.%20I%20myself%20have%20not%20formally%20studied%20Lagrangian%20Mechanics%2C%20however%20a%20study%20of%20Lagrangian%20Mechanics%20is%20not%20necessary%20in%20order%20to%20simply%20implement%20constraints.%20(I%20am%20proof%20of%20that!)%20%5C(%5Clambda%5C)%20can%20be%20solved%20using%20a%20%3Cem%3Econstraint%20solver%3C%2Fem%3E%20(more%20on%20this%20later).%3C%2Fp%3E%0A%3Chr%3E%0A%3Ch2%20class%3D%22nolinks%22%3ESolving%20for%20Jacobians%3C%2Fh2%3E%0A%3Cp%3EIn%20%3Ca%20href%3D%22https%3A%2F%2Fcode.google.com%2Fp%2Fbox2d%2Fdownloads%2Fdetail%3Fname%3DGDC2005_ErinCatto.zip%26amp%3Bcan%3D2%26amp%3Bq%3D%22%3EErin%20Catto's%20paper%3C%2Fa%3E%2C%20there%26nbsp%3Bexists%20a%20simple%20outline%20for%20hand-deriving%20Jacobians.%20The%20steps%20are%3A%3C%2Fp%3E%0A%3Col%3E%0A%3Cli%3EStart%20with%20constraint%20equation%20%5C(C%5C)%3C%2Fli%3E%0A%3Cli%3ECompute%20time%20derivative%26nbsp%3B%5C(%5Cdot%7BC%7D%5C)%3C%2Fli%3E%0A%3Cli%3EIsolate%20all%20velocity%20terms%3C%2Fli%3E%0A%3Cli%3EIdentify%20%5C(J%5C)%20by%20inspection%3C%2Fli%3E%0A%3C%2Fol%3E%0A%3Cp%3EThe%20only%20hard%20part%20is%20computing%20the%20derivative%2C%20and%20this%20can%20come%20with%20practice.%20In%20general%2C%20hand-deriving%20constraints%20is%20difficult%2C%20but%20gets%20easier%20with%20time.%3C%2Fp%3E%0A%3Cp%3ELet's%20derive%20a%20valid%20Jacobian%20for%20use%20in%20solving%20a%20distance%20constraint.%20We%20can%20start%20at%20Step%201%20with%20%5Ceqref%7Beq2%7D.%20Here%20are%20some%20details%20for%20Step%202%3A%3C%2Fp%3E%0A%3Cp%3E%5Cbegin%7Bequation%7D%3Cbr%3E%0A%5Cdot%7BC%7D%20%3D%20(P_2%20-%20P_1)(%5Cdot%7BP%7D_2%20-%20%5Cdot%7BP%7D_1)%3Cbr%3E%0A%5Clabel%7Beq9%7D%3Cbr%3E%0A%5Cend%7Bequation%7D%3C%2Fp%3E%0A%3Cp%3E%5Cbegin%7Bequation%7D%3Cbr%3E%0A%5Cdot%7BC%7D%20%3D%20(P_2%20-%20P_1)((v_2%20%2B%20%CF%89_2%20%5Ctimes%20r_2)%20-%20(v_1%20%2B%20%CF%89_1%20%5Ctimes%20r_1))%3Cbr%3E%0A%5Clabel%7Beq10%7D%3Cbr%3E%0A%5Cend%7Bequation%7D%3C%2Fp%3E%0A%3Cp%3E%5C(r_1%5C)%20and%20%5C(r_2%5C)%20are%20vectors%20from%20the%20center%20of%20mass%20to%20the%20anchor%20point%2C%20for%20bodies%201%20and%202%20respectively.%3C%2Fp%3E%0A%3Cp%3EThe%20next%20step%20is%20to%20isolate%20the%20velocity%20terms.%20To%20do%20this%2C%20we'll%20make%20use%20of%20the%20scalar%20triple%20product%20identity%3A%3C%2Fp%3E%0A%3Cp%3E%5Cbegin%7Bequation%7D%3Cbr%3E%0A(P_2%20-%20P_1)%20%3D%20d%3Cbr%3E%0A%5Clabel%7Beq11%7D%3Cbr%3E%0A%5Cend%7Bequation%7D%3C%2Fp%3E%0A%3Cp%3E%5Cbegin%7Bequation%7D%3Cbr%3E%0A%5Cdot%7BC%7D%20%3D%20(d%20%5Ccdot%20v_2%20%2B%20d%20%5Ccdot%20%CF%89_2%20%5Ctimes%20r_2)%20-%20(d%20%5Ccdot%20v_1%20%2B%20d%20%5Ccdot%20%CF%89_1%20%5Ctimes%20r_1)%3Cbr%3E%0A%5Clabel%7Beq12%7D%3Cbr%3E%0A%5Cend%7Bequation%7D%3C%2Fp%3E%0A%3Cp%3E%5Cbegin%7Bequation%7D%3Cbr%3E%0A%5Cdot%7BC%7D%20%3D%20(d%20%5Ccdot%20v_2%20%2B%20%CF%89_2%20%5Ccdot%20r_2%20%5Ctimes%20d)%20-%20(d%20%5Ccdot%20v_1%20%2B%20%CF%89_1%20%5Ccdot%20r_1%20%5Ctimes%20d)%3Cbr%3E%0A%5Clabel%7Beq13%7D%3Cbr%3E%0A%5Cend%7Bequation%7D%3C%2Fp%3E%0A%3Cp%3EThe%20last%20step%20is%20to%20identify%20the%20Jacobian%20by%20inspection.%20In%20order%20to%20do%20this%2C%20all%20the%20coefficients%20of%20all%20velocity%20terms%20(%5C(V%5C)%20and%20%5C(%CF%89%5C))%20will%20be%20used%20as%20the%20Jacobian%20elements.%20Therefore%3A%3C%2Fp%3E%0A%3Cp%3E%5Cbegin%7Bequation%7D%3Cbr%3E%0AJ%20%3D%20%5Cbegin%7Bbmatrix%7D%20-d%20%26amp%3B%20-r_1%20%5Ctimes%20d%20%26amp%3B%20d%20%26amp%3B%20r_2%20%5Ctimes%20d%20%5Cend%7Bbmatrix%7D%3Cbr%3E%0A%5Clabel%7Beq14%7D%3Cbr%3E%0A%5Cend%7Bequation%7D%3C%2Fp%3E%0A%3Ch3%20class%3D%22nolinks%22%3ESome%20more%20Jacobians%3C%2Fh3%3E%0A%3Cp%3EContact%20constraint%20(interpenetration%20constraint)%2C%20where%20%5C(n%5C)%20is%20the%20contact%20normal%3A%3C%2Fp%3E%0A%3Cp%3E%5Cbegin%7Bequation%7D%3Cbr%3E%0AJ%20%3D%20%5Cbegin%7Bbmatrix%7D%20-n%20%26amp%3B%20-r_1%20%5Ctimes%20n%20%26amp%3B%20n%20%26amp%3B%20r_2%20%5Ctimes%20n%20%5Cend%7Bbmatrix%7D%3Cbr%3E%0A%5Clabel%7Beq15%7D%3Cbr%3E%0A%5Cend%7Bequation%7D%3C%2Fp%3E%0A%3Cp%3EFriction%20constraint%20(active%20during%20penetration)%2C%20where%20%5C(t%5C)%26nbsp%3Bis%20an%20axis%20of%20friction%20(2D%20has%20one%20axis%2C%203D%20has%20two)%3A%3C%2Fp%3E%0A%3Cp%3E%5Cbegin%7Bequation%7D%3Cbr%3E%0AJ%20%3D%20%5Cbegin%7Bbmatrix%7D%20-t%20%26amp%3B%20-r_1%20%5Ctimes%20t%20%26amp%3B%20t%20%26amp%3B%20r_2%20%5Ctimes%20t%20%5Cend%7Bbmatrix%7D%3Cbr%3E%0A%5Clabel%7Beq16%7D%3Cbr%3E%0A%5Cend%7Bequation%7D%3C%2Fp%3E%0A%3Chr%3E%0A%3Ch2%20class%3D%22nolinks%22%3ESolving%20Constraints%3C%2Fh2%3E%0A%3Cp%3ENow%20that%20we%20have%20an%20understanding%20of%20what%20a%20constraint%20is%2C%20we%20can%20talk%20about%20how%20to%20solve%20them.%20As%20stated%20earlier%2C%20once%20a%20Jacobian%20is%20hand-derived%2C%20we%20only%20need%20to%20solve%20for%26nbsp%3B%5C(%5Clambda%5C).%20Solving%20a%20single%20constraint%20in%20isolation%20is%20easy%2C%20but%20solving%20many%20constraints%20simultaneously%20is%20hard%2C%20and%20very%20inefficient%20(computationally).%20This%20poses%20a%20problem%2C%20as%20games%20and%20simulations%20will%20likely%20want%20to%20have%20many%20constraints%20active%20all%20at%20once.%3C%2Fp%3E%0A%3Cp%3EAn%20alternative%20method%20to%20solving%20all%20constraints%20simultaneously%20(globally%20solve)%20would%20be%20to%20solve%20the%20constraints%20iteratively.%20By%20solving%20for%20approximations%20of%20the%20solution%2C%20and%20feeding%20in%20previous%20solutions%20to%20the%20equations%2C%20we%20can%20converge%20on%20the%20solution.%3C%2Fp%3E%0A%3Cp%3EOne%20such%20iterative%20solver%20is%20known%20as%20Sequential%20Impulses%2C%20as%20dubbed%20by%20Erin%20Catto.%20Sequential%20Impulses%20is%20very%20similar%20to%20%3Ca%20href%3D%22http%3A%2F%2Fen.wikipedia.org%2Fwiki%2FGauss%25E2%2580%2593Seidel_method%22%3EProjected%20Gauss%20Seidel%3C%2Fa%3E.%20The%20idea%20is%20to%20solve%20all%20constraints%2C%20one%20at%20a%20time%2C%20multiple%20times.%20The%20solutions%20will%20invalidate%20each%20other%2C%20but%20over%20many%20iterations%20each%20individual%20constraint%20will%20converge%20and%20a%20global%20solution%20can%20be%20achieved.%20This%20is%20good!%20Iterative%20solvers%20are%20fast.%3C%2Fp%3E%0A%3Cp%3EOnce%20a%20solution%20is%20achieved%2C%20an%20impulse%20can%20be%20applied%20to%20both%20bodies%20in%20the%20constraint%20in%20order%20to%20enforce%20the%20constraint.%3C%2Fp%3E%0A%3Cp%3ETo%20solve%20a%20single%20constraint%2C%20we%20can%20use%20the%20following%20equation%3A%3C%2Fp%3E%0A%3Cp%3E%5Cbegin%7Bequation%7D%3Cbr%3E%0A%5Clambda%20%3D%20%5Cfrac%7B-(JV%20%2B%20b)%7D%7BJM%5E%7B-1%7DJ%5ET%7D%3Cbr%3E%0A%5Clabel%7Beq17%7D%3Cbr%3E%0A%5Cend%7Bequation%7D%3C%2Fp%3E%0A%3Cp%3E%5C(M%5E%7B-1%7D%5C)%20is%20the%20mass%20of%20the%20constraint%3B%20%5C(b%5C)%20is%20the%20bias%20(more%20on%20this%20later).%3C%2Fp%3E%0A%3Cp%3EThis%20is%20a%20matrix%20containing%20the%20inverse%20mass%20and%20inverse%20inertia%20of%20both%20rigid%20bodies%20in%20the%20constraint.%20The%20following%20is%20the%20mass%20of%20the%20constraint%3B%20note%20that%20%5C(m%5E%7B-1%7D%5C)%20is%20the%20inverse%20mass%20of%20a%20body%2C%20while%20%5C(I%5E%7B-1%7D%5C)%20is%20the%20inverse%20inertia%20of%20a%20body%3A%3C%2Fp%3E%0A%3Cp%3E%5Cbegin%7Bequation%7D%20M%5E%7B-1%7D%20%3D%3Cbr%3E%0A%5Cbegin%7Bbmatrix%7D%3Cbr%3E%0Am_1%20%5E%7B-1%7D%20%26amp%3B%200%20%26amp%3B%200%20%26amp%3B%200%20%5C%5C%3Cbr%3E%0A0%20%26amp%3B%20I_1%20%5E%7B-1%7D%20%26amp%3B%200%20%26amp%3B%200%20%5C%5C%3Cbr%3E%0A0%20%26amp%3B%200%20%26amp%3B%20m_2%20%5E%7B-1%7D%20%26amp%3B%200%20%5C%5C%3Cbr%3E%0A0%20%26amp%3B%200%20%26amp%3B%200%20%26amp%3B%20I_2%20%5E%7B-1%7D%3Cbr%3E%0A%5Cend%7Bbmatrix%7D%3Cbr%3E%0A%5Clabel%7Beq18%7D%3Cbr%3E%0A%5Cend%7Bequation%7D%3C%2Fp%3E%0A%3Cp%3EAlthough%20%5C(M%5E%7B-1%7D%5C)%20is%20theoretically%20a%20matrix%2C%20please%20do%20not%20actually%20model%20it%20as%20such%20(most%20of%20it%20is%20zeroes!).%20Instead%2C%20be%20smart%20about%20what%20sort%20of%20calculations%20you%20do.%3C%2Fp%3E%0A%3Cp%3E%5C(JM%5E%7B-1%7DJ%5ET%5C)%20is%20known%20as%20the%20%3Cem%3Econstraint%20mass%3C%2Fem%3E.%20This%20term%20is%20calculated%20one%20time%20and%20used%20to%20solve%20for%20%5C(%5Clambda%5C).%20We%20calculate%20it%20for%20a%20system%20like%20so%3A%3C%2Fp%3E%0A%3Cp%3E%5Cbegin%7Bequation%7D%3Cbr%3E%0AJM%5E%7B-1%7DJ%5ET%20%3D%20(l_1%20%5Ccdot%20l_1)%20*%20m_1%20%5E%7B-1%7D%20%2B%20(l_2%20%5Ccdot%20l_2)%20*%20m_2%20%5E%7B-1%7D%20%2B%20a_1%20*%20(I_1%20%5E%7B-1%7D%20a_1)%20%2B%20a_2%20*%20(I_2%20%5E%7B-1%7D%20a_2)%3Cbr%3E%0A%5Clabel%7Beq19%7D%3Cbr%3E%0A%5Cend%7Bequation%7D%3C%2Fp%3E%0A%3Cp%3EPlease%20note%20that%20you%20must%20invert%20%5Ceqref%7Beq19%7D%20in%20order%20to%20compute%20%5Ceqref%7Beq17%7D.%3C%2Fp%3E%0A%3Cp%3EThe%20above%20information%20is%20all%20that%20is%20needed%20to%20solve%20a%20constraint!%20A%20force%20in%20Cartesian%20space%20can%20be%20solved%20for%20and%20used%20to%20update%20the%20velocity%20of%20an%20object%2C%20in%20order%20to%20enforce%20a%20constraint.%20Please%20recall%20%5Ceqref%7Beq5%7D%3A%3C%2Fp%3E%0A%3Cp%3E%5Cbegin%7Bequation%7D%3Cbr%3E%0AF%20%3D%20%5Clambda%20J%5ET%20%5C%5C%3Cbr%3E%0AV_%7Bfinal%7D%20%3D%20V_%7Binitial%7D%20%2B%20m%5E%7B-1%7D%20*%20F%20%5C%5C%3Cbr%3E%0A%E2%88%B4%20%5C%5C%3Cbr%3E%0A%5Cbegin%7Bbmatrix%7D%3Cbr%3E%0Av_1%20%5C%5C%3Cbr%3E%0A%CF%89_1%20%5C%5C%3Cbr%3E%0Av_2%20%5C%5C%3Cbr%3E%0A%CF%89_2%20%5C%5C%3Cbr%3E%0A%5Cend%7Bbmatrix%7D%20%2B%3D%20%5Cbegin%7Bbmatrix%7D%3Cbr%3E%0Am_1%20%5E%7B-1%7D%20%26amp%3B%200%20%26amp%3B%200%20%26amp%3B%200%20%5C%5C%3Cbr%3E%0A0%20%26amp%3B%20I_1%20%5E%7B-1%7D%20%26amp%3B%200%20%26amp%3B%200%20%5C%5C%3Cbr%3E%0A0%20%26amp%3B%200%20%26amp%3B%20m_2%20%5E%7B-1%7D%20%26amp%3B%200%20%5C%5C%3Cbr%3E%0A0%20%26amp%3B%200%20%26amp%3B%200%20%26amp%3B%20I_2%20%5E%7B-1%7D%3Cbr%3E%0A%5Cend%7Bbmatrix%7D%5Cbegin%7Bbmatrix%7D%3Cbr%3E%0A%5Clambda%20*%20l_1%20%5C%5C%3Cbr%3E%0A%5Clambda%20*%20a_1%20%5C%5C%3Cbr%3E%0A%5Clambda%20*%20l_2%20%5C%5C%3Cbr%3E%0A%5Clambda%20*%20a_2%20%5C%5C%3Cbr%3E%0A%5Cend%7Bbmatrix%7D%3Cbr%3E%0A%5Clabel%7Beq20%7D%3Cbr%3E%0A%5Cend%7Bequation%7D%3C%2Fp%3E%0A%3Chr%3E%0A%3Ch2%20class%3D%22nolinks%22%3EConstraint%20Drift%3C%2Fh2%3E%0A%3Cp%3EDue%20to%20the%20linearization%20of%20the%20non-linear%20position%20equations%2C%20some%20information%20is%20lost.%20This%20results%20in%20solutions%20that%20don't%20quite%20satisfy%20the%20original%20position%20equation%2C%20but%20do%20satisfy%20the%20velocity%20equations.%20This%20error%20is%20known%20as%20%3Cem%3Econstraint%20drift%3C%2Fem%3E.%20One%20can%20think%20of%20this%20error%20as%20the%20result%20of%20a%20%3Ca%20href%3D%22http%3A%2F%2Fen.wikipedia.org%2Fwiki%2FLinear_approximation%22%3Etangent%20line%20approximation%3C%2Fa%3E.%3C%2Fp%3E%0A%3Cp%3EThere%20are%20a%20few%20different%20ways%20to%20solve%20such%20errors%2C%20all%20of%20which%20approximate%20the%20error%20and%20apply%20some%20form%20of%20correction.%20The%20simplest%20is%20known%20as%20%3Cem%3EBaumgarte%3C%2Fem%3E.%3C%2Fp%3E%0A%3Cp%3EBaumgarte%20is%20a%20small%20addition%20of%20energy%20in%20constraint%20space%2C%20and%20accounts%20for%20the%20%5C(b%5C)%20term%20in%20the%20previous%20equations.%20To%20account%20for%20bias%2C%20here%20is%20a%20modified%20version%20of%20%5Ceqref%7Beq4%7D%3A%3C%2Fp%3E%0A%3Cp%3E%5Cbegin%7Bequation%7D%3Cbr%3E%0A%5Cdot%7BC%7D%20%3D%20JV%20%2B%20b%20%3D%200%3Cbr%3E%0A%5Clabel%7Beq21%7D%3Cbr%3E%0A%5Cend%7Bequation%7D%3C%2Fp%3E%0A%3Cp%3ETo%20calculate%20a%20Baumgarte%20term%20and%20apply%20it%20as%20a%20bias%2C%20we%20must%20inspect%20the%20original%20constraint%20equation%20and%20identify%20a%20suitable%20method%20for%20calculating%20error.%20Baumgarte%20is%20in%20the%20form%3A%3C%2Fp%3E%0A%3Cp%3E%5Cbegin%7Bequation%7D%3Cbr%3E%0AJV%20%3D%20-%5Cbeta%20C%3Cbr%3E%0A%5Clabel%7Beq22%7D%3Cbr%3E%0A%5Cend%7Bequation%7D%3C%2Fp%3E%0A%3Cp%3E%5C(%5Cbeta%5C)%20(Baumgarte%20term)%20is%20a%20tunable%2C%20unit-less%2C%20simulation-dependent%20factor.%20It%20is%20usually%20between%20%3Ccode%3E0.1%3C%2Fcode%3E%20and%20%3Ccode%3E0.3%3C%2Fcode%3E.%3C%2Fp%3E%0A%3Cp%3EIn%20order%20to%20calculate%20the%20bias%20term%2C%20let's%20look%20at%20the%20equation%20for%20the%20non-penetration%20constraint%20%5Ceqref%7Beq15%7D%20before%20deriving%20with%20respect%20to%20time%2C%20where%20%5C(n%5C)%20is%20the%20contact%20normal%3A%3C%2Fp%3E%0A%3Cp%3E%5Cbegin%7Bequation%7D%3Cbr%3E%0AC%20%3D%20%5Cbegin%7Bbmatrix%7D%20-x_1%20%26amp%3B%20-r_1%20%26amp%3B%20x_2%20%26amp%3B%20r_2%20%5Cend%7Bbmatrix%7D%20%5Ccdot%20%5Cvec%7Bn%7D%3Cbr%3E%0A%5Clabel%7Beq23%7D%3Cbr%3E%0A%5Cend%7Bequation%7D%3C%2Fp%3E%0A%3Cp%3EThe%20above%20equation%20is%20saying%20that%20the%20scalar%20error%20of%20%5C(C%5C)%20is%20the%20inter-penetration%20depth%20between%20two%20rigid%20bodies.%3C%2Fp%3E%0A%3Chr%3E%0A%3Ch2%20class%3D%22nolinks%22%3EConclusion%3C%2Fh2%3E%0A%3Cp%3EThanks%20to%20Erin%20Catto%20and%20his%20paper%20on%20constraint%20solving%2C%20we've%20got%20a%20way%20to%20solve%20position%20constraints%20in%20terms%20of%20velocity.%20Many%20interesting%20behaviors%20can%20arise%20from%20constraints%2C%20and%20hopefully%20the%20article%20will%20be%20of%20use%20to%20many%20people.%20As%20always%2C%20please%20feel%20free%20to%20ask%20questions%20or%20give%20comments%20below.%3C%2Fp%3E%0A%3Cp%3EPlease%20see%20%3Ca%20href%3D%22https%3A%2F%2Fcode.google.com%2Fp%2Fbox2d%2Fdownloads%2Fdetail%3Fname%3DBox2D_Lite.zip%26amp%3Bcan%3D2%26amp%3Bq%3D%22%3EBox2D%20Lite%3C%2Fa%3E%20for%20a%20resource%20on%20solving%20various%20types%20of%202D%20constraints%2C%20as%20well%20as%20insight%20into%20many%20implementation%20specifics%20that%20are%20not%20covered%20here.%3C%2Fp%3E