> The problem seems to be when splitting a slow area that contains one fast 
> area and one very slow area (relatively, in pixels per second; of course 
> it's faster than the big tile it belongs to!).
>
> Any ideas? I'll post some more images later.

Why not split the image repeatedly (alternating horizontal and vertical 
splits), but for every split choose the split position so that the sum of 
pixels is the same on either side of the split.  When the sum of pixels 
reaches some minimum value, or the rectangle is some minimum size, don't 
split anymore.

Post a reply to this message