1 /* Copyright (C) 2007-2008 The Android Open Source Project
2 **
3 ** This software is licensed under the terms of the GNU General Public
4 ** License version 2, as published by the Free Software Foundation, and
5 ** may be copied, distributed, and modified under those terms.
6 **
7 ** This program is distributed in the hope that it will be useful,
8 ** but WITHOUT ANY WARRANTY; without even the implied warranty of
9 ** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
10 ** GNU General Public License for more details.
11 */
12 #include "android/skin/region.h"
13 #include <limits.h>
14 #include <string.h>
15 #include <stdlib.h> /* malloc/free */
16
17 /*************************************************************************
18 *************************************************************************
19 ****
20 **** ASSERTION SUPPORT
21 ****
22 ****
23 ****/
24
25 #ifdef UNIT_TEST
26 #include <stdlib.h>
27 #include <stdio.h>
28 static void
_rpanic(void)29 _rpanic(void)
30 {
31 *((char*)(void*)0) = 1; /* should SEGFAULT */
32 /* put a breakpoint here */
33 exit(1);
34 }
35
36 #define RASSERT(cond) \
37 ({ if (!(cond)) { fprintf(stderr, "%s:%d:%s: assertion failed: %s", \
38 __FILE__, __LINE__, __FUNCTION__, #cond ); _rpanic(); } })
39
40 #else
41 #define RASSERT(cond) ((void)0)
42 #endif
43
44
45 /*************************************************************************
46 *************************************************************************
47 ****
48 **** IMPLEMENTATION DETAILS
49 ****
50 ****
51 ****/
52
53 /* this implementation of regions encodes the the region's spans with the
54 following format:
55
56 region ::= yband+ YSENTINEL
57 yband ::= YTOP YBOTTOM scanline
58 scanline ::= span+ XSENTINEL
59 span ::= XLEFT XRIGHT
60
61 XSENTINEL ::= 0x7fff
62 YSENTINEL := 0x7fff
63
64 all values are sorted in increasing order, which means that:
65
66 - YTOP1 < YBOTTOM1 <= YTOP2 < YBOTTOM2 <= .... < YSENTINEL
67 - XLEFT1 < XRIGHT1 < XLEFT2 < XRIGHT2 < .... < XSENTINEL
68 (in a given scanline)
69 */
70
71 /* convenience shortbuts */
72 typedef SkinRegionRun Run;
73 typedef SkinRegion Region;
74
75 #define RUNS_RECT_COUNT 6 /* YTOP YBOT XLEFT XRIGHT XSENTINEL YSENTINEL */
76
77 #define XSENTINEL SKIN_REGION_SENTINEL
78 #define YSENTINEL SKIN_REGION_SENTINEL
79
80 #define RUNS_EMPTY ((Run*)(void*)(-1))
81 #define RUNS_RECT ((Run*)(void*)(0))
82
83 static __inline__ int
region_isEmpty(Region * r)84 region_isEmpty( Region* r )
85 {
86 return r->runs == RUNS_EMPTY;
87 }
88
89 static __inline__ int
region_isRect(Region * r)90 region_isRect( Region* r )
91 {
92 return r->runs == RUNS_RECT;
93 }
94
95 static __inline__ int
region_isComplex(Region * r)96 region_isComplex( Region* r )
97 {
98 return r->runs != RUNS_EMPTY && r->runs != RUNS_RECT;
99 }
100
101 /** RunStore: ref-counted storage for runs
102 **/
103
104 typedef struct {
105 int refcount;
106 int count;
107 } RunStore;
108
109 static void
runstore_free(RunStore * s)110 runstore_free( RunStore* s )
111 {
112 free(s);
113 }
114
115 static RunStore*
runstore_alloc(int count)116 runstore_alloc( int count )
117 {
118 RunStore* s = malloc( sizeof(*s) + sizeof(Run)*count );
119 RASSERT(s != NULL);
120 s->count = count;
121 s->refcount = 1;
122 return s;
123 }
124
125 static RunStore*
runstore_edit(RunStore * s)126 runstore_edit( RunStore* s )
127 {
128 RunStore* s2;
129
130 if (s->refcount == 1)
131 return s;
132
133 s2 = runstore_alloc( s->count );
134 if (s2) {
135 memcpy( s2, s, sizeof(*s) + s->count*sizeof(Run) );
136 s->refcount -= 1;
137 s2->refcount = 1;
138 }
139 return s2;
140 }
141
142 static void
runstore_unrefp(RunStore ** ps)143 runstore_unrefp( RunStore* *ps )
144 {
145 RunStore* s = *ps;
146 if (s != NULL) {
147 if (s->refcount <= 0)
148 runstore_free(s);
149 *ps = NULL;
150 }
151 }
152
153 static RunStore*
runstore_ref(RunStore * s)154 runstore_ref( RunStore* s )
155 {
156 if (s) s->refcount += 1;
157 return s;
158 }
159
160 static __inline__ RunStore*
runstore_from_runs(Run * runs)161 runstore_from_runs( Run* runs )
162 {
163 RASSERT(runs != RUNS_EMPTY);
164 RASSERT(runs != RUNS_RECT);
165 return (RunStore*)runs - 1;
166 }
167
168 static __inline__ Run*
runstore_to_runs(RunStore * s)169 runstore_to_runs( RunStore* s )
170 {
171 RASSERT(s != NULL);
172 return (Run*)(s + 1);
173 }
174
175 static Run*
region_edit(Region * r)176 region_edit( Region* r )
177 {
178 RunStore* s;
179
180 RASSERT(region_isComplex(r));
181
182 s = runstore_from_runs(r->runs);
183 s = runstore_edit(s);
184 r->runs = runstore_to_runs(s);
185 return r->runs;
186 }
187
188 /** Run parsing
189 **/
190
191 static Run*
runs_next_scanline(Run * runs)192 runs_next_scanline( Run* runs )
193 {
194 RASSERT(runs[0] != YSENTINEL && runs[1] != YSENTINEL );
195 runs += 2;
196 do { runs += 1; } while (runs[-1] != XSENTINEL);
197 return runs;
198 }
199
200 static Run*
runs_find_y(Run * runs,int y)201 runs_find_y( Run* runs, int y )
202 {
203 do {
204 int ybot, ytop = runs[0];
205
206 if (y < ytop)
207 return NULL;
208
209 ybot = runs[1];
210 if (y < ybot)
211 return runs;
212
213 runs = runs_next_scanline( runs );
214 } while (runs[0] != YSENTINEL);
215
216 return NULL;
217 }
218
219 static void
runs_set_rect(Run * runs,SkinRect * rect)220 runs_set_rect( Run* runs, SkinRect* rect )
221 {
222 runs[0] = rect->pos.y;
223 runs[1] = rect->pos.y + rect->size.h;
224 runs[2] = rect->pos.x;
225 runs[3] = rect->pos.x + rect->size.w;
226 runs[4] = XSENTINEL;
227 runs[5] = YSENTINEL;
228 }
229
230 static Run*
runs_copy_scanline(Run * dst,Run * src)231 runs_copy_scanline( Run* dst, Run* src )
232 {
233 RASSERT(src[0] != YSENTINEL);
234 RASSERT(src[1] != YSENTINEL);
235 dst[0] = src[0];
236 dst[1] = src[1];
237 src += 2;
238 dst += 2;
239 do { *dst++ = *src++; } while (src[-1] != XSENTINEL);
240 return dst;
241 }
242
243 static Run*
runs_copy_scanline_adj(Run * dst,Run * src,int ytop,int ybot)244 runs_copy_scanline_adj( Run* dst, Run* src, int ytop, int ybot )
245 {
246 Run* runs2 = runs_copy_scanline( dst, src );
247 dst[0] = (Run) ytop;
248 dst[1] = (Run) ybot;
249 return runs2;
250 }
251
252 static __inline__ Run*
runs_add_span(Run * dst,int left,int right)253 runs_add_span( Run* dst, int left, int right )
254 {
255 dst[0] = (Run) left;
256 dst[1] = (Run) right;
257 return dst + 2;
258 }
259
260 static __inline__ int
runs_get_count(Run * runs)261 runs_get_count( Run* runs )
262 {
263 RunStore* s = runstore_from_runs(runs);
264 return s->count;
265 }
266
267
268 static void
runs_coalesce_band(Run ** psrc_spans,Run ** pdst_spans,SkinBox * minmax)269 runs_coalesce_band( Run* *psrc_spans, Run* *pdst_spans, SkinBox* minmax )
270 {
271 Run* sspan = *psrc_spans;
272 Run* dspan = *pdst_spans;
273 int pleft = sspan[0];
274 int pright = sspan[1];
275 int xleft, xright;
276
277 RASSERT(pleft != XSENTINEL);
278 RASSERT(pright != XSENTINEL);
279 RASSERT(pleft < pright);
280
281 if (pleft < minmax->x1) minmax->x1 = pleft;
282
283 sspan += 2;
284 xleft = sspan[0];
285
286 while (xleft != XSENTINEL)
287 {
288 xright = sspan[1];
289 RASSERT(xright != XSENTINEL);
290 RASSERT(xleft < xright);
291
292 if (xleft == pright) {
293 pright = xright;
294 } else {
295 dspan[0] = (Run) pleft;
296 dspan[1] = (Run) pright;
297 dspan += 2;
298 }
299 sspan += 2;
300 xleft = sspan[0];
301 }
302 dspan[0] = (Run) pleft;
303 dspan[1] = (Run) pright;
304 dspan[2] = XSENTINEL;
305 dspan += 3;
306 sspan += 1; /* skip XSENTINEL */
307
308 if (pright > minmax->x2) minmax->x2 = pright;
309
310 *psrc_spans = sspan;
311 *pdst_spans = dspan;
312 }
313
314
315 static int
runs_coalesce(Run * dst,Run * src,SkinBox * minmax)316 runs_coalesce( Run* dst, Run* src, SkinBox* minmax )
317 {
318 Run* prev = NULL;
319 Run* dst0 = dst;
320 int ytop = src[0];
321 int ybot;
322
323 while (ytop != YSENTINEL)
324 {
325 Run* sspan = src + 2;
326 Run* dspan = dst + 2;
327
328 ybot = src[1];
329 RASSERT( ytop < ybot );
330 RASSERT( ybot != YSENTINEL );
331 RASSERT( src[2] != XSENTINEL );
332
333 if (ytop < minmax->y1) minmax->y1 = ytop;
334 if (ybot > minmax->y2) minmax->y2 = ybot;
335
336 dst[0] = (Run) ytop;
337 dst[1] = (Run) ybot;
338
339 runs_coalesce_band( &sspan, &dspan, minmax );
340
341 if (prev && prev[1] == dst[0] && (dst-prev) == (dspan-dst) &&
342 !memcmp(prev+2, dst+2, (dspan-dst-2)*sizeof(Run)))
343 {
344 /* coalesce two identical bands */
345 prev[1] = dst[1];
346 }
347 else
348 {
349 prev = dst;
350 dst = dspan;
351 }
352 src = sspan;
353 ytop = src[0];
354 }
355 dst[0] = YSENTINEL;
356 return (dst + 1 - dst0);
357 }
358
359 /*************************************************************************
360 *************************************************************************
361 ****
362 **** PUBLIC API
363 ****
364 ****/
365
366 void
skin_region_init_empty(SkinRegion * r)367 skin_region_init_empty( SkinRegion* r )
368 {
369 /* empty region */
370 r->bounds.pos.x = r->bounds.pos.y = 0;
371 r->bounds.size.w = r->bounds.size.h = 0;
372 r->runs = RUNS_EMPTY;
373 }
374
375 void
skin_region_init(SkinRegion * r,int x1,int y1,int x2,int y2)376 skin_region_init( SkinRegion* r, int x1, int y1, int x2, int y2 )
377 {
378 if (x1 >= x2 || y1 >= y2) {
379 skin_region_init_empty(r);
380 return;
381 }
382 r->bounds.pos.x = x1;
383 r->bounds.pos.y = y1;
384 r->bounds.size.w = x2 - x1;
385 r->bounds.size.h = y2 - y1;
386 r->runs = RUNS_RECT;
387 }
388
389 void
skin_region_init_rect(SkinRegion * r,SkinRect * rect)390 skin_region_init_rect( SkinRegion* r, SkinRect* rect )
391 {
392 if (rect == NULL || rect->size.w <= 0 || rect->size.h <= 0) {
393 skin_region_init_empty(r);
394 return;
395 }
396 r->bounds = rect[0];
397 r->runs = RUNS_RECT;
398 }
399
400 void
skin_region_init_box(SkinRegion * r,SkinBox * box)401 skin_region_init_box( SkinRegion* r, SkinBox* box )
402 {
403 if (box == NULL || box->x1 >= box->x2 || box->y1 >= box->y2) {
404 skin_region_init_empty(r);
405 return;
406 }
407 r->bounds.pos.x = box->x1;
408 r->bounds.pos.y = box->y1;
409 r->bounds.size.w = box->x2 - box->x1;
410 r->bounds.size.h = box->y2 - box->y1;
411 r->runs = RUNS_RECT;
412 }
413
414 void
skin_region_init_copy(SkinRegion * r,SkinRegion * src)415 skin_region_init_copy( SkinRegion* r, SkinRegion* src )
416 {
417 if (src == NULL || region_isEmpty(src))
418 skin_region_init_empty(r);
419 else {
420 r[0] = src[0];
421 if (region_isComplex(src)) {
422 RunStore* s = runstore_from_runs(r->runs);
423 runstore_ref(s);
424 }
425 }
426 }
427
428
429 void
skin_region_reset(SkinRegion * r)430 skin_region_reset( SkinRegion* r )
431 {
432 if (r != NULL) {
433 if (region_isComplex(r)) {
434 RunStore* s = runstore_from_runs(r->runs);
435 runstore_unrefp( &s );
436 }
437 skin_region_init_empty(r);
438 }
439 }
440
441
442
443 void
skin_region_copy(SkinRegion * r,SkinRegion * src)444 skin_region_copy( SkinRegion* r, SkinRegion* src )
445 {
446 skin_region_reset(r);
447 skin_region_init_copy(r, src);
448 }
449
450
451 int
skin_region_equals(SkinRegion * r1,SkinRegion * r2)452 skin_region_equals( SkinRegion* r1, SkinRegion* r2 )
453 {
454 Run *runs1, *runs2;
455 RunStore *store1, *store2;
456
457 if (r1 == r2)
458 return 1;
459
460 if (!skin_rect_equals( &r1->bounds, &r2->bounds ))
461 return 0;
462
463 runs1 = r1->runs;
464 runs2 = r2->runs;
465
466 if (runs1 == runs2) /* empties and rects */
467 return 1;
468
469 if ( !region_isComplex(r1) || !region_isComplex(r2) )
470 return 0;
471
472 store1 = runstore_from_runs(runs1);
473 store2 = runstore_from_runs(runs2);
474
475 if (store1->count == store2->count &&
476 !memcmp( (char*)runs1, (char*)runs2, store1->count*sizeof(Run) ) )
477 return 1;
478
479 return 0;
480 }
481
482 void
skin_region_translate(SkinRegion * r,int dx,int dy)483 skin_region_translate( SkinRegion* r, int dx, int dy )
484 {
485 Run* runs;
486
487 if (region_isEmpty(r))
488 return;
489
490 skin_rect_translate( &r->bounds, dx, dy );
491 if (region_isRect(r))
492 return;
493
494 runs = region_edit(r);
495 while (runs[0] != YSENTINEL) {
496 int ytop = runs[0];
497 int ybot = runs[1];
498
499 RASSERT(ybot != YSENTINEL);
500 runs[0] = (Run)(ytop + dy);
501 runs[1] = (Run)(ybot + dy);
502 runs += 2;
503 while (runs[0] != XSENTINEL) {
504 int xleft = runs[0];
505 int xright = runs[1];
506 RASSERT(xright != YSENTINEL);
507 runs[0] = (Run)(xleft + dx);
508 runs[1] = (Run)(xright + dx);
509 runs += 2;
510 }
511 runs += 1;
512 }
513 }
514
515 void
skin_region_get_bounds(SkinRegion * r,SkinRect * bounds)516 skin_region_get_bounds( SkinRegion* r, SkinRect* bounds )
517 {
518 if (r != NULL) {
519 bounds[0] = r->bounds;
520 } else {
521 bounds->pos.x = bounds->pos.y = 0;
522 bounds->size.w = bounds->size.h = 0;
523 }
524 }
525
526 int
skin_region_is_empty(SkinRegion * r)527 skin_region_is_empty( SkinRegion* r )
528 {
529 return region_isEmpty(r);
530 }
531
532 int
skin_region_is_rect(SkinRegion * r)533 skin_region_is_rect( SkinRegion* r )
534 {
535 return region_isRect(r);
536 }
537
538 int
skin_region_is_complex(SkinRegion * r)539 skin_region_is_complex( SkinRegion* r )
540 {
541 return region_isComplex(r);
542 }
543
544 void
skin_region_swap(SkinRegion * r,SkinRegion * r2)545 skin_region_swap( SkinRegion* r, SkinRegion* r2 )
546 {
547 SkinRegion tmp;
548 tmp = r[0];
549 r[0] = r2[0];
550 r2[0] = tmp;
551 }
552
553
554 SkinOverlap
skin_region_contains(SkinRegion * r,int x,int y)555 skin_region_contains( SkinRegion* r, int x, int y )
556 {
557 if (region_isEmpty(r))
558 return SKIN_OUTSIDE;
559 if (region_isRect(r)) {
560 return skin_rect_contains(&r->bounds,x,y);
561 } else {
562 Run* runs = runs_find_y( r->runs, y );
563 if (runs != NULL) {
564 runs += 2;
565 do {
566 int xright, xleft = runs[0];
567
568 if (x < xleft) // also x < xleft == XSENTINEL
569 break;
570 xright = runs[1];
571 if (xright == XSENTINEL)
572 break;
573 if (x < xright)
574 return SKIN_INSIDE;
575 runs += 2;
576 } while (runs[0] != XSENTINEL);
577 }
578 return SKIN_OUTSIDE;
579 }
580 }
581
582
583 SkinOverlap
skin_region_contains_rect(SkinRegion * r,SkinRect * rect)584 skin_region_contains_rect( SkinRegion* r, SkinRect* rect )
585 {
586 SkinRegion r2[1];
587 skin_region_init_rect( r2, rect );
588 return skin_region_test_intersect( r, r2 );
589 }
590
591
592 SkinOverlap
skin_region_contains_box(SkinRegion * r,SkinBox * b)593 skin_region_contains_box( SkinRegion* r, SkinBox* b )
594 {
595 SkinRegion r2[1];
596
597 skin_region_init_box( r2, b );
598 return skin_region_test_intersect( r, r2 );
599 }
600
601
602
603 #define FLAG_REGION_1 (1 << 0)
604 #define FLAG_REGION_2 (1 << 1)
605 #define FLAG_REGION_BOTH (1 << 2)
606
607 SkinOverlap
skin_region_test_intersect(SkinRegion * r1,SkinRegion * r2)608 skin_region_test_intersect( SkinRegion* r1,
609 SkinRegion* r2 )
610 {
611 Run *runs1, *runs2;
612 Run run2_tmp[ RUNS_RECT_COUNT ];
613 SkinRect r;
614
615 if (region_isEmpty(r1) || region_isEmpty(r2))
616 return SKIN_OUTSIDE;
617
618 if ( !skin_rect_intersect( &r, &r1->bounds, &r2->bounds) )
619 return SKIN_OUTSIDE;
620
621 if (region_isRect(r1)) {
622 if (region_isRect(r2)) {
623 return skin_rect_contains_rect(&r1->bounds, &r2->bounds);
624 } else {
625 SkinRegion* tmp = r1;
626 r1 = r2;
627 r2 = tmp;
628 }
629 }
630 /* here r1 is guaranteed to be complex, r2 is either rect of complex */
631 runs1 = r1->runs;
632 if (region_isRect(r2)) {
633 runs2 = run2_tmp;
634 runs_set_rect(runs2, &r2->bounds);
635 }
636 else {
637 runs2 = r2->runs;
638 }
639
640 {
641 int flags = 0;
642
643 while (runs1[0] != YSENTINEL && runs2[0] != YSENTINEL)
644 {
645 int ytop1 = runs1[0];
646 int ybot1 = runs1[1];
647 int ytop2 = runs2[0];
648 int ybot2 = runs2[1];
649
650 if (ybot1 <= ytop2)
651 {
652 /* band1 over band2 */
653 flags |= FLAG_REGION_1;
654 runs1 = runs_next_scanline( runs1 );
655 }
656 else if (ybot2 <= ytop1)
657 {
658 /* band2 over band1 */
659 flags |= FLAG_REGION_2;
660 runs2 = runs_next_scanline( runs2 );
661 }
662 else /* band1 and band2 overlap */
663 {
664 Run* span1;
665 Run* span2;
666 int ybot;
667
668 if (ytop1 < ytop2) {
669 flags |= FLAG_REGION_1;
670 ytop1 = ytop2;
671 } else if (ytop2 < ytop1) {
672 flags |= FLAG_REGION_2;
673 ytop2 = ytop1;
674 }
675
676 ybot = (ybot1 < ybot2) ? ybot1 : ybot2;
677
678 span1 = runs1 + 2;
679 span2 = runs2 + 2;
680
681 while (span1[0] != XSENTINEL && span2[0] != XSENTINEL)
682 {
683 int xleft1 = span1[0];
684 int xright1 = span1[1];
685 int xleft2 = span2[0];
686 int xright2 = span2[1];
687
688 RASSERT(xright1 != XSENTINEL);
689 RASSERT(xright2 != XSENTINEL);
690
691 if (xright1 <= xleft2) {
692 flags |= FLAG_REGION_1;
693 span1 += 2;
694 }
695 else if (xright2 <= xleft1) {
696 flags |= FLAG_REGION_2;
697 span2 += 2;
698 }
699 else {
700 int xright;
701
702 if (xleft1 < xleft2) {
703 flags |= FLAG_REGION_1;
704 xleft1 = xleft2;
705 } else if (xleft2 < xleft1) {
706 flags |= FLAG_REGION_2;
707 xleft2 = xleft1;
708 }
709
710 xright = (xright1 < xright2) ? xright1 : xright2;
711
712 flags |= FLAG_REGION_BOTH;
713
714 if (xright == xright1)
715 span1 += 2;
716 if (xright == xright2)
717 span2 += 2;
718 }
719 }
720
721 if (span1[0] != XSENTINEL) {
722 flags |= FLAG_REGION_1;
723 }
724
725 if (span2[0] != XSENTINEL) {
726 flags |= FLAG_REGION_2;
727 }
728
729 if (ybot == ybot1)
730 runs1 = runs_next_scanline( runs1 );
731
732 if (ybot == ybot2)
733 runs2 = runs_next_scanline( runs2 );
734 }
735 }
736
737 if (runs1[0] != YSENTINEL) {
738 flags |= FLAG_REGION_1;
739 }
740
741 if (runs2[0] != YSENTINEL) {
742 flags |= FLAG_REGION_2;
743 }
744
745 if ( !(flags & FLAG_REGION_BOTH) ) {
746 /* no intersection at all */
747 return SKIN_OUTSIDE;
748 }
749
750 if ( (flags & FLAG_REGION_2) != 0 ) {
751 /* intersection + overlap */
752 return SKIN_OVERLAP;
753 }
754
755 return SKIN_INSIDE;
756 }
757 }
758
759 typedef struct {
760 Run* runs1;
761 Run* runs2;
762 Run* runs_base;
763 Run* runs;
764 RunStore* store;
765 Region result[1];
766 Run runs1_rect[ RUNS_RECT_COUNT ];
767 Run runs2_rect[ RUNS_RECT_COUNT ];
768 } RegionOperator;
769
770
771 static void
region_operator_init(RegionOperator * o,Region * r1,Region * r2)772 region_operator_init( RegionOperator* o,
773 Region* r1,
774 Region* r2 )
775 {
776 int run1_count, run2_count;
777 int maxruns;
778
779 RASSERT( !region_isEmpty(r1) );
780 RASSERT( !region_isEmpty(r2) );
781
782 if (region_isRect(r1)) {
783 run1_count = RUNS_RECT_COUNT;
784 o->runs1 = o->runs1_rect;
785 runs_set_rect( o->runs1, &r1->bounds );
786 } else {
787 o->runs1 = r1->runs;
788 run1_count = runs_get_count(r1->runs);
789 }
790
791 if (region_isRect(r2)) {
792 run2_count = RUNS_RECT_COUNT;
793 o->runs2 = o->runs2_rect;
794 runs_set_rect( o->runs2, &r2->bounds );
795 } else {
796 o->runs2 = r2->runs;
797 run2_count = runs_get_count(r2->runs);
798 }
799
800 maxruns = run1_count < run2_count ? run2_count : run1_count;
801 o->store = runstore_alloc( 3*maxruns );
802 o->runs_base = runstore_to_runs(o->store);
803 }
804
805
806 static void
region_operator_do(RegionOperator * o,int wanted)807 region_operator_do( RegionOperator* o, int wanted )
808 {
809 Run* runs1 = o->runs1;
810 Run* runs2 = o->runs2;
811 Run* runs = o->runs_base;
812 int ytop1 = runs1[0];
813 int ytop2 = runs2[0];
814
815 if (ytop1 != YSENTINEL && ytop2 != YSENTINEL)
816 {
817 int ybot1, ybot2;
818
819 while (ytop1 != YSENTINEL && ytop2 != YSENTINEL)
820 {
821 int ybot;
822
823 ybot1 = runs1[1];
824 ybot2 = runs2[1];
825
826 RASSERT(ybot1 != YSENTINEL);
827 RASSERT(ybot2 != YSENTINEL);
828
829 if (ybot1 <= ytop2) {
830 if (wanted & FLAG_REGION_1)
831 runs = runs_copy_scanline_adj( runs, runs1, ytop1, ybot1 );
832 runs1 = runs_next_scanline( runs1 );
833 ytop1 = runs1[0];
834 continue;
835 }
836
837 if (ybot2 <= ytop1) {
838 if (wanted & FLAG_REGION_2)
839 runs = runs_copy_scanline_adj( runs, runs2, ytop2, ybot2 );
840 runs2 = runs_next_scanline(runs2);
841 ytop2 = runs2[0];
842 continue;
843 }
844
845 if (ytop1 < ytop2) {
846 if (wanted & FLAG_REGION_1)
847 runs = runs_copy_scanline_adj( runs, runs1, ytop1, ytop2 );
848 ytop1 = ytop2;
849 }
850 else if (ytop2 < ytop1) {
851 if (wanted & FLAG_REGION_2)
852 runs = runs_copy_scanline_adj( runs, runs2, ytop2, ytop1 );
853 ytop2 = ytop1;
854 }
855
856 ybot = (ybot1 <= ybot2) ? ybot1 : ybot2;
857
858 runs[0] = (Run) ytop1;
859 runs[1] = (Run) ybot;
860
861 /* do the common band */
862 {
863 Run* span1 = runs1 + 2;
864 Run* span2 = runs2 + 2;
865 Run* span = runs + 2;
866 int xleft1 = span1[0];
867 int xleft2 = span2[0];
868 int xright1, xright2;
869
870 while (xleft1 != XSENTINEL && xleft2 != XSENTINEL)
871 {
872 int xright;
873
874 xright1 = span1[1];
875 xright2 = span2[1];
876
877 RASSERT(xright1 != XSENTINEL);
878 RASSERT(xright2 != XSENTINEL);
879
880 if (xright1 <= xleft2) {
881 if (wanted & FLAG_REGION_1)
882 span = runs_add_span( span, xleft1, xright1 );
883 span1 += 2;
884 xleft1 = span1[0];
885 continue;
886 }
887
888 if (xright2 <= xleft1) {
889 if (wanted & FLAG_REGION_2)
890 span = runs_add_span( span, xleft2, xright2 );
891 span2 += 2;
892 xleft2 = span2[0];
893 continue;
894 }
895
896 if (xleft1 < xleft2) {
897 if (wanted & FLAG_REGION_1)
898 span = runs_add_span( span, xleft1, xleft2 );
899 xleft1 = xleft2;
900 }
901
902 else if (xleft2 < xleft1) {
903 if (wanted & FLAG_REGION_2)
904 span = runs_add_span( span, xleft2, xleft1 );
905 xleft2 = xleft1;
906 }
907
908 xright = (xright1 <= xright2) ? xright1 : xright2;
909
910 if (wanted & FLAG_REGION_BOTH)
911 span = runs_add_span( span, xleft1, xright );
912
913 xleft1 = xleft2 = xright;
914
915 if (xright == xright1) {
916 span1 += 2;
917 xleft1 = span1[0];
918 }
919 if (xright == xright2) {
920 span2 += 2;
921 xleft2 = span2[0];
922 }
923 }
924
925 if (wanted & FLAG_REGION_1) {
926 while (xleft1 != XSENTINEL) {
927 RASSERT(span1[1] != XSENTINEL);
928 span[0] = (Run) xleft1;
929 span[1] = span1[1];
930 span += 2;
931 span1 += 2;
932 xleft1 = span1[0];
933 }
934 }
935
936 if (wanted & FLAG_REGION_2) {
937 while (xleft2 != XSENTINEL) {
938 RASSERT(span2[1] != XSENTINEL);
939 span[0] = (Run) xleft2;
940 span[1] = span2[1];
941 span += 2;
942 span2 += 2;
943 xleft2 = span2[0];
944 }
945 }
946
947 if (span > runs + 2) {
948 span[0] = XSENTINEL;
949 runs = span + 1;
950 }
951 }
952
953 ytop1 = ytop2 = ybot;
954
955 if (ybot == ybot1) {
956 runs1 = runs_next_scanline( runs1 );
957 ytop1 = runs1[0];
958 }
959 if (ybot == ybot2) {
960 runs2 = runs_next_scanline( runs2 );
961 ytop2 = runs2[0];
962 }
963 }
964 }
965
966 if ((wanted & FLAG_REGION_1) != 0) {
967 while (ytop1 != YSENTINEL) {
968 runs = runs_copy_scanline_adj( runs, runs1, ytop1, runs1[1] );
969 runs1 = runs_next_scanline(runs1);
970 ytop1 = runs1[0];
971 }
972 }
973
974 if ((wanted & FLAG_REGION_2) != 0) {
975 while (ytop2 != YSENTINEL) {
976 runs = runs_copy_scanline_adj( runs, runs2, ytop2, runs2[1] );
977 runs2 = runs_next_scanline(runs2);
978 ytop2 = runs2[0];
979 }
980 }
981
982 runs[0] = YSENTINEL;
983 o->runs = runs + 1;
984 }
985
986 /* returns 1 if the result is not empty */
987 static int
region_operator_done(RegionOperator * o)988 region_operator_done( RegionOperator* o )
989 {
990 Run* src = o->runs;
991 int count;
992 SkinBox minmax;
993 RunStore* store;
994
995 if (src <= o->runs_base + 1) {
996 /* result is empty */
997 skin_region_init_empty( o->result );
998 return 0;
999 }
1000
1001 /* coalesce the temp runs in-place and compute the corresponding bounds */
1002 minmax.x1 = minmax.y1 = INT_MAX;
1003 minmax.x2 = minmax.y2 = INT_MIN;
1004
1005 count = runs_coalesce( o->runs_base, o->runs_base, &minmax );
1006 if (count == 1) {
1007 /* result is empty */
1008 skin_region_init_empty( o->result );
1009 }
1010 else
1011 {
1012 skin_box_to_rect( &minmax, &o->result->bounds );
1013 if (count == RUNS_RECT_COUNT) {
1014 o->result->runs = RUNS_RECT;
1015 }
1016 else
1017 {
1018 /* result is complex */
1019 store = runstore_alloc( count );
1020 o->result->runs = runstore_to_runs(store);
1021 memcpy( o->result->runs, o->runs_base, count*sizeof(Run) );
1022 }
1023 }
1024
1025 /* release temporary runstore */
1026 runstore_unrefp( &o->store );
1027
1028 return region_isEmpty(o->result);
1029 }
1030
1031
1032
1033 int
skin_region_intersect(SkinRegion * r,SkinRegion * r2)1034 skin_region_intersect( SkinRegion* r, SkinRegion* r2 )
1035 {
1036 RegionOperator oper[1];
1037
1038 if (region_isEmpty(r))
1039 return 0;
1040
1041 if (region_isEmpty(r2))
1042 return 1;
1043
1044 if ( skin_rect_contains_rect( &r->bounds, &r2->bounds ) == SKIN_OUTSIDE ) {
1045 skin_region_init_empty(r);
1046 return 0;
1047 }
1048
1049 region_operator_init( oper, r, r2 );
1050 region_operator_do( oper, FLAG_REGION_BOTH );
1051 region_operator_done( oper );
1052
1053 skin_region_swap( r, oper->result );
1054 skin_region_reset( oper->result );
1055
1056 return region_isEmpty( r );
1057 }
1058
1059
1060 /* performs r = (intersect r (region+_from_rect rect)), returns true iff
1061 the resulting region is not empty */
1062 int
skin_region_intersect_rect(SkinRegion * r,SkinRect * rect)1063 skin_region_intersect_rect( SkinRegion* r, SkinRect* rect )
1064 {
1065 Region r2[1];
1066
1067 skin_region_init_rect( r2, rect );
1068 return skin_region_intersect( r, r2 );
1069 }
1070
1071 /* performs r = (union r r2) */
1072 void
skin_region_union(SkinRegion * r,SkinRegion * r2)1073 skin_region_union( SkinRegion* r, SkinRegion* r2 )
1074 {
1075 RegionOperator oper[1];
1076
1077 if (region_isEmpty(r)) {
1078 skin_region_copy(r, r2);
1079 return;
1080 }
1081
1082 if (region_isEmpty(r2))
1083 return;
1084
1085 region_operator_init( oper, r, r2 );
1086 region_operator_do( oper, FLAG_REGION_1|FLAG_REGION_2|FLAG_REGION_BOTH );
1087 region_operator_done( oper );
1088
1089 skin_region_swap( r, oper->result );
1090 skin_region_reset( oper->result );
1091 }
1092
1093 void
skin_region_union_rect(SkinRegion * r,SkinRect * rect)1094 skin_region_union_rect( SkinRegion* r, SkinRect* rect )
1095 {
1096 Region r2[1];
1097
1098 skin_region_init_rect(r2, rect);
1099 return skin_region_union( r, r2 );
1100 }
1101
1102 /* performs r = (difference r r2) */
1103 void
skin_region_substract(SkinRegion * r,SkinRegion * r2)1104 skin_region_substract( SkinRegion* r, SkinRegion* r2 )
1105 {
1106 RegionOperator oper[1];
1107
1108 if (region_isEmpty(r) || region_isEmpty(r2))
1109 return;
1110
1111 if ( skin_rect_contains_rect( &r->bounds, &r2->bounds ) == SKIN_OUTSIDE ) {
1112 skin_region_init_empty(r);
1113 return;
1114 }
1115
1116 region_operator_init( oper, r, r2 );
1117 region_operator_do( oper, FLAG_REGION_1 );
1118 region_operator_done( oper );
1119
1120 skin_region_swap( r, oper->result );
1121 skin_region_reset( oper->result );
1122 }
1123
1124 void
skin_region_substract_rect(SkinRegion * r,SkinRect * rect)1125 skin_region_substract_rect( SkinRegion* r, SkinRect* rect )
1126 {
1127 Region r2[1];
1128
1129 skin_region_init_rect(r2, rect);
1130 return skin_region_substract( r, r2 );
1131 }
1132
1133 /* performs r = (xor r r2) */
1134 void
skin_region_xor(SkinRegion * r,SkinRegion * r2)1135 skin_region_xor( SkinRegion* r, SkinRegion* r2 )
1136 {
1137 RegionOperator oper[1];
1138
1139 if (region_isEmpty(r)) {
1140 skin_region_copy(r, r2);
1141 return;
1142 }
1143
1144 if (region_isEmpty(r2))
1145 return;
1146
1147 if ( skin_rect_contains_rect( &r->bounds, &r2->bounds ) == SKIN_OUTSIDE ) {
1148 skin_region_init_empty(r);
1149 return;
1150 }
1151
1152 region_operator_init( oper, r, r2 );
1153 region_operator_do( oper, FLAG_REGION_1 );
1154 region_operator_done( oper );
1155
1156 skin_region_swap( r, oper->result );
1157 skin_region_reset( oper->result );
1158 }
1159
1160
1161 void
skin_region_iterator_init(SkinRegionIterator * iter,SkinRegion * region)1162 skin_region_iterator_init( SkinRegionIterator* iter,
1163 SkinRegion* region )
1164 {
1165 iter->region = region;
1166 iter->band = NULL;
1167 iter->span = NULL;
1168 }
1169
1170 int
skin_region_iterator_next(SkinRegionIterator * iter,SkinRect * rect)1171 skin_region_iterator_next( SkinRegionIterator* iter, SkinRect *rect )
1172 {
1173 static const Run dummy[ 2 ] = { XSENTINEL, YSENTINEL };
1174
1175 Run* span = iter->span;
1176 Run* band = iter->band;
1177
1178 if (span == NULL) {
1179 Region* r = iter->region;
1180 if (region_isEmpty(r))
1181 return 0;
1182 if (region_isRect(r)) {
1183 rect[0] = r->bounds;
1184 iter->span = (Run*) dummy;
1185 return 1;
1186 }
1187 iter->band = band = r->runs;
1188 iter->span = span = r->runs + 2;
1189 }
1190 else if (band == NULL)
1191 return 0;
1192
1193 while (span[0] == XSENTINEL) {
1194 band = span + 1;
1195 if (band[0] == YSENTINEL || band[1] == YSENTINEL)
1196 return 0;
1197
1198 iter->band = band;
1199 iter->span = span = band + 2;
1200 }
1201
1202 if (span[1] == XSENTINEL)
1203 return 0;
1204
1205 rect->pos.y = band[0];
1206 rect->pos.x = span[0];
1207 rect->size.h = band[1] - band[0];
1208 rect->size.w = span[1] - span[0];
1209
1210 iter->span = span + 2;
1211 return 1;
1212 }
1213
1214 int
skin_region_iterator_next_box(SkinRegionIterator * iter,SkinBox * box)1215 skin_region_iterator_next_box( SkinRegionIterator* iter, SkinBox *box )
1216 {
1217 SkinRect rect;
1218 int result = skin_region_iterator_next( iter, &rect );
1219
1220 if (result)
1221 skin_box_from_rect( box, &rect );
1222
1223 return result;
1224 }
1225
1226 #ifdef UNIT_TEST
1227
1228 #include <stdio.h>
1229 #include <stdlib.h>
1230 #include "skin_rect.c"
1231
1232 static void
panic(void)1233 panic(void)
1234 {
1235 *((char*)0) = 1;
1236 exit(0);
1237 }
1238
1239 static void
_expectCompare(Region * r,const SkinBox * boxes,int count)1240 _expectCompare( Region* r, const SkinBox* boxes, int count )
1241 {
1242 if (count == 0) {
1243 if ( !skin_region_is_empty(r) ) {
1244 printf( " result is not empty\n" );
1245 panic();
1246 }
1247 }
1248 else if (count == 1) {
1249 SkinRect rect1, rect2;
1250 if ( !skin_region_is_rect(r) ) {
1251 printf( " result is not a rectangle\n" );
1252 panic();
1253 }
1254 skin_region_get_bounds( r, &rect1 );
1255 skin_box_to_rect( (SkinBox*)boxes, &rect2 );
1256 if ( !skin_rect_equals( &rect1, &rect2 ) ) {
1257 printf( " result is (%d,%d,%d,%d), expected (%d,%d,%d,%d)\n",
1258 rect1.pos.x, rect1.pos.y,
1259 rect1.pos.x + rect1.size.w, rect1.pos.y + rect1.size.h,
1260 rect2.pos.x, rect2.pos.y,
1261 rect2.pos.x + rect2.size.w, rect2.pos.y + rect2.size.h );
1262 panic();
1263 }
1264 }
1265 else {
1266 SkinRegionIterator iter;
1267 SkinBox b;
1268 int n;
1269
1270 skin_region_iterator_init( &iter, r );
1271 n = 0;
1272 while (n < count) {
1273 if ( !skin_region_iterator_next_box( &iter, &b ) ) {
1274 printf( "missing region box (%d, %d, %d, %d)\n",
1275 boxes->x1, boxes->y1, boxes->x2, boxes->y2 );
1276 panic();
1277 }
1278
1279 if (b.x1 != boxes->x1 || b.x2 != boxes->x2||
1280 b.y1 != boxes->y1 || b.y2 != boxes->y2)
1281 {
1282 printf( "invalid region box (%d,%d,%d,%d) expecting (%d,%d,%d,%d)\n",
1283 b.x1, b.y1, b.x2, b.y2,
1284 boxes->x1, boxes->y1, boxes->x2, boxes->y2 );
1285 panic();
1286 }
1287 boxes += 1;
1288 n += 1;
1289 }
1290
1291 if ( skin_region_iterator_next_box( &iter, &b ) ) {
1292 printf( "excess region box (%d,%d,%d,%d)\n",
1293 b.x1, b.y1, b.x2, b.y2 );
1294 panic();
1295 }
1296 }
1297 }
1298
1299
1300 static void
expectEmptyRegion(Region * r)1301 expectEmptyRegion( Region* r )
1302 {
1303 printf( "expectEmptyRegion: " );
1304 if (!skin_region_is_empty(r)) {
1305 printf( "region not empty !!\n" );
1306 panic();
1307 }
1308 printf( "ok\n" );
1309 }
1310
1311 static void
expectTestIntersect(Region * r1,Region * r2,SkinOverlap overlap)1312 expectTestIntersect( Region* r1, Region* r2, SkinOverlap overlap )
1313 {
1314 SkinOverlap result;
1315 printf( "expectTestIntersect(%d): ", overlap );
1316 result = skin_region_test_intersect(r1, r2);
1317 if (result != overlap) {
1318 printf( "bad result %d, expected %d\n", result, overlap );
1319 panic();
1320 }
1321 printf( "ok\n" );
1322 }
1323
1324 static void
expectRectRegion(Region * r,int x1,int y1,int x2,int y2)1325 expectRectRegion( Region* r, int x1, int y1, int x2, int y2 )
1326 {
1327 SkinRect rect;
1328 SkinBox b;
1329
1330 printf( "expectRectRegion(%d,%d,%d,%d): ",x1,y1,x2,y2 );
1331 if (!skin_region_is_rect(r)) {
1332 printf( "region not rect !!\n" );
1333 panic();
1334 }
1335
1336 skin_region_get_bounds( r, &rect );
1337 skin_box_from_rect( &b, &rect );
1338
1339 if (b.x1 != x1 || b.x2 != x2 || b.y1 != y1 || b.y2 != y2) {
1340 printf( "rect region bounds are (%d,%d,%d,%d), expecting (%d,%d,%d,%d)\n",
1341 b.x1, b.y1, b.x2, b.y2, x1, y1, x2, y2 );
1342 panic();
1343 }
1344 printf( "ok\n" );
1345 }
1346
1347 static void
expectComplexRegion(Region * r,const SkinBox * boxes,int count)1348 expectComplexRegion( Region* r, const SkinBox* boxes, int count )
1349 {
1350 SkinRegionIterator iter;
1351 SkinBox b;
1352 int n;
1353
1354 printf( "expectComplexRegion(): " );
1355 if (!skin_region_is_complex(r)) {
1356 printf( "region is not complex !!\n" );
1357 panic();
1358 }
1359 _expectCompare( r, boxes, count );
1360 printf( "ok\n" );
1361 }
1362
1363 static void
expectIntersect(Region * r1,Region * r2,const SkinBox * boxes,int count)1364 expectIntersect( Region* r1, Region* r2, const SkinBox* boxes, int count )
1365 {
1366 SkinRegion r[1];
1367
1368 printf( "expectIntersect(%d): ", count );
1369 skin_region_init_copy( r, r1 );
1370 skin_region_intersect( r, r2 );
1371 _expectCompare( r, boxes, count );
1372 printf( "ok\n" );
1373 }
1374
1375 static void
expectUnion(Region * r1,Region * r2,const SkinBox * boxes,int count)1376 expectUnion( Region* r1, Region* r2, const SkinBox* boxes, int count )
1377 {
1378 SkinRegion r[1];
1379
1380 printf( "expectUnion(%d): ", count );
1381 skin_region_init_copy( r, r1 );
1382 skin_region_union( r, r2 );
1383 _expectCompare( r, boxes, count );
1384 printf( "ok\n" );
1385 }
1386
1387
1388 static void
expectSubstract(Region * r1,Region * r2,const SkinBox * boxes,int count)1389 expectSubstract( Region* r1, Region* r2, const SkinBox* boxes, int count )
1390 {
1391 SkinRegion r[1];
1392
1393 printf( "expectSubstract(%d): ", count );
1394 skin_region_init_copy( r, r1 );
1395 skin_region_substract( r, r2 );
1396 _expectCompare( r, boxes, count );
1397 printf( "ok\n" );
1398 }
1399
1400
main(void)1401 int main( void )
1402 {
1403 SkinRegion r[1], r2[1];
1404
1405 skin_region_init_empty( r );
1406 expectEmptyRegion( r );
1407
1408 skin_region_init( r, 10, 20, 110, 120 );
1409 expectRectRegion( r, 10, 20, 110, 120 );
1410
1411 skin_region_translate( r, 50, 80 );
1412 expectRectRegion( r, 60, 100, 160, 200 );
1413
1414 skin_region_init( r, 10, 10, 40, 40 );
1415 skin_region_init( r2, 20, 20, 50, 50 );
1416 expectTestIntersect( r, r2, SKIN_OVERLAP );
1417
1418 skin_region_translate(r2, +20, + 20 );
1419 expectTestIntersect( r, r2, SKIN_OUTSIDE );
1420
1421 skin_region_translate(r2, -30, -30 );
1422 expectTestIntersect( r, r2, SKIN_INSIDE );
1423
1424 {
1425 static const SkinBox result1[1] = {
1426 { 20, 20, 40, 40 }
1427 };
1428 static const SkinBox result2[3] = {
1429 { 10, 10, 40, 20 },
1430 { 10, 20, 50, 40 },
1431 { 20, 40, 50, 50 },
1432 };
1433 static const SkinBox result3[2] = {
1434 { 10, 10, 40, 20 },
1435 { 10, 20, 20, 40 },
1436 };
1437
1438 skin_region_init( r, 10, 10, 40, 40 );
1439 skin_region_init( r2, 20, 20, 50, 50 );
1440 expectIntersect( r, r2, result1, 1 );
1441 expectUnion( r, r2, result2, 3 );
1442 expectSubstract( r, r2, result3, 2 );
1443 }
1444
1445 return 0;
1446 }
1447
1448 #endif /* UNIT_TEST */
1449