/* Copyright (C) 2007-2008 The Android Open Source Project ** ** This software is licensed under the terms of the GNU General Public ** License version 2, as published by the Free Software Foundation, and ** may be copied, distributed, and modified under those terms. ** ** This program is distributed in the hope that it will be useful, ** but WITHOUT ANY WARRANTY; without even the implied warranty of ** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the ** GNU General Public License for more details. */ #include "android/skin/region.h" #include #include #include /* malloc/free */ /************************************************************************* ************************************************************************* **** **** ASSERTION SUPPORT **** **** ****/ #ifdef UNIT_TEST #include #include static void _rpanic(void) { *((char*)(void*)0) = 1; /* should SEGFAULT */ /* put a breakpoint here */ exit(1); } #define RASSERT(cond) \ ({ if (!(cond)) { fprintf(stderr, "%s:%d:%s: assertion failed: %s", \ __FILE__, __LINE__, __FUNCTION__, #cond ); _rpanic(); } }) #else #define RASSERT(cond) ((void)0) #endif /************************************************************************* ************************************************************************* **** **** IMPLEMENTATION DETAILS **** **** ****/ /* this implementation of regions encodes the the region's spans with the following format: region ::= yband+ YSENTINEL yband ::= YTOP YBOTTOM scanline scanline ::= span+ XSENTINEL span ::= XLEFT XRIGHT XSENTINEL ::= 0x7fff YSENTINEL := 0x7fff all values are sorted in increasing order, which means that: - YTOP1 < YBOTTOM1 <= YTOP2 < YBOTTOM2 <= .... < YSENTINEL - XLEFT1 < XRIGHT1 < XLEFT2 < XRIGHT2 < .... < XSENTINEL (in a given scanline) */ /* convenience shortbuts */ typedef SkinRegionRun Run; typedef SkinRegion Region; #define RUNS_RECT_COUNT 6 /* YTOP YBOT XLEFT XRIGHT XSENTINEL YSENTINEL */ #define XSENTINEL SKIN_REGION_SENTINEL #define YSENTINEL SKIN_REGION_SENTINEL #define RUNS_EMPTY ((Run*)(void*)(-1)) #define RUNS_RECT ((Run*)(void*)(0)) static __inline__ int region_isEmpty( Region* r ) { return r->runs == RUNS_EMPTY; } static __inline__ int region_isRect( Region* r ) { return r->runs == RUNS_RECT; } static __inline__ int region_isComplex( Region* r ) { return r->runs != RUNS_EMPTY && r->runs != RUNS_RECT; } /** RunStore: ref-counted storage for runs **/ typedef struct { int refcount; int count; } RunStore; static void runstore_free( RunStore* s ) { free(s); } static RunStore* runstore_alloc( int count ) { RunStore* s = malloc( sizeof(*s) + sizeof(Run)*count ); RASSERT(s != NULL); s->count = count; s->refcount = 1; return s; } static RunStore* runstore_edit( RunStore* s ) { RunStore* s2; if (s->refcount == 1) return s; s2 = runstore_alloc( s->count ); if (s2) { memcpy( s2, s, sizeof(*s) + s->count*sizeof(Run) ); s->refcount -= 1; s2->refcount = 1; } return s2; } static void runstore_unrefp( RunStore* *ps ) { RunStore* s = *ps; if (s != NULL) { if (s->refcount <= 0) runstore_free(s); *ps = NULL; } } static RunStore* runstore_ref( RunStore* s ) { if (s) s->refcount += 1; return s; } static __inline__ RunStore* runstore_from_runs( Run* runs ) { RASSERT(runs != RUNS_EMPTY); RASSERT(runs != RUNS_RECT); return (RunStore*)runs - 1; } static __inline__ Run* runstore_to_runs( RunStore* s ) { RASSERT(s != NULL); return (Run*)(s + 1); } static Run* region_edit( Region* r ) { RunStore* s; RASSERT(region_isComplex(r)); s = runstore_from_runs(r->runs); s = runstore_edit(s); r->runs = runstore_to_runs(s); return r->runs; } /** Run parsing **/ static Run* runs_next_scanline( Run* runs ) { RASSERT(runs[0] != YSENTINEL && runs[1] != YSENTINEL ); runs += 2; do { runs += 1; } while (runs[-1] != XSENTINEL); return runs; } static Run* runs_find_y( Run* runs, int y ) { do { int ybot, ytop = runs[0]; if (y < ytop) return NULL; ybot = runs[1]; if (y < ybot) return runs; runs = runs_next_scanline( runs ); } while (runs[0] != YSENTINEL); return NULL; } static void runs_set_rect( Run* runs, SkinRect* rect ) { runs[0] = rect->pos.y; runs[1] = rect->pos.y + rect->size.h; runs[2] = rect->pos.x; runs[3] = rect->pos.x + rect->size.w; runs[4] = XSENTINEL; runs[5] = YSENTINEL; } static Run* runs_copy_scanline( Run* dst, Run* src ) { RASSERT(src[0] != YSENTINEL); RASSERT(src[1] != YSENTINEL); dst[0] = src[0]; dst[1] = src[1]; src += 2; dst += 2; do { *dst++ = *src++; } while (src[-1] != XSENTINEL); return dst; } static Run* runs_copy_scanline_adj( Run* dst, Run* src, int ytop, int ybot ) { Run* runs2 = runs_copy_scanline( dst, src ); dst[0] = (Run) ytop; dst[1] = (Run) ybot; return runs2; } static __inline__ Run* runs_add_span( Run* dst, int left, int right ) { dst[0] = (Run) left; dst[1] = (Run) right; return dst + 2; } static __inline__ int runs_get_count( Run* runs ) { RunStore* s = runstore_from_runs(runs); return s->count; } static void runs_coalesce_band( Run* *psrc_spans, Run* *pdst_spans, SkinBox* minmax ) { Run* sspan = *psrc_spans; Run* dspan = *pdst_spans; int pleft = sspan[0]; int pright = sspan[1]; int xleft, xright; RASSERT(pleft != XSENTINEL); RASSERT(pright != XSENTINEL); RASSERT(pleft < pright); if (pleft < minmax->x1) minmax->x1 = pleft; sspan += 2; xleft = sspan[0]; while (xleft != XSENTINEL) { xright = sspan[1]; RASSERT(xright != XSENTINEL); RASSERT(xleft < xright); if (xleft == pright) { pright = xright; } else { dspan[0] = (Run) pleft; dspan[1] = (Run) pright; dspan += 2; } sspan += 2; xleft = sspan[0]; } dspan[0] = (Run) pleft; dspan[1] = (Run) pright; dspan[2] = XSENTINEL; dspan += 3; sspan += 1; /* skip XSENTINEL */ if (pright > minmax->x2) minmax->x2 = pright; *psrc_spans = sspan; *pdst_spans = dspan; } static int runs_coalesce( Run* dst, Run* src, SkinBox* minmax ) { Run* prev = NULL; Run* dst0 = dst; int ytop = src[0]; int ybot; while (ytop != YSENTINEL) { Run* sspan = src + 2; Run* dspan = dst + 2; ybot = src[1]; RASSERT( ytop < ybot ); RASSERT( ybot != YSENTINEL ); RASSERT( src[2] != XSENTINEL ); if (ytop < minmax->y1) minmax->y1 = ytop; if (ybot > minmax->y2) minmax->y2 = ybot; dst[0] = (Run) ytop; dst[1] = (Run) ybot; runs_coalesce_band( &sspan, &dspan, minmax ); if (prev && prev[1] == dst[0] && (dst-prev) == (dspan-dst) && !memcmp(prev+2, dst+2, (dspan-dst-2)*sizeof(Run))) { /* coalesce two identical bands */ prev[1] = dst[1]; } else { prev = dst; dst = dspan; } src = sspan; ytop = src[0]; } dst[0] = YSENTINEL; return (dst + 1 - dst0); } /************************************************************************* ************************************************************************* **** **** PUBLIC API **** ****/ void skin_region_init_empty( SkinRegion* r ) { /* empty region */ r->bounds.pos.x = r->bounds.pos.y = 0; r->bounds.size.w = r->bounds.size.h = 0; r->runs = RUNS_EMPTY; } void skin_region_init( SkinRegion* r, int x1, int y1, int x2, int y2 ) { if (x1 >= x2 || y1 >= y2) { skin_region_init_empty(r); return; } r->bounds.pos.x = x1; r->bounds.pos.y = y1; r->bounds.size.w = x2 - x1; r->bounds.size.h = y2 - y1; r->runs = RUNS_RECT; } void skin_region_init_rect( SkinRegion* r, SkinRect* rect ) { if (rect == NULL || rect->size.w <= 0 || rect->size.h <= 0) { skin_region_init_empty(r); return; } r->bounds = rect[0]; r->runs = RUNS_RECT; } void skin_region_init_box( SkinRegion* r, SkinBox* box ) { if (box == NULL || box->x1 >= box->x2 || box->y1 >= box->y2) { skin_region_init_empty(r); return; } r->bounds.pos.x = box->x1; r->bounds.pos.y = box->y1; r->bounds.size.w = box->x2 - box->x1; r->bounds.size.h = box->y2 - box->y1; r->runs = RUNS_RECT; } void skin_region_init_copy( SkinRegion* r, SkinRegion* src ) { if (src == NULL || region_isEmpty(src)) skin_region_init_empty(r); else { r[0] = src[0]; if (region_isComplex(src)) { RunStore* s = runstore_from_runs(r->runs); runstore_ref(s); } } } void skin_region_reset( SkinRegion* r ) { if (r != NULL) { if (region_isComplex(r)) { RunStore* s = runstore_from_runs(r->runs); runstore_unrefp( &s ); } skin_region_init_empty(r); } } void skin_region_copy( SkinRegion* r, SkinRegion* src ) { skin_region_reset(r); skin_region_init_copy(r, src); } int skin_region_equals( SkinRegion* r1, SkinRegion* r2 ) { Run *runs1, *runs2; RunStore *store1, *store2; if (r1 == r2) return 1; if (!skin_rect_equals( &r1->bounds, &r2->bounds )) return 0; runs1 = r1->runs; runs2 = r2->runs; if (runs1 == runs2) /* empties and rects */ return 1; if ( !region_isComplex(r1) || !region_isComplex(r2) ) return 0; store1 = runstore_from_runs(runs1); store2 = runstore_from_runs(runs2); if (store1->count == store2->count && !memcmp( (char*)runs1, (char*)runs2, store1->count*sizeof(Run) ) ) return 1; return 0; } void skin_region_translate( SkinRegion* r, int dx, int dy ) { Run* runs; if (region_isEmpty(r)) return; skin_rect_translate( &r->bounds, dx, dy ); if (region_isRect(r)) return; runs = region_edit(r); while (runs[0] != YSENTINEL) { int ytop = runs[0]; int ybot = runs[1]; RASSERT(ybot != YSENTINEL); runs[0] = (Run)(ytop + dy); runs[1] = (Run)(ybot + dy); runs += 2; while (runs[0] != XSENTINEL) { int xleft = runs[0]; int xright = runs[1]; RASSERT(xright != YSENTINEL); runs[0] = (Run)(xleft + dx); runs[1] = (Run)(xright + dx); runs += 2; } runs += 1; } } void skin_region_get_bounds( SkinRegion* r, SkinRect* bounds ) { if (r != NULL) { bounds[0] = r->bounds; } else { bounds->pos.x = bounds->pos.y = 0; bounds->size.w = bounds->size.h = 0; } } int skin_region_is_empty( SkinRegion* r ) { return region_isEmpty(r); } int skin_region_is_rect( SkinRegion* r ) { return region_isRect(r); } int skin_region_is_complex( SkinRegion* r ) { return region_isComplex(r); } void skin_region_swap( SkinRegion* r, SkinRegion* r2 ) { SkinRegion tmp; tmp = r[0]; r[0] = r2[0]; r2[0] = tmp; } SkinOverlap skin_region_contains( SkinRegion* r, int x, int y ) { if (region_isEmpty(r)) return SKIN_OUTSIDE; if (region_isRect(r)) { return skin_rect_contains(&r->bounds,x,y); } else { Run* runs = runs_find_y( r->runs, y ); if (runs != NULL) { runs += 2; do { int xright, xleft = runs[0]; if (x < xleft) // also x < xleft == XSENTINEL break; xright = runs[1]; if (xright == XSENTINEL) break; if (x < xright) return SKIN_INSIDE; runs += 2; } while (runs[0] != XSENTINEL); } return SKIN_OUTSIDE; } } SkinOverlap skin_region_contains_rect( SkinRegion* r, SkinRect* rect ) { SkinRegion r2[1]; skin_region_init_rect( r2, rect ); return skin_region_test_intersect( r, r2 ); } SkinOverlap skin_region_contains_box( SkinRegion* r, SkinBox* b ) { SkinRegion r2[1]; skin_region_init_box( r2, b ); return skin_region_test_intersect( r, r2 ); } #define FLAG_REGION_1 (1 << 0) #define FLAG_REGION_2 (1 << 1) #define FLAG_REGION_BOTH (1 << 2) SkinOverlap skin_region_test_intersect( SkinRegion* r1, SkinRegion* r2 ) { Run *runs1, *runs2; Run run2_tmp[ RUNS_RECT_COUNT ]; SkinRect r; if (region_isEmpty(r1) || region_isEmpty(r2)) return SKIN_OUTSIDE; if ( !skin_rect_intersect( &r, &r1->bounds, &r2->bounds) ) return SKIN_OUTSIDE; if (region_isRect(r1)) { if (region_isRect(r2)) { return skin_rect_contains_rect(&r1->bounds, &r2->bounds); } else { SkinRegion* tmp = r1; r1 = r2; r2 = tmp; } } /* here r1 is guaranteed to be complex, r2 is either rect of complex */ runs1 = r1->runs; if (region_isRect(r2)) { runs2 = run2_tmp; runs_set_rect(runs2, &r2->bounds); } else { runs2 = r2->runs; } { int flags = 0; while (runs1[0] != YSENTINEL && runs2[0] != YSENTINEL) { int ytop1 = runs1[0]; int ybot1 = runs1[1]; int ytop2 = runs2[0]; int ybot2 = runs2[1]; if (ybot1 <= ytop2) { /* band1 over band2 */ flags |= FLAG_REGION_1; runs1 = runs_next_scanline( runs1 ); } else if (ybot2 <= ytop1) { /* band2 over band1 */ flags |= FLAG_REGION_2; runs2 = runs_next_scanline( runs2 ); } else /* band1 and band2 overlap */ { Run* span1; Run* span2; int ybot; if (ytop1 < ytop2) { flags |= FLAG_REGION_1; ytop1 = ytop2; } else if (ytop2 < ytop1) { flags |= FLAG_REGION_2; ytop2 = ytop1; } ybot = (ybot1 < ybot2) ? ybot1 : ybot2; span1 = runs1 + 2; span2 = runs2 + 2; while (span1[0] != XSENTINEL && span2[0] != XSENTINEL) { int xleft1 = span1[0]; int xright1 = span1[1]; int xleft2 = span2[0]; int xright2 = span2[1]; RASSERT(xright1 != XSENTINEL); RASSERT(xright2 != XSENTINEL); if (xright1 <= xleft2) { flags |= FLAG_REGION_1; span1 += 2; } else if (xright2 <= xleft1) { flags |= FLAG_REGION_2; span2 += 2; } else { int xright; if (xleft1 < xleft2) { flags |= FLAG_REGION_1; xleft1 = xleft2; } else if (xleft2 < xleft1) { flags |= FLAG_REGION_2; xleft2 = xleft1; } xright = (xright1 < xright2) ? xright1 : xright2; flags |= FLAG_REGION_BOTH; if (xright == xright1) span1 += 2; if (xright == xright2) span2 += 2; } } if (span1[0] != XSENTINEL) { flags |= FLAG_REGION_1; } if (span2[0] != XSENTINEL) { flags |= FLAG_REGION_2; } if (ybot == ybot1) runs1 = runs_next_scanline( runs1 ); if (ybot == ybot2) runs2 = runs_next_scanline( runs2 ); } } if (runs1[0] != YSENTINEL) { flags |= FLAG_REGION_1; } if (runs2[0] != YSENTINEL) { flags |= FLAG_REGION_2; } if ( !(flags & FLAG_REGION_BOTH) ) { /* no intersection at all */ return SKIN_OUTSIDE; } if ( (flags & FLAG_REGION_2) != 0 ) { /* intersection + overlap */ return SKIN_OVERLAP; } return SKIN_INSIDE; } } typedef struct { Run* runs1; Run* runs2; Run* runs_base; Run* runs; RunStore* store; Region result[1]; Run runs1_rect[ RUNS_RECT_COUNT ]; Run runs2_rect[ RUNS_RECT_COUNT ]; } RegionOperator; static void region_operator_init( RegionOperator* o, Region* r1, Region* r2 ) { int run1_count, run2_count; int maxruns; RASSERT( !region_isEmpty(r1) ); RASSERT( !region_isEmpty(r2) ); if (region_isRect(r1)) { run1_count = RUNS_RECT_COUNT; o->runs1 = o->runs1_rect; runs_set_rect( o->runs1, &r1->bounds ); } else { o->runs1 = r1->runs; run1_count = runs_get_count(r1->runs); } if (region_isRect(r2)) { run2_count = RUNS_RECT_COUNT; o->runs2 = o->runs2_rect; runs_set_rect( o->runs2, &r2->bounds ); } else { o->runs2 = r2->runs; run2_count = runs_get_count(r2->runs); } maxruns = run1_count < run2_count ? run2_count : run1_count; o->store = runstore_alloc( 3*maxruns ); o->runs_base = runstore_to_runs(o->store); } static void region_operator_do( RegionOperator* o, int wanted ) { Run* runs1 = o->runs1; Run* runs2 = o->runs2; Run* runs = o->runs_base; int ytop1 = runs1[0]; int ytop2 = runs2[0]; if (ytop1 != YSENTINEL && ytop2 != YSENTINEL) { int ybot1, ybot2; while (ytop1 != YSENTINEL && ytop2 != YSENTINEL) { int ybot; ybot1 = runs1[1]; ybot2 = runs2[1]; RASSERT(ybot1 != YSENTINEL); RASSERT(ybot2 != YSENTINEL); if (ybot1 <= ytop2) { if (wanted & FLAG_REGION_1) runs = runs_copy_scanline_adj( runs, runs1, ytop1, ybot1 ); runs1 = runs_next_scanline( runs1 ); ytop1 = runs1[0]; continue; } if (ybot2 <= ytop1) { if (wanted & FLAG_REGION_2) runs = runs_copy_scanline_adj( runs, runs2, ytop2, ybot2 ); runs2 = runs_next_scanline(runs2); ytop2 = runs2[0]; continue; } if (ytop1 < ytop2) { if (wanted & FLAG_REGION_1) runs = runs_copy_scanline_adj( runs, runs1, ytop1, ytop2 ); ytop1 = ytop2; } else if (ytop2 < ytop1) { if (wanted & FLAG_REGION_2) runs = runs_copy_scanline_adj( runs, runs2, ytop2, ytop1 ); ytop2 = ytop1; } ybot = (ybot1 <= ybot2) ? ybot1 : ybot2; runs[0] = (Run) ytop1; runs[1] = (Run) ybot; /* do the common band */ { Run* span1 = runs1 + 2; Run* span2 = runs2 + 2; Run* span = runs + 2; int xleft1 = span1[0]; int xleft2 = span2[0]; int xright1, xright2; while (xleft1 != XSENTINEL && xleft2 != XSENTINEL) { int xright; xright1 = span1[1]; xright2 = span2[1]; RASSERT(xright1 != XSENTINEL); RASSERT(xright2 != XSENTINEL); if (xright1 <= xleft2) { if (wanted & FLAG_REGION_1) span = runs_add_span( span, xleft1, xright1 ); span1 += 2; xleft1 = span1[0]; continue; } if (xright2 <= xleft1) { if (wanted & FLAG_REGION_2) span = runs_add_span( span, xleft2, xright2 ); span2 += 2; xleft2 = span2[0]; continue; } if (xleft1 < xleft2) { if (wanted & FLAG_REGION_1) span = runs_add_span( span, xleft1, xleft2 ); xleft1 = xleft2; } else if (xleft2 < xleft1) { if (wanted & FLAG_REGION_2) span = runs_add_span( span, xleft2, xleft1 ); xleft2 = xleft1; } xright = (xright1 <= xright2) ? xright1 : xright2; if (wanted & FLAG_REGION_BOTH) span = runs_add_span( span, xleft1, xright ); xleft1 = xleft2 = xright; if (xright == xright1) { span1 += 2; xleft1 = span1[0]; } if (xright == xright2) { span2 += 2; xleft2 = span2[0]; } } if (wanted & FLAG_REGION_1) { while (xleft1 != XSENTINEL) { RASSERT(span1[1] != XSENTINEL); span[0] = (Run) xleft1; span[1] = span1[1]; span += 2; span1 += 2; xleft1 = span1[0]; } } if (wanted & FLAG_REGION_2) { while (xleft2 != XSENTINEL) { RASSERT(span2[1] != XSENTINEL); span[0] = (Run) xleft2; span[1] = span2[1]; span += 2; span2 += 2; xleft2 = span2[0]; } } if (span > runs + 2) { span[0] = XSENTINEL; runs = span + 1; } } ytop1 = ytop2 = ybot; if (ybot == ybot1) { runs1 = runs_next_scanline( runs1 ); ytop1 = runs1[0]; } if (ybot == ybot2) { runs2 = runs_next_scanline( runs2 ); ytop2 = runs2[0]; } } } if ((wanted & FLAG_REGION_1) != 0) { while (ytop1 != YSENTINEL) { runs = runs_copy_scanline_adj( runs, runs1, ytop1, runs1[1] ); runs1 = runs_next_scanline(runs1); ytop1 = runs1[0]; } } if ((wanted & FLAG_REGION_2) != 0) { while (ytop2 != YSENTINEL) { runs = runs_copy_scanline_adj( runs, runs2, ytop2, runs2[1] ); runs2 = runs_next_scanline(runs2); ytop2 = runs2[0]; } } runs[0] = YSENTINEL; o->runs = runs + 1; } /* returns 1 if the result is not empty */ static int region_operator_done( RegionOperator* o ) { Run* src = o->runs; int count; SkinBox minmax; RunStore* store; if (src <= o->runs_base + 1) { /* result is empty */ skin_region_init_empty( o->result ); return 0; } /* coalesce the temp runs in-place and compute the corresponding bounds */ minmax.x1 = minmax.y1 = INT_MAX; minmax.x2 = minmax.y2 = INT_MIN; count = runs_coalesce( o->runs_base, o->runs_base, &minmax ); if (count == 1) { /* result is empty */ skin_region_init_empty( o->result ); } else { skin_box_to_rect( &minmax, &o->result->bounds ); if (count == RUNS_RECT_COUNT) { o->result->runs = RUNS_RECT; } else { /* result is complex */ store = runstore_alloc( count ); o->result->runs = runstore_to_runs(store); memcpy( o->result->runs, o->runs_base, count*sizeof(Run) ); } } /* release temporary runstore */ runstore_unrefp( &o->store ); return region_isEmpty(o->result); } int skin_region_intersect( SkinRegion* r, SkinRegion* r2 ) { RegionOperator oper[1]; if (region_isEmpty(r)) return 0; if (region_isEmpty(r2)) return 1; if ( skin_rect_contains_rect( &r->bounds, &r2->bounds ) == SKIN_OUTSIDE ) { skin_region_init_empty(r); return 0; } region_operator_init( oper, r, r2 ); region_operator_do( oper, FLAG_REGION_BOTH ); region_operator_done( oper ); skin_region_swap( r, oper->result ); skin_region_reset( oper->result ); return region_isEmpty( r ); } /* performs r = (intersect r (region+_from_rect rect)), returns true iff the resulting region is not empty */ int skin_region_intersect_rect( SkinRegion* r, SkinRect* rect ) { Region r2[1]; skin_region_init_rect( r2, rect ); return skin_region_intersect( r, r2 ); } /* performs r = (union r r2) */ void skin_region_union( SkinRegion* r, SkinRegion* r2 ) { RegionOperator oper[1]; if (region_isEmpty(r)) { skin_region_copy(r, r2); return; } if (region_isEmpty(r2)) return; region_operator_init( oper, r, r2 ); region_operator_do( oper, FLAG_REGION_1|FLAG_REGION_2|FLAG_REGION_BOTH ); region_operator_done( oper ); skin_region_swap( r, oper->result ); skin_region_reset( oper->result ); } void skin_region_union_rect( SkinRegion* r, SkinRect* rect ) { Region r2[1]; skin_region_init_rect(r2, rect); return skin_region_union( r, r2 ); } /* performs r = (difference r r2) */ void skin_region_substract( SkinRegion* r, SkinRegion* r2 ) { RegionOperator oper[1]; if (region_isEmpty(r) || region_isEmpty(r2)) return; if ( skin_rect_contains_rect( &r->bounds, &r2->bounds ) == SKIN_OUTSIDE ) { skin_region_init_empty(r); return; } region_operator_init( oper, r, r2 ); region_operator_do( oper, FLAG_REGION_1 ); region_operator_done( oper ); skin_region_swap( r, oper->result ); skin_region_reset( oper->result ); } void skin_region_substract_rect( SkinRegion* r, SkinRect* rect ) { Region r2[1]; skin_region_init_rect(r2, rect); return skin_region_substract( r, r2 ); } /* performs r = (xor r r2) */ void skin_region_xor( SkinRegion* r, SkinRegion* r2 ) { RegionOperator oper[1]; if (region_isEmpty(r)) { skin_region_copy(r, r2); return; } if (region_isEmpty(r2)) return; if ( skin_rect_contains_rect( &r->bounds, &r2->bounds ) == SKIN_OUTSIDE ) { skin_region_init_empty(r); return; } region_operator_init( oper, r, r2 ); region_operator_do( oper, FLAG_REGION_1 ); region_operator_done( oper ); skin_region_swap( r, oper->result ); skin_region_reset( oper->result ); } void skin_region_iterator_init( SkinRegionIterator* iter, SkinRegion* region ) { iter->region = region; iter->band = NULL; iter->span = NULL; } int skin_region_iterator_next( SkinRegionIterator* iter, SkinRect *rect ) { static const Run dummy[ 2 ] = { XSENTINEL, YSENTINEL }; Run* span = iter->span; Run* band = iter->band; if (span == NULL) { Region* r = iter->region; if (region_isEmpty(r)) return 0; if (region_isRect(r)) { rect[0] = r->bounds; iter->span = (Run*) dummy; return 1; } iter->band = band = r->runs; iter->span = span = r->runs + 2; } else if (band == NULL) return 0; while (span[0] == XSENTINEL) { band = span + 1; if (band[0] == YSENTINEL || band[1] == YSENTINEL) return 0; iter->band = band; iter->span = span = band + 2; } if (span[1] == XSENTINEL) return 0; rect->pos.y = band[0]; rect->pos.x = span[0]; rect->size.h = band[1] - band[0]; rect->size.w = span[1] - span[0]; iter->span = span + 2; return 1; } int skin_region_iterator_next_box( SkinRegionIterator* iter, SkinBox *box ) { SkinRect rect; int result = skin_region_iterator_next( iter, &rect ); if (result) skin_box_from_rect( box, &rect ); return result; } #ifdef UNIT_TEST #include #include #include "skin_rect.c" static void panic(void) { *((char*)0) = 1; exit(0); } static void _expectCompare( Region* r, const SkinBox* boxes, int count ) { if (count == 0) { if ( !skin_region_is_empty(r) ) { printf( " result is not empty\n" ); panic(); } } else if (count == 1) { SkinRect rect1, rect2; if ( !skin_region_is_rect(r) ) { printf( " result is not a rectangle\n" ); panic(); } skin_region_get_bounds( r, &rect1 ); skin_box_to_rect( (SkinBox*)boxes, &rect2 ); if ( !skin_rect_equals( &rect1, &rect2 ) ) { printf( " result is (%d,%d,%d,%d), expected (%d,%d,%d,%d)\n", rect1.pos.x, rect1.pos.y, rect1.pos.x + rect1.size.w, rect1.pos.y + rect1.size.h, rect2.pos.x, rect2.pos.y, rect2.pos.x + rect2.size.w, rect2.pos.y + rect2.size.h ); panic(); } } else { SkinRegionIterator iter; SkinBox b; int n; skin_region_iterator_init( &iter, r ); n = 0; while (n < count) { if ( !skin_region_iterator_next_box( &iter, &b ) ) { printf( "missing region box (%d, %d, %d, %d)\n", boxes->x1, boxes->y1, boxes->x2, boxes->y2 ); panic(); } if (b.x1 != boxes->x1 || b.x2 != boxes->x2|| b.y1 != boxes->y1 || b.y2 != boxes->y2) { printf( "invalid region box (%d,%d,%d,%d) expecting (%d,%d,%d,%d)\n", b.x1, b.y1, b.x2, b.y2, boxes->x1, boxes->y1, boxes->x2, boxes->y2 ); panic(); } boxes += 1; n += 1; } if ( skin_region_iterator_next_box( &iter, &b ) ) { printf( "excess region box (%d,%d,%d,%d)\n", b.x1, b.y1, b.x2, b.y2 ); panic(); } } } static void expectEmptyRegion( Region* r ) { printf( "expectEmptyRegion: " ); if (!skin_region_is_empty(r)) { printf( "region not empty !!\n" ); panic(); } printf( "ok\n" ); } static void expectTestIntersect( Region* r1, Region* r2, SkinOverlap overlap ) { SkinOverlap result; printf( "expectTestIntersect(%d): ", overlap ); result = skin_region_test_intersect(r1, r2); if (result != overlap) { printf( "bad result %d, expected %d\n", result, overlap ); panic(); } printf( "ok\n" ); } static void expectRectRegion( Region* r, int x1, int y1, int x2, int y2 ) { SkinRect rect; SkinBox b; printf( "expectRectRegion(%d,%d,%d,%d): ",x1,y1,x2,y2 ); if (!skin_region_is_rect(r)) { printf( "region not rect !!\n" ); panic(); } skin_region_get_bounds( r, &rect ); skin_box_from_rect( &b, &rect ); if (b.x1 != x1 || b.x2 != x2 || b.y1 != y1 || b.y2 != y2) { printf( "rect region bounds are (%d,%d,%d,%d), expecting (%d,%d,%d,%d)\n", b.x1, b.y1, b.x2, b.y2, x1, y1, x2, y2 ); panic(); } printf( "ok\n" ); } static void expectComplexRegion( Region* r, const SkinBox* boxes, int count ) { SkinRegionIterator iter; SkinBox b; int n; printf( "expectComplexRegion(): " ); if (!skin_region_is_complex(r)) { printf( "region is not complex !!\n" ); panic(); } _expectCompare( r, boxes, count ); printf( "ok\n" ); } static void expectIntersect( Region* r1, Region* r2, const SkinBox* boxes, int count ) { SkinRegion r[1]; printf( "expectIntersect(%d): ", count ); skin_region_init_copy( r, r1 ); skin_region_intersect( r, r2 ); _expectCompare( r, boxes, count ); printf( "ok\n" ); } static void expectUnion( Region* r1, Region* r2, const SkinBox* boxes, int count ) { SkinRegion r[1]; printf( "expectUnion(%d): ", count ); skin_region_init_copy( r, r1 ); skin_region_union( r, r2 ); _expectCompare( r, boxes, count ); printf( "ok\n" ); } static void expectSubstract( Region* r1, Region* r2, const SkinBox* boxes, int count ) { SkinRegion r[1]; printf( "expectSubstract(%d): ", count ); skin_region_init_copy( r, r1 ); skin_region_substract( r, r2 ); _expectCompare( r, boxes, count ); printf( "ok\n" ); } int main( void ) { SkinRegion r[1], r2[1]; skin_region_init_empty( r ); expectEmptyRegion( r ); skin_region_init( r, 10, 20, 110, 120 ); expectRectRegion( r, 10, 20, 110, 120 ); skin_region_translate( r, 50, 80 ); expectRectRegion( r, 60, 100, 160, 200 ); skin_region_init( r, 10, 10, 40, 40 ); skin_region_init( r2, 20, 20, 50, 50 ); expectTestIntersect( r, r2, SKIN_OVERLAP ); skin_region_translate(r2, +20, + 20 ); expectTestIntersect( r, r2, SKIN_OUTSIDE ); skin_region_translate(r2, -30, -30 ); expectTestIntersect( r, r2, SKIN_INSIDE ); { static const SkinBox result1[1] = { { 20, 20, 40, 40 } }; static const SkinBox result2[3] = { { 10, 10, 40, 20 }, { 10, 20, 50, 40 }, { 20, 40, 50, 50 }, }; static const SkinBox result3[2] = { { 10, 10, 40, 20 }, { 10, 20, 20, 40 }, }; skin_region_init( r, 10, 10, 40, 40 ); skin_region_init( r2, 20, 20, 50, 50 ); expectIntersect( r, r2, result1, 1 ); expectUnion( r, r2, result2, 3 ); expectSubstract( r, r2, result3, 2 ); } return 0; } #endif /* UNIT_TEST */