src/cairo-hull.c

   1 /* cairo - a vector graphics library with display and print output
   2  *
   3  * Copyright © 2003 University of Southern California
   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  * The Initial Developer of the Original Code is University of Southern
  31  * California.
  32  *
  33  * Contributor(s):
  34  *      Carl D. Worth <cworth@cworth.org>
  35  */
  36
  37 #include "cairoint.h"
  38
  39 #include "cairo-error-private.h"
  40 #include "cairo-slope-private.h"
  41
  42 typedef struct cairo_hull {
  43     cairo_point_t point;
  44     cairo_slope_t slope;
  45     int discard;
  46     int id;
  47 } cairo_hull_t;
  48
  49 static void
  50 _cairo_hull_init (cairo_hull_t                  *hull,
  51                   cairo_pen_vertex_t            *vertices,
  52                   int                            num_vertices)
  53 {
  54     cairo_point_t *p, *extremum, tmp;
  55     int i;
  56
  57     extremum = &vertices[0].point;
  58     for (i = 1; i < num_vertices; i++) {
  59         p = &vertices[i].point;
  60         if (p->y < extremum->y || (p->y == extremum->y && p->x < extremum->x))
  61             extremum = p;
  62     }
  63     /* Put the extremal point at the beginning of the array */
  64     tmp = *extremum;
  65     *extremum = vertices[0].point;
  66     vertices[0].point = tmp;
  67
  68     for (i = 0; i < num_vertices; i++) {
  69         hull[i].point = vertices[i].point;
  70         _cairo_slope_init (&hull[i].slope, &hull[0].point, &hull[i].point);
  71
  72         /* give each point a unique id for later comparison */
  73         hull[i].id = i;
  74
  75         /* Don't discard by default */
  76         hull[i].discard = 0;
  77
  78         /* Discard all points coincident with the extremal point */
  79         if (i != 0 && hull[i].slope.dx == 0 && hull[i].slope.dy == 0)
  80             hull[i].discard = 1;
  81     }
  82 }
  83
  84 static inline cairo_int64_t
  85 _slope_length (cairo_slope_t *slope)
  86 {
  87     return _cairo_int64_add (_cairo_int32x32_64_mul (slope->dx, slope->dx),
  88                              _cairo_int32x32_64_mul (slope->dy, slope->dy));
  89 }
  90
  91 static int
  92 _cairo_hull_vertex_compare (const void *av, const void *bv)
  93 {
  94     cairo_hull_t *a = (cairo_hull_t *) av;
  95     cairo_hull_t *b = (cairo_hull_t *) bv;
  96     int ret;
  97
  98     /* Some libraries are reported to actually compare identical
  99      * pointers and require the result to be 0. This is the crazy world we
 100      * have to live in.
 101      */
 102     if (a == b)
 103         return 0;
 104
 105     ret = _cairo_slope_compare (&a->slope, &b->slope);
 106
 107     /*
 108      * In the case of two vertices with identical slope from the
 109      * extremal point discard the nearer point.
 110      */
 111     if (ret == 0) {
 112         int cmp;
 113
 114         cmp = _cairo_int64_cmp (_slope_length (&a->slope),
 115                                 _slope_length (&b->slope));
 116
 117         /*
 118          * Use the points' ids to ensure a well-defined ordering,
 119          * and avoid setting discard on both points.
 120          */
 121         if (cmp < 0 || (cmp == 0 && a->id < b->id)) {
 122             a->discard = 1;
 123             ret = -1;
 124         } else {
 125             b->discard = 1;
 126             ret = 1;
 127         }
 128     }
 129
 130     return ret;
 131 }
 132
 133 static int
 134 _cairo_hull_prev_valid (cairo_hull_t *hull, int num_hull, int index)
 135 {
 136     /* hull[0] is always valid, and we never need to wraparound, (if
 137      * we are passed an index of 0 here, then the calling loop is just
 138      * about to terminate). */
 139     if (index == 0)
 140         return 0;
 141
 142     do {
 143         index--;
 144     } while (hull[index].discard);
 145
 146     return index;
 147 }
 148
 149 static int
 150 _cairo_hull_next_valid (cairo_hull_t *hull, int num_hull, int index)
 151 {
 152     do {
 153         index = (index + 1) % num_hull;
 154     } while (hull[index].discard);
 155
 156     return index;
 157 }
 158
 159 static void
 160 _cairo_hull_eliminate_concave (cairo_hull_t *hull, int num_hull)
 161 {
 162     int i, j, k;
 163     cairo_slope_t slope_ij, slope_jk;
 164
 165     i = 0;
 166     j = _cairo_hull_next_valid (hull, num_hull, i);
 167     k = _cairo_hull_next_valid (hull, num_hull, j);
 168
 169     do {
 170         _cairo_slope_init (&slope_ij, &hull[i].point, &hull[j].point);
 171         _cairo_slope_init (&slope_jk, &hull[j].point, &hull[k].point);
 172
 173         /* Is the angle formed by ij and jk concave? */
 174         if (_cairo_slope_compare (&slope_ij, &slope_jk) >= 0) {
 175             if (i == k)
 176                 return;
 177             hull[j].discard = 1;
 178             j = i;
 179             i = _cairo_hull_prev_valid (hull, num_hull, j);
 180         } else {
 181             i = j;
 182             j = k;
 183             k = _cairo_hull_next_valid (hull, num_hull, j);
 184         }
 185     } while (j != 0);
 186 }
 187
 188 static void
 189 _cairo_hull_to_pen (cairo_hull_t *hull, cairo_pen_vertex_t *vertices, int *num_vertices)
 190 {
 191     int i, j = 0;
 192
 193     for (i = 0; i < *num_vertices; i++) {
 194         if (hull[i].discard)
 195             continue;
 196         vertices[j++].point = hull[i].point;
 197     }
 198
 199     *num_vertices = j;
 200 }
 201
 202 /* Given a set of vertices, compute the convex hull using the Graham
 203    scan algorithm. */
 204 cairo_status_t
 205 _cairo_hull_compute (cairo_pen_vertex_t *vertices, int *num_vertices)
 206 {
 207     cairo_hull_t hull_stack[CAIRO_STACK_ARRAY_LENGTH (cairo_hull_t)];
 208     cairo_hull_t *hull;
 209     int num_hull = *num_vertices;
 210
 211     if (CAIRO_INJECT_FAULT ())
 212         return _cairo_error (CAIRO_STATUS_NO_MEMORY);
 213
 214     if (num_hull > ARRAY_LENGTH (hull_stack)) {
 215         hull = _cairo_malloc_ab (num_hull, sizeof (cairo_hull_t));
 216         if (unlikely (hull == NULL))
 217             return _cairo_error (CAIRO_STATUS_NO_MEMORY);
 218     } else {
 219         hull = hull_stack;
 220     }
 221
 222     _cairo_hull_init (hull, vertices, num_hull);
 223
 224     qsort (hull + 1, num_hull - 1,
 225            sizeof (cairo_hull_t), _cairo_hull_vertex_compare);
 226
 227     _cairo_hull_eliminate_concave (hull, num_hull);
 228
 229     _cairo_hull_to_pen (hull, vertices, num_vertices);
 230
 231     if (hull != hull_stack)
 232         free (hull);
 233
 234     return CAIRO_STATUS_SUCCESS;
 235 }