1 /* -*- mode: C; c-file-style: "gnu"; indent-tabs-mode: nil; -*- */
2 /*
3 * Utilities for region manipulation
4 *
5 * Copyright (C) 2010 Red Hat, Inc.
6 *
7 * This program is free software; you can redistribute it and/or
8 * modify it under the terms of the GNU General Public License as
9 * published by the Free Software Foundation; either version 2 of the
10 * License, or (at your option) any later version.
11 *
12 * This program is distributed in the hope that it will be useful, but
13 * WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 * General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with this program; if not, see <http://www.gnu.org/licenses/>.
19 */
20
21 #include "config.h"
22
23 #include "backends/meta-monitor-transform.h"
24 #include "compositor/region-utils.h"
25 #include "core/boxes-private.h"
26
27 #include <math.h>
28
29 #define META_REGION_MAX_STACK_RECTS 256
30
31 #define META_REGION_CREATE_RECTANGLE_ARRAY_SCOPED(n_rects, rects) \
32 g_autofree cairo_rectangle_int_t *G_PASTE(__n, __LINE__) = NULL; \
33 if (n_rects < META_REGION_MAX_STACK_RECTS) \
34 rects = g_newa (cairo_rectangle_int_t, n_rects); \
35 else \
36 rects = G_PASTE(__n, __LINE__) = g_new (cairo_rectangle_int_t, n_rects);
37
38 /* MetaRegionBuilder */
39
40 /* Various algorithms in this file require unioning together a set of rectangles
41 * that are unsorted or overlap; unioning such a set of rectangles 1-by-1
42 * using cairo_region_union_rectangle() produces O(N^2) behavior (if the union
43 * adds or removes rectangles in the middle of the region, then it has to
44 * move all the rectangles after that.) To avoid this behavior, MetaRegionBuilder
45 * creates regions for small groups of rectangles and merges them together in
46 * a binary tree.
47 *
48 * Possible improvement: From a glance at the code, accumulating all the rectangles
49 * into a flat array and then calling the (not usefully documented)
50 * cairo_region_create_rectangles() would have the same behavior and would be
51 * simpler and a bit more efficient.
52 */
53
54 /* Optimium performance seems to be with MAX_CHUNK_RECTANGLES=4; 8 is about 10% slower.
55 * But using 8 may be more robust to systems with slow malloc(). */
56 #define MAX_CHUNK_RECTANGLES 8
57
58 void
meta_region_builder_init(MetaRegionBuilder * builder)59 meta_region_builder_init (MetaRegionBuilder *builder)
60 {
61 int i;
62 for (i = 0; i < META_REGION_BUILDER_MAX_LEVELS; i++)
63 builder->levels[i] = NULL;
64 builder->n_levels = 1;
65 }
66
67 void
meta_region_builder_add_rectangle(MetaRegionBuilder * builder,int x,int y,int width,int height)68 meta_region_builder_add_rectangle (MetaRegionBuilder *builder,
69 int x,
70 int y,
71 int width,
72 int height)
73 {
74 cairo_rectangle_int_t rect;
75 int i;
76
77 if (builder->levels[0] == NULL)
78 builder->levels[0] = cairo_region_create ();
79
80 rect.x = x;
81 rect.y = y;
82 rect.width = width;
83 rect.height = height;
84
85 cairo_region_union_rectangle (builder->levels[0], &rect);
86 if (cairo_region_num_rectangles (builder->levels[0]) >= MAX_CHUNK_RECTANGLES)
87 {
88 for (i = 1; i < builder->n_levels + 1; i++)
89 {
90 if (builder->levels[i] == NULL)
91 {
92 if (i < META_REGION_BUILDER_MAX_LEVELS)
93 {
94 builder->levels[i] = builder->levels[i - 1];
95 builder->levels[i - 1] = NULL;
96 if (i == builder->n_levels)
97 builder->n_levels++;
98 }
99
100 break;
101 }
102 else
103 {
104 cairo_region_union (builder->levels[i], builder->levels[i - 1]);
105 cairo_region_destroy (builder->levels[i - 1]);
106 builder->levels[i - 1] = NULL;
107 }
108 }
109 }
110 }
111
112 cairo_region_t *
meta_region_builder_finish(MetaRegionBuilder * builder)113 meta_region_builder_finish (MetaRegionBuilder *builder)
114 {
115 cairo_region_t *result = NULL;
116 int i;
117
118 for (i = 0; i < builder->n_levels; i++)
119 {
120 if (builder->levels[i])
121 {
122 if (result == NULL)
123 result = builder->levels[i];
124 else
125 {
126 cairo_region_union(result, builder->levels[i]);
127 cairo_region_destroy (builder->levels[i]);
128 }
129 }
130 }
131
132 if (result == NULL)
133 result = cairo_region_create ();
134
135 return result;
136 }
137
138
139 /* MetaRegionIterator */
140
141 void
meta_region_iterator_init(MetaRegionIterator * iter,cairo_region_t * region)142 meta_region_iterator_init (MetaRegionIterator *iter,
143 cairo_region_t *region)
144 {
145 iter->region = region;
146 iter->i = 0;
147 iter->n_rectangles = cairo_region_num_rectangles (region);
148 iter->line_start = TRUE;
149
150 if (iter->n_rectangles > 1)
151 {
152 cairo_region_get_rectangle (region, 0, &iter->rectangle);
153 cairo_region_get_rectangle (region, 1, &iter->next_rectangle);
154
155 iter->line_end = iter->next_rectangle.y != iter->rectangle.y;
156 }
157 else if (iter->n_rectangles > 0)
158 {
159 cairo_region_get_rectangle (region, 0, &iter->rectangle);
160 iter->line_end = TRUE;
161 }
162 }
163
164 gboolean
meta_region_iterator_at_end(MetaRegionIterator * iter)165 meta_region_iterator_at_end (MetaRegionIterator *iter)
166 {
167 return iter->i >= iter->n_rectangles;
168 }
169
170 void
meta_region_iterator_next(MetaRegionIterator * iter)171 meta_region_iterator_next (MetaRegionIterator *iter)
172 {
173 iter->i++;
174 iter->rectangle = iter->next_rectangle;
175 iter->line_start = iter->line_end;
176
177 if (iter->i + 1 < iter->n_rectangles)
178 {
179 cairo_region_get_rectangle (iter->region, iter->i + 1, &iter->next_rectangle);
180 iter->line_end = iter->next_rectangle.y != iter->rectangle.y;
181 }
182 else
183 {
184 iter->line_end = TRUE;
185 }
186 }
187
188 cairo_region_t *
meta_region_scale_double(cairo_region_t * region,double scale,MetaRoundingStrategy rounding_strategy)189 meta_region_scale_double (cairo_region_t *region,
190 double scale,
191 MetaRoundingStrategy rounding_strategy)
192 {
193 int n_rects, i;
194 cairo_rectangle_int_t *rects;
195 cairo_region_t *scaled_region;
196
197 g_return_val_if_fail (scale > 0.0, NULL);
198
199 if (G_APPROX_VALUE (scale, 1.f, FLT_EPSILON))
200 return cairo_region_copy (region);
201
202 n_rects = cairo_region_num_rectangles (region);
203 META_REGION_CREATE_RECTANGLE_ARRAY_SCOPED (n_rects, rects);
204 for (i = 0; i < n_rects; i++)
205 {
206 cairo_region_get_rectangle (region, i, &rects[i]);
207
208 meta_rectangle_scale_double (&rects[i], scale, rounding_strategy,
209 &rects[i]);
210 }
211
212 scaled_region = cairo_region_create_rectangles (rects, n_rects);
213
214 return scaled_region;
215 }
216
217 cairo_region_t *
meta_region_scale(cairo_region_t * region,int scale)218 meta_region_scale (cairo_region_t *region, int scale)
219 {
220 int n_rects, i;
221 cairo_rectangle_int_t *rects;
222 cairo_region_t *scaled_region;
223
224 if (scale == 1)
225 return cairo_region_copy (region);
226
227 n_rects = cairo_region_num_rectangles (region);
228 META_REGION_CREATE_RECTANGLE_ARRAY_SCOPED (n_rects, rects);
229 for (i = 0; i < n_rects; i++)
230 {
231 cairo_region_get_rectangle (region, i, &rects[i]);
232 rects[i].x *= scale;
233 rects[i].y *= scale;
234 rects[i].width *= scale;
235 rects[i].height *= scale;
236 }
237
238 scaled_region = cairo_region_create_rectangles (rects, n_rects);
239
240 return scaled_region;
241 }
242
243 static void
add_expanded_rect(MetaRegionBuilder * builder,int x,int y,int width,int height,int x_amount,int y_amount,gboolean flip)244 add_expanded_rect (MetaRegionBuilder *builder,
245 int x,
246 int y,
247 int width,
248 int height,
249 int x_amount,
250 int y_amount,
251 gboolean flip)
252 {
253 if (flip)
254 meta_region_builder_add_rectangle (builder,
255 y - y_amount, x - x_amount,
256 height + 2 * y_amount, width + 2 * x_amount);
257 else
258 meta_region_builder_add_rectangle (builder,
259 x - x_amount, y - y_amount,
260 width + 2 * x_amount, height + 2 * y_amount);
261 }
262
263 static cairo_region_t *
expand_region(cairo_region_t * region,int x_amount,int y_amount,gboolean flip)264 expand_region (cairo_region_t *region,
265 int x_amount,
266 int y_amount,
267 gboolean flip)
268 {
269 MetaRegionBuilder builder;
270 int n;
271 int i;
272
273 meta_region_builder_init (&builder);
274
275 n = cairo_region_num_rectangles (region);
276 for (i = 0; i < n; i++)
277 {
278 cairo_rectangle_int_t rect;
279
280 cairo_region_get_rectangle (region, i, &rect);
281 add_expanded_rect (&builder,
282 rect.x, rect.y, rect.width, rect.height,
283 x_amount, y_amount, flip);
284 }
285
286 return meta_region_builder_finish (&builder);
287 }
288
289 /* This computes a (clipped version) of the inverse of the region
290 * and expands it by the given amount */
291 static cairo_region_t *
expand_region_inverse(cairo_region_t * region,int x_amount,int y_amount,gboolean flip)292 expand_region_inverse (cairo_region_t *region,
293 int x_amount,
294 int y_amount,
295 gboolean flip)
296 {
297 MetaRegionBuilder builder;
298 MetaRegionIterator iter;
299 cairo_rectangle_int_t extents;
300
301 int last_x;
302
303 meta_region_builder_init (&builder);
304
305 cairo_region_get_extents (region, &extents);
306 add_expanded_rect (&builder,
307 extents.x, extents.y - 1, extents.width, 1,
308 x_amount, y_amount, flip);
309 add_expanded_rect (&builder,
310 extents.x - 1, extents.y, 1, extents.height,
311 x_amount, y_amount, flip);
312 add_expanded_rect (&builder,
313 extents.x + extents.width, extents.y, 1, extents.height,
314 x_amount, y_amount, flip);
315 add_expanded_rect (&builder,
316 extents.x, extents.y + extents.height, extents.width, 1,
317 x_amount, y_amount, flip);
318
319 last_x = extents.x;
320 for (meta_region_iterator_init (&iter, region);
321 !meta_region_iterator_at_end (&iter);
322 meta_region_iterator_next (&iter))
323 {
324 if (iter.rectangle.x > last_x)
325 add_expanded_rect (&builder,
326 last_x, iter.rectangle.y,
327 iter.rectangle.x - last_x, iter.rectangle.height,
328 x_amount, y_amount, flip);
329
330 if (iter.line_end)
331 {
332 if (extents.x + extents.width > iter.rectangle.x + iter.rectangle.width)
333 add_expanded_rect (&builder,
334 iter.rectangle.x + iter.rectangle.width, iter.rectangle.y,
335 (extents.x + extents.width) - (iter.rectangle.x + iter.rectangle.width), iter.rectangle.height,
336 x_amount, y_amount, flip);
337 last_x = extents.x;
338 }
339 else
340 last_x = iter.rectangle.x + iter.rectangle.width;
341 }
342
343 return meta_region_builder_finish (&builder);
344 }
345
346 /**
347 * meta_make_border_region:
348 * @region: a #cairo_region_t
349 * @x_amount: distance from the border to extend horizontally
350 * @y_amount: distance from the border to extend vertically
351 * @flip: if true, the result is computed with x and y interchanged
352 *
353 * Computes the "border region" of a given region, which is roughly
354 * speaking the set of points near the boundary of the region. If we
355 * define the operation of growing a region as computing the set of
356 * points within a given manhattan distance of the region, then the
357 * border is 'grow(region) intersect grow(inverse(region))'.
358 *
359 * If we create an image by filling the region with a solid color,
360 * the border is the region affected by blurring the region.
361 *
362 * Return value: a new region which is the border of the given region
363 */
364 cairo_region_t *
meta_make_border_region(cairo_region_t * region,int x_amount,int y_amount,gboolean flip)365 meta_make_border_region (cairo_region_t *region,
366 int x_amount,
367 int y_amount,
368 gboolean flip)
369 {
370 cairo_region_t *border_region;
371 cairo_region_t *inverse_region;
372
373 border_region = expand_region (region, x_amount, y_amount, flip);
374 inverse_region = expand_region_inverse (region, x_amount, y_amount, flip);
375 cairo_region_intersect (border_region, inverse_region);
376 cairo_region_destroy (inverse_region);
377
378 return border_region;
379 }
380
381 cairo_region_t *
meta_region_transform(const cairo_region_t * region,MetaMonitorTransform transform,int width,int height)382 meta_region_transform (const cairo_region_t *region,
383 MetaMonitorTransform transform,
384 int width,
385 int height)
386 {
387 int n_rects, i;
388 cairo_rectangle_int_t *rects;
389 cairo_region_t *transformed_region;
390
391 if (transform == META_MONITOR_TRANSFORM_NORMAL)
392 return cairo_region_copy (region);
393
394 n_rects = cairo_region_num_rectangles (region);
395 META_REGION_CREATE_RECTANGLE_ARRAY_SCOPED (n_rects, rects);
396 for (i = 0; i < n_rects; i++)
397 {
398 cairo_region_get_rectangle (region, i, &rects[i]);
399
400 meta_rectangle_transform (&rects[i],
401 transform,
402 width,
403 height,
404 &rects[i]);
405 }
406
407 transformed_region = cairo_region_create_rectangles (rects, n_rects);
408
409 return transformed_region;
410 }
411
412 cairo_region_t *
meta_region_crop_and_scale(cairo_region_t * region,graphene_rect_t * src_rect,int dst_width,int dst_height)413 meta_region_crop_and_scale (cairo_region_t *region,
414 graphene_rect_t *src_rect,
415 int dst_width,
416 int dst_height)
417 {
418 int n_rects, i;
419 cairo_rectangle_int_t *rects;
420 cairo_region_t *viewport_region;
421
422 if (G_APPROX_VALUE (src_rect->size.width, dst_width, FLT_EPSILON) &&
423 G_APPROX_VALUE (src_rect->size.height, dst_height, FLT_EPSILON) &&
424 G_APPROX_VALUE (roundf (src_rect->origin.x),
425 src_rect->origin.x, FLT_EPSILON) &&
426 G_APPROX_VALUE (roundf (src_rect->origin.y),
427 src_rect->origin.y, FLT_EPSILON))
428 {
429 viewport_region = cairo_region_copy (region);
430
431 if (!G_APPROX_VALUE (src_rect->origin.x, 0, FLT_EPSILON) ||
432 !G_APPROX_VALUE (src_rect->origin.y, 0, FLT_EPSILON))
433 {
434 cairo_region_translate (viewport_region,
435 (int) src_rect->origin.x,
436 (int) src_rect->origin.y);
437 }
438
439 return viewport_region;
440 }
441
442 n_rects = cairo_region_num_rectangles (region);
443 META_REGION_CREATE_RECTANGLE_ARRAY_SCOPED (n_rects, rects);
444 for (i = 0; i < n_rects; i++)
445 {
446 cairo_region_get_rectangle (region, i, &rects[i]);
447
448 meta_rectangle_crop_and_scale (&rects[i],
449 src_rect,
450 dst_width,
451 dst_height,
452 &rects[i]);
453 }
454
455 viewport_region = cairo_region_create_rectangles (rects, n_rects);
456
457 return viewport_region;
458 }
459