HOME

TheInfoList



OR:

Geometric constraint solving is
constraint satisfaction In artificial intelligence and operations research, constraint satisfaction is the process of finding a solution through a set of constraints that impose conditions that the variables must satisfy. A solution is therefore an assignment of value ...
in a computational geometry setting, which has primary applications in
computer aided design Computer-aided design (CAD) is the use of computers (or ) to aid in the creation, modification, analysis, or optimization of a design. This software is used to increase the productivity of the designer, improve the quality of design, improve c ...
. A problem to be solved consists of a given set of geometric elements and a description of geometric
constraints Constraint may refer to: * Constraint (computer-aided design), a demarcation of geometrical characteristics between two or more entities or solid modeling bodies * Constraint (mathematics), a condition of an optimization problem that the solution m ...
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, 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. 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, detection of over- and under-constrained sets and subsets, 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: decomposition-recombination planning algorithms, tree decomposition, C-tree decomposition, graph reduction, re-parametrization and reduction, computing fundamental circuits, body-and-cad structure, or the witness configuration method. Some other methods and approaches include the degrees of freedom analysis, symbolic computations, rule-based computations, constraint programming and constraint propagation, and genetic algorithms. 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.


Applications

Geometric constraint solving has applications in a wide variety of fields, such as computer aided design, mechanical engineering,
inverse kinematics In computer animation and robotics, inverse kinematics is the mathematical process of calculating the variable joint parameters needed to place the end of a kinematic chain, such as a robot manipulator or animation character's skeleton, in a g ...
and
robotics Robotics is the interdisciplinary study and practice of the design, construction, operation, and use of robots. Within mechanical engineering, robotics is the design and construction of the physical structures of robots, while in computer s ...
, architecture and construction, molecular chemistry, 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.


Software implementations

The list of geometric constraint solvers includes at least * DCM (Dimensional Constraint Manager), a commercial solver from D-Cubed (subsidiary of
Siemens PLM Software Siemens Digital Industries Software (formerly UGS and then Siemens PLM Software) is an American computer software company specializing in 3D & 2D Product Lifecycle Management (PLM) software. The company is a business unit of Siemens, operates ...
), integrated in
AutoCAD AutoCAD is a 2D and 3D computer-aided design (CAD) software application developed by Autodesk. It was first released in December 1982 for the CP/M and IBM PC platforms as a desktop app running on microcomputers with internal graphics control ...
,
SolidWorks SolidWorks (stylized as SOLIDWORKS) is a brand of software used for solid modeling computer-aided design (CAD) and computer-aided engineering (CAE). It was one of the first 3D CAD applications designed to run on a desktop PC. The brand is owned ...
, Creo, and many other popular CAD systems; * LGS, a commercial solver developed by LEDAS and currently owned by Bricsys, integrated in Cimatron E and BricsCAD; * C3D Solver, a commercially available solver which is a part of
C3D Toolkit C3D Toolkit is a proprietary cross-platform geometric modeling kit software developed by Russian C3D Labs (previously part of ASCON Group). It's written in C++ . It can be licensed by other companies for use in their 3D computer graphics soft ...
, integrated into KOMPAS-3D; * GeoSolver, a
GNU General Public License The GNU General Public Licenses (GNU GPL or simply GPL) are a series of widely used free software licenses, or ''copyleft'' licenses, that guarantee end users the freedom to run, study, share, or modify the software. The GPL was the first ...
Python Python may refer to: Snakes * Pythonidae, a family of nonvenomous snakes found in Africa, Asia, and Australia ** ''Python'' (genus), a genus of Pythonidae found in Africa and Asia * Python (mythology), a mythical serpent Computing * Python (prog ...
package for geometric constraint solving. *
SolveSpace SolveSpace is a Free and open-source software, free and open-source 2D/3D computer graphics, 3D Constraint (computer-aided design), constraint-based Parametric design, parametric computer-aided design (CAD) software that supports basic Sketch-bas ...
, open-source CAD that ships with its own integrated geometric constraint solver


See also

*
Geometric modeling kernel A geometric modeling kernel is a solid modeling software component used in computer-aided design (CAD) packages. Available modelling kernels include: *ACIS is developed and licensed by Spatial Corporation of Dassault Systèmes. *SMLib is develope ...


References

{{Reflist Constraint programming