Bug 691984 - Antialiasing on graphics is very slow
Summary: Antialiasing on graphics is very slow
Status: RESOLVED FIXED
Alias: None
Product: Ghostscript
Classification: Unclassified
Component: Graphics Library (show other bugs)
Version: master
Hardware: PC Linux
: P4 normal
Assignee: Robin Watts
URL: https://bugzilla.gnome.org/show_bug.c...
Keywords:
Depends on:
Blocks:
 
Reported: 2011-02-19 17:15 UTC by Andreas Becker
Modified: 2018-07-09 10:07 UTC (History)
2 users (show)

See Also:
Customer:
Word Size: ---


Attachments
eps-file that is rendered very slow when antialiasing is turned on (633.02 KB, application/postscript)
2011-02-19 17:15 UTC, Andreas Becker
Details
problem.alpha.sleepy (14.97 KB, application/octet-stream)
2011-04-08 15:02 UTC, Robin Watts
Details
problem.normal.sleepy (4.84 KB, application/octet-stream)
2011-04-08 15:03 UTC, Robin Watts
Details

Note You need to log in before you can comment on or make changes to this bug.
Description Andreas Becker 2011-02-19 17:15:03 UTC
Created attachment 7262 [details]
eps-file that is rendered very slow when antialiasing is turned on

Antialiasing with -dGraphicsAlphaBits=2 or greater is extremely slow for the attached eps file. The problem also occurs when the eps file is converted to pdf and then displayed. Poppler/evince can render the pdf file fast.
The eps file contains a diagram with many (ca. 3300) lines.

I think the antialiasing algorithm is not optimized enough in ghostscript.
Comment 1 Andreas Becker 2011-02-20 09:18:16 UTC
Sorry, the diagram contains 33000 and no only 3300 lines.
Comment 2 Hin-Tak Leung 2011-03-13 04:03:19 UTC
Re-file/assign to 'graphic library' owner since this does not appear to be an x11-specific issue.
Comment 3 Henry Stiles 2011-04-07 17:02:45 UTC
Hi Robin, maybe you could provide some "sleepy" profiling results for this one.
Comment 4 Robin Watts 2011-04-08 15:02:59 UTC
Created attachment 7439 [details]
problem.alpha.sleepy

A profile, showing that a huge amount of time is spent in the scan conversion code.
Comment 5 Robin Watts 2011-04-08 15:03:45 UTC
Created attachment 7440 [details]
problem.normal.sleepy

A profile with no antialiasing for comparison.
Comment 6 Robin Watts 2011-04-08 15:37:15 UTC
The problem here is the inate complexity of Ghostscripts scan converter, and that fact that a different job is done with and without antialiasing.

The file consists of a long path (33000 lineto's) which then gets stroked.

In the non-antialiased case, this results in the line being stroked, and every section of that line filled individually. The scan converter therefore has typically around 4 edges to worry about at a time (left, right, top and bottom of each given segment). As the scan converter runs through the edge list, it has only 2 edges 'active' at any one time.

In the antialiased case, the line is stroked entirely to give a path (naively with 33000*4 segments in it). This is then filled all at once. Because the line folds back upon itself repeatedly, we can easily have 66000 lines 'active' at once.

No simple tweaks to the code are going to get past this problem. We need a basic change to the algorithm.
Comment 7 Robin Watts 2011-04-08 15:57:13 UTC
My prototype scan converter that doesn't use an active edge list manages this file in under 2 seconds (rather than > 15 minutes). The results aren't identical, but this is probably because I've never used the prototype scan converter with the antialiasing buffers before, and there may be some kinks to work out.
Comment 8 Julian D. A. Wiseman 2015-04-07 06:19:03 UTC
Related: bug #695906
http://bugs.ghostscript.com/show_bug.cgi?id=695906 
(Added just so that the relationship isn’t lost or forgotten.)
Comment 9 Robin Watts 2018-07-09 10:07:15 UTC
This has been fixed by the new scan converter.