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-box-inline.h"
37 #include "cairo-boxes-private.h"
38 #include "cairo-error-private.h"
39
40 void
_cairo_boxes_init(cairo_boxes_t * boxes)41 _cairo_boxes_init (cairo_boxes_t *boxes)
42 {
43 boxes->status = CAIRO_STATUS_SUCCESS;
44 boxes->num_limits = 0;
45 boxes->num_boxes = 0;
46
47 boxes->tail = &boxes->chunks;
48 boxes->chunks.next = NULL;
49 boxes->chunks.base = boxes->boxes_embedded;
50 boxes->chunks.size = ARRAY_LENGTH (boxes->boxes_embedded);
51 boxes->chunks.count = 0;
52
53 boxes->is_pixel_aligned = TRUE;
54 }
55
56 void
_cairo_boxes_init_from_rectangle(cairo_boxes_t * boxes,int x,int y,int w,int h)57 _cairo_boxes_init_from_rectangle (cairo_boxes_t *boxes,
58 int x, int y, int w, int h)
59 {
60 _cairo_boxes_init (boxes);
61
62 _cairo_box_from_integers (&boxes->chunks.base[0], x, y, w, h);
63 boxes->num_boxes = 1;
64 }
65
66 void
_cairo_boxes_init_with_clip(cairo_boxes_t * boxes,cairo_clip_t * clip)67 _cairo_boxes_init_with_clip (cairo_boxes_t *boxes,
68 cairo_clip_t *clip)
69 {
70 _cairo_boxes_init (boxes);
71 if (clip)
72 _cairo_boxes_limit (boxes, clip->boxes, clip->num_boxes);
73 }
74
75 void
_cairo_boxes_init_for_array(cairo_boxes_t * boxes,cairo_box_t * array,int num_boxes)76 _cairo_boxes_init_for_array (cairo_boxes_t *boxes,
77 cairo_box_t *array,
78 int num_boxes)
79 {
80 int n;
81
82 boxes->status = CAIRO_STATUS_SUCCESS;
83 boxes->num_limits = 0;
84 boxes->num_boxes = num_boxes;
85
86 boxes->tail = &boxes->chunks;
87 boxes->chunks.next = NULL;
88 boxes->chunks.base = array;
89 boxes->chunks.size = num_boxes;
90 boxes->chunks.count = num_boxes;
91
92 for (n = 0; n < num_boxes; n++) {
93 if (! _cairo_fixed_is_integer (array[n].p1.x) ||
94 ! _cairo_fixed_is_integer (array[n].p1.y) ||
95 ! _cairo_fixed_is_integer (array[n].p2.x) ||
96 ! _cairo_fixed_is_integer (array[n].p2.y))
97 {
98 break;
99 }
100 }
101
102 boxes->is_pixel_aligned = n == num_boxes;
103 }
104
105 /** _cairo_boxes_limit:
106 *
107 * Computes the minimum bounding box of the given list of boxes and assign
108 * it to the given boxes set. It also assigns that list as the list of
109 * limiting boxes in the box set.
110 *
111 * @param boxes the box set to be filled (return buffer)
112 * @param limits array of the limiting boxes to compute the bounding
113 * box from
114 * @param num_limits length of the limits array
115 */
116 void
_cairo_boxes_limit(cairo_boxes_t * boxes,const cairo_box_t * limits,int num_limits)117 _cairo_boxes_limit (cairo_boxes_t *boxes,
118 const cairo_box_t *limits,
119 int num_limits)
120 {
121 int n;
122
123 boxes->limits = limits;
124 boxes->num_limits = num_limits;
125
126 if (boxes->num_limits) {
127 boxes->limit = limits[0];
128 for (n = 1; n < num_limits; n++) {
129 if (limits[n].p1.x < boxes->limit.p1.x)
130 boxes->limit.p1.x = limits[n].p1.x;
131
132 if (limits[n].p1.y < boxes->limit.p1.y)
133 boxes->limit.p1.y = limits[n].p1.y;
134
135 if (limits[n].p2.x > boxes->limit.p2.x)
136 boxes->limit.p2.x = limits[n].p2.x;
137
138 if (limits[n].p2.y > boxes->limit.p2.y)
139 boxes->limit.p2.y = limits[n].p2.y;
140 }
141 }
142 }
143
144 static void
_cairo_boxes_add_internal(cairo_boxes_t * boxes,const cairo_box_t * box)145 _cairo_boxes_add_internal (cairo_boxes_t *boxes,
146 const cairo_box_t *box)
147 {
148 struct _cairo_boxes_chunk *chunk;
149
150 if (unlikely (boxes->status))
151 return;
152
153 chunk = boxes->tail;
154 if (unlikely (chunk->count == chunk->size)) {
155 int size;
156
157 size = chunk->size * 2;
158 chunk->next = _cairo_malloc_ab_plus_c (size,
159 sizeof (cairo_box_t),
160 sizeof (struct _cairo_boxes_chunk));
161
162 if (unlikely (chunk->next == NULL)) {
163 boxes->status = _cairo_error (CAIRO_STATUS_NO_MEMORY);
164 return;
165 }
166
167 chunk = chunk->next;
168 boxes->tail = chunk;
169
170 chunk->next = NULL;
171 chunk->count = 0;
172 chunk->size = size;
173 chunk->base = (cairo_box_t *) (chunk + 1);
174 }
175
176 chunk->base[chunk->count++] = *box;
177 boxes->num_boxes++;
178
179 if (boxes->is_pixel_aligned)
180 boxes->is_pixel_aligned = _cairo_box_is_pixel_aligned (box);
181 }
182
183 cairo_status_t
_cairo_boxes_add(cairo_boxes_t * boxes,cairo_antialias_t antialias,const cairo_box_t * box)184 _cairo_boxes_add (cairo_boxes_t *boxes,
185 cairo_antialias_t antialias,
186 const cairo_box_t *box)
187 {
188 cairo_box_t b;
189
190 if (antialias == CAIRO_ANTIALIAS_NONE) {
191 b.p1.x = _cairo_fixed_round_down (box->p1.x);
192 b.p1.y = _cairo_fixed_round_down (box->p1.y);
193 b.p2.x = _cairo_fixed_round_down (box->p2.x);
194 b.p2.y = _cairo_fixed_round_down (box->p2.y);
195 box = &b;
196 }
197
198 if (box->p1.y == box->p2.y)
199 return CAIRO_STATUS_SUCCESS;
200
201 if (box->p1.x == box->p2.x)
202 return CAIRO_STATUS_SUCCESS;
203
204 if (boxes->num_limits) {
205 cairo_point_t p1, p2;
206 cairo_bool_t reversed = FALSE;
207 int n;
208
209 /* support counter-clockwise winding for rectangular tessellation */
210 if (box->p1.x < box->p2.x) {
211 p1.x = box->p1.x;
212 p2.x = box->p2.x;
213 } else {
214 p2.x = box->p1.x;
215 p1.x = box->p2.x;
216 reversed = ! reversed;
217 }
218
219 if (p1.x >= boxes->limit.p2.x || p2.x <= boxes->limit.p1.x)
220 return CAIRO_STATUS_SUCCESS;
221
222 if (box->p1.y < box->p2.y) {
223 p1.y = box->p1.y;
224 p2.y = box->p2.y;
225 } else {
226 p2.y = box->p1.y;
227 p1.y = box->p2.y;
228 reversed = ! reversed;
229 }
230
231 if (p1.y >= boxes->limit.p2.y || p2.y <= boxes->limit.p1.y)
232 return CAIRO_STATUS_SUCCESS;
233
234 for (n = 0; n < boxes->num_limits; n++) {
235 const cairo_box_t *limits = &boxes->limits[n];
236 cairo_box_t _box;
237 cairo_point_t _p1, _p2;
238
239 if (p1.x >= limits->p2.x || p2.x <= limits->p1.x)
240 continue;
241 if (p1.y >= limits->p2.y || p2.y <= limits->p1.y)
242 continue;
243
244 /* Otherwise, clip the box to the limits. */
245 _p1 = p1;
246 if (_p1.x < limits->p1.x)
247 _p1.x = limits->p1.x;
248 if (_p1.y < limits->p1.y)
249 _p1.y = limits->p1.y;
250
251 _p2 = p2;
252 if (_p2.x > limits->p2.x)
253 _p2.x = limits->p2.x;
254 if (_p2.y > limits->p2.y)
255 _p2.y = limits->p2.y;
256
257 if (_p2.y <= _p1.y || _p2.x <= _p1.x)
258 continue;
259
260 _box.p1.y = _p1.y;
261 _box.p2.y = _p2.y;
262 if (reversed) {
263 _box.p1.x = _p2.x;
264 _box.p2.x = _p1.x;
265 } else {
266 _box.p1.x = _p1.x;
267 _box.p2.x = _p2.x;
268 }
269
270 _cairo_boxes_add_internal (boxes, &_box);
271 }
272 } else {
273 _cairo_boxes_add_internal (boxes, box);
274 }
275
276 return boxes->status;
277 }
278
279 /** _cairo_boxes_extents:
280 *
281 * Computes the minimum bounding box of the given box set and stores
282 * it in the given box.
283 *
284 * @param boxes The box set whose minimum bounding is computed.
285 * @param box Return buffer for the computed result.
286 */
287 void
_cairo_boxes_extents(const cairo_boxes_t * boxes,cairo_box_t * box)288 _cairo_boxes_extents (const cairo_boxes_t *boxes,
289 cairo_box_t *box)
290 {
291 const struct _cairo_boxes_chunk *chunk;
292 cairo_box_t b;
293 int i;
294
295 if (boxes->num_boxes == 0) {
296 box->p1.x = box->p1.y = box->p2.x = box->p2.y = 0;
297 return;
298 }
299
300 b = boxes->chunks.base[0];
301 for (chunk = &boxes->chunks; chunk != NULL; chunk = chunk->next) {
302 for (i = 0; i < chunk->count; i++) {
303 if (chunk->base[i].p1.x < b.p1.x)
304 b.p1.x = chunk->base[i].p1.x;
305
306 if (chunk->base[i].p1.y < b.p1.y)
307 b.p1.y = chunk->base[i].p1.y;
308
309 if (chunk->base[i].p2.x > b.p2.x)
310 b.p2.x = chunk->base[i].p2.x;
311
312 if (chunk->base[i].p2.y > b.p2.y)
313 b.p2.y = chunk->base[i].p2.y;
314 }
315 }
316 *box = b;
317 }
318
319 void
_cairo_boxes_clear(cairo_boxes_t * boxes)320 _cairo_boxes_clear (cairo_boxes_t *boxes)
321 {
322 struct _cairo_boxes_chunk *chunk, *next;
323
324 for (chunk = boxes->chunks.next; chunk != NULL; chunk = next) {
325 next = chunk->next;
326 free (chunk);
327 }
328
329 boxes->tail = &boxes->chunks;
330 boxes->chunks.next = 0;
331 boxes->chunks.count = 0;
332 boxes->chunks.base = boxes->boxes_embedded;
333 boxes->chunks.size = ARRAY_LENGTH (boxes->boxes_embedded);
334 boxes->num_boxes = 0;
335
336 boxes->is_pixel_aligned = TRUE;
337 }
338
339 /** _cairo_boxes_to_array:
340 *
341 * Linearize a box set of possibly multiple chunks into one big chunk
342 * and returns an array of boxes
343 *
344 * @param boxes The box set to be converted.
345 * @param num_boxes Return buffer for the number of boxes (array count).
346 * @return Pointer to the newly allocated array of boxes
347 * (the number o elements is given in num_boxes).
348 */
349 cairo_box_t *
_cairo_boxes_to_array(const cairo_boxes_t * boxes,int * num_boxes)350 _cairo_boxes_to_array (const cairo_boxes_t *boxes,
351 int *num_boxes)
352 {
353 const struct _cairo_boxes_chunk *chunk;
354 cairo_box_t *box;
355 int i, j;
356
357 *num_boxes = boxes->num_boxes;
358
359 box = _cairo_malloc_ab (boxes->num_boxes, sizeof (cairo_box_t));
360 if (box == NULL) {
361 _cairo_error_throw (CAIRO_STATUS_NO_MEMORY);
362 return NULL;
363 }
364
365 j = 0;
366 for (chunk = &boxes->chunks; chunk != NULL; chunk = chunk->next) {
367 for (i = 0; i < chunk->count; i++)
368 box[j++] = chunk->base[i];
369 }
370
371 return box;
372 }
373
374 void
_cairo_boxes_fini(cairo_boxes_t * boxes)375 _cairo_boxes_fini (cairo_boxes_t *boxes)
376 {
377 struct _cairo_boxes_chunk *chunk, *next;
378
379 for (chunk = boxes->chunks.next; chunk != NULL; chunk = next) {
380 next = chunk->next;
381 free (chunk);
382 }
383 }
384
385 cairo_bool_t
_cairo_boxes_for_each_box(cairo_boxes_t * boxes,cairo_bool_t (* func)(cairo_box_t * box,void * data),void * data)386 _cairo_boxes_for_each_box (cairo_boxes_t *boxes,
387 cairo_bool_t (*func) (cairo_box_t *box, void *data),
388 void *data)
389 {
390 struct _cairo_boxes_chunk *chunk;
391 int i;
392
393 for (chunk = &boxes->chunks; chunk != NULL; chunk = chunk->next) {
394 for (i = 0; i < chunk->count; i++)
395 if (! func (&chunk->base[i], data))
396 return FALSE;
397 }
398
399 return TRUE;
400 }
401
402 struct cairo_box_renderer {
403 cairo_span_renderer_t base;
404 cairo_boxes_t *boxes;
405 };
406
407 static cairo_status_t
span_to_boxes(void * abstract_renderer,int y,int h,const cairo_half_open_span_t * spans,unsigned num_spans)408 span_to_boxes (void *abstract_renderer, int y, int h,
409 const cairo_half_open_span_t *spans, unsigned num_spans)
410 {
411 struct cairo_box_renderer *r = abstract_renderer;
412 cairo_status_t status = CAIRO_STATUS_SUCCESS;
413 cairo_box_t box;
414
415 if (num_spans == 0)
416 return CAIRO_STATUS_SUCCESS;
417
418 box.p1.y = _cairo_fixed_from_int (y);
419 box.p2.y = _cairo_fixed_from_int (y + h);
420 do {
421 if (spans[0].coverage) {
422 box.p1.x = _cairo_fixed_from_int(spans[0].x);
423 box.p2.x = _cairo_fixed_from_int(spans[1].x);
424 status = _cairo_boxes_add (r->boxes, CAIRO_ANTIALIAS_DEFAULT, &box);
425 }
426 spans++;
427 } while (--num_spans > 1 && status == CAIRO_STATUS_SUCCESS);
428
429 return status;
430 }
431
432 cairo_status_t
_cairo_rasterise_polygon_to_boxes(cairo_polygon_t * polygon,cairo_fill_rule_t fill_rule,cairo_boxes_t * boxes)433 _cairo_rasterise_polygon_to_boxes (cairo_polygon_t *polygon,
434 cairo_fill_rule_t fill_rule,
435 cairo_boxes_t *boxes)
436 {
437 struct cairo_box_renderer renderer;
438 cairo_scan_converter_t *converter;
439 cairo_int_status_t status;
440 cairo_rectangle_int_t r;
441
442 TRACE ((stderr, "%s: fill_rule=%d\n", __FUNCTION__, fill_rule));
443
444 _cairo_box_round_to_rectangle (&polygon->extents, &r);
445 converter = _cairo_mono_scan_converter_create (r.x, r.y,
446 r.x + r.width,
447 r.y + r.height,
448 fill_rule);
449 status = _cairo_mono_scan_converter_add_polygon (converter, polygon);
450 if (unlikely (status))
451 goto cleanup_converter;
452
453 renderer.boxes = boxes;
454 renderer.base.render_rows = span_to_boxes;
455
456 status = converter->generate (converter, &renderer.base);
457 cleanup_converter:
458 converter->destroy (converter);
459 return status;
460 }
461
462 void
_cairo_debug_print_boxes(FILE * stream,const cairo_boxes_t * boxes)463 _cairo_debug_print_boxes (FILE *stream, const cairo_boxes_t *boxes)
464 {
465 const struct _cairo_boxes_chunk *chunk;
466 cairo_box_t extents;
467 int i;
468
469 _cairo_boxes_extents (boxes, &extents);
470 fprintf (stream, "boxes x %d: (%f, %f) x (%f, %f)\n",
471 boxes->num_boxes,
472 _cairo_fixed_to_double (extents.p1.x),
473 _cairo_fixed_to_double (extents.p1.y),
474 _cairo_fixed_to_double (extents.p2.x),
475 _cairo_fixed_to_double (extents.p2.y));
476
477 for (chunk = &boxes->chunks; chunk != NULL; chunk = chunk->next) {
478 for (i = 0; i < chunk->count; i++) {
479 fprintf (stderr, " box[%d]: (%f, %f), (%f, %f)\n", i,
480 _cairo_fixed_to_double (chunk->base[i].p1.x),
481 _cairo_fixed_to_double (chunk->base[i].p1.y),
482 _cairo_fixed_to_double (chunk->base[i].p2.x),
483 _cairo_fixed_to_double (chunk->base[i].p2.y));
484 }
485 }
486 }
487