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!
bleber
Posts: 259
Joined: Thu Jun 30, 2016 5:12 pm

Re: B-Spline Constraints: Looking for Crowdfunding

Post by bleber »

Some random idea To increase responsiveness of point in curve, you can divide spline in small know steps and move over the steps wen move the point over the line, and when Slow move calculate position invetween steps.
User avatar
jnxd
Posts: 951
Joined: Mon Mar 30, 2015 2:30 pm
Contact:

Re: B-Spline Constraints: Looking for Crowdfunding

Post by jnxd »

bleber wrote: Tue Oct 04, 2022 8:11 pm Some random idea To increase responsiveness of point in curve, you can divide spline in small know steps and move over the steps wen move the point over the line, and when Slow move calculate position invetween steps.
Thanks for the consideration. Thing is, this should ideally be handled already within the solver, with adaptive steps taken, etc. But maybe it'll need to be done manually.
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: Looking for Crowdfunding

Post by jnxd »

CODING UPDATE 8 OCTOBER 2022

As I mentioned in the funding update on Tuesday, I now have a setup ready for the point-on-B-spline constraint. You can try these out by building from the branch or by getting the snap. The previous knot constraints are also included.

[EDIT: Also note that for a multi-piece B-spline the point lies on an extrapolation of the original piece while dragging. This should immediately snap back to the other segment upon release]

As I had mentioned, the results are horrible.

phpBB [video]
typical-sketch-with-pointonbspline.FCStd
Typical Sketch with Point-on-BSpline contraint. Note that dragging any object around is extremely jittery, but the constraint is still satisfied.
(4.7 KiB) Downloaded 26 times
As you can see, the constraint works, but performance is extremely bad. And I think I have an idea why, but trying to fix it will need working directly with the solver rather than just the constraints. This will get technical too fast, but the tl;dr is that I'm using a non-dimensional parametric variable with dimensioned "regular" variables that usually go into constraints. When the dimensions are in the 10 mm range (or the default length unit) while the parameter still is within [0, 1], things work fine, things get wonky; but if we are working with 1 mm range, the solver has an easier time.

phpBB [video]
very-small-sketch.FCStd
Another Sketch with Point-on-BSpline contraint, but with dimensions smaller than 1mm. Note that dragging is no longer jittery.
(4.59 KiB) Downloaded 25 times
Let's first begin with some quick math behind constraints. Every point/curve in Sketcher can be represented by some variables, each of which adds a degree of freedom, e.g. a point with it's coordinates, a circle with the coordinates of it's center and it's radius. Let's call them x = [x_0, x_1, x_2,...]. Every constraint then is a relation (or set of relations) between these points. For example, a coincident constraint between two points (x_1, x_2) and (x_3, x_4) can be given by
f_1(x) = x_3 - x_1 = 0 and f_2(x) = x_4 - x_2 = 0.
We describe them in this way so that we can make a vector equation in the form (remember x is itself a vector)
f(x) = [f_0(x), f_1(x), ...] = 0.
This is the equation we solve in the solver. And to do this, we start with an initial guess, and iteratively change variables (the x_i's) little by little to get as close to the solution as possible. The exact details can be found in @abdullah's document.

[EDIT: Note that the issue is now resolved and was because of an error in gradient calculation. The following is kept just for the record]
Now, let's get to our point-on-B-spline constraint. This constraint is described by (for a non-rational B-spline)
q - (B_0(u)*p_0 + B_1(u)*p_1 + ...) = 0
where q is a coordinate of the constraint point (x or y), p_i are the corresponding (x or y) coordinates of the poles, B_i are the basis functions (these are the B in B-splines; they also depend on degree and knot vector, but we leave it aside for now), and finally u is a parameter that goes from 0 to 1 along the B-spline. Then, the variables are [q, p_0, p_1,..., u]. Now, for a typical sketch, the coordinates would be in, say, 10-100 unit range, or if not, they're free to move as far as they want. But however large or small the coordinates are, u will always stay within 0-1 (no units). This is (probably) what causes the issue: the solver is currently designed assuming all the variables are lengths. So when lengths are way larger that that 0-1 range, the solver tries to make u also jump around like anything, and doesn't converge (ideally with every iteration it should be able to take smaller and smaller steps to get closer and closer to a solution).

So this is where my thought process ends right now. I'm trying out a few things within describing the constraint itself, but I guess eventually I'll have to dig in to the solver code itself. This might also solve the issue with weights in the process, but I can't be sure of that yet.
Last edited by jnxd on Wed Oct 12, 2022 2:37 pm, edited 2 times in total.
My latest (or last) project: B-spline Construction Project.
User avatar
adrianinsaval
Veteran
Posts: 5541
Joined: Thu Apr 05, 2018 5:15 pm

Re: B-Spline Constraints: Looking for Crowdfunding

Post by adrianinsaval »

Impressive work! How well does it behave with fixed BSplines? I'll give it a test run tonight
User avatar
jnxd
Posts: 951
Joined: Mon Mar 30, 2015 2:30 pm
Contact:

Re: B-Spline Constraints: Looking for Crowdfunding

Post by jnxd »

adrianinsaval wrote: Sat Oct 08, 2022 4:54 pm Impressive work! How well does it behave with fixed BSplines? I'll give it a test run tonight
If you mean a fully constrained B-spline, it works just as well with a non-fixed one: everything is smooth so long as the the scale is 1 unit (you can set the units to cm or m for larger sketches). You might be asking this because of the rational B-splines knot constraint case, and yes fixing the B-spline was the first thing I tried.
My latest (or last) project: B-spline Construction Project.
User avatar
adrianinsaval
Veteran
Posts: 5541
Joined: Thu Apr 05, 2018 5:15 pm

Re: B-Spline Constraints: Looking for Crowdfunding

Post by adrianinsaval »

knot coincidence and tangency seems to work fine, if I were in charge I would merge that part.
Regarding tangency on knot, is it possible to have it work also like "endpoint tangency" constraint? That is select the enpoint of an edge and a bspline knot and make them tangent and coincident at that point at the same time?
Also, I can't really think of an usecase right now, but is it possible to set bsplines tangent to each other?
Point on bspline isn't very useful in the current state, guess you'll have to get into solver stuff if you want to finish that implementation.
User avatar
jnxd
Posts: 951
Joined: Mon Mar 30, 2015 2:30 pm
Contact:

Re: B-Spline Constraints: Looking for Crowdfunding

Post by jnxd »

Thanks for testing out @adrianinsaval!
adrianinsaval wrote: Sun Oct 09, 2022 2:24 pm Regarding tangency on knot, is it possible to have it work also like "endpoint tangency" constraint? That is select the enpoint of an edge and a bspline knot and make them tangent and coincident at that point at the same time?
That sounds possible.
adrianinsaval wrote: Sun Oct 09, 2022 2:24 pm Also, I can't really think of an usecase right now, but is it possible to set bsplines tangent to each other?
What you can do is make them tangent to the same line segment and put a coincident constraint on the knots. Thing is I don't want to create the same constraint for different combinations, if this trick can work. Maybe once the tangency is reviewed and merged I'll make those constraints incorporating the reviews.
adrianinsaval wrote: Sun Oct 09, 2022 2:24 pm Point on bspline isn't very useful in the current state, guess you'll have to get into solver stuff if you want to finish that implementation.
Indeed.
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: Looking for Crowdfunding

Post by jnxd »

BTW, I created a PR thread for the knot position constraint: https://forum.freecadweb.org/viewtopic.php?f=17&t=72288.
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: Looking for Crowdfunding

Post by jnxd »

adrianinsaval wrote: Sun Oct 09, 2022 2:24 pm Point on bspline isn't very useful in the current state, guess you'll have to get into solver stuff if you want to finish that implementation.
Just noticed a maxStep method that can be done within the (planegcs) constraint itself. Results are quite a bit better (which just means usable).

Could you try again? Just re-triggered the snap so if you're using this wait for it to build. [UPDATE: Snap is failing, apparently because of some linking issues affecting Techdraw. Source builds still appear to work on local machine.][UPDATE 2: Snap is working now]
Last edited by jnxd on Tue Oct 11, 2022 11:23 am, edited 2 times in total.
My latest (or last) project: B-spline Construction Project.
User avatar
adrianinsaval
Veteran
Posts: 5541
Joined: Thu Apr 05, 2018 5:15 pm

Re: B-Spline Constraints: Looking for Crowdfunding

Post by adrianinsaval »

I'll give it a spin tonight
Post Reply