Line data Source code
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., 51 Franklin Street, Suite 500, Boston, MA 02110-1335, 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 : #include "cairo-slope-private.h"
40 :
41 : cairo_bool_t
42 0 : _cairo_spline_init (cairo_spline_t *spline,
43 : cairo_spline_add_point_func_t add_point_func,
44 : void *closure,
45 : const cairo_point_t *a, const cairo_point_t *b,
46 : const cairo_point_t *c, const cairo_point_t *d)
47 : {
48 0 : spline->add_point_func = add_point_func;
49 0 : spline->closure = closure;
50 :
51 0 : spline->knots.a = *a;
52 0 : spline->knots.b = *b;
53 0 : spline->knots.c = *c;
54 0 : spline->knots.d = *d;
55 :
56 0 : if (a->x != b->x || a->y != b->y)
57 0 : _cairo_slope_init (&spline->initial_slope, &spline->knots.a, &spline->knots.b);
58 0 : else if (a->x != c->x || a->y != c->y)
59 0 : _cairo_slope_init (&spline->initial_slope, &spline->knots.a, &spline->knots.c);
60 0 : else if (a->x != d->x || a->y != d->y)
61 0 : _cairo_slope_init (&spline->initial_slope, &spline->knots.a, &spline->knots.d);
62 : else
63 0 : return FALSE;
64 :
65 0 : if (c->x != d->x || c->y != d->y)
66 0 : _cairo_slope_init (&spline->final_slope, &spline->knots.c, &spline->knots.d);
67 0 : else if (b->x != d->x || b->y != d->y)
68 0 : _cairo_slope_init (&spline->final_slope, &spline->knots.b, &spline->knots.d);
69 : else
70 0 : _cairo_slope_init (&spline->final_slope, &spline->knots.a, &spline->knots.d);
71 :
72 0 : return TRUE;
73 : }
74 :
75 : static cairo_status_t
76 0 : _cairo_spline_add_point (cairo_spline_t *spline, cairo_point_t *point)
77 : {
78 : cairo_point_t *prev;
79 :
80 0 : prev = &spline->last_point;
81 0 : if (prev->x == point->x && prev->y == point->y)
82 0 : return CAIRO_STATUS_SUCCESS;
83 :
84 0 : spline->last_point = *point;
85 0 : return spline->add_point_func (spline->closure, point);
86 : }
87 :
88 : static void
89 0 : _lerp_half (const cairo_point_t *a, const cairo_point_t *b, cairo_point_t *result)
90 : {
91 0 : result->x = a->x + ((b->x - a->x) >> 1);
92 0 : result->y = a->y + ((b->y - a->y) >> 1);
93 0 : }
94 :
95 : static void
96 0 : _de_casteljau (cairo_spline_knots_t *s1, cairo_spline_knots_t *s2)
97 : {
98 : cairo_point_t ab, bc, cd;
99 : cairo_point_t abbc, bccd;
100 : cairo_point_t final;
101 :
102 0 : _lerp_half (&s1->a, &s1->b, &ab);
103 0 : _lerp_half (&s1->b, &s1->c, &bc);
104 0 : _lerp_half (&s1->c, &s1->d, &cd);
105 0 : _lerp_half (&ab, &bc, &abbc);
106 0 : _lerp_half (&bc, &cd, &bccd);
107 0 : _lerp_half (&abbc, &bccd, &final);
108 :
109 0 : s2->a = final;
110 0 : s2->b = bccd;
111 0 : s2->c = cd;
112 0 : s2->d = s1->d;
113 :
114 0 : s1->b = ab;
115 0 : s1->c = abbc;
116 0 : s1->d = final;
117 0 : }
118 :
119 : /* Return an upper bound on the error (squared) that could result from
120 : * approximating a spline as a line segment connecting the two endpoints. */
121 : static double
122 0 : _cairo_spline_error_squared (const cairo_spline_knots_t *knots)
123 : {
124 : double bdx, bdy, berr;
125 : double cdx, cdy, cerr;
126 :
127 : /* We are going to compute the distance (squared) between each of the the b
128 : * and c control points and the segment a-b. The maximum of these two
129 : * distances will be our approximation error. */
130 :
131 0 : bdx = _cairo_fixed_to_double (knots->b.x - knots->a.x);
132 0 : bdy = _cairo_fixed_to_double (knots->b.y - knots->a.y);
133 :
134 0 : cdx = _cairo_fixed_to_double (knots->c.x - knots->a.x);
135 0 : cdy = _cairo_fixed_to_double (knots->c.y - knots->a.y);
136 :
137 0 : if (knots->a.x != knots->d.x || knots->a.y != knots->d.y) {
138 : /* Intersection point (px):
139 : * px = p1 + u(p2 - p1)
140 : * (p - px) ∙ (p2 - p1) = 0
141 : * Thus:
142 : * u = ((p - p1) ∙ (p2 - p1)) / ∥p2 - p1∥²;
143 : */
144 :
145 : double dx, dy, u, v;
146 :
147 0 : dx = _cairo_fixed_to_double (knots->d.x - knots->a.x);
148 0 : dy = _cairo_fixed_to_double (knots->d.y - knots->a.y);
149 0 : v = dx * dx + dy * dy;
150 :
151 0 : u = bdx * dx + bdy * dy;
152 0 : if (u <= 0) {
153 : /* bdx -= 0;
154 : * bdy -= 0;
155 : */
156 0 : } else if (u >= v) {
157 0 : bdx -= dx;
158 0 : bdy -= dy;
159 : } else {
160 0 : bdx -= u/v * dx;
161 0 : bdy -= u/v * dy;
162 : }
163 :
164 0 : u = cdx * dx + cdy * dy;
165 0 : if (u <= 0) {
166 : /* cdx -= 0;
167 : * cdy -= 0;
168 : */
169 0 : } else if (u >= v) {
170 0 : cdx -= dx;
171 0 : cdy -= dy;
172 : } else {
173 0 : cdx -= u/v * dx;
174 0 : cdy -= u/v * dy;
175 : }
176 : }
177 :
178 0 : berr = bdx * bdx + bdy * bdy;
179 0 : cerr = cdx * cdx + cdy * cdy;
180 0 : if (berr > cerr)
181 0 : return berr;
182 : else
183 0 : return cerr;
184 : }
185 :
186 : static cairo_status_t
187 0 : _cairo_spline_decompose_into (cairo_spline_knots_t *s1, double tolerance_squared, cairo_spline_t *result)
188 : {
189 : cairo_spline_knots_t s2;
190 : cairo_status_t status;
191 :
192 0 : if (_cairo_spline_error_squared (s1) < tolerance_squared) {
193 0 : return _cairo_spline_add_point (result, &s1->a);
194 : }
195 :
196 0 : _de_casteljau (s1, &s2);
197 :
198 0 : status = _cairo_spline_decompose_into (s1, tolerance_squared, result);
199 0 : if (unlikely (status)) {
200 0 : return status;
201 : }
202 :
203 0 : status = _cairo_spline_decompose_into (&s2, tolerance_squared, result);
204 0 : return status;
205 : }
206 :
207 : cairo_status_t
208 0 : _cairo_spline_decompose (cairo_spline_t *spline, double tolerance)
209 : {
210 : cairo_spline_knots_t s1;
211 : cairo_status_t status;
212 :
213 0 : s1 = spline->knots;
214 0 : spline->last_point = s1.a;
215 0 : status = _cairo_spline_decompose_into (&s1, tolerance * tolerance, spline);
216 0 : if (unlikely (status))
217 0 : return status;
218 :
219 0 : return _cairo_spline_add_point (spline, &spline->knots.d);
220 : }
221 :
222 : /* Note: this function is only good for computing bounds in device space. */
223 : cairo_status_t
224 0 : _cairo_spline_bound (cairo_spline_add_point_func_t add_point_func,
225 : void *closure,
226 : const cairo_point_t *p0, const cairo_point_t *p1,
227 : const cairo_point_t *p2, const cairo_point_t *p3)
228 : {
229 : double x0, x1, x2, x3;
230 : double y0, y1, y2, y3;
231 : double a, b, c;
232 : double t[4];
233 0 : int t_num = 0, i;
234 : cairo_status_t status;
235 :
236 0 : x0 = _cairo_fixed_to_double (p0->x);
237 0 : y0 = _cairo_fixed_to_double (p0->y);
238 0 : x1 = _cairo_fixed_to_double (p1->x);
239 0 : y1 = _cairo_fixed_to_double (p1->y);
240 0 : x2 = _cairo_fixed_to_double (p2->x);
241 0 : y2 = _cairo_fixed_to_double (p2->y);
242 0 : x3 = _cairo_fixed_to_double (p3->x);
243 0 : y3 = _cairo_fixed_to_double (p3->y);
244 :
245 : /* The spline can be written as a polynomial of the four points:
246 : *
247 : * (1-t)³p0 + 3t(1-t)²p1 + 3t²(1-t)p2 + t³p3
248 : *
249 : * for 0≤t≤1. Now, the X and Y components of the spline follow the
250 : * same polynomial but with x and y replaced for p. To find the
251 : * bounds of the spline, we just need to find the X and Y bounds.
252 : * To find the bound, we take the derivative and equal it to zero,
253 : * and solve to find the t's that give the extreme points.
254 : *
255 : * Here is the derivative of the curve, sorted on t:
256 : *
257 : * 3t²(-p0+3p1-3p2+p3) + 2t(3p0-6p1+3p2) -3p0+3p1
258 : *
259 : * Let:
260 : *
261 : * a = -p0+3p1-3p2+p3
262 : * b = p0-2p1+p2
263 : * c = -p0+p1
264 : *
265 : * Gives:
266 : *
267 : * a.t² + 2b.t + c = 0
268 : *
269 : * With:
270 : *
271 : * delta = b*b - a*c
272 : *
273 : * the extreme points are at -c/2b if a is zero, at (-b±√delta)/a if
274 : * delta is positive, and at -b/a if delta is zero.
275 : */
276 :
277 : #define ADD(t0) \
278 : { \
279 : double _t0 = (t0); \
280 : if (0 < _t0 && _t0 < 1) \
281 : t[t_num++] = _t0; \
282 : }
283 :
284 : #define FIND_EXTREMES(a,b,c) \
285 : { \
286 : if (a == 0) { \
287 : if (b != 0) \
288 : ADD (-c / (2*b)); \
289 : } else { \
290 : double b2 = b * b; \
291 : double delta = b2 - a * c; \
292 : if (delta > 0) { \
293 : cairo_bool_t feasible; \
294 : double _2ab = 2 * a * b; \
295 : /* We are only interested in solutions t that satisfy 0<t<1 \
296 : * here. We do some checks to avoid sqrt if the solutions \
297 : * are not in that range. The checks can be derived from: \
298 : * \
299 : * 0 < (-b±√delta)/a < 1 \
300 : */ \
301 : if (_2ab >= 0) \
302 : feasible = delta > b2 && delta < a*a + b2 + _2ab; \
303 : else if (-b / a >= 1) \
304 : feasible = delta < b2 && delta > a*a + b2 + _2ab; \
305 : else \
306 : feasible = delta < b2 || delta < a*a + b2 + _2ab; \
307 : \
308 : if (unlikely (feasible)) { \
309 : double sqrt_delta = sqrt (delta); \
310 : ADD ((-b - sqrt_delta) / a); \
311 : ADD ((-b + sqrt_delta) / a); \
312 : } \
313 : } else if (delta == 0) { \
314 : ADD (-b / a); \
315 : } \
316 : } \
317 : }
318 :
319 : /* Find X extremes */
320 0 : a = -x0 + 3*x1 - 3*x2 + x3;
321 0 : b = x0 - 2*x1 + x2;
322 0 : c = -x0 + x1;
323 0 : FIND_EXTREMES (a, b, c);
324 :
325 : /* Find Y extremes */
326 0 : a = -y0 + 3*y1 - 3*y2 + y3;
327 0 : b = y0 - 2*y1 + y2;
328 0 : c = -y0 + y1;
329 0 : FIND_EXTREMES (a, b, c);
330 :
331 0 : status = add_point_func (closure, p0);
332 0 : if (unlikely (status))
333 0 : return status;
334 :
335 0 : for (i = 0; i < t_num; i++) {
336 : cairo_point_t p;
337 : double x, y;
338 : double t_1_0, t_0_1;
339 : double t_2_0, t_0_2;
340 : double t_3_0, t_2_1_3, t_1_2_3, t_0_3;
341 :
342 0 : t_1_0 = t[i]; /* t */
343 0 : t_0_1 = 1 - t_1_0; /* (1 - t) */
344 :
345 0 : t_2_0 = t_1_0 * t_1_0; /* t * t */
346 0 : t_0_2 = t_0_1 * t_0_1; /* (1 - t) * (1 - t) */
347 :
348 0 : t_3_0 = t_2_0 * t_1_0; /* t * t * t */
349 0 : t_2_1_3 = t_2_0 * t_0_1 * 3; /* t * t * (1 - t) * 3 */
350 0 : t_1_2_3 = t_1_0 * t_0_2 * 3; /* t * (1 - t) * (1 - t) * 3 */
351 0 : t_0_3 = t_0_1 * t_0_2; /* (1 - t) * (1 - t) * (1 - t) */
352 :
353 : /* Bezier polynomial */
354 0 : x = x0 * t_0_3
355 0 : + x1 * t_1_2_3
356 0 : + x2 * t_2_1_3
357 0 : + x3 * t_3_0;
358 0 : y = y0 * t_0_3
359 0 : + y1 * t_1_2_3
360 0 : + y2 * t_2_1_3
361 0 : + y3 * t_3_0;
362 :
363 0 : p.x = _cairo_fixed_from_double (x);
364 0 : p.y = _cairo_fixed_from_double (y);
365 0 : status = add_point_func (closure, &p);
366 0 : if (unlikely (status))
367 0 : return status;
368 : }
369 :
370 0 : return add_point_func (closure, p3);
371 : }
|
