Curve Library Review

Technical Feedback
1

Before implementing curve evaluation for the new Curves type, I did a review of available curve libraries, with the hope of avoiding reimplenting evaluation and other tools in case an existing library already provided the functionality. In addition to providing necessary features, a library should be actively maintained, have a focus on performance, interface with C/C++, have a “pleasant” API, and a GPL compatible license.

We’re aiming on supporting four curve types: poly curves, Bezier curves, Catmull Rom curves, and NURBS, like the existing Blender curve object, with the addition of Catmull Rom, which is a standard for hair-like use cases. As a reminder, NURBS (Non-Uniform (knots vector can be adjusted manually), Rational (every control point has a weight), B-spline) is a generalization of the other curve types. The generality comes with a performance and UI cost.

Storing attributes on curves and interpolating those to the resulting evaluated points seems to be a use case that isn’t often considered. Ideally, interpolating attributes besides positions would not require a complete re-evaluation of a complex curve.

I found quite a few suggestions online, but in the end, I don’t think I found a library that met our needs and followed the other criteria. The following is a description of the options and my reasoning, in a rough order of how compelling I thought they were.

I’m sharing this here in case anyone finds it interesting, and since I think it’s better than keeping it as a note locally.

  1. Open CASCADE
    • The geometry kernel behind FreeCAD. I’m sure this has all of the relevant features (though it’s hard to tell exactly, since the library does quite a lot).
    • Also being looked into for work on surfaces (Better curve surface support). Though that’s not what I’m interested in at the moment, supporting proper solids in Blender in the longer term would be wonderful, especially in a procedural context.
    • The focus on geometry is definitely a plus, compared so some other libraries that focus on splines in the context of image manipulation, for example.
    • It looks like quite a bit of learning would be required just for our simple use case.
    • It’s not clear if it has a focus on performance. In fact, its large scope may be a downside in this case.
    • Conclusion: I’m not sure yet. It strikes me as complicated, but well documented from what I’ve seen so far. The scope is just way bigger than what we need at the moment.
  2. tinynurbs
    • A small header-only library.
    • Actively in development.
    • The curves seem to own their control points arrays, weights, etc, meaning we will have extra copies if using this.
    • Code looks well written and self-explanatory.
    • Conclusion: It’s not clear this is worth using, but if not, it looks like it would serve as a great point of reference.
  3. vspline
    • A “modern C++” approach, with a focus on performance with SIMD and multi-threading.
    • Well documented.
    • It’s not clear that this is a downside, but the library seems focussed on image processing use cases.
    • No support for non-uniform & rational B-splines (NURBS).
    • Rather complicated, using plenty of seemingly unique terminology (though maybe it just looks that way because it provides proper documentation).
    • Conclusion: Tempting, because of the focus on performance and the apparent abundance of features, but in the end the lack of support for NURBS and its complexity are turn-offs.
  4. tinyspline
    • Supports general NURBS, Bezier curves, B-splines.
    • Written in C89 with C++ bindings.
    • Latest commits are fairly recent.
    • Documentation is a bit lacking, and the examples don’t seem that compelling honestly.
    • Conclusion: No real benefit over using our own implementation.
  5. Boost
    • Provides a straightforward implemenation of Bezier and Catmull-Rom evaluation (not NURBS).
    • Seems to focus on performance.
    • Conclusion: Not worth using a library for these relatively simple curve types.
  6. Ayam
    • A general modeling application with support for NURBS.
    • Development looks active.
    • Doesn’t look like it’s meant to be used as a library.
    • Conclusion: Not applicable.
  7. SplineLibrary
    • Provides implementations of Catmull-Rom splines, generric B-splines, and others.
    • No support for non-uniform & rational B-splines (NURBS).
    • Last commit in 2018
    • Conclusion: No real benefit over using our own implementation.
  8. SISL
    • A general NURBS curve and surface library.
    • C rather than C++ (not templated on float type).
    • Not “modern” code (seems to use public function names like s1012 for some reason), unamed parameters in headers
    • I don’t think AGPL is compatible with Blender’s GPL license.
    • Conclusion: It looks interesting and full-featured, but even disragarding the license issue, I’m not sure using it would be helpful.
  9. GNU Scientific Library
    • The scope of the provided features isn’t clear.
    • Part of a much larger library.
    • Conclusion: Not clear enough that this would be helpful.
  10. Einspline
    • Doesn’t look actively maintained.
    • Only B-splines supported, not more general NURBS.
    • Conclusion: Not applicable.
  11. Eigen
    • The “unsupported” status makes this not a compelling choice to me.
    • The documentation isn’t very clear on the purpose of the module.
    • Conclusion: Not applicable.
  12. Scyllarus C++ API NURBS
    • Licensing isn’t clear, focus is image processing anyway.
    • Conclusion: Not applicable.
  13. openNURBS
    • Misleading naming and marketing-- this is just an implementation of I/O for Rhino’s proprietary 3DM format, not an “open” implementation of NURBS.
    • Conclusion: Not applicable.
  14. libnurbs
    • A “planned” extension of the openNURBS project, to improve the documentation apparently.
    • Not updated for 9 years.
    • Conclusion: Not applicable.
27 Likes
2

There is a pretty good Primer on GitHub about the math and implementation of Bezier and Nurbs, if it helps in any way.

I am looking for chances to contribute to having a generalised Nurbs support in Blender.

1 Like
3

Would you be interested to consider the rhino library?
– Answer: Not applicable. :slight_smile:

4

Thanks! I’ve used that in the past, when working on curve evaluation and editing for geometry nodes last year. I think the section on B-splines has been expanded since I last looked at it. That’s a great explanation.

Good to hear! There is some discussion going on over here: Better curve surface support. Generally the implementation of surfaces in Blender is quite old, and it is also stored in the same Curve data-block used for the existing/legacy curve object type. I’d push for a proper data-block for surfaces, and a bit of a rewrite.

Beyond that, I’m sure it’s possible to improve the evaluation of NURBS curves, and that would be a smaller project. If you have some time soon, and experience with C++, we’re working on evaluation for the new Curves data-block, and a better implementation of NURBS evaluation could be helpful there. Exposing the knot vector to the Python API for the new curves type is another potential thing to do soon, though it’s a bit early for that at the moment.

Yeah, beyond being proprietary, it’s also not a library, just a separate application.

5

Thank you for your reply. I was thinking that you might know this already. I was studying Pomax library for a while now. I have a little experience with code but I am not an experienced developer. In the past I was dealing with Nurbs and OBJ implementation. The documentation of OBJ is very helpful when it comes to all kinds of curve types and how they are defined in the data.

http://www.martinreddy.net/gfx/3d/OBJ.spec

Since it can become quite time intense to study all of this, I was cutting short by doing some basic tests with curves first. I was exporting curves from Alias via OBJ to get them into Blender. I checked different curve degrees (2-9 degree) and they seem to be interpret identical in both programs. The knots make some of the issues though when the intervals between them are not the same. Blender seems to ignore that information at the moment.
In Pomax’ chapter „ Manipulating the curve through the knot vector“ the issue with knot intervals is well explained. This is something to start with I could imagine.
Second would be the rational part of curves and getting into cv weights.
Besides testing the curve data I was comparing the mesh tessellation in Alias and Blender and found some general differences.
Blender tessellates the curve by the resolution of the parameter (t) value which leads to inconsistent and uncontrollable deviation. Alias‘ tessellation comes with tolerance control and max edge length for producing less mesh data in less curvy areas. I believe they are using Aruba tessellation.
I am also aware of the path animation timing. I didn’t look into this yet.
Pomax described an algorithm for tracing curves into equal length intervals. This could be a thing since it would mean consistent speed in path animations no matter where the curve points are placed.
If my research and testing is helpful in your discussion about a future data model I will carry on giving some input. I have a lot of different curve/surface/cos data/file-formats to look into.

6

Out of plain curiosity, what did you end up using ? is the choice paying off so far ?

1 Like
7

None of them actually. Using a generic library would have made code more complicated and precluded some potential performance optimizations. Also none of the libraries were generic enough to really be helpful. So I basically just ported and improved the existing curve evaluation code. There are still traces of the ~30 year old implementation from very early Blender versions in there :slight_smile:

8 Likes
8

Alright I see, thanks.

I heard code doesn’t rust !

9

Unless it’s written in Rust. Leaves

6 Likes