5 ms·

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 tang

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.

kasbah 8y ago
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. [1]: https://github.com/monostable/footwork https://github.com/monostable/footwork [2]: http://fpmagic.engineerjs.com/ http://fpmagic.engineerjs.com/ [3]: https://forum.kicad.info/t/import-create-footprint-dxf/11818/ https://forum.kicad.info/t/import-create-footprint-dxf/11818...
- henrikeh 8y ago
  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.
  - sleavey 8y ago
    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. [1] http://solvespace.com/forum.pl?action=viewthread&parent=2425&tt=1536736305 http://solvespace.com/forum.pl?action=viewthread&parent=2425...
sleavey 8y ago
> geometric constraint solving 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. [1] https://github.com/SeanDS/optivis https://github.com/SeanDS/optivis [2] https://en.wikipedia.org/wiki/Mach%E2%80%93Zehnder_interferometer https://en.wikipedia.org/wiki/Mach%E2%80%93Zehnder_interfero... [3] https://github.com/SeanDS/pygeosolve https://github.com/SeanDS/pygeosolve [4] https://www.sciencedirect.com/science/article/pii/S0010448509000694 https://www.sciencedirect.com/science/article/pii/S001044850... [5] http://geosolver.sourceforge.net/ http://geosolver.sourceforge.net/ [6] https://github.com/SeanDS/cluster/tree/feature/import-new https://github.com/SeanDS/cluster/tree/feature/import-new [7] http://solvespace.com/ http://solvespace.com/ [8] https://github.com/KmolYuan/python-solvespace https://github.com/KmolYuan/python-solvespace
pwnna 8y ago
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).

kasbah 8y ago

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. [1]: https://github.com/monostable/footwork https://github.com/monostable/footwork [2]: http://fpmagic.engineerjs.com/ http://fpmagic.engineerjs.com/ [3]: https://forum.kicad.info/t/import-create-footprint-dxf/11818/ https://forum.kicad.info/t/import-create-footprint-dxf/11818...

henrikeh 8y ago
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.
- sleavey 8y ago
  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. [1] http://solvespace.com/forum.pl?action=viewthread&parent=2425&tt=1536736305 http://solvespace.com/forum.pl?action=viewthread&parent=2425...

sleavey 8y ago

> geometric constraint solving 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. [1] https://github.com/SeanDS/optivis https://github.com/SeanDS/optivis [2] https://en.wikipedia.org/wiki/Mach%E2%80%93Zehnder_interferometer https://en.wikipedia.org/wiki/Mach%E2%80%93Zehnder_interfero... [3] https://github.com/SeanDS/pygeosolve https://github.com/SeanDS/pygeosolve [4] https://www.sciencedirect.com/science/article/pii/S0010448509000694 https://www.sciencedirect.com/science/article/pii/S001044850... [5] http://geosolver.sourceforge.net/ http://geosolver.sourceforge.net/ [6] https://github.com/SeanDS/cluster/tree/feature/import-new https://github.com/SeanDS/cluster/tree/feature/import-new [7] http://solvespace.com/ http://solvespace.com/ [8] https://github.com/KmolYuan/python-solvespace https://github.com/KmolYuan/python-solvespace

pwnna 8y ago

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).