src/cairo-contour.c

   1 /*
   2  * Copyright © 2004 Carl Worth
   3  * Copyright © 2006 Red Hat, Inc.
   4  * Copyright © 2008 Chris Wilson
   5  * Copyright © 2011 Intel Corporation
   6  *
   7  * This library is free software; you can redistribute it and/or
   8  * modify it either under the terms of the GNU Lesser General Public
   9  * License version 2.1 as published by the Free Software Foundation
  10  * (the "LGPL") or, at your option, under the terms of the Mozilla
  11  * Public License Version 1.1 (the "MPL"). If you do not alter this
  12  * notice, a recipient may use your version of this file under either
  13  * the MPL or the LGPL.
  14  *
  15  * You should have received a copy of the LGPL along with this library
  16  * in the file COPYING-LGPL-2.1; if not, write to the Free Software
  17  * Foundation, Inc., 51 Franklin Street, Suite 500, Boston, MA 02110-1335, USA
  18  * You should have received a copy of the MPL along with this library
  19  * in the file COPYING-MPL-1.1
  20  *
  21  * The contents of this file are subject to the Mozilla Public License
  22  * Version 1.1 (the "License"); you may not use this file except in
  23  * compliance with the License. You may obtain a copy of the License at
  24  * http://www.mozilla.org/MPL/
  25  *
  26  * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
  27  * OF ANY KIND, either express or implied. See the LGPL or the MPL for
  28  * the specific language governing rights and limitations.
  29  *
  30  * The Original Code is the cairo graphics library.
  31  *
  32  * The Initial Developer of the Original Code is Carl Worth
  33  *
  34  * Contributor(s):
  35  *      Carl D. Worth <cworth@cworth.org>
  36  *      Chris Wilson <chris@chris-wilson.co.uk>
  37  */
  38
  39 #include "cairoint.h"
  40
  41 #include "cairo-error-private.h"
  42 #include "cairo-freelist-private.h"
  43 #include "cairo-combsort-private.h"
  44 #include "cairo-contour-private.h"
  45
  46 void
  47 _cairo_contour_init (cairo_contour_t *contour,
  48                      int direction)
  49 {
  50     contour->direction = direction;
  51     contour->chain.points = contour->embedded_points;
  52     contour->chain.next = NULL;
  53     contour->chain.num_points = 0;
  54     contour->chain.size_points = ARRAY_LENGTH (contour->embedded_points);
  55     contour->tail = &contour->chain;
  56 }
  57
  58 cairo_int_status_t
  59 __cairo_contour_add_point (cairo_contour_t *contour,
  60                           const cairo_point_t *point)
  61 {
  62     cairo_contour_chain_t *tail = contour->tail;
  63     cairo_contour_chain_t *next;
  64
  65     assert (tail->next == NULL);
  66
  67     next = _cairo_malloc_ab_plus_c (tail->size_points*2,
  68                                     sizeof (cairo_point_t),
  69                                     sizeof (cairo_contour_chain_t));
  70     if (unlikely (next == NULL))
  71         return _cairo_error (CAIRO_STATUS_NO_MEMORY);
  72
  73     next->size_points = tail->size_points*2;
  74     next->num_points = 1;
  75     next->points = (cairo_point_t *)(next+1);
  76     next->next = NULL;
  77     tail->next = next;
  78     contour->tail = next;
  79
  80     next->points[0] = *point;
  81     return CAIRO_INT_STATUS_SUCCESS;
  82 }
  83
  84 static void
  85 first_inc (cairo_contour_t *contour,
  86            cairo_point_t **p,
  87            cairo_contour_chain_t **chain)
  88 {
  89     if (*p == (*chain)->points + (*chain)->num_points) {
  90         assert ((*chain)->next);
  91         *chain = (*chain)->next;
  92         *p = &(*chain)->points[0];
  93     } else
  94         ++*p;
  95 }
  96
  97 static void
  98 last_dec (cairo_contour_t *contour,
  99           cairo_point_t **p,
 100           cairo_contour_chain_t **chain)
 101 {
 102     if (*p == (*chain)->points) {
 103         cairo_contour_chain_t *prev;
 104         assert (*chain != &contour->chain);
 105         for (prev = &contour->chain; prev->next != *chain; prev = prev->next)
 106             ;
 107         *chain = prev;
 108         *p = &(*chain)->points[(*chain)->num_points-1];
 109     } else
 110         --*p;
 111 }
 112
 113 void
 114 _cairo_contour_reverse (cairo_contour_t *contour)
 115 {
 116     cairo_contour_chain_t *first_chain, *last_chain;
 117     cairo_point_t *first, *last;
 118
 119     contour->direction = -contour->direction;
 120
 121     if (contour->chain.num_points <= 1)
 122         return;
 123
 124     first_chain = &contour->chain;
 125     last_chain = contour->tail;
 126
 127     first = &first_chain->points[0];
 128     last = &last_chain->points[last_chain->num_points-1];
 129
 130     while (first != last) {
 131         cairo_point_t p;
 132
 133         p = *first;
 134         *first = *last;
 135         *last = p;
 136
 137         first_inc (contour, &first, &first_chain);
 138         last_dec (contour, &last, &last_chain);
 139     }
 140 }
 141
 142 cairo_int_status_t
 143 _cairo_contour_add (cairo_contour_t *dst,
 144                     const cairo_contour_t *src)
 145 {
 146     const cairo_contour_chain_t *chain;
 147     cairo_int_status_t status;
 148     int i;
 149
 150     for (chain = &src->chain; chain; chain = chain->next) {
 151         for (i = 0; i < chain->num_points; i++) {
 152             status = _cairo_contour_add_point (dst, &chain->points[i]);
 153             if (unlikely (status))
 154                 return status;
 155         }
 156     }
 157
 158     return CAIRO_INT_STATUS_SUCCESS;
 159 }
 160
 161 static inline cairo_bool_t
 162 iter_next (cairo_contour_iter_t *iter)
 163 {
 164     if (iter->point == &iter->chain->points[iter->chain->size_points-1]) {
 165         iter->chain = iter->chain->next;
 166         if (iter->chain == NULL)
 167             return FALSE;
 168
 169         iter->point = &iter->chain->points[0];
 170         return TRUE;
 171     } else {
 172         iter->point++;
 173         return TRUE;
 174     }
 175 }
 176
 177 static cairo_bool_t
 178 iter_equal (const cairo_contour_iter_t *i1,
 179             const cairo_contour_iter_t *i2)
 180 {
 181     return i1->chain == i2->chain && i1->point == i2->point;
 182 }
 183
 184 static void
 185 iter_init (cairo_contour_iter_t *iter, cairo_contour_t *contour)
 186 {
 187     iter->chain = &contour->chain;
 188     iter->point = &contour->chain.points[0];
 189 }
 190
 191 static void
 192 iter_init_last (cairo_contour_iter_t *iter, cairo_contour_t *contour)
 193 {
 194     iter->chain = contour->tail;
 195     iter->point = &contour->tail->points[contour->tail->num_points-1];
 196 }
 197
 198 static const cairo_contour_chain_t *prev_const_chain(const cairo_contour_t *contour,
 199                                                      const cairo_contour_chain_t *chain)
 200 {
 201     const cairo_contour_chain_t *prev;
 202
 203     if (chain == &contour->chain)
 204         return NULL;
 205
 206     for (prev = &contour->chain; prev->next != chain; prev = prev->next)
 207         ;
 208
 209     return prev;
 210 }
 211
 212 cairo_int_status_t
 213 _cairo_contour_add_reversed (cairo_contour_t *dst,
 214                              const cairo_contour_t *src)
 215 {
 216     const cairo_contour_chain_t *last;
 217     cairo_int_status_t status;
 218     int i;
 219
 220     if (src->chain.num_points == 0)
 221         return CAIRO_INT_STATUS_SUCCESS;
 222
 223     for (last = src->tail; last; last = prev_const_chain (src, last)) {
 224         for (i = last->num_points-1; i >= 0; i--) {
 225             status = _cairo_contour_add_point (dst, &last->points[i]);
 226             if (unlikely (status))
 227                 return status;
 228         }
 229     }
 230
 231     return CAIRO_INT_STATUS_SUCCESS;
 232 }
 233
 234 static cairo_uint64_t
 235 point_distance_sq (const cairo_point_t *p1,
 236                    const cairo_point_t *p2)
 237 {
 238     int32_t dx = p1->x - p2->x;
 239     int32_t dy = p1->y - p2->y;
 240     return _cairo_int32x32_64_mul (dx, dx) + _cairo_int32x32_64_mul (dy, dy);
 241 }
 242
 243 #define DELETED(p) ((p)->x == INT_MIN && (p)->y == INT_MAX)
 244 #define MARK_DELETED(p) ((p)->x = INT_MIN, (p)->y = INT_MAX)
 245
 246 static cairo_bool_t
 247 _cairo_contour_simplify_chain (cairo_contour_t *contour, const double tolerance,
 248                                const cairo_contour_iter_t *first,
 249                                const cairo_contour_iter_t *last)
 250 {
 251     cairo_contour_iter_t iter, furthest;
 252     uint64_t max_error;
 253     int x0, y0;
 254     int nx, ny;
 255     int count;
 256
 257     iter = *first;
 258     iter_next (&iter);
 259     if (iter_equal (&iter, last))
 260         return FALSE;
 261
 262     x0 = first->point->x;
 263     y0 = first->point->y;
 264     nx = last->point->y - y0;
 265     ny = x0 - last->point->x;
 266
 267     count = 0;
 268     max_error = 0;
 269     do {
 270         cairo_point_t *p = iter.point;
 271         if (! DELETED(p)) {
 272             uint64_t d = (uint64_t)nx * (x0 - p->x) + (uint64_t)ny * (y0 - p->y);
 273             if (d * d > max_error) {
 274                 max_error = d * d;
 275                 furthest = iter;
 276             }
 277             count++;
 278         }
 279         iter_next (&iter);
 280     } while (! iter_equal (&iter, last));
 281     if (count == 0)
 282         return FALSE;
 283
 284     if (max_error > tolerance * ((uint64_t)nx * nx + (uint64_t)ny * ny)) {
 285         cairo_bool_t simplified;
 286
 287         simplified = FALSE;
 288         simplified |= _cairo_contour_simplify_chain (contour, tolerance,
 289                                                      first, &furthest);
 290         simplified |= _cairo_contour_simplify_chain (contour, tolerance,
 291                                                      &furthest, last);
 292         return simplified;
 293     } else {
 294         iter = *first;
 295         iter_next (&iter);
 296         do {
 297             MARK_DELETED (iter.point);
 298             iter_next (&iter);
 299         } while (! iter_equal (&iter, last));
 300
 301         return TRUE;
 302     }
 303 }
 304
 305 void
 306 _cairo_contour_simplify (cairo_contour_t *contour, double tolerance)
 307 {
 308     cairo_contour_chain_t *chain;
 309     cairo_point_t *last = NULL;
 310     cairo_contour_iter_t iter, furthest;
 311     cairo_bool_t simplified;
 312     uint64_t max = 0;
 313     int i;
 314
 315     if (contour->chain.num_points <= 2)
 316         return;
 317
 318     tolerance = tolerance * CAIRO_FIXED_ONE;
 319     tolerance *= tolerance;
 320
 321     /* stage 1: vertex reduction */
 322     for (chain = &contour->chain; chain; chain = chain->next) {
 323         for (i = 0; i < chain->num_points; i++) {
 324             if (last == NULL ||
 325                 point_distance_sq (last, &chain->points[i]) > tolerance) {
 326                 last = &chain->points[i];
 327             } else {
 328                 MARK_DELETED (&chain->points[i]);
 329             }
 330         }
 331     }
 332
 333     /* stage2: polygon simplification using Douglas-Peucker */
 334     simplified = FALSE;
 335     do {
 336         last = &contour->chain.points[0];
 337         iter_init (&furthest, contour);
 338         max = 0;
 339         for (chain = &contour->chain; chain; chain = chain->next) {
 340             for (i = 0; i < chain->num_points; i++) {
 341                 uint64_t d;
 342
 343                 if (DELETED (&chain->points[i]))
 344                     continue;
 345
 346                 d = point_distance_sq (last, &chain->points[i]);
 347                 if (d > max) {
 348                     furthest.chain = chain;
 349                     furthest.point = &chain->points[i];
 350                     max = d;
 351                 }
 352             }
 353         }
 354         assert (max);
 355
 356         simplified = FALSE;
 357         iter_init (&iter, contour);
 358         simplified |= _cairo_contour_simplify_chain (contour, tolerance,
 359                                                      &iter, &furthest);
 360
 361         iter_init_last (&iter, contour);
 362         if (! iter_equal (&furthest, &iter))
 363             simplified |= _cairo_contour_simplify_chain (contour, tolerance,
 364                                                          &furthest, &iter);
 365     } while (simplified);
 366
 367     iter_init (&iter, contour);
 368     for (chain = &contour->chain; chain; chain = chain->next) {
 369         int num_points = chain->num_points;
 370         chain->num_points = 0;
 371         for (i = 0; i < num_points; i++) {
 372             if (! DELETED(&chain->points[i])) {
 373                 if (iter.point != &chain->points[i])
 374                     *iter.point = chain->points[i];
 375                 iter.chain->num_points++;
 376                 iter_next (&iter);
 377             }
 378         }
 379     }
 380
 381     if (iter.chain) {
 382         cairo_contour_chain_t *next;
 383
 384         for (chain = iter.chain->next; chain; chain = next) {
 385             next = chain->next;
 386             free (chain);
 387         }
 388
 389         iter.chain->next = NULL;
 390         contour->tail = iter.chain;
 391     }
 392 }
 393
 394 void
 395 _cairo_contour_reset (cairo_contour_t *contour)
 396 {
 397     _cairo_contour_fini (contour);
 398     _cairo_contour_init (contour, contour->direction);
 399 }
 400
 401 void
 402 _cairo_contour_fini (cairo_contour_t *contour)
 403 {
 404     cairo_contour_chain_t *chain, *next;
 405
 406     for (chain = contour->chain.next; chain; chain = next) {
 407         next = chain->next;
 408         free (chain);
 409     }
 410 }
 411
 412 void
 413 _cairo_debug_print_contour (FILE *file, cairo_contour_t *contour)
 414 {
 415     cairo_contour_chain_t *chain;
 416     int num_points, size_points;
 417     int i;
 418
 419     num_points = 0;
 420     size_points = 0;
 421     for (chain = &contour->chain; chain; chain = chain->next) {
 422         num_points += chain->num_points;
 423         size_points += chain->size_points;
 424     }
 425
 426     fprintf (file, "contour: direction=%d, num_points=%d / %d\n",
 427              contour->direction, num_points, size_points);
 428
 429     num_points = 0;
 430     for (chain = &contour->chain; chain; chain = chain->next) {
 431         for (i = 0; i < chain->num_points; i++) {
 432             fprintf (file, "  [%d] = (%f, %f)\n",
 433                      num_points++,
 434                      _cairo_fixed_to_double (chain->points[i].x),
 435                      _cairo_fixed_to_double (chain->points[i].y));
 436         }
 437     }
 438 }
 439
 440 void
 441 __cairo_contour_remove_last_chain (cairo_contour_t *contour)
 442 {
 443     cairo_contour_chain_t *chain;
 444
 445     if (contour->tail == &contour->chain)
 446         return;
 447
 448     for (chain = &contour->chain; chain->next != contour->tail; chain = chain->next)
 449         ;
 450     free (contour->tail);
 451     contour->tail = chain;
 452     chain->next = NULL;
 453 }