Comment 4 for bug 188849

Revision history for this message
RM (rm-launchpad) wrote :

Ok, here's a little more detail. The way the interpolation works is
by fixing the endpoints at two mouse points and possibly fixing the
direction of the first tangent as well if there were previous curves
(to ensure continuity)[1]. That leaves one or both tangent points
free which are then used to minimize the squared distance between the
cubic line and the mouse points between the two endpoints.

Because the two endpoints are fixed, the selection of these end points
becomes very important.

Imagine three mouse points x0, ..., x1, ..., x2, (in order of
increasing parameter t) in a series. Assume Q0 is a least-squares
interpolated curve between x0 and x1, and Q1 between x0 and x2.

In general it may be the case that:

least_squares_error(Q0) > tolerance > least_squares_error(Q1)

That is to say: if we only used x1 as the final endpoint, it would
exceed the tolerance and force a knot to be inserted in the path and a
new curve started. However, if we had waited until we had x2, we
could have had a longer curve Q1, which would include x1 and still be
within the error tolerance.

This would tend to lead to fewer cubic segments, and smoother overall
results.

The code change would defer interpolation until all the points have
been input (on button release).

I'll have to look at the algorithm again to make sure i'm thinking
along the right lines, but i don't have a copy of Graphic Gems I.

[0] I have reservations about unconditionally fixing the direction of
the tangent, but whatever....