9 ms·

Constraint Solver (2015)

109 points by kasbah 8y ago

speps 8y ago
Please add (2015). Also check out Matt's CAD project: https://libfive.com/ https://libfive.com/
- mayoff 8y ago
  Wow. Any user of OpenSCAD should check out libfive Studio. It looks amazing.
  - blt 8y ago
    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. [1] https://github.com/libfive/libfive/blob/master/libfive/include/libfive/solve/solver.hpp https://github.com/libfive/libfive/blob/master/libfive/inclu...
    - pwnna 8y ago
      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.
      - blt 8y ago
        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.
        sjm-yc-acct 8y ago
        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.
        blt 8y ago
        You are probably right. I realize my previous post sounded pessimistic but I was only trying to state my ignorance :)
  - sjm-yc-acct 8y ago
    Matt Keeter's Libfive is a very promising project. Our company has written a Common Lisp binding: https://common-lisp.net/project/tovero/ https://common-lisp.net/project/tovero/ and it would be useful to have a constraint solver. We are looking at ways of applying Libfive to mechanical design. I have also developed a prototype of a Libfive viewer--written in Guile Scheme for use with a REPL/Emacs: https://github.com/sjm-tl-gh/inspekt3d https://github.com/sjm-tl-gh/inspekt3d Coding 3D models in Lisp has been an amazing experience (even without a constraint solver). Libfive also has a FFI-friendly C API, so other language bindings (e.g. Python) are very feasible. One feature Libfive is currently missing is a general sweep of a shape along a curve--which seems to not be so straight forward with F-rep modeling.
henrikeh 8y ago
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...
amelius 8y ago
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).
c-smile 8y ago
Hmm, this looks like Cassowary solver that was first used in 1940 as stated here: https://cassowary.readthedocs.io/en/latest/topics/theory.html https://cassowary.readthedocs.io/en/latest/topics/theory.htm... 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.
- mayoff 8y ago
  Simplex solves only linear systems, and finds a global optimum. Cassowary is an incremental version of simplex—it lets you efficiently add, remove, and modify constraints. Gradient descent works for non-linear systems, but isn't guaranteed to find the global optimum.
  - jpfr 8y ago
    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. See here for further reference: http://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf http://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf

109 points by kasbah 8y ago

speps 8y ago

Please add (2015). Also check out Matt's CAD project: https://libfive.com/ https://libfive.com/

mayoff 8y ago
Wow. Any user of OpenSCAD should check out libfive Studio. It looks amazing.
- blt 8y ago
  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. [1] https://github.com/libfive/libfive/blob/master/libfive/include/libfive/solve/solver.hpp https://github.com/libfive/libfive/blob/master/libfive/inclu...
  - pwnna 8y ago
    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.
    - blt 8y ago
      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.
      - sjm-yc-acct 8y ago
        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.
        blt 8y ago
        You are probably right. I realize my previous post sounded pessimistic but I was only trying to state my ignorance :)
- sjm-yc-acct 8y ago
  Matt Keeter's Libfive is a very promising project. Our company has written a Common Lisp binding: https://common-lisp.net/project/tovero/ https://common-lisp.net/project/tovero/ and it would be useful to have a constraint solver. We are looking at ways of applying Libfive to mechanical design. I have also developed a prototype of a Libfive viewer--written in Guile Scheme for use with a REPL/Emacs: https://github.com/sjm-tl-gh/inspekt3d https://github.com/sjm-tl-gh/inspekt3d Coding 3D models in Lisp has been an amazing experience (even without a constraint solver). Libfive also has a FFI-friendly C API, so other language bindings (e.g. Python) are very feasible. One feature Libfive is currently missing is a general sweep of a shape along a curve--which seems to not be so straight forward with F-rep modeling.

henrikeh 8y ago

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

amelius 8y ago

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

c-smile 8y ago

Hmm, this looks like Cassowary solver that was first used in 1940 as stated here: https://cassowary.readthedocs.io/en/latest/topics/theory.html https://cassowary.readthedocs.io/en/latest/topics/theory.htm... 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.

mayoff 8y ago
Simplex solves only linear systems, and finds a global optimum. Cassowary is an incremental version of simplex—it lets you efficiently add, remove, and modify constraints. Gradient descent works for non-linear systems, but isn't guaranteed to find the global optimum.
- jpfr 8y ago
  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. See here for further reference: http://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf http://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf