[cairo] status of dashed curve_to ?

[Carl Worth]

On Tue, 31 May 2005 14:48:59 -0400, John Ellson wrote:
> Are self-intersecting polylines dealt with now?

No, they are currently giving the wrong answer.

I've just added a test (cairo/test/self-intersecting.c) to demonstrate
the problem. Here's the blurb from the test:

 * 2005-06-01  Carl Worth  <cworth at cworth.org>
 *
 *   There's a long-standing bug in that self-intersecting paths give
 *   an incorrect result when stroked. The problem is that the
 *   trapezoids are generated incrementally along the stroke and as
 *   such, are not disjoint. The errant intersections of these
 *   trapezoids then leads to overfilled pixels.
 *
 *   The test belows first creates and fills a path. Then it creates a
 *   second path which has a stroked boundary identical to the first
 *   filled path. But the results of the two operations are
 *   different. The most obvious difference is in the central region
 *   where the entire path intersects itself. But notice that every
 *   time the path turns there are also errors on the inside of the
 *   turn, (since the subsequent trapezoids along the path intersect).

Since the error only occurs in pixels along antialiased edges of the
shape it is subtle, but it is observable.

Here's a zoomed-in look at the results from the test. The top portion
is the correctly filled shape, while the bottom portion is the stroked
version with the errors.

> So I guess I'm asking if _cairo_stroker_curve_to() couldn't just convert 
> the bezier segment to a sequence
> of _cairo_stroker_line_to() with round[*] joins (and similarly for the 
> dashed versions) and that should be it?

There should be some unification of the code here, but
_cairo_stroker_line_to doesn't do everything we want here. One problem
it has is the incremental trapezoid generation, (described above).
Another problem is all the arithmetic it performs, (see _compute_face
which has sqrt and lots of division). I don't think we'll want to push
every segment of every spline through all of that, (though we will
have to handle the extra faces from dashing one way or another).

> [*]  At the tolerance level of straight line segments approximating the 
> bezier, why wouldn't miter joins
> be sufficient?

Ah, this is the interesting part.

Given an infinitely thin spline, it is quite straightforward to
approximate that spline by a series of line segments such that the
approximation error is guaranteed to be less than a given
tolerance. (See _cairo_spline_decompose which does exactly that.)

The problem comes when stroking this approximation with a circular pen
of finite width. The radius of the pen will result in greater errors
at the stroke boundary than in the original approximation of the
spline. Given an arbitrarily small tolerance for the spline
approximation, a sufficiently large radius can be chosen such that the
error at the stroke boundary exceeds that tolerance, (ignoring the
case of a degenerate spline that is approximated exactly by a single
line segment).

The following thought experiment should demonstrate the problem quite
clearly by constructing a worst-case scenario.

Imagine a stroked cubic spline with a nice smooth loop in it. Now
imagine adjusting that spline so that the loop shrinks. As the loop
gets smaller, fewer line segments will be needed in the approximation
of the looping portion of the spline. Eventually, there is a point
where the loop will have just disappear, (eg. the tangent of the
spline is spinning around with no change in the spline position). At
this point, the approximation of the spline needs no segments at all
in order to accurately capture this portion of the spline. But the
stroked version still needs an arbitrarily large number of segments in
order to capture the smooth curve as the spline changes direction.

The solution that cairo has for this problem is the notion of the
convolution of polygonal tracings[*] which Lyle Ramshaw guided us
to. The idea is that a polygonal approximation of the pen can be
convolved with the polygonal approximation of the path and yield the
correct result. In effect, an arbitrarily accurate approximation to
the composition of a quadratic and a cubic function can be found by a
linear combination of linear approximations to each function.

So, that's the theory here.

As for what the code should actually do, we definitely want the stroke
code for both splines and lines to go through:

	path -> stroke_path -> fill

(And when we have that we'll also be able to provide
cairo_stroke_to_path in the public interface). We may want to unify
splines and lines around convolution, (eg. selecting the proper pen
vertex while stroking). This has a couple of benefits:

  * It's more efficient than what's currently done for stroking lines.

  * Round joins fall out automatically.

But dashing does complicate things a bit. We don't yet have code to
integrate dashing with convolution, and the convolution won't
automatically put faces in the right place for the dashes. With the
current spline convolution code we are add 4 extra points to the pen
to guarantee that precise initial and final faces fall out from the
convolution. Maybe we could just adjust the computation in
_cairo_pen_vertices_needed so that it will guarantee that any dash
faces are accurate within the tolerance value.

*phew* I hadn't meant to type that much. Hopefully I haven't scared
you away from contributing any code here. I'm quite sure that the
work is actually much simpler than I made things sound here.

-Carl

[*] Leo Guibas, Lyle Ramshaw, and Jorge Stolfi.
    A kinetic framework for computational geometry.
    In Proceedings of the IEEE 1983 24th Annual Symposium on the
    Foundations of Computer Science, pages 100-111. IEEE Computer
    Society Press, 1983.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: not available
Url : http://lists.freedesktop.org/archives/cairo/attachments/20050601/5730473a/attachment.pgp