Geometric constraint solving: Difference between revisions

Revision as of 11:21, 2 November 2017

Revision as of 05:08, 3 November 2017

Line 1:

{{Userspace draft|source=ArticleWizard|date=November 2017}}

Geometric constraint solving is [[constraint satisfaction]] in a computational geometry, which has a primary applications in [[computer aided design]].<ref>{{cite book|last1=Roller|first1=edited by Beat Brüderlin, Dieter|title=Geometric Constraint Solving and Applications|date=1998|publisher=Springer Berlin Heidelberg|___location=Berlin, Heidelberg|isbn=978-3-642-58898-3|pages=3-23|url=http://www.springer.com/gp/book/9783642637810|language=en}}</ref> The problem to be solved consists of a given set of geometric elements and a description of geometric [[Constraint (computer-aided design)|constraints]] between the elements, which could be non-parametric (tangency, horizontality, coaxiality, etc) or parametric (like distance, angle, radius). The goal is to find positions of the geometric elements in 2D or 3D space which satisfy the given constraints,<ref>{{cite book|last1=Christoph M. Hoffmann|last2=Pamela J. Vermeer|title=Geometric constraint solving in R2 and R3|url=https://pdfs.semanticscholar.org/5495/673d9bda0ec575a2185ddb890f887328be58.pdf}}</ref> which is done by dedicated software components called geometric constraint solvers.

The geometric constraint solving became necessary part of CAD systems in 80s, when Pro/Engineer firstly introduced feature-based parametric modeling concept.<ref>{{cite book|last1=Robert Joan-Arinyo|title=Basics on Geometric Constraint Solving|url=http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.331.9554&rep=rep1&type=pdf}}</ref><ref>{{cite book|last1=R. Anderl|last2=R. Mendgen|title=Modelling with constraints: theoretical foundation and application|url=http://www.sciencedirect.com/science/article/pii/0010448595000232}}</ref>

There are additional problems of geometric constraint solving that are related to sets of geometric elements and constraints: dynamic moving of given element keeping all the constraints satisfied,<ref>{{cite book|title=A constraint-based dynamic geometry system|last1=Marc Freixas|last2=Robert Joan-Arinyo|last3=Antoni Soto-Riera|url=http://www.sciencedirect.com/science/article/pii/S0010448509000876}}</ref> detection of over- and under-constrained sets and subsets,<ref>{{cite book|last1=Rossignac|first1=Jaroslaw|last2=SIGGRAPH|first2=Joshua Turner, editors ; sponsored by ACM|title=Proceedings : Symposium on Solid Modeling Foundations and CAD/CAM Applications, Radisson Plaza Hotel, Austin, Texas, June 5-7, 1991|date=1991|publisher=Association for Computing Machinery|___location=New York|isbn=0-89791-427-9}}</ref><ref>{{cite book|title=Extensions of the witness method to characterize under-, over- and well-constrained geometric constraint systems|url=http://www.sciencedirect.com/science/article/pii/S0010448511001606}}</ref> auto-constraining of under-constrained problems, etc.

== Methods ==

General scheme of geometric constraint solving consist of modeling of 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 system of equations to be solved:<ref>{{cite book|title=A formalization of geometric constraint systems and their decomposition|last1=Pascal Mathis|last2=Simon E. B. Thierry|url=https://link.springer.com/article/10.1007%2Fs00165-009-0117-8}}</ref> decomposition-recombination planning algorithms,<ref>{{cite book|title=Decomposition Plans for Geometric Constraint Systems, Part I: Performance Measures for CAD|url=http://www.sciencedirect.com/science/article/pii/S0747717100904024}}</ref><ref>{{cite book|title=Decomposition Plans for Geometric Constraint Problems, Part II: New Algorithms|url=http://www.sciencedirect.com/science/article/pii/S0747717100904036}}</ref> tree decomposition,<ref>{{cite book|title=h-graphs: A new representation for tree decompositions of graphs|url=http://www.sciencedirect.com/science/article/pii/S0010448515000688}}</ref> C-tree decomposition,<ref>{{cite book|title=A C-tree decomposition algorithm for 2D and 3D geometric constraint solving|url=http://www.sciencedirect.com/science/article/pii/S0010448505000813}}</ref> graph reduction,<ref>{{cite book|title=A 2D geometric constraint solver using a graph reduction method|url=http://www.sciencedirect.com/science/article/pii/S0965997810001006}}</ref> re-parametrization and reduction,<ref>{{cite book|title=Re-parameterization reduces irreducible geometric constraint systems|url=http://www.sciencedirect.com/science/article/pii/S0010448515001116}}</ref> computing fundamental circuits,<ref>{{cite book|title=Decomposition of geometric constraint graphs based on computing fundamental circuits. Correctness and complexity|url=http://www.sciencedirect.com/science/article/pii/S001044851400030X}}</ref> body-and-cad structure,<ref>{{cite book|title=Body-and-cad geometric constraint systems|url=http://www.sciencedirect.com/science/article/pii/S0925772112000235}}</ref> witness configuration method.<ref>{{cite book|title=Geometric constraint solving: The witness configuration method|url=http://www.sciencedirect.com/science/article/pii/S001044850600025X}}</ref>

Some other methods and approaches include 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 book|title=A geometric constraint solver for 3-D assembly modeling|url=https://link.springer.com/article/10.1007%2Fs00170-004-2391-1?LI=true}}</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}}</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}}</ref> constraint programming and constraint propagation,<ref name="purdue" /><ref>{{cite book|title=Stabilizing 3D modeling with geometric constraints propagation|url=http://www.sciencedirect.com/science/article/pii/S1077314209001003}}</ref> genetic algorithms.<ref>{{cite book|title=Constructive Geometric Constraint Solving: A New Application of Genetic Algorithms|url=https://link.springer.com/chapter/10.1007/3-540-45712-7_73}}</ref>

The solving of non-linear system of equations is mostly done by iterative methods that resolve linear problem on each iteration, Newton-Raphson method being most popular example.<ref name="purdue" />

Line 17:

== 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 book|title=Leading a continuation method by geometry for solving geometric constraints|date=2014|last1=Rémi Imbach|last2=Pascal Schreck|last3=Pascal Mathis|url=http://www.sciencedirect.com/science/article/pii/S0010448513001668}}</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}}</ref>

== Software implementations ==