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!
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 2:37 pm Hi Ajinkija, just in short (I will carefully read you comments later):
Let's discuss further after you've had the chance to go through my comments. Talking before that will only lead to more confusion and repetition.
uwestoehr wrote: Sat Oct 22, 2022 2:37 pm - 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.
As I already mentioned in the comments, a good amount of math is unavoidable. I don't expect people to come reading the document immediately, so lets try to slowly move the math into the dedicated page rather than deleting key information outright.
uwestoehr wrote: Sat Oct 22, 2022 2:37 pm - 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.
I see. However, as I mentioned, it is IMHO best to remove the references to Bernstein polynomials altogether then.
uwestoehr wrote: Sat Oct 22, 2022 2:37 pm 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.
Your second sentence here "B-splines can have different basis but the one we use in FreeCAD use Bernstein polynomials" directly contradicts the claim I make "Bernstein polynomials are not a basis for splines, only for Bezier curves". Please understand the difference between "polynomial" and "piecewise polynomial". We can never represent a piecewise polynomial of degree "d" with a polynomial of the same degree (for example, work with d=1 to convince yourself of that). It is true that the pieces of N(t) between knots are individually polynomial, but N(t) by themselves are not polynomials. There may be similarities between the structures of how those individual pieces are computed using the control points of the B-spline, but going into that is actually going more into the math than just stating how N(t) should behave.
uwestoehr wrote: Sat Oct 22, 2022 2:37 pm 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
I totally agree we should be doing a better job at not requiring average users to dive deeper into these things. However, unfortunately you are making a mistake in that section, and I hope I am able to convey why. If it is still not clear, let's get back to this when your friend has had the chance to take a look at this.
My latest (or last) project: B-spline Construction Project.
User avatar
FBXL5
Posts: 979
Joined: Sat Aug 03, 2019 8:45 pm

Re: Sketcher: B-Spline pages

Post by FBXL5 »

uwestoehr wrote: Sat Oct 22, 2022 2:37 pm the Wiki page was already too deep into math for my taste
+1

I agree with some others that see the wiki pages mainly as command reference pages which should be kept quite short.

From a users point of view I'd like to have a short description of some geometric background on these pages, but the arithmetic part deserves an extra page.
I think spline tools are easy to use even without kowing the arithmetic background.
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 Jun 24, 2022 9:29 pm Thing is, it seems you're mixing up the concepts of "Bezier curves" and "B-Splines". Bernstein polynomials form the basis for Bezier curves only. When weights are applied, we get what is called a rational Bezier curve.
I think you make a mistake here. The polynomials of a B-spline that is formed out of e.g. 3 Bézier segments. We know it is not just a linear combination of the 3 polynomials defining the Béziers, but it is nevertheless a Bernstein polynomial -> the structure of the polynomial did not change.
As I wrote other basis functions would loose the properties the Bézier curves provide. So a B-spline with a basis does not consist of Bernstein polynomials is not that useful.

When you look at rational Bézier curve you see that there the b(t) functions are the Bernstein polynomials, see their definition: https://en.wikipedia.org/wiki/B%C3%A9zi ... erminology). The additional factor like the weight does not change this.
jnxd wrote: Fri Jun 24, 2022 9:29 pm In this case, the first curve spans a 0<=t<0.5, and the second spans 0.5<=t<=1.0. We define the functions to be zero outside of their respective ranges. Now, if we consider the pole at t = 0.5 to be the same for both curves, we have 7 poles, and this is equivalent to a cubic spline with a 3-multiplicity knot at t=0.5. However, if we want continuity at higher derivatives, we have to impose more restrictions on these poles. This effectively reduces the number of poles, since one new point dictates two other points at every derivative continuity imposed. I will not go into the details of how, but the lectures we have been discussing can shed some light on that.
But that does not prove the basis are no longer Bernstein polynomials. Let's look at a standard quadratic polynomial:
f(t) = A*x^2 + B*x + C

When you add a factor W (weight) to it you get:
f(t) = W*A*t^2 + W*B*t + W*C
this is still a quadratic polynomial:
f'(t) = A'*t^2 + B'*t + C'
Where A' = W*A

moving it to a different interval is easy:
f(t) = A'*(t-s)^2 + B'*(t-s) + C'
where s is the amount the curve is shifted to greater t values.
The result is nevertheless a quadratic polynomial.

I had again a look and I cannot see neither in the Wikipedia nor in the videos that the basis functions are no longer Bernstein polynomials. They are still in the form
b(t) = (n over i) * t^i *(1 - t)^(n - i)

Where do you see that this form is no longer there?

Edit: the B(t) function in https://en.wikipedia.org/wiki/B%C3%A9zi ... ier_curves is of course no longer a Bernstein polynomials, but the b(t) are still ones.
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 »

FBXL5 wrote: Sun Oct 23, 2022 1:18 pm I agree with some others that see the wiki pages mainly as command reference pages which should be kept quite short.
From a users point of view I'd like to have a short description of some geometric background on these pages, but the arithmetic part deserves an extra page.
Therefore let's keep the page as simple as it is and create a separate page we can pack full with math. In this page you can derive the spline concept as you have in mind since readers of this page already have the basic knowledge and you can directly dive in deeper.

While reading your posts, I came to the conclusion that the knot vector should probably better introduced in this special page because to understand this, more math is necessary but this would pump up the basic B-spline page we have.
When you agree to this special page, I think we found a solution that suits us.

The only difference I identify in our argumentation is that you say Berrnstein polynomials are not the basis of B-Spline. I just stated about this in my previous post as I understand the math.
Important is hereby how FreeCAD does it. So what is the structure of the basis polynomials for FreeCAD's B-splines?
@abdullah can help us here please?
User avatar
jnxd
Posts: 951
Joined: Mon Mar 30, 2015 2:30 pm
Contact:

Re: Sketcher: B-Spline pages

Post by jnxd »

uwestoehr wrote: Sun Oct 23, 2022 7:39 pm I think you make a mistake here. The polynomials of a B-spline that is formed out of e.g. 3 Bézier segments. We know it is not just a linear combination of the 3 polynomials defining the Béziers, but it is nevertheless a Bernstein polynomial -> the structure of the polynomial did not change.
As I wrote other basis functions would loose the properties the Bézier curves provide. So a B-spline with a basis does not consist of Bernstein polynomials is not that useful.
Note that any basis of a spline will have to defined and follow the rules in all the segments, not just one. A Bernstein polynomial does work for a single segment, but this basis is discontinuous at the end-points. Additionally, basis splines do provide the nice properties (viz. convex hull) that Bezier curves provide, in fact in a stricter sense.
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: Sun Oct 23, 2022 8:43 pm Additionally, basis splines do provide the nice properties (viz. convex hull) that Bezier curves provide, in fact in a stricter sense.
Can you please give me the math formula of the B-spline basis functions used by FreeCAD? Then we know kind of polynomials we have.
User avatar
jnxd
Posts: 951
Joined: Mon Mar 30, 2015 2:30 pm
Contact:

Re: Sketcher: B-Spline pages

Post by jnxd »

uwestoehr wrote: Sun Oct 23, 2022 8:49 pm
jnxd wrote: Sun Oct 23, 2022 8:43 pm Additionally, basis splines do provide the nice properties (viz. convex hull) that Bezier curves provide, in fact in a stricter sense.
Can you please give me the math formula of the B-spline basis functions used by FreeCAD? Then we know kind of polynomials we have.
Not formula but algorithm: https://en.m.wikipedia.org/wiki/De_Boor%27s_algorithm. The definition itself can be found in the "definition" section here: https://en.m.wikipedia.org/wiki/B-spline.
I once again reiterate that we do not have polynomials, but piecewise polynomials.
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: Sun Oct 23, 2022 9:37 pm Not formula but algorithm:...
I once again reiterate that we do not have polynomials, but piecewise polynomials.
Why can't you give me the formula? Don't we have them in our code? if so what third-party library is used?

Sure the polynomials are piecewise, nevertheless they are still Bernstein polynomials. Or what kind of polynomials are they if not Bernstein polynomials?
User avatar
jnxd
Posts: 951
Joined: Mon Mar 30, 2015 2:30 pm
Contact:

Re: Sketcher: B-Spline pages

Post by jnxd »

uwestoehr wrote: Sun Oct 23, 2022 10:03 pm
jnxd wrote: Sun Oct 23, 2022 9:37 pm Not formula but algorithm:...
I once again reiterate that we do not have polynomials, but piecewise polynomials.
Why can't you give me the formula? Don't we have them in our code? if so what third-party library is used?

Sure the polynomials are piecewise, nevertheless they are still Bernstein polynomials. Or what kind of polynomials are they if not Bernstein polynomials?
The formula itself will be "this polynomial between t1 and t2, this other polynomial between t2 and t3...". It is faster and more stable to compute them using the algorithm I mentioned. In the current master all B-spline values are obtained from OCCT. In the new features I implemented it myself in GCS::BSpline::ValueAt.

The phrase "polynomials are piecewise" is wrong. If it is piecewise defined, the function cannot be polynomial. Each "polynomial piece" is a certain polynomial such that the function together satisfies all continuity and value criteria. Sure, each piece of each of the basis splines can itself be represented as a sum of Bernstein polynomials, but that doesn't matter for B-splines because that makes a new basis now.
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: Sun Oct 23, 2022 10:23 pm The formula itself will be "this polynomial between t1 and t2, this other polynomial between t2 and t3...". It is faster and more stable to compute them using the algorithm I mentioned. In the current master all B-spline values are obtained from OCCT. In the new features I implemented it myself in GCS::BSpline::ValueAt.
So we have piece wise defined Bernstein polynomials.
jnxd wrote: Sun Oct 23, 2022 10:23 pm The phrase "polynomials are piecewise" is wrong. If it is piecewise defined, the function cannot be polynomial. Each "polynomial piece" is a certain polynomial such that the function together satisfies all continuity and value criteria. Sure, each piece of each of the basis splines can itself be represented as a sum of Bernstein polynomials, but that doesn't matter for B-splines because that makes a new basis now.
The polynomial of each piece is a Bernstein polynomial. That is my point.
It must be like that because when I e.g. take quadratic polynomials as base, the spline would look like this

C(t) = -2t^2+5, for t in [0, 1[
t^2+3*t-1, for t in [1, 2[
and so on.
But then the continuity feature is gone. So what kind of polynomials provide the continuity feature if not the Bernstein polynomials?

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