Re: [PATCH weston] gl-renderer: compress pixman bands to simplify geometry
On Wed, 19 Nov 2014 09:03:31 -0800 Jasper St. Pierre jstpie...@mecheye.net wrote: On Wed, Nov 19, 2014 at 7:22 AM, Daniel Stone dan...@fooishbar.org wrote: Hi, On 19 November 2014 14:58, Derek Foreman der...@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. Thanks, pq ___ wayland-devel mailing list wayland-devel@lists.freedesktop.org http://lists.freedesktop.org/mailman/listinfo/wayland-devel
Re: [PATCH weston] gl-renderer: compress pixman bands to simplify geometry
On Wed, 19 Nov 2014 08:58:14 -0600 Derek Foreman der...@osg.samsung.com wrote: On 19/11/14 08:33 AM, Pekka Paalanen wrote: On Thu, 16 Oct 2014 16:37:02 -0500 Derek Foreman der...@osg.samsung.com wrote: Pixman uses y-x banded rectangles to represent regions. We use these y-x banded rectangles to generate triangle fans, resulting in more geometry than strictly necessary to draw the screen. This patch combines the bands to reduce geometry for complex scenes. --- src/gl-renderer.c | 67 --- 1 file changed, 64 insertions(+), 3 deletions(-) Hi Derek, could you explain a bit where I can see the effect of this and how big an improvement it is? If you turn on triangle fan debug (something like shift+mod+space followed by f) then open a few windows you can see the difference. The easiest way is to just open two terminals, put them side by side, run yes or something that constantly refreshes one, then drag the other one up and down beside it (but far enough away that the shadows don't overlap) Before my patch you'll see extra triangles inserted where the horizontal boundaries of one window project across the other window. If you've got a copy of pixman's src lying around, the comments near the top of pixman-region.c explain how regions are split. The patch can result in a fairly dramatic reduction in polygon count in certain cases, but the smaller set of polygons will have the same coverage. Honestly, I'm not sure how to benchmark this. Oh yeah, I see it now if I use the DRM backend. On X11 backend I think it always paints everything which means the mesh is a lot more messy. One way to measure would be to print the vertex count of a repaint cycle. I'd expect the difference in performance to be negligible. I believe the only difference would be in CPU time, the overhead of submitting draws to the GPU is probably a lot more than what a few less vertices does, and the fragment count would be roughly the same anyway. Maybe it could be profiled with 'perf', since the effect should be on CPU time? There is an Acked-by from Jasper, and Tested-by me, but I'm still not sure this is worth the code it adds... to be honest, it feels like premature optimization to me. OTOH, it reduces the box-count, which reduces both calculate_edges and glDrawArrays calls, so... Pushed! Thanks, pq ___ wayland-devel mailing list wayland-devel@lists.freedesktop.org http://lists.freedesktop.org/mailman/listinfo/wayland-devel
Re: [PATCH weston] gl-renderer: compress pixman bands to simplify geometry
On 21/11/14 04:32 AM, Pekka Paalanen wrote: On Wed, 19 Nov 2014 09:03:31 -0800 Jasper St. Pierre jstpie...@mecheye.net wrote: On Wed, Nov 19, 2014 at 7:22 AM, Daniel Stone dan...@fooishbar.org wrote: Hi, On 19 November 2014 14:58, Derek Foreman der...@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... ___ wayland-devel mailing list wayland-devel@lists.freedesktop.org http://lists.freedesktop.org/mailman/listinfo/wayland-devel
Re: [PATCH weston] gl-renderer: compress pixman bands to simplify geometry
On Thu, 16 Oct 2014 16:37:02 -0500 Derek Foreman der...@osg.samsung.com wrote: Pixman uses y-x banded rectangles to represent regions. We use these y-x banded rectangles to generate triangle fans, resulting in more geometry than strictly necessary to draw the screen. This patch combines the bands to reduce geometry for complex scenes. --- src/gl-renderer.c | 67 --- 1 file changed, 64 insertions(+), 3 deletions(-) diff --git a/src/gl-renderer.c b/src/gl-renderer.c index 076c242..40447c7 100644 --- a/src/gl-renderer.c +++ b/src/gl-renderer.c @@ -25,6 +25,7 @@ #include GLES2/gl2.h #include GLES2/gl2ext.h +#include stdbool.h #include stdlib.h #include string.h #include ctype.h @@ -296,6 +297,55 @@ calculate_edges(struct weston_view *ev, pixman_box32_t *rect, return n; } +static bool +merge_down(pixman_box32_t *a, pixman_box32_t *b, pixman_box32_t *merge) +{ + if (a-x1 == b-x1 a-x2 == b-x2 a-y1 == b-y2) { + merge-x1 = a-x1; + merge-x2 = a-x2; + merge-y1 = b-y1; + merge-y2 = a-y2; + return true; + } + return false; +} + +static int +compress_bands(pixman_box32_t *inrects, int nrects, +pixman_box32_t **outrects) +{ + bool merged; + pixman_box32_t *out, merge_rect; + int i, j, nout; + + if (!nrects) { + *outrects = NULL; + return 0; + } + + /* nrects is an upper bound - we're not too worried about + * allocating a little extra + */ + out = malloc(sizeof(pixman_box32_t) * nrects); + out[0] = inrects[0]; + nout = 1; + for (i = 1; i nrects; i++) { + for (j = 0; j nout; j++) { + merged = merge_down(inrects[i], out[j], merge_rect); + if (merged) { + out[j] = merge_rect; + break; + } + } + if (!merged) { + out[nout] = inrects[i]; + nout++; + } + } + *outrects = out; + return nout; +} + static int texture_region(struct weston_view *ev, pixman_region32_t *region, pixman_region32_t *surf_region) @@ -306,11 +356,20 @@ texture_region(struct weston_view *ev, pixman_region32_t *region, GLfloat *v, inv_width, inv_height; unsigned int *vtxcnt, nvtx = 0; pixman_box32_t *rects, *surf_rects; - int i, j, k, nrects, nsurf; - - rects = pixman_region32_rectangles(region, nrects); + pixman_box32_t *raw_rects; + int i, j, k, nrects, nsurf, raw_nrects; + bool used_band_compression; + raw_rects = pixman_region32_rectangles(region, raw_nrects); surf_rects = pixman_region32_rectangles(surf_region, nsurf); + if (raw_nrects 4) { + used_band_compression = false; + nrects = raw_nrects; + rects = raw_rects; + } else { + nrects = compress_bands(raw_rects, raw_nrects, rects); + used_band_compression = true; + } /* worst case we can have 8 vertices per rect (ie. clipped into * an octagon): */ @@ -369,6 +428,8 @@ texture_region(struct weston_view *ev, pixman_region32_t *region, } } + if (used_band_compression) + free(rects); return nvtx; } Hi Derek, could you explain a bit where I can see the effect of this and how big an improvement it is? Thanks, pq ___ wayland-devel mailing list wayland-devel@lists.freedesktop.org http://lists.freedesktop.org/mailman/listinfo/wayland-devel
Re: [PATCH weston] gl-renderer: compress pixman bands to simplify geometry
On 19/11/14 08:33 AM, Pekka Paalanen wrote: On Thu, 16 Oct 2014 16:37:02 -0500 Derek Foreman der...@osg.samsung.com wrote: Pixman uses y-x banded rectangles to represent regions. We use these y-x banded rectangles to generate triangle fans, resulting in more geometry than strictly necessary to draw the screen. This patch combines the bands to reduce geometry for complex scenes. --- src/gl-renderer.c | 67 --- 1 file changed, 64 insertions(+), 3 deletions(-) diff --git a/src/gl-renderer.c b/src/gl-renderer.c index 076c242..40447c7 100644 --- a/src/gl-renderer.c +++ b/src/gl-renderer.c @@ -25,6 +25,7 @@ #include GLES2/gl2.h #include GLES2/gl2ext.h +#include stdbool.h #include stdlib.h #include string.h #include ctype.h @@ -296,6 +297,55 @@ calculate_edges(struct weston_view *ev, pixman_box32_t *rect, return n; } +static bool +merge_down(pixman_box32_t *a, pixman_box32_t *b, pixman_box32_t *merge) +{ +if (a-x1 == b-x1 a-x2 == b-x2 a-y1 == b-y2) { +merge-x1 = a-x1; +merge-x2 = a-x2; +merge-y1 = b-y1; +merge-y2 = a-y2; +return true; +} +return false; +} + +static int +compress_bands(pixman_box32_t *inrects, int nrects, + pixman_box32_t **outrects) +{ +bool merged; +pixman_box32_t *out, merge_rect; +int i, j, nout; + +if (!nrects) { +*outrects = NULL; +return 0; +} + +/* nrects is an upper bound - we're not too worried about + * allocating a little extra + */ +out = malloc(sizeof(pixman_box32_t) * nrects); +out[0] = inrects[0]; +nout = 1; +for (i = 1; i nrects; i++) { +for (j = 0; j nout; j++) { +merged = merge_down(inrects[i], out[j], merge_rect); +if (merged) { +out[j] = merge_rect; +break; +} +} +if (!merged) { +out[nout] = inrects[i]; +nout++; +} +} +*outrects = out; +return nout; +} + static int texture_region(struct weston_view *ev, pixman_region32_t *region, pixman_region32_t *surf_region) @@ -306,11 +356,20 @@ texture_region(struct weston_view *ev, pixman_region32_t *region, GLfloat *v, inv_width, inv_height; unsigned int *vtxcnt, nvtx = 0; pixman_box32_t *rects, *surf_rects; -int i, j, k, nrects, nsurf; - -rects = pixman_region32_rectangles(region, nrects); +pixman_box32_t *raw_rects; +int i, j, k, nrects, nsurf, raw_nrects; +bool used_band_compression; +raw_rects = pixman_region32_rectangles(region, raw_nrects); surf_rects = pixman_region32_rectangles(surf_region, nsurf); +if (raw_nrects 4) { +used_band_compression = false; +nrects = raw_nrects; +rects = raw_rects; +} else { +nrects = compress_bands(raw_rects, raw_nrects, rects); +used_band_compression = true; +} /* worst case we can have 8 vertices per rect (ie. clipped into * an octagon): */ @@ -369,6 +428,8 @@ texture_region(struct weston_view *ev, pixman_region32_t *region, } } +if (used_band_compression) +free(rects); return nvtx; } Hi Derek, could you explain a bit where I can see the effect of this and how big an improvement it is? If you turn on triangle fan debug (something like shift+mod+space followed by f) then open a few windows you can see the difference. The easiest way is to just open two terminals, put them side by side, run yes or something that constantly refreshes one, then drag the other one up and down beside it (but far enough away that the shadows don't overlap) Before my patch you'll see extra triangles inserted where the horizontal boundaries of one window project across the other window. If you've got a copy of pixman's src lying around, the comments near the top of pixman-region.c explain how regions are split. The patch can result in a fairly dramatic reduction in polygon count in certain cases, but the smaller set of polygons will have the same coverage. Honestly, I'm not sure how to benchmark this. 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... ___ wayland-devel mailing list wayland-devel@lists.freedesktop.org http://lists.freedesktop.org/mailman/listinfo/wayland-devel
Re: [PATCH weston] gl-renderer: compress pixman bands to simplify geometry
Hi, On 19 November 2014 14:58, Derek Foreman der...@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. Cheers, Dan ___ wayland-devel mailing list wayland-devel@lists.freedesktop.org http://lists.freedesktop.org/mailman/listinfo/wayland-devel
Re: [PATCH weston] gl-renderer: compress pixman bands to simplify geometry
On Wed, Nov 19, 2014 at 7:22 AM, Daniel Stone dan...@fooishbar.org wrote: Hi, On 19 November 2014 14:58, Derek Foreman der...@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 Cheers, Dan ___ wayland-devel mailing list wayland-devel@lists.freedesktop.org http://lists.freedesktop.org/mailman/listinfo/wayland-devel -- Jasper ___ wayland-devel mailing list wayland-devel@lists.freedesktop.org http://lists.freedesktop.org/mailman/listinfo/wayland-devel
[PATCH weston] gl-renderer: compress pixman bands to simplify geometry
Pixman uses y-x banded rectangles to represent regions. We use these y-x banded rectangles to generate triangle fans, resulting in more geometry than strictly necessary to draw the screen. This patch combines the bands to reduce geometry for complex scenes. --- src/gl-renderer.c | 67 --- 1 file changed, 64 insertions(+), 3 deletions(-) diff --git a/src/gl-renderer.c b/src/gl-renderer.c index 076c242..40447c7 100644 --- a/src/gl-renderer.c +++ b/src/gl-renderer.c @@ -25,6 +25,7 @@ #include GLES2/gl2.h #include GLES2/gl2ext.h +#include stdbool.h #include stdlib.h #include string.h #include ctype.h @@ -296,6 +297,55 @@ calculate_edges(struct weston_view *ev, pixman_box32_t *rect, return n; } +static bool +merge_down(pixman_box32_t *a, pixman_box32_t *b, pixman_box32_t *merge) +{ + if (a-x1 == b-x1 a-x2 == b-x2 a-y1 == b-y2) { + merge-x1 = a-x1; + merge-x2 = a-x2; + merge-y1 = b-y1; + merge-y2 = a-y2; + return true; + } + return false; +} + +static int +compress_bands(pixman_box32_t *inrects, int nrects, + pixman_box32_t **outrects) +{ + bool merged; + pixman_box32_t *out, merge_rect; + int i, j, nout; + + if (!nrects) { + *outrects = NULL; + return 0; + } + + /* nrects is an upper bound - we're not too worried about +* allocating a little extra +*/ + out = malloc(sizeof(pixman_box32_t) * nrects); + out[0] = inrects[0]; + nout = 1; + for (i = 1; i nrects; i++) { + for (j = 0; j nout; j++) { + merged = merge_down(inrects[i], out[j], merge_rect); + if (merged) { + out[j] = merge_rect; + break; + } + } + if (!merged) { + out[nout] = inrects[i]; + nout++; + } + } + *outrects = out; + return nout; +} + static int texture_region(struct weston_view *ev, pixman_region32_t *region, pixman_region32_t *surf_region) @@ -306,11 +356,20 @@ texture_region(struct weston_view *ev, pixman_region32_t *region, GLfloat *v, inv_width, inv_height; unsigned int *vtxcnt, nvtx = 0; pixman_box32_t *rects, *surf_rects; - int i, j, k, nrects, nsurf; - - rects = pixman_region32_rectangles(region, nrects); + pixman_box32_t *raw_rects; + int i, j, k, nrects, nsurf, raw_nrects; + bool used_band_compression; + raw_rects = pixman_region32_rectangles(region, raw_nrects); surf_rects = pixman_region32_rectangles(surf_region, nsurf); + if (raw_nrects 4) { + used_band_compression = false; + nrects = raw_nrects; + rects = raw_rects; + } else { + nrects = compress_bands(raw_rects, raw_nrects, rects); + used_band_compression = true; + } /* worst case we can have 8 vertices per rect (ie. clipped into * an octagon): */ @@ -369,6 +428,8 @@ texture_region(struct weston_view *ev, pixman_region32_t *region, } } + if (used_band_compression) + free(rects); return nvtx; } -- 2.1.1 ___ wayland-devel mailing list wayland-devel@lists.freedesktop.org http://lists.freedesktop.org/mailman/listinfo/wayland-devel