B-spline Construction Project

Info about new community or project announcements, implemented features, classes, modules or APIs. Might get technical!
PLEASE DO NOT POST HELP REQUESTS OR OTHER DISCUSSIONS HERE!
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:

B-spline Construction Project

Post by jnxd »

tl;dr: I plan to add alternative methods to create B-splines so that they are defined to pass through a given set of points, instead of through the control points. This project (or at least one part of it) will be done while I'm working at Ondsel Inc. through funding from the Open Toolchain Foundation. Apart from the funding source difference, I expect the project to proceed similarly to the B-spline constraint project.

Introduction

After a successful “B-spline constraint” project, we have better control over how complex curves are shaped in sketcher. This now opens up some more possibilities. To begin with, since we can now constrain knots like any other point, we should be able to auto-constrain them at creation time. To do this, we will need an alternative method to create splines (note that these may not be in B-spline form). In this method, we specify the points through which the spline passes, and these become the knots of the spline.

An additional advantage of this method is that we can have on the fly control on the continuity at the knot, in addition to the degree of the spline.

This project will be done while I'm employed at Ondsel Inc., and funded by the Open Toolchain Foundation. I will be starting 15 February, 2023, so we can take this time to take community input and solidify the plan.


In this project I expect to explore two directions, viz. continuing to work with B-splines, and introducing new formats of splines that are better suited for interpolation. However, as will be evident shortly, "direction 2" might take a longer time commitment and thus might not be possible within the time frame. So that will be explored in the future.

Direction 1

While specifying the points is itself not difficult, the biggest problem is the degrees of freedom the result B-spline will have. Control points can specify exactly a (uniform non-rational) B-spline, but just the knots allow for some freedom, specifically 2*(the difference between the number of knots and number of control points). Thus, making an educated guess of the shape of the B-spline becomes important.

There are also some additional degrees of freedom that can be considered. While working on B-spline constraints I demonstrated that just knot position and slope do not necessarily yield good curves, the knot parameters may also need to be specified. So, as a part of this project, I also plan to allow smoothly changing these knot parameters.

Direction 1 Duration: Targeted for completion before the end of March.

Direction 2

An alternative way to construct through knots is not to create B-splines, but other forms of the spline, like the Hermite form. This takes away the hassle of having to compute the control points.

However, the biggest problem with this is that these are not implemented in OCCT. So, we would either have to implement these ourselves, or only create Bezier curves and constrain them at the end points. The latter will then only have support for C1 continuity. To avoid this limitation, an “equal curvature” constraint can also be created.

An additional factor of consideration is that multiple forms of a spline would need to be distinguished from each other. This would need marking internal points differently. So, for example, knots, control points and direction indicators will all have to be distinguished with, say, different colors or shapes.

Direction 2 Duration: TBD. Since this involves creating alternative forms of splines (which do not exist in OCCT itself), this direction will take longer to implement.


As earlier, I invite interested people to track this thread and the relevant PRs/branches. Please let me know if there are things I may be missing, or if there are any other features you would like to see implemented once the current plan is completed.
My latest (or last) project: B-spline Construction Project.
User avatar
onekk
Veteran
Posts: 6144
Joined: Sat Jan 17, 2015 7:48 am
Contact:

Re: B-spline Construction Project

Post by onekk »

There is not already interpolate and approximate functions thst will do the job?

edwillimas16 has done some works that show a decent approximation of conics with Nurbs, as Conics are maybe the most difficult things some techniques could be used.

Regards

Carlo D.
GitHub page: https://github.com/onekk/freecad-doc.
- In deep articles on FreeCAD.
- Learning how to model with scripting.
- Various other stuffs.

Blog: https://okkmkblog.wordpress.com/
User avatar
jnxd
Posts: 951
Joined: Mon Mar 30, 2015 2:30 pm
Contact:

Re: B-spline Construction Project

Post by jnxd »

onekk wrote: Thu Feb 09, 2023 3:03 pm There is not already interpolate and approximate functions thst will do the job?

edwillimas16 has done some works that show a decent approximation of conics with Nurbs, as Conics are maybe the most difficult things some techniques could be used.

Regards

Carlo D.
Interpolate exists (it occurred to me as I was typing that I should have added a "what's already there" section), but I need to look at how well it works, and whether or not it allows for discontinuities. I'm not sure I'm 100% clear on how the (arcs of) conics to NURBS conversion can help. While it indeed needs rational splines, the procedure is largely known already, and is restricted to producing single piece B-splines.
My latest (or last) project: B-spline Construction Project.
Hologram
Posts: 201
Joined: Thu Nov 03, 2022 3:05 pm

Re: B-spline Construction Project

Post by Hologram »

Great news, interesting project, congrats on the funding! It touches neatly upon things we discussed in the other topic too.

For anyone looking for a refresher on splines, have a look at this video.

Since this is pure curve creation:
1. Will you handle both Draft Workbench and Sketcher geometry?
I think that it's important to be able to at least edit the Spline in the Draft workbench in case you convert a wire to a sketch or vice versa.

This then also implies importing curves from other software through IGES, DXF or any other file types that may be suitable (OBJ also supports curves IIRC).

2. How do you plan on dealing with imported geometry if at all? If the importer cannot read the geometry correctly, but the FreeCAD will support it, then that's untapped potential. I have to confess, I don't know how it deals with imported curves, regardless of spline type.

3. As for features, I would like to see the ability to 'rebuild' geometry to specify the degree and number of points (as you may remember from the Alias Theory builder I linked to in the other thread). This is helpful for constraints and surface modelling/ reverse engineering as well.

4. Final point for now: do you plan to enable adding/ removing CV's to existing splines (i.e. by invoking a tool and then hover over a curve > show a preview of the new CV insertion point > click to create)?
While looking at the existing spline behaviour, I noticed this works quite funky now, as it doesn't change the spline at all, see the gif here:
https://gifyu.com/image/SqwAc
User avatar
jnxd
Posts: 951
Joined: Mon Mar 30, 2015 2:30 pm
Contact:

Re: B-spline Construction Project

Post by jnxd »

Hologram wrote: Thu Feb 09, 2023 3:39 pm Since this is pure curve creation:
1. Will you handle both Draft Workbench and Sketcher geometry?
I think that it's important to be able to at least edit the Spline in the Draft workbench in case you convert a wire to a sketch or vice versa.

This then also implies importing curves from other software through IGES, DXF or any other file types that may be suitable (OBJ also supports curves IIRC).
This is intended for Sketcher only. Sorry but I've literally never worked or even used draft. :oops:
Hologram wrote: Thu Feb 09, 2023 3:39 pm 2. How do you plan on dealing with imported geometry if at all? If the importer cannot read the geometry correctly, but the FreeCAD will support it, then that's untapped potential. I have to confess, I don't know how it deals with imported curves, regardless of spline type.
Haven't tried, but we can look at this after the current work. I know people have been asking for a proper import from Inkscape for a while.
Hologram wrote: Thu Feb 09, 2023 3:39 pm 3. As for features, I would like to see the ability to 'rebuild' geometry to specify the degree and number of points (as you may remember from the Alias Theory builder I linked to in the other thread). This is helpful for constraints and surface modelling/ reverse engineering as well.
Need to look up what rebuild means here. Do you mean "convert to NURBS"?
Hologram wrote: Thu Feb 09, 2023 3:39 pm 4. Final point for now: do you plan to enable adding/ removing CV's to existing splines (i.e. by invoking a tool and then hover over a curve > show a preview of the new CV insertion point > click to create)?
While looking at the existing spline behaviour, I noticed this works quite funky now, as it doesn't change the spline at all, see the gif here:
https://gifyu.com/image/SqwAc
As I have mentioned earlier as well, editing CV's directly wouldn't maintain the shape of the B-spline. Instead, you can add/remove knots. If you have a representative video of another software working by deleting control points, maybe that'd give me a better idea (though there may also be patents associated with it so I need to be careful on that front).

In the video, note that just deleting the physical points only deletes what is called the "internal geometry", without modifying the curve itself. @abdullah can give a better idea, as well as his future plans. Currently they behave more like a focus (or any other interior point) of a parabola/ellipse.
My latest (or last) project: B-spline Construction Project.
Hologram
Posts: 201
Joined: Thu Nov 03, 2022 3:05 pm

Re: B-spline Construction Project

Post by Hologram »

jnxd wrote: Thu Feb 09, 2023 4:36 pm As I have mentioned earlier as well, editing CV's directly wouldn't maintain the shape of the B-spline. Instead, you can add/remove knots. If you have a representative video of another software working by deleting control points, maybe that'd give me a better idea (though there may also be patents associated with it so I need to be careful on that front).
Oh yeah, now I understand why we don't understand each other. I am talking from a user perspective and you from a developer perspective. So, what I actually want is two things: delete a CV > change the curve altogether. This is useful when you already have constraints applied and need to do drastic edits, e.g. delete a CV when there are not enough CV's for curvature constraints (this would delete the CV and change the Curvature constraint to a Tangency constraint — in the future™). And second, the actual curve 'rebuilding' this procedure changes the degree of the curve and/ or number of CVs. So while you are correct that this changes the curve, for the user it should look (almost) the same after using the tool. Note that rebuilding is more part of high-end surface modelling workflows and that Mechanical CAD usually only offers adding and removing individual CVs.

Basically, commercial algorithms apply a curve matching, so that if you change a 4th degree curve to a 5th degree curve, the latter approaches the first. It looks the same, but with an additional CV. So it is basically substituting the original curve with a closely approximated curve that has a higher/ lower degree or CV count. Similarly, you could also apply this to manually adding or removing CVs rather than knots.

You could therefore do both: add/ delete CV > change the curve's appearance.
add/ delete CV > approximate curve > maintain appearance but with one more/ less handle.

Have a look at these tutorials for some basic info: NURBS Surfaces Degree and CVs and NURBS Curves: spans and edit points.

There used to be a very good series from Autodesk that explained in-depth why you need rebuilding tools, but unfortunately, I can't find them anymore (I bookmarked it but it's no longer there). This one covers the same concept, pay close attention to how he works. He often adds a line, upps the degree to get a curve. If the curve cannot match the desired shape, he adds another CV and another degree and works his way through, until he gets the desired shape with the least number of CVs possible (like with mesh modelling, you want to have a maximum of control with the least amount of effort to tweak shapes). See https://youtu.be/vrIaMI5tfUo?t=780.

But, Alias has a terrible UI, so here's the Fusion 360 way of adding a point on a spline, notice how the shape remains constant: https://youtu.be/quGQB91V0z0?t=111.

The overall alias tutorial series, for anyone interested:
https://knowledge.autodesk.com/support/ ... tml?v=2021
User avatar
jnxd
Posts: 951
Joined: Mon Mar 30, 2015 2:30 pm
Contact:

Re: B-spline Construction Project

Post by jnxd »

By "changes the curve", I meant it changes the shape of the curve if one control point is deleted/added and all other control points are kept the same. What you are asking for seems to at least maintain the shape of the curve (to the extent possible, this can be done exactly while adding a point and changing others, but only approximately otherwise).

Hologram wrote: Thu Feb 09, 2023 5:23 pm
Basically, commercial algorithms apply a curve matching, so that if you change a 4th degree curve to a 5th degree curve, the latter approaches the first. It looks the same, but with an additional CV. So it is basically substituting the original curve with a closely approximated curve that has a higher/ lower degree or CV count. Similarly, you could also apply this to manually adding or removing CVs rather than knots.
We already have https://wiki.freecad.org/Sketcher_BSplineDecreaseDegree and https://wiki.freecad.org/Sketcher_BSplineIncreaseDegree if that's what you want.
My latest (or last) project: B-spline Construction Project.
Hologram
Posts: 201
Joined: Thu Nov 03, 2022 3:05 pm

Re: B-spline Construction Project

Post by Hologram »

Oh yeah, forgot to mention that for surface modeling, you'd want to keep the spans low, ideally use single span (golden rule of Alias #3) From what I read on the existing tools is that they add knots (create multi-span curves) this creates worse curvature. But, it may also be a terminology difference between FreeCAD and Alias/ Rhino?

In most surface modelling software, you can get to 7th or 9th degree curves. But for Curvature continuity you would need to have 6 CV's to constrain. Meaning (CVs = degree + span) 6 CVs = 1 span + degree 5 curves.

So the existing multi-knot based splines may not be the best for surface modelling. According to the Alias theory builder you should use single span bezier curves only. Just putting this out, because I'm interested in Surface modelling. It's not there yet, but it might be something to work towards as well when adding new spline types and potentially workflows that build on this.

But I won't bother you with this if you are not interested. I'm happy to see you continue your work first and foremost.
User avatar
jnxd
Posts: 951
Joined: Mon Mar 30, 2015 2:30 pm
Contact:

Re: B-spline Construction Project

Post by jnxd »

Hologram wrote: Thu Feb 09, 2023 6:25 pm Oh yeah, forgot to mention that for surface modeling, you'd want to keep the spans low, ideally use single span (golden rule of Alias #3) From what I read on the existing tools is that they add knots (create multi-span curves) this creates worse curvature. In most surface modelling software, you can get to 7th or 9th degree curves. But for Curvature continuity you would need to have 6 CV's to constrain. Meaning (CVs = degree + span) 6 CVs = 1 span + degree 5 curves.
So the existing knot based splines may not be the best for surface modelling. You may need different spline types for that (though I am not a mathematician). Just putting this out, because I'm interested in Surface modelling. It's not there yet, but it might be something to work towards as well when adding new spline types and potentially workflows that build on this.
I definitely want to move into surface modelling (was the target of getting into B-splines), but for now there's much to do in 2D.

Our biggest conflict of ideas seems to come from the fact that I'm looking at B-splines by themselves, while you are (rightfully) looking at them as a connector between two curves. My understanding was higher degree curves tend to misbehave a lot, but if classical wisdom mentions using them I'm wrong somewhere.
Hologram wrote: Thu Feb 09, 2023 6:25 pm But I won't bother you with this if you are not interested. I'm happy to see you continue your work first and foremost.
Please don't mind my apathetic tone. Admittedly it is such right now, but I would definitely want to know what users want. Currently, I believe there's a deadline to deal with, and even without that I can end up being stubborn as a mule. I think we're getting to a better solution with this back and forth.
My latest (or last) project: B-spline Construction Project.
abdullah
Veteran
Posts: 4935
Joined: Sun May 04, 2014 3:16 pm
Contact:

Re: B-spline Construction Project

Post by abdullah »

jnxd wrote: Thu Feb 09, 2023 4:36 pm In the video, note that just deleting the physical points only deletes what is called the "internal geometry", without modifying the curve itself. @abdullah can give a better idea, as well as his future plans. Currently they behave more like a focus (or any other interior point) of a parabola/ellipse.
Sure! When I have time, I will remove the ability to delete internal geometry (unless the complex curve having it is deleted too).
Post Reply