src/cpml/cpml-curve.c

   1 /* CPML - Cairo Path Manipulation Library
   2  * Copyright (C) 2007-2021  Nicola Fontana <ntd at entidi.it>
   3  *
   4  * This library is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU Lesser General Public
   6  * License as published by the Free Software Foundation; either
   7  * version 2 of the License, or (at your option) any later version.
   8  *
   9  * This library is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12  * Lesser General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU Lesser General Public
  15  * License along with this library; if not, write to the
  16  * Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  17  * Boston, MA  02110-1301, USA.
  18  */
  19
  20
  21 /**
  22  * SECTION:cpml-curve
  23  * @Section_Id:CpmlCurve
  24  * @title: CpmlCurve
  25  * @short_description: Bézier cubic curve primitive management
  26  *
  27  * The following functions manipulate %CPML_CURVE #CpmlPrimitive.
  28  * No validation is made on the input so use the following methods
  29  * only when you are sure the <varname>primitive</varname> argument
  30  * is effectively a cubic Bézier curve.
  31  *
  32  * <important>
  33  * <title>TODO</title>
  34  * <itemizedlist>
  35  * <listitem>the <function>get_length</function> method must be
  36  *           implemented;</listitem>
  37  * <listitem>actually the <function>put_extents</function> method is
  38  *           implemented by computing the bounding box of the control
  39  *           polygon and this will likely include some empty space:
  40  *           there is room for improvements;</listitem>
  41  * <listitem>the <function>put_pair_at</function> method must be
  42  *           implemented;</listitem>
  43  * <listitem>the <function>put_vector_at</function> method must be
  44  *           implemented;</listitem>
  45  * <listitem>the <function>get_closest_pos</function> method must be
  46  *           implemented;</listitem>
  47  * <listitem>the <function>put_intersections</function> method must be
  48  *           implemented;</listitem>
  49  * </itemizedlist>
  50  * </important>
  51  *
  52  * Since: 1.0
  53  **/
  54
  55
  56 /**
  57  * CpmlCurveOffsetAlgorithm:
  58  * @CPML_CURVE_OFFSET_ALGORITHM_NONE: unknown or no specific algorithm
  59  * @CPML_CURVE_OFFSET_ALGORITHM_DEFAULT: default algorithm
  60  * @CPML_CURVE_OFFSET_ALGORITHM_GEOMETRICAL: geometrical algorithm
  61  * @CPML_CURVE_OFFSET_ALGORITHM_HANDCRAFT: handcraft algorithm
  62  * @CPML_CURVE_OFFSET_ALGORITHM_BAIOCA: B.A.I.O.C.A. algorithm
  63  *
  64  * Enumeration of all available algorithms for offsetting the B(t) cubic
  65  * Bézier curve.
  66  *
  67  * The geometrical algorithm offset the control polygon, further applying a
  68  * factor of 4/3 on the control points along the vector normal to B(0.5). That
  69  * factor mix well with curves approximating arcs (the most common case). It
  70  * is a stable algorithm, i.e. it can be used for every Bézier.
  71  *
  72  * The handcraft algorithm offsets the point at B(0.5) and it forces the
  73  * condition the offset curve at t=0.5 must pass through that point. If it
  74  * fails, falls back to geometrical.
  75  *
  76  * The BAIOCA algorithm offsets a specific set of t values and try to minimize
  77  * the error between those points and the offset curve at the same t values.
  78  * If it fails, falls back to geometrical. By default the set of t values is
  79  * { 0, 0.25, 0.5, 0.75, 1 }. As implied by this description, using the set
  80  * { 0, 0.5, 1 } is logically equivalent to the handcraft algorithm.
  81  *
  82  * The default algorith is #CPML_CURVE_OFFSET_ALGORITHM_HANDCRAFT.
  83  *
  84  * Since: 1.0
  85  **/
  86
  87
  88 #include "cpml-internal.h"
  89 #include "cpml-extents.h"
  90 #include "cpml-segment.h"
  91 #include "cpml-primitive.h"
  92 #include "cpml-primitive-private.h"
  93 #include "cpml-curve.h"
  94
  95 #define DEFAULT_ALGORITHM   offset_handcraft
  96
  97
  98 static void     put_extents             (const CpmlPrimitive    *curve,
  99                                          CpmlExtents            *extents);
 100 static void     offset_geometrical      (CpmlPrimitive          *curve,
 101                                          double                  offset);
 102 static void     offset_handcraft        (CpmlPrimitive          *curve,
 103                                          double                  offset);
 104 static void     offset_baioca           (CpmlPrimitive          *curve,
 105                                          double                  offset);
 106
 107 /* class_data is outside get_class so it can be modified by other methods */
 108 static _CpmlPrimitiveClass class_data = {
 109     "curve to", 4,
 110     NULL,
 111     put_extents,
 112     NULL,
 113     NULL,
 114     NULL,
 115     NULL,
 116     DEFAULT_ALGORITHM,
 117     NULL
 118 };
 119
 120
 121 const _CpmlPrimitiveClass *
 122 _cpml_curve_get_class(void)
 123 {
 124     return &class_data;
 125 }
 126
 127 /**
 128  * cpml_curve_offset_algorithm:
 129  * @new_algorithm: the new algorithm to use
 130  *
 131  * Selects the algorithm to use for offsetting Bézier curves and
 132  * returns the old algorithm.
 133  *
 134  * You can use #CPML_CURVE_OFFSET_ALGORITHM_NONE (that does not
 135  * change the current algorithm) if you are only interested in
 136  * knowing which is the current algorithm used.
 137  *
 138  * <important><para>
 139  * This function is <emphasis>not thread-safe</emphasis>. If you
 140  * are changing the algorithm in a thread environment you must
 141  * ensure by yourself no other threads are calling #CpmlCurve
 142  * methods in the meantime.
 143  * </para></important>
 144  *
 145  * Returns: the previous algorithm used.
 146  *
 147  * Since: 1.0
 148  **/
 149 CpmlCurveOffsetAlgorithm
 150 cpml_curve_offset_algorithm(CpmlCurveOffsetAlgorithm new_algorithm)
 151 {
 152     CpmlCurveOffsetAlgorithm old_algorithm;
 153
 154     /* Reverse lookup of the algorithm used */
 155     if (class_data.offset == offset_handcraft) {
 156         old_algorithm = CPML_CURVE_OFFSET_ALGORITHM_HANDCRAFT;
 157     } else if (class_data.offset == offset_baioca) {
 158         old_algorithm = CPML_CURVE_OFFSET_ALGORITHM_BAIOCA;
 159     } else if (class_data.offset == offset_geometrical) {
 160         old_algorithm = CPML_CURVE_OFFSET_ALGORITHM_GEOMETRICAL;
 161     } else {
 162         old_algorithm = CPML_CURVE_OFFSET_ALGORITHM_NONE;
 163     }
 164
 165     switch (new_algorithm) {
 166     case CPML_CURVE_OFFSET_ALGORITHM_NONE:
 167         break;
 168     case CPML_CURVE_OFFSET_ALGORITHM_DEFAULT:
 169         class_data.offset = DEFAULT_ALGORITHM;
 170         break;
 171     case CPML_CURVE_OFFSET_ALGORITHM_GEOMETRICAL:
 172         class_data.offset = offset_geometrical;
 173         break;
 174     case CPML_CURVE_OFFSET_ALGORITHM_BAIOCA:
 175         class_data.offset = offset_baioca;
 176         break;
 177     case CPML_CURVE_OFFSET_ALGORITHM_HANDCRAFT:
 178         class_data.offset = offset_handcraft;
 179         break;
 180     }
 181
 182     return old_algorithm;
 183 }
 184
 185 /**
 186  * cpml_curve_put_pair_at_time:
 187  * @curve: the #CpmlPrimitive curve data
 188  * @t:     the "time" value
 189  * @pair:  the destination pair
 190  *
 191  * Given the @curve Bézier cubic, finds the coordinates at time @t
 192  * (where 0 is the start and 1 is the end) and stores the result
 193  * in @pair. Keep in mind @t is not homogeneous, so 0.5 does not
 194  * necessarily means the mid point.
 195  *
 196  * Since: 1.0
 197  **/
 198 void
 199 cpml_curve_put_pair_at_time(const CpmlPrimitive *curve, double t,
 200                             CpmlPair *pair)
 201 {
 202     CpmlPair p1, p2, p3, p4;
 203     double t_2, t_3, t1, t1_2, t1_3;
 204
 205     cpml_primitive_put_point(curve, 0, &p1);
 206     cpml_primitive_put_point(curve, 1, &p2);
 207     cpml_primitive_put_point(curve, 2, &p3);
 208     cpml_primitive_put_point(curve, 3, &p4);
 209
 210     t_2 = t * t;
 211     t_3 = t_2 * t;
 212     t1 = 1 - t;
 213     t1_2 = t1 * t1;
 214     t1_3 = t1_2 * t1;
 215
 216     pair->x = t1_3 * p1.x + 3 * t1_2 * t * p2.x
 217               + 3 * t1 * t_2 * p3.x + t_3 * p4.x;
 218     pair->y = t1_3 * p1.y + 3 * t1_2 * t * p2.y
 219               + 3 * t1 * t_2 * p3.y + t_3 * p4.y;
 220 }
 221
 222 /**
 223  * cpml_curve_put_vector_at_time:
 224  * @curve:  the #CpmlPrimitive curve data
 225  * @t:      the "time" value
 226  * @vector: the destination vector
 227  *
 228  * Given the @curve Bézier cubic, finds the slope at time @t
 229  * (where 0 is the start and 1 is the end) and stores the result
 230  * in @vector. Keep in mind @t is not homogeneous, so 0.5
 231  * does not necessarily means the mid point.
 232  *
 233  * Since: 1.0
 234  **/
 235 void
 236 cpml_curve_put_vector_at_time(const CpmlPrimitive *curve,
 237                               double t, CpmlVector *vector)
 238 {
 239     CpmlPair p1, p2, p3, p4;
 240     CpmlPair p21, p32, p43;
 241     double t1, t1_2, t_2;
 242
 243     cpml_primitive_put_point(curve, 0, &p1);
 244     cpml_primitive_put_point(curve, 1, &p2);
 245     cpml_primitive_put_point(curve, 2, &p3);
 246     cpml_primitive_put_point(curve, 3, &p4);
 247
 248     p21.x = p2.x - p1.x;
 249     p21.y = p2.y - p1.y;
 250     p32.x = p3.x - p2.x;
 251     p32.y = p3.y - p2.y;
 252     p43.x = p4.x - p3.x;
 253     p43.y = p4.y - p3.y;
 254
 255     t1 = 1 - t;
 256     t1_2 = t1 * t1;
 257     t_2 = t * t;
 258
 259     vector->x = 3 * t1_2 * p21.x + 6 * t1 * t * p32.x + 3 * t_2 * p43.x;
 260     vector->y = 3 * t1_2 * p21.y + 6 * t1 * t * p32.y + 3 * t_2 * p43.y;
 261 }
 262
 263 /**
 264  * cpml_curve_put_offset_at_time:
 265  * @curve:                        the #CpmlPrimitive curve data
 266  * @t:                            the "time" value
 267  * @offset:                       the offset distance
 268  * @pair: (out caller-allocates): the destination pair
 269  *
 270  * Given the @curve Bézier cubic, find the coordinates at time @t
 271  * (where 0 is the start and 1 is the end), offset that point at
 272  * @offset distance and stores the result in @pair.
 273  *
 274  * The point to offset and the vector along which that point must
 275  * be offseted are found calling cpml_curve_put_pair_at_time() and
 276  * cpml_curve_put_vector_at_time() respectively.
 277  *
 278  * Since: 1.0
 279  **/
 280 void
 281 cpml_curve_put_offset_at_time(const CpmlPrimitive *curve,
 282                               double t, double offset,
 283                               CpmlPair *pair)
 284 {
 285     CpmlVector vector;
 286
 287     cpml_curve_put_vector_at_time(curve, t, &vector);
 288     cpml_vector_normal(&vector);
 289     cpml_vector_set_length(&vector, offset);
 290
 291     cpml_curve_put_pair_at_time(curve, t, pair);
 292     pair->x += vector.x;
 293     pair->y += vector.y;
 294 }
 295
 296 static void
 297 put_extents(const CpmlPrimitive *curve, CpmlExtents *extents)
 298 {
 299     CpmlPair p1, p2, p3, p4;
 300
 301     extents->is_defined = 0;
 302
 303     cpml_primitive_put_point(curve, 0, &p1);
 304     cpml_primitive_put_point(curve, 1, &p2);
 305     cpml_primitive_put_point(curve, 2, &p3);
 306     cpml_primitive_put_point(curve, 3, &p4);
 307
 308     cpml_extents_pair_add(extents, &p1);
 309     cpml_extents_pair_add(extents, &p2);
 310     cpml_extents_pair_add(extents, &p3);
 311     cpml_extents_pair_add(extents, &p4);
 312 }
 313
 314 static int
 315 geometrical(CpmlPrimitive *curve, double offset, const CpmlVector *v)
 316 {
 317     CpmlVector v0, v3;
 318     CpmlPair p0, p1, p2, p3;
 319
 320     /* Firstly, convert the curve points from cairo format to cpml format
 321      * and store them (temporary) in p0..p3 */
 322     cpml_pair_from_cairo(&p0, curve->org);
 323     cpml_pair_from_cairo(&p1, &curve->data[1]);
 324     cpml_pair_from_cairo(&p2, &curve->data[2]);
 325     cpml_pair_from_cairo(&p3, &curve->data[3]);
 326
 327     /* v0 = p1-p0 */
 328     v0.x = p1.x - p0.x;
 329     v0.y = p1.y - p0.y;
 330
 331     /* v3 = p3-p2 */
 332     v3.x = p3.x - p2.x;
 333     v3.y = p3.y - p2.y;
 334
 335     cpml_curve_put_offset_at_time(curve, 0, offset, &p0);
 336     cpml_curve_put_offset_at_time(curve, 1, offset, &p3);
 337
 338     p1.x = p0.x + v0.x + v->x;
 339     p1.y = p0.y + v0.y + v->y;
 340     p2.x = p3.x - v3.x + v->x;
 341     p2.y = p3.y - v3.y + v->y;
 342
 343     /* Return the new curve in the original array */
 344     cpml_pair_to_cairo(&p0, curve->org);
 345     cpml_pair_to_cairo(&p1, &curve->data[1]);
 346     cpml_pair_to_cairo(&p2, &curve->data[2]);
 347     cpml_pair_to_cairo(&p3, &curve->data[3]);
 348
 349     return 1;
 350 }
 351
 352 static void
 353 offset_geometrical(CpmlPrimitive *curve, double offset)
 354 {
 355     CpmlVector v;
 356
 357     cpml_curve_put_vector_at_time(curve, 0.5, &v);
 358     cpml_vector_normal(&v);
 359     cpml_vector_set_length(&v, offset * 4/3);
 360
 361     geometrical(curve, offset, &v);
 362 }
 363
 364 static int
 365 handcraft(CpmlPrimitive *curve, double offset, double m)
 366 {
 367     CpmlVector v0, v3;
 368     CpmlPair p0, p1, p2, p3, r, s;
 369     double mm, k0, k3;
 370
 371     /* Firstly, convert the curve points from cairo format to cpml format
 372      * and store them (temporary) in p0..p3 */
 373     cpml_pair_from_cairo(&p0, curve->org);
 374     cpml_pair_from_cairo(&p1, &curve->data[1]);
 375     cpml_pair_from_cairo(&p2, &curve->data[2]);
 376     cpml_pair_from_cairo(&p3, &curve->data[3]);
 377
 378     /* v0 = p1-p0 */
 379     v0.x = p1.x - p0.x;
 380     v0.y = p1.y - p0.y;
 381
 382     /* v3 = p3-p2 */
 383     v3.x = p3.x - p2.x;
 384     v3.y = p3.y - p2.y;
 385
 386     if (v0.x*v3.y == v3.x*v0.y)
 387         return 0;
 388
 389     cpml_curve_put_offset_at_time(curve, m, offset, &r);
 390     cpml_curve_put_offset_at_time(curve, 0, offset, &p0);
 391     cpml_curve_put_offset_at_time(curve, 1, offset, &p3);
 392
 393     mm = 1 - m;
 394     s.x = (r.x - mm*mm*(1+m+m)*p0.x - m*m*(1+mm+mm)*p3.x) / (3*m*(1-m));
 395     s.y = (r.y - mm*mm*(1+m+m)*p0.y - m*m*(1+mm+mm)*p3.y) / (3*m*(1-m));
 396
 397     if (v0.x != 0) {
 398         k3 = (s.y - s.x*v0.y / v0.x) / (m*(v3.y - v3.x*v0.y / v0.x));
 399         k0 = (s.x - m*k3*v3.x) / (mm*v0.x);
 400     } else {
 401         k0 = (s.y - s.x*v3.y / v3.x) / (mm*(v0.y - v0.x*v3.y / v3.x));
 402         k3 = (s.x - mm*k0*v0.x) / (m*v3.x);
 403     }
 404
 405     p1.x = p0.x + k0*v0.x;
 406     p1.y = p0.y + k0*v0.y;
 407     p2.x = p3.x + k3*v3.x;
 408     p2.y = p3.y + k3*v3.y;
 409
 410     /* Return the new curve in the original array */
 411     cpml_pair_to_cairo(&p0, curve->org);
 412     cpml_pair_to_cairo(&p1, &curve->data[1]);
 413     cpml_pair_to_cairo(&p2, &curve->data[2]);
 414     cpml_pair_to_cairo(&p3, &curve->data[3]);
 415
 416     return 1;
 417 }
 418
 419 static void
 420 offset_handcraft(CpmlPrimitive *curve, double offset)
 421 {
 422     if (! handcraft(curve, offset, 0.5))
 423         offset_geometrical(curve, offset);
 424 }
 425
 426 /* Helper macro that returns the scalar product of two vectors */
 427 #define SP(a,b) ((a).x * (b).x + (a).y * (b).y)
 428
 429 static int
 430 baioca(CpmlPrimitive *curve, double offset, const double t[], int n)
 431 {
 432     int i;
 433     double _t, _t2, _1t, _1t2;
 434     CpmlPair B0, B1, B2, B3;
 435     CpmlPair Q0, Q1, Q2, Q3;
 436     CpmlPair P0, P2, Ci;
 437     double b0, b1, b2, b3;
 438     double D0, D2, E01, E02, E11, E12, E13, E22, E23;
 439     double A1, A2, A3, A4, A5;
 440     double r, s, divisor;
 441
 442     /* Pick the CpmlPair from the original primitive */
 443     cpml_pair_from_cairo(&B0, curve->org);
 444     cpml_pair_from_cairo(&B1, &curve->data[1]);
 445     cpml_pair_from_cairo(&B2, &curve->data[2]);
 446     cpml_pair_from_cairo(&B3, &curve->data[3]);
 447
 448     /* 3. Calculate P0 and P2 */
 449     P0.x = B1.x - B0.x;
 450     P0.y = B1.y - B0.y;
 451     P2.x = B3.x - B2.x;
 452     P2.y = B3.y - B2.y;
 453
 454     D0 = D2 = E01 = E02 = E11 = E12 = E13 = E22 = E23 = 0;
 455     for (i = 0; i <= n; ++i) {
 456         _t = t[i];
 457
 458         /* 2. Compute Ci */
 459         cpml_curve_put_offset_at_time(curve, _t, offset, &Ci);
 460         if (i == 0) {
 461             cpml_pair_copy(&Q0, &Ci);
 462         } else if (i == n) {
 463             cpml_pair_copy(&Q3, &Ci);
 464         } else {
 465             _t2 = _t * _t;
 466             _1t = 1 - _t;
 467             _1t2 = _1t * _1t;
 468             b0 = _1t * _1t2;
 469             b1 = 3 * _1t2 * _t;
 470             b2 = 3 * _1t * _t2;
 471             b3 = _t * _t2;
 472
 473             /* 4. Calculate D0, D2, E01, E02, E11, E12, E13, E22, E23 */
 474             D0  += b1 * SP(Ci, P0);
 475             D2  += b2 * SP(Ci, P2);
 476             E01 += b0 * b1;
 477             E02 += b0 * b2;
 478             E11 += b1 * b1;
 479             E12 += b1 * b2;
 480             E13 += b1 * b3;
 481             E22 += b2 * b2;
 482             E23 += b2 * b3;
 483         }
 484     }
 485
 486     /* 5. Calculate A1, A2, A3, A4 and A5 */
 487     A1 = D0 - SP(Q0, P0) * (E01 + E11) - SP(Q3, P0) * (E12 + E13);
 488     A2 = D2 - SP(Q0, P2) * (E02 + E12) - SP(Q3, P2) * (E22 + E23);
 489     A3 = SP(P0, P0) * E11;
 490     A4 = SP(P0, P2) * E12;
 491     A5 = SP(P2, P2) * E22;
 492
 493     /* 6. Calculate r and s */
 494     divisor = A3 * A5 - A4 * A4;
 495     if (divisor == 0)
 496         return 0;
 497
 498     r = (A1 * A5 - A4 * A2) / divisor;
 499     s = (A3 * A2 - A1 * A4) / divisor;
 500
 501     /* 7. Get Q1 and Q2 */
 502     Q1.x = Q0.x + r * P0.x;
 503     Q1.y = Q0.y + r * P0.y;
 504     Q2.x = Q3.x + s * P2.x;
 505     Q2.y = Q3.y + s * P2.y;
 506
 507     /* Store the results into the original primitive */
 508     cpml_pair_to_cairo(&Q0, curve->org);
 509     cpml_pair_to_cairo(&Q1, &curve->data[1]);
 510     cpml_pair_to_cairo(&Q2, &curve->data[2]);
 511     cpml_pair_to_cairo(&Q3, &curve->data[3]);
 512
 513     return 1;
 514 }
 515
 516 static void
 517 offset_baioca(CpmlPrimitive *curve, double offset)
 518 {
 519     int i, n = 4;
 520     double t[n+1];
 521
 522     /* 1. Select t_i using the lazy method */
 523     for (i = 0; i <= n; ++i)
 524         t[i] = (double) i / n;
 525
 526     if (! baioca(curve, offset, t, n))
 527         offset_geometrical(curve, offset);
 528 }