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!
Post Reply
User avatar
jnxd
Posts: 951
Joined: Mon Mar 30, 2015 2:30 pm
Contact:

B-Spline Constraints: Fully Funded! Thanks everybody!

Post by jnxd »

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:
Image
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.

phpBB [video]

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

phpBB [video]

Additionally, some bugs need fixing for supporting periodic B-splines. This is now fixed
knot-constr-fail-for-periodic.png
knot-constr-fail-for-periodic.png (62.2 KiB) Viewed 693437 times
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

phpBB [video]

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.
chrisb
Veteran
Posts: 53920
Joined: Tue Mar 17, 2015 9:14 am

Re: B-Spline Constraints: Looking for Crowdfunding

Post by chrisb »

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.
A Sketcher Lecture with in-depth information is available in English, auf Deutsch, en français, en español.
User avatar
jnxd
Posts: 951
Joined: Mon Mar 30, 2015 2:30 pm
Contact:

Re: B-Spline Constraints: Looking for Crowdfunding

Post by jnxd »

chrisb wrote: Tue Aug 16, 2022 1:31 pm Beziers exist already in Draft workbench, and I guess they are already available in OCC. This may speed things up.
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.
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.
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?

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.
User avatar
adrianinsaval
Veteran
Posts: 5541
Joined: Thu Apr 05, 2018 5:15 pm

Re: B-Spline Constraints: Looking for Crowdfunding

Post by adrianinsaval »

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)
chrisb
Veteran
Posts: 53920
Joined: Tue Mar 17, 2015 9:14 am

Re: B-Spline Constraints: Looking for Crowdfunding

Post by chrisb »

jnxd wrote: Tue Aug 16, 2022 4:14 pm I am indeed aware Bezier curves exist
What a pity, so you considered this already :) .
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?
No
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.
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.
A Sketcher Lecture with in-depth information is available in English, auf Deutsch, en français, en español.
User avatar
jnxd
Posts: 951
Joined: Mon Mar 30, 2015 2:30 pm
Contact:

Re: B-Spline Constraints: Looking for Crowdfunding

Post by jnxd »

chrisb wrote: Tue Aug 16, 2022 6:08 pm 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.
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.
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: 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)
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.
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 »

Done, you have my grain of sand :) (or actually 10 USD), hopefully others will follow.
User avatar
onekk
Veteran
Posts: 6144
Joined: Sat Jan 17, 2015 7:48 am
Contact:

Re: B-Spline Constraints: Looking for Crowdfunding

Post by onekk »

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.
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/
User avatar
jnxd
Posts: 951
Joined: Mon Mar 30, 2015 2:30 pm
Contact:

Re: B-Spline Constraints: Looking for Crowdfunding

Post by jnxd »

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.
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 :oops:). My point is that working with this special case can be a good step towards full B-spline constraint support.

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.
Post Reply