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