Geometric constraint solving

Geometric constraint solving is constraint satisfaction in a computational geometry setting, which has 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 first 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 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 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

• DCM (Dimensional Constraint Manager),^[27] a commercial solver from D-Cubed (subsidiary of Siemens PLM Software), integrated in AutoCAD, SolidWorks, Creo, and many other popular CAD systems;^[28]
• LGS,^[29] a commercial solver developed by LEDAS and currently owned by Bricsys, integrated in Cimatron E and BricsCAD;^[30][31]
• C3D Solver,^[32] a commercially available solver which is a part of C3D Toolkit, integrated into KOMPAS-3D;^[33]
• GeoSolver,^[34] a GNU General Public License Python package for geometric constraint solving.
• SolveSpace, open-source CAD that ships with its own integrated geometric constraint solver

See also

• Geometric modeling kernel