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-inline.h"
  44 #include "cairo-contour-inline.h"
  45 #include "cairo-contour-private.h"
  46
  47 void
  48 _cairo_contour_init (cairo_contour_t *contour,
  49                      int direction)
  50 {
  51     contour->direction = direction;
  52     contour->chain.points = contour->embedded_points;
  53     contour->chain.next = NULL;
  54     contour->chain.num_points = 0;
  55     contour->chain.size_points = ARRAY_LENGTH (contour->embedded_points);
  56     contour->tail = &contour->chain;
  57 }
  58
  59 cairo_int_status_t
  60 __cairo_contour_add_point (cairo_contour_t *contour,
  61                           const cairo_point_t *point)
  62 {
  63     cairo_contour_chain_t *tail = contour->tail;
  64     cairo_contour_chain_t *next;
  65
  66     assert (tail->next == NULL);
  67
  68     next = _cairo_malloc_ab_plus_c (tail->size_points*2,
  69                                     sizeof (cairo_point_t),
  70                                     sizeof (cairo_contour_chain_t));
  71     if (unlikely (next == NULL))
  72         return _cairo_error (CAIRO_STATUS_NO_MEMORY);
  73
  74     next->size_points = tail->size_points*2;
  75     next->num_points = 1;
  76     next->points = (cairo_point_t *)(next+1);
  77     next->next = NULL;
  78     tail->next = next;
  79     contour->tail = next;
  80
  81     next->points[0] = *point;
  82     return CAIRO_INT_STATUS_SUCCESS;
  83 }
  84
  85 static void
  86 first_inc (cairo_contour_t *contour,
  87            cairo_point_t **p,
  88            cairo_contour_chain_t **chain)
  89 {
  90     if (*p == (*chain)->points + (*chain)->num_points) {
  91         assert ((*chain)->next);
  92         *chain = (*chain)->next;
  93         *p = &(*chain)->points[0];
  94     } else
  95         ++*p;
  96 }
  97
  98 static void
  99 last_dec (cairo_contour_t *contour,
 100           cairo_point_t **p,
 101           cairo_contour_chain_t **chain)
 102 {
 103     if (*p == (*chain)->points) {
 104         cairo_contour_chain_t *prev;
 105         assert (*chain != &contour->chain);
 106         for (prev = &contour->chain; prev->next != *chain; prev = prev->next)
 107             ;
 108         *chain = prev;
 109         *p = &(*chain)->points[(*chain)->num_points-1];
 110     } else
 111         --*p;
 112 }
 113
 114 void
 115 _cairo_contour_reverse (cairo_contour_t *contour)
 116 {
 117     cairo_contour_chain_t *first_chain, *last_chain;
 118     cairo_point_t *first, *last;
 119
 120     contour->direction = -contour->direction;
 121
 122     if (contour->chain.num_points <= 1)
 123         return;
 124
 125     first_chain = &contour->chain;
 126     last_chain = contour->tail;
 127
 128     first = &first_chain->points[0];
 129     last = &last_chain->points[last_chain->num_points-1];
 130
 131     while (first != last) {
 132         cairo_point_t p;
 133
 134         p = *first;
 135         *first = *last;
 136         *last = p;
 137
 138         first_inc (contour, &first, &first_chain);
 139         last_dec (contour, &last, &last_chain);
 140     }
 141 }
 142
 143 cairo_int_status_t
 144 _cairo_contour_add (cairo_contour_t *dst,
 145                     const cairo_contour_t *src)
 146 {
 147     const cairo_contour_chain_t *chain;
 148     cairo_int_status_t status;
 149     int i;
 150
 151     for (chain = &src->chain; chain; chain = chain->next) {
 152         for (i = 0; i < chain->num_points; i++) {
 153             status = _cairo_contour_add_point (dst, &chain->points[i]);
 154             if (unlikely (status))
 155                 return status;
 156         }
 157     }
 158
 159     return CAIRO_INT_STATUS_SUCCESS;
 160 }
 161
 162 static inline cairo_bool_t
 163 iter_next (cairo_contour_iter_t *iter)
 164 {
 165     if (iter->point == &iter->chain->points[iter->chain->size_points-1]) {
 166         iter->chain = iter->chain->next;
 167         if (iter->chain == NULL)
 168             return FALSE;
 169
 170         iter->point = &iter->chain->points[0];
 171         return TRUE;
 172     } else {
 173         iter->point++;
 174         return TRUE;
 175     }
 176 }
 177
 178 static cairo_bool_t
 179 iter_equal (const cairo_contour_iter_t *i1,
 180             const cairo_contour_iter_t *i2)
 181 {
 182     return i1->chain == i2->chain && i1->point == i2->point;
 183 }
 184
 185 static void
 186 iter_init (cairo_contour_iter_t *iter, cairo_contour_t *contour)
 187 {
 188     iter->chain = &contour->chain;
 189     iter->point = &contour->chain.points[0];
 190 }
 191
 192 static void
 193 iter_init_last (cairo_contour_iter_t *iter, cairo_contour_t *contour)
 194 {
 195     iter->chain = contour->tail;
 196     iter->point = &contour->tail->points[contour->tail->num_points-1];
 197 }
 198
 199 static const cairo_contour_chain_t *prev_const_chain(const cairo_contour_t *contour,
 200                                                      const cairo_contour_chain_t *chain)
 201 {
 202     const cairo_contour_chain_t *prev;
 203
 204     if (chain == &contour->chain)
 205         return NULL;
 206
 207     for (prev = &contour->chain; prev->next != chain; prev = prev->next)
 208         ;
 209
 210     return prev;
 211 }
 212
 213 cairo_int_status_t
 214 _cairo_contour_add_reversed (cairo_contour_t *dst,
 215                              const cairo_contour_t *src)
 216 {
 217     const cairo_contour_chain_t *last;
 218     cairo_int_status_t status;
 219     int i;
 220
 221     if (src->chain.num_points == 0)
 222         return CAIRO_INT_STATUS_SUCCESS;
 223
 224     for (last = src->tail; last; last = prev_const_chain (src, last)) {
 225         for (i = last->num_points-1; i >= 0; i--) {
 226             status = _cairo_contour_add_point (dst, &last->points[i]);
 227             if (unlikely (status))
 228                 return status;
 229         }
 230     }
 231
 232     return CAIRO_INT_STATUS_SUCCESS;
 233 }
 234
 235 static cairo_uint64_t
 236 point_distance_sq (const cairo_point_t *p1,
 237                    const cairo_point_t *p2)
 238 {
 239     int32_t dx = p1->x - p2->x;
 240     int32_t dy = p1->y - p2->y;
 241     return _cairo_int32x32_64_mul (dx, dx) + _cairo_int32x32_64_mul (dy, dy);
 242 }
 243
 244 #define DELETED(p) ((p)->x == INT_MIN && (p)->y == INT_MAX)
 245 #define MARK_DELETED(p) ((p)->x = INT_MIN, (p)->y = INT_MAX)
 246
 247 static cairo_bool_t
 248 _cairo_contour_simplify_chain (cairo_contour_t *contour, const double tolerance,
 249                                const cairo_contour_iter_t *first,
 250                                const cairo_contour_iter_t *last)
 251 {
 252     cairo_contour_iter_t iter, furthest;
 253     uint64_t max_error;
 254     int x0, y0;
 255     int nx, ny;
 256     int count;
 257
 258     iter = *first;
 259     iter_next (&iter);
 260     if (iter_equal (&iter, last))
 261         return FALSE;
 262
 263     x0 = first->point->x;
 264     y0 = first->point->y;
 265     nx = last->point->y - y0;
 266     ny = x0 - last->point->x;
 267
 268     count = 0;
 269     max_error = 0;
 270     do {
 271         cairo_point_t *p = iter.point;
 272         if (! DELETED(p)) {
 273             uint64_t d = (uint64_t)nx * (x0 - p->x) + (uint64_t)ny * (y0 - p->y);
 274             if (d * d > max_error) {
 275                 max_error = d * d;
 276                 furthest = iter;
 277             }
 278             count++;
 279         }
 280         iter_next (&iter);
 281     } while (! iter_equal (&iter, last));
 282     if (count == 0)
 283         return FALSE;
 284
 285     if (max_error > tolerance * ((uint64_t)nx * nx + (uint64_t)ny * ny)) {
 286         cairo_bool_t simplified;
 287
 288         simplified = FALSE;
 289         simplified |= _cairo_contour_simplify_chain (contour, tolerance,
 290                                                      first, &furthest);
 291         simplified |= _cairo_contour_simplify_chain (contour, tolerance,
 292                                                      &furthest, last);
 293         return simplified;
 294     } else {
 295         iter = *first;
 296         iter_next (&iter);
 297         do {
 298             MARK_DELETED (iter.point);
 299             iter_next (&iter);
 300         } while (! iter_equal (&iter, last));
 301
 302         return TRUE;
 303     }
 304 }
 305
 306 void
 307 _cairo_contour_simplify (cairo_contour_t *contour, double tolerance)
 308 {
 309     cairo_contour_chain_t *chain;
 310     cairo_point_t *last = NULL;
 311     cairo_contour_iter_t iter, furthest;
 312     cairo_bool_t simplified;
 313     uint64_t max = 0;
 314     int i;
 315
 316     if (contour->chain.num_points <= 2)
 317         return;
 318
 319     tolerance = tolerance * CAIRO_FIXED_ONE;
 320     tolerance *= tolerance;
 321
 322     /* stage 1: vertex reduction */
 323     for (chain = &contour->chain; chain; chain = chain->next) {
 324         for (i = 0; i < chain->num_points; i++) {
 325             if (last == NULL ||
 326                 point_distance_sq (last, &chain->points[i]) > tolerance) {
 327                 last = &chain->points[i];
 328             } else {
 329                 MARK_DELETED (&chain->points[i]);
 330             }
 331         }
 332     }
 333
 334     /* stage2: polygon simplification using Douglas-Peucker */
 335     simplified = FALSE;
 336     do {
 337         last = &contour->chain.points[0];
 338         iter_init (&furthest, contour);
 339         max = 0;
 340         for (chain = &contour->chain; chain; chain = chain->next) {
 341             for (i = 0; i < chain->num_points; i++) {
 342                 uint64_t d;
 343
 344                 if (DELETED (&chain->points[i]))
 345                     continue;
 346
 347                 d = point_distance_sq (last, &chain->points[i]);
 348                 if (d > max) {
 349                     furthest.chain = chain;
 350                     furthest.point = &chain->points[i];
 351                     max = d;
 352                 }
 353             }
 354         }
 355         assert (max);
 356
 357         simplified = FALSE;
 358         iter_init (&iter, contour);
 359         simplified |= _cairo_contour_simplify_chain (contour, tolerance,
 360                                                      &iter, &furthest);
 361
 362         iter_init_last (&iter, contour);
 363         if (! iter_equal (&furthest, &iter))
 364             simplified |= _cairo_contour_simplify_chain (contour, tolerance,
 365                                                          &furthest, &iter);
 366     } while (simplified);
 367
 368     iter_init (&iter, contour);
 369     for (chain = &contour->chain; chain; chain = chain->next) {
 370         int num_points = chain->num_points;
 371         chain->num_points = 0;
 372         for (i = 0; i < num_points; i++) {
 373             if (! DELETED(&chain->points[i])) {
 374                 if (iter.point != &chain->points[i])
 375                     *iter.point = chain->points[i];
 376                 iter.chain->num_points++;
 377                 iter_next (&iter);
 378             }
 379         }
 380     }
 381
 382     if (iter.chain) {
 383         cairo_contour_chain_t *next;
 384
 385         for (chain = iter.chain->next; chain; chain = next) {
 386             next = chain->next;
 387             free (chain);
 388         }
 389
 390         iter.chain->next = NULL;
 391         contour->tail = iter.chain;
 392     }
 393 }
 394
 395 void
 396 _cairo_contour_reset (cairo_contour_t *contour)
 397 {
 398     _cairo_contour_fini (contour);
 399     _cairo_contour_init (contour, contour->direction);
 400 }
 401
 402 void
 403 _cairo_contour_fini (cairo_contour_t *contour)
 404 {
 405     cairo_contour_chain_t *chain, *next;
 406
 407     for (chain = contour->chain.next; chain; chain = next) {
 408         next = chain->next;
 409         free (chain);
 410     }
 411 }
 412
 413 void
 414 _cairo_debug_print_contour (FILE *file, cairo_contour_t *contour)
 415 {
 416     cairo_contour_chain_t *chain;
 417     int num_points, size_points;
 418     int i;
 419
 420     num_points = 0;
 421     size_points = 0;
 422     for (chain = &contour->chain; chain; chain = chain->next) {
 423         num_points += chain->num_points;
 424         size_points += chain->size_points;
 425     }
 426
 427     fprintf (file, "contour: direction=%d, num_points=%d / %d\n",
 428              contour->direction, num_points, size_points);
 429
 430     num_points = 0;
 431     for (chain = &contour->chain; chain; chain = chain->next) {
 432         for (i = 0; i < chain->num_points; i++) {
 433             fprintf (file, "  [%d] = (%f, %f)\n",
 434                      num_points++,
 435                      _cairo_fixed_to_double (chain->points[i].x),
 436                      _cairo_fixed_to_double (chain->points[i].y));
 437         }
 438     }
 439 }
 440
 441 void
 442 __cairo_contour_remove_last_chain (cairo_contour_t *contour)
 443 {
 444     cairo_contour_chain_t *chain;
 445
 446     if (contour->tail == &contour->chain)
 447         return;
 448
 449     for (chain = &contour->chain; chain->next != contour->tail; chain = chain->next)
 450         ;
 451     free (contour->tail);
 452     contour->tail = chain;
 453     chain->next = NULL;
 454 }