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