Sketcher: B-Spline pages

Discussions about the wiki documentation of FreeCAD and its translation.
Forum rules
Be nice to others! Respect the FreeCAD code of conduct!
edwilliams16
Veteran
Posts: 3117
Joined: Thu Sep 24, 2020 10:31 pm
Location: Hawaii
Contact:

Re: Sketcher: B-Spline pages

Post by edwilliams16 »

@jnxd
Since you are referencing youtube videos, I think this prize-winning video https://www.youtube.com/watch?v=aVwxzDHniEw on Bezier Curves by Freya Holmer is excellent.
User avatar
jnxd
Posts: 951
Joined: Mon Mar 30, 2015 2:30 pm
Contact:

Re: Sketcher: B-Spline pages

Post by jnxd »

edwilliams16 wrote: Wed Oct 19, 2022 11:47 pm @jnxd
Since you are referencing youtube videos, I think this prize-winning video https://www.youtube.com/watch?v=aVwxzDHniEw on Bezier Curves by Freya Holmer is excellent.
I have indeed watched it, but I was waiting for her video on B-splines to come out.
My latest (or last) project: B-spline Construction Project.
edwilliams16
Veteran
Posts: 3117
Joined: Thu Sep 24, 2020 10:31 pm
Location: Hawaii
Contact:

Re: Sketcher: B-Spline pages

Post by edwilliams16 »

jnxd wrote: Thu Oct 20, 2022 5:41 am I have indeed watched it, but I was waiting for her video on B-splines to come out.
She's working on one? Could be great.
User avatar
jnxd
Posts: 951
Joined: Mon Mar 30, 2015 2:30 pm
Contact:

Re: Sketcher: B-Spline pages

Post by jnxd »

uwestoehr wrote: Mon Oct 17, 2022 7:48 pm let's do it this way:
- you change the Wiki page directly as you think it is correct. You invested now many hours and I am sure you became a master. Therefore just put it in.
- the Wiki has a the nice timeline feature, so I can ask my math Ph.D. friend to look at both versions and judge (however he is getting a father soon, so I don't know if he will have time)
OK I changed as far as I had prepared. Some parts are left lazily as "TODO" or "WIP" :oops:, but the overall scheme your friend can take a look.
My latest (or last) project: B-spline Construction Project.
User avatar
uwestoehr
Veteran
Posts: 4961
Joined: Sun Jan 27, 2019 3:21 am
Location: Germany
Contact:

Re: Sketcher: B-Spline pages

Post by uwestoehr »

jnxd wrote: Fri Oct 21, 2022 12:59 pm OK I changed as far as I had prepared. Some parts are left lazily as "TODO" or "WIP" :oops:, but the overall scheme your friend can take a look.
Thanks.

I had a look and have several questions and issues:

- what precisely was not correct? I want to know my mistakes and learn ;)

- My aim was not to go too much into details. Especially not for Beziers since the Wiki page is about B-splines and this is what users of FreeCAD will use. Therefore in section https://wiki.freecadweb.org/index.php?t ... 01181#Math I kept math short and linked a video for those who want to know more.
Now you added a new section https://wiki.freecadweb.org/index.php?t ... 1181#Basis but in the Math section it was already stated that a Bezier is a linear combination of polynomials and that P_i are the coordinates. So to keep the Bezier section short, I would rather omit this new section and instead reference in the B-splines section that Beziers consists if polynoms. Since a combination of Beziers form a spline, we can treat these polynoms the creating base of splines and so on. So I would bring this after the main introduction of the idea of splines, their benefits and rules.

- the concept of the page was to first describe Bezier curves, then derive B-splines from them. In the B-splines section that you can use the approach of the knot vector, but I would not mix this up. Both approaches are correct and lead to B-splines of course. Important for me is that newbies can follow and understand. In my experience the step from Bezier to B-splines is easier than the more abstract knot vector. Therefore I would leave the Bezier approach and present the knot vector approach as alternative way. (So like quantum mechanics can be derived either via Matrix mechanics or Wave mechanics (Schrödinger equation). The latter is easier to understand for newbies therefore this is usually taught first.)

- There is however one sentence I don't understand:
"An alternative way to look at splines is to describe them with bases of their own. These splines are called B-splines."
Mathematically this is not correct. Furthermore, in principle you can use another base than Bernstein polynoms. This is then still a B-spline but we won't have the nice features of Beziers. But in the B-spline introduction I made clear what properties we need and in the examples it will become even more clear what this means in practice. But this is too much info because, see next point:

- in general: I once sat long time to create the page thinking about the right amount of info. There are special cases which you already noted in your ToDo. I purposley omitted them because the objective is not a proper math lecture but a FreeCAD lecture :) . If you like to have these special cases covered, I therefore propose that you create a dedicated Wiki page with the math in detail. Then link this new Wiki page.

- Your ToDo and WIP (what means WIP by the way?) should not appear in the Wiki page since readers will be confused page was marked being ready long ago, (therefore it should be kept in a ready state). Can you write them out for you and then remove them from the page please? Whenever you resolved a Todo, change the Wiki page or add this to the new dedicated math Wiki page.
User avatar
uwestoehr
Veteran
Posts: 4961
Joined: Sun Jan 27, 2019 3:21 am
Location: Germany
Contact:

Re: Sketcher: B-Spline pages

Post by uwestoehr »

uwestoehr wrote: Sat Oct 22, 2022 1:27 am - what precisely was not correct? I want to know my mistakes and learn ;)
I got it now: I described the uniformity wrong. Rational splines are not automatically non-uniform. It took me a long while to understand this and I am sorry I did not earlier get your point.

I took now some time to rework the whole explanation:
https://wiki.freecadweb.org/B-Splines#B-Splines
Can you please have a look if this is now better understandable and correct?

While revising, I noticed was already too deep into math and therefore kicked out some details and formulas and refer instead the videos.

However for your B-spline project you might like more math and handle special cases. As I wrote, the best would be a dedicated new Wiki page. This way we can please 3 different kind of users:
- beginners
- experienced users who use splines but like to know some background
- experts

I think the concept of the knot vector is necessary to understand the knots in FC's splines support. So this is a missing piece of the page.

While reworking I removed your TODOs but you see them via the history function:
https://wiki.freecadweb.org/index.php?t ... on=history
User avatar
jnxd
Posts: 951
Joined: Mon Mar 30, 2015 2:30 pm
Contact:

Re: Sketcher: B-Spline pages

Post by jnxd »

uwestoehr wrote: Sat Oct 22, 2022 1:27 am - My aim was not to go too much into details. Especially not for Beziers since the Wiki page is about B-splines and this is what users of FreeCAD will use. Therefore in section https://wiki.freecadweb.org/index.php?t ... 01181#Math I kept math short and linked a video for those who want to know more.
Now you added a new section https://wiki.freecadweb.org/index.php?t ... 1181#Basis but in the Math section it was already stated that a Bezier is a linear combination of polynomials and that P_i are the coordinates. So to keep the Bezier section short, I would rather omit this new section and instead reference in the B-splines section that Beziers consists if polynoms. Since a combination of Beziers form a spline, we can treat these polynoms the creating base of splines and so on. So I would bring this after the main introduction of the idea of splines, their benefits and rules.
My idea is to go this way:
1. Introduce what is a "basis" in a Bezier curve.
2. Introduce what is a "spline" first: a piecewise continuous function whose pieces are polynomials.
3. Introduce what is a "basis spline": one of several splines whose linear combination can be used to represent any spline function that respect a certain continuity.

Note that Bernstein polynomials are not a basis for splines, only for Bezier curves.

My overarching goal is to decouple the concept of "spline" with the specific representation of splines using bases (the "B-splines"). This way, I intend to in the future introduce and implement an alternative approach for representing splines (one similar to inkscape). In the future, I intend for there to be an option to change the representation of splines as needed (so, for example, we immediately show splines as their individual Bezier pieces, which will simplify the tangency control and/or creation directly using knots).
uwestoehr wrote: Sat Oct 22, 2022 1:27 am - the concept of the page was to first describe Bezier curves, then derive B-splines from them. In the B-splines section that you can use the approach of the knot vector, but I would not mix this up. Both approaches are correct and lead to B-splines of course. Important for me is that newbies can follow and understand. In my experience the step from Bezier to B-splines is easier than the more abstract knot vector. Therefore I would leave the Bezier approach and present the knot vector approach as alternative way. (So like quantum mechanics can be derived either via Matrix mechanics or Wave mechanics (Schrödinger equation). The latter is easier to understand for newbies therefore this is usually taught first.)
Bezier curves are indeed easier (or more accurately, necessary) to understand, but in my mind the concept of basis is also easier to understand through them. A user can easily see that {1, x, x^2, x^3} can be used to create any general polynomial function (I acknowledge I didn't mention this). From there, ease the user into accepting that a Bernstein polynomial basis can also do the same, but has certain useful properties like the convex hull property. From there, introduce the idea that a piecewise polynomial can also be created by a linear combination of certain other bases.
uwestoehr wrote: Sat Oct 22, 2022 1:27 am - There is however one sentence I don't understand:
"An alternative way to look at splines is to describe them with bases of their own. These splines are called B-splines."
Mathematically this is not correct. Furthermore, in principle you can use another base than Bernstein polynoms. This is then still a B-spline but we won't have the nice features of Beziers. But in the B-spline introduction I made clear what properties we need and in the examples it will become even more clear what this means in practice. But this is too much info because, see next point:
As I mentioned earlier, Bernstein polynomials are not a basis for splines, only for Bezier curves (see my earlier post explaining where Bernstein polynomials fit into the idea of splines). Think of it this way: a Bernstein polynomial is by definition infinitely continuous within it's domain, so a linear combination of them will also be infinitely continuous, but splines are by definition intended to have discontinuity at their knot points.
uwestoehr wrote: Sat Oct 22, 2022 1:27 am - in general: I once sat long time to create the page thinking about the right amount of info. There are special cases which you already noted in your ToDo. I purposley omitted them because the objective is not a proper math lecture but a FreeCAD lecture :) . If you like to have these special cases covered, I therefore propose that you create a dedicated Wiki page with the math in detail. Then link this new Wiki page.
As such, this page is already one level deep from https://wiki.freecadweb.org/Sketcher_CreateBSpline, so I don't know how deep we want to go from there. I wonder if we should go as deep into the math as making yet another level page. As such the most appropriate thing would be to direct people to textbooks and lecture notes. However, I'm trying to put in a minimum level of math, which I guess is still a lot.

As for the special cases, I think the idea can be shown from knot vectors:
1. Introduce knot vectors with each having single multiplicity (including end points).
2. Let the user know that some knots can be equal.
3. Finally tell the special cases that are needed in FreeCAD (non-periodic splines have end knots of n+1 multiplicity, and periodic splines have knots in a way that ensures periodicity).
uwestoehr wrote: Sat Oct 22, 2022 1:27 am - Your ToDo and WIP (what means WIP by the way?) should not appear in the Wiki page since readers will be confused page was marked being ready long ago, (therefore it should be kept in a ready state). Can you write them out for you and then remove them from the page please? Whenever you resolved a Todo, change the Wiki page or add this to the new dedicated math Wiki page.
WIP is work in progress. I think if needed it should be possible to change the state of the wiki page back to WIP/"under construction". I apologize for not keeping things complete, but as I already mentioned I chose to push through in the hopes that I will be pressured into completing them.
My latest (or last) project: B-spline Construction Project.
User avatar
jnxd
Posts: 951
Joined: Mon Mar 30, 2015 2:30 pm
Contact:

Re: Sketcher: B-Spline pages

Post by jnxd »

uwestoehr wrote: Sat Oct 22, 2022 4:42 am I got it now: I described the uniformity wrong. Rational splines are not automatically non-uniform. It took me a long while to understand this and I am sorry I did not earlier get your point.
Indeed rational and non-uniform are independent concepts. I had to start working on B-splines in FreeCAD to finally get it myself :lol:. However, one other piece you have been missing is that (Bernstein) polynomial basis and B-spline basis are different
uwestoehr wrote: Sat Oct 22, 2022 4:42 am I took now some time to rework the whole explanation:
https://wiki.freecadweb.org/B-Splines#B-Splines
Can you please have a look if this is now better understandable and correct?

While revising, I noticed was already too deep into math and therefore kicked out some details and formulas and refer instead the videos.

However for your B-spline project you might like more math and handle special cases. As I wrote, the best would be a dedicated new Wiki page. This way we can please 3 different kind of users:
- beginners
- experienced users who use splines but like to know some background
- experts
I'll take a look, there will probably be a good few iterations. A certain amount of math is unfortunately unavoidable. We could have gotten away with hand-waving if, say, we had implemented Bezier curves and then a bunch of "n-th derivative continuous at end-point" constraints, but B-splines need at least the knowledge of "basis".

The current state of the B-spline project doesn't need math to be exposed to the user, that can stay within planegcs and any technical report out of this. In fact, in the future I intend to implement splines in the form of individual Bezier curves, so the idea of knot vector themselves becomes less necessary (can't guarantee this is how it will pan out, though; need to explore this further).

Let's see how this goes. This might need some workshopping since I tend to go too deep into math myself. However, one rule we absolutely must follow is to err on the side of correctness, not on the side of brevity. So it is better for a beginner to be thrown into the deep end of experts (with the express understanding that there is a lifeguard in the form of closing the book) than to let them swim wrongly and believe they are correct (and maybe in the future jump into deep oceans without a lifeguard, sorry the analogy is breaking down).
uwestoehr wrote: Sat Oct 22, 2022 4:42 am I think the concept of the knot vector is necessary to understand the knots in FC's splines support. So this is a missing piece of the page.
Indeed knot vectors need to be added. Nag me if I don't get it done by next week.
uwestoehr wrote: Sat Oct 22, 2022 4:42 am While reworking I removed your TODOs but you see them via the history function:
https://wiki.freecadweb.org/index.php?t ... on=history
Probably better to somehow demarcate that this information is missing or incomplete. That's the reason I replaced TODOs with WIP, so that the onus of completing appears on the writer not the reader.
My latest (or last) project: B-spline Construction Project.
User avatar
jnxd
Posts: 951
Joined: Mon Mar 30, 2015 2:30 pm
Contact:

Re: Sketcher: B-Spline pages

Post by jnxd »

uwestoehr wrote: Sat Oct 22, 2022 4:42 am I took now some time to rework the whole explanation:
https://wiki.freecadweb.org/B-Splines#B-Splines
Can you please have a look if this is now better understandable and correct?
I am taking a look at the changes you're making, and I can't help but see this as a recap of you reverting changes made by other contributors unilaterally. Forgive me if in the following text I come out a little irritable: it is as much a fault of my own not being able to pin-point where your thought process is wrong (or where it is different from what I'm trying to do). Forgive me also that I'm probably repeating some points I already made in the previous posts.

The particular change I'm talking about is this: https://wiki.freecadweb.org/index.php?t ... id=1201427. Admittedly this change was done by me unilaterally as well, but I hope you understand that this is coming after a good few months of study.

I had taken care to move all references of "Bernstein polynomials" to the "Bezier curves" section because that's what is happening: Bernstein polynomials are not a basis for (B-)splines. If you do not wish to write about the basis of Bezier curves, let us remove the mention of Bernstein polynomials as well. The reason I am so vehemently advocating for this is to avoid confusion: when the basis splines that form a basis for non-periodic splines are drawn without context, they look very similar to Bernstein polynomials.

For looking at B-spline basis without bothering about Bezier curves or Bernstein polynomials, see their definition on wikipedia: https://en.wikipedia.org/wiki/B-spline#Definition.

The key features of these basis functions are:
1. Each basis function is a spline in itself, i.e. they are polynomials (of given degree) only between consecutive knots, and have some continuity at the knots, which depend on the knot's multiplicity and degree of the spline. If you count multiple knots as separate, they have exactly C^(degree-1) continuity at each knot.
1.1. Note that this is true for the entire real number line (-infty, infty). A knot that has multiplicity (degree+1) results in a discontinuity, which makes the function jump from
2. Each basis function is non-zero only in a certain range i.e. between a given set of (degree + 2) knots (counting multiple knots as separate).
2.1. Remember that the continuity is still in effect. So at the limits, not just the value, but also slopes and higher derivatives upto continuity should become zero.
3. The integral of each basis function over (-infty, infty) is unity. This last property makes each of the functions unique.

Now, indeed this is significantly mathematical for a beginner, as was my own experience. It does seem like this is a drawback of B-splines that everything needs to be defined before it can be even remotely useful. I think at the very basics these ideas need to get across:
1. Splines can make arbitrary curves with arbitrary continuity, between arbitrary sets of points.
2. B-splines are a minimalist way of representing a given such curve. For splines represented as Bezier curves you need to give all the points and then constrain their control points for continuity. But with B-splines this is replaced by a single control point (or at least results in a reduction of control points).
My latest (or last) project: B-spline Construction Project.
User avatar
uwestoehr
Veteran
Posts: 4961
Joined: Sun Jan 27, 2019 3:21 am
Location: Germany
Contact:

Re: Sketcher: B-Spline pages

Post by uwestoehr »

Hi Ajinkija, just in short (I will carefully read you comments later):

- the Wiki page's target group are beginners which can skip the math details and interested users who get the basic insights.
- the Wiki page was already too deep into math for my taste, therefore it should not get more math
- A dedicated new Wiki page would be best in my opinion. There you can describe everything with all details. Therefore I ask you not to revise the existing Wiki page but focus on the new detail page.
- from the didactic point of view i purposely derived B-splines from Béziers as they do it in the linked videos because I want to link the videos. interested users can then watch the whole lecture if they are interested And since the Wiki's page didactic follow the lecture's didactic I think they can easily follow the lecture. Therefore I did not introduce the basis in the Bézier section of the Wiki page.

You write "Note that Bernstein polynomials are not a basis for splines, only for Bezier curves."
B-splines can have different basis but the one we use in FreeCAD use Bernstein polynomials. I hope I made this clear in section
https://wiki.freecadweb.org/B-Splines#Basis
The N(t) polynomials have the same structure as the Bézier polynomials.

But again, average users don't need to dive in too deeply. For them it is important how we do it in FreeCAD. And if I have not made a mistake we do it as I described it in https://wiki.freecadweb.org/B-Splines#Basis
Post Reply