[PATCH weston] gl-renderer: compress pixman bands to simplify geometry

[Derek Foreman]

On 21/11/14 04:32 AM, Pekka Paalanen wrote:
> On Wed, 19 Nov 2014 09:03:31 -0800
> "Jasper St. Pierre" <jstpierre at mecheye.net> wrote:
> 
>> On Wed, Nov 19, 2014 at 7:22 AM, Daniel Stone <daniel at fooishbar.org> wrote:
>>
>>> Hi,
>>>
>>> On 19 November 2014 14:58, Derek Foreman <derekf at osg.samsung.com> wrote:
>>>
>>>> Since we're sort of on the topic, is there anywhere we gain anything
>>>> from y-x banded regions?  I'm wondering if it would be worthwhile to
>>>> replace pixman's region code with something that doesn't band.  I think
>>>> this would let us drop the pixman dependency when not building the
>>>> pixman renderer...
>>>
>>>
>>> Not really, no. Pixman only does it because the X server requires regions
>>> to be marked as YX-banded to be deigned valid (or 'complete', as an FBO
>>> analogy), and a number of the rendering algorithms in the server depend on
>>> it.
>>>
>>> We don't have any of that, so can happily do without banding. A patch to
>>> Pixman which would optionally drop the strict banding would be nice, but if
>>> there's a small enough region implementation we could use instead, that
>>> could work.
>>>
>>
>> It's more that the algorithms for combining regions only work in the case
>> where you have a vertically-sorted list of horizontal bands. So, you would
>> have to come up with an entirely new algorithm for pixman_region_union,
>> pixman_region_subtract, etc. if want some other format.
>>
>> What's the format you're suggesting? If we flip the axes (horizontally
>> sorted list of vertical bands), then it will work fine for the move up/down
>> case, but break for the left/right case.
>>
>> Derek's approach of post-processing the bands to make a minimal set of
>> overall rectangles seems fine to me.
>>
>> If we only need union, then we could very simply create our own region
>> class that did what we wanted. [0]
>>
>> [0] Or steal
>> http://cgit.freedesktop.org/plymouth/tree/src/libply/ply-region.c
> 
> $ git grep -E 'pixman_region.._.+\(' | egrep -o 'pixman_region.._.+\(' | sort | uniq -c | sort -n
>       1 pixman_region32_contains_point (
>       1 pixman_region32_equal(
>       1 pixman_region32_init_rects(
>       1 pixman_region32_translate(&final_region, (int)view_x, (
>       3 pixman_region32_init_with_extents(
>       3 pixman_region32_intersect_rect(
>       8 pixman_region32_clear(
>      10 pixman_region32_contains_point(
>      12 pixman_region32_translate(
>      14 pixman_region32_intersect(
>      15 pixman_region32_extents(
>      15 pixman_region32_rectangles(
>      15 pixman_region32_union(
>      15 pixman_region32_union_rect(
>      17 pixman_region32_not_empty(
>      23 pixman_region32_subtract(
>      25 pixman_region32_copy(
>      26 pixman_region32_init_rect(
>      63 pixman_region32_init(
>      88 pixman_region32_fini(
> 
> We even have wl_region.subtract in the core protocol, so union only is
> not enough.

Yup, we've got union, subtract and intersect.  It's possible that all
our intersection usage is region + rect or region + region containing a
single rect.  I'm not sure if this lack of generality makes anything
easier though.

Jasper's link is a great start, shame about the license.

Some internal discussion over here has turned up some resentment towards
the pixman dependency, so I think re-implementing the region code can
have a couple of benefits:
Losing the y-x bandedness
Losing the pixman dependency (when not building the pixman renderer)

If there's any interest, I'm willing to code it up and see how it turns
out - should be pretty easy to make a test case that links pixman and
does identical (random) operations with both implementations to test
correctness, performance, and resulting number of regions...