Line data Source code
1 : /* -*- Mode: C; c-basic-offset: 4; indent-tabs-mode: nil -*- */
2 : /*
3 : Copyright (C) 2009 Red Hat, Inc.
4 :
5 : This library is free software; you can redistribute it and/or
6 : modify it under the terms of the GNU Lesser General Public
7 : License as published by the Free Software Foundation; either
8 : version 2.1 of the License, or (at your option) any later version.
9 :
10 : This library is distributed in the hope that it will be useful,
11 : but WITHOUT ANY WARRANTY; without even the implied warranty of
12 : MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 : Lesser General Public License for more details.
14 :
15 : You should have received a copy of the GNU Lesser General Public
16 : License along with this library; if not, see <http://www.gnu.org/licenses/>.
17 : */
18 : #include <config.h>
19 :
20 : #include <stdio.h>
21 : #include <string.h>
22 : #include <stdlib.h>
23 : #include <spice/macros.h>
24 :
25 : #include "region.h"
26 : #include "rect.h"
27 : #include "mem.h"
28 :
29 : /* true iff two Boxes overlap */
30 : #define EXTENTCHECK(r1, r2) \
31 : (!( ((r1)->x2 <= (r2)->x1) || \
32 : ((r1)->x1 >= (r2)->x2) || \
33 : ((r1)->y2 <= (r2)->y1) || \
34 : ((r1)->y1 >= (r2)->y2) ) )
35 :
36 : /* true iff Box r1 contains Box r2 */
37 : #define SUBSUMES(r1, r2) \
38 : ( ((r1)->x1 <= (r2)->x1) && \
39 : ((r1)->x2 >= (r2)->x2) && \
40 : ((r1)->y1 <= (r2)->y1) && \
41 : ((r1)->y2 >= (r2)->y2) )
42 :
43 :
44 2 : void region_init(QRegion *rgn)
45 : {
46 2 : pixman_region32_init(rgn);
47 2 : }
48 :
49 200010 : void region_clear(QRegion *rgn)
50 : {
51 200010 : pixman_region32_fini(rgn);
52 200010 : pixman_region32_init(rgn);
53 200010 : }
54 :
55 4 : void region_destroy(QRegion *rgn)
56 : {
57 4 : pixman_region32_fini(rgn);
58 4 : }
59 :
60 2 : void region_clone(QRegion *dest, const QRegion *src)
61 : {
62 2 : pixman_region32_init(dest);
63 2 : pixman_region32_copy(dest, (pixman_region32_t *)src);
64 2 : }
65 :
66 : #define FIND_BAND(r, r_band_end, r_end, ry1) \
67 : do { \
68 : ry1 = r->y1; \
69 : r_band_end = r + 1; \
70 : while ((r_band_end != r_end) && (r_band_end->y1 == ry1)) { \
71 : r_band_end++; \
72 : } \
73 : } while (0)
74 :
75 1128951 : static int test_band(int query,
76 : int res,
77 : pixman_box32_t *r1,
78 : pixman_box32_t *r1_end,
79 : pixman_box32_t *r2,
80 : pixman_box32_t *r2_end)
81 : {
82 : int x1;
83 : int x2;
84 :
85 : do {
86 1128951 : x1 = MAX(r1->x1, r2->x1);
87 1128951 : x2 = MIN(r1->x2, r2->x2);
88 :
89 : /*
90 : * Is there any overlap between the two rectangles?
91 : */
92 1128951 : if (x1 < x2) {
93 844106 : res |= REGION_TEST_SHARED;
94 :
95 844106 : if (r1->x1 < r2->x1 || r1->x2 > r2->x2) {
96 590569 : res |= REGION_TEST_LEFT_EXCLUSIVE;
97 : }
98 :
99 844106 : if (r2->x1 < r1->x1 || r2->x2 > r1->x2) {
100 590397 : res |= REGION_TEST_RIGHT_EXCLUSIVE;
101 : }
102 : } else {
103 : /* No overlap at all, the leftmost is exclusive */
104 284845 : if (r1->x1 < r2->x1) {
105 141906 : res |= REGION_TEST_LEFT_EXCLUSIVE;
106 : } else {
107 142939 : res |= REGION_TEST_RIGHT_EXCLUSIVE;
108 : }
109 : }
110 :
111 1128951 : if ((res & query) == query) {
112 501711 : return res;
113 : }
114 :
115 : /*
116 : * Advance the pointer(s) with the leftmost right side, since the next
117 : * rectangle on that list may still overlap the other region's
118 : * current rectangle.
119 : */
120 627240 : if (r1->x2 == x2) {
121 315703 : r1++;
122 : }
123 627240 : if (r2->x2 == x2) {
124 316268 : r2++;
125 : }
126 627240 : } while ((r1 != r1_end) && (r2 != r2_end));
127 :
128 : /*
129 : * Deal with whichever band (if any) still has rectangles left.
130 : */
131 448852 : if (r1 != r1_end) {
132 222761 : res |= REGION_TEST_LEFT_EXCLUSIVE;
133 226091 : } else if (r2 != r2_end) {
134 221932 : res |= REGION_TEST_RIGHT_EXCLUSIVE;
135 : }
136 :
137 448852 : return res;
138 : }
139 :
140 626641 : static int test_generic (pixman_region32_t *reg1,
141 : pixman_region32_t *reg2,
142 : int query)
143 : {
144 : pixman_box32_t *r1; /* Pointer into first region */
145 : pixman_box32_t *r2; /* Pointer into 2d region */
146 : pixman_box32_t *r1_end; /* End of 1st region */
147 : pixman_box32_t *r2_end; /* End of 2d region */
148 : int ybot; /* Bottom of intersection */
149 : int ytop; /* Top of intersection */
150 : pixman_box32_t * r1_band_end; /* End of current band in r1 */
151 : pixman_box32_t * r2_band_end; /* End of current band in r2 */
152 : int top; /* Top of non-overlapping band */
153 : int bot; /* Bottom of non-overlapping band*/
154 : int r1y1; /* Temps for r1->y1 and r2->y1 */
155 : int r2y1;
156 : int r1_num_rects;
157 : int r2_num_rects;
158 : int res;
159 :
160 626641 : r1 = pixman_region32_rectangles(reg1, &r1_num_rects);
161 626641 : r1_end = r1 + r1_num_rects;
162 :
163 626641 : r2 = pixman_region32_rectangles(reg2, &r2_num_rects);
164 626641 : r2_end = r2 + r2_num_rects;
165 :
166 626641 : res = 0;
167 :
168 : /*
169 : * Initialize ybot.
170 : * In the upcoming loop, ybot and ytop serve different functions depending
171 : * on whether the band being handled is an overlapping or non-overlapping
172 : * band.
173 : * In the case of a non-overlapping band (only one of the regions
174 : * has points in the band), ybot is the bottom of the most recent
175 : * intersection and thus clips the top of the rectangles in that band.
176 : * ytop is the top of the next intersection between the two regions and
177 : * serves to clip the bottom of the rectangles in the current band.
178 : * For an overlapping band (where the two regions intersect), ytop clips
179 : * the top of the rectangles of both regions and ybot clips the bottoms.
180 : */
181 :
182 626641 : ybot = MIN(r1->y1, r2->y1);
183 :
184 : do {
185 : /*
186 : * This algorithm proceeds one source-band (as opposed to a
187 : * destination band, which is determined by where the two regions
188 : * intersect) at a time. r1_band_end and r2_band_end serve to mark the
189 : * rectangle after the last one in the current band for their
190 : * respective regions.
191 : */
192 2054532 : FIND_BAND(r1, r1_band_end, r1_end, r1y1);
193 2053714 : FIND_BAND(r2, r2_band_end, r2_end, r2y1);
194 :
195 : /*
196 : * First handle the band that doesn't intersect, if any.
197 : *
198 : * Note that attention is restricted to one band in the
199 : * non-intersecting region at once, so if a region has n
200 : * bands between the current position and the next place it overlaps
201 : * the other, this entire loop will be passed through n times.
202 : */
203 1809371 : if (r1y1 < r2y1) {
204 862132 : top = MAX (r1y1, ybot);
205 862132 : bot = MIN (r1->y2, r2y1);
206 862132 : if (top != bot) {
207 671160 : res |= REGION_TEST_LEFT_EXCLUSIVE;
208 :
209 671160 : if ((res & query) == query) {
210 46020 : return res & query;
211 : }
212 : }
213 :
214 816112 : ytop = r2y1;
215 947239 : } else if (r2y1 < r1y1) {
216 858947 : top = MAX (r2y1, ybot);
217 858947 : bot = MIN (r2->y2, r1y1);
218 :
219 858947 : if (top != bot) {
220 669799 : res |= REGION_TEST_RIGHT_EXCLUSIVE;
221 :
222 669799 : if ((res & query) == query) {
223 45732 : return res & query;
224 : }
225 : }
226 813215 : ytop = r1y1;
227 : } else {
228 88292 : ytop = r1y1;
229 : }
230 :
231 : /*
232 : * Now see if we've hit an intersecting band. The two bands only
233 : * intersect if ybot > ytop
234 : */
235 1717619 : ybot = MIN (r1->y2, r2->y2);
236 1717619 : if (ybot > ytop) {
237 950563 : res = test_band(query, res,
238 : r1, r1_band_end,
239 : r2, r2_band_end);
240 950563 : if ((res & query) == query) {
241 520405 : return res & query;
242 : }
243 : }
244 :
245 : /*
246 : * If we've finished with a band (y2 == ybot) we skip forward
247 : * in the region to the next band.
248 : */
249 1197214 : if (r1->y2 == ybot) {
250 605827 : r1 = r1_band_end;
251 : }
252 :
253 1197214 : if (r2->y2 == ybot) {
254 607614 : r2 = r2_band_end;
255 : }
256 :
257 : }
258 1197214 : while (r1 != r1_end && r2 != r2_end);
259 :
260 : /*
261 : * Deal with whichever region (if any) still has rectangles left.
262 : */
263 :
264 14484 : if (r1 != r1_end) {
265 7074 : res |= REGION_TEST_LEFT_EXCLUSIVE;
266 7410 : } else if (r2 != r2_end) {
267 7380 : res |= REGION_TEST_RIGHT_EXCLUSIVE;
268 : }
269 :
270 14484 : return res & query;
271 : }
272 :
273 700075 : int region_test(const QRegion *_reg1, const QRegion *_reg2, int query)
274 : {
275 : int res;
276 700075 : pixman_region32_t *reg1 = (pixman_region32_t *)_reg1;
277 700075 : pixman_region32_t *reg2 = (pixman_region32_t *)_reg2;
278 :
279 700075 : query = (query) ? query & REGION_TEST_ALL : REGION_TEST_ALL;
280 :
281 700075 : res = 0;
282 :
283 700075 : if (!pixman_region32_not_empty(reg1) || !pixman_region32_not_empty(reg2) ||
284 631581 : !EXTENTCHECK (®1->extents, ®2->extents)) {
285 : /* One or more regions are empty or they are disjoint */
286 :
287 72525 : if (pixman_region32_not_empty(reg1)) {
288 37026 : res |= REGION_TEST_LEFT_EXCLUSIVE;
289 : }
290 :
291 72525 : if (pixman_region32_not_empty(reg2)) {
292 37946 : res |= REGION_TEST_RIGHT_EXCLUSIVE;
293 : }
294 :
295 72525 : return res & query;
296 627550 : } else if (!reg1->data && !reg2->data) {
297 : /* Just two rectangles that intersect */
298 889 : res |= REGION_TEST_SHARED;
299 :
300 889 : if (!SUBSUMES(®1->extents, ®2->extents)) {
301 868 : res |= REGION_TEST_RIGHT_EXCLUSIVE;
302 : }
303 :
304 889 : if (!SUBSUMES(®2->extents, ®1->extents)) {
305 875 : res |= REGION_TEST_LEFT_EXCLUSIVE;
306 : }
307 :
308 889 : return res & query;
309 626661 : } else if (!reg2->data && SUBSUMES (®2->extents, ®1->extents)) {
310 : /* reg2 is just a rect that contains all of reg1 */
311 :
312 6 : res |= REGION_TEST_SHARED; /* some piece must be shared, because reg is not empty */
313 6 : res |= REGION_TEST_RIGHT_EXCLUSIVE; /* reg2 contains all of reg1 and then some */
314 :
315 6 : return res & query;
316 626655 : } else if (!reg1->data && SUBSUMES (®1->extents, ®2->extents)) {
317 : /* reg1 is just a rect that contains all of reg2 */
318 :
319 14 : res |= REGION_TEST_SHARED; /* some piece must be shared, because reg is not empty */
320 14 : res |= REGION_TEST_LEFT_EXCLUSIVE; /* reg1 contains all of reg2 and then some */
321 :
322 14 : return res & query;
323 626641 : } else if (reg1 == reg2) {
324 0 : res |= REGION_TEST_SHARED;
325 0 : return res & query;
326 : } else {
327 : /* General purpose intersection */
328 626641 : return test_generic (reg1, reg2, query);
329 : }
330 : }
331 :
332 17 : int region_is_valid(const QRegion *rgn)
333 : {
334 17 : return pixman_region32_selfcheck((pixman_region32_t *)rgn);
335 : }
336 :
337 102 : int region_is_empty(const QRegion *rgn)
338 : {
339 102 : return !pixman_region32_not_empty((pixman_region32_t *)rgn);
340 : }
341 :
342 0 : SpiceRect *region_dup_rects(const QRegion *rgn, uint32_t *num_rects)
343 : {
344 : pixman_box32_t *boxes;
345 : SpiceRect *rects;
346 : int n, i;
347 :
348 0 : boxes = pixman_region32_rectangles((pixman_region32_t *)rgn, &n);
349 0 : if (num_rects) {
350 0 : *num_rects = n;
351 : }
352 0 : rects = spice_new(SpiceRect, n);
353 0 : for (i = 0; i < n; i++) {
354 0 : rects[i].left = boxes[i].x1;
355 0 : rects[i].top = boxes[i].y1;
356 0 : rects[i].right = boxes[i].x2;
357 0 : rects[i].bottom = boxes[i].y2;
358 : }
359 0 : return rects;
360 : }
361 :
362 0 : void region_ret_rects(const QRegion *rgn, SpiceRect *rects, uint32_t num_rects)
363 : {
364 : pixman_box32_t *boxes;
365 : unsigned int n, i;
366 :
367 0 : boxes = pixman_region32_rectangles((pixman_region32_t *)rgn, (int *)&n);
368 0 : for (i = 0; i < n && i < num_rects; i++) {
369 0 : rects[i].left = boxes[i].x1;
370 0 : rects[i].top = boxes[i].y1;
371 0 : rects[i].right = boxes[i].x2;
372 0 : rects[i].bottom = boxes[i].y2;
373 : }
374 :
375 0 : if (i && i != n) {
376 : unsigned int x;
377 :
378 0 : for (x = 0; x < (n - num_rects); ++x) {
379 0 : rects[i - 1].left = MIN(rects[i - 1].left, boxes[i + x].x1);
380 0 : rects[i - 1].top = MIN(rects[i - 1].top, boxes[i + x].y1);
381 0 : rects[i - 1].right = MAX(rects[i - 1].right, boxes[i + x].x2);
382 0 : rects[i - 1].bottom = MAX(rects[i - 1].bottom, boxes[i + x].y2);
383 : }
384 : }
385 0 : }
386 :
387 0 : void region_extents(const QRegion *rgn, SpiceRect *r)
388 : {
389 : pixman_box32_t *extents;
390 :
391 0 : extents = pixman_region32_extents((pixman_region32_t *)rgn);
392 :
393 0 : r->left = extents->x1;
394 0 : r->top = extents->y1;
395 0 : r->right = extents->x2;
396 0 : r->bottom = extents->y2;
397 0 : }
398 :
399 51 : int region_is_equal(const QRegion *rgn1, const QRegion *rgn2)
400 : {
401 51 : return pixman_region32_equal((pixman_region32_t *)rgn1, (pixman_region32_t *)rgn2);
402 : }
403 :
404 51 : int region_intersects(const QRegion *rgn1, const QRegion *rgn2)
405 : {
406 : int test_res;
407 :
408 51 : if (!region_bounds_intersects(rgn1, rgn2)) {
409 27 : return FALSE;
410 : }
411 :
412 24 : test_res = region_test(rgn1, rgn2, REGION_TEST_SHARED);
413 24 : return !!test_res;
414 : }
415 :
416 51 : int region_bounds_intersects(const QRegion *rgn1, const QRegion *rgn2)
417 : {
418 : pixman_box32_t *extents1, *extents2;
419 :
420 51 : extents1 = pixman_region32_extents((pixman_region32_t *)rgn1);
421 51 : extents2 = pixman_region32_extents((pixman_region32_t *)rgn2);
422 :
423 51 : return EXTENTCHECK(extents1, extents2);
424 : }
425 :
426 51 : int region_contains(const QRegion *rgn, const QRegion *other)
427 : {
428 : int test_res;
429 :
430 51 : test_res = region_test(rgn, other, REGION_TEST_RIGHT_EXCLUSIVE);
431 51 : return !test_res;
432 : }
433 :
434 0 : int region_contains_point(const QRegion *rgn, int32_t x, int32_t y)
435 : {
436 0 : return pixman_region32_contains_point((pixman_region32_t *)rgn, x, y, NULL);
437 : }
438 :
439 0 : void region_or(QRegion *rgn, const QRegion *other_rgn)
440 : {
441 0 : pixman_region32_union(rgn, rgn, (pixman_region32_t *)other_rgn);
442 0 : }
443 :
444 1 : void region_and(QRegion *rgn, const QRegion *other_rgn)
445 : {
446 1 : pixman_region32_intersect(rgn, rgn, (pixman_region32_t *)other_rgn);
447 1 : }
448 :
449 0 : void region_xor(QRegion *rgn, const QRegion *other_rgn)
450 : {
451 : pixman_region32_t intersection;
452 :
453 0 : pixman_region32_init(&intersection);
454 0 : pixman_region32_copy(&intersection, rgn);
455 0 : pixman_region32_intersect(&intersection,
456 : &intersection,
457 : (pixman_region32_t *)other_rgn);
458 0 : pixman_region32_union(rgn, rgn, (pixman_region32_t *)other_rgn);
459 0 : pixman_region32_subtract(rgn, rgn, &intersection);
460 0 : pixman_region32_fini(&intersection);
461 0 : }
462 :
463 0 : void region_exclude(QRegion *rgn, const QRegion *other_rgn)
464 : {
465 0 : pixman_region32_subtract(rgn, rgn, (pixman_region32_t *)other_rgn);
466 0 : }
467 :
468 1902195 : void region_add(QRegion *rgn, const SpiceRect *r)
469 : {
470 1902195 : pixman_region32_union_rect(rgn, rgn, r->left, r->top,
471 1902195 : r->right - r->left,
472 1902195 : r->bottom - r->top);
473 1902195 : }
474 :
475 0 : void region_remove(QRegion *rgn, const SpiceRect *r)
476 : {
477 : pixman_region32_t rg;
478 :
479 0 : pixman_region32_init_rect(&rg, r->left, r->top,
480 0 : r->right - r->left,
481 0 : r->bottom - r->top);
482 0 : pixman_region32_subtract(rgn, rgn, &rg);
483 0 : pixman_region32_fini(&rg);
484 0 : }
485 :
486 :
487 0 : void region_offset(QRegion *rgn, int32_t dx, int32_t dy)
488 : {
489 0 : pixman_region32_translate(rgn, dx, dy);
490 0 : }
491 :
492 0 : void region_dump(const QRegion *rgn, const char *prefix)
493 : {
494 : pixman_box32_t *rects, *extents;
495 : int n_rects, i;
496 :
497 0 : printf("%sREGION: %p, ", prefix, rgn);
498 :
499 0 : if (!pixman_region32_not_empty((pixman_region32_t *)rgn)) {
500 0 : printf("EMPTY\n");
501 0 : return;
502 : }
503 :
504 0 : extents = pixman_region32_extents((pixman_region32_t *)rgn);
505 0 : rects = pixman_region32_rectangles((pixman_region32_t *)rgn, &n_rects);
506 0 : printf("num %u bounds (%d, %d, %d, %d)\n",
507 : n_rects,
508 : extents->x1,
509 : extents->y1,
510 : extents->x2,
511 : extents->y2);
512 :
513 :
514 0 : for (i = 0; i < n_rects; i++) {
515 0 : printf("%*s %12d %12d %12d %12d\n",
516 0 : (int)strlen(prefix), "",
517 0 : rects[i].x1,
518 0 : rects[i].y1,
519 0 : rects[i].x2,
520 0 : rects[i].y2);
521 : }
522 : }
|
