A particular flavor of constraint solving is geometric constraint solving, where constraints such as "this line is parallel to this line" and "this line is tangent to this curve". This is widely used in pretty much everything single mechanical CAD tool worth its salt.
But you know what it is missing from: electrical CAD tools.
For footprints this would be especially useful. Some think that footprints are just one size fits all, but that is far from the truth. Footprints should vary depending on the environment, production tolerances, manufacturing method. Right now I have several varieties of the same footprint for different deratings and uses -- what if I could simply specify a parametric footprint which actually adapted to specifications made in the design process.
This could be done with wizard programs (several commercial options exists), but I think an approach based upon geometric constraint solvers and parametric drawings is a far, far more user-friendly and powerful approach. The widespread usage in mechanical CAD tools prove that this is not a far-fetched application; it simply hasn't taken a foothold within electrical CAD tools.
I've been toying with the ideas and researching how it could be done for quite a while, but I haven't made much code-wise progress yet. However, there is a lot of tools to draw upon (libraries for geometric constraint solving exists). If someone is interested in co-developing on some ideas, or already knows of such a project, then I'd love to hear about it (email is in profile) -- I'm getting tired of manually calculating grid sizes and offsets.
I'd be interested in looking at co-developing something. I have been kicking around ideas about using constraint programmning for electronics CAD in my head for quite a while which is why I found this blog post so fascinating.
I began developing something I called Footwork [1] where you could write KiCad footprints in Racket, with the end goal of hooking this up to the Rosette constraint programming DSL, but I didn't get very far with it.
I know there are some experiments like fpmagic [2] and people drawing KiCad footprints in Freecad [3] (which I assume lets you draw using constraints). Like you said, there are proprietary commercial solutions as well but I rarely find the time to assess them.
After reading this blog post and looking at the author's libfive, I thought I would play around with that and see if I could start a solution using it. I'd be interested to hear what your own approach to this would be though.
fpmagic looks quite interesting -- very barebones, but at least its a start!
Footwork too looks like a neat project and I especially think the closer connection between code and interaction is beneficial. It is the same thing which impresses me about libfive and the whole stack around it: it is not just a GUI, not just a scripting language, not just an API -- it is all at once!
From my research into available libraries for geometric constraint solving the best choice is probably SolveSpace. It is actively developed and fast. However, I haven't yet put action behind my thoughts and I'm willing to try things out and make some progress.
Unfortunately there's not a great deal of publicly available examples of SolveSpace being used as a library. I almost immediately ran into a problem when I recently tried to have it solve a simple triangle system [1]. I'm probably doing something stupid, but like I say there's hardly anything to look at as a reference.
Uh oh, that's my trigger word! I've been grappling with this problem recently and have a lot to say on the matter. I've been trying to build a simple geometric constraint solver for laying out 2D diagrams of optics in laser systems. The idea is not to be optically rigorous (for which CAD tools already exist, like Zemax), but to lay things out in a nice way for publications, such that lengths and angles can be constrained programmatically. This stems from when I was writing my PhD thesis and had to edit some 2D optical diagrams. By changing the angle of one mirror, I had to then move a whole bunch of other optics around to keep the incidence angle equal to the reflected angle.
I eventually wrote Optivis [1], which was my first attempt at solving the optical layout problem, but I quickly realised that my simple algorithm didn't work for cyclicly connected optics, i.e. optics connected back to themselves in some way. This is the case for any triangular cavity, or e.g. a Mach-Zehnder interferometer [2]. The problem is that by simply defining length and angle constraints between lines and optics, you overconstrain the problem when you connect something back to itself: you are setting an angle or length which is already implicitly defined by all the other (constrained) angles and lengths. To properly solve such problems, you must use a geometric constraint solver - one which can tell whether the problem is under-, well-, or over-constrained.
With a little research, I found that the traditional CAD approach to solving this type of problem is to write a bunch of non-linear equations representing the lengths and angles, and then use a minimiser to solve it based on some cost function. I wrote a simple library to do this [3], but I found that the problem had to be drawn with an initial guess close to its final solution in order for the solver to converge on the solution. Ideally, I wanted to be able to programmatically draw an optical layout based solely on a set of length and angle definitions from a file, rather than a prototype drawn e.g. by the user.
I found an academic paper [4] which described a wonderful approach to solving such a problem. It is based on the idea of "cluster rewriting" instead of solving non-linear equations. This approach represents constraints as "clusters", or sets of points, and the relations between them. The algorithm in the paper supports three types of cluster innately: "rigid" clusters, which are points with fixed positions with respect to each other; "radial" clusters, where a set of points are defined to have some fixed length from a central, rigid point; and "scalable" clusters, which are points whose vertices have well defined angles but no defined lengths. The algorithm identifies groups of points that fall into these definitions, and tries to merge them together until there is only one rigid cluster left. Or, in other words, it starts out with the initial set of constraints defined by the user, then derives a whole bunch of implicit constraints on the other points that are consistent with the initial constraints, provided that the problem is well constrained. What's awesome about this paper is that the authors provide a Python library [5]. It was written between about 2009 and 2013 for use with Python 2.5, so I spent a few weeks over summer porting it to Python 3 [6]. I managed to get it to work, and it was managing to solve fairly complicated problems, but I found that it had a few latent bugs which I could not fix easily without really taking time to understand the full algorithm. For example, when adding a new constraint to a relatively simple set of points, it would spontaneously move everything back to the origin. I think I somewhat understand which part of the code is causing this, but I don't understand it well enough to really fix it.
That's where I left the problem. Recently I have again been looking at constraint solving using non-linear solvers, particularly with SolveSpace [7], because its (C++ based) library was recently exposed via Python [8], but this will again be susceptible to the problem that the user must provide a close-to-optimal prototype for the system to converge. I am disappointed I couldn't get the paper's algorithm to work fully, because it is an excellent approach to this problem. Perhaps someone here has some more experience in this domain and can help?
I also plan to use whatever I come up with to draw electrical diagrams around optics. In my field we frequently draw diagrams of optical layouts with the electrical signals included. For electrical problems you would probably be more interested in having "neat" signals with 90 degree angles, and parallel lines, but this would probably be quite straightforward to implement.
Interestingly I am myself doing a Ph.d. in photonics engineering, but I am almost entirely in signal processing and information theory.
Anyway, thanks for the links and the thoughts! Amusingly almost all of the links were already visited! I've looked several times at your library for geometric constraint solving in Python and almost thought about using it for my own projects. In the end however I think SolveSpace is the best choice -- it is solid, actively developed and fast.
Your ambition of having the drawings be singularly specified by their constraints is absolutely admirable, but from my experience it is simple not feasible nor desirable. First, the optimization problem is difficult to solve and it will be difficult to specify it such that there is only one unique solution. Secondly, I think the human provided prototype (through a GUI) is a critical part of the design process which makes this technology usable. But I understand the desire to have drawings specified only by constraints.
In the long term, if I am allowed to dream, I'd like to see the development of a more general purpose constraint-based and parametric drawing library. Right now I am focused on PCB footprints, but many of same ideas are useful in electrical diagrams, optical diagrams, GUIs, page layout etc etc. We'll see how far I get ;)
Nice to see my work is not completely unnoticed, but, you are right to take it with a grain of salt as I don't actively maintain any of the stuff I linked!
The paper I previously linked discusses the problem of "solution selection" as you state: the problem of selecting from systems with multiple solutions (for example, when one specific side of a triangle is constrained onto another line, it can do so in one of two directions or "orientations" as the paper refers to them). The paper presents two strategies for selecting solutions: a selection heuristic approach, whereby the user defines that they want a certain class of cluster such as one with clockwise angles; and a prototype-based selection method where the solution which most closely resembles the user's sketch is selected. I prefer the latter approach, but that's unfortunately the one that is buggy in the library I found.
I completely agree about how awesome it would be to have a parametric drawing library. That's actually what my overall goal was to be, eventually, once I got the optical layout problem solved - there's nothing really to stop such a library from being generalised to any kind of drawing. I was surprised that I couldn't find one already, to be honest, as it would no doubt be really useful in untold applications.
If you manage to get something working, please let me know :-)
Multi-start optimization is the simplest way to deal with the initial guess problem. Is there any heuristic you can use to generate a reasonably-sized set of guesses that is likely to contain at least one guess contained in the region of convergence of the global optimum?
An example of such a heuristic: when fitting a Gaussian mixture model using the E-M algorithm, you can perform K-means clustering with several sets of uniformly sampled random initial cluster centers; then use those cluster centers with the K-means hard correspondence to compute the initial fit of the Gaussians.
There are some cool global minimisation algorithms which can handle certain types of problem where the initial guess is far away. Some involve switching between different algorithms until the cost function is close to its minimum. I did try the ones available in SciPy when I built a non-linear equation based constraint solver, but none really worked well enough. However, I know such algorithms exist if I put the time in to learn about them. Since I discovered cluster-rewriting based constraint solvers, I've been spending most of my time investigating those.
I'm actually not against the idea of asking the user to provide a sketch, I'm just trying to solve the harder problem first and if I can't do so then I'll introduce some constraints (pun not intended).
I don't know anything about the problem domain but I'm guessing that you need to make some topological as well as geometric choices... In which case the evolutionary algorithms could be interesting
To add to this, another one that seems to be missing is a software CAD tool, where certain simple algorithms that you have to write can be automated based on some constraints (which itself can be turned then be into tests/proofs).
This is really cool but it looks like the constraint solver [1] is not much more complex than the one shown in this web page. I really want a program-driven functional CAD tool like libfive or OpenSCAD, but with powerful 3d constraint solving like, e.g. Solidworks can provide.
I've always wanted this as well but I haven't gotten the time to actually look into writing this. This would solve a lot of complaints I have and have heard about traditional CAD software, as they tend to constrain you with their very complex GUI.
It might not be that difficult to implement a high level DSL around one of the geometric modeling kernels like Parasolid, ACIS, etc. that form the computational core of GUI CAD programs. But I don't know if any equally powerful CAD kernels exist in the open source world.
FreeCAD uses Open CASCADE, which is is a free software (LGPL) CAD kernel. Open CASCADE has a comprehensive modeling API which uses B-rep. For scripting, FreeCAD has a Python interface. CadQuery is another Python tool (DSL) which is a plug-in for FreeCAD. FreeCAD itself already has some constraint functionality.
Libfive is layered and can be used without Studio to generate models with its extensible Guile Scheme binding. It uses F-rep modeling.
Correct me if I'm wrong, but it should be possible today to add a programmatic (non-GUI) constraint solver to either FreeCAD or Libfive.
The only difference is that it is using Simplex method instead of gradient descent (as in article). Simplex and GD are slightly different methods of finding local minimums in systems of linear equations.
There is a huge class of non-linear problems where gradient descent (with line search) is guaranteed to find the global optimum: Convex optimization problems.
And within convex problems there is a hierarchy of "difficulty": LP ⊂ QP ⊂ SOCP ⊂ SDP
The Simplex algorithm solves only LP. And it was shown that the Simplex has an exponential worst-case runtime (in the number of constraints). Whereas interior-point methods (basically variations of Gradient Descent) have a much better worst-case runtime.
Isn't there an incremental way to solve this? Seems a bit wasteful to recompute everything from scratch for every tiny change in constraints (in the example for every movement of the mouse).
But you know what it is missing from: electrical CAD tools.
For footprints this would be especially useful. Some think that footprints are just one size fits all, but that is far from the truth. Footprints should vary depending on the environment, production tolerances, manufacturing method. Right now I have several varieties of the same footprint for different deratings and uses -- what if I could simply specify a parametric footprint which actually adapted to specifications made in the design process.
This could be done with wizard programs (several commercial options exists), but I think an approach based upon geometric constraint solvers and parametric drawings is a far, far more user-friendly and powerful approach. The widespread usage in mechanical CAD tools prove that this is not a far-fetched application; it simply hasn't taken a foothold within electrical CAD tools.
I've been toying with the ideas and researching how it could be done for quite a while, but I haven't made much code-wise progress yet. However, there is a lot of tools to draw upon (libraries for geometric constraint solving exists). If someone is interested in co-developing on some ideas, or already knows of such a project, then I'd love to hear about it (email is in profile) -- I'm getting tired of manually calculating grid sizes and offsets.