Sketcher: B-Spline pages
Forum rules
Be nice to others! Respect the FreeCAD code of conduct!
Be nice to others! Respect the FreeCAD code of conduct!
Re: Sketcher: B-Spline pages
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.
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.
Re: Sketcher: B-Spline pages
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.
My latest (or last) project: B-spline Construction Project.
Re: Sketcher: B-Spline pages
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.
Re: Sketcher: B-Spline pages
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.
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.
Re: Sketcher: B-Spline pages
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.uwestoehr wrote: ↑Mon Oct 24, 2022 12:54 am -> 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.
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.).
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.uwestoehr wrote: ↑Mon Oct 24, 2022 1:07 am 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.
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.
My latest (or last) project: B-spline Construction Project.
Re: Sketcher: B-Spline pages
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
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.jnxd wrote: ↑Mon Oct 24, 2022 3:45 am 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.
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.
Re: Sketcher: B-Spline pages
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.uwestoehr wrote: ↑Mon Oct 24, 2022 12:32 pm 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
De Boor did. Might be worth finding a copy of his original book where this basis comes into picture.
You ask a good question but ultimately I believe it is a more scientific question rather than an engineering one.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.
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.
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.
My latest (or last) project: B-spline Construction Project.
Re: Sketcher: B-Spline pages
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).
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.jnxd wrote: ↑Mon Oct 24, 2022 1:24 pm 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.
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.
Re: Sketcher: B-Spline pages
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.uwestoehr wrote: ↑Mon Oct 24, 2022 1:59 pm 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)
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
Reluctant for what exactly?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.
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.
My latest (or last) project: B-spline Construction Project.
Re: Sketcher: B-Spline pages
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.
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.
Yes, but all this please in the separate Wiki page.jnxd wrote: ↑Mon Oct 24, 2022 2:48 pm 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.