Evaluate NURBS curve

[Durman]

Problem statement

To calculate single point on Bezier curve just with 20 control points takes 5ms. I don't know too much about the theory but I believe it should be possible to implement faster even on Python.

untitled.zip

This function is called 438 times during work of the node. https://github.com/nortikin/sverchok/blob/0815e497d21fcd98a275c2515f9111ea78e33bc9/utils/nurbs_common.py#L123

[portnov]

I'm afraid this can not be helped by much. Generic NURBS calculation is really not so simple math.

This function is called 438 times

I'll look into this, but theoretically it is possible that this is really the number of times this function should be called in this case.

This problem, though, does not usually surface so much because of the following facts:

1. If you use Bezier curves instead of generic NURBS, and especially Bezier curves of 3rd order, everything should be faster. Bezier is a special case of Nurbs, but in Sverchok we have a special implementation of Bezier curves, which is much simpler and because of that it should be faster. And for Bezier curves of 3rd order we have even simpler implementation. In your setup, you can switch "Concatenate segments" flag off - then you will deal with a set of Bezier segments instead of one concatenated Nurbs curve.
2. Evaluation of Nurbs curves (and surfaces as well) is vectorized by use of Numpy. This means that evaluation of the curve in 1000 points should be about as fast as evaluation in 1 point. Or at least the time of evaluation should not grow by much when you increase the number of points.

[portnov]

I checked your file and everything looks like it should.

• Of 438 calls to calc, only 58 are calls from outside, others are recursive calls. calc is implemented with recursive algorithm, because it is the simplest way of implementing generic NURBS math. It is possible to make it faster if we would have special versions of code for different degrees of the curve, but for now I think it would be just too much code for us to maintain.
• 58 is effective number of control points in this curve. 19 is the number of Bezier segments, and each Bezier segment has 4 control points. Some of control points (those at ends of interim segments) are eliminated when we join Bezier segments into one Nurbs curve, so we have 4*19 - 18 = 58 control points in the Nurbs curve.
• If I switch "Concatenate" flag off, I get 19 points in 1ms instead of 1 point in 9ms :) So yes, Bezier is faster than generic nurbs.
• Having "Concatenate" still on, evaluation of the curve in 1000 points takes 17ms.
• Geomdl version of Nurbs evaluates 1 point in 0ms, but 1000 points in 44ms.
• FreeCad's version of Nurbs seems to be faster, at least, in this case: it evaluates 1 point in 0ms, and 1000 points in 18ms. But this is C++ :)

[Durman]

I don't know the theory too much but as to me the design of Bezier Input node looks weird. With such name of the node it's very unexpected that it returns NURBs by default. With switched off Concatenate Segments it returns Bezier curves indeed but they all are split into segments what is also unexpected. I don't know is it impossible to concatenate Bezier segments into one Bezier curve? It seems Blender is quite capable of that.

[portnov]

From mathematics perspective, Blender just missuses the terminology. To be honest, most of software that uses Bezier curves, do so. Bezier curve is a curve of degree N, with N+1 control points. For example, Bezier curve of degree 3 (which is mostly used, and in Blender, as in many other software, even can not be changed) always has 4 control points: two at ends of the curve, and two additional. But with 4 control points, you can not draw much: such a curve can be either "C" shaped, or "S" shaped, and that's basically all. To draw something interesting, you have to draw many Bezier curves one after another, combining Bezier segments into one curve. And that's what Blender, as well as most of software which uses Bezier curves, does. But, mathematically, if you concatenate two Bezier curves, it will no longer be Bezier curve: if you have two curves of degree 3, each with 4 control points, you concatenate them, removing one excessive control point in the point of concatenation, and you have 4+4-1 = 7 control points, which is not equal to degree+1 = 3+1 = 4. Curves which have more control points than degree+1, are, mathematically, NURBS curves. Sometimes, in some software, such curves which are made of several Bezier curves, are called "Bezier Splines", made of "Bezier Segments". Personally I do not think that the word "Spline" does introduce any clarity here :)

[Durman]

If Bezier curves are much faster than NURBs then it worth to combine them into splines because as separate segments they are not too much useful.

[portnov]

yeah, maybe. In Sverchok, we have a generic SvConcatCurve class, which just composes several arbitrary Curve objects into one, just redirecting all calls. So we could add a dropdown into "Bezier In" node, instead of checkbox: do not concatenate, generic concatenate (or "concatenate as Bezier Spline"), concatenate as Nurbs.

[portnov]

Nurbs are better in a sense of "full nurbs workflow". For example, if you have a Nurbs curve(s), you can make revolution surface from it, or loft surface, or birail surface — and it still will be a Nurbs surface, so you can pass it to FreeCAD-based solid nodes to do booleans, for example, or export it to one of applications which work with nurbs (into Rhino, for example)...

[Durman]

It's clear that NURBs might have their benefits but they also have their price.

I checked Concatenate Curves node, it also converts Beziers into NURBs.

[Durman]

It seems GN is much faster than even FreeCAD.

[portnov]

Probably (just a guess) Blender guys are using the fact that Blender's NURBS has restrictions: no arbitrary knotvector, for example - so NURBS basis functions are probably just hardcoded in C, instead of calculating them for user-provided knotvector.

[portnov]

@Durman Huh. For non-rational curves (bezier splines or nurbs without weights), I managed to speed up evaluation significantly (see in bspline_speedup branch). 19000 points in 23 ms:

I'm currently testing it, there may be unexpected problems.

[Durman]

I knew that there should be a way =)