Skip to Content
Choose a Siemens Country/Region
There is significant literature on the algorithms of geometric constraint solvers. However, much of it applies to algorithms and systems that are not in wide-spread commercial use in the CAD and related markets.
The D-Cubed 2D DCM and 3D DCM geometric constraint solvers are used in more commercial CAD products by more end-users than any other such solvers by quite some margin. Hence, there is significant interest in their algorithms. However, for reasons of commercial confidentiality the DCM algorithms are largely unpublished. Nevertheless, some important information has been published by John Owen, in some cases working with his academic collaborators.
John Owen founded D-Cubed Limited in 1989, having the role of managing director until its sale to UGS (now Siemens PLM Software) in 2004. He is a key contributor to the innovative core algorithms in the 2D DCM and 3D DCM. John is still with the team he started to set-up back in 1989.
Though mostly not directly relevant to commercial geometric constraint solving issues, for the mathematically-minded the following publications provide interesting insights into some of the wider and more fundamental mathematical issues in this field. They also illustrate some of the overlaps with fields beyond commercial CAD systems. Please note that access to some of the publications requires a subscription with the respective publisher, or a fee payable to the publisher:
J.C. Owen, pages 397-407 of the Symposium on Solid Modelling Foundations and CAD/CAM Applications", 1991, sponsored by ACM SIGGRAPH, Austin, Texas.
Of these academic references, this is arguably the most wide-ranging, most accessible and most significant for understanding some of the core geometric constraint solving issues in the D-Cubed DCM products. This paper describes some basic graph decompositions and indicates that (for points in 2D) these decompositions are sufficient to solve constraint systems which are generically solvable with ruler and compass constructions.
J.C. Owen, International Journal of Computational Geometry and Applications, pages 421-434, Volume 6, Number 4, 1996.
Another relatively accessible and relevant paper for core geometric constraint solving issues in a CAD context. This paper extends the ideas of the preceding paper to include more geometric elements such as lines and circles.
J.C. Owen and S.C. Power, arXiv.org, 2005
Unpublished conference proceedings which describes the mathematical methods used to prove the completeness of the graph decomposition method.
J.C. Owen and S.C. Power, Transactions of the American Mathematical Society, Volume 359 (5). pp. 2269-2303, 2007.
This paper gives a formal proof for the completeness of the graph decomposition methods described in the preceding references when applied to planar graphs.
J.C. Owen and S.C. Power, Bulletin of the London Mathematical Society, Volume 41, Issue 6, pp. 1105-1111, 2009.
This paper extends a classical theorem of Kempe (that there is a finite mechanism which traces out any algebraic curve) to show that there is a bounded infinite mechanism which traces out any continuous curve, including space-filling curves. This indicates that as geometric constraint systems become large they may exhibit increasingly exotic behaviours.
J.C. Owen and S.C. Power, International Journal of Computational Geometry and Applications, pages 723-750, Volume 20, Number 6, 2010.
Symmetries play a key role in determining the singular (non-regular) points for geometric constraint equations. This paper uses techniques recently developed in the theory of rigid structures to predict singular points in geometric constraint equations.
J.C. Owen and S.C. Power, 2010
This paper investigates the properties of infinitely large systems of geometric constraint equations! The results are however relevant to the properties of physical materials such as zeolites.
A. Nixon, J.C. Owen and S.C. Power, arXiv.org, 2010
This paper investigates the properties of geometric constraint equations where the geometric elements (points) are constrained to lie on an engineering surface such as a sphere, cylinder, cone or torus.
B. Jackson and J.C. Owen, arXiv.org, 2012
Most systems of geometries, dimensions and constraints have multiple solutions. For example, a point dimensioned to be a distance from two other fixed points often has two possible locations. Such systems of geometries, dimensions and constraints, (and other similar systems that arise in different contexts), can be represented by a graph. This paper shows how the analysis of certain types of such graphs can determine key information regarding the number and nature of the potential solutions.
B. Jackson and J.C. Owen, arXiv.org, 2012
Configurations of geometries positioned by dimensions and constraints require the solution of a system of polynomial equations. A 2D framework is a simple example in which points on a plane are specified by relative distance dimensions. If the distances have generic values the framework is uniquely described by a graph. The graph is radically solvable if positions for the points can be determined by sequentially taking roots of the dimension values. This paper gives a sufficient condition for any rigid, generic 2D framework to be radically solvable and conjectures that this condition is also necessary.
Share this page through any of the following channels.