Jump to content

Geometric constraint solving

From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by Ilya.lichman (talk | contribs) at 11:20, 2 November 2017 (Added a source "Algebraic solution for geometry from dimensional constraints" and an application "C3D solver"). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.


Geometric constraint solving is constraint satisfaction in a computational geometry, which has a primary applications in computer aided design.[1] The 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 positions of the geometric elements in 2D or 3D space which satisfy the given constraints,[2] 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.[3][4]

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,[5] detection of over- and under-constrained sets and subsets,[6][7] 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 techniques could be used in order to decrease the size of system of equations to be solved:[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] witness configuration method.[17]

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

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.[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. ^ Geometric Constraint Solving and Applications.
  2. ^ Geometric constraint solving in R2 and R3 (PDF).
  3. ^ Robert Joan-Arinyo. Basics on Geometric Constraint Solving.
  4. ^ Modelling with constraints: theoretical foundation and application.
  5. ^ 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. ^ Extensions of the witness method to characterize under-, over- and well-constrained geometric constraint systems.
  8. ^ A formalization of geometric constraint systems and their decomposition.
  9. ^ Decomposition Plans for Geometric Constraint Systems, Part I: Performance Measures for CAD.
  10. ^ Decomposition Plans for Geometric Constraint Problems, Part II: New Algorithms.
  11. ^ h-graphs: A new representation for tree decompositions of graphs.
  12. ^ A C-tree decomposition algorithm for 2D and 3D geometric constraint solving.
  13. ^ A 2D geometric constraint solver using a graph reduction method.
  14. ^ Re-parameterization reduces irreducible geometric constraint systems.
  15. ^ Decomposition of geometric constraint graphs based on computing fundamental circuits. Correctness and complexity.
  16. ^ Body-and-cad geometric constraint systems.
  17. ^ 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. ^ A geometric constraint solver for 3-D assembly modeling.
  20. ^ Solving Geometric Constraint Systems II. A Symbolic Approach and Decision of Rc-constructibility (PDF).
  21. ^ a b c A Geometric Constraint Solver.
  22. ^ Stabilizing 3D modeling with geometric constraints propagation.
  23. ^ Constructive Geometric Constraint Solving: A New Application of Genetic Algorithms.
  24. ^ "Geometric constraint solver".
  25. ^ Leading a continuation method by geometry for solving geometric constraints.
  26. ^ Variational Direct Modeling: How to Keep Design Intent in History-Free CAD (PDF). 2008.
  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=808355434"