B-Spline Constraints: Fully Funded! Thanks everybody!
Forum rules
Be nice to others! Respect the FreeCAD code of conduct!
Be nice to others! Respect the FreeCAD code of conduct!
Re: B-Spline Constraints: Looking for Crowdfunding
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.
Re: B-Spline Constraints: Looking for Crowdfunding
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.
Re: B-Spline Constraints: Looking for Crowdfunding
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.
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.
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.
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.
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.
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.
- adrianinsaval
- Veteran
- Posts: 5551
- Joined: Thu Apr 05, 2018 5:15 pm
Re: B-Spline Constraints: Looking for Crowdfunding
Impressive work! How well does it behave with fixed BSplines? I'll give it a test run tonight
Re: B-Spline Constraints: Looking for Crowdfunding
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.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
My latest (or last) project: B-spline Construction Project.
- adrianinsaval
- Veteran
- Posts: 5551
- Joined: Thu Apr 05, 2018 5:15 pm
Re: B-Spline Constraints: Looking for Crowdfunding
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.
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.
Re: B-Spline Constraints: Looking for Crowdfunding
Thanks for testing out @adrianinsaval!
That sounds possible.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?
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 Also, I can't really think of an usecase right now, but is it possible to set bsplines tangent to each other?
Indeed.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.
My latest (or last) project: B-spline Construction Project.
Re: B-Spline Constraints: Looking for Crowdfunding
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.
Re: B-Spline Constraints: Looking for Crowdfunding
Just noticed a maxStep method that can be done within the (planegcs) constraint itself. Results are quite a bit better (which just means usable).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.
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.
- adrianinsaval
- Veteran
- Posts: 5551
- Joined: Thu Apr 05, 2018 5:15 pm
Re: B-Spline Constraints: Looking for Crowdfunding
I'll give it a spin tonight