1 /* cairo - a vector graphics library with display and print output
2 *
3 * Copyright © 2009 Intel Corporation
4 *
5 * This library is free software; you can redistribute it and/or
6 * modify it either under the terms of the GNU Lesser General Public
7 * License version 2.1 as published by the Free Software Foundation
8 * (the "LGPL") or, at your option, under the terms of the Mozilla
9 * Public License Version 1.1 (the "MPL"). If you do not alter this
10 * notice, a recipient may use your version of this file under either
11 * the MPL or the LGPL.
12 *
13 * You should have received a copy of the LGPL along with this library
14 * in the file COPYING-LGPL-2.1; if not, write to the Free Software
15 * Foundation, Inc., 51 Franklin Street, Suite 500, Boston, MA 02110-1335, USA
16 * You should have received a copy of the MPL along with this library
17 * in the file COPYING-MPL-1.1
18 *
19 * The contents of this file are subject to the Mozilla Public License
20 * Version 1.1 (the "License"); you may not use this file except in
21 * compliance with the License. You may obtain a copy of the License at
22 * http://www.mozilla.org/MPL/
23 *
24 * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
25 * OF ANY KIND, either express or implied. See the LGPL or the MPL for
26 * the specific language governing rights and limitations.
27 *
28 * The Original Code is the cairo graphics library.
29 *
30 * Contributor(s):
31 * Chris Wilson <chris@chris-wilson.co.uk>
32 */
33
34 #include "cairoint.h"
35
36 #include "cairo-boxes-private.h"
37 #include "cairo-error-private.h"
38
39 void
_cairo_boxes_init(cairo_boxes_t * boxes)40 _cairo_boxes_init (cairo_boxes_t *boxes)
41 {
42 boxes->status = CAIRO_STATUS_SUCCESS;
43 boxes->num_limits = 0;
44 boxes->num_boxes = 0;
45
46 boxes->tail = &boxes->chunks;
47 boxes->chunks.next = NULL;
48 boxes->chunks.base = boxes->boxes_embedded;
49 boxes->chunks.size = ARRAY_LENGTH (boxes->boxes_embedded);
50 boxes->chunks.count = 0;
51
52 boxes->is_pixel_aligned = TRUE;
53 }
54
55 void
_cairo_boxes_init_for_array(cairo_boxes_t * boxes,cairo_box_t * array,int num_boxes)56 _cairo_boxes_init_for_array (cairo_boxes_t *boxes,
57 cairo_box_t *array,
58 int num_boxes)
59 {
60 int n;
61
62 boxes->status = CAIRO_STATUS_SUCCESS;
63 boxes->num_limits = 0;
64 boxes->num_boxes = num_boxes;
65
66 boxes->tail = &boxes->chunks;
67 boxes->chunks.next = NULL;
68 boxes->chunks.base = array;
69 boxes->chunks.size = num_boxes;
70 boxes->chunks.count = num_boxes;
71
72 for (n = 0; n < num_boxes; n++) {
73 if (! _cairo_fixed_is_integer (array[n].p1.x) ||
74 ! _cairo_fixed_is_integer (array[n].p1.y) ||
75 ! _cairo_fixed_is_integer (array[n].p2.x) ||
76 ! _cairo_fixed_is_integer (array[n].p2.y))
77 {
78 break;
79 }
80 }
81
82 boxes->is_pixel_aligned = n == num_boxes;
83 }
84
85 void
_cairo_boxes_limit(cairo_boxes_t * boxes,const cairo_box_t * limits,int num_limits)86 _cairo_boxes_limit (cairo_boxes_t *boxes,
87 const cairo_box_t *limits,
88 int num_limits)
89 {
90 int n;
91
92 boxes->limits = limits;
93 boxes->num_limits = num_limits;
94
95 if (boxes->num_limits) {
96 boxes->limit = limits[0];
97 for (n = 1; n < num_limits; n++) {
98 if (limits[n].p1.x < boxes->limit.p1.x)
99 boxes->limit.p1.x = limits[n].p1.x;
100
101 if (limits[n].p1.y < boxes->limit.p1.y)
102 boxes->limit.p1.y = limits[n].p1.y;
103
104 if (limits[n].p2.x > boxes->limit.p2.x)
105 boxes->limit.p2.x = limits[n].p2.x;
106
107 if (limits[n].p2.y > boxes->limit.p2.y)
108 boxes->limit.p2.y = limits[n].p2.y;
109 }
110 }
111 }
112
113 static void
_cairo_boxes_add_internal(cairo_boxes_t * boxes,const cairo_box_t * box)114 _cairo_boxes_add_internal (cairo_boxes_t *boxes,
115 const cairo_box_t *box)
116 {
117 struct _cairo_boxes_chunk *chunk;
118
119 if (unlikely (boxes->status))
120 return;
121
122 chunk = boxes->tail;
123 if (unlikely (chunk->count == chunk->size)) {
124 int size;
125
126 size = chunk->size * 2;
127 chunk->next = _cairo_malloc_ab_plus_c (size,
128 sizeof (cairo_box_t),
129 sizeof (struct _cairo_boxes_chunk));
130
131 if (unlikely (chunk->next == NULL)) {
132 boxes->status = _cairo_error (CAIRO_STATUS_NO_MEMORY);
133 return;
134 }
135
136 chunk = chunk->next;
137 boxes->tail = chunk;
138
139 chunk->next = NULL;
140 chunk->count = 0;
141 chunk->size = size;
142 chunk->base = (cairo_box_t *) (chunk + 1);
143 }
144
145 chunk->base[chunk->count++] = *box;
146 boxes->num_boxes++;
147
148 if (boxes->is_pixel_aligned) {
149 boxes->is_pixel_aligned =
150 _cairo_fixed_is_integer (box->p1.x) &&
151 _cairo_fixed_is_integer (box->p1.y) &&
152 _cairo_fixed_is_integer (box->p2.x) &&
153 _cairo_fixed_is_integer (box->p2.y);
154 }
155 }
156
157 cairo_status_t
_cairo_boxes_add(cairo_boxes_t * boxes,const cairo_box_t * box)158 _cairo_boxes_add (cairo_boxes_t *boxes,
159 const cairo_box_t *box)
160 {
161 if (box->p1.y == box->p2.y)
162 return CAIRO_STATUS_SUCCESS;
163
164 if (box->p1.x == box->p2.x)
165 return CAIRO_STATUS_SUCCESS;
166
167 if (boxes->num_limits) {
168 cairo_point_t p1, p2;
169 cairo_bool_t reversed = FALSE;
170 int n;
171
172 /* support counter-clockwise winding for rectangular tessellation */
173 if (box->p1.x < box->p2.x) {
174 p1.x = box->p1.x;
175 p2.x = box->p2.x;
176 } else {
177 p2.x = box->p1.x;
178 p1.x = box->p2.x;
179 reversed = ! reversed;
180 }
181
182 if (p1.x >= boxes->limit.p2.x || p2.x <= boxes->limit.p1.x)
183 return CAIRO_STATUS_SUCCESS;
184
185 if (box->p1.y < box->p2.y) {
186 p1.y = box->p1.y;
187 p2.y = box->p2.y;
188 } else {
189 p2.y = box->p1.y;
190 p1.y = box->p2.y;
191 reversed = ! reversed;
192 }
193
194 if (p1.y >= boxes->limit.p2.y || p2.y <= boxes->limit.p1.y)
195 return CAIRO_STATUS_SUCCESS;
196
197 for (n = 0; n < boxes->num_limits; n++) {
198 const cairo_box_t *limits = &boxes->limits[n];
199 cairo_box_t _box;
200 cairo_point_t _p1, _p2;
201
202 if (p1.x >= limits->p2.x || p2.x <= limits->p1.x)
203 continue;
204 if (p1.y >= limits->p2.y || p2.y <= limits->p1.y)
205 continue;
206
207 /* Otherwise, clip the box to the limits. */
208 _p1 = p1;
209 if (_p1.x < limits->p1.x)
210 _p1.x = limits->p1.x;
211 if (_p1.y < limits->p1.y)
212 _p1.y = limits->p1.y;
213
214 _p2 = p2;
215 if (_p2.x > limits->p2.x)
216 _p2.x = limits->p2.x;
217 if (_p2.y > limits->p2.y)
218 _p2.y = limits->p2.y;
219
220 if (_p2.y <= _p1.y || _p2.x <= _p1.x)
221 continue;
222
223 _box.p1.y = _p1.y;
224 _box.p2.y = _p2.y;
225 if (reversed) {
226 _box.p1.x = _p2.x;
227 _box.p2.x = _p1.x;
228 } else {
229 _box.p1.x = _p1.x;
230 _box.p2.x = _p2.x;
231 }
232
233 _cairo_boxes_add_internal (boxes, &_box);
234 }
235 } else {
236 _cairo_boxes_add_internal (boxes, box);
237 }
238
239 return boxes->status;
240 }
241
242 void
_cairo_boxes_extents(const cairo_boxes_t * boxes,cairo_rectangle_int_t * extents)243 _cairo_boxes_extents (const cairo_boxes_t *boxes,
244 cairo_rectangle_int_t *extents)
245 {
246 const struct _cairo_boxes_chunk *chunk;
247 cairo_box_t box;
248 int i;
249
250 box.p1.y = box.p1.x = INT_MAX;
251 box.p2.y = box.p2.x = INT_MIN;
252
253 for (chunk = &boxes->chunks; chunk != NULL; chunk = chunk->next) {
254 const cairo_box_t *b = chunk->base;
255 for (i = 0; i < chunk->count; i++) {
256 if (b[i].p1.x < box.p1.x)
257 box.p1.x = b[i].p1.x;
258
259 if (b[i].p1.y < box.p1.y)
260 box.p1.y = b[i].p1.y;
261
262 if (b[i].p2.x > box.p2.x)
263 box.p2.x = b[i].p2.x;
264
265 if (b[i].p2.y > box.p2.y)
266 box.p2.y = b[i].p2.y;
267 }
268 }
269
270 _cairo_box_round_to_rectangle (&box, extents);
271 }
272
273 void
_cairo_boxes_clear(cairo_boxes_t * boxes)274 _cairo_boxes_clear (cairo_boxes_t *boxes)
275 {
276 struct _cairo_boxes_chunk *chunk, *next;
277
278 for (chunk = boxes->chunks.next; chunk != NULL; chunk = next) {
279 next = chunk->next;
280 free (chunk);
281 }
282
283 boxes->tail = &boxes->chunks;
284 boxes->chunks.next = 0;
285 boxes->chunks.count = 0;
286 boxes->num_boxes = 0;
287
288 boxes->is_pixel_aligned = TRUE;
289 }
290
291 void
_cairo_boxes_fini(cairo_boxes_t * boxes)292 _cairo_boxes_fini (cairo_boxes_t *boxes)
293 {
294 struct _cairo_boxes_chunk *chunk, *next;
295
296 for (chunk = boxes->chunks.next; chunk != NULL; chunk = next) {
297 next = chunk->next;
298 free (chunk);
299 }
300 }
301