ImplicitCAD: Powerful, Open-Source, Programmatic CAD

The above looks pretty 3d to me.

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.

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

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

[1]: https://www.onshape.com [2]: http://plmsource.industrysoftware.automation.siemens.com/plm...

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

Ha, well someone has to know OpenCASCADE to maintain FreeCAD. And someone has to fix OpenCASCADE when bugs are found, and when it's time to refactor legacy junk...