I guess you can randomly adjust points, check the constraints and iterate, but that sounds inefficient.
> If the sketch is not fully constrained, then the Jacobian is solved in a least squares sense, with each equation written in such a way as to make the quantity being minimized a useful penalty metric. This tends to yield "less surprising" results when dragging points in an underconstrained sketch, compared to approaches that use weak dimensions to keep the sketch always fully constrained.
https://solvespace.com/tech.pl
Not sure what the Big Players (Autodesk, Dassault Systemes, Siemens, ...) use, though.
In Autodesk Fusion 360, they seem to use something similar but with weird discontinuities in the computation. You'll be smoothly moving a point or edge or something and then at some point the 1px movement causes everything to snap differently and confusingly :). And if you pull back in the direction you came from, it doesn't go back the way it was. At least Ctrl-Z generally works pretty well :D
It occurred to me after I posted that this is similar in a way to molecular dynamics simulations, which are essentially constrained sets of points (constraints like atoms have to be within a certain distance range or angle/torsion).
In those you use techniques like gradient descent (similar to Newton's method it seems) and forcefields and so on. I guess it's all numerical optimization in the end.
https://www.plm.automation.siemens.com/global/en/products/pl...
Siemens PLM - NX and SolidEdge
Dassault - CATIA & SolidWorks
Autodesk - Inventor & Fusion
PTC - not sure ProEngineer's original sketcher predates 2D DCM of course because they invented history-based feature modeling for 3D CAD.
OnShape also.
Russian systems tend to use LEDAS
https://levindavid.blogspot.com/2011/10/providing-geometric-...
2D DCM is now owned and sold by Siemens PLM but originally created by John Owen at D-Cubed Ltd (Cambridge UK) from circa 1989 before he sold the company to Siemens in 2004
https://www.plm.automation.siemens.com/global/en/our-story/n...
Original 2D DCM paper by John Owen from 1991
Algebraic Solution for Geometry from Dimensional. Constraints
http://papers.cumincad.org/data/works/att/9ad2.content.pdf
(The split the graph into biconnected components doesn't really cover variable radius circles though.)
Other more recent papers by John Owen on arXiv
https://arxiv.org/search/math?searchtype=author&query=Owen%2...
(Some of these are for 3D DCM.)
Disclaimer: D-Cubed Ltd employee from 1995-2000.
As for splitting the graph into biconnected component, that mirrors what I know about automated layout of graphs (essentially the same problem?) in that it makes sense to have a very high-level algorithm of:
1) split graph into bi- (or tri-) connected components 2) layout these components individually 3) layout the block-tree of components
With the goal for layout to make it 'look nice' in some sense, while the goal for CAD is more that the constraints should ... make the final structure buildable and the 'right' shape?
The original author of solvespace said the same thing. He set out to make a constraint solver that behaved more intuitively than the commercial ones he'd used. He still licenses the solver for commercial use.
Sounds like a big Achilles heel to civilization in some ways.. :D
I mean, even with search engines, there is more competition..
https://en.m.wikipedia.org/wiki/Parasolid
https://en.m.wikipedia.org/wiki/ACIS
Even Autodesk use a fork of an old version of ACIS they own:
Am I the only one to find it crazy that basically all of engineering is using the same proprietary constraint solver that only one company knows how to build?
Perhaps, but it’s a surprisingly complicated problem and at the same time a highly specialised one. Having the big players in the CAD world, who all need to solve much the same problem here, essentially funding a small group of specialists enough to work on it might just be economic incentives doing their job.
I have no insider knowledge about this, but given that D-Cubed was first bought by UGS (a customer, and a direct competitor of many of its other customers) prior to becoming part of Siemens, I expect the lawyers all had provisions in place to deal with any dependency concerns.
It probably also becomes clear now why Russian systems use a different product.. :D
> 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]
He based this on the principles in the Solvespace constraint solver which is used in the blender add-on.
See https://vimeo.com/454404808 at the 9:25 and at the 28:36 timestamps.