commit 66092334e7474b526a024da0aeecf830938ef812 Author: Vladimir Vukicevic 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;