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!
B-Spline Constraints: Fully Funded! Thanks everybody!
UPDATE: As of 11 November 2022, this is project is fully funded. The merging process is still ongoing. The funding links are still open for anyone still interested in funding my future work.
tl;dr: I have made some progress towards being able to constrain knot-points on a B-spline, which can be used as a kind of point-on-curve constraint until better tools can be arranged. I also have a roadmap for future work towards more B-spline constraints, and now I'm looking to fund this project. You can fund me on Github Sponsors [https://github.com/sponsors/AjinkyaDahale/] or Liberapay [https://liberapay.com/ajinkyadahale/].
Introduction
B-splines (and Bezier curves) are a powerful tool in CAD allowing the user to make complex, arbitrarily smooth shapes with ease. There has been significant development in support for B-splines in the Sketcher workbench of FreeCAD (mainly thanks to Abdullah). However, there is room for significant improvement: point-on-curve and tangency constraints are not yet supported for B-splines, which limits their functionality in Sketcher.
To this end, I have been able to make some progress. I am looking to raise some amount to further this work and can accept funding through Github Sponsors [https://github.com/sponsors/AjinkyaDahale/] and LiberaPay [https://liberapay.com/ajinkyadahale/]. If you're interested, your sponsorship will not only fund future development, but also offset the past few months I spent learning the intricacies of Sketcher and the theory of B-splines.
GOALS
$1000: Finish knot-constraint work (Stage 1).
$3000: Implement Bezier curves and attempt point on curve (Stage 2).
$5000: Undecided (depending on new knowledge I could implement point on curve on B-spline, or tangency constraint, or Bezier to B-spline inter-conversion), but this and any further amount will be helpful in more FreeCAD development.
Current Status:
Updated manually.
The stages are described in further details below.
Stage 0: What is already done
I have been able to make knot points to be able to behave as other points, in that they can be constrained like them. Effectively this will allow you to have a B-spline pass through certain points. The work can be seen on this branch: https://github.com/AjinkyaDahale/FreeCA ... rain-knots
As of the time of writing, knot-points on non-periodic non-rational B-Splines can be dragged around like "normal" vertices.
This was done by constraining the position of knot-points with respect to the B-spline poles within the planeGCS solver, as opposed to getting the positions through OCC. In principle, this should allow the ability to constrain knot points by themselves, in a way allowing for a (limited) "point on curve" constraint.
Stage 1
The first part of my project would be to complete the knot constraints. Some remaining aspects are described below.
There are some safeguards put in place for knots (like it is technically considered "fixed" similar to external geometries). This leads to some dimension constraints being treated as "non-driving" when applied on knots. This is now fixed
Additionally, some bugs need fixing for supporting periodic B-splines. This is now fixed
For rational B-splines, the constraints need to be modified somewhat, which is not particularly difficult but some design decisions need to be made. Rational B-splines are now supported
Stage 1 Duration: I am expecting all this to take about 3-4 weeks.
Stage 2
[NOTE: this section was updated following some feedback]
Once stage 1 is done, I plan to start working on supporting true point-on-curve constraints such that a point constrained to be on the B-spline is free to move along the B-spline.
It would be easier to start with Bezier curves. The primary difference between Bezier curves and B-splines is that B-splines are piecewise Bezier curves. This I expect will make making point on object constraints easier at least on Bezier curves, and thus parts of B-splines. [EDIT 6 October 2022: It appears now I can jump directly to B-splines and leave Bezier curves for a future project]
We can already make a Bezier curve by making a B-spline with only the two end knots. Thus, the point-on-curve constraint can be started initially by only supporting such B-splines. However, it may be worthwhile to actually implement Bezier curves as their own type supported in Sketcher (as is done in Draft). For example, this can allow the user to create curves through existing points rather than creating a B-spline and then constraining the knots.
Stage 2 Duration: The point-on-curve constraint itself will require finding an appropriate “error function” that can be easily computed for the constraint solver planeGCS. Implementing Bezier curves themselves sounds relatively straightforward, but a lot of changes will need to be done. I expect it to take at least 1-2 months.
Thank you for your consideration, regardless of your sponsoring decision. I also invite interested people to track this thread and the relevant PRs/branches. Please let me know if there are things I may be missing, or if there are any other features you would like to see implemented once the current plan is completed.
tl;dr: I have made some progress towards being able to constrain knot-points on a B-spline, which can be used as a kind of point-on-curve constraint until better tools can be arranged. I also have a roadmap for future work towards more B-spline constraints, and now I'm looking to fund this project. You can fund me on Github Sponsors [https://github.com/sponsors/AjinkyaDahale/] or Liberapay [https://liberapay.com/ajinkyadahale/].
Introduction
B-splines (and Bezier curves) are a powerful tool in CAD allowing the user to make complex, arbitrarily smooth shapes with ease. There has been significant development in support for B-splines in the Sketcher workbench of FreeCAD (mainly thanks to Abdullah). However, there is room for significant improvement: point-on-curve and tangency constraints are not yet supported for B-splines, which limits their functionality in Sketcher.
To this end, I have been able to make some progress. I am looking to raise some amount to further this work and can accept funding through Github Sponsors [https://github.com/sponsors/AjinkyaDahale/] and LiberaPay [https://liberapay.com/ajinkyadahale/]. If you're interested, your sponsorship will not only fund future development, but also offset the past few months I spent learning the intricacies of Sketcher and the theory of B-splines.
GOALS
$1000: Finish knot-constraint work (Stage 1).
$3000: Implement Bezier curves and attempt point on curve (Stage 2).
$5000: Undecided (depending on new knowledge I could implement point on curve on B-spline, or tangency constraint, or Bezier to B-spline inter-conversion), but this and any further amount will be helpful in more FreeCAD development.
Current Status:
Updated manually.
The stages are described in further details below.
Stage 0: What is already done
I have been able to make knot points to be able to behave as other points, in that they can be constrained like them. Effectively this will allow you to have a B-spline pass through certain points. The work can be seen on this branch: https://github.com/AjinkyaDahale/FreeCA ... rain-knots
As of the time of writing, knot-points on non-periodic non-rational B-Splines can be dragged around like "normal" vertices.
This was done by constraining the position of knot-points with respect to the B-spline poles within the planeGCS solver, as opposed to getting the positions through OCC. In principle, this should allow the ability to constrain knot points by themselves, in a way allowing for a (limited) "point on curve" constraint.
Stage 1
The first part of my project would be to complete the knot constraints. Some remaining aspects are described below.
There are some safeguards put in place for knots (like it is technically considered "fixed" similar to external geometries). This leads to some dimension constraints being treated as "non-driving" when applied on knots. This is now fixed
Additionally, some bugs need fixing for supporting periodic B-splines. This is now fixed
For rational B-splines, the constraints need to be modified somewhat, which is not particularly difficult but some design decisions need to be made. Rational B-splines are now supported
Stage 1 Duration: I am expecting all this to take about 3-4 weeks.
Stage 2
[NOTE: this section was updated following some feedback]
Once stage 1 is done, I plan to start working on supporting true point-on-curve constraints such that a point constrained to be on the B-spline is free to move along the B-spline.
It would be easier to start with Bezier curves. The primary difference between Bezier curves and B-splines is that B-splines are piecewise Bezier curves. This I expect will make making point on object constraints easier at least on Bezier curves, and thus parts of B-splines. [EDIT 6 October 2022: It appears now I can jump directly to B-splines and leave Bezier curves for a future project]
We can already make a Bezier curve by making a B-spline with only the two end knots. Thus, the point-on-curve constraint can be started initially by only supporting such B-splines. However, it may be worthwhile to actually implement Bezier curves as their own type supported in Sketcher (as is done in Draft). For example, this can allow the user to create curves through existing points rather than creating a B-spline and then constraining the knots.
Stage 2 Duration: The point-on-curve constraint itself will require finding an appropriate “error function” that can be easily computed for the constraint solver planeGCS. Implementing Bezier curves themselves sounds relatively straightforward, but a lot of changes will need to be done. I expect it to take at least 1-2 months.
Thank you for your consideration, regardless of your sponsoring decision. I also invite interested people to track this thread and the relevant PRs/branches. Please let me know if there are things I may be missing, or if there are any other features you would like to see implemented once the current plan is completed.
Last edited by jnxd on Fri Nov 11, 2022 7:10 pm, edited 44 times in total.
My latest (or last) project: B-spline Construction Project.
Re: B-Spline Constraints: Looking for Crowdfunding
Besides the concrete tasks, I appreciate your approach: You have an idea, it is too much to do it alone or for free, and you are asking for support.
Considerations on your approach: Beziers exist already in Draft workbench, and I guess they are already available in OCC. This may speed things up. On the other hand: Point-on-object can come in two flavours:
1) You take an existing immutable B-spline and put a point on it. That could be covered by your estimations. I would rate this already as a leap forward!
2) If it should also work the other way round, that you have a given set of constraints and the B-spline is fully integrated in the solving of the sketch , meaning that it can be adapted to some points as well as vice versa (that's what works now e.g. for arcs), then I expect an enormous amount of work to feed this to the solver.
Considerations on your approach: Beziers exist already in Draft workbench, and I guess they are already available in OCC. This may speed things up. On the other hand: Point-on-object can come in two flavours:
1) You take an existing immutable B-spline and put a point on it. That could be covered by your estimations. I would rate this already as a leap forward!
2) If it should also work the other way round, that you have a given set of constraints and the B-spline is fully integrated in the solving of the sketch , meaning that it can be adapted to some points as well as vice versa (that's what works now e.g. for arcs), then I expect an enormous amount of work to feed this to the solver.
A Sketcher Lecture with in-depth information is available in English, auf Deutsch, en français, en español.
Re: B-Spline Constraints: Looking for Crowdfunding
I am indeed aware Bezier curves exist in OCC: https://dev.opencascade.org/doc/occt-7. ... curve.html. So the implementation will be similar to b-splines. However, that involves making all (or at least a lot of, for a minimal casr) the the app and gui and planeGCS infrastructure, ensuring whatever I actually do copy is relevant and remove or add things as necessary.
I imagine part (1) should be straightforward: this point would be similar to present-day knots, except instead of knot position we give a parameter where the point lies. It could also be possible to constrain this point similar to the knot constraint changes I am proposing. Was there something else you were thinking?On the other hand: Point-on-object can come in two flavours:
1) You take an existing immutable B-spline and put a point on it. That could be covered by your estimations. I would rate this already as a leap forward!
2) If it should also work the other way round, that you have a given set of constraints and the B-spline is fully integrated in the solving of the sketch , meaning that it can be adapted to some points as well as vice versa (that's what works now e.g. for arcs), then I expect an enormous amount of work to feed this to the solver.
Part (2) will need a bit of thought. To make a point otherwise unrelated to a curve lie on a curve there is an error function that needs to be created. For a line or conic, the expressions are at least closed form. For Bezier, I don't right now know the way, but looking deep into OCC's "closest point" implementation I already see Newton-Raphson iterations. There's also the fact that Bezier curves can self intersect, which may need it's own handling.
For B-spline there's that added complexity of which of the pieces concerns us, whether we want to allow to change it (remember a single b-spline can represent an entire polyline). I will possibly explain my ideas about this in details in another post.
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
Excellent initiative, which of the payment platforms do you prefer? I have not setup my card on either so I'll do whichever you prefer.
Also, perhaps we can use some of the bountysource money for this? What do others thing? (specially those who have contributed to it)
Also, perhaps we can use some of the bountysource money for this? What do others thing? (specially those who have contributed to it)
Re: B-Spline Constraints: Looking for Crowdfunding
What a pity, so you considered this already .
NoI imagine part (1) should be straightforward: this point would be similar to present-day knots, except instead of knot position we give a parameter where the point lies. It could also be possible to constrain this point similar to the knot constraint changes I am proposing. Was there something else you were thinking?
I like Beziers which I know from Inkscape, but I haven't seen any request for years to add them to the Sketcher. If implementing them would be additional work I would like to see it postponed after B-spline is finished. If they are needed for the solution of the B-spline issues, it is, of course, a different game.For Bezier, I don't right now know the way, but looking deep into OCC's "closest point" implementation I already see Newton-Raphson iterations.
A Sketcher Lecture with in-depth information is available in English, auf Deutsch, en français, en español.
Re: B-Spline Constraints: Looking for Crowdfunding
It is more that I do not know. I do keep digging into google scholar and other sources every now and then to try finding something relevant, so I might end up with a solution much faster. Or it could end up becoming new research in itself.
My idea with Bezier curves is that they have a simpler form, so their solution should in principle be simpler. Unfortunately simplifying things sometimes means taking a longer route. It may be possible to reach a proof of concept with b-splines themselves and just ensuring there are only two knots, but I'd imagine having bezier curves themselves has their own advantage.
To that last point I would really like some input from people who themselves use B-splines on a regular basis. How often do you need to actually know some math behind it? How often is there just some buttons you press without thinking what happens behind the curtain? What are you trying to achieve at those times?
My latest (or last) project: B-spline Construction Project.
Re: B-Spline Constraints: Looking for Crowdfunding
Thanks for asking. Liberapay has to use PayPal in the backend for my case, which in turn takes a rather big cut. Github claims to pass 100% of payments from individuals, but this is the first time I'm setting it up so I don't know if a hurdle comes up.adrianinsaval wrote: ↑Tue Aug 16, 2022 5:53 pm Excellent initiative, which of the payment platforms do you prefer? I have not setup my card on either so I'll do whichever you prefer.
Also, perhaps we can use some of the bountysource money for this? What do others thing? (specially those who have contributed to it)
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
Done, you have my grain of sand (or actually 10 USD), hopefully others will follow.
Re: B-Spline Constraints: Looking for Crowdfunding
BSpline and Bezier are somewhat similar, you could think of Bezier curve as subset if BSPlines, BSpline segments could be thought as Bezier curves, sadly I'm on mobile, but I have a link of a University course about CG that explain many of the maths.
Maybe tomorrow I will find and post here the link.
EDIT:
https://pages.mtu.edu/~shene/COURSES/cs3621/NOTES/
Some terminology may be different from those used by FC, but it has not to be too distant.
END EDIT
Regards
Carlo D.
Maybe tomorrow I will find and post here the link.
EDIT:
https://pages.mtu.edu/~shene/COURSES/cs3621/NOTES/
Some terminology may be different from those used by FC, but it has not to be too distant.
END EDIT
Regards
Carlo D.
GitHub page: https://github.com/onekk/freecad-doc.
- In deep articles on FreeCAD.
- Learning how to model with scripting.
- Various other stuffs.
Blog: https://okkmkblog.wordpress.com/
- In deep articles on FreeCAD.
- Learning how to model with scripting.
- Various other stuffs.
Blog: https://okkmkblog.wordpress.com/
Re: B-Spline Constraints: Looking for Crowdfunding
Thanks, Carlo! I am indeed aware that Bezier curves can be considered as special cases of B-splines, and have mentioned it in the OP and some replies (perhaps ambiguously ). My point is that working with this special case can be a good step towards full B-spline constraint support.onekk wrote: ↑Tue Aug 16, 2022 9:50 pm BSpline and Bezier are somewhat similar, you could think of Bezier curve as subset if BSPlines, BSpline segments could be thought as Bezier curves, sadly I'm on mobile, but I have a link of a University course about CG that explain many of the maths.
Maybe tomorrow I will find and post here the link.
EDIT:
https://pages.mtu.edu/~shene/COURSES/cs3621/NOTES/
Some terminology may be different from those used by FC, but it has not to be too distant.
END EDIT
Regards
Carlo D.
I plan to elaborate on the details at some point in the future once I am nearing completion of "stage 1".
My latest (or last) project: B-spline Construction Project.