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: Looking for Crowdfunding

Post by jnxd »

abdullah wrote: Mon Nov 07, 2022 1:33 pm I have this sketch:
Screenshot_20221107_141717.png

I have selected the line, selected the knot and hit tangency constraint. FreeCAD hang. I killed it after 5 minutes.

In a second attempt, it solved but did not update the 3D View. After dragging the B-Spline, it briefly appeared a tangent line on the knot position, only to reduce the line to a point and hang again (killed after 2 minutes):
Screenshot_20221107_142416.png

I did some other tests with the line closer to tangent (as opposed of closer to normal as above). Then it did not hang.
I am aware that if the line is closer to normal than tangent, the solver may fail. However, I don't recall a hang specifically. Could you share a file just before attempting the constraint?

EDIT: Just played around a bit more. I think if the spline is "pretty flat" around the knot then there seems to be some hanging.
abdullah wrote: Mon Nov 07, 2022 1:33 pm It is important for me to know if you can reproduce these issues, as I may be using a different solver configuration (advanced solver parameters), as I did not expect GCS to hang FreeCAD.
There might be an unintended infinite loop somewhere with the new configuration.
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: Almost Done! Help Reach Goal!

Post by abdullah »

Thanks for giving it a run.

I have switch to testing constraining the knot. This I found to work very good.

It

This file:
hang.FCStd
(4.63 KiB) Downloaded 31 times
Makes my system unresponsive with LM and Dogleg. This is my config (that may be slightly different than the default parameters, but should work).
Attachments
Screenshot_20221107_165744.png
Screenshot_20221107_165744.png (63.74 KiB) Viewed 111030 times
User avatar
jnxd
Posts: 951
Joined: Mon Mar 30, 2015 2:30 pm
Contact:

Re: B-Spline Constraints: Almost Done! Help Reach Goal!

Post by jnxd »

abdullah wrote: Mon Nov 07, 2022 3:58 pm Thanks for giving it a run.

I have switch to testing constraining the knot. This I found to work very good.
OK great! What do you suggest we do about tangent issue then? Given the complexity of B-splines I'm sure that there can be convergence issues given a sufficiently difficult initial condition. The only stopper then should be the hang-up right?
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: Almost Done! Help Reach Goal!

Post by abdullah »

jnxd wrote: Mon Nov 07, 2022 4:24 pm OK great! What do you suggest we do about tangent issue then? Given the complexity of B-splines I'm sure that there can be convergence issues given a sufficiently difficult initial condition. The only stopper then should be the hang-up right?
Hang-up is really a show stopper. It is our task to avoid that the user feels the urge to throw the computer through the window. We do like computers.

About tangent, it would be great if you could debug what is happening. Is it converging very slowly? Why the 100 iterations limit is not being hit? The code has really not gotten to 100 iterations in 5 minutes on an i8?

If it is a convergence issue, for example because the equation expression is bad conditioned, it might be possible to isolate the region where this happens and do "something slightly different". But we will cross the bridge when we get there...
User avatar
jnxd
Posts: 951
Joined: Mon Mar 30, 2015 2:30 pm
Contact:

Re: B-Spline Constraints: Almost Done! Help Reach Goal!

Post by jnxd »

abdullah wrote: Mon Nov 07, 2022 4:48 pm About tangent, it would be great if you could debug what is happening. Is it converging very slowly? Why the 100 iterations limit is not being hit? The code has really not gotten to 100 iterations in 5 minutes on an i8?
From what I can tell the solver works out, but the problem happens somewhere after. Here's the last back-trace I could find:

Code: Select all

#0  GCS::System::diagnose(GCS::Algorithm) (this=0x55555894ae80, alg=GCS::DogLeg)
    at /.../src/Mod/Sketcher/App/planegcs/GCS.cpp:3941
#1  0x00007fffb3673430 in GCS::System::initSolution(GCS::Algorithm) (this=0x55555894ae80, alg=GCS::DogLeg)
    at /.../src/Mod/Sketcher/App/planegcs/GCS.cpp:1488
#2  0x00007fffb37ecee8 in Sketcher::Sketch::setUpSketch(std::vector<Part::Geometry*, std::allocator<Part::Geometry*> > const&, std::vector<Sketcher::Constraint*, std::allocator<Sketcher::Constraint*> > const&, int)
    (this=0x55555894ae40, GeoList=std::vector of length 12, capacity 20 = {...}, ConstraintList=std::vector of length 15, capacity 28 = {...}, extGeoCount=2) at /.../src/Mod/Sketcher/App/Sketch.cpp:251
#3  0x00007fffb35ce9f5 in Sketcher::SketchObject::setUpSketch() (this=0x55555894a1a0)
    at /.../src/Mod/Sketcher/App/SketchObject.cpp:643
#4  0x00007fffb37a81b0 in Sketcher::SketchObjectPy::addConstraint(_object*) (this=0x555558010930, args=0x7fffecf38ac0)
    at /.../src/Mod/Sketcher/App/SketchObjectPyImp.cpp:363
#5  0x00007fffb379aee3 in Sketcher::SketchObjectPy::staticCallback_addConstraint(_object*, _object*)
    (self=0x555558010938, args=0x7fffecf38ac0) at /home/ajinkya/Applications/freecad-build-debug/src/Mod/Sketcher/App/SketchObjectPy.cpp:1022
#6  0x00007ffff3709728 in  () at /usr/lib/libpython3.10.so.1.0
#7  0x00007ffff3702d9b in _PyObject_MakeTpCall () at /usr/lib/libpython3.10.so.1.0
#8  0x00007ffff36fe161 in _PyEval_EvalFrameDefault () at /usr/lib/libpython3.10.so.1.0
#9  0x00007ffff36f79c0 in  () at /usr/lib/libpython3.10.so.1.0
#10 0x00007ffff37a64c4 in PyEval_EvalCode () at /usr/lib/libpython3.10.so.1.0
#11 0x00007ffff37b6293 in  () at /usr/lib/libpython3.10.so.1.0
#12 0x00007ffff37b19ea in  () at /usr/lib/libpython3.10.so.1.0
#13 0x00007ffff37a96f1 in PyRun_StringFlags () at /usr/lib/libpython3.10.so.1.0
#14 0x00007ffff400631e in Base::InterpreterSingleton::runString[abi:cxx11](char const*)
    (this=0x5555555caaa0, sCmd=0x5555585cb628 "App.getDocument('test_for_knot_tangent_hang').getObject('Sketch').addConstraint(Sketcher.Constraint('TangentViaPoint',9,5,7,1)) ") at /.../src/Base/Interpreter.cpp:240
#15 0x00007ffff669bbc5 in Gui::Command::_runCommand(char const*, int, Gui::Command::DoCmd_Type, char const*)
    (file=0x7fff01062600 "/.../src/Gui/CommandT.h", line=384, eType=Gui::Command::Doc, sCmd=0x5555585cb628 "App.getDocument('test_for_knot_tangent_hang').getObject('Sketch').addConstraint(Sketcher.Constraint('TangentViaPoint',9,5,7,1)) ")
    at /.../src/Gui/Command.cpp:700
#16 0x00007ffff669b82f in Gui::Command::_doCommand(char const*, int, Gui::Command::DoCmd_Type, char const*, ...)
    (file=0x7fff01062600 "/.../src/Gui/Command.cpp:652
#17 0x00007fff00ce99e5 in Gui::cmdAppObjectArgs<int&, int&, int&, int>(App::DocumentObject const*, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&, int&, int&, int&, int&&)
    (obj=0x55555894a1a0, cmd="addConstraint(Sketcher.Constraint('TangentViaPoint',%d,%d,%d,%d)) ")
    at /.../src/Gui/CommandT.h:384
#18 0x00007fff00cc9e86 in CmdSketcherConstrainTangent::activated(int) (this=0x55555897a940, iMsg=0)
    at /.../src/Mod/Sketcher/Gui/CommandConstraints.cpp:4178
#19 0x00007ffff669a62b in Gui::Command::_invoke(int, bool) (this=0x55555897a940, id=0, disablelog=true)
    at /.../src/Gui/Command.cpp:419
#20 0x00007ffff669a36b in Gui::Command::invoke(int, Gui::Command::TriggerSource)
    (this=0x55555897a940, i=0, trigger=Gui::Command::TriggerAction) at /.../src/Gui/Command.cpp:384
#21 0x00007ffff66883c4 in Gui::Action::onActivated() (this=0x555558862270) at /.../src/Gui/Action.cpp:102
#22 0x00007ffff668fe33 in Gui::Action::qt_static_metacall(QObject*, QMetaObject::Call, int, void**)
I went a little deeper while in the code, and I see a while (1) in System::identifyConflictingRedundantConstraints.
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: Almost Done! Help Reach Goal!

Post by jnxd »

abdullah wrote: Mon Nov 07, 2022 4:48 pm About tangent, it would be great if you could debug what is happening. Is it converging very slowly? Why the 100 iterations limit is not being hit? The code has really not gotten to 100 iterations in 5 minutes on an i8?
I reverted the commit bffb82d5316c79e330d91ef69f0075941a3e0c59 and now it just results in an "over-constrained sketch".
Screenshot from 2022-11-08 18-25-42.png
Screenshot from 2022-11-08 18-25-42.png (115.85 KiB) Viewed 110979 times
My guess is that the changes there affect the algorithm checking redundant and conflicting constraints. The ideal way forward may be to adapt the algorithm to consider internal alignments as well.
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: Almost Done! Help Reach Goal!

Post by abdullah »

jnxd wrote: Mon Nov 07, 2022 7:56 pm I went a little deeper while in the code, and I see a while (1) in System::identifyConflictingRedundantConstraints.
I see. That while loop is for the popularity contest to rule on redundant/conflicting constraints.

When doing the QR decomposition of the Jacobian of constraints, the number of rows of constraints does not match the number of DoFs taken (i.e. the number of linearly independent rows, i.e. the rank of the Jacobian). This happens because: a) there are conflicting constraints or b) there are redundant constraints.

So the first finding (upstream), in System::diagnose(...), is that identifyConflictingRedundantConstraints(...) is called. Thus there are (most likely unless something is really wrong) redundant solver constraints, which should not be the case in such a simple tangency.

Because of pivoting and row permutations during QR decomposition, these redundant/conflicting constraints appear in the R matrix (the upper triangular matrix of the QR decomposition), non-zeros over the pivot are removed, so as to identify the actual constraints.

The popularity contest works by identifying which of those constraints are the ones that should be removed, to tell the user and to solve a temporary system to see if it converges or not, to decide whether they are conflicting or redundant constraints. This should not hang despite the while(1).

I wrote that above as it is good that more of us are aware of how it works.

So:
- Problem 1: there are redundant constraints, and we need to log that Jacobian and R matrix to a file and to see what is generating that redundancy.
- Problem 2: I changed the popularity contest very recently so that internal alignment constraints are not shown as redundant. Here I need to see if I need to consider an additional exit condition in case internal alignment constraints alone generate a redundancy. Somehow, this should not be necessary when internal alignment constraints are not redundant in the first place, but the cost for a user, if this goes into production, is high.

I will look into it.

EDIT: The solution should not really be to accept redundant constraints of internal alignment. Look at which constraints it is indicating that should be removed...
abdullah
Veteran
Posts: 4935
Joined: Sun May 04, 2014 3:16 pm
Contact:

Re: B-Spline Constraints: Almost Done! Help Reach Goal!

Post by abdullah »

Also, in your screenshot the line turned into a point. If you assign a length to the line (15 mm), then it fails to converge:
Screenshot_20221108_141047.png
Screenshot_20221108_141047.png (90.6 KiB) Viewed 110819 times
abdullah
Veteran
Posts: 4935
Joined: Sun May 04, 2014 3:16 pm
Contact:

Re: B-Spline Constraints: Almost Done! Help Reach Goal!

Post by abdullah »

Momentarily, I have changed branch to test the knot only version:
https://github.com/FreeCAD/FreeCAD/pull/7484

This still has the issues with the signed/unsigned we discussed via PM for version 2.

I have been giving it some runs and looks good from a functionality point of view, including the solver.

I do have a question. Which impact do you foresee for older projects having B-Splines?

I have opened some of mine, but I generally use a block constraint on a B-Spline at the end to fix what is left, so I see no issue. This is important for backwards compatibility. I would like to anticipate any problem users may face because of the introduction of this PR.
User avatar
jnxd
Posts: 951
Joined: Mon Mar 30, 2015 2:30 pm
Contact:

Re: B-Spline Constraints: Almost Done! Help Reach Goal!

Post by jnxd »

abdullah wrote: Tue Nov 08, 2022 1:48 pm Momentarily, I have changed branch to test the knot only version:
https://github.com/FreeCAD/FreeCAD/pull/7484
OK. Let's move to that then.
abdullah wrote: Tue Nov 08, 2022 1:48 pm This still has the issues with the signed/unsigned we discussed via PM for version 2.
Yeah I had addressed it only in #7607. I changed some signatures (in getLinCombFactors), so this needs to be looked up in details again.
abdullah wrote: Tue Nov 08, 2022 1:48 pm I have been giving it some runs and looks good from a functionality point of view, including the solver.

I do have a question. Which impact do you foresee for older projects having B-Splines?

I have opened some of mine, but I generally use a block constraint on a B-Spline at the end to fix what is left, so I see no issue. This is important for backwards compatibility. I would like to anticipate any problem users may face because of the introduction of this PR.
You might want to try with periodic B-splines and/or combinations of multiplicities. Also, maybe try with different weights (rational B-splines), which have now become more finnicky. That said, I don't anticipate any problems simply by opening an older file. The constraint is in effect a generalization of the symmetric constraint.
My latest (or last) project: B-spline Construction Project.
Post Reply