cairo/src/cairo-spline.c

   1 /* cairo - a vector graphics library with display and print output
   2  *
   3  * Copyright © 2002 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 static cairo_status_t
  40 _cairo_spline_grow (cairo_spline_t *spline);
  41
  42 static cairo_status_t
  43 _cairo_spline_add_point (cairo_spline_t *spline, const cairo_point_t *point);
  44
  45 static void
  46 _lerp_half (const cairo_point_t *a, const cairo_point_t *b, cairo_point_t *result);
  47
  48 static void
  49 _de_casteljau (cairo_spline_knots_t *s1, cairo_spline_knots_t *s2);
  50
  51 static double
  52 _cairo_spline_error_squared (const cairo_spline_knots_t *spline);
  53
  54 static cairo_status_t
  55 _cairo_spline_decompose_into (cairo_spline_knots_t *spline, double tolerance_squared, cairo_spline_t *result);
  56
  57 cairo_int_status_t
  58 _cairo_spline_init (cairo_spline_t *spline,
  59                     const cairo_point_t *a, const cairo_point_t *b,
  60                     const cairo_point_t *c, const cairo_point_t *d)
  61 {
  62     spline->knots.a = *a;
  63     spline->knots.b = *b;
  64     spline->knots.c = *c;
  65     spline->knots.d = *d;
  66
  67     if (a->x != b->x || a->y != b->y)
  68         _cairo_slope_init (&spline->initial_slope, &spline->knots.a, &spline->knots.b);
  69     else if (a->x != c->x || a->y != c->y)
  70         _cairo_slope_init (&spline->initial_slope, &spline->knots.a, &spline->knots.c);
  71     else if (a->x != d->x || a->y != d->y)
  72         _cairo_slope_init (&spline->initial_slope, &spline->knots.a, &spline->knots.d);
  73     else
  74         return CAIRO_INT_STATUS_DEGENERATE;
  75
  76     if (c->x != d->x || c->y != d->y)
  77         _cairo_slope_init (&spline->final_slope, &spline->knots.c, &spline->knots.d);
  78     else if (b->x != d->x || b->y != d->y)
  79         _cairo_slope_init (&spline->final_slope, &spline->knots.b, &spline->knots.d);
  80     else
  81         _cairo_slope_init (&spline->final_slope, &spline->knots.a, &spline->knots.d);
  82
  83     spline->points = spline->points_embedded;
  84     spline->points_size = ARRAY_LENGTH (spline->points_embedded);
  85     spline->num_points = 0;
  86
  87     return CAIRO_STATUS_SUCCESS;
  88 }
  89
  90 void
  91 _cairo_spline_fini (cairo_spline_t *spline)
  92 {
  93     if (spline->points != spline->points_embedded)
  94         free (spline->points);
  95
  96     spline->points = spline->points_embedded;
  97     spline->points_size = ARRAY_LENGTH (spline->points_embedded);
  98     spline->num_points = 0;
  99 }
 100
 101 /* make room for at least one more point */
 102 static cairo_status_t
 103 _cairo_spline_grow (cairo_spline_t *spline)
 104 {
 105     cairo_point_t *new_points;
 106     int old_size = spline->points_size;
 107     int new_size = 2 * MAX (old_size, 16);
 108
 109     assert (spline->num_points <= spline->points_size);
 110
 111     if (spline->points == spline->points_embedded) {
 112         new_points = _cairo_malloc_ab (new_size, sizeof (cairo_point_t));
 113         if (new_points)
 114             memcpy (new_points, spline->points, old_size * sizeof (cairo_point_t));
 115     } else {
 116         new_points = _cairo_realloc_ab (spline->points,
 117                                         new_size, sizeof (cairo_point_t));
 118     }
 119
 120     if (new_points == NULL)
 121         return _cairo_error (CAIRO_STATUS_NO_MEMORY);
 122
 123     spline->points = new_points;
 124     spline->points_size = new_size;
 125
 126     return CAIRO_STATUS_SUCCESS;
 127 }
 128
 129 static cairo_status_t
 130 _cairo_spline_add_point (cairo_spline_t *spline, const cairo_point_t *point)
 131 {
 132     cairo_status_t status;
 133     cairo_point_t *prev;
 134
 135     if (spline->num_points) {
 136         prev = &spline->points[spline->num_points - 1];
 137         if (prev->x == point->x && prev->y == point->y)
 138             return CAIRO_STATUS_SUCCESS;
 139     }
 140
 141     if (spline->num_points >= spline->points_size) {
 142         status = _cairo_spline_grow (spline);
 143         if (status)
 144             return status;
 145     }
 146
 147     spline->points[spline->num_points] = *point;
 148     spline->num_points++;
 149
 150     return CAIRO_STATUS_SUCCESS;
 151 }
 152
 153 static void
 154 _lerp_half (const cairo_point_t *a, const cairo_point_t *b, cairo_point_t *result)
 155 {
 156     result->x = a->x + ((b->x - a->x) >> 1);
 157     result->y = a->y + ((b->y - a->y) >> 1);
 158 }
 159
 160 static void
 161 _de_casteljau (cairo_spline_knots_t *s1, cairo_spline_knots_t *s2)
 162 {
 163     cairo_point_t ab, bc, cd;
 164     cairo_point_t abbc, bccd;
 165     cairo_point_t final;
 166
 167     _lerp_half (&s1->a, &s1->b, &ab);
 168     _lerp_half (&s1->b, &s1->c, &bc);
 169     _lerp_half (&s1->c, &s1->d, &cd);
 170     _lerp_half (&ab, &bc, &abbc);
 171     _lerp_half (&bc, &cd, &bccd);
 172     _lerp_half (&abbc, &bccd, &final);
 173
 174     s2->a = final;
 175     s2->b = bccd;
 176     s2->c = cd;
 177     s2->d = s1->d;
 178
 179     s1->b = ab;
 180     s1->c = abbc;
 181     s1->d = final;
 182 }
 183
 184 /* Return an upper bound on the error (squared) that could result from
 185  * approximating a spline as a line segment connecting the two endpoints. */
 186 static double
 187 _cairo_spline_error_squared (const cairo_spline_knots_t *knots)
 188 {
 189     double bdx, bdy, berr;
 190     double cdx, cdy, cerr;
 191
 192     /* Intersection point (px):
 193      *      px = p1 + u(p2 - p1)
 194      *      (p - px) ∙ (p2 - p1) = 0
 195      * Thus:
 196      *      u = ((p - p1) ∙ (p2 - p1)) / ∥p2 - p1∥²;
 197      */
 198     bdx = _cairo_fixed_to_double (knots->b.x - knots->a.x);
 199     bdy = _cairo_fixed_to_double (knots->b.y - knots->a.y);
 200
 201     cdx = _cairo_fixed_to_double (knots->c.x - knots->a.x);
 202     cdy = _cairo_fixed_to_double (knots->c.y - knots->a.y);
 203
 204     if (knots->a.x != knots->d.x || knots->a.y != knots->d.y) {
 205         double dx, dy, u, v;
 206
 207         dx = _cairo_fixed_to_double (knots->d.x - knots->a.x);
 208         dy = _cairo_fixed_to_double (knots->d.y - knots->a.y);
 209          v = dx * dx + dy * dy;
 210
 211         u = bdx * dx + bdy * dy;
 212         if (u <= 0) {
 213             /* bdx -= 0;
 214              * bdy -= 0;
 215              */
 216         } else if (u >= v) {
 217             bdx -= dx;
 218             bdy -= dy;
 219         } else {
 220             bdx -= u/v * dx;
 221             bdy -= u/v * dy;
 222         }
 223
 224         u = cdx * dx + cdy * dy;
 225         if (u <= 0) {
 226             /* cdx -= 0;
 227              * cdy -= 0;
 228              */
 229         } else if (u >= v) {
 230             cdx -= dx;
 231             cdy -= dy;
 232         } else {
 233             cdx -= u/v * dx;
 234             cdy -= u/v * dy;
 235         }
 236     }
 237
 238     berr = bdx * bdx + bdy * bdy;
 239     cerr = cdx * cdx + cdy * cdy;
 240     if (berr > cerr)
 241         return berr;
 242     else
 243         return cerr;
 244 }
 245
 246 static cairo_status_t
 247 _cairo_spline_decompose_into (cairo_spline_knots_t *s1, double tolerance_squared, cairo_spline_t *result)
 248 {
 249     cairo_spline_knots_t s2;
 250     cairo_status_t status;
 251
 252     if (_cairo_spline_error_squared (s1) < tolerance_squared)
 253         return _cairo_spline_add_point (result, &s1->a);
 254
 255     _de_casteljau (s1, &s2);
 256
 257     status = _cairo_spline_decompose_into (s1, tolerance_squared, result);
 258     if (status)
 259         return status;
 260
 261     status = _cairo_spline_decompose_into (&s2, tolerance_squared, result);
 262     if (status)
 263         return status;
 264
 265     return CAIRO_STATUS_SUCCESS;
 266 }
 267
 268 cairo_status_t
 269 _cairo_spline_decompose (cairo_spline_t *spline, double tolerance)
 270 {
 271     cairo_status_t status;
 272     cairo_spline_knots_t s1;
 273
 274     /* reset the spline, but keep the buffer */
 275     spline->num_points = 0;
 276
 277     s1 = spline->knots;
 278     status = _cairo_spline_decompose_into (&s1, tolerance * tolerance, spline);
 279     if (status)
 280         return status;
 281
 282     status = _cairo_spline_add_point (spline, &spline->knots.d);
 283     if (status)
 284         return status;
 285
 286     return CAIRO_STATUS_SUCCESS;
 287 }