Content deleted Content added
Added free to read link in citations with OAbot #oabot |
m →Software implementations: HTTP to HTTPS for SourceForge |
||
| (13 intermediate revisions by 8 users not shown) | |||
Line 1:
'''Geometric constraint solving''' is [[constraint satisfaction]] in a [[computational geometry]] setting, which has 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=https://www.springer.com/gp/book/9783642637810|language=en}}</ref> A 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 the positions of geometric elements in 2D or 3D space that satisfy the given constraints,<ref>{{cite book|last1=Christoph M. Hoffmann|last2=Pamela J. Vermeer|s2cid=18272588|title=Geometric constraint solving in R2 and R3|
Geometric constraint solving became an integral part of CAD systems in the 80s, when Pro/Engineer
There are additional problems of geometric constraint solving that are related to sets of geometric elements and constraints: dynamic moving of given elements keeping all constraints satisfied,<ref>{{cite journal|title=A constraint-based dynamic geometry system|journal=Computer-Aided Design|volume=42|issue=2|pages=151–161|last1=Marc Freixas|last2=Robert Joan-Arinyo|last3=Antoni Soto-Riera|doi=10.1016/j.cad.2009.02.016|year=2010}}</ref> detection of over- and under-constrained sets and subsets,<ref>{{cite book|last1=Rossignac|first1=Jaroslaw|last2=SIGGRAPH|first2=Joshua Turner, editors
== 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|s2cid=16959899 |url=https://hal.archives-ouvertes.fr/hal-00534926|doi-access=free}}</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|doi-access=free}}</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|doi-access=free}}</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|last1=Marta Hidalgoa|last2=Robert Joan-Arinyo|doi=10.1016/j.cad.2015.05.003|year=2015|hdl=2117/78683|url=https://upcommons.upc.edu/bitstream/2117/78683/8/main.pdf|hdl-access=free}}</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|last1=Xiao-Shan Gao|last2=Qiang Lin|last3=Gui-Fang Zhang|doi=10.1016/j.cad.2005.03.002|year=2006|url=https://hal.inria.fr/inria-00517706/file/Xiao-ShanGao2006a.pdf}}</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|last1=Hichem Barki|last2=Lincong Fang|last3=Dominique Michelucci|last4=Sebti Foufou|doi=10.1016/j.cad.2015.07.011|year=2016|url=https://hal.archives-ouvertes.fr/hal-01205755/file/Re-Parameterization-Barki-etAl-CAD-2016.pdf}}</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|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|arxiv=1006.1126}}</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|s2cid=120186972 }}</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|
Non-linear equation systems are mostly solved by iterative methods that resolve the linear problem at each iteration, the Newton-Raphson method being the most popular example.<ref name="purdue" />
Line 24:
* LGS,<ref>{{cite web|title=Bricsys Component Technology for Constraint Management in 2D/3D|url=https://www.bricsys.com/el-gr/applications/developers/components/}}</ref> a commercial solver developed by LEDAS and currently owned by Bricsys, integrated in [[Cimatron#CimatronE|Cimatron E]] and [[BricsCAD]];<ref>{{cite news|title=Cimatron to Introduce New Motion Simulator Powered by LEDAS LGS 3D|url=http://www.3dcadinfo.com/news/1794/cimatron-to-introduce-new-motion-simulator-powered-by-ledas-lgs-3d/}}</ref><ref>{{cite web|title=Exclusive Q&A: What it means, now that Bricsys bought IP from Ledas|url=http://worldcadaccess.typepad.com/blog/2011/10/exclusive-qa-what-it-means-now-that-bricsys-bought-ip-from-ledas.html}}</ref>
* C3D Solver,<ref>{{cite web|title=C3D Solver|url=http://c3dlabs.com/en/products/solver/}}</ref> a commercially available solver which is a part of [[C3D Toolkit]], integrated into KOMPAS-3D;<ref>{{cite web|title=C3D Toolkit|url=http://c3dlabs.com/en/products/c3d-kernel/}}</ref>
* GeoSolver,<ref>{{cite web|title=GeoSolver Project Page|url=
* [[SolveSpace]], open-source CAD that ships with its own integrated geometric constraint solver
== See also ==
* [[Geometric modeling kernel]]
== References ==
| |||