Bug 2343

Created attachment 1727 [details]
snippet demonstration of problem

Maybe just draw a solid line with opacity set to the dash pattern
coverage, if we can detect when things have gotten small enough
for that?

That sounds like a fine plan. We can take the maximum single length from the
dash sequence, (either drawn or not), and compute its maximum size in device
space. (We should have code for that part in cairo_pen.c).

Then if that length is less than the tolerance, multiplying the current alpha
by the percentage of the dash sequence that's lit, then stroking a solid line
should be sufficient.

There's still the larger issue about how to deal with unexpected slow response
time from the library. I don't know the right answer for that, and we might
want to take it up on the list. The denial-of-service opportunity in the library
will certainly be a concern for some users.

Created attachment 2264 [details] [review]
patch for review

The high-level logic in the patch looks just fine.

I'd like to see a couple of changes to _dashes_invisble:

1) If we're sharing expansion arithmetic with cairo_pen.c then we should put
   it into a named, shared, and commented function.

2) I'd like to see a comment justifying the threshold value, (currently 0.5f).
   The criteria here is that the scaled dash pattern should be equivalent to
   the single alpha value, (ie. I don't want sudden, harsh transitions when
   zooming).

Actually, on further consideration, a threshold test on the length of the
maximal (transformed) dash segment cannot be adequate. Given any threshold
value, I can construct a dash pattern entirely of segments smaller than the
threshold that results in alternating fully-lit and fully-unlit pixels,
(particularly if I can include zero-length segments).

Granted, that's a rather degenerate pattern, but I can't prove that similar
issues don't appear in more conventional dash patterns.

One approach that would work is a sliding integral over the pattern with a
1-pixel-wide window, checking for a constant value at every position, (after
rounding based on the maximum 8-bit alpha depth).

(In reply to comment #5)
> The high-level logic in the patch looks just fine.
> 
> I'd like to see a couple of changes to _dashes_invisble:
> 
> 1) If we're sharing expansion arithmetic with cairo_pen.c then we should put
>    it into a named, shared, and commented function.

Ok, I'll see about doing that.  Note that the minimal expansion that we're using
is a conservative test, and will sometimes tell us to use a solid line when a
dashed one would still be appropriate.  Think of a extremely nonlinear scaling
and drawing both a horizontal and vertical line.

> 2) I'd like to see a comment justifying the threshold value, (currently 0.5f).
>    The criteria here is that the scaled dash pattern should be equivalent to
>    the single alpha value, (ie. I don't want sudden, harsh transitions when
>    zooming).

It's an optimistic application of the sampling limit.

> Actually, on further consideration, a threshold test on the length of the
> maximal (transformed) dash segment cannot be adequate. Given any threshold
> value, I can construct a dash pattern entirely of segments smaller than the
> threshold that results in alternating fully-lit and fully-unlit pixels,
> (particularly if I can include zero-length segments).

True, but the extra work being done will be a factor of O(number of dasharray
elements), which is better than the current unbounded work.

(In reply to comment #6)
> Ok, I'll see about doing that.  Note that the minimal expansion that we're using
> is a conservative test, and will sometimes tell us to use a solid line when a
> dashed one would still be appropriate.  Think of a extremely nonlinear scaling
> and drawing both a horizontal and vertical line.

Ah, we should change that then. I'm really not interested in performance
optimizations that give the wrong answer.

> True, but the extra work being done will be a factor of O(number of dasharray
> elements), which is better than the current unbounded work.

Yeah, I'm not worried about any work that's linear in the number of dash
segments. That's all still constant with respect to the length of the path. 

> Ah, we should change that then. I'm really not interested in performance
> optimizations that give the wrong answer.

From my point of view, I'm really not interested in allowing trivial SVG to
perform a denial of service attack on mozilla and am willing to take a visual
quality hit in extreme circumstances for now.  Thus I'll probably be landing a
version of this patch in the mozilla cairo fork in the near future.

For straight lines, the threshold can be checked along the slope of the line,
but if the code for dashing beziers is ever written things become much less clear.

Created attachment 2277 [details] [review]
split expansion calculation off

Move bugs against "cvs" version to "0.9.3" so we can remove the "cvs" version.

While this ancient-ish bug seems to be still present, it is reduced to the scale of seconds (instead of the original minutes). The provided patch doesn't apply anymore, so it would need forward-porting, but I guess it might be more sensible to look at the current situation freshly given that the patch introduces (how ever slight) correctness regression.

To help that, I'll attach a sysprof "screenshot" of the major offenders when running the test code.

Created attachment 10557 [details]
Profile of stroking extreme dashing

Moved to todo.