BSpline Curve fitting in toSketch workbench.

Have some feature requests, feedback, cool stuff to share, or want to know where FreeCAD is going? This is the place.
Forum rules
Be nice to others! Read the FreeCAD code of conduct!
Post Reply
keithsloan52
Veteran
Posts: 2756
Joined: Mon Feb 27, 2012 5:31 pm

BSpline Curve fitting in toSketch workbench.

Post by keithsloan52 »

I am trying to improve the curve fitting in the toSketch workbench.

If one performs a toSketch command/icon on a section through say a Mesh one ends up with a sketch made up of lines.
Curves are made up of a number of short lines and straight lines can be a mixture of short and long lines see
385CF7ED-55FE-4B00-A8DD-C178FE729E57.jpeg
385CF7ED-55FE-4B00-A8DD-C178FE729E57.jpeg (46.99 KiB) Viewed 682 times
The to_Curve fit command/icon processes the selected sketch and performs
  • Merges lines that have a very similar slope
  • Tries to perform a BSpline fit using the geomdl python library.
For simple curves a BSpline fit of Degree 3 and 4 control points works quite well but not for more complex curves.
5B709B76-34E0-42D7-988A-5C92361B74DB.jpeg
5B709B76-34E0-42D7-988A-5C92361B74DB.jpeg (63.5 KiB) Viewed 682 times
My latest attempt is to start with 4 control points and calculate the hausdroff distance between the points being fitted and the evaluation points of the BSplne. I then increase the number of control points until the hausdroff distance no longer decreases.
This produces a better fit but still no cigar
1029DB2C-2743-4C9C-8D89-F40C20F52B88.jpeg
1029DB2C-2743-4C9C-8D89-F40C20F52B88.jpeg (176.29 KiB) Viewed 682 times
One can get a good fit by having the same number of control points as point to be fitted but in the example above that would be 87 control points which is not really a solution in my opinion.

So I am open to suggestions, for example any idea how i could break the curve in the example into 3 or 4 sets for evaulation.

Current test file
Throttle-Lock-Test-Curve3.FCStd
(134.88 KiB) Downloaded 15 times
User avatar
jnxd
Posts: 951
Joined: Mon Mar 30, 2015 2:30 pm
Contact:

Re: BSpline Curve fitting in toSketch workbench.

Post by jnxd »

@keithsloan52
My latest attempt is to start with 4 control points and calculate the hausdroff distance between the points being fitted and the evaluation points of the BSplne. I then increase the number of control points until the hausdroff distance no longer decreases.
Had to search Hausdorff distance. If you're just adding control points you're probably keeping the weights same and knot values uniform. You should probably look into that. One way would be to try to add a knot where the diatance is worst in the last iteration (getClosestParam is your friend here).

Ideally a spline formulated using knots and tangents (and maybe curvatures) would be better (like hermite spline), but that's not supported right now (sneak peak, that's one of my next possible plans).

Curve fitting is quite a big deal of research so expect it to take time.
My latest (or last) project: B-spline Construction Project.
edwilliams16
Veteran
Posts: 3106
Joined: Thu Sep 24, 2020 10:31 pm
Location: Hawaii
Contact:

Re: BSpline Curve fitting in toSketch workbench.

Post by edwilliams16 »

Have you tried a least squares fit, as in https://www.geometrictools.com/Document ... resFit.pdf
keithsloan52
Veteran
Posts: 2756
Joined: Mon Feb 27, 2012 5:31 pm

Re: BSpline Curve fitting in toSketch workbench.

Post by keithsloan52 »

edwilliams16 wrote: Mon Nov 28, 2022 9:14 pm Have you tried a least squares fit, as in https://www.geometrictools.com/Document ... resFit.pdf
I am using https://nurbs-python.readthedocs.io/en/ ... mate_curve
geomdl.fitting.approximate_curve(points, degree, **kwargs)
Curve approximation using least squares method with fixed number of control points.

Please refer to The NURBS Book (2nd Edition), pp.410-413 for details.

Keyword Arguments:
centripetal: activates centripetal parametrization method. Default: False
ctrlpts_size: number of control points. Default: len(points) - 1
Parameters:
points (list, tuple) – data points
degree (int) – degree of the output parametric curve
Returns:
approximated B-Spline curve

Return type:
BSpline.Curve

If I use the similar function without specifying the number of control_points it seems to use the number of data points as the number of control points, which gives a good fit but defeats trying to create a curve that fits the data but with a minimum number of control points.

There is also a function https://nurbs-python.readthedocs.io/en ... ement.html but have to get my head round what it is doing, plus if I call it, does it effect the evaluations points in the curve that I use to calc the hausdroff distance?

There is this paper https://hub.hku.hk/bitstream/10722/4842 ... f?accept=1 which is where I found out about hausdroff distance
but not sure about the rest of the method(s). Also there are a number of research papers but how does one implement with a python library of which I am aware of at least three. The one I am using, https://sintef.github.io/Splipy/index.html and standard scipy.
edwilliams16
Veteran
Posts: 3106
Joined: Thu Sep 24, 2020 10:31 pm
Location: Hawaii
Contact:

Re: BSpline Curve fitting in toSketch workbench.

Post by edwilliams16 »

The abstract for this looked to be attractive. https://web.cs.dal.ca/~eem/cvWeb/pubs/sp-paper.pdf It has a reasonably simple objective function, at least simpler to understand than usin Hausdorff distance, and they also propose inserting extra knots where the fit is locally bad - which seems very sensible to me. I don't know if they have published their code anywhere.

The Nurbs book has a fancier algorithm than the plain least square fit one you quoted, in the following section pp 413-419.
Post Reply