Geometric constraint solving: Difference between revisions

Revision as of 07:48, 2 November 2017

Revision as of 07:53, 2 November 2017

Line 9:

== 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|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|url=https://pdfs.semanticscholar.org/a1c3/6b6aa83ecc85d28a7cdde258ab1355613926.pdf}}</ref> rule-based computations,<ref name="purdue">{{cite book|title=A Geometric Constraint Solver|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>

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|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 ==

Line 25:

* [https://www.plm.automation.siemens.com/en/products/open/d-cubed/2ddcm/index.shtml DCM] (Dimensional Constraint Manager), a commercial solver from D-Cubed (subsidiary of [[Siemens PLM Software]]), integrated in [[AutoCAD]], [[SolidWorks]], [[PTC Creo|Creo]], and many other popular CAD systems;<ref>{{cite web|title=D-Cubed Customers|url=https://www.plm.automation.siemens.com/en/products/open/d-cubed/customers/}}</ref>

* [https://www.bricsys.com/el-gr/applications/developers/components/ LGS], 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>

* [http://geosolver.sourceforge.net/ GeoSolver], a [[GNU Public License]] [[Python (programming language)|Python]] package for geometric constraint solving.