Geometric constraint solving: Difference between revisions

Revision as of 21:53, 13 January 2019

Revision as of 13:17, 19 July 2019

Line 7:

== Methods ==

A general scheme of geometric constraint solving consists of modeling a set of geometric elements and constraints by a system of equations, and then solving this system by non-linear algebraic solver. For the sake of performance, a number of [[Decomposition method (constraint satisfaction)|decomposition techniques]] could be used in order to decrease the size of an equation set:<ref>{{cite journal|title=A formalization of geometric constraint systems and their decomposition|journal=Formal Aspects of Computing|volume=22|issue=2|pages=129–151|last1=Pascal Mathis|last2=Simon E. B. Thierry|doi=10.1007/s00165-009-0117-8|year=2010|url=https://hal.archives-ouvertes.fr/hal-00534926}}</ref> decomposition-recombination planning algorithms,<ref>{{cite journal|title=Decomposition Plans for Geometric Constraint Systems, Part I: Performance Measures for CAD|journal=Journal of Symbolic Computation|volume=31|issue=4|pages=367–408|last1=Christoph M.Hoffman|last2=Andrew Lomonosov|last3=Meera Sitharam|doi=10.1006/jsco.2000.0402|year=2001}}</ref><ref>{{cite journal|title=Decomposition Plans for Geometric Constraint Problems, Part II: New Algorithms|journal=Journal of Symbolic Computation|volume=31|issue=4|pages=409–427|last1=Christoph M.Hoffman|last2=Andrew Lomonosov|last3=Meera Sitharam|doi=10.1006/jsco.2000.0403|year=2001}}</ref> tree decomposition,<ref>{{cite journal|title=h-graphs: A new representation for tree decompositions of graphs|journal=Computer-Aided Design|volume=67-68|pages=38–47|url=http://www.sciencedirect.com/science/article/pii/S0010448515000688|last1=Marta Hidalgoa|last2=Robert Joan-Arinyo|doi=10.1016/j.cad.2015.05.003|year=2015|hdl=2117/78683}}</ref> C-tree decomposition,<ref>{{cite journal|title=A C-tree decomposition algorithm for 2D and 3D geometric constraint solving|journal=Computer-Aided Design|volume=38|pages=1–13|url=http://www.sciencedirect.com/science/article/pii/S0010448505000813|last1=Xiao-Shan Gao|last2=Qiang Lin|last3=Gui-Fang Zhang|doi=10.1016/j.cad.2005.03.002|year=2006}}</ref> graph reduction,<ref>{{cite journal|title=A 2D geometric constraint solver using a graph reduction method|journal=Advances in Engineering Software|volume=41|issue=10–11|pages=1187–1194|last1=Samy Ait-Aoudia|last2=Sebti Foufou|doi=10.1016/j.advengsoft.2010.07.008|year=2010}}</ref> re-parametrization and reduction,<ref>{{cite journal|title=Re-parameterization reduces irreducible geometric constraint systems|journal=Computer-Aided Design|volume=70|pages=182–192|url=http://www.sciencedirect.com/science/article/pii/S0010448515001116|last1=Hichem Barki|last2=Lincong Fang|last3=Dominique Michelucci|last4=Sebti Foufou|doi=10.1016/j.cad.2015.07.011|year=2016}}</ref> computing fundamental circuits,<ref>{{cite journal|title=Decomposition of geometric constraint graphs based on computing fundamental circuits. Correctness and complexity|journal=Computer-Aided Design|volume=52|pages=1–16|url=http://www.sciencedirect.com/science/article/pii/S001044851400030X|last1=R.Joan-Arinyo|last2=M.Tarrés-Puertas|last3=S.Vila-Marta|doi=10.1016/j.cad.2014.02.006|year=2014}}</ref> body-and-cad structure,<ref>{{cite journal|title=Body-and-cad geometric constraint systems|journal=Computational Geometry|volume=45|issue=8|pages=385–405|last1=Kirk Haller|last2=Audrey Lee-St.John|last3=Meera Sitharam|last4=Ileana Streinu|last5=Neil White|doi=10.1016/j.comgeo.2010.06.003|year=2012}}</ref> or the witness configuration method.<ref>{{cite journal|title=Geometric constraint solving: The witness configuration method|journal=Computer-Aided Design|volume=38|issue=4|pages=284–299|last1=Dominique Michelucci|last2=Sebti Foufou|doi=10.1016/j.cad.2006.01.005|year=2006|citeseerx=10.1.1.579.2143}}</ref>

Some other methods and approaches include the degrees of freedom analysis,<ref>{{cite book|last1=Kramer|first1=Glenn A.|title=Solving geometric constraint systems : a case study in kinematics|date=1992|publisher=MIT Press|___location=Cambridge, Mass.|isbn=9780262111645|edition=1:a upplagan.|url=https://mitpress.mit.edu/books/solving-geometric-constraint-systems}}</ref><ref>{{cite journal|title=A geometric constraint solver for 3-D assembly modeling|journal=The International Journal of Advanced Manufacturing Technology|volume=28|issue=5–6|pages=561–570|last1=Xiaobo Peng|last2=Kunwoo Lee|last3=Liping Chen|doi=10.1007/s00170-004-2391-1|year=2006}}</ref> symbolic computations,<ref>{{cite book|title=Solving Geometric Constraint Systems II. A Symbolic Approach and Decision of Rc-constructibility|last1=Xiao-Shan Gao|last2=Shang-Ching Chou|url=https://pdfs.semanticscholar.org/a1c3/6b6aa83ecc85d28a7cdde258ab1355613926.pdf|year=1998}}</ref> rule-based computations,<ref name="purdue">{{cite book|title=A Geometric Constraint Solver|date=1993|url=http://docs.lib.purdue.edu/cgi/viewcontent.cgi?article=2067&context=cstech|last1=William Bouma|last2=Ioannis Fudos|last3=Christoph M. Hoffmann|last4=Jiazhen Cai|last5=Robert Paige}}</ref> constraint programming and constraint propagation,<ref name="purdue" /><ref>{{cite journal|title=Stabilizing 3D modeling with geometric constraints propagation|journal=Computer Vision and Image Understanding|volume=113|issue=11|pages=1147–1157|last1=Michela Farenzena|last2=Andrea Fusiello|doi=10.1016/j.cviu.2009.05.004|year=2009}}</ref> and genetic algorithms.<ref>{{cite book|last1=R. Joan-Arinyo|last2=M.V. Luzón|last3=A. Soto|doi=10.1007/3-540-45712-7_73|title = Parallel Problem Solving from Nature — PPSN VII|volume = 2439|pages=759–768|series = Lecture Notes in Computer Science|year = 2002|isbn = 978-3-540-44139-7}}</ref>

Line 15:

== Applications ==

Geometric constraint solving has applications in a wide variety of fields, such as computer aided design, mechanical engineering, [[inverse kinematics]] and [[robotics]],<ref>{{cite web|title=Geometric constraint solver|url=http://www.coppeliarobotics.com/helpFiles/en/geometricConstraintSolverModule.htm}}</ref> architecture and construction, molecular chemistry,<ref>{{cite journal|title=Leading a continuation method by geometry for solving geometric constraints|journal=Computer-Aided Design|volume=46|pages=138–147|date=2014|last1=Rémi Imbach|last2=Pascal Schreck|last3=Pascal Mathis|url=http://www.sciencedirect.com/science/article/pii/S0010448513001668|doi=10.1016/j.cad.2013.08.026}}</ref> and geometric theorem proving. The primary application area is computer aided design, where geometric constraint solving is used in both parametric history-based modeling and variational direct modeling.<ref>{{cite book|title=Variational Direct Modeling: How to Keep Design Intent in History-Free CAD|date=2008|url=http://www.ledas.com/pdf/VariationalDirectModeling.pdf|last1=Dmitry Ushakov}}</ref>

== Software implementations ==