Bug 2343

Summary: Extreme scaling of dashed line takes a long time
Product: cairo Reporter: tor
Component: generalAssignee: tor
Status: RESOLVED FIXED QA Contact: cairo-bugs mailing list <cairo-bugs>
Severity: normal    
Priority: high CC: billy.biggs, cworth, jwatt
Version: 0.9.3   
Hardware: x86 (IA32)   
OS: Linux (All)   
Whiteboard:
i915 platform: i915 features:
Attachments: snippet demonstration of problem
patch for review
split expansion calculation off
Profile of stroking extreme dashing

Description tor 2005-01-20 14:30:23 UTC
Drawing a dashed line with extreme scaling as done in the attached
snippet takes on the order of minutes, and could easily be increased
by modifying the parameters.  I'm not sure what the appropriate action
to take when this sort of thing happens, but I'd think the library
user would appreciate some sort of bail-out since this sort of thing
could be triggered by external input, such as the SVG file I was dealing
with when this happened.
Comment 1 tor 2005-01-20 14:31:15 UTC
Created attachment 1727 [details]
snippet demonstration of problem
Comment 2 tor 2005-01-20 14:42:53 UTC
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?
Comment 3 Carl Worth 2005-01-20 18:37:55 UTC
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.
Comment 4 tor 2005-03-30 14:31:15 UTC
Created attachment 2264 [details] [review]
patch for review
Comment 5 Carl Worth 2005-03-30 15:42:17 UTC
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).
Comment 6 tor 2005-03-31 09:17:32 UTC
(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.
Comment 7 Carl Worth 2005-03-31 10:30:43 UTC
(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. 
Comment 8 tor 2005-03-31 11:21:54 UTC
> 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.
Comment 9 tor 2005-03-31 11:22:45 UTC
Created attachment 2277 [details] [review]
split expansion calculation off
Comment 10 Carl Worth 2005-08-22 17:14:17 UTC
Move bugs against "cvs" version to "0.9.3" so we can remove the "cvs" version.
Comment 11 Kalle Vahlman 2007-07-02 09:14:01 UTC
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.


Comment 12 Kalle Vahlman 2007-07-02 09:16:12 UTC
Created attachment 10557 [details]
Profile of stroking extreme dashing
Comment 13 Chris Wilson 2008-10-08 06:40:25 UTC
Moved to todo.

Use of freedesktop.org services, including Bugzilla, is subject to our Code of Conduct. How we collect and use information is described in our Privacy Policy.