Splines with shared knot vectors

[Mark Stijnman]

Hi all,

This is going to be more about design issues and might get rather long,
but I was hoping some of you might have some input on this. I'm using
splines to model two-dimensional parametric curves (x(t),y(t)) to
interpolate between nodes. I have a working Spline class that does
cubic spline interpolation of function values f that are defined at
knot positions t. I use this in my current Curve class. Along with
the splines for x and y, the Curva class also has one for any other
values (say p and q) that need to be interpolated along the curve. All
Splines x, y, p and q currently have their own knot vector t and the
Curve class provides functions that ensure a certain t of all
splines only get changed all at once (in my app the t sometimes need
to change to enhance the parameter mapping of the curve). The logical
next step would be, to change the spline class so it supports sharing a
knot vector between splines - it will save storage and will guarantee
all Splines stay in sync. Also, I expect subclasses of curve to add
more interpolation variables, which will also be easier handled if it
is possible to just attach the new spline to the existing knot vector.
I think I will be able to figure out a way to handle this neatly, most
likely using smart pointers with reference counting.

Now for my dilemma: my current spline class supports a public member
mySpline.Add(t_new, f_new) to add a new interpolation value at the end
(t_new > max(t)), so splines can be built one point at a time.
Similarly, the curve class supports myCurve.Add(t_new,
x_new,y_new,p_new,q_new) and will just add the new data to the
corresponding spline. This also provides an interface to build the
curve one point at a time. I still want to provide this functionality
in the new spline class (with the shared knot vector) and obviously
retain it for the Curve class. But what should the behaviour of
mySpline.Add(...) be if mySpline uses a shared knot vector? Ideally,

x.Add(t_new, x_new); y.Add(t_new, y_new);

probably should behave the same, whether x and y share a knot vector or
just have a knot vector with equal values. However,

x.Add(t_new, x_new); y.Add(t_alternate, y_new);

probably should generate an error when the knot vectors are shared. I
imagine further that any spline that share a knot vector that is not
explicitly expanded gets expanded with a default value - or it might be
better to require all splines to be given a new value explicitely
before more points can be added.

So my question is, how can I get at such a mechanism? I assume the knot
vector object should keep track of which associated splines have been
updated and which not, but I can't get at a good mechanism to do so. Or
am I just going at this the wrong way? I hope you can give me some
ideas, thanks in advance,

best regards Mark

 

[Victor Bazarov]

[...splines sharing a vector of knots and built one point at a time...]
So my question is, how can I get at such a mechanism? I assume the knot
vector object should keep track of which associated splines have been
updated and which not, but I can't get at a good mechanism to do so. Or
am I just going at this the wrong way? I hope you can give me some
ideas, thanks in advance,

Make a separate class -- knotvector. Make your spline class to have
a pointer to a knotvector (it's called "association"). That would allow
you to share knotvectors between instances of splines. I imagine that
not all instances of the spline need to have the same knotvector, but
some may.

You should probably think a bit more about the functionality of your
system. You say that the knot vector should have a list of splines it is
associated with. I am not sure about that. If you update one of the
splines that share a knot vector and *never* update the other splines with
the same knot vector, what then? I imagine that "breaking off" one of the
splines from the set by cloning and changing its knot vector is not out of
the realm of possibilities. IOW, they share a knot vector until one of
the splines needs a different knot vector. In that case that one spline
"breaks off" with its own, now unique, knot vector. It's like "copy on
write" sort of thing.

This is marginally a language question. Try the comp.object newsgroup and
the comp.graphics.algorithms as well.

V

 

[Mark Stijnman]

[...splines sharing a vector of knots and built one point at a time...]
So my question is, how can I get at such a mechanism? I assume the knot
vector object should keep track of which associated splines have been
updated and which not, but I can't get at a good mechanism to do so. Or
am I just going at this the wrong way? I hope you can give me some
ideas, thanks in advance,

Make a separate class -- knotvector. Make your spline class to have
a pointer to a knotvector (it's called "association"). That would allow
you to share knotvectors between instances of splines. I imagine that
not all instances of the spline need to have the same knotvector, but
some may.

That was the plan indeed.

You should probably think a bit more about the functionality of your
system. You say that the knot vector should have a list of splines it is
associated with. I am not sure about that. If you update one of the
splines that share a knot vector and *never* update the other splines with
the same knot vector, what then?

Actually, changes to the knot vector render the interpolation data
useless, so the spline objects need to be notified of the change. And
about never updating the others, that's really where the trouble is
indeed.

I imagine that "breaking off" one of the
splines from the set by cloning and changing its knot vector is not out of
the realm of possibilities. IOW, they share a knot vector until one of
the splines needs a different knot vector. In that case that one spline
"breaks off" with its own, now unique, knot vector. It's like "copy on
write" sort of thing.

That might be something one would want the spline class to support,
yes. I'm still not fully convinced I'm doing the right thing by
performing the 'optimization' of allowing shared knot vectors in the
first place though, I'm still considering options.

This is marginally a language question. Try the comp.object newsgroup and
the comp.graphics.algorithms as well.

V

You are probably right, I'll have a look at comp.object. Thanks for the
response though

grtz Mark