Highlighting unconstrained features in the sketch workbench (#1041)

Here's the place for discussion related to coding in FreeCAD, C++ or Python. Design, interfaces and structures.
kcleung
Posts: 120
Joined: Sun Apr 24, 2011 11:56 am

Highlighting unconstrained features in the sketch workbench (#1041)

Postby kcleung » Mon Apr 17, 2017 3:52 am

As explained in issue #1041:

https://freecadweb.org/tracker/view.php?id=1041

in a sketch, it is very easy to forget to join the points together, and as a result, it is easy to accidentally leave features unconstrained, which is very difficult to debug.

Currently, the SketchObject::getLastDoF checks the lastDoF counter and report the degree of freedom.

Then I saw the lastDoF is set up by a call in SketchObject.cpp:

solvedSketch.setUpSketch(getCompleteGeometry(), Constraints.getValues(), getExternalGeometryCount());

then I looked at Sketch::setupSketch(const std::vector<Part::Geometry *> &GeoList,
const std::vector<Constraint *> &ConstraintList,
int extGeoCount))

in Sketch.cpp:

and the degree of freedom is obtained by calling: GCSsys.dofsNumber();



Now I would like to get a list of degree of freedom and somehow show it either on the drawing board, or at least list it in a table within the "solver messages" window. Where can I get the list of freedoms?
abdullah
Posts: 3583
Joined: Sun May 04, 2014 3:16 pm

Re: Highlighting unconstrained features in the sketch workbench (#1041)

Postby abdullah » Mon Apr 17, 2017 7:55 am

Some ideas:
1. DoF is a property of a equation system. There is no such a thing to my knowledge as "a list of DoF".
2. A geometric element has at least one, but generally more parameters (actually a point having 2, one for x, one for y is the minimum I can think of).
3. Parameters get constrained... by constraints, a "solver" constraint per parameter.
4. As parameters get constraint, the number of DoF of the system gets reduced.

All this action goes on in GCS.cpp. Look for that beautiful Jacobian matrix in:

Code: Select all

int System::diagnose(Algorithm alg)
How to tackle this?

a) The Jacobian restricts parameters based on constraints. You can get the DoF of a system by doing a QR decomposition as shown in that function (do not do another one, we already have one in that function I referred above).
b) You can keep track of parameters and the geometric elements to which they belong with the Geoms array in Sketch.h

So basically you know how many parameters a geometric element has and you should be able to know from the QR decomposition which of them are constraint. So elements having all its parameters constraint are "constraint".

With this information it is up to you to show the elements fully constraint or to show those which are not.

Caveats:
QR decomposition is an "expensive" operation. Just try to reuse results. Take a look at the libEigen functions involved in the QR decomposition.

Good luck! ;)
kcleung
Posts: 120
Joined: Sun Apr 24, 2011 11:56 am

Re: Highlighting unconstrained features in the sketch workbench (#1041)

Postby kcleung » Mon Apr 17, 2017 10:23 am

Thanks Abdullah! I start having a look at System::diagnose(Algorithm alg) in GCS.cpp right now.

All I want is to fish a list of unconstrained features. So what is the most efficient way to get it?

Once I get this list, I would love to color the unconstrained feature with a color that is different from the one normally used, but I will worry about this part later.
abdullah
Posts: 3583
Joined: Sun May 04, 2014 3:16 pm

Re: Highlighting unconstrained features in the sketch workbench (#1041)

Postby abdullah » Mon Apr 17, 2017 8:28 pm

abdullah wrote:How to tackle this?

a) The Jacobian restricts parameters based on constraints. You can get the DoF of a system by doing a QR decomposition as shown in that function (do not do another one, we already have one in that function I referred above).
b) You can keep track of parameters and the geometric elements to which they belong with the Geoms array in Sketch.h

So basically you know how many parameters a geometric element has and you should be able to know from the QR decomposition which of them are constraint. So elements having all its parameters constraint are "constraint".

With this information it is up to you to show the elements fully constraint or to show those which are not.
I think these are the main lines (reuse the QR decomposition and see how one can map the QR rows/cols with elements/constraints). You have to dig a little bit in the specifics. If I would have to do this today, I would start looking into what can I achieve with the existing QR decomposition, specially with the R triangular matrix. It is not that I like riddles, it is that today I would have to figure it out myself ;)
kcleung
Posts: 120
Joined: Sun Apr 24, 2011 11:56 am

Re: Highlighting unconstrained features in the sketch workbench (#1041)

Postby kcleung » Mon Apr 17, 2017 11:10 pm

I had a good look at System::diagnose().


Initially, diagnose() sets up the matrix J where the first index (is this row or column?) represents a list of constraints, and the second index represents the parameters. So each constraint apparently has the full list of parameters to begin with:

Eigen::MatrixXd J(clist.size(), plist.size());
int count=0;
for (std::vector<Constraint *>::iterator constr=clist.begin(); constr != clist.end(); ++constr) {
(*constr)->revertParams();
if ((*constr)->getTag() >= 0) {
count++;
for (int j=0; j < int(plist.size()); j++)
J(count-1,j) = (*constr)->grad(plist[j]);
}
}

though I don't get what grad() does.

Also, the other thing I don't understand is that the code told us plist is a list of parameters (from the entire sketch?). However, each element can have more than one parameters. So at the end, if we manage to identify a subset of parameters from the plist which is unconstrained, then we will somehow need to map each unconstrained parameter to its element, am I correct?



Then part of code:

Eigen::MatrixXd R;
int paramsNum = 0;
int constrNum = 0;
int rank = 0;
Eigen::FullPivHouseholderQR<Eigen::MatrixXd> qrJT;

if(qrAlgorithm==EigenDenseQR){
if (J.rows() > 0) {
qrJT.compute(J.topRows(count).transpose());
//Eigen::MatrixXd Q = qrJT.matrixQ ();

paramsNum = qrJT.rows();
constrNum = qrJT.cols();
qrJT.setThreshold(qrpivotThreshold);
rank = qrJT.rank();

if (constrNum >= paramsNum)
R = qrJT.matrixQR().triangularView<Eigen::Upper>();
else
R = qrJT.matrixQR().topRows(constrNum)
.triangularView<Eigen::Upper>();
}
}

apparently does the QR decomposition. and then if number of rows in J is larger than 0, the code will subsequently identify conflicting and redundant constraints. Then what do the rows and column of the matrix R represent?


Also later in the code, I read of a line:

int res = solve(subSysTmp,true,alg,true);

Is the real action taken here?


Thanks!
abdullah
Posts: 3583
Joined: Sun May 04, 2014 3:16 pm

Re: Highlighting unconstrained features in the sketch workbench (#1041)

Postby abdullah » Tue Apr 18, 2017 1:11 am

kcleung wrote:So each constraint apparently has the full list of parameters to begin with:
Potentially yes. This would be a "fix everything constraint". In practice, the matrix is very sparse (lots of elements are zero).
kcleung wrote:though I don't get what grad() does.
Gradient. The Jacobian is this:
https://en.wikipedia.org/wiki/Jacobian_ ... eterminant
kcleung wrote:Also, the other thing I don't understand is that the code told us plist is a list of parameters (from the entire sketch?). However, each element can have more than one parameters. So at the end, if we manage to identify a subset of parameters from the plist which is unconstrained, then we will somehow need to map each unconstrained parameter to its element, am I correct?
A line has 4 parameters, P1X, P1Y, P2X, P2Y. The Jacobian has the parameters of the full sketch yes. That is why you can get the rank (linked to DoF) from the QR decomposition of the Jacobian.

Mapping:
abdullah wrote:b) You can keep track of parameters and the geometric elements to which they belong with the Geoms array in Sketch.h
All GCS is pointers, Geoms contains all the shapes and its parameters.
kcleung wrote: Then what do the rows and column of the matrix R represent?
https://en.wikipedia.org/wiki/QR_decomposition

As you already discovered, the R matrix is used to identify redundancy/conflicting, when the rank is lower than the number of constraints (i.e. some constraints are linearly dependent, so do not contribute to increasing the rank). Eigen library is nice enough to allow you to track all the columns permutations performed while doing QR, so you can identify the constraints that contributed to each row of the R matrix.
kcleung wrote:int res = solve(subSysTmp,true,alg,true);

Is the real action taken here?
If I remember correctly, that is part of the redundant/conflicting constraint determination. The action the whole diagnose function. I imagine that once you know which constraints are redundant, the rest of the constraints contribute to the current rank (DoF). Then you can use the Eigen functionality I mentioned above to see which parameters are them constraining. I mean, I do not have a solution myself ATM. I just think this is how a solution may be reached to.

It is not an easy undertaking the one you have selected. I will cost you time to fully understand what is happening in the code and then to find a way to achieve what you want.
kcleung
Posts: 120
Joined: Sun Apr 24, 2011 11:56 am

Re: Highlighting unconstrained features in the sketch workbench (#1041)

Postby kcleung » Tue Apr 18, 2017 7:10 am

abdullah wrote: It is not an easy undertaking the one you have selected. I will cost you time to fully understand what is happening in the code and then to find a way to achieve what you want.
Thanks for your pointer, and it will take me the rest of this night to digest what you said.

However, will understand this part of the code help me with development of solvers in other modules, such as the assembly module? If so, then it would be really worthwhile for me to get to the bottom of the code, and the algorithms, despite the upfront cost of my time.
abdullah
Posts: 3583
Joined: Sun May 04, 2014 3:16 pm

Re: Highlighting unconstrained features in the sketch workbench (#1041)

Postby abdullah » Tue Apr 18, 2017 10:30 pm

kcleung wrote:
abdullah wrote: It is not an easy undertaking the one you have selected. I will cost you time to fully understand what is happening in the code and then to find a way to achieve what you want.
Thanks for your pointer, and it will take me the rest of this night to digest what you said.

However, will understand this part of the code help me with development of solvers in other modules, such as the assembly module? If so, then it would be really worthwhile for me to get to the bottom of the code, and the algorithms, despite the upfront cost of my time.
You are welcome.

To your question:
The geometric solver has some issues but is working. If what you seek is to improve the solver or learn to extract more information from the solver (i.e. how the algorithms work their magic to enforce constraints), then it will help you. If what you seek is to learn how to write constraints to limit parameters (i.e. we already have a geometric solver, now how would I write (a/several) solver constraints to for example enforce that a face of one object is parallel to another)... well, I do not think it is really going to help you much. Everything depends on what you want to learn.

I am very happy to see somebody working on this. If you want to continue, once you have understood what is going on, I am more than happy to try to answer your questions and help you out in the way.