4 ms·

Author of ImplicitCAD here. I completely agree. At first, I tried to implement constraints in a Haskell DSL. Unfortunately, constraints usually only partially

by colah3 12y ago

Author of ImplicitCAD here. I completely agree. At first, I tried to implement constraints in a Haskell DSL. Unfortunately, constraints usually only partially describe your object. Even a well-constrained object can be flipped and maintain the constraints, in most systems. I coudln't find a reasonable way to implement a text-based interface for this. It really needs to be graphical. I abandoned ImplicitCAD to write a constraint-based CAD program with my friend Rob Gilson. (I handled constraint solving with gradient descent, which worked surprisingly well, and a dab of grobner bases here and there.) We got some neat stuff working, but eventually got pulled away to other projects. I think there's a lot of interesting work to be done linking programmatic and graphical CAD. In particular, I think there's neat connections between constraint based CAD which is a form of visual logic programming, and functional programming. (Aside: I like Bret Victor's talk "Stop Drawing Dead Fish" which is on a kind of related topic.) Unfortunately, I'm too busy with ML research these days to work on this stuff!

ObviousScience 12y ago
I've had an interest in constraint-based CAD programs (with an interest in designing things for 3D printers), and was wondering if you could recommend any literature on the subject.
- colah3 12y ago
  Sadly, I never did a serious literature review. That said, I naively tried a bunch of naive approaches and had quite a bit of success with plain old gradient descent -- it was really surprising. I'm not sure if it would scale to really significant models, but it's something you could implement in a few hours and you could use to get a project off the ground.
  - colah3 12y ago
    For the algebraic geometry side, though, *Ideals, Varieties and Algorithms" by Cox, Little and O'Shea is great.
toong 12y ago
I think CAD constraints would always be expressed in a linear system. I'm wondering if one could use Cassowary for constraint solving here ? Somehow UI-control-layouting with constraints feels similar to constraints in CAD drawings ? :-) + How does gradient descent work with over-constrainted models ? (as in: impossible to satisfy all constraints). You need some way to back out of those or relax one of the constraints. Ref: http://en.wikipedia.org/wiki/Cassowary_(software) http://en.wikipedia.org/wiki/Cassowary_(software)
- colah3 12y ago
  > I think CAD constraints would always be expressed in a linear system Typically, you want to at least be able to express the lengths of lines, and the values of angles. I don't know how you could do this without using at least quadratic terms. So you have to do at least quadratic programming, and there's some things that can add higher degree terms. Moreover, extremely similar problems are studied in automated geometric theorem proving, and they also get pulled into using polynomials. Unfortunately, these problems are much much harder than linear programming. There's some really powerful tools from algebraic geometry, mainly Grobner Bases, which you would ideally want to use. They're ridiculously powerful. Not only can you use them to solve systems of polynomial equations, but you can also test whether a set of equations implies another polynomial, or conflicts with another polynomial -- super useful for dealing with over-constrained models. Tragically, the relevant algorithm is O(exp(exp(n))) -- well, or at least, that's the best upper bound anyone can probe, in practice it isn't that bad. Still, I quickly ran into computational problems. Grobner bases, also, while great are tricky to work with if you only want real valued solutions. They like to give you complex valued solutions to problems, and complex valued solutions to your CAD constraints are usually not what you are looking for. > How does gradient descent work with over-constrainted models ? (as in: impossible to satisfy all constraints). You need some way to back out of those or relax one of the constraints. In my implementation, each constraint was a separate cost function, which I added together. Normally, when you run the solver, it pushes all the constraint costs to zero, and you know you've solved everything. Sometimes it would get stuck in a local minimum and require user intervention to help it get to the right solution. That was surprisingly rare. If you have conflicting constraints it simply fails to reach a cost of zero at all. You can handle that in your interface however you like. The obvious thing is to try and solve a constraint immediately after adding it and then reject the constraint if you can't. (I really didn't expect a local optimization method like gradient descent to work so well, but it did. That said, if I attacked the problem again I would try to use some sort of second order optimization method, I think.)
auxym 12y ago
As a frequent user of Solidworks for ~4 years, I'd have to guess that CAD constraint solvers are not an easy problem. It happens pretty often that you'll modify a single constraint (flipping it is a common culprit), the solver will get "confused" and flip a bunch of your other constraints around. Constraint conflict resolution also often gets very hairy to almost impossible. Sometimes the fastest thing to do is to nuke a good part of your constraints and start over -- in a saner way. I guess the BIG CAD packages (CATIA, NX) might be a bit better at this, or at least better at strongly encouraging saner ways of build parametric constraints (which is what I've heard). It's too bad that there isn't a simple, intuitive and useful free/oss CAD software out there. With the whole hobbyist maker movement explosion out there, a lot of people would be thrilled to have something like that. Though, it seems that things are not very much better in the PCB CAD/CAM world either.
- colah3 12y ago
  I was really excited about handling some of the messy constraint situations better than existing tools. I'll split this into two pieces: > It happens pretty often that you'll modify a single constraint (flipping it is a common culprit), the solver will get "confused" and flip a bunch of your other constraints around. For "confused" constraint solvers, I see this as largely being a problem of there being lots of solutions to a well constrained system, because of flips and such. It needs to be easy for the user to specify which one they want. Our approach was to have fast pulls of the mouse temporarily over ride the constraint solver. So, if you needed to flip the model, you do a really fast pull and it would flip. This works much better with multi touch, where you can just grab a few points with different fingers and force your model into whatever shape you want. > Constraint conflict resolution also often gets very hairy to almost impossible. There's some really powerful tools from algebraic geometry I tried to apply to this. In particular, there's these things called Grobner Bases which you can use to test if certain polynomials imply that another is true, false, or if it's independent of them. From the users perspective, I wanted to use these to do a few things. (1) Display implied constraints. If you make three corners of a quadrilateral perpendicular, the fourth is forced to be perpendicular. I grayed out perpendicular constraint could alert you to this, and prevent you from adding a conflicting constraint. Obviously, that example is kind of silly, but I think that propagating constraints through the whole model would really help people understand how more complicated models are constrained. (2) If you try to add a constraint which conflicts with preexisting ones, highlight in red a minimal set it conflicts with. I never got this part of the project to work though. I did some very small proof of concepts in sage, but couldn't really get things to work. I'm not really sure how realistic it is to make these work for real models.
pwnna 12y ago
> I think there's a lot of interesting work to be done linking programmatic and graphical CAD. I thought about this as well, but I don't know anyone who works with CAD who would likely switch their work flow from GUI to text-based, other than people in this thread, I suppose. Furthermore, while I don't know about the details on how to implement a text-based 3D modelling language for constraint based modelling, I don't think there's a lot of point if a GUI is going to be attached to it anyway. Existing systems already do a reasonable job. One of the most annoying part of the confused constraint system, for me, is that it is difficult to fix the constraints. Options are likely to be hidden behind layers and layers of menus and dialog. A text file can be easily searched and diffed, which in my mind should make a confused system easier to resolve. So maybe this kind of constraint based CAD should have both a language and a revision control system built into it, or something.
- colah3 12y ago
  > but I don't know anyone who works with CAD who would likely switch their work flow from GUI to text-based, other than people in this thread, I suppose. Programming doesn't have to be writing text. :P Everyone seems to be thinking about APIs to the CAD program, which solidworks, autodesk, and presumably others provide. I had in mind a pretty deep way to embed a lambda calculus into the visual interface. The hope was to make it intuitive to create powerful parametric models, where every sketch is a function of different parameters. We never implemented that part, though. :/

by colah3 12y ago

ObviousScience 12y ago

I've had an interest in constraint-based CAD programs (with an interest in designing things for 3D printers), and was wondering if you could recommend any literature on the subject.

colah3 12y ago
Sadly, I never did a serious literature review. That said, I naively tried a bunch of naive approaches and had quite a bit of success with plain old gradient descent -- it was really surprising. I'm not sure if it would scale to really significant models, but it's something you could implement in a few hours and you could use to get a project off the ground.
- colah3 12y ago
  For the algebraic geometry side, though, *Ideals, Varieties and Algorithms" by Cox, Little and O'Shea is great.

toong 12y ago

I think CAD constraints would always be expressed in a linear system. I'm wondering if one could use Cassowary for constraint solving here ? Somehow UI-control-layouting with constraints feels similar to constraints in CAD drawings ? :-) + How does gradient descent work with over-constrainted models ? (as in: impossible to satisfy all constraints). You need some way to back out of those or relax one of the constraints. Ref: http://en.wikipedia.org/wiki/Cassowary_(software) http://en.wikipedia.org/wiki/Cassowary_(software)

colah3 12y ago
> I think CAD constraints would always be expressed in a linear system Typically, you want to at least be able to express the lengths of lines, and the values of angles. I don't know how you could do this without using at least quadratic terms. So you have to do at least quadratic programming, and there's some things that can add higher degree terms. Moreover, extremely similar problems are studied in automated geometric theorem proving, and they also get pulled into using polynomials. Unfortunately, these problems are much much harder than linear programming. There's some really powerful tools from algebraic geometry, mainly Grobner Bases, which you would ideally want to use. They're ridiculously powerful. Not only can you use them to solve systems of polynomial equations, but you can also test whether a set of equations implies another polynomial, or conflicts with another polynomial -- super useful for dealing with over-constrained models. Tragically, the relevant algorithm is O(exp(exp(n))) -- well, or at least, that's the best upper bound anyone can probe, in practice it isn't that bad. Still, I quickly ran into computational problems. Grobner bases, also, while great are tricky to work with if you only want real valued solutions. They like to give you complex valued solutions to problems, and complex valued solutions to your CAD constraints are usually not what you are looking for. > How does gradient descent work with over-constrainted models ? (as in: impossible to satisfy all constraints). You need some way to back out of those or relax one of the constraints. In my implementation, each constraint was a separate cost function, which I added together. Normally, when you run the solver, it pushes all the constraint costs to zero, and you know you've solved everything. Sometimes it would get stuck in a local minimum and require user intervention to help it get to the right solution. That was surprisingly rare. If you have conflicting constraints it simply fails to reach a cost of zero at all. You can handle that in your interface however you like. The obvious thing is to try and solve a constraint immediately after adding it and then reject the constraint if you can't. (I really didn't expect a local optimization method like gradient descent to work so well, but it did. That said, if I attacked the problem again I would try to use some sort of second order optimization method, I think.)

auxym 12y ago

As a frequent user of Solidworks for ~4 years, I'd have to guess that CAD constraint solvers are not an easy problem. It happens pretty often that you'll modify a single constraint (flipping it is a common culprit), the solver will get "confused" and flip a bunch of your other constraints around. Constraint conflict resolution also often gets very hairy to almost impossible. Sometimes the fastest thing to do is to nuke a good part of your constraints and start over -- in a saner way. I guess the BIG CAD packages (CATIA, NX) might be a bit better at this, or at least better at strongly encouraging saner ways of build parametric constraints (which is what I've heard). It's too bad that there isn't a simple, intuitive and useful free/oss CAD software out there. With the whole hobbyist maker movement explosion out there, a lot of people would be thrilled to have something like that. Though, it seems that things are not very much better in the PCB CAD/CAM world either.

colah3 12y ago
I was really excited about handling some of the messy constraint situations better than existing tools. I'll split this into two pieces: > It happens pretty often that you'll modify a single constraint (flipping it is a common culprit), the solver will get "confused" and flip a bunch of your other constraints around. For "confused" constraint solvers, I see this as largely being a problem of there being lots of solutions to a well constrained system, because of flips and such. It needs to be easy for the user to specify which one they want. Our approach was to have fast pulls of the mouse temporarily over ride the constraint solver. So, if you needed to flip the model, you do a really fast pull and it would flip. This works much better with multi touch, where you can just grab a few points with different fingers and force your model into whatever shape you want. > Constraint conflict resolution also often gets very hairy to almost impossible. There's some really powerful tools from algebraic geometry I tried to apply to this. In particular, there's these things called Grobner Bases which you can use to test if certain polynomials imply that another is true, false, or if it's independent of them. From the users perspective, I wanted to use these to do a few things. (1) Display implied constraints. If you make three corners of a quadrilateral perpendicular, the fourth is forced to be perpendicular. I grayed out perpendicular constraint could alert you to this, and prevent you from adding a conflicting constraint. Obviously, that example is kind of silly, but I think that propagating constraints through the whole model would really help people understand how more complicated models are constrained. (2) If you try to add a constraint which conflicts with preexisting ones, highlight in red a minimal set it conflicts with. I never got this part of the project to work though. I did some very small proof of concepts in sage, but couldn't really get things to work. I'm not really sure how realistic it is to make these work for real models.

pwnna 12y ago

> I think there's a lot of interesting work to be done linking programmatic and graphical CAD. I thought about this as well, but I don't know anyone who works with CAD who would likely switch their work flow from GUI to text-based, other than people in this thread, I suppose. Furthermore, while I don't know about the details on how to implement a text-based 3D modelling language for constraint based modelling, I don't think there's a lot of point if a GUI is going to be attached to it anyway. Existing systems already do a reasonable job. One of the most annoying part of the confused constraint system, for me, is that it is difficult to fix the constraints. Options are likely to be hidden behind layers and layers of menus and dialog. A text file can be easily searched and diffed, which in my mind should make a confused system easier to resolve. So maybe this kind of constraint based CAD should have both a language and a revision control system built into it, or something.

colah3 12y ago
> but I don't know anyone who works with CAD who would likely switch their work flow from GUI to text-based, other than people in this thread, I suppose. Programming doesn't have to be writing text. :P Everyone seems to be thinking about APIs to the CAD program, which solidworks, autodesk, and presumably others provide. I had in mind a pretty deep way to embed a lambda calculus into the visual interface. The hope was to make it intuitive to create powerful parametric models, where every sketch is a function of different parameters. We never implemented that part, though. :/