Sketcher: B-Spline pages

[uwestoehr]

It seems OCC uses the De Boor's algorithm:
https://en.wikipedia.org/wiki/De_Boor's_algorithm

This is cool recursive one that does not explicitly deliver the polynomial function, see the second sentence here: https://en.wikipedia.org/wiki/De_Boor's ... _algorithm

Of course still want to know what polynomials the basis are -> I'll ask my math friend about this tomorrow.

[jnxd]

Reading in literature I have not yet found another polynom type with this feature. It might exist, but I only read about Bernstein polynomials.

Could you share your sources?

There are some examples of how the pieces look. You will see that they don't necessarily look like Bernstein polynomials.

Besides, I should point out that the point of B-splines is using splines directly as basis. So we should move on from polynomials by the time we reach there.

[uwestoehr]

Of course still want to know what polynomials the basis are -> I'll ask my math friend about this tomorrow.

No need since the definition:
https://en.wikipedia.org/wiki/B-spline#Definition

gives us the formula. For example a quadratic basis for the interval 0,1 is (if the further intervals are [1,2] and [2,3])
1/2 * (-x(x-2))-(x-1)(x-3)

This is following the scheme of Bernstein polynomials but differ. The value 3 in this formula cannot be explained by the interval setting (moving and stretching the polynomials to different intervals) and is a consequence of the recursion taking into account the 2 following intervals.

-> I was wrong. The basis functions are no Bernstein polynomial.

Here they calculated some basis functions: https://pages.mtu.edu/~shene/COURSES/cs ... basis.html

Interesting stuff but harder to get than I thought. I will fix the Wiki page accordingly . i will also remove the Bernstein polynomial image because this would only be misleading since the page if for B-splines.

[uwestoehr]

OK, there is something I still don't understand. I read several times that B-splines can have in principal any basis functions. However when googling for "B-spline" definition I find only the spline construction using the de Boor's algorithm. But then the basis functions are well defined and cannot be chosen.

So right now it appears for me that only the defined set of basis functions form a B-spline and using another basis is then no "B-Spline" but just a spline.

-------------
Allow me please to thank your for your persistence. I was wrong here and it is good that you did not give up but helped me to get it right.

[jnxd]

-> I was wrong. The basis functions are no Bernstein polynomial.

Here they calculated some basis functions: https://pages.mtu.edu/~shene/COURSES/cs ... basis.html

Interesting stuff but harder to get than I thought. I will fix the Wiki page accordingly . i will also remove the Bernstein polynomial image because this would only be misleading since the page if for B-splines.

I'm glad to see you're finally convinced! Could you point to where in the lecture notes you finally got the idea? I'm pretty sure I must have come across these notes as well and I probably didn't catch it at that time.

And indeed this is some very involved stuff, since it needs people to follow some strict math as well as understand phtsical significance at the same time! While working on them within FreeCAD I had so many of my assumptions beaten down (I used to think knots don't matter, or they are just the centers of gravity of relevant control points etc.).

OK, there is something I still don't understand. I read several times that B-splines can have in principal any basis functions. However when googling for "B-spline" definition I find only the spline construction using the de Boor's algorithm. But then the basis functions are well defined and cannot be chosen.

So right now it appears for me that only the defined set of basis functions form a B-spline and using another basis is then no "B-Spline" but just a spline.

If you go back to linear algebra you can notice that splines of given degree over certain knots form a vector space. And any vector space can have an infinite set of bases. The reason other bases are not shown might be that this is the only one found to have a good use case.

I suspect other representations of splines (like Hermite splines) also have some kind of linear algebra attached to them, but they evolved differently (through their physical significance), so their bases are not considered B-splines. I could be wrong here, though and other representation of splines might involve some sort of nonlinearity or the other.

[uwestoehr]

I'm glad to see you're finally convinced! Could you point to where in the lecture notes you finally got the idea?

I got it this way:
- asked you how FC does it, you referred to OCC, I googled this, then came across the De Boor's algorithm
- I used my CAS program (which is still the old MuPAD but that is sufficient) and programmed the recursion. I plotted the results to check if I did it right
- then I still had no formula to compare if my results are still the results of squeezed and moved Bernsteins. First then I googled again and found the page I linked where they calculate some of the polynomials and the same time I realized that this was all the time already there - in the Wikipedia page about B-splines is the definition

If you go back to linear algebra you can notice that splines of given degree over certain knots form a vector space. And any vector space can have an infinite set of bases. The reason other bases are not shown might be that this is the only one found to have a good use case.

But who "defined" the B-splines? Meaning in a good lecture there should be a derivation why this particular base is used. In the video lecture I linked in our Wiki page they only say that the basis must have the same properties than the Béziers and that the B-spline is a composition of Béziers. If this is the "definition" it implies that only one basis makes sense for B-spline.
This definition is sensible but either a note that B-splines can have any basis or that, if a spline has not this basis it is not the "defined" B-spline would have been useful in the lecture.

However, since we have it, we can start the dedicated math Wiki page and introduce there the knot vector concept since this is important to get the full picture as user.

[jnxd]

I got it this way:
- asked you how FC does it, you referred to OCC, I googled this, then came across the De Boor's algorithm
- I used my CAS program (which is still the old MuPAD but that is sufficient) and programmed the recursion. I plotted the results to check if I did it right
- then I still had no formula to compare if my results are still the results of squeezed and moved Bernsteins. First then I googled again and found the page I linked where they calculate some of the polynomials and the same time I realized that this was all the time already there - in the Wikipedia page about B-splines is the definition

Need to learn what's CAS and MuPAD now. As it happened the algorithm I mentioned when you asked for the formula was also de Boor Algorithm.

But who "defined" the B-splines?

De Boor did. Might be worth finding a copy of his original book where this basis comes into picture.

Meaning in a good lecture there should be a derivation why this particular base is used. In the video lecture I linked in our Wiki page they only say that the basis must have the same properties than the Béziers and that the B-spline is a composition of Béziers. If this is the "definition" it implies that only one basis makes sense for B-spline.
This definition is sensible but either a note that B-splines can have any basis or that, if a spline has not this basis it is not the "defined" B-spline would have been useful in the lecture.

You ask a good question but ultimately I believe it is a more scientific question rather than an engineering one.

I think there are a couple salient features:
1. The basis splines are always non-negative. This might be arriving from the fact that they should be non-zero within the support. This is also similar to the Bernstein polynomials' property of being non-negative within their range.
2. The factors of the basis splines have a nice physical significance, and use the absolute minimum number of points to represent the spline. I'll probably have more information about this once I start adding other kinds of splines.

Perhaps if we rummage through google scholar looking for "basis of splines ~B-splines" or "alternative bases of splines" we could get something.

However, since we have it, we can start the dedicated math Wiki page and introduce there the knot vector concept since this is important to get the full picture as user.

We can surely do that, though I believe we already have a "create b-splines" sketcher page and a "b-splines in freecad" section. So I don't know how deep we want to go. I'm open to your suggestions of how the new page should look. Feel free to split Bezier curves and B-splines: I plan to add Bezier curves in the near future.

[uwestoehr]

Need to learn what's CAS and MuPAD now.

No need:
https://en.wikipedia.org/wiki/Computer_algebra_system
and
https://en.wikipedia.org/wiki/MuPAD

A good free CAS is
https://en.wikipedia.org/wiki/Maxima_(software)

I also tried out
https://en.wikipedia.org/wiki/SageMath
but this is a huge software and for my daily work often slower than Maxima (on Windows).

We can surely do that, though I believe we already have a "create b-splines" sketcher page and a "b-splines in freecad" section. So I don't know how deep we want to go. I'm open to your suggestions of how the new page should look. Feel free to split Bezier curves and B-splines: I plan to add Bezier curves in the near future.

I am still reluctant. The page as it is should not go in too deep but knot vectors are important. So having this pert in the page might be helpful. Let me think about it further.
For everything else (how to have tangential lines to splines etc. please put this all in a new Wiki page. This Wiki page will then be linked for interested reader.

[jnxd]

https://en.wikipedia.org/wiki/Computer_algebra_system
and
https://en.wikipedia.org/wiki/MuPAD

A good free CAS is
https://en.wikipedia.org/wiki/Maxima_(software)

Silly me, I already knew about CAS but forgot. Maxima is good but I often only use wxMaxima and it's UI is a pain.

Did you try SymPy?

A good symbolic math tool is actually getting more and more important as the equations start egtting more and more complex. Bonus if they can convert it to C++ code

I am still reluctant. The page as it is should not go in too deep but knot vectors are important. So having this pert in the page might be helpful. Let me think about it further.
For everything else (how to have tangential lines to splines etc. please put this all in a new Wiki page. This Wiki page will then be linked for interested reader.

Reluctant for what exactly?

I'll write something about knots in the coming days.

We should also consider referring people to more robust literature for more involved stuff. I think this can include the tangents to splines etc. I already have posted in the project thread a document about the math that's implemented in the solver, but I don't think it belongs in the wiki.

[uwestoehr]

Did you try SymPy?

No. I need CAS to be productive, eaning i am just an average user who quickly needs nice looking results for presentations or reports.
Therefreo I still use MuPAD because I never found a more user-friendly UI yet. With this I can change plots by clicking around, no need to learn commands. The other CAS i tried require to learn commands to modify plots.

Reluctant for what exactly?

If the B-spline page should contain a section explaining knot vector. This would pump up the page.
But OK, let's add this.

However, please don't change the existing didactic order of the Wiki page that we can rely on the video lecture we link. I think the best place to add a new section after this section:
https://wiki.freecadweb.org/B-Splines#Basis
for the knot vector.
So the knot vector section would be section 3.1.2. This is a good place because directly below it we have the non-uniform splines and to understand this properly one needs to know the knot vector.

We should also consider referring people to more robust literature for more involved stuff. I think this can include the tangents to splines etc. I already have posted in the project thread a document about the math that's implemented in the solver, but I don't think it belongs in the wiki.

Yes, but all this please in the separate Wiki page.