Geometric constraint solving: Difference between revisions

From Wikipedia, the free encyclopedia
Browse history interactively
← Previous editNext edit →
Content deleted Content added
VisualWikitext
m ce
SwisterTwister (talk | contribs)
187,094 edits
No edit summary
Line 1: Line 1:
{{cleanup|reason=external links in the Software implementations section should be formatted as references.|date=December 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> 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|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.
'''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> 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|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.


Line 22: Line 21:
The list of geometric constraint solvers includes at least
The list of geometric constraint solvers includes at least


* [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>
*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>
*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://c3dlabs.com/en/products/solver/ C3D Solver], 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>
*C3D, 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>
* [http://geosolver.sourceforge.net/ GeoSolver], a [[GNU Public License]] [[Python (programming language)|Python]] package for geometric constraint solving.
*GeoSolver, a [[GNU Public License]] [[Python (programming language)|Python]] package for geometric constraint solving.


== References ==
== References ==

Revision as of 04:32, 28 December 2017

Geometric constraint solving is constraint satisfaction in a computational geometry, which has a primary applications in computer aided design.[1] A problem to be solved consists of a given set of geometric elements and a description of geometric 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,[2] which is done by dedicated software components called geometric constraint solvers.

Geometric constraint solving became an integral part of CAD systems in the 80s, when Pro/Engineer firstly introduced a novel concept of feature-based parametric modeling concept.[3][4]

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,[5] detection of over- and under-constrained sets and subsets,[6][7] auto-constraining of under-constrained problems, etc.

Methods

A general scheme of geometric constraint solving comprises 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 techniques could be used in order to decrease the size of an equation set:[8] decomposition-recombination planning algorithms,[9][10] tree decomposition,[11] C-tree decomposition,[12] graph reduction,[13] re-parametrization and reduction,[14] computing fundamental circuits,[15] body-and-cad structure,[16] or the witness configuration method.[17]

Some other methods and approaches include the degrees of freedom analysis,[18][19] symbolic computations,[20] rule-based computations,[21] constraint programming and constraint propagation,[21][22] and genetic algorithms.[23]

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.[21]

Applications

Geometric constraint solving has applications in a wide variety of fields, such as computer aided design, mechanical engineering, inverse kinematics and robotics,[24] architecture and construction, molecular chemistry,[25] 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.[26]

Software implementations

The list of geometric constraint solvers includes at least

References

  1. ^ Roller, edited by Beat Brüderlin, Dieter (1998). Geometric Constraint Solving and Applications. Berlin, Heidelberg: Springer Berlin Heidelberg. pp. 3–23. ISBN 978-3-642-58898-3. {{cite book}}: |first1= has generic name (help)CS1 maint: multiple names: authors list (link)
  2. ^ Christoph M. Hoffmann; Pamela J. Vermeer. Geometric constraint solving in R2 and R3 (PDF).
  3. ^ Robert Joan-Arinyo. Basics on Geometric Constraint Solving.
  4. ^ R. Anderl; R. Mendgen. Modelling with constraints: theoretical foundation and application.
  5. ^ Marc Freixas; Robert Joan-Arinyo; Antoni Soto-Riera. A constraint-based dynamic geometry system.
  6. ^ Rossignac, Jaroslaw; SIGGRAPH, Joshua Turner, editors ; sponsored by ACM (1991). Proceedings : Symposium on Solid Modeling Foundations and CAD/CAM Applications, Radisson Plaza Hotel, Austin, Texas, June 5-7, 1991. New York: Association for Computing Machinery. ISBN 0-89791-427-9. {{cite book}}: |first2= has generic name (help)CS1 maint: multiple names: authors list (link)
  7. ^ Simon E.B.Thierry; Pascal Schreck; Dominique Michelucci; Christoph Fünfzig; Jean-David Génevaux. Extensions of the witness method to characterize under-, over- and well-constrained geometric constraint systems.
  8. ^ Pascal Mathis; Simon E. B. Thierry. A formalization of geometric constraint systems and their decomposition.
  9. ^ Christoph M.Hoffman; Andrew Lomonosov; Meera Sitharam. Decomposition Plans for Geometric Constraint Systems, Part I: Performance Measures for CAD.
  10. ^ Christoph M.Hoffman; Andrew Lomonosov; Meera Sitharam. Decomposition Plans for Geometric Constraint Problems, Part II: New Algorithms.
  11. ^ Marta Hidalgoa; Robert Joan-Arinyo. h-graphs: A new representation for tree decompositions of graphs.
  12. ^ Xiao-Shan Gao; Qiang Lin; Gui-Fang Zhang. A C-tree decomposition algorithm for 2D and 3D geometric constraint solving.
  13. ^ Samy Ait-Aoudia; Sebti Foufou. A 2D geometric constraint solver using a graph reduction method.
  14. ^ Hichem Barki; Lincong Fang; Dominique Michelucci; Sebti Foufou. Re-parameterization reduces irreducible geometric constraint systems.
  15. ^ R.Joan-Arinyo; M.Tarrés-Puertas; S.Vila-Marta. Decomposition of geometric constraint graphs based on computing fundamental circuits. Correctness and complexity.
  16. ^ Kirk Haller; Audrey Lee-St.John; Meera Sitharam; Ileana Streinu; Neil White. Body-and-cad geometric constraint systems.
  17. ^ Dominique Michelucci; Sebti Foufou. Geometric constraint solving: The witness configuration method.
  18. ^ Kramer, Glenn A. (1992). Solving geometric constraint systems : a case study in kinematics (1:a upplagan. ed.). Cambridge, Mass.: MIT Press. ISBN 9780262111645.
  19. ^ Xiaobo Peng; Kunwoo Lee; Liping Chen. A geometric constraint solver for 3-D assembly modeling.
  20. ^ Xiao-Shan Gao; Shang-Ching Chou. Solving Geometric Constraint Systems II. A Symbolic Approach and Decision of Rc-constructibility (PDF).
  21. ^ a b c William Bouma; Ioannis Fudos; Christoph M. Hoffmann; Jiazhen Cai; Robert Paige (1993). A Geometric Constraint Solver.
  22. ^ Michela Farenzena; Andrea Fusiello. Stabilizing 3D modeling with geometric constraints propagation.
  23. ^ R. Joan-Arinyo; M.V. Luzón; A. Soto. Constructive Geometric Constraint Solving: A New Application of Genetic Algorithms.
  24. ^ "Geometric constraint solver".
  25. ^ Rémi Imbach; Pascal Schreck; Pascal Mathis (2014). Leading a continuation method by geometry for solving geometric constraints.
  26. ^ Dmitry Ushakov (2008). Variational Direct Modeling: How to Keep Design Intent in History-Free CAD (PDF).
  27. ^ "D-Cubed Customers".
  28. ^ "Cimatron to Introduce New Motion Simulator Powered by LEDAS LGS 3D".
  29. ^ "Exclusive Q&A: What it means, now that Bricsys bought IP from Ledas".
  30. ^ "C3D Toolkit".
Retrieved from "https://en.wikipedia.org/w/index.php?title=Geometric_constraint_solving&oldid=817401872"