1 /* CPML - Cairo Path Manipulation Library
2 * Copyright (C) 2008,2009,2010 Nicola Fontana <ntd at entidi.it>
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.
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.
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.
23 * @Section_Id:CpmlCurve
25 * @short_description: Bézier cubic curve primitive management
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.
35 * <listitem>the get_length() method must be implemented;</listitem>
36 * <listitem>actually the put_extents() method is implemented by computing
37 * the bounding box of the control polygon and this will likely
38 * include some empty space: there is room for improvements;</listitem>
39 * <listitem>the put_pair_at() method must be implemented;</listitem>
40 * <listitem>the put_vector_at() method must be implemented;</listitem>
41 * <listitem>the get_closest_pos() method must be implemented;</listitem>
42 * <listitem>the put_intersections() method must be implemented;</listitem>
43 * <listitem>by default, the offset curve is calculated by using the point
44 * at t=0.5 as reference: use a better candidate;</listitem>
45 * <listitem>in the offset() implementation, when the equations are
46 * inconsistent, the alternative approach performs very bad
47 * if <varname>v0</varname> and <varname>v3</varname> are
48 * opposite or staggered.</listitem>
52 * <refsect2 id="offset">
53 * <title>Offseting algorithm</title>
55 * Given a cubic Bézier primitive, it must be found the approximated
56 * Bézier curve parallel to the original one at a specific distance
57 * (the so called "offset curve"). The four points needed to build
58 * the new curve must be returned.
60 * To solve the offset problem, a custom algorithm is used. First, the
61 * resulting curve MUST have the same slope at the start and end point.
62 * These constraints are not sufficient to resolve the system, so I let
63 * the curve pass thought a given point (pm, known and got from the
64 * original curve) at a given time (m, now hardcoded to 0.5).
66 * Firstly, I define some useful variables:
69 * v0 = unitvector(p[1]-p[0]) * offset;
70 * v3 = unitvector(p[3]-p[2]) * offset;
71 * p0 = p[0] + normal v0;
72 * p3 = p[3] + normal v3.
75 * Now I want the curve to have the specified slopes at the start
76 * and end point. Forcing the same slope at the start point means:
82 * where k0 is an arbitrary factor. Decomposing for x and y components:
85 * p1.x = p0.x + k0 v0.x;
86 * p1.y = p0.y + k0 v0.y.
89 * Doing the same for the end point gives:
92 * p2.x = p3.x + k3 v3.x;
93 * p2.y = p3.y + k3 v3.y.
96 * Now I interpolate the curve by forcing it to pass throught pm
97 * when "time" is m, where 0 < m < 1. The cubic Bézier function is:
100 * C(t) = (1-t)³p0 + 3t(1-t)²p1 + 3t²(1-t)p2 + t³p3.
103 * and forcing t=m and C(t) = pm:
106 * pm = (1-m)³p0 + 3m(1-m)²p1 + 3m²(1-m)p2 + m³p3.
108 * (1-m) p1 + m p2 = (pm - (1-m)³p0 - m³p3) / (3m (1-m)).
111 * So the final system is:
114 * p1.x = p0.x + k0 v0.x;
115 * p1.y = p0.y + k0 v0.y;
116 * p2.x = p3.x + k3 v3.x;
117 * p2.y = p3.y + k3 v3.y;
118 * (1-m) p1.x + m p2.x = (pm.x - (1-m)³p0.x - m³p3.x) / (3m (1-m));
119 * (1-m) p1.y + m p2.y = (pm.y - (1-m)³p0.y - m³p3.y) / (3m (1-m)).
122 * Substituting and resolving for k0 and k3:
125 * (1-m) k0 v0.x + m k3 v3.x =
126 * (pm.x - (1-m)³p0.x - m³p3.x) / (3m (1-m)) - (1-m) p0.x - m p3.x;
127 * (1-m) k0 v0.y + m k3 v3.y =
128 * (pm.y - (1-m)³p0.y - m³p3.y) / (3m (1-m)) - (1-m) p0.y - m p3.y.
130 * (1-m) k0 v0.x + m k3 v3.x =
131 * (pm.x - (1-m)²(1+2m) p0.x - m²(3-2m) p3.x) / (3m (1-m));
132 * (1-m) k0 v0.y + m k3 v3.y =
133 * (pm.y - (1-m)²(1+2m) p0.y - m²(3-2m) p3.y) / (3m (1-m)).
139 * pk = (pm - (1-m)²(1+2m) p0 - m²(3-2m) p3) / (3m (1-m)).
142 * gives the following system:
145 * (1-m) k0 v0.x + m k3 v3.x = pk.x;
146 * (1-m) k0 v0.y + m k3 v3.y = pk.y.
149 * Now I should avoid division by 0 troubles. If either v0.x and v3.x
150 * are 0, the first equation will be inconsistent. More in general the
151 * v0.x*v3.y = v3.x*v3.y condition should be avoided. This is the first
152 * case to check, in which case an alternative approach is used. In the
153 * other cases the above system can be used.
155 * If v0.x != 0 I can resolve for k0 and then find k3:
158 * k0 = (pk.x - m k3 v3.x) / ((1-m) v0.x);
159 * (pk.x - m k3 v3.x) v0.y / v0.x + m k3 v3.y = pk.y.
161 * k0 = (pk.x - m k3 v3.x) / ((1-m) v0.x);
162 * k3 m (v3.y - v3.x v0.y / v0.x) = pk.y - pk.x v0.y / v0.x.
164 * k3 = (pk.y - pk.x v0.y / v0.x) / (m (v3.y - v3.x v0.y / v0.x));
165 * k0 = (pk.x - m k3 v3.x) / ((1-m) v0.x).
168 * If v3.x != 0 I can resolve for k3 and then find k0:
171 * k3 = (pk.x - (1-m) k0 v0.x) / (m v3.x);
172 * (1-m) k0 v0.y + (pk.x - (1-m) k0 v0.x) v3.y / v3.x = pk.y.
174 * k3 = (pk.x - (1-m) k0 v0.x) / (m v3.x);
175 * k0 (1-m) (v0.y - k0 v0.x v3.y / v3.x) = pk.y - pk.x v3.y / v3.x.
177 * k0 = (pk.y - pk.x v3.y / v3.x) / ((1-m) (v0.y - v0.x v3.y / v3.x));
178 * k3 = (pk.x - (1-m) k0 v0.x) / (m v3.x).
188 * The type code used to identify "curve-to" primitives.
189 * It is equivalent to the %CAIRO_PATH_CURVE_TO cairo constant.
193 #include "cpml-internal.h"
194 #include "cpml-extents.h"
195 #include "cpml-segment.h"
196 #include "cpml-primitive.h"
197 #include "cpml-primitive-private.h"
198 #include "cpml-curve.h"
201 static void put_extents (const CpmlPrimitive
*curve
,
202 CpmlExtents
*extents
);
203 static void offset (CpmlPrimitive
*curve
,
207 const _CpmlPrimitiveClass
*
208 _cpml_curve_get_class(void)
210 static _CpmlPrimitiveClass
*p_class
= NULL
;
212 if (p_class
== NULL
) {
213 static _CpmlPrimitiveClass class_data
= {
224 p_class
= &class_data
;
232 * cpml_curve_put_pair_at_time:
233 * @curve: the #CpmlPrimitive curve data
234 * @t: the "time" value
235 * @pair: the destination pair
237 * Given the @curve Bézier cubic, finds the coordinates at time @t
238 * (where 0 is the start and 1 is the end) and stores the result
239 * in @pair. Keep in mind @t is not homogeneous, so 0.5 does not
240 * necessarily means the mid point.
243 cpml_curve_put_pair_at_time(const CpmlPrimitive
*curve
, double t
,
246 cairo_path_data_t
*p1
, *p2
, *p3
, *p4
;
247 double t_2
, t_3
, t1
, t1_2
, t1_3
;
249 p1
= cpml_primitive_get_point(curve
, 0);
250 p2
= cpml_primitive_get_point(curve
, 1);
251 p3
= cpml_primitive_get_point(curve
, 2);
252 p4
= cpml_primitive_get_point(curve
, 3);
260 pair
->x
= t1_3
* p1
->point
.x
+ 3 * t1_2
* t
* p2
->point
.x
261 + 3 * t1
* t_2
* p3
->point
.x
+ t_3
* p4
->point
.x
;
262 pair
->y
= t1_3
* p1
->point
.y
+ 3 * t1_2
* t
* p2
->point
.y
263 + 3 * t1
* t_2
* p3
->point
.y
+ t_3
* p4
->point
.y
;
267 * cpml_curve_put_vector_at_time:
268 * @curve: the #CpmlPrimitive curve data
269 * @t: the "time" value
270 * @vector: the destination vector
272 * Given the @curve Bézier cubic, finds the slope at time @t
273 * (where 0 is the start and 1 is the end) and stores the result
274 * in @vector. Keep in mind @t is not homogeneous, so 0.5
275 * does not necessarily means the mid point.
278 cpml_curve_put_vector_at_time(const CpmlPrimitive
*curve
,
279 double t
, CpmlVector
*vector
)
281 cairo_path_data_t
*p1
, *p2
, *p3
, *p4
;
282 CpmlPair p21
, p32
, p43
;
283 double t1
, t1_2
, t_2
;
285 p1
= cpml_primitive_get_point(curve
, 0);
286 p2
= cpml_primitive_get_point(curve
, 1);
287 p3
= cpml_primitive_get_point(curve
, 2);
288 p4
= cpml_primitive_get_point(curve
, 3);
290 p21
.x
= p2
->point
.x
- p1
->point
.x
;
291 p21
.y
= p2
->point
.y
- p1
->point
.y
;
292 p32
.x
= p3
->point
.x
- p2
->point
.x
;
293 p32
.y
= p3
->point
.y
- p2
->point
.y
;
294 p43
.x
= p4
->point
.x
- p3
->point
.x
;
295 p43
.y
= p4
->point
.y
- p3
->point
.y
;
301 vector
->x
= 3 * t1_2
* p21
.x
+ 6 * t1
* t
* p32
.x
+ 3 * t_2
* p43
.x
;
302 vector
->y
= 3 * t1_2
* p21
.y
+ 6 * t1
* t
* p32
.y
+ 3 * t_2
* p43
.y
;
307 put_extents(const CpmlPrimitive
*curve
, CpmlExtents
*extents
)
309 CpmlPair p1
, p2
, p3
, p4
;
311 extents
->is_defined
= 0;
313 cpml_pair_from_cairo(&p1
, cpml_primitive_get_point(curve
, 0));
314 cpml_pair_from_cairo(&p2
, cpml_primitive_get_point(curve
, 1));
315 cpml_pair_from_cairo(&p3
, cpml_primitive_get_point(curve
, 2));
316 cpml_pair_from_cairo(&p4
, cpml_primitive_get_point(curve
, 3));
318 cpml_extents_pair_add(extents
, &p1
);
319 cpml_extents_pair_add(extents
, &p2
);
320 cpml_extents_pair_add(extents
, &p3
);
321 cpml_extents_pair_add(extents
, &p4
);
325 offset(CpmlPrimitive
*curve
, double offset
)
328 CpmlVector v0
, v3
, vm
, vtmp
;
329 CpmlPair p0
, p1
, p2
, p3
, pm
;
334 /* Firstly, convert the curve points from cairo format to cpml format
335 * and store them (temporary) in p0..p3 */
336 cpml_pair_from_cairo(&p0
, curve
->org
);
337 cpml_pair_from_cairo(&p1
, &curve
->data
[1]);
338 cpml_pair_from_cairo(&p2
, &curve
->data
[2]);
339 cpml_pair_from_cairo(&p3
, &curve
->data
[3]);
349 /* pm = point in C(m) offseted the requested @offset distance */
350 cpml_curve_put_vector_at_time(curve
, m
, &vm
);
351 cpml_vector_set_length(&vm
, offset
);
352 cpml_vector_normal(&vm
);
353 cpml_curve_put_pair_at_time(curve
, m
, &pm
);
357 /* p0 = p0 + normal of v0 of @offset magnitude (exact value) */
358 cpml_pair_copy(&vtmp
, &v0
);
359 cpml_vector_set_length(&vtmp
, offset
);
360 cpml_vector_normal(&vtmp
);
364 /* p3 = p3 + normal of v3 of @offset magnitude, as done for p0 */
365 cpml_pair_copy(&vtmp
, &v3
);
366 cpml_vector_set_length(&vtmp
, offset
);
367 cpml_vector_normal(&vtmp
);
371 if (v0
.x
*v3
.y
== v3
.x
*v0
.y
) {
372 /* Inconsistent equations: use the alternative approach */
373 p1
.x
= p0
.x
+ v0
.x
+ vm
.x
* 4/3;
374 p1
.y
= p0
.y
+ v0
.y
+ vm
.y
* 4/3;
375 p2
.x
= p3
.x
- v3
.x
+ vm
.x
* 4/3;
376 p2
.y
= p3
.y
- v3
.y
+ vm
.y
* 4/3;
381 pk
.x
= (pm
.x
- mm
*mm
*(1+m
+m
)*p0
.x
- m
*m
*(1+mm
+mm
)*p3
.x
) / (3*m
*(1-m
));
382 pk
.y
= (pm
.y
- mm
*mm
*(1+m
+m
)*p0
.y
- m
*m
*(1+mm
+mm
)*p3
.y
) / (3*m
*(1-m
));
385 k3
= (pk
.y
- pk
.x
*v0
.y
/ v0
.x
) / (m
*(v3
.y
- v3
.x
*v0
.y
/ v0
.x
));
386 k0
= (pk
.x
- m
*k3
*v3
.x
) / (mm
*v0
.x
);
388 k0
= (pk
.y
- pk
.x
*v3
.y
/ v3
.x
) / (mm
*(v0
.y
- v0
.x
*v3
.y
/ v3
.x
));
389 k3
= (pk
.x
- mm
*k0
*v0
.x
) / (m
*v3
.x
);
392 p1
.x
= p0
.x
+ k0
*v0
.x
;
393 p1
.y
= p0
.y
+ k0
*v0
.y
;
394 p2
.x
= p3
.x
+ k3
*v3
.x
;
395 p2
.y
= p3
.y
+ k3
*v3
.y
;
398 /* Return the new curve in the original array */
399 cpml_pair_to_cairo(&p0
, curve
->org
);
400 cpml_pair_to_cairo(&p1
, &curve
->data
[1]);
401 cpml_pair_to_cairo(&p2
, &curve
->data
[2]);
402 cpml_pair_to_cairo(&p3
, &curve
->data
[3]);