src/cpml/cpml-curve.c

   1 /* CPML - Cairo Path Manipulation Library
   2  * Copyright (C) 2007,2008,2009,2010,2011,2012,2013  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  * <listitem>by default, the offset curve is calculated by using the point
  50  *           at t=0.5 as reference: use a better candidate;</listitem>
  51  * <listitem>in the <function>offset</function> implementation, when the
  52  *           equations are inconsistent, the alternative approach performs
  53  *           very bad if <varname>v0</varname> and <varname>v3</varname> are
  54  *           opposite or staggered.</listitem>
  55  * </itemizedlist>
  56  * </important>
  57  *
  58  * Since: 1.0
  59  **/
  60
  61
  62 #include "cpml-internal.h"
  63 #include "cpml-extents.h"
  64 #include "cpml-segment.h"
  65 #include "cpml-primitive.h"
  66 #include "cpml-primitive-private.h"
  67 #include "cpml-curve.h"
  68
  69
  70 static void     put_extents             (const CpmlPrimitive    *curve,
  71                                          CpmlExtents            *extents);
  72 static void     offset                  (CpmlPrimitive          *curve,
  73                                          double                  offset);
  74
  75
  76 const _CpmlPrimitiveClass *
  77 _cpml_curve_get_class(void)
  78 {
  79     static _CpmlPrimitiveClass *p_class = NULL;
  80
  81     if (p_class == NULL) {
  82         static _CpmlPrimitiveClass class_data = {
  83             "curve to", 4,
  84             NULL,
  85             put_extents,
  86             NULL,
  87             NULL,
  88             NULL,
  89             NULL,
  90             offset,
  91             NULL
  92         };
  93         p_class = &class_data;
  94     }
  95
  96     return p_class;
  97 }
  98
  99
 100 /**
 101  * cpml_curve_put_pair_at_time:
 102  * @curve: the #CpmlPrimitive curve data
 103  * @t:     the "time" value
 104  * @pair:  the destination pair
 105  *
 106  * Given the @curve Bézier cubic, finds the coordinates at time @t
 107  * (where 0 is the start and 1 is the end) and stores the result
 108  * in @pair. Keep in mind @t is not homogeneous, so 0.5 does not
 109  * necessarily means the mid point.
 110  *
 111  * Since: 1.0
 112  **/
 113 void
 114 cpml_curve_put_pair_at_time(const CpmlPrimitive *curve, double t,
 115                             CpmlPair *pair)
 116 {
 117     CpmlPair p1, p2, p3, p4;
 118     double t_2, t_3, t1, t1_2, t1_3;
 119
 120     cpml_primitive_put_point(curve, 0, &p1);
 121     cpml_primitive_put_point(curve, 1, &p2);
 122     cpml_primitive_put_point(curve, 2, &p3);
 123     cpml_primitive_put_point(curve, 3, &p4);
 124
 125     t_2 = t * t;
 126     t_3 = t_2 * t;
 127     t1 = 1 - t;
 128     t1_2 = t1 * t1;
 129     t1_3 = t1_2 * t1;
 130
 131     pair->x = t1_3 * p1.x + 3 * t1_2 * t * p2.x
 132               + 3 * t1 * t_2 * p3.x + t_3 * p4.x;
 133     pair->y = t1_3 * p1.y + 3 * t1_2 * t * p2.y
 134               + 3 * t1 * t_2 * p3.y + t_3 * p4.y;
 135 }
 136
 137 /**
 138  * cpml_curve_put_vector_at_time:
 139  * @curve:  the #CpmlPrimitive curve data
 140  * @t:      the "time" value
 141  * @vector: the destination vector
 142  *
 143  * Given the @curve Bézier cubic, finds the slope at time @t
 144  * (where 0 is the start and 1 is the end) and stores the result
 145  * in @vector. Keep in mind @t is not homogeneous, so 0.5
 146  * does not necessarily means the mid point.
 147  *
 148  * Since: 1.0
 149  **/
 150 void
 151 cpml_curve_put_vector_at_time(const CpmlPrimitive *curve,
 152                               double t, CpmlVector *vector)
 153 {
 154     CpmlPair p1, p2, p3, p4;
 155     CpmlPair p21, p32, p43;
 156     double t1, t1_2, t_2;
 157
 158     cpml_primitive_put_point(curve, 0, &p1);
 159     cpml_primitive_put_point(curve, 1, &p2);
 160     cpml_primitive_put_point(curve, 2, &p3);
 161     cpml_primitive_put_point(curve, 3, &p4);
 162
 163     p21.x = p2.x - p1.x;
 164     p21.y = p2.y - p1.y;
 165     p32.x = p3.x - p2.x;
 166     p32.y = p3.y - p2.y;
 167     p43.x = p4.x - p3.x;
 168     p43.y = p4.y - p3.y;
 169
 170     t1 = 1 - t;
 171     t1_2 = t1 * t1;
 172     t_2 = t * t;
 173
 174     vector->x = 3 * t1_2 * p21.x + 6 * t1 * t * p32.x + 3 * t_2 * p43.x;
 175     vector->y = 3 * t1_2 * p21.y + 6 * t1 * t * p32.y + 3 * t_2 * p43.y;
 176 }
 177
 178
 179 static void
 180 put_extents(const CpmlPrimitive *curve, CpmlExtents *extents)
 181 {
 182     CpmlPair p1, p2, p3, p4;
 183
 184     extents->is_defined = 0;
 185
 186     cpml_primitive_put_point(curve, 0, &p1);
 187     cpml_primitive_put_point(curve, 1, &p2);
 188     cpml_primitive_put_point(curve, 2, &p3);
 189     cpml_primitive_put_point(curve, 3, &p4);
 190
 191     cpml_extents_pair_add(extents, &p1);
 192     cpml_extents_pair_add(extents, &p2);
 193     cpml_extents_pair_add(extents, &p3);
 194     cpml_extents_pair_add(extents, &p4);
 195 }
 196
 197 static void
 198 offset(CpmlPrimitive *curve, double offset)
 199 {
 200     double m, mm;
 201     CpmlVector v0, v3, vm, vtmp;
 202     CpmlPair p0, p1, p2, p3, r;
 203
 204     m = 0.5;
 205     mm = 1-m;
 206
 207     /* Firstly, convert the curve points from cairo format to cpml format
 208      * and store them (temporary) in p0..p3 */
 209     cpml_pair_from_cairo(&p0, curve->org);
 210     cpml_pair_from_cairo(&p1, &curve->data[1]);
 211     cpml_pair_from_cairo(&p2, &curve->data[2]);
 212     cpml_pair_from_cairo(&p3, &curve->data[3]);
 213
 214     /* v0 = p1-p0 */
 215     v0.x = p1.x - p0.x;
 216     v0.y = p1.y - p0.y;
 217
 218     /* v3 = p3-p2 */
 219     v3.x = p3.x - p2.x;
 220     v3.y = p3.y - p2.y;
 221
 222     /* r = point in C(m) offseted the requested @offset distance */
 223     cpml_curve_put_vector_at_time(curve, m, &vm);
 224     cpml_vector_set_length(&vm, offset);
 225     cpml_vector_normal(&vm);
 226     cpml_curve_put_pair_at_time(curve, m, &r);
 227     r.x += vm.x;
 228     r.y += vm.y;
 229
 230     /* p0 = p0 + normal of v0 of @offset magnitude (exact value) */
 231     cpml_pair_copy(&vtmp, &v0);
 232     cpml_vector_set_length(&vtmp, offset);
 233     cpml_vector_normal(&vtmp);
 234     p0.x += vtmp.x;
 235     p0.y += vtmp.y;
 236
 237     /* p3 = p3 + normal of v3 of @offset magnitude, as done for p0 */
 238     cpml_pair_copy(&vtmp, &v3);
 239     cpml_vector_set_length(&vtmp, offset);
 240     cpml_vector_normal(&vtmp);
 241     p3.x += vtmp.x;
 242     p3.y += vtmp.y;
 243
 244     if (v0.x*v3.y == v3.x*v0.y) {
 245         /* Inconsistent equations: use the alternative approach */
 246         p1.x = p0.x + v0.x + vm.x * 4/3;
 247         p1.y = p0.y + v0.y + vm.y * 4/3;
 248         p2.x = p3.x - v3.x + vm.x * 4/3;
 249         p2.y = p3.y - v3.y + vm.y * 4/3;
 250     } else {
 251         CpmlPair s;
 252         double k0, k3;
 253
 254         s.x = (r.x - mm*mm*(1+m+m)*p0.x - m*m*(1+mm+mm)*p3.x) / (3*m*(1-m));
 255         s.y = (r.y - mm*mm*(1+m+m)*p0.y - m*m*(1+mm+mm)*p3.y) / (3*m*(1-m));
 256
 257         if (v0.x != 0) {
 258             k3 = (s.y - s.x*v0.y / v0.x) / (m*(v3.y - v3.x*v0.y / v0.x));
 259             k0 = (s.x - m*k3*v3.x) / (mm*v0.x);
 260         } else {
 261             k0 = (s.y - s.x*v3.y / v3.x) / (mm*(v0.y - v0.x*v3.y / v3.x));
 262             k3 = (s.x - mm*k0*v0.x) / (m*v3.x);
 263         }
 264
 265         p1.x = p0.x + k0*v0.x;
 266         p1.y = p0.y + k0*v0.y;
 267         p2.x = p3.x + k3*v3.x;
 268         p2.y = p3.y + k3*v3.y;
 269     }
 270
 271     /* Return the new curve in the original array */
 272     cpml_pair_to_cairo(&p0, curve->org);
 273     cpml_pair_to_cairo(&p1, &curve->data[1]);
 274     cpml_pair_to_cairo(&p2, &curve->data[2]);
 275     cpml_pair_to_cairo(&p3, &curve->data[3]);
 276 }