A fast way to approximate a Bezier- or Nurbsspline to an array of points

Rhino Developer
1

Hello,

It’s one of my first posts here at this forum but I’m frequently hanging out at the grasshopper forum.
A while ago I made a plugin, called Advanced Surface Tools for Grasshopper.
My intention is to bring some very basic class-A surface functionality to Grasshopper in order to automate some surfacing tasks, which I frequently have to deal with when working with Icem Surf/Rhino -> high quality surface patterns and the ultimate goal: filleting of repetitive structures.

One of my main problems so far, besides all the hundreds of bugs :), is regarding accurate (<0.002mm) and fast approximation of splines to an array of points (or a curve). I need this for a lot of components.

Let’s see this example to get an impression of the problem:

approx.png1462×519 2.49 KB

An application example -> match a surface by projection:

approx3.png1081×545 131 KB

I came up with 2 approaches which do have some pros and cons:

  1. Least square fitting with variable Degree:

Pro:
• quite accurate
• very fast
• constant spacing between cps
Cons:
• not stable for higher degree at some data problems start at degree 6, in this example at degree 11
• it can only approximate Beziers not Nurbs

  1. Recursive Approximation

Pro:
• Supports nurbs
• stable at higher degree
• spacing can be variable, because it tries to fit an existing spline to an reference (pts or curve)
Cons:
• not accurate enough -> problem here is measuring deviation fast enough for each iteration. So I limited measuring at the greville parameter.
• “Slower” in most cases, recursion aborts under a certain tolerance, but because of limited measuring this is not trustworthy. I limited to 2000 iterations. Now 4-12 ms at my maschine is not slow per se, but because this should be an core algorithm I think an recursive approach is last option.

approx1.png1521×857 10.1 KB

approx2.png769×695 72.2 KB

Has somebody dealt with this problem?
Maybe someone has another or similar approach and is willing to share?
Is there may be a more stable least square approach with a nurbs extension?
My knowledge of advanced math is very limited, and I’m proud I made least square work with variable degree. So if
somebody can help improving this, it would be awesome.
Is there maybe a “hidden” rhinocommon method I haven’t found so far?
Any ideas in how to improve accuracy?

I have attached the code:
leastSquareVariableDegree_.gh (12.3 KB)
leastSquare.cs (3.1 KB)

1 Like
2

Hi Tom,

The functionality behind Rhino’s InterpCrv command can be accesssed with RhinoCommon’s Rhino.Geometry.Curve.CreateInterpolatedCurve function.

Does this help?

– Dale

3

One method for fitting a NURB with an arbitrary number of control points to a set of input points is to use a banded matrix solver. Depending on the number and distribution of the input points relative to the number of control points auxilary conditions (such as minimizing wiggles or interpolation of control points) may be needed to bridge areas where there are insufficient input points to uniquely determine all of the NURB control points.

InterpCrv command produces curves with the number of control points depending on the number of input points and curve degree.

FitCrv ommand with a polyline as input fits a curve of specified degree to vertices of the polyline. The polyline can be created using CurveThroughPt with degree 1. Unfortunately while FitCrv has a tolerance input the resulting curve frequently is further from some of the input points than the tolerance. http://docs.mcneel.com/rhino/5/help/en-us/commands/fitcrv.htm

4

Hello Dale,

thank you for the reply. No I’m not looking for interpolation.

The reason is quite simple. If I use Interpolation and I have an array of 30 points, I get a nurbscurve out of 30+ points. -> count of arraypoints <= controlpoint count of nurbscurve.

The core idea behind is to reduce controlpoints, in order to maximize shape quality.
Its clear that you cannot perfectly fit an nurbscurve to an array of points if there is the arrCount > cpCount.
You could say I simply need to reduce the points in the array, but then I get higher deviation, and maybe weird curvature results. So interpolation is not the solution here in my opinion.
I actually could live what my leastsquare approach delievers. The problem is that the algorithm sometimes breaks.
It seems not to be numerical stable.

see what happened at degree 17 (ok degree > 11 is nonsense anyway, but this error sometimes occur at degree 6 or 7, which is quite common in beziermodelling):

approx4.png1569×697 66.1 KB

5

Hello David,

thank you for the reply.

Okay that means I shouldn’t go for the native Rhinocommon Matrix implementation, but rather use an more feature rich math library like for instance math.net or similar?! And then instead of leastsquare I use an approach where I set up some boundary conditions like start and end tangent and deviation and then solve it.
I will play around with this idea. thank you

6

FitCrv ommand with a polyline as input fits a curve of specified degree to vertices of the polyline. The polyline can be created using CurveThroughPt with degree 1. Unfortunately while FitCrv has a tolerance input the resulting curve frequently is further from some of the input points than the tolerance. http://docs.mcneel.com/rhino/5/help/en-us/commands/fitcrv.htm1

"Interpolation "+“Fitcurve” is problematic → as you said tolerance issues, no control on cp count
“Interpolation”+ “Draw Sketch with snapping on pts” → produces quite good results, but again no control on cp count, no implementation on Rhinocommon
“Interpolation” + “_rebulidCrvNonUniform”-> quite good either but no implementation in rhinocommon and no control on cp count. Seems to be recursive as well, but not sure here. It has some control on knotlocation, which is interesting

7

The Rebuild command allows you to specify the number of control points. In RhinoCommon, you’d call Rhino.Geometry.Curve.Rebuild.

8

The Rebuild command allows you to specify the number of control points. In Rhinocommon, you’d call Rhino.Geometry.Curve.Rebuild.

No, I’m not looking for Rebuild. As I said there is no approximation algorithm in Rhinocommon. Rebuild does not keep the shape in place, because lowering the degree with keeping the shape, cannot be solved properly.So interpolation + rebuild is not a satisfying approximation. My hope was to find some answers beyond rhinocommon, because VSR Tools, Icem Surf and Autodesk Alias obviously do implement such approximation algorithm. So there must be a solution to this problem. Its just so hard to find any reference about nurbs/bezier math which deals with approx , blend , match, trim and all the so important functionality.

Anyways, thank you for your help

approxIcem.png996×464 43.2 KB

9

When you split an (interpolated) nurbs curve at its Greville Points you get a bunch of cubic bezier curves. Can’t this be a starting point? I mean, then you can start merging while checking accuracy? (Sorry, creative today, Tom. ;))

10

@chuck, what do make of all this?

11

As you noticed, it doesn’t work to fix the span count and increase the degree until the desired accuracy is reached. I would suggest picking a degree that gives you the desired continuity, definitely no higher than 7, and increase the span count until happy. A least squares algorithm will involve assigning a parameter to each point. To test your fit, you can just evaluate the curve at a point’s parameter and check the distance. This should not take any significant time but will lead to more spans than necessary. To reduce the span count, rather than just check the distance, do a local minimization of the distance from a point to the curve using the point’s parameter as the seed. I don’t know if you have access to local closest point algorithms in RhinoCommon or Grasshopper. If not, global closest point should not take significant time since the tree decomposition of the curve is only computed once and is cached on the curve. If you can come up with a good guess for a starting knot vector, maybe based on some estimate of curvature change in the point list, and refine by adding a knot on the spans that don’t fit, you should be able to reach your desired accuracy in a small number of iterations. If it’s taking more than 32, you should rethink how you’re setting the initial guess.

1 Like
12

just some examples were I need approximation:

1st example Surface split, or I call it “Real Trim”

example1.png858×520 20.1 KB

2nd example Matching onto surface:

example2.png891×533 73 KB

3rd example Matching at multiple surfaces,

example3.png869×545 98.7 KB

Just some ideas where to use approximation.
Other usage - mesh to surface approximation or Nurbs to Bezier conversion in general

Due to my needs at work, Single span is always preferred over multispan & lower degree. I’m working in class a industry.

1 Like
13

Hello Chuck,

thank you for answering.

As you noticed, it doesn’t work to fix the span count and increase the degree until the desired accuracy is reached. I would suggest picking a degree that gives you the desired continuity, definitely no higher than 7, and increase the span count until happy. A least squares algorithm will involve assigning a parameter to each point.

I managed Leastsquare for Bezier, but I do have some troubles with Nurbs. I probably need to study on how to implement a Nurbscurve in Matrix representation. Then I will be able to implement that least square approach. However as I mentioned, due to my work, single span is always preferred over multispan. So a non-rational single span approximation would be better.

rather than just check the distance, do a local minimization of the distance from a point to the curve using the point’s parameter as the seed.

that’s a good idea. I will try this out. I vaguely remember such method in rhinocommon.

. If it’s taking more than 32, you should rethink how you’re setting the initial guess.

So I probably should mix both. Least square for a first guess and some minor adjustments with recursion.

So the first thing is to find a way to implement Least square with Nurbs rather than Bezier. And even if stay single span, I do have some more flexibility.

Thank you

14

I may be wrong, but I don’t think you can visually tell the difference between a multiple span degree 7 curve with simple knots and a single span curve of higher degree. The degree 7 curve has 6 continuous derivatives.

15

I wouldn’t say that. The problem with multispan is something different, in my opinion.
Bezier segments are joined with (only) curvature continuity in between. I agree you don’t see any difference in it without using a curvature graph. So to approximate a multispan will probably make things easier and you wont see any difference with the eye. However as I pointed out I like to work further on with that. Two problems occur with multispan shapes. Its way more difficult to control the overall curvature flow and its more difficult to match a weighted multitspan surface onto another multispan surface. So there is a high chance that a matched surface will increase cpcount drastically and if you match another surface onto that it will increase either. So in the end
you get a lot of “heavy” patches, unable to be modified manually.
I do have to say that I’m working in automotive industry, and I create final shapes in exterieur design, which do not only have to represent a certain design but also do care about curvature flow and highlights.
I know that rhino does not exactly fits the need in that very specialised field of cad. But due to the rising of “generative parametric design”, automating task do play a greater role, something you cannot do with Icem Surf or Autodesk Alias, but Rhino is prefect for. Another problem is that I’m bound by certain guidelines on how surfaces have to be like. I often find these regulations nonsense, but I do believe in less is more.

2 Likes
16

Just to clarify, if a NURBS has simple knots, degree 3 gives (only) curvature continuity. Degree 4, curvature varies smoothly. Degree 7 has much higher continuity.

17

oh okay. didn’t know that. This is interesting. Thank you

18

I just like to share some improvements on my current work in order somebody is interested in:

I managed to stabilise the least square. Some problems are solved by setting in a boundary condition of a defined start- and endpoint. I also thought about adding a boundary condition on tangency at the curve ends, but that’s not a problem now.

Whats good now:
*more accurate, thanks to chucks hint of using a min max deviation analysis( “Curve.GetDistancesBetweenCurves(…)”)
*quite fast, eventhough its way slower than expected
*works well with unclean reference data

  • possibility to refine data (improves accuracy but also triples time)

whats not good:

*No implementation of multispan
*no cp location corresponding to Curvature Maximas
*At higher curved reference data, cp distribution seems not good anymore,
especially arcs

  • I had to limited the degree to 11, because at higher degree there seems to be issues with rhinocommon methods, Setting endpoints didn’t work properly anymore, and the deviation analysis sometimes crashed rhino.
    Could be also something in my code, but I couldn’t find the issue. After limiting the degree both errors did not occur anymore.

I’m going also to improve my recursive variant. I expect not being that slower.
In my recursion variant I implemented a need to provide a curve where to work from.
The advantage of this approach is that I don’t need to dive so much into math and I can
better control cp distribution, knots …

Approx2_.gh (17.4 KB)

Approximation.cs (7.5 KB)

4 Likes
19

Hello Tom
your approach is definitively not finding the best solutions in your examples.
I donwloaded your gh script baked the input curves: despite one they are all simple one-spanned low degree Beziers. The only exception is the half arc.
Using our nurbstoolkit I could compute a bezier degree4 approx to the half arc within 0.002 max error.
The approximations for the other curves stopped mostly at the curve reproduction level, meaning the errro drops to zero one the approximating curve has exactly the same degree/span as the original curve. half-circle.3dm (21.0 KB)

A more interresting example would be a C2 continous trim curve on a single or patched surface configuration.

20

Who claimed this? This actually is the only Bezier approximation algorithm in this whole forum free to download. The purpose of this thread was to get support on this, but in the end I made it for myself the best I could back then. As a plus I shared this approach. Most people do not even know why this is good for, not to speak of having any clue on how to solve such problems within a real engineering process.The generative car parts I made with these tools can be buyed today, everything I couldn’t automate was done manually during the development. Such is life and this won’t change in the near future. But introducing a semi- automated approach on generative patterns, increased possibilities in class A modelling and helped our technicians from doing very boring and repetive work. It was really helpful back then and still is (at least I hope so, because I left design engineering). I know very good approximation algorithms, I just couldn’t use them for generative automation. Probally they are better then yours, because they had years of devellopment, time and knowledge, I did not have. If you wonder why I left my previous job… One aspect had something to do with people talking about others work, with absolutly having no clue about the whole picture. (By the way I’m not innocent as well, but at least I’m working on it, trying to give constructive replies)

1 Like