2 * Copyright 2008 Chris Wilson
4 * Permission to use, copy, modify, distribute, and sell this software
5 * and its documentation for any purpose is hereby granted without
6 * fee, provided that the above copyright notice appear in all copies
7 * and that both that copyright notice and this permission notice
8 * appear in supporting documentation, and that the name of
9 * Chris Wilson not be used in advertising or publicity pertaining to
10 * distribution of the software without specific, written prior
11 * permission. Chris Wilson makes no representations about the
12 * suitability of this software for any purpose. It is provided "as
13 * is" without express or implied warranty.
15 * CHRIS WILSON DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS
16 * SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND
17 * FITNESS, IN NO EVENT SHALL CHRIS WILSON BE LIABLE FOR ANY SPECIAL,
18 * INDIRECT OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER
19 * RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION
20 * OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR
21 * IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
23 * Author: Chris Wilson <chris@chris-wilson.co.uk>
26 #include "cairo-test.h"
28 typedef struct _point {
32 typedef struct _knots {
36 static knots_t knots[5] = {
37 { {0, 0}, {0, 100}, {100, 100}, {100, 0} },
38 { {0, 0}, {75, 100}, {25, 100}, {100, 0} },
39 { {0, 0}, {100, 100}, {0, 100}, {100, 0} },
40 { {0, 0}, {150, 100}, {-50, 100}, {100, 0} },
41 { {0, 0}, {100, 200}, {0, -100}, {100, 100} },
46 _lerp_half (const point_t *a, const point_t *b, point_t *result)
48 result->x = .5 * (a->x + b->x);
49 result->y = .5 * (a->y + b->y);
53 _de_casteljau (knots_t *k1, knots_t *k2)
59 _lerp_half (&k1->a, &k1->b, &ab);
60 _lerp_half (&k1->b, &k1->c, &bc);
61 _lerp_half (&k1->c, &k1->d, &cd);
62 _lerp_half (&ab, &bc, &abbc);
63 _lerp_half (&bc, &cd, &bccd);
64 _lerp_half (&abbc, &bccd, &final);
77 _spline_error_squared (const knots_t *knots)
79 double bdx, bdy, berr;
80 double cdx, cdy, cerr;
83 /* Intersection point (px):
84 * px = p1 + u(p2 - p1)
85 * (p - px) ∙ (p2 - p1) = 0
87 * u = ((p - p1) ∙ (p2 - p1)) / ∥p2 - p1∥²;
89 bdx = knots->b.x - knots->a.x;
90 bdy = knots->b.y - knots->a.y;
92 cdx = knots->c.x - knots->a.x;
93 cdy = knots->c.y - knots->a.y;
95 dx = knots->d.x - knots->a.x;
96 dy = knots->d.y - knots->a.y;
97 v = dx * dx + dy * dy;
101 u = bdx * dx + bdy * dy;
114 u = cdx * dx + cdy * dy;
128 berr = bdx * bdx + bdy * bdy;
129 cerr = cdx * cdx + cdy * cdy;
137 _offset_line_to (cairo_t *cr,
161 cairo_line_to (cr, p0->x, p0->y);
163 cairo_line_to (cr, p0->x - offset * dy / v, p0->y + offset * dx / v);
167 _spline_decompose_into (knots_t *k1,
168 double tolerance_squared,
174 if (_spline_error_squared (k1) < tolerance_squared) {
175 _offset_line_to (cr, &k1->a, &k1->b, &k1->c, &k1->d, offset);
179 _de_casteljau (k1, &k2);
181 _spline_decompose_into (k1, tolerance_squared, offset, cr);
182 _spline_decompose_into (&k2, tolerance_squared, offset, cr);
186 _spline_decompose (const knots_t *knots,
187 double tolerance, double offset,
193 _spline_decompose_into (&k, tolerance * tolerance, offset, cr);
195 _offset_line_to (cr, &knots->d, &knots->c, &knots->b, &knots->a, -offset);
199 _knots_reverse (knots_t *knots)
213 thick_splines (cairo_t *cr, double offset)
218 cairo_translate (cr, 15, 15);
223 _spline_decompose (&k, .1, offset, cr);
225 _spline_decompose (&k, .1, offset, cr);
226 cairo_close_path (cr);
229 cairo_translate (cr, 130, 0);
234 _spline_decompose (&k, .1, offset, cr);
236 _spline_decompose (&k, .1, offset, cr);
237 cairo_close_path (cr);
240 cairo_translate (cr, 130, 0);
245 _spline_decompose (&k, .1, offset, cr);
247 _spline_decompose (&k, .1, offset, cr);
248 cairo_close_path (cr);
251 cairo_translate (cr, -130 - 65, 130);
256 _spline_decompose (&k, .1, offset, cr);
258 _spline_decompose (&k, .1, offset, cr);
259 cairo_close_path (cr);
262 cairo_translate (cr, 130, 0);
267 _spline_decompose (&k, .1, offset, cr);
269 _spline_decompose (&k, .1, offset, cr);
270 cairo_close_path (cr);
276 thin_splines (cairo_t *cr)
279 cairo_translate (cr, 15, 15);
282 _spline_decompose (&knots[0], .1, 0, cr);
285 cairo_translate (cr, 130, 0);
288 _spline_decompose (&knots[1], .1, 0, cr);
291 cairo_translate (cr, 130, 0);
294 _spline_decompose (&knots[2], .1, 0, cr);
297 cairo_translate (cr, -130 - 65, 130);
300 _spline_decompose (&knots[3], .1, 0, cr);
303 cairo_translate (cr, 130, 0);
306 _spline_decompose (&knots[4], .1, 0, cr);
313 draw_bbox (cairo_t *cr, double x0, double y0, double x1, double y1)
316 floor (x0) + .5, floor (y0) + .5,
317 ceil (x1) - floor (x0), ceil (y1) - floor (y0));
322 stroke_splines (cairo_t *cr)
324 double stroke_x0, stroke_x1, stroke_y0, stroke_y1;
325 double path_x0, path_x1, path_y0, path_y1;
328 cairo_translate (cr, 15, 15);
332 knots[0].a.x, knots[0].a.y);
334 knots[0].b.x, knots[0].b.y,
335 knots[0].c.x, knots[0].c.y,
336 knots[0].d.x, knots[0].d.y);
337 cairo_stroke_extents (cr, &stroke_x0, &stroke_y0, &stroke_x1, &stroke_y1);
338 cairo_path_extents (cr, &path_x0, &path_y0, &path_x1, &path_y1);
342 cairo_set_line_width (cr, 1);
343 cairo_set_source_rgb (cr, 1, 0, 0);
344 draw_bbox (cr, stroke_x0, stroke_y0, stroke_x1, stroke_y1);
345 cairo_set_source_rgb (cr, 0, 0, 1);
346 draw_bbox (cr, path_x0, path_y0, path_x1, path_y1);
347 } cairo_restore (cr);
349 cairo_translate (cr, 130, 0);
353 knots[1].a.x, knots[1].a.y);
355 knots[1].b.x, knots[1].b.y,
356 knots[1].c.x, knots[1].c.y,
357 knots[1].d.x, knots[1].d.y);
358 cairo_stroke_extents (cr, &stroke_x0, &stroke_y0, &stroke_x1, &stroke_y1);
359 cairo_path_extents (cr, &path_x0, &path_y0, &path_x1, &path_y1);
363 cairo_set_line_width (cr, 1);
364 cairo_set_source_rgb (cr, 1, 0, 0);
365 draw_bbox (cr, stroke_x0, stroke_y0, stroke_x1, stroke_y1);
366 cairo_set_source_rgb (cr, 0, 0, 1);
367 draw_bbox (cr, path_x0, path_y0, path_x1, path_y1);
368 } cairo_restore (cr);
370 cairo_translate (cr, 130, 0);
374 knots[2].a.x, knots[2].a.y);
376 knots[2].b.x, knots[2].b.y,
377 knots[2].c.x, knots[2].c.y,
378 knots[2].d.x, knots[2].d.y);
379 cairo_stroke_extents (cr, &stroke_x0, &stroke_y0, &stroke_x1, &stroke_y1);
380 cairo_path_extents (cr, &path_x0, &path_y0, &path_x1, &path_y1);
384 cairo_set_line_width (cr, 1);
385 cairo_set_source_rgb (cr, 1, 0, 0);
386 draw_bbox (cr, stroke_x0, stroke_y0, stroke_x1, stroke_y1);
387 cairo_set_source_rgb (cr, 0, 0, 1);
388 draw_bbox (cr, path_x0, path_y0, path_x1, path_y1);
389 } cairo_restore (cr);
391 cairo_translate (cr, -130 - 65, 130);
395 knots[3].a.x, knots[3].a.y);
397 knots[3].b.x, knots[3].b.y,
398 knots[3].c.x, knots[3].c.y,
399 knots[3].d.x, knots[3].d.y);
400 cairo_stroke_extents (cr, &stroke_x0, &stroke_y0, &stroke_x1, &stroke_y1);
401 cairo_path_extents (cr, &path_x0, &path_y0, &path_x1, &path_y1);
405 cairo_set_line_width (cr, 1);
406 cairo_set_source_rgb (cr, 1, 0, 0);
407 draw_bbox (cr, stroke_x0, stroke_y0, stroke_x1, stroke_y1);
408 cairo_set_source_rgb (cr, 0, 0, 1);
409 draw_bbox (cr, path_x0, path_y0, path_x1, path_y1);
410 } cairo_restore (cr);
412 cairo_translate (cr, 130, 0);
416 knots[4].a.x, knots[4].a.y);
418 knots[4].b.x, knots[4].b.y,
419 knots[4].c.x, knots[4].c.y,
420 knots[4].d.x, knots[4].d.y);
421 cairo_stroke_extents (cr, &stroke_x0, &stroke_y0, &stroke_x1, &stroke_y1);
422 cairo_path_extents (cr, &path_x0, &path_y0, &path_x1, &path_y1);
426 cairo_set_line_width (cr, 1);
427 cairo_set_source_rgb (cr, 1, 0, 0);
428 draw_bbox (cr, stroke_x0, stroke_y0, stroke_x1, stroke_y1);
429 cairo_set_source_rgb (cr, 0, 0, 1);
430 draw_bbox (cr, path_x0, path_y0, path_x1, path_y1);
431 } cairo_restore (cr);
436 static cairo_test_status_t
437 draw (cairo_t *cr, int width, int height)
439 cairo_set_source_rgb (cr, 1, 1, 1);
443 cairo_set_source_rgb (cr, 0, 0, 0);
444 thick_splines (cr, 5);
446 cairo_set_source_rgb (cr, 1, 1, 1);
451 * Use a high tolerance to reduce dependence upon algorithm used for
452 * spline decomposition.
454 cairo_set_tolerance (cr, 0.001);
456 cairo_set_line_width (cr, 10);
457 cairo_set_source_rgb (cr, 0, 0, 0);
459 cairo_set_line_width (cr, 2);
460 cairo_set_source_rgb (cr, 1, 1, 1);
463 return CAIRO_TEST_SUCCESS;
466 CAIRO_TEST (spline_decomposition,
467 "Tests splines with various inflection points",
468 "stroke, spline", /* keywords */
469 NULL, /* requirements */