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

Sketcher: B-Spline pages

Post by jnxd »

Starting this thread to discuss the pages related to sketcher B-Splines.

The first thing I wanted to know was the page for the curve itself. Specifically, what constitutes a uniform vs. non-uniform and rational vs. non-rational b-spline. In https://wiki.freecadweb.org/B-Splines#N ... _B-splines:
As you can imagine, it can be useful to have B-splines whose Bézier parts have different path lengths. This can be achieved by weighting the different polynomials:
b67a0a28ec46e75c8b43628a6760beb66ec97c4a.svg
(9.12 KiB) Downloaded 71 times
[w_k] is hereby the weight of the [k]-th control point. When the weights are not equal, the B-spline is called non-uniform.
Now, I want to know whether this is in fact the correct form of non-uniform b-splines by some translation. AFAICT, a non-uniform b-spline only needs to have knots being unequally apart. By setting different weights to poles the spline becomes rational. So,
- A b-spline with unequally spaced knots (including multiplicities) but with all poles having equal weights makes a non-uniform non-rational b-spline.
- A b-spline with equally spaced knots (including multiplicities) but with all poles having different weights makes a uniform rational b-spline.

I am trying to find resources that can shed some light on whether there is some equivalence between these. If there is not, this also has some implications in https://wiki.freecadweb.org/B-Splines#C ... the_Weight. For example, the following statement may be wrong:
To create a non-uniform B-spline the weights have to be non-uniform. To achieve that you can either change the radius constraint of the first control point circle
uwestoehr wrote: Hi
HI Uwe, tagging you since you last updated this page. Could you dig up the source for the formula?
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 Mar 20, 2022 8:54 pm For example, the following statement may be wrong:
To create a non-uniform B-spline the weights have to be non-uniform. To achieve that you can either change the radius constraint of the first control point circle
Why do you think this is wrong? Looking at the formulas this is correct.

The formulas are the ones you also find by googling. I think I once took them from here: https://en.wikipedia.org/wiki/Non-unifo ... URBS_curve
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 Mar 20, 2022 11:06 pm Why do you think this is wrong? Looking at the formulas this is correct.
My problem is mainly with this formula:
Screenshot from 2022-03-20 19-21-17.png
Screenshot from 2022-03-20 19-21-17.png (3.42 KiB) Viewed 2806 times
Firstly, I didn't find any analog (at least in the Wikipedia page and it's resources). Secondly, just looking at it, something seems off: if you were to double each of the [w_k]'s, this should not change the spline. However, if we go by the formula, this creates a totally different spline, which would be twice as large as the first one. Apart from creating a different spline, this would also make it possible for the b-spline to be outside the convex hull of its poles, something which AFAICT is guaranteed.
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 Mar 20, 2022 11:31 pm if you were to double each of the [w_k]'s, this should not change the spline. However, if we go by the formula, this creates a totally different spline, which would be twice as large as the first one.
Yes. But what is wrong with this? When all w_k are equal they behave like a normal factor. Therefore you normalize this (the NURBS formula). There equal w_k cancel out.
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 Mar 21, 2022 1:02 am
jnxd wrote: Sun Mar 20, 2022 11:31 pm if you were to double each of the [w_k]'s, this should not change the spline. However, if we go by the formula, this creates a totally different spline, which would be twice as large as the first one.
Yes. But what is wrong with this? When all w_k are equal they behave like a normal factor. Therefore you normalize this (the NURBS formula). There equal w_k cancel out.
It's not that straightforward. The normalization gives us the uniform rational b-splines, but without a knot vector specified it's still uniform. The example from wikipedia explains the difference:
Screenshot from 2022-03-20 21-07-03.png
Screenshot from 2022-03-20 21-07-03.png (11.98 KiB) Viewed 2731 times
Note the extremely close knots (peaks in linear basis functions) and how the quadratic basis functions are nearer to them? Note the peak is in the middle of two knots rather than at a single knot. For equal knots the basis functions would be identical in shape. I was looking if the "un-normalized" formula can replicate that but I can't see any way.
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: Mon Mar 21, 2022 1:20 am The normalization gives us the uniform rational b-splines, but without a knot vector specified it's still uniform.
I still don't know you what you want to get/achieve. First, the first equation in https://wiki.freecadweb.org/B-Splines#N ... _B-splines is just a non-uniform spline. It is not normalized and of no practical usage. It only introduces the weights.
Then I explain the normalization and why this is sensible and thus used in practice. The formula in the Wiki is also the one in the Wikipedia.

Concerning the knot vector, you cannot freely play around with this. I linked this video: https://www.youtube.com/watch?v=ni5NNPCVvDY where one can see, that to get a cubic spline, the know vector must have a certain form. And for CAD we usually need cubic splines. Non-unifom cubic splines means that the different segments are weighted differently, not that their time range is shortened or widened. The time of travel is changed by the weights.

I might have a mistake then please write me the correct formula.
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 Mar 21, 2022 1:39 am
jnxd wrote: Mon Mar 21, 2022 1:20 am The normalization gives us the uniform rational b-splines, but without a knot vector specified it's still uniform.
First, the first equation in https://wiki.freecadweb.org/B-Splines#N ... _B-splines is just a non-uniform spline. It is not normalized and of no practical usage. It only introduces the weights.
Then I explain the normalization and why this is sensible and thus used in practice. The formula in the Wiki is also the one in the Wikipedia.
My point is that the "weighted" form you show should not be called "non-uniform" because a "non-uniform b-spline" is specifically defined as something else. I see now what you intended to do by why putting up that formula, but it still needs to be re-worded: maybe just saying weights doesn't help.
uwestoehr wrote: Mon Mar 21, 2022 1:39 am Concerning the knot vector, you cannot freely play around with this.
Thanks for pointing me to the video, that should give me some more info before I proceed. However, the question of whether or not we can freely play with the knot vector depends a lot on what we want to do. After all, increasing a knot's multiplicity is indeed changing the knot vector: there are not unequal distances between knots (some being zero). These are needed, for example, to exactly represent a circle. That example is not a good one, however, since distinct knots are still equally spaced. If I find better examples I'll post them.

I should also note that OCCT defines non-uniform knots in this way: https://dev.opencascade.org/doc/refman/ ... 9619f9b86c.
I might have a mistake then please write me the correct formula.
As I said, I think the error is not in the formula (especially since already it's there to demonstrate its uselessness), but the definitions. I don't want to change things with the limited knowledge I have though, so I'll need to take some more time to figure out what to do.
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: Mon Mar 21, 2022 1:39 am
jnxd wrote: Mon Mar 21, 2022 1:20 am The normalization gives us the uniform rational b-splines, but without a knot vector specified it's still uniform.
I linked this video: https://www.youtube.com/watch?v=ni5NNPCVvDY where one can see, that to get a cubic spline, the know vector must have a certain form.
If you're talking of the line at time https://youtu.be/ni5NNPCVvDY?t=308 note that what they say is "to define a uniform cubic spline, only the poles are needed". They do not say that it is the only way to define a general cubic bspline. However, for a general b-spline, the knot vector and/or weights should also be defined.
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: Mon Mar 21, 2022 2:24 am My point is that the "weighted" form you show should not be called "non-uniform" because a "non-uniform b-spline" is specifically defined as something else.
Where is such a "definition"?

Looking at the image in https://wiki.freecadweb.org/B-Splines#Basis (in this section you also find 2 linked videos) you see how the spline becomes non-uniform by weighting. Assume that in the image all basis functions have the weight 1 but the yellow one the factor 10, then it is clear what happens - you will no longer the the orange line as result, but basically the yellow curve since it outweights all other basis functions in the summation.

jnxd wrote: Mon Mar 21, 2022 2:24 am so I'll need to take some more time to figure out what to do.
And this is not yet clear to me. What do you want to achieve, what do you want to do?
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 Mar 21, 2022 5:24 pm Where is such a "definition"?
I do not have an authoritative book with me to give an exact definition, but there are multiple places that imply this:

In Wikipedia B-Spline Properties section
If each knot is separated by the same distance h {\displaystyle h} h (where h = t j + 1 − t j {\displaystyle h=t_{j+1}-t_{j}} {\displaystyle h=t_{j+1}-t_{j}}) from its predecessor, the knot vector and the corresponding B-splines are called "uniform"...
Implying that in non-uniform b-splines the knots are separated by possibly unequal distances.

In http://web.cs.wpi.edu/~matt/courses/cs5 ... nurbs.html
For NURBS, the relative parametric intervals (knot spans) need not be the same for all shape segments, i.e. the knot spacing is nonuniform...
Indicating that "non-uniform" is used in reference to knot spacing rather than in weights.

In https://dev.opencascade.org/doc/refman/ ... 9619f9b86c
Returns NonUniform or Uniform or QuasiUniform or PiecewiseBezier. If all the knots differ by a positive constant from the preceding knot the BSpline Curve can be :

Uniform if all the knots are of multiplicity 1,
QuasiUniform if all the knots are of multiplicity 1 except for the first and last knot which are of multiplicity Degree + 1,
PiecewiseBezier if the first and last knots have multiplicity Degree + 1 and if interior knots have multiplicity Degree

A piecewise Bezier with only two knots is a BezierCurve. else the curve is non uniform. The tolerance criterion is Epsilon from class Real.
Note that here knots and multiplicities are separated (as opposed to the more mathematical definition in the MOOC videos where knots are simply repeated). So a b-spline with a (middle) knot with multiplicity higher than 1 will be returned as NonUniform (except for PiecewiseBezier, but I expect this is again for implementation purposes, so it's still a special case of non-uniform b-splines).
uwestoehr wrote: Mon Mar 21, 2022 5:24 pm And this is not yet clear to me. What do you want to achieve, what do you want to do?
I just intend to make sure the text is correct. I will update it once I learn if and when unequal but non-zero knot spans are useful.
My latest (or last) project: B-spline Construction Project.
Post Reply