Reimplementing constraint solver

Discussion about the development of the Assembly workbench.
Mark Szlazak
Posts: 424
Joined: Tue Apr 04, 2017 6:06 pm
Location: SF Bay Area, California

Re: Reimplementing constraint solver

Postby Mark Szlazak » Wed Mar 25, 2020 3:17 pm

My apologies if this is not the right place for these questions.
Does your program provide "under-constrained", "fully-constrained" and "over-constrained" feedback?
If so what technique/algorithm is used to determine those conditions?
Thanks.
abdullah
Posts: 3530
Joined: Sun May 04, 2014 3:16 pm

Re: Reimplementing constraint solver

Postby abdullah » Wed Mar 25, 2020 3:36 pm

DeepSOIC wrote:...
I have pushed some cosmetic self() to getHandle() renaming for coherence, but you may have to rebase before pushing or there is chance the repo does not compile (if you used self() in the meantime).
User avatar
DeepSOIC
Posts: 7791
Joined: Fri Aug 29, 2014 12:45 am
Location: Saint-Petersburg, Russia

Re: Reimplementing constraint solver

Postby DeepSOIC » Wed Mar 25, 2020 4:12 pm

Mark Szlazak wrote:
Wed Mar 25, 2020 3:17 pm
Does your program provide "under-constrained", "fully-constrained" and "over-constrained" feedback?
If so what technique/algorithm is used to determine those conditions?
No, not yet. That's what that scary diagnose does. It's not yet implemented in ConstraintSolver.
User avatar
DeepSOIC
Posts: 7791
Joined: Fri Aug 29, 2014 12:45 am
Location: Saint-Petersburg, Russia

Re: Reimplementing constraint solver

Postby DeepSOIC » Wed Mar 25, 2020 4:32 pm

abdullah wrote:
Wed Mar 25, 2020 3:36 pm
I have pushed some cosmetic ...
:|
abdullah
Posts: 3530
Joined: Sun May 04, 2014 3:16 pm

Re: Reimplementing constraint solver

Postby abdullah » Wed Mar 25, 2020 4:35 pm

Mark Szlazak wrote:
Wed Mar 25, 2020 3:17 pm
My apologies if this is not the right place for these questions.
Does your program provide "under-constrained", "fully-constrained" and "over-constrained" feedback?
If so what technique/algorithm is used to determine those conditions?
Thanks.
There are some requirements:
1. You need a rank-revealing decomposition.
2. You must reveal which rows/columns (parameters/constraints) of the original matrix give rise to redundant/conflicting constraints or are not constraint parameters. Sketcher does this with a QR decomposition, using the R matrix. Eigen keeps track of the transpositions/permutations of the pivoting during decomposition, which allows to map the R matrix to the original rows/columns

QR is rather expensive computationally. I think it was gael from Eigen suggested using other cheaper rank revealing decomposition (LU I think it was), but then is the problem of identifying redundant/conflicting and unconstrained parameters.

For reasons I do not understand, to get the unconstrained parameters, you need to use a dense QR with full pivoting. SparseQR is not good enough for this (or the needed tracking is not exposed in eigen or I do not understand how to use what it gives).

If I implement the diagnosis, I will use QR because it is what I know and "kind of" understand.
abdullah
Posts: 3530
Joined: Sun May 04, 2014 3:16 pm

Re: Reimplementing constraint solver

Postby abdullah » Wed Mar 25, 2020 4:38 pm

DeepSOIC wrote:
Wed Mar 25, 2020 4:32 pm
abdullah wrote:
Wed Mar 25, 2020 3:36 pm
I have pushed some cosmetic ...
:|
I know you expect other "help" and other "speed". I am not there yet. :|
Mark Szlazak
Posts: 424
Joined: Tue Apr 04, 2017 6:06 pm
Location: SF Bay Area, California

Re: Reimplementing constraint solver

Postby Mark Szlazak » Wed Mar 25, 2020 4:57 pm

abdullah wrote:
Wed Mar 25, 2020 4:35 pm

There are some requirements:
...
I know DeepSonic has been re-implementing things with (dual?) quaternions and i got interested in them with regards to screw-displacement theory. I do not know if that is the direction this could evolve with regards to 3d-constrains in sketches and assemblies. In any case, i found a paper on this topic of screw-theory and reciprocal screws but not in terms of quaternions. I suspect it could be modified for quaternions. It does claim very fast real-time constraint evaluation (under, over, full).

https://www.hindawi.com/journals/mpe/2016/1761968/
User avatar
DeepSOIC
Posts: 7791
Joined: Fri Aug 29, 2014 12:45 am
Location: Saint-Petersburg, Russia

Re: Reimplementing constraint solver

Postby DeepSOIC » Wed Mar 25, 2020 5:13 pm

Mark Szlazak wrote:
Wed Mar 25, 2020 4:57 pm
...
ConstraintSolver has nothing to do with screw theory right now. I was using something from it to implement placement interpolation (SCLERP) in FreeCAD.
ConstraintSolver has no 3d part yet, and thus does not use quaternions in any form. When 3d comes, dual quaternion is going to be used, but in a manner very different to how it's used in SCLERP. That will actually be a challenging conflict to implement a sclerp for constraintsolver, should the need arise.
User avatar
DeepSOIC
Posts: 7791
Joined: Fri Aug 29, 2014 12:45 am
Location: Saint-Petersburg, Russia

Re: Reimplementing constraint solver

Postby DeepSOIC » Wed Mar 25, 2020 5:23 pm

I am planning to attack ellipse next.
User avatar
DeepSOIC
Posts: 7791
Joined: Fri Aug 29, 2014 12:45 am
Location: Saint-Petersburg, Russia

Re: Reimplementing constraint solver

Postby DeepSOIC » Wed Mar 25, 2020 7:19 pm

I've added a bunch of issues toConstraintSolver issue tracker, as a reminder and as thought-provoker.