Support custom NURBS knot vectors #99891

New Issue

Hans Goudey · 2022-07-21T17:35:35+02:00

Hans Goudey commented

2022-07-21 17:35:35 +02:00

Knot vectors describe which control points influence sections of the evaluated points for NURBS curves. The initial implementation of the new curves type doesn't support custom knot vectors because they are often computed automatically anyway, and it wasn't obvious how to store them efficiently.

A new knots_mode type should be added, NURBS_KNOT_MODE_CUSTOM, which could use knot values imported from other software, manually edited by the user, or adjusted by operations. Ideally the knot vectors would be stored as an optional builtin attribute. However, since more knot values are needed than the number of points, it isn't clear exactly how to store it.

Knot vectors describe which control points influence sections of the evaluated points for NURBS curves. The initial implementation of the new curves type doesn't support custom knot vectors because they are often computed automatically anyway, and it wasn't obvious how to store them efficiently. A new `knots_mode` type should be added, `NURBS_KNOT_MODE_CUSTOM`, which could use knot values imported from other software, manually edited by the user, or adjusted by operations. Ideally the knot vectors would be stored as an optional builtin attribute. However, since more knot values are needed than the number of points, it isn't clear exactly how to store it.

Hans Goudey commented

2022-07-21 17:35:35 +02:00

Changed status from 'Needs Triage' to: 'Confirmed'

Hans Goudey commented

2022-07-21 17:35:35 +02:00

Added subscriber: @HooglyBoogly

Laurynas Duburas commented

2024-10-09 16:55:12 +02:00

NURBS knot vector storage in the Point domain proposal.

To explain it is easiest to start from clamped (Endpoint) non cyclic case.
Order 4 curve with n control points has knot structure is
[ k0 = 0, k1 = 0, k2 = 0, k3 = 0, k4, k5, ..., kn, kn, kn, kn] with length (n + order).
Step 1.
Last 3 knots can easily be dropped without loss of information.
This leaves us with [ k0 = 0, k1 = 0, k2 = 0, k3 = 0, k4, k5, ..., kn] (n + 1) values.
Step 2.
Store not knot values, but distances between adjacent knots.
[k1 - k0 = 0, k2 - k1 = 0, k3 - k2 = 0, k4 - k3, ..., kn - kn_1].
We get n values with a cost of loosing k0.
k0 is unimportant as basis functions use only distances between knot values.
So it can always to be 0.
And this is what was needed knot vector expressed as n values.

Cyclic case.
It isn't affected by this transformation as it's knot vector tail is already calculated from the head.
[ k0, k1, k2, k3, k4, k5, ..., kn + (k0 - k0), kn + (k1 - k0), kn + (k2 - k0), kn + (k3 - k0)]
This actualy covers and clamped case examined above, leading to same code for clamped and cyclic.
[ k0 = 0, k1 = 0, k2 = 0, k3 = 0, k4, k5, ..., kn + (k0 - k0), kn + (k1 - k0), kn + (k2 - k0), kn + (k3 - k0)]
equals
[ 0, 0, 0, 0, k4, k5, ..., kn, kn, kn, kn].

Bezier cases.
It is solved by the same formula from above as distances in the tail matches distances in the head.
https://archive.blender.org/developer/file/12814/12814512/nurbs_knots.png

Non clamped (Non Endpoint) case.
This is trickier. Blender's non clamped curves have evenly spaced knots and same formula from above applies.
For the future tools modifying knots I see only ones affecting knot values in the interval
[k3, .., kn] (order is 4 here) as only into it geometry of a curve can be mapped.
I would expect other packages also to have uniformly spaced both endings of the knot vector.
If some doesn't their knots can be clamped on import without curve geometry changes.
Though control points would change and re importing back would give same curve geometry with changed control points and changed knots.

### NURBS knot vector storage in the Point domain proposal. ![shrink_knots.png](/attachments/8d5f1aeb-381e-4c00-96c7-244515af1635) To explain it is easiest to start from clamped (Endpoint) non cyclic case. Order 4 curve with n control points has knot structure is `[ k0 = 0, k1 = 0, k2 = 0, k3 = 0, k4, k5, ..., kn, kn, kn, kn]` with length `(n + order)`. Step 1. Last 3 knots can easily be dropped without loss of information. This leaves us with `[ k0 = 0, k1 = 0, k2 = 0, k3 = 0, k4, k5, ..., kn]` `(n + 1)` values. Step 2. Store not knot values, but distances between adjacent knots. `[k1 - k0 = 0, k2 - k1 = 0, k3 - k2 = 0, k4 - k3, ..., kn - kn_1]`. We get n values with a cost of loosing `k0`. `k0` is unimportant as basis functions use only distances between knot values. So it can always to be `0`. And this is what was needed knot vector expressed as `n` values. Cyclic case. It isn't affected by this transformation as it's knot vector tail is already calculated from the head. `[ k0, k1, k2, k3, k4, k5, ..., kn + (k0 - k0), kn + (k1 - k0), kn + (k2 - k0), kn + (k3 - k0)]` This actualy covers and clamped case examined above, leading to same code for clamped and cyclic. `[ k0 = 0, k1 = 0, k2 = 0, k3 = 0, k4, k5, ..., kn + (k0 - k0), kn + (k1 - k0), kn + (k2 - k0), kn + (k3 - k0)]` equals `[ 0, 0, 0, 0, k4, k5, ..., kn, kn, kn, kn]`. Bezier cases. It is solved by the same formula from above as distances in the tail matches distances in the head. https://archive.blender.org/developer/file/12814/12814512/nurbs_knots.png Non clamped (Non Endpoint) case. This is trickier. Blender's non clamped curves have evenly spaced knots and same formula from above applies. For the future tools modifying knots I see only ones affecting knot values in the interval `[k3, .., kn]` (order is 4 here) as only into it geometry of a curve can be mapped. I would expect other packages also to have uniformly spaced both endings of the knot vector. If some doesn't their knots can be clamped on import without curve geometry changes. Though control points would change and re importing back would give same curve geometry with changed control points and changed knots.

shrink_knots.png

404 KiB

👍 2

Iliya Katushenock removed the

labels 2024-10-10 18:17:46 +02:00

Iliya Katushenock added this to the Nodes & Physics project 2024-10-10 18:17:49 +02:00

Iliya Katushenock added