1
/* -*- mode: C; c-file-style: "gnu"; indent-tabs-mode: nil; -*- */
3
* Utilities for region manipulation
5
* Copyright (C) 2010 Red Hat, Inc.
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.
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.
17
* You should have received a copy of the GNU General Public License
18
* along with this program; if not, write to the Free Software
19
* Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
23
#include "region-utils.h"
27
/* MetaRegionBuilder */
29
/* Various algorithms in this file require unioning together a set of rectangles
30
* that are unsorted or overlap; unioning such a set of rectangles 1-by-1
31
* using cairo_region_union_rectangle() produces O(N^2) behavior (if the union
32
* adds or removes rectangles in the middle of the region, then it has to
33
* move all the rectangles after that.) To avoid this behavior, MetaRegionBuilder
34
* creates regions for small groups of rectangles and merges them together in
37
* Possible improvement: From a glance at the code, accumulating all the rectangles
38
* into a flat array and then calling the (not usefully documented)
39
* cairo_region_create_rectangles() would have the same behavior and would be
40
* simpler and a bit more efficient.
43
/* Optimium performance seems to be with MAX_CHUNK_RECTANGLES=4; 8 is about 10% slower.
44
* But using 8 may be more robust to systems with slow malloc(). */
45
#define MAX_CHUNK_RECTANGLES 8
50
/* To merge regions in binary tree order, we need to keep track of
51
* the regions that we've already merged together at different
52
* levels of the tree. We fill in an array in the pattern:
60
cairo_region_t *levels[MAX_LEVELS];
65
meta_region_builder_init (MetaRegionBuilder *builder)
68
for (i = 0; i < MAX_LEVELS; i++)
69
builder->levels[i] = NULL;
70
builder->n_levels = 1;
74
meta_region_builder_add_rectangle (MetaRegionBuilder *builder,
80
cairo_rectangle_int_t rect;
83
if (builder->levels[0] == NULL)
84
builder->levels[0] = cairo_region_create ();
91
cairo_region_union_rectangle (builder->levels[0], &rect);
92
if (cairo_region_num_rectangles (builder->levels[0]) >= MAX_CHUNK_RECTANGLES)
94
for (i = 1; i < builder->n_levels + 1; i++)
96
if (builder->levels[i] == NULL)
100
builder->levels[i] = builder->levels[i - 1];
101
builder->levels[i - 1] = NULL;
102
if (i == builder->n_levels)
110
cairo_region_union (builder->levels[i], builder->levels[i - 1]);
111
cairo_region_destroy (builder->levels[i - 1]);
112
builder->levels[i - 1] = NULL;
118
static cairo_region_t *
119
meta_region_builder_finish (MetaRegionBuilder *builder)
121
cairo_region_t *result = NULL;
124
for (i = 0; i < builder->n_levels; i++)
126
if (builder->levels[i])
129
result = builder->levels[i];
132
cairo_region_union(result, builder->levels[i]);
133
cairo_region_destroy (builder->levels[i]);
139
result = cairo_region_create ();
145
/* MetaRegionIterator */
148
meta_region_iterator_init (MetaRegionIterator *iter,
149
cairo_region_t *region)
151
iter->region = region;
153
iter->n_rectangles = cairo_region_num_rectangles (region);
154
iter->line_start = TRUE;
156
if (iter->n_rectangles > 1)
158
cairo_region_get_rectangle (region, 0, &iter->rectangle);
159
cairo_region_get_rectangle (region, 1, &iter->next_rectangle);
161
iter->line_end = iter->next_rectangle.y != iter->rectangle.y;
163
else if (iter->n_rectangles > 0)
165
cairo_region_get_rectangle (region, 0, &iter->rectangle);
166
iter->line_end = TRUE;
171
meta_region_iterator_at_end (MetaRegionIterator *iter)
173
return iter->i >= iter->n_rectangles;
177
meta_region_iterator_next (MetaRegionIterator *iter)
180
iter->rectangle = iter->next_rectangle;
181
iter->line_start = iter->line_end;
183
if (iter->i < iter->n_rectangles)
185
cairo_region_get_rectangle (iter->region, iter->i + 1, &iter->next_rectangle);
186
iter->line_end = iter->next_rectangle.y != iter->rectangle.y;
190
iter->line_end = TRUE;
195
add_expanded_rect (MetaRegionBuilder *builder,
205
meta_region_builder_add_rectangle (builder,
206
y - y_amount, x - x_amount,
207
height + 2 * y_amount, width + 2 * x_amount);
209
meta_region_builder_add_rectangle (builder,
210
x - x_amount, y - y_amount,
211
width + 2 * x_amount, height + 2 * y_amount);
214
static cairo_region_t *
215
expand_region (cairo_region_t *region,
220
MetaRegionBuilder builder;
224
meta_region_builder_init (&builder);
226
n = cairo_region_num_rectangles (region);
227
for (i = 0; i < n; i++)
229
cairo_rectangle_int_t rect;
231
cairo_region_get_rectangle (region, i, &rect);
232
add_expanded_rect (&builder,
233
rect.x, rect.y, rect.width, rect.height,
234
x_amount, y_amount, flip);
237
return meta_region_builder_finish (&builder);
240
/* This computes a (clipped version) of the inverse of the region
241
* and expands it by the given amount */
242
static cairo_region_t *
243
expand_region_inverse (cairo_region_t *region,
248
MetaRegionBuilder builder;
249
MetaRegionIterator iter;
250
cairo_rectangle_int_t extents;
251
cairo_region_t *chunk;
255
meta_region_builder_init (&builder);
257
cairo_region_get_extents (region, &extents);
258
add_expanded_rect (&builder,
259
extents.x, extents.y - 1, extents.width, 1,
260
x_amount, y_amount, flip);
261
add_expanded_rect (&builder,
262
extents.x - 1, extents.y, 1, extents.height,
263
x_amount, y_amount, flip);
264
add_expanded_rect (&builder,
265
extents.x + extents.width, extents.y, 1, extents.height,
266
x_amount, y_amount, flip);
267
add_expanded_rect (&builder,
268
extents.x, extents.y + extents.height, extents.width, 1,
269
x_amount, y_amount, flip);
274
for (meta_region_iterator_init (&iter, region);
275
!meta_region_iterator_at_end (&iter);
276
meta_region_iterator_next (&iter))
279
chunk = cairo_region_create ();
281
if (iter.rectangle.x > last_x)
282
add_expanded_rect (&builder,
283
last_x, iter.rectangle.y,
284
iter.rectangle.x - last_x, iter.rectangle.height,
285
x_amount, y_amount, flip);
289
if (extents.x + extents.width > iter.rectangle.x + iter.rectangle.width)
290
add_expanded_rect (&builder,
291
iter.rectangle.x + iter.rectangle.width, iter.rectangle.y,
292
(extents.x + extents.width) - (iter.rectangle.x + iter.rectangle.width), iter.rectangle.height,
293
x_amount, y_amount, flip);
297
last_x = iter.rectangle.x + iter.rectangle.width;
300
return meta_region_builder_finish (&builder);
304
* meta_make_border_region:
305
* @region: a #cairo_region_t
306
* @x_amount: distance from the border to extend horizontally
307
* @y_amount: distance from the border to extend vertically
308
* @flip: if true, the result is computed with x and y interchanged
310
* Computes the "border region" of a given region, which is roughly
311
* speaking the set of points near the boundary of the region. If we
312
* define the operation of growing a region as computing the set of
313
* points within a given manhattan distance of the region, then the
314
* border is 'grow(region) intersect grow(inverse(region))'.
316
* If we create an image by filling the region with a solid color,
317
* the border is the region affected by blurring the region.
319
* Return value: a new region which is the border of the given region
322
meta_make_border_region (cairo_region_t *region,
327
cairo_region_t *border_region;
328
cairo_region_t *inverse_region;
330
border_region = expand_region (region, x_amount, y_amount, flip);
331
inverse_region = expand_region_inverse (region, x_amount, y_amount, flip);
332
cairo_region_intersect (border_region, inverse_region);
333
cairo_region_destroy (inverse_region);
335
return border_region;