source/libs/cairo/cairo-src/src/cairo-boxes.c

   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
  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
  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
  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
  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 void
 106 _cairo_boxes_limit (cairo_boxes_t       *boxes,
 107                     const cairo_box_t   *limits,
 108                     int                  num_limits)
 109 {
 110     int n;
 111
 112     boxes->limits = limits;
 113     boxes->num_limits = num_limits;
 114
 115     if (boxes->num_limits) {
 116         boxes->limit = limits[0];
 117         for (n = 1; n < num_limits; n++) {
 118             if (limits[n].p1.x < boxes->limit.p1.x)
 119                 boxes->limit.p1.x = limits[n].p1.x;
 120
 121             if (limits[n].p1.y < boxes->limit.p1.y)
 122                 boxes->limit.p1.y = limits[n].p1.y;
 123
 124             if (limits[n].p2.x > boxes->limit.p2.x)
 125                 boxes->limit.p2.x = limits[n].p2.x;
 126
 127             if (limits[n].p2.y > boxes->limit.p2.y)
 128                 boxes->limit.p2.y = limits[n].p2.y;
 129         }
 130     }
 131 }
 132
 133 static void
 134 _cairo_boxes_add_internal (cairo_boxes_t *boxes,
 135                            const cairo_box_t *box)
 136 {
 137     struct _cairo_boxes_chunk *chunk;
 138
 139     if (unlikely (boxes->status))
 140         return;
 141
 142     chunk = boxes->tail;
 143     if (unlikely (chunk->count == chunk->size)) {
 144         int size;
 145
 146         size = chunk->size * 2;
 147         chunk->next = _cairo_malloc_ab_plus_c (size,
 148                                                sizeof (cairo_box_t),
 149                                                sizeof (struct _cairo_boxes_chunk));
 150
 151         if (unlikely (chunk->next == NULL)) {
 152             boxes->status = _cairo_error (CAIRO_STATUS_NO_MEMORY);
 153             return;
 154         }
 155
 156         chunk = chunk->next;
 157         boxes->tail = chunk;
 158
 159         chunk->next = NULL;
 160         chunk->count = 0;
 161         chunk->size = size;
 162         chunk->base = (cairo_box_t *) (chunk + 1);
 163     }
 164
 165     chunk->base[chunk->count++] = *box;
 166     boxes->num_boxes++;
 167
 168     if (boxes->is_pixel_aligned)
 169         boxes->is_pixel_aligned = _cairo_box_is_pixel_aligned (box);
 170 }
 171
 172 cairo_status_t
 173 _cairo_boxes_add (cairo_boxes_t *boxes,
 174                   cairo_antialias_t antialias,
 175                   const cairo_box_t *box)
 176 {
 177     cairo_box_t b;
 178
 179     if (antialias == CAIRO_ANTIALIAS_NONE) {
 180         b.p1.x = _cairo_fixed_round_down (box->p1.x);
 181         b.p1.y = _cairo_fixed_round_down (box->p1.y);
 182         b.p2.x = _cairo_fixed_round_down (box->p2.x);
 183         b.p2.y = _cairo_fixed_round_down (box->p2.y);
 184         box = &b;
 185     }
 186
 187     if (box->p1.y == box->p2.y)
 188         return CAIRO_STATUS_SUCCESS;
 189
 190     if (box->p1.x == box->p2.x)
 191         return CAIRO_STATUS_SUCCESS;
 192
 193     if (boxes->num_limits) {
 194         cairo_point_t p1, p2;
 195         cairo_bool_t reversed = FALSE;
 196         int n;
 197
 198         /* support counter-clockwise winding for rectangular tessellation */
 199         if (box->p1.x < box->p2.x) {
 200             p1.x = box->p1.x;
 201             p2.x = box->p2.x;
 202         } else {
 203             p2.x = box->p1.x;
 204             p1.x = box->p2.x;
 205             reversed = ! reversed;
 206         }
 207
 208         if (p1.x >= boxes->limit.p2.x || p2.x <= boxes->limit.p1.x)
 209             return CAIRO_STATUS_SUCCESS;
 210
 211         if (box->p1.y < box->p2.y) {
 212             p1.y = box->p1.y;
 213             p2.y = box->p2.y;
 214         } else {
 215             p2.y = box->p1.y;
 216             p1.y = box->p2.y;
 217             reversed = ! reversed;
 218         }
 219
 220         if (p1.y >= boxes->limit.p2.y || p2.y <= boxes->limit.p1.y)
 221             return CAIRO_STATUS_SUCCESS;
 222
 223         for (n = 0; n < boxes->num_limits; n++) {
 224             const cairo_box_t *limits = &boxes->limits[n];
 225             cairo_box_t _box;
 226             cairo_point_t _p1, _p2;
 227
 228             if (p1.x >= limits->p2.x || p2.x <= limits->p1.x)
 229                 continue;
 230             if (p1.y >= limits->p2.y || p2.y <= limits->p1.y)
 231                 continue;
 232
 233             /* Otherwise, clip the box to the limits. */
 234             _p1 = p1;
 235             if (_p1.x < limits->p1.x)
 236                 _p1.x = limits->p1.x;
 237             if (_p1.y < limits->p1.y)
 238                 _p1.y = limits->p1.y;
 239
 240             _p2 = p2;
 241             if (_p2.x > limits->p2.x)
 242                 _p2.x = limits->p2.x;
 243             if (_p2.y > limits->p2.y)
 244                 _p2.y = limits->p2.y;
 245
 246             if (_p2.y <= _p1.y || _p2.x <= _p1.x)
 247                 continue;
 248
 249             _box.p1.y = _p1.y;
 250             _box.p2.y = _p2.y;
 251             if (reversed) {
 252                 _box.p1.x = _p2.x;
 253                 _box.p2.x = _p1.x;
 254             } else {
 255                 _box.p1.x = _p1.x;
 256                 _box.p2.x = _p2.x;
 257             }
 258
 259             _cairo_boxes_add_internal (boxes, &_box);
 260         }
 261     } else {
 262         _cairo_boxes_add_internal (boxes, box);
 263     }
 264
 265     return boxes->status;
 266 }
 267
 268 void
 269 _cairo_boxes_extents (const cairo_boxes_t *boxes,
 270                       cairo_box_t *box)
 271 {
 272     const struct _cairo_boxes_chunk *chunk;
 273     cairo_box_t b;
 274     int i;
 275
 276     if (boxes->num_boxes == 0) {
 277         box->p1.x = box->p1.y = box->p2.x = box->p2.y = 0;
 278         return;
 279     }
 280
 281     b = boxes->chunks.base[0];
 282     for (chunk = &boxes->chunks; chunk != NULL; chunk = chunk->next) {
 283         for (i = 0; i < chunk->count; i++) {
 284             if (chunk->base[i].p1.x < b.p1.x)
 285                 b.p1.x = chunk->base[i].p1.x;
 286
 287             if (chunk->base[i].p1.y < b.p1.y)
 288                 b.p1.y = chunk->base[i].p1.y;
 289
 290             if (chunk->base[i].p2.x > b.p2.x)
 291                 b.p2.x = chunk->base[i].p2.x;
 292
 293             if (chunk->base[i].p2.y > b.p2.y)
 294                 b.p2.y = chunk->base[i].p2.y;
 295         }
 296     }
 297     *box = b;
 298 }
 299
 300 void
 301 _cairo_boxes_clear (cairo_boxes_t *boxes)
 302 {
 303     struct _cairo_boxes_chunk *chunk, *next;
 304
 305     for (chunk = boxes->chunks.next; chunk != NULL; chunk = next) {
 306         next = chunk->next;
 307         free (chunk);
 308     }
 309
 310     boxes->tail = &boxes->chunks;
 311     boxes->chunks.next = 0;
 312     boxes->chunks.count = 0;
 313     boxes->chunks.base = boxes->boxes_embedded;
 314     boxes->chunks.size = ARRAY_LENGTH (boxes->boxes_embedded);
 315     boxes->num_boxes = 0;
 316
 317     boxes->is_pixel_aligned = TRUE;
 318 }
 319
 320 cairo_box_t *
 321 _cairo_boxes_to_array (const cairo_boxes_t *boxes,
 322                        int *num_boxes,
 323                        cairo_bool_t force_allocation)
 324 {
 325     const struct _cairo_boxes_chunk *chunk;
 326     cairo_box_t *box;
 327     int i, j;
 328
 329     *num_boxes = boxes->num_boxes;
 330     if (boxes->chunks.next == NULL && ! force_allocation)
 331             return boxes->chunks.base;
 332
 333     box = _cairo_malloc_ab (boxes->num_boxes, sizeof (cairo_box_t));
 334     if (box == NULL) {
 335         _cairo_error_throw (CAIRO_STATUS_NO_MEMORY);
 336         return NULL;
 337     }
 338
 339     j = 0;
 340     for (chunk = &boxes->chunks; chunk != NULL; chunk = chunk->next) {
 341         for (i = 0; i < chunk->count; i++)
 342             box[j++] = chunk->base[i];
 343     }
 344
 345     return box;
 346 }
 347
 348 void
 349 _cairo_boxes_fini (cairo_boxes_t *boxes)
 350 {
 351     struct _cairo_boxes_chunk *chunk, *next;
 352
 353     for (chunk = boxes->chunks.next; chunk != NULL; chunk = next) {
 354         next = chunk->next;
 355         free (chunk);
 356     }
 357 }
 358
 359 cairo_bool_t
 360 _cairo_boxes_for_each_box (cairo_boxes_t *boxes,
 361                            cairo_bool_t (*func) (cairo_box_t *box, void *data),
 362                            void *data)
 363 {
 364     struct _cairo_boxes_chunk *chunk;
 365     int i;
 366
 367     for (chunk = &boxes->chunks; chunk != NULL; chunk = chunk->next) {
 368         for (i = 0; i < chunk->count; i++)
 369             if (! func (&chunk->base[i], data))
 370                 return FALSE;
 371     }
 372
 373     return TRUE;
 374 }
 375
 376 struct cairo_box_renderer {
 377     cairo_span_renderer_t base;
 378     cairo_boxes_t *boxes;
 379 };
 380
 381 static cairo_status_t
 382 span_to_boxes (void *abstract_renderer, int y, int h,
 383                const cairo_half_open_span_t *spans, unsigned num_spans)
 384 {
 385     struct cairo_box_renderer *r = abstract_renderer;
 386     cairo_status_t status = CAIRO_STATUS_SUCCESS;
 387     cairo_box_t box;
 388
 389     if (num_spans == 0)
 390         return CAIRO_STATUS_SUCCESS;
 391
 392     box.p1.y = _cairo_fixed_from_int (y);
 393     box.p2.y = _cairo_fixed_from_int (y + h);
 394     do {
 395         if (spans[0].coverage) {
 396             box.p1.x = _cairo_fixed_from_int(spans[0].x);
 397             box.p2.x = _cairo_fixed_from_int(spans[1].x);
 398             status = _cairo_boxes_add (r->boxes, CAIRO_ANTIALIAS_DEFAULT, &box);
 399         }
 400         spans++;
 401     } while (--num_spans > 1 && status == CAIRO_STATUS_SUCCESS);
 402
 403     return status;
 404 }
 405
 406 cairo_status_t
 407 _cairo_rasterise_polygon_to_boxes (cairo_polygon_t                      *polygon,
 408                                    cairo_fill_rule_t                     fill_rule,
 409                                    cairo_boxes_t *boxes)
 410 {
 411     struct cairo_box_renderer renderer;
 412     cairo_scan_converter_t *converter;
 413     cairo_int_status_t status;
 414     cairo_rectangle_int_t r;
 415
 416     TRACE ((stderr, "%s: fill_rule=%d\n", __FUNCTION__, fill_rule));
 417
 418     _cairo_box_round_to_rectangle (&polygon->extents, &r);
 419     converter = _cairo_mono_scan_converter_create (r.x, r.y,
 420                                                    r.x + r.width,
 421                                                    r.y + r.height,
 422                                                    fill_rule);
 423     status = _cairo_mono_scan_converter_add_polygon (converter, polygon);
 424     if (unlikely (status))
 425         goto cleanup_converter;
 426
 427     renderer.boxes = boxes;
 428     renderer.base.render_rows = span_to_boxes;
 429
 430     status = converter->generate (converter, &renderer.base);
 431 cleanup_converter:
 432     converter->destroy (converter);
 433     return status;
 434 }
 435
 436 void
 437 _cairo_debug_print_boxes (FILE *stream, const cairo_boxes_t *boxes)
 438 {
 439     const struct _cairo_boxes_chunk *chunk;
 440     cairo_box_t extents;
 441     int i;
 442
 443     _cairo_boxes_extents (boxes, &extents);
 444     fprintf (stream, "boxes x %d: (%f, %f) x (%f, %f)\n",
 445              boxes->num_boxes,
 446              _cairo_fixed_to_double (extents.p1.x),
 447              _cairo_fixed_to_double (extents.p1.y),
 448              _cairo_fixed_to_double (extents.p2.x),
 449              _cairo_fixed_to_double (extents.p2.y));
 450
 451     for (chunk = &boxes->chunks; chunk != NULL; chunk = chunk->next) {
 452         for (i = 0; i < chunk->count; i++) {
 453             fprintf (stderr, "  box[%d]: (%f, %f), (%f, %f)\n", i,
 454                      _cairo_fixed_to_double (chunk->base[i].p1.x),
 455                      _cairo_fixed_to_double (chunk->base[i].p1.y),
 456                      _cairo_fixed_to_double (chunk->base[i].p2.x),
 457                      _cairo_fixed_to_double (chunk->base[i].p2.y));
 458         }
 459     }
 460 }