Pencil interpolation change

Thanks for the patch! Could you explain in a little more detail about the issue this addresses? (Are there already other bug reports in launchpad describing the issues?)

here is an example:

http://arcsin.org/temp/Screenshot-3.png

these two curves are composed of the exact same mouse points at the same tolerance. the only difference is that
in the first curve, the interpolation is done on the fly, and the second, afterwards.

basically it's a difference in how much look-ahead the interpolation algorithm has access to. the more it has, the better can interpolate the set of points overall.

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....

Thanks for explaining it in more detail

Bulia, would you mind looking at this patch for 0.47?

thanks, and sorry for the delay with reviewing it! two things:

- can you please update the patch to reflect the recent changes with SPCurve interface - it has been migrated to 2geom and sp_curve_unref etc. don't compile now

- I'm not happy about pvt_concat_colors_and_flush - can you try to avoid that much code duplication and only code those parts that need to be changed? or maybe make the change in the function in drawing-context directly?

So, will you please update the patch as detailed above? I promise to commit it ASAP after that. Otherwise you may miss the 0.47 window, I would hate to lose this patch because of these issues.

1. can you give me a general idea about when a freeze will happen?
2. ok on 2geom
3. concerning pvt_concat_colors_and_flush:

iirc, the color business was only necessary to show one color for those points that had already been interpolated, and another for that part of the line which was yet to be interpolated.

since the patch defers interpolation until the mouse is un-clicked, this is no longer necessary: all points will be interpolated at the same time. the reason i duplicated it was because it shouldn't do anything, but (again iirc) i was a bit unsure how best to extricate the old code paths (and memory allocations).

if i need help going over the code who would be familiar with it?

On Tue, Oct 28, 2008 at 12:16 PM, RM <email address hidden> wrote:
> 1. can you give me a general idea about when a freeze will happen?

No date set, but this may be within a month or two, with release in early 2009

> 2. ok on 2geom
> 3. concerning pvt_concat_colors_and_flush:
>
> iirc, the color business was only necessary to show one color for those
> points that had already been interpolated, and another for that part of
> the line which was yet to be interpolated.
>
> since the patch defers interpolation until the mouse is un-clicked,
> this is no longer necessary: all points will be interpolated at the same
> time. the reason i duplicated it was because it shouldn't do anything,
> but (again iirc) i was a bit unsure how best to extricate the old code
> paths (and memory allocations).
>
> if i need help going over the code who would be familiar with it?

Be bold :) and delete any code which you think is not needed with
your changes. You can ask me if you have any questions on the code.

ok here's another crack at the patch.

this one is setup such that,

- while the line is being drawn, the only change is that all the points are stored in a new array and the interpolation in fit_and_split is done with a tolerance of 0.
- when the mouse is released, the initial curve is removed and a new curve is interpolated using all the points (using code similar to fit_and_split)

note:
- the old mechanism (using the 16 Point array) is basically unchanged and is used to draw the temporary curve as before. i don't really see a big need to change it.
- we use stl::vector<Geom::Point> to store all the mouse points (could use glib's stuff here though)
- the range of the GUI slider for the smoothing tolerance may need adjustment, since interpolation with all points results in a smoother curve at a given tolerance than on-the-fly interpolation.

Thanks - i added the change to pencil-context.h which you forgot to include into the patch, and readjusted the toerance range. Please test, and thanks for the contribution!