[cairo] Regression in long random polyline rendering time

[Emmanuel Pacaud]

Le vendredi 25 septembre 2009 à 22:54 +0200, M Joonas Pihlaja a écrit : 
> The example is stroking N line segments in an area of size 100 x 100 
> pixels for N up to 10000.  Things get progressively worse as N grows. 
> Previously (<= 1.8) cairo would not consider self-intersections in the 
> stroke when it was stroking lines.  In your example for N = 10000 
> random line segments, one may assume that most line segments are going 
> to intersect with most other line segments, so on average there are 
> going to be on the order of 50 million segment-segment intersections 
> in the image.  There are only 100^2 pixels in the image however so for 
> each pixel you're going to see about 5000ish intersections.  That's a 
> lot of intersections per pixel [1].

> In your particular case of using the image surface I suspect what's 
> happening is that the polygon scan converter's twiddle-an-ordered-list 
> subroutine is being exercised in new and exciting ways it's not really 
> been designed for: namely completely reshuffling the list every pixel 
> due to the high number of intersections.  The up shot of the changes 
> in 1.9 is that your stroked line segments are now more beautiful than 
> ever before!

I have another example which exhibits this regression. It consists in
drawing a noisy sinusoid y = sin (x) + rand() * noise_amplitude. You are
right, the new rendering is nicer. But sooo slow... And unfortunately,
in this case, it's something you may actually have to draw in real
life. 

> As a workaround, trading pure gorgeousness for speed, you can stroke 
> each individual line segment separately.  This brings the times for 
> cairo master vs. cairo 1.6.4 and 1.8 to about the same.  Still a bunch 
> slower than stroking everything at once with proper joins using cairo 
> <= 1.8, but not nearly as bad as what you're seeing.

An alternative that may help to keep a nice rendering could be to cut
the long polyline in smaller ones, using an intermediate surface when
the line is not completely opaque.

Anyway, I would love to not have to use workarounds at all. As well as
all the other users doing scientific plots using cairo, I guess.

Emmanuel.