Geometric constraint solving: Difference between revisions

Revision as of 21:52, 7 February 2021

Latest revision as of 20:14, 9 August 2025

(10 intermediate revisions by 7 users not shown)

Line 3:

Geometric constraint solving became an integral part of CAD systems in the 80s, when Pro/Engineer first introduced a novel concept of feature-based parametric modeling concept.<ref>{{cite book|last1=Robert Joan-Arinyo|title=Basics on Geometric Constraint Solving|citeseerx=10.1.1.331.9554}}</ref><ref>{{cite journal|last1=R. Anderl|last2=R. Mendgen|title=Modelling with constraints: theoretical foundation and application|journal=Computer-Aided Design|volume=28|issue=3|pages=155–168|doi=10.1016/0010-4485(95)00023-2|year=1996}}</ref>

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 ; 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=978-0-89791-427-7}}</ref><ref>{{cite journal|title=Extensions of the witness method to characterize under-, over- and well-constrained geometric constraint systems|journal=Computer-Aided Design|volume=43|issue=10|pages=1234–1249|last1=Simon E.B.Thierry|last2=Pascal Schreck|last3=Dominique Michelucci|last4=Christoph Fünfzig|last5=Jean-David Génevaux|doi=10.1016/j.cad.2011.06.018|year=2011|url=https://hal.archives-ouvertes.fr/hal-00691690/file/cad11.pdf}}</ref> auto-constraining of under-constrained problems, etc.

== 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|s2cid=775489|year=1998|doi=10.1016/s0010-4485(97)00055-9}}</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>

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=httphttps://geosolver.sourceforge.net/}}</ref> a [[GNU General Public License]] [[Python (programming language)|Python]] package for geometric constraint solving.

* [[SolveSpace]], open-source CAD that ships with its own integrated geometric constraint solver

== See also ==

* [[Geometric modeling kernel]]

== References ==