test/spline-decomposition.c

   1 /*
   2  * Copyright 2008 Chris Wilson
   3  *
   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.
  14  *
  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.
  22  *
  23  * Author: Chris Wilson <chris@chris-wilson.co.uk>
  24  */
  25
  26 #include "cairo-test.h"
  27
  28 typedef struct _point {
  29     double x,y;
  30 } point_t;
  31
  32 typedef struct _knots {
  33     point_t a,b,c,d;
  34 } knots_t;
  35
  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} },
  42 };
  43
  44 #ifdef REFERENCE
  45 static void
  46 _lerp_half (const point_t *a, const point_t *b, point_t *result)
  47 {
  48     result->x = .5 * (a->x + b->x);
  49     result->y = .5 * (a->y + b->y);
  50 }
  51
  52 static void
  53 _de_casteljau (knots_t *k1, knots_t *k2)
  54 {
  55     point_t ab, bc, cd;
  56     point_t abbc, bccd;
  57     point_t final;
  58
  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);
  65
  66     k2->a = final;
  67     k2->b = bccd;
  68     k2->c = cd;
  69     k2->d = k1->d;
  70
  71     k1->b = ab;
  72     k1->c = abbc;
  73     k1->d = final;
  74 }
  75
  76 static double
  77 _spline_error_squared (const knots_t *knots)
  78 {
  79     double bdx, bdy, berr;
  80     double cdx, cdy, cerr;
  81     double dx, dy, v;
  82
  83     /* Intersection point (px):
  84      *      px = p1 + u(p2 - p1)
  85      *      (p - px) ∙ (p2 - p1) = 0
  86      * Thus:
  87      *      u = ((p - p1) ∙ (p2 - p1)) / ∥p2 - p1∥²;
  88      */
  89     bdx = knots->b.x - knots->a.x;
  90     bdy = knots->b.y - knots->a.y;
  91
  92     cdx = knots->c.x - knots->a.x;
  93     cdy = knots->c.y - knots->a.y;
  94
  95     dx = knots->d.x - knots->a.x;
  96     dy = knots->d.y - knots->a.y;
  97     v = dx * dx + dy * dy;
  98     if (v != 0.) {
  99         double u;
 100
 101         u = bdx * dx + bdy * dy;
 102         if (u <= 0) {
 103             /* bdx -= 0;
 104              * bdy -= 0;
 105              */
 106         } else if (u >= v) {
 107             bdx -= dx;
 108             bdy -= dy;
 109         } else {
 110             bdx -= u/v * dx;
 111             bdy -= u/v * dy;
 112         }
 113
 114         u = cdx * dx + cdy * dy;
 115         if (u <= 0) {
 116             /* cdx -= 0;
 117              * cdy -= 0;
 118              */
 119         } else if (u >= v) {
 120             cdx -= dx;
 121             cdy -= dy;
 122         } else {
 123             cdx -= u/v * dx;
 124             cdy -= u/v * dy;
 125         }
 126     }
 127
 128     berr = bdx * bdx + bdy * bdy;
 129     cerr = cdx * cdx + cdy * cdy;
 130     if (berr > cerr)
 131         return berr * v;
 132     else
 133         return cerr * v;
 134 }
 135
 136 static void
 137 _offset_line_to (cairo_t *cr,
 138                  const point_t *p0,
 139                  const point_t *p1,
 140                  const point_t *p2,
 141                  const point_t *p3,
 142                  double offset)
 143 {
 144     double dx, dy, v;
 145
 146     dx = p1->x - p0->x;
 147     dy = p1->y - p0->y;
 148      v = hypot (dx, dy);
 149      if (v == 0) {
 150          dx = p2->x - p0->x;
 151          dy = p2->y - p0->y;
 152          v = hypot (dx, dy);
 153          if (v == 0) {
 154              dx = p3->x - p0->x;
 155              dy = p3->y - p0->y;
 156              v = hypot (dx, dy);
 157          }
 158      }
 159
 160      if (v == 0) {
 161          cairo_line_to (cr, p0->x, p0->y);
 162      } else
 163          cairo_line_to (cr, p0->x - offset * dy / v, p0->y + offset * dx / v);
 164 }
 165
 166 static void
 167 _spline_decompose_into (knots_t *k1,
 168                         double tolerance_squared,
 169                         double offset,
 170                         cairo_t *cr)
 171 {
 172     knots_t k2;
 173
 174     if (_spline_error_squared (k1) < tolerance_squared) {
 175         _offset_line_to (cr, &k1->a, &k1->b, &k1->c, &k1->d, offset);
 176         return;
 177     }
 178
 179     _de_casteljau (k1, &k2);
 180
 181     _spline_decompose_into (k1, tolerance_squared, offset, cr);
 182     _spline_decompose_into (&k2, tolerance_squared, offset, cr);
 183 }
 184
 185 static void
 186 _spline_decompose (const knots_t *knots,
 187                    double tolerance, double offset,
 188                    cairo_t *cr)
 189 {
 190     knots_t k;
 191
 192     k = *knots;
 193     _spline_decompose_into (&k, tolerance * tolerance, offset, cr);
 194
 195     _offset_line_to (cr, &knots->d, &knots->c, &knots->b, &knots->a, -offset);
 196 }
 197
 198 static void
 199 _knots_reverse (knots_t *knots)
 200 {
 201     point_t tmp;
 202
 203     tmp = knots->a;
 204     knots->a = knots->d;
 205     knots->d = tmp;
 206
 207     tmp = knots->b;
 208     knots->b = knots->c;
 209     knots->c = tmp;
 210 }
 211
 212 static void
 213 thick_splines (cairo_t *cr, double offset)
 214 {
 215     knots_t k;
 216
 217     cairo_save (cr);
 218     cairo_translate (cr, 15, 15);
 219
 220     k = knots[0];
 221
 222     cairo_new_path (cr);
 223     _spline_decompose (&k, .1, offset, cr);
 224     _knots_reverse (&k);
 225     _spline_decompose (&k, .1, offset, cr);
 226     cairo_close_path (cr);
 227     cairo_fill (cr);
 228
 229     cairo_translate (cr, 130, 0);
 230
 231     k = knots[1];
 232
 233     cairo_new_path (cr);
 234     _spline_decompose (&k, .1, offset, cr);
 235     _knots_reverse (&k);
 236     _spline_decompose (&k, .1, offset, cr);
 237     cairo_close_path (cr);
 238     cairo_fill (cr);
 239
 240     cairo_translate (cr, 130, 0);
 241
 242     k = knots[2];
 243
 244     cairo_new_path (cr);
 245     _spline_decompose (&k, .1, offset, cr);
 246     _knots_reverse (&k);
 247     _spline_decompose (&k, .1, offset, cr);
 248     cairo_close_path (cr);
 249     cairo_fill (cr);
 250
 251     cairo_translate (cr, -130 - 65, 130);
 252
 253     k = knots[3];
 254
 255     cairo_new_path (cr);
 256     _spline_decompose (&k, .1, offset, cr);
 257     _knots_reverse (&k);
 258     _spline_decompose (&k, .1, offset, cr);
 259     cairo_close_path (cr);
 260     cairo_fill (cr);
 261
 262     cairo_translate (cr, 130, 0);
 263
 264     k = knots[4];
 265
 266     cairo_new_path (cr);
 267     _spline_decompose (&k, .1, offset, cr);
 268     _knots_reverse (&k);
 269     _spline_decompose (&k, .1, offset, cr);
 270     cairo_close_path (cr);
 271     cairo_fill (cr);
 272     cairo_restore (cr);
 273 }
 274
 275 static void
 276 thin_splines (cairo_t *cr)
 277 {
 278     cairo_save (cr);
 279     cairo_translate (cr, 15, 15);
 280
 281     cairo_new_path (cr);
 282     _spline_decompose (&knots[0], .1, 0, cr);
 283     cairo_stroke (cr);
 284
 285     cairo_translate (cr, 130, 0);
 286
 287     cairo_new_path (cr);
 288     _spline_decompose (&knots[1], .1, 0, cr);
 289     cairo_stroke (cr);
 290
 291     cairo_translate (cr, 130, 0);
 292
 293     cairo_new_path (cr);
 294     _spline_decompose (&knots[2], .1, 0, cr);
 295     cairo_stroke (cr);
 296
 297     cairo_translate (cr, -130 - 65, 130);
 298
 299     cairo_new_path (cr);
 300     _spline_decompose (&knots[3], .1, 0, cr);
 301     cairo_stroke (cr);
 302
 303     cairo_translate (cr, 130, 0);
 304
 305     cairo_new_path (cr);
 306     _spline_decompose (&knots[4], .1, 0, cr);
 307     cairo_stroke (cr);
 308     cairo_restore (cr);
 309 }
 310 #endif
 311
 312 static void
 313 draw_bbox (cairo_t *cr, double x0, double y0, double x1, double y1)
 314 {
 315     cairo_rectangle (cr,
 316                      floor (x0) + .5, floor (y0) + .5,
 317                      ceil (x1) - floor (x0), ceil (y1) - floor (y0));
 318     cairo_stroke (cr);
 319 }
 320
 321 static void
 322 stroke_splines (cairo_t *cr)
 323 {
 324     double stroke_x0, stroke_x1, stroke_y0, stroke_y1;
 325     double path_x0, path_x1, path_y0, path_y1;
 326
 327     cairo_save (cr);
 328     cairo_translate (cr, 15, 15);
 329
 330     cairo_new_path (cr);
 331     cairo_move_to (cr,
 332                    knots[0].a.x, knots[0].a.y);
 333     cairo_curve_to (cr,
 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);
 339     cairo_stroke (cr);
 340
 341     cairo_save (cr); {
 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);
 348
 349     cairo_translate (cr, 130, 0);
 350
 351     cairo_new_path (cr);
 352     cairo_move_to (cr,
 353                    knots[1].a.x, knots[1].a.y);
 354     cairo_curve_to (cr,
 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);
 360     cairo_stroke (cr);
 361
 362     cairo_save (cr); {
 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);
 369
 370     cairo_translate (cr, 130, 0);
 371
 372     cairo_new_path (cr);
 373     cairo_move_to (cr,
 374                    knots[2].a.x, knots[2].a.y);
 375     cairo_curve_to (cr,
 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);
 381     cairo_stroke (cr);
 382
 383     cairo_save (cr); {
 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);
 390
 391     cairo_translate (cr, -130 - 65, 130);
 392
 393     cairo_new_path (cr);
 394     cairo_move_to (cr,
 395                    knots[3].a.x, knots[3].a.y);
 396     cairo_curve_to (cr,
 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);
 402     cairo_stroke (cr);
 403
 404     cairo_save (cr); {
 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);
 411
 412     cairo_translate (cr, 130, 0);
 413
 414     cairo_new_path (cr);
 415     cairo_move_to (cr,
 416                    knots[4].a.x, knots[4].a.y);
 417     cairo_curve_to (cr,
 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);
 423     cairo_stroke (cr);
 424
 425     cairo_save (cr); {
 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);
 432
 433     cairo_restore (cr);
 434 }
 435
 436 static cairo_test_status_t
 437 draw (cairo_t *cr, int width, int height)
 438 {
 439     cairo_set_source_rgb (cr, 1, 1, 1);
 440     cairo_paint (cr);
 441
 442 #ifdef REFERENCE
 443     cairo_set_source_rgb (cr, 0, 0, 0);
 444     thick_splines (cr, 5);
 445
 446     cairo_set_source_rgb (cr, 1, 1, 1);
 447     thin_splines (cr);
 448 #endif
 449
 450     /*
 451      * Use a high tolerance to reduce dependence upon algorithm used for
 452      * spline decomposition.
 453      */
 454     cairo_set_tolerance (cr, 0.001);
 455
 456     cairo_set_line_width (cr, 10);
 457     cairo_set_source_rgb (cr, 0, 0, 0);
 458     stroke_splines (cr);
 459     cairo_set_line_width (cr, 2);
 460     cairo_set_source_rgb (cr, 1, 1, 1);
 461     stroke_splines (cr);
 462
 463     return CAIRO_TEST_SUCCESS;
 464 }
 465
 466 CAIRO_TEST (spline_decomposition,
 467             "Tests splines with various inflection points",
 468             "stroke, spline", /* keywords */
 469             NULL, /* requirements */
 470             390, 260,
 471             NULL, draw)