B-Spline Constraints: Fully Funded! Thanks everybody!

Info about new community or project announcements, implemented features, classes, modules or APIs. Might get technical!
PLEASE DO NOT POST HELP REQUESTS OR OTHER DISCUSSIONS HERE!
Forum rules
Be nice to others! Respect the FreeCAD code of conduct!
User avatar
jnxd
Posts: 951
Joined: Mon Mar 30, 2015 2:30 pm
Contact:

Re: B-Spline Constraints: Fully Funded! Thanks everybody!

Post by jnxd »

abdullah wrote: Mon Jan 09, 2023 7:15 pm
jnxd wrote: Mon Jan 09, 2023 6:52 pm By "first version" do you mean the one which led to zero length lines in cases?
Yes. I mean that one. I think that mechanism may be preventing the point to converge here. Could you check that?
OK. I'm prioritizing the infinite loop (mentioned in french forum and https://github.com/FreeCAD/FreeCAD/issues/8143), and this is next in the line!
My latest (or last) project: B-spline Construction Project.
abdullah
Veteran
Posts: 4935
Joined: Sun May 04, 2014 3:16 pm
Contact:

Re: B-Spline Constraints: Fully Funded! Thanks everybody!

Post by abdullah »

jnxd wrote: Tue Jan 10, 2023 1:48 pm OK. I'm prioritizing the infinite loop (mentioned in french forum and https://github.com/FreeCAD/FreeCAD/issues/8143), and this is next in the line!
The infinite loop no longer happens.

It could make sense to check if this issue happened before the merge of the knots commit (not the tangency one, but the previous one).
User avatar
jnxd
Posts: 951
Joined: Mon Mar 30, 2015 2:30 pm
Contact:

Re: B-Spline Constraints: Fully Funded! Thanks everybody!

Post by jnxd »

abdullah wrote: Tue Jan 10, 2023 8:20 pm
jnxd wrote: Tue Jan 10, 2023 1:48 pm OK. I'm prioritizing the infinite loop (mentioned in french forum and https://github.com/FreeCAD/FreeCAD/issues/8143), and this is next in the line!
The infinite loop no longer happens.

It could make sense to check if this issue happened before the merge of the knots commit (not the tangency one, but the previous one).
I did just notice the infinite loop doesnt happen (the one when setting the degree to high, not the split one). Maybe I was testing with an older version when I confirmed it.

However the degree issue should be fixed still. Making a 8-degree periodic spline but only giving 4 points still gives bad results.

We could test that using the 0.20 version (the degree setting was included). If confirmed, the fixes should be applied towards the next point release.
My latest (or last) project: B-spline Construction Project.
User avatar
jnxd
Posts: 951
Joined: Mon Mar 30, 2015 2:30 pm
Contact:

Re: B-Spline Constraints: Fully Funded! Thanks everybody!

Post by jnxd »

abdullah wrote: Mon Jan 09, 2023 7:15 pm
Yes. I mean that one. I think that mechanism may be preventing the point to converge here. Could you check that?
So I did a quick check through GDB, and the "conflicting" groups are just the one PointOnObject (from tangent-at-knot) and two Equal constraints. What I now get is this is just being called "partially redundant" as opposed to some constraints being auto-removed.

[EDIT:Just to clarify, by "now", I mean after certain changes in the diagnosis step that prevents from calling non-convergent cases fully-constrained.]

@adrianinsaval what is the behaviour on your end now?
My latest (or last) project: B-spline Construction Project.
User avatar
jnxd
Posts: 951
Joined: Mon Mar 30, 2015 2:30 pm
Contact:

Re: B-Spline Constraints: Fully Funded! Thanks everybody!

Post by jnxd »

abdullah wrote: Mon Jan 09, 2023 6:34 pm I think there might be two forces at play: 1) the internals of the tangency that prevent the line endpoint from converging to the knot position (if the line is first made tangent to the knot and the the end point is tried to be made coincident),...

For 1), it may be possible to "modify" what we introduced when trying to avoid the lack of convergence of the first version.
The way I see it, this is not the case. The sketcher constraint of "knot to line tangent" has two solver constraints: point-on-line and slope equality. From gdb I can tell that the issue is happening on the "point-on-line" side: when the coincident constraint is added, the point-on-line is automatically satisfied and thus redundant.
...and 2) the fact that the selection of the tangency (point-to-line) is not adequate.

For 2), I think we have a case that we have not considered, point-to-point tangency with a line endpoint and the knot. That is what we should use to solve the legit partial redundancy message. That one should add internally a concident as opposed to a point on object.
This is indeed a possibility, and easy to implement. In fact, this may be a solution to support two slopes at a C0-knot: the side of the B-spline to consider can depend on whether we have selected the start or end of line.

However, the issue remains that one can always repeat the steps as Adrian suggested. One possibility I see is to make the "point-on-line" part of the "tangent-at-knot" constraint at lower priority, in the following way:
1. If another sketcher constraint can be completely removed while satisfying all solver constraints that it imposes, remove that.
2. If (1) is not possible, and a lower priority solver constraint can be completely removed, remove that.
3. If there is a conflict between a constraint at this priority and another at high priority, this should still be treated as a full conflict (as opposed to the temporary constraints we impose when dragging elements).
For lines and endpoints there is a constraint swapping mechanism (constraint substitution) to make user's life a little bit less miserable, a similar one should be then implemented for knots and line endpoints...
This is something I need to explore. Could you point me to the relevant part of the code where this substitution takes place?

Meanwhile, I'll add the "knot-to-endpoint tangent" constraint since that is definitely needed.
My latest (or last) project: B-spline Construction Project.
abdullah
Veteran
Posts: 4935
Joined: Sun May 04, 2014 3:16 pm
Contact:

Re: B-Spline Constraints: Fully Funded! Thanks everybody!

Post by abdullah »

jnxd wrote: Wed Jan 11, 2023 4:22 pm So I did a quick check through GDB, and the "conflicting" groups are just the one PointOnObject (from tangent-at-knot) and two Equal constraints. What I now get is this is just being called "partially redundant" as opposed to some constraints being auto-removed.
You do not need GDB for that. If you have the debug of the Advanced solver dialog to iteration level, you get something like this:

Code: Select all

16:49:24  EigenSparseQR, Threads: 1, Vectorization: On, Pivot Threshold: 1e-13, Params: 48, Constr: 36, Rank: 35
16:49:24  Analysing groups of constraints of special interest:
[16 16 17 ]
16:49:24  Chosen redundants: [17 ]
16:49:24  DL: tolg: 1e-80, tolx: 1e-80, tolf: 1e-10, convergence: 1e-10, dogLegGaussStep: FullPivLU, xsize: 48, csize: 35, maxIter: 105
16:49:24  DL: stopcode: 1, Success
16:49:24  Sketcher::RedundantSolving-DogLeg-
16:49:24  Sketcher Redundant solving: 1 redundants
16:49:24  (Partially) Redundant, Group 0, index 2, Tag: 17
16:49:24  Sketcher::setUpSketch()-T:0.004
So, there is a single group of interest which comprises two counts for the coincidence constraint (vertical and horizontal) and one count for the tangency constraint (of the Sketcher level constraints). The coincidence is two solver equalities, and the "redundant" part here is the Point on Object.
abdullah
Veteran
Posts: 4935
Joined: Sun May 04, 2014 3:16 pm
Contact:

Re: B-Spline Constraints: Fully Funded! Thanks everybody!

Post by abdullah »

jnxd wrote: Mon Jan 16, 2023 2:43 am The way I see it, this is not the case. The sketcher constraint of "knot to line tangent" has two solver constraints: point-on-line and slope equality. From gdb I can tell that the issue is happening on the "point-on-line" side: when the coincident constraint is added, the point-on-line is automatically satisfied and thus redundant.
IMO, both are true. That is why you are getting the partial redundant (if you first add the coincident and then the tangency). This is indeed what we should see doing it the other way around. However, with the latter we get no convergence, whereas in the former we get the "partial redundant". The problem of the convergence is what I think is related to the fix for the other corner case.

If you want to pursue this, I propose that you add support for adding point-to-point tangency, and add internally the coincident constraint. Constraint substitution can come later.
jnxd wrote: Mon Jan 16, 2023 2:43 am In fact, this may be a solution to support two slopes at a C0-knot: the side of the B-spline to consider can depend on whether we have selected the start or end of line.
It may not be the most seamless user interaction. We can look at it separately if you want.
jnxd wrote: Mon Jan 16, 2023 2:43 am However, the issue remains that one can always repeat the steps as Adrian suggested. One possibility I see is to make the "point-on-line" part of the "tangent-at-knot" constraint at lower priority, in the following way:
1. If another sketcher constraint can be completely removed while satisfying all solver constraints that it imposes, remove that.
2. If (1) is not possible, and a lower priority solver constraint can be completely removed, remove that.
3. If there is a conflict between a constraint at this priority and another at high priority, this should still be treated as a full conflict (as opposed to the temporary constraints we impose when dragging elements).
For multi-solver constraint it is not that straightforward. Here you want to get rid of half the tangency constraint (the point on object part). This is exactly what FC currently does, following popularity contest and redundant solving (noting that it is doing it by telling you "partially redundant"). The lack of convergence is unrelated to the redundancy. Redundant constraints converge, unless something is preventing them from converging.

I do see that we could add another intermediate priority for constraint internal constraints. It is not that I think it is meritless. However, this kind of hidden decisions on partial constraints is something users have complained about (Chrisb is one prominent detractor). Additionally, partial redundancies accumulated over a sketch tend to lead to bigger problems in the detection of subsequent redundancies and conflicting constraints.

Because of these issues, we have constraint substitution in place for other tangencies. Just draw two curves select both edges make a tangency, then select the endpoints and make a coincident constraint. The system will collapse them into a single tangency with an internal coincidence. The same happens if you invert the order.

This solution (i.e. checking for other constraints when adding new ones and performing a substitution) is not the most elegant solution, but it is very effective. It leads to no redundancies and prevents those further issues.
abdullah
Veteran
Posts: 4935
Joined: Sun May 04, 2014 3:16 pm
Contact:

Re: B-Spline Constraints: Fully Funded! Thanks everybody!

Post by abdullah »

DeepSOIC wrote: Thu Dec 29, 2022 12:16 am Hi everyone! @abdullah has kindly asked me to have a look at this. I have looked at some of the code of the pull-request (jnxd's sketcher-point-on-bspline branch at 44fb105b4d1d6a8aa724e1384dc5ae570894b1fe), but did not compile it, and did not fully read this discussion. Here's my opinion.

I have no serious objections to the current implementation (constraint having the parameter of the point stored as a datum value of the constraint). This is exactly how i think this constraint should be implemented, mainly because finding the distance to a spline given just point coordinates requires significant computational time (numerical solving for the closest point), but also because splines can be periodic and/or self-intersecting, so finding such point is (in general) ambiguous.
Thank you for reading the code and the very appropriate remark on periodic/self-intersecting.
DeepSOIC wrote: Thu Dec 29, 2022 12:16 am I have noticed a few minor things.
1) ConstraintPointOnBSpline has a std::vector<double> factors member, which can be replaced with just a single non-array variable in constraint computations (as far as i can see).
2) these's one comment in the code that point-on-bspline constraint in driving mode does not make sense. My opinion is that it does absolutely make sense if the value of the parameter is made available for editing/expression in the UI. Think of it as non-driving = a bead on the spline that is free to slide along, driving = a crimp affixed to a particular place of the spline.
3) the lack of dynamic segment hopping while the solver is working may cause a mis-solution. Allowing the hopping will require to declare all of the poles (and weights and knots) as dependent parameters of the constraint, causing a lot of extra grad runs, possibly causing a significant drop in performance for splines with many segments. I'm not sure what is more important here, correctness or performance.
Thanks.

For 1) I will let Ajinkya decide whether he wants to tackle it now or in a separate PR.

For 2) I understand the terminology may be misleading. What is implemented is what you say it should be. A fixed parameter is added to FixedParameters array. A freewheeling parameter (any) is added to Parameters. A freewheeling parameter that is part of a non-driving constraint is, in addition to Parameters, also added to drivenParameters. This has to do with diagnose (detection of DoFs).

For 3) I think it is in Ajinkya's radar. I think there would be more calls, however, all but the current ones will directly return 0, as only a small number of poles are affected by a single segment. I hope we will see this. I think it is important and gives the impression of a more finished product.

Thanks again. I really appreciate your insight :)
jnxd wrote: Thu Dec 29, 2022 4:26 am However if it does result in a dense matrix (albeit with most elements within it set to zero) the performance penalty is indeed significant.
It should not. Diagnosis is run at the beginning, with the parameter value as initialised by OCC. If the constraint uses this value to calculate gradients (Jacobian), all but the intervening ones will be zero. This will keep the matrix sparse. If a point can move in a segment of BSpline, it will move on any to other. So the fact that diagnosis is restricted to the relevant segment appears to me an advantage...
jnxd wrote: Tue Dec 27, 2022 7:07 pm If you look into the code for tangent to b-spline (not tangent at knot), you'll notice that I have added more parameters which makes it still more complicated (though in the future it may be formalized better as angleviapoint).
Are you really looking for me to have a heart attack? With this parameter I have enough for months!! :lol:

Now a more serious answer. We really need to have this code tested before!! ... that would give me time to get a pacemaker ;)
User avatar
jnxd
Posts: 951
Joined: Mon Mar 30, 2015 2:30 pm
Contact:

Re: B-Spline Constraints: Fully Funded! Thanks everybody!

Post by jnxd »

abdullah wrote: Tue Jan 17, 2023 3:18 pm
jnxd wrote: Thu Dec 29, 2022 4:26 am However if it does result in a dense matrix (albeit with most elements within it set to zero) the performance penalty is indeed significant.
It should not. Diagnosis is run at the beginning, with the parameter value as initialised by OCC. If the constraint uses this value to calculate gradients (Jacobian), all but the intervening ones will be zero. This will keep the matrix sparse. If a point can move in a segment of BSpline, it will move on any to other. So the fact that diagnosis is restricted to the relevant segment appears to me an advantage...
Note that the sparsity of a matrix in the data structure may be different than the actual sparsity of the matrix: it is possible that elements that are actually zero are stored explicitly in the data structure, eating up resources during computations. This may not be a bad thing all the time (e.g. in GPU matrix operations, which we don't do here), but just something to keep in mind.
abdullah wrote: Tue Jan 17, 2023 3:18 pm
jnxd wrote: Tue Dec 27, 2022 7:07 pm If you look into the code for tangent to b-spline (not tangent at knot), you'll notice that I have added more parameters which makes it still more complicated (though in the future it may be formalized better as angleviapoint).
Are you really looking for me to have a heart attack? With this parameter I have enough for months!! :lol:

Now a more serious answer. We really need to have this code tested before!! ... that would give me time to get a pacemaker ;)
Definitely don't have anything against your heart's health. It's in everyone's (including Sketcher's) interest that it keeps working fine ;).

I think most of the actual "tests" will eventually only happen in the wild. Anyone who wanted to test it pre-merge seems to have already done so.
My latest (or last) project: B-spline Construction Project.
User avatar
jnxd
Posts: 951
Joined: Mon Mar 30, 2015 2:30 pm
Contact:

Re: B-Spline Constraints: Fully Funded! Thanks everybody!

Post by jnxd »

abdullah wrote: Tue Jan 17, 2023 3:18 pm
DeepSOIC wrote: Thu Dec 29, 2022 12:16 am I have noticed a few minor things.
1) ConstraintPointOnBSpline has a std::vector<double> factors member, which can be replaced with just a single non-array variable in constraint computations (as far as i can see).
...
3) the lack of dynamic segment hopping while the solver is working may cause a mis-solution. Allowing the hopping will require to declare all of the poles (and weights and knots) as dependent parameters of the constraint, causing a lot of extra grad runs, possibly causing a significant drop in performance for splines with many segments. I'm not sure what is more important here, correctness or performance.
Thanks.

For 1) I will let Ajinkya decide whether he wants to tackle it now or in a separate PR.
...

For 3) I think it is in Ajinkya's radar. I think there would be more calls, however, all but the current ones will directly return 0, as only a small number of poles are affected by a single segment. I hope we will see this. I think it is important and gives the impression of a more finished product.
Just addressed 1. and 3. here:

1) The variable is now just a non-array double.
3) I added the dynamic segment hopping, at least as a prototype. It's not particularly difficult to implement, but we need to know the performance hit. Here I just update the piece in error. We could also only update it if it goes beyond the range. That's done too.
My latest (or last) project: B-spline Construction Project.
Post Reply