[cairo] patch for cairo_traps_extract_region
Behdad Esfahbod
behdad at behdad.org
Mon Jun 18 12:26:11 PDT 2007
On Wed, 2007-06-13 at 20:03 -0400, Vladimir Vukicevic wrote:
> The current implementation of cairo_traps_extract_region calls union()
> in a loop to add subsequent rectangles. This adds a new pixregion
> method to take a passed-in array of rectangles, initialize the region,
> and then call validate() on that region.
>
> One thing I'm not clear on... pixman_region_validate returns a variable
> indicating whether any of the rectangles overlapped; if they did, does
> it fix the overlaps and just return the flag to let you know?
Check the code? :) Or test!
> Right now
> I assume that it leaves in overlaps and just bail out of the
> optimization if there are any overlapping rects, but I believe Carl
> mentioned that the tessellator can potentially return overlapping traps...
Not sure about tessellator (and guess it doesn't), but our stroker does
return overlapping traps. This was raised on the list a couple or more
months ago.
behdad
> - Vlad
>
> plain text document attachment (cairo-region-init-rects.patch)
> commit 66092334e7474b526a024da0aeecf830938ef812
> Author: Vladimir Vukicevic <vladimir at pobox.com>
> Date: Wed Jun 13 16:56:10 2007 -0700
>
> [perf] Add pixman_region_init_rects, and use from extract_region
>
> Avoid O(N*N) operation of calling union repeatedly to create a region
> from traps by adding a method to directly pass the rects in.
>
> diff --git a/pixman/src/pixman.h b/pixman/src/pixman.h
> index 8a2dd18..18534b7 100644
> --- a/pixman/src/pixman.h
> +++ b/pixman/src/pixman.h
> @@ -142,6 +142,8 @@ pixman_region_init_rect(pixman_region16_t *region,
> pixman_private void
> pixman_region_init_with_extents(pixman_region16_t *region, pixman_box16_t *extents);
> pixman_private void
> +pixman_region_init_rects(pixman_region16_t *region, pixman_box16_t *boxes, int count, int *pOverlap);
> +pixman_private void
> pixman_region_fini (pixman_region16_t *region);
>
> /* manipulation */
> diff --git a/pixman/src/pixregion.c b/pixman/src/pixregion.c
> index 0c214cb..64c2efb 100644
> --- a/pixman/src/pixregion.c
> +++ b/pixman/src/pixregion.c
> @@ -76,6 +76,10 @@ static pixman_region16_data_t pixman_brokendata = {0, 0};
>
> static pixman_region_status_t
> pixman_break (pixman_region16_t *pReg);
> +static pixman_region_status_t
> +pixman_rect_alloc(pixman_region16_t * region, int n);
> +static void
> +pixman_set_extents (pixman_region16_t *region);
>
> /*
> * The functions in this file implement the Region abstraction used extensively
> @@ -312,6 +316,27 @@ pixman_region_init_with_extents(pixman_region16_t *region, pixman_box16_t *exten
> }
>
> void
> +pixman_region_init_rects(pixman_region16_t *region, pixman_box16_t *boxes, int count, int *pOverlap)
> +{
> + pixman_region_init(region);
> +
> + if (!pixman_rect_alloc(region, count)) {
> + /* XXX no way to signal failure, return an empty region */
> + pixman_region_init(region);
> + return;
> + }
> +
> + /* Copy in the rects */
> + memcpy (PIXREGION_RECTS(region), boxes, sizeof(pixman_box16_t) * count);
> +
> + /* Calculate the extents */
> + pixman_set_extents (region);
> +
> + /* Validate and figure out if there are overlapping rects */
> + pixman_region_validate (region, pOverlap);
> +}
> +
> +void
> pixman_region_fini (pixman_region16_t *region)
> {
> good (region);
> diff --git a/src/cairo-traps.c b/src/cairo-traps.c
> index f7171dd..f11d115 100644
> --- a/src/cairo-traps.c
> +++ b/src/cairo-traps.c
> @@ -597,7 +597,10 @@ cairo_int_status_t
> _cairo_traps_extract_region (cairo_traps_t *traps,
> pixman_region16_t *region)
> {
> - int i;
> +#define NUM_STATIC_BOXES 16
> + pixman_box16_t static_boxes[16];
> + pixman_box16_t *boxes;
> + int i, box_count, hasOverlap;
>
> for (i = 0; i < traps->num_traps; i++)
> if (!(traps->traps[i].left.p1.x == traps->traps[i].left.p2.x
> @@ -609,26 +612,47 @@ _cairo_traps_extract_region (cairo_traps_t *traps,
> return CAIRO_INT_STATUS_UNSUPPORTED;
> }
>
> - pixman_region_init (region);
> + if (traps->num_traps <= NUM_STATIC_BOXES) {
> + boxes = static_boxes;
> + } else {
> + /*boxes = _cairo_malloc2 (traps->num_traps, sizeof(pixman_box16_t));*/
> + boxes = malloc (traps->num_traps * sizeof(pixman_box16_t));
> +
> + if (boxes == NULL)
> + return CAIRO_STATUS_NO_MEMORY;
> + }
> +
> + box_count = 0;
>
> for (i = 0; i < traps->num_traps; i++) {
> - int x = _cairo_fixed_integer_part(traps->traps[i].left.p1.x);
> - int y = _cairo_fixed_integer_part(traps->traps[i].top);
> - int width = _cairo_fixed_integer_part(traps->traps[i].right.p1.x) - x;
> - int height = _cairo_fixed_integer_part(traps->traps[i].bottom) - y;
> -
> - /* XXX: Sometimes we get degenerate trapezoids from the tesellator,
> - * if we call pixman_region_union_rect(), it bizarrly fails on such
> - * an empty rectangle, so skip them.
> + int x1 = _cairo_fixed_integer_part(traps->traps[i].left.p1.x);
> + int y1 = _cairo_fixed_integer_part(traps->traps[i].top);
> + int x2 = _cairo_fixed_integer_part(traps->traps[i].right.p1.x);
> + int y2 = _cairo_fixed_integer_part(traps->traps[i].bottom);
> +
> + /* XXX: Sometimes we get degenerate trapezoids from the tesellator;
> + * skip these.
> */
> - if (width == 0 || height == 0)
> - continue;
> + if (x1 == x2 || y1 == y2)
> + continue;
>
> - if (pixman_region_union_rect (region, region,
> - x, y, width, height) != PIXMAN_REGION_STATUS_SUCCESS) {
> - pixman_region_fini (region);
> - return CAIRO_STATUS_NO_MEMORY;
> - }
> + boxes[box_count].x1 = (short) x1;
> + boxes[box_count].y1 = (short) y1;
> + boxes[box_count].x2 = (short) x2;
> + boxes[box_count].y2 = (short) y2;
> +
> + box_count++;
> + }
> +
> + pixman_region_init_rects (region, boxes, box_count, &hasOverlap);
> +
> + if (boxes != static_boxes)
> + free (boxes);
> +
> + if (hasOverlap) {
> + /* We can't use the optimization here, so let's bail */
> + pixman_region_fini (region);
> + return CAIRO_INT_STATUS_UNSUPPORTED;
> }
>
> return CAIRO_STATUS_SUCCESS;
> _______________________________________________
> cairo mailing list
> cairo at cairographics.org
> http://cairographics.org/cgi-bin/mailman/listinfo/cairo
--
behdad
http://behdad.org/
"Those who would give up Essential Liberty to purchase a little
Temporary Safety, deserve neither Liberty nor Safety."
-- Benjamin Franklin, 1759
More information about the cairo
mailing list