cairo/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 static cairo_test_draw_function_t draw;
  29
  30 static const cairo_test_t test = {
  31     "spline-decomposition",
  32     "Tests splines with various inflection points",
  33     390, 260,
  34     draw
  35 };
  36
  37 typedef struct _point {
  38     double x,y;
  39 } point_t;
  40
  41 typedef struct _knots {
  42     point_t a,b,c,d;
  43 } knots_t;
  44
  45 static knots_t knots[5] = {
  46     { {0, 0}, {0, 100}, {100, 100}, {100, 0} },
  47     { {0, 0}, {75, 100}, {25, 100}, {100, 0} },
  48     { {0, 0}, {100, 100}, {0, 100}, {100, 0} },
  49     { {0, 0}, {150, 100}, {-50, 100}, {100, 0} },
  50     { {0, 0}, {100, 200}, {0, -100}, {100, 100} },
  51 };
  52
  53 #ifdef REFERENCE
  54 static void
  55 _lerp_half (const point_t *a, const point_t *b, point_t *result)
  56 {
  57     result->x = .5 * (a->x + b->x);
  58     result->y = .5 * (a->y + b->y);
  59 }
  60
  61 static void
  62 _de_casteljau (knots_t *k1, knots_t *k2)
  63 {
  64     point_t ab, bc, cd;
  65     point_t abbc, bccd;
  66     point_t final;
  67
  68     _lerp_half (&k1->a, &k1->b, &ab);
  69     _lerp_half (&k1->b, &k1->c, &bc);
  70     _lerp_half (&k1->c, &k1->d, &cd);
  71     _lerp_half (&ab, &bc, &abbc);
  72     _lerp_half (&bc, &cd, &bccd);
  73     _lerp_half (&abbc, &bccd, &final);
  74
  75     k2->a = final;
  76     k2->b = bccd;
  77     k2->c = cd;
  78     k2->d = k1->d;
  79
  80     k1->b = ab;
  81     k1->c = abbc;
  82     k1->d = final;
  83 }
  84
  85 static double
  86 _spline_error_squared (const knots_t *knots)
  87 {
  88     double bdx, bdy, berr;
  89     double cdx, cdy, cerr;
  90     double dx, dy, v;
  91
  92     /* Intersection point (px):
  93      *      px = p1 + u(p2 - p1)
  94      *      (p - px) ∙ (p2 - p1) = 0
  95      * Thus:
  96      *      u = ((p - p1) ∙ (p2 - p1)) / ∥p2 - p1∥²;
  97      */
  98     bdx = knots->b.x - knots->a.x;
  99     bdy = knots->b.y - knots->a.y;
 100
 101     cdx = knots->c.x - knots->a.x;
 102     cdy = knots->c.y - knots->a.y;
 103
 104     dx = knots->d.x - knots->a.x;
 105     dy = knots->d.y - knots->a.y;
 106     v = dx * dx + dy * dy;
 107     if (v != 0.) {
 108         double u;
 109
 110         u = bdx * dx + bdy * dy;
 111         if (u <= 0) {
 112             /* bdx -= 0;
 113              * bdy -= 0;
 114              */
 115         } else if (u >= v) {
 116             bdx -= dx;
 117             bdy -= dy;
 118         } else {
 119             bdx -= u/v * dx;
 120             bdy -= u/v * dy;
 121         }
 122
 123         u = cdx * dx + cdy * dy;
 124         if (u <= 0) {
 125             /* cdx -= 0;
 126              * cdy -= 0;
 127              */
 128         } else if (u >= v) {
 129             cdx -= dx;
 130             cdy -= dy;
 131         } else {
 132             cdx -= u/v * dx;
 133             cdy -= u/v * dy;
 134         }
 135     }
 136
 137     berr = bdx * bdx + bdy * bdy;
 138     cerr = cdx * cdx + cdy * cdy;
 139     if (berr > cerr)
 140         return berr * v;
 141     else
 142         return cerr * v;
 143 }
 144
 145 static void
 146 _offset_line_to (cairo_t *cr,
 147                  const point_t *p0,
 148                  const point_t *p1,
 149                  const point_t *p2,
 150                  const point_t *p3,
 151                  double offset)
 152 {
 153     double dx, dy, v;
 154
 155     dx = p1->x - p0->x;
 156     dy = p1->y - p0->y;
 157      v = hypot (dx, dy);
 158      if (v == 0) {
 159          dx = p2->x - p0->x;
 160          dy = p2->y - p0->y;
 161          v = hypot (dx, dy);
 162          if (v == 0) {
 163              dx = p3->x - p0->x;
 164              dy = p3->y - p0->y;
 165              v = hypot (dx, dy);
 166          }
 167      }
 168
 169      if (v == 0) {
 170          cairo_line_to (cr, p0->x, p0->y);
 171      } else
 172          cairo_line_to (cr, p0->x - offset * dy / v, p0->y + offset * dx / v);
 173 }
 174
 175 static void
 176 _spline_decompose_into (knots_t *k1,
 177                         double tolerance_squared,
 178                         double offset,
 179                         cairo_t *cr)
 180 {
 181     knots_t k2;
 182
 183     if (_spline_error_squared (k1) < tolerance_squared) {
 184         _offset_line_to (cr, &k1->a, &k1->b, &k1->c, &k1->d, offset);
 185         return;
 186     }
 187
 188     _de_casteljau (k1, &k2);
 189
 190     _spline_decompose_into (k1, tolerance_squared, offset, cr);
 191     _spline_decompose_into (&k2, tolerance_squared, offset, cr);
 192 }
 193
 194 static void
 195 _spline_decompose (const knots_t *knots,
 196                    double tolerance, double offset,
 197                    cairo_t *cr)
 198 {
 199     knots_t k;
 200
 201     k = *knots;
 202     _spline_decompose_into (&k, tolerance * tolerance, offset, cr);
 203
 204     _offset_line_to (cr, &knots->d, &knots->c, &knots->b, &knots->a, -offset);
 205 }
 206
 207 static void
 208 _knots_reverse (knots_t *knots)
 209 {
 210     point_t tmp;
 211
 212     tmp = knots->a;
 213     knots->a = knots->d;
 214     knots->d = tmp;
 215
 216     tmp = knots->b;
 217     knots->b = knots->c;
 218     knots->c = tmp;
 219 }
 220
 221 static void
 222 thick_splines (cairo_t *cr, double offset)
 223 {
 224     knots_t k;
 225
 226     cairo_save (cr);
 227     cairo_translate (cr, 15, 15);
 228
 229     k = knots[0];
 230
 231     cairo_new_path (cr);
 232     _spline_decompose (&k, .1, offset, cr);
 233     _knots_reverse (&k);
 234     _spline_decompose (&k, .1, offset, cr);
 235     cairo_close_path (cr);
 236     cairo_fill (cr);
 237
 238     cairo_translate (cr, 130, 0);
 239
 240     k = knots[1];
 241
 242     cairo_new_path (cr);
 243     _spline_decompose (&k, .1, offset, cr);
 244     _knots_reverse (&k);
 245     _spline_decompose (&k, .1, offset, cr);
 246     cairo_close_path (cr);
 247     cairo_fill (cr);
 248
 249     cairo_translate (cr, 130, 0);
 250
 251     k = knots[2];
 252
 253     cairo_new_path (cr);
 254     _spline_decompose (&k, .1, offset, cr);
 255     _knots_reverse (&k);
 256     _spline_decompose (&k, .1, offset, cr);
 257     cairo_close_path (cr);
 258     cairo_fill (cr);
 259
 260     cairo_translate (cr, -130 - 65, 130);
 261
 262     k = knots[3];
 263
 264     cairo_new_path (cr);
 265     _spline_decompose (&k, .1, offset, cr);
 266     _knots_reverse (&k);
 267     _spline_decompose (&k, .1, offset, cr);
 268     cairo_close_path (cr);
 269     cairo_fill (cr);
 270
 271     cairo_translate (cr, 130, 0);
 272
 273     k = knots[4];
 274
 275     cairo_new_path (cr);
 276     _spline_decompose (&k, .1, offset, cr);
 277     _knots_reverse (&k);
 278     _spline_decompose (&k, .1, offset, cr);
 279     cairo_close_path (cr);
 280     cairo_fill (cr);
 281     cairo_restore (cr);
 282 }
 283
 284 static void
 285 thin_splines (cairo_t *cr)
 286 {
 287     cairo_save (cr);
 288     cairo_translate (cr, 15, 15);
 289
 290     cairo_new_path (cr);
 291     _spline_decompose (&knots[0], .1, 0, cr);
 292     cairo_stroke (cr);
 293
 294     cairo_translate (cr, 130, 0);
 295
 296     cairo_new_path (cr);
 297     _spline_decompose (&knots[1], .1, 0, cr);
 298     cairo_stroke (cr);
 299
 300     cairo_translate (cr, 130, 0);
 301
 302     cairo_new_path (cr);
 303     _spline_decompose (&knots[2], .1, 0, cr);
 304     cairo_stroke (cr);
 305
 306     cairo_translate (cr, -130 - 65, 130);
 307
 308     cairo_new_path (cr);
 309     _spline_decompose (&knots[3], .1, 0, cr);
 310     cairo_stroke (cr);
 311
 312     cairo_translate (cr, 130, 0);
 313
 314     cairo_new_path (cr);
 315     _spline_decompose (&knots[4], .1, 0, cr);
 316     cairo_stroke (cr);
 317     cairo_restore (cr);
 318 }
 319 #endif
 320
 321 static void
 322 stroke_splines (cairo_t *cr)
 323 {
 324     cairo_save (cr);
 325     cairo_translate (cr, 15, 15);
 326
 327     cairo_new_path (cr);
 328     cairo_move_to (cr,
 329                    knots[0].a.x, knots[0].a.y);
 330     cairo_curve_to (cr,
 331                     knots[0].b.x, knots[0].b.y,
 332                     knots[0].c.x, knots[0].c.y,
 333                     knots[0].d.x, knots[0].d.y);
 334     cairo_stroke (cr);
 335
 336     cairo_translate (cr, 130, 0);
 337
 338     cairo_new_path (cr);
 339     cairo_move_to (cr,
 340                    knots[1].a.x, knots[1].a.y);
 341     cairo_curve_to (cr,
 342                     knots[1].b.x, knots[1].b.y,
 343                     knots[1].c.x, knots[1].c.y,
 344                     knots[1].d.x, knots[1].d.y);
 345     cairo_stroke (cr);
 346
 347     cairo_translate (cr, 130, 0);
 348
 349     cairo_new_path (cr);
 350     cairo_move_to (cr,
 351                    knots[2].a.x, knots[2].a.y);
 352     cairo_curve_to (cr,
 353                     knots[2].b.x, knots[2].b.y,
 354                     knots[2].c.x, knots[2].c.y,
 355                     knots[2].d.x, knots[2].d.y);
 356     cairo_stroke (cr);
 357
 358     cairo_translate (cr, -130 - 65, 130);
 359
 360     cairo_new_path (cr);
 361     cairo_move_to (cr,
 362                    knots[3].a.x, knots[3].a.y);
 363     cairo_curve_to (cr,
 364                     knots[3].b.x, knots[3].b.y,
 365                     knots[3].c.x, knots[3].c.y,
 366                     knots[3].d.x, knots[3].d.y);
 367     cairo_stroke (cr);
 368
 369     cairo_translate (cr, 130, 0);
 370
 371     cairo_new_path (cr);
 372     cairo_move_to (cr,
 373                    knots[4].a.x, knots[4].a.y);
 374     cairo_curve_to (cr,
 375                     knots[4].b.x, knots[4].b.y,
 376                     knots[4].c.x, knots[4].c.y,
 377                     knots[4].d.x, knots[4].d.y);
 378     cairo_stroke (cr);
 379     cairo_restore (cr);
 380 }
 381
 382 static cairo_test_status_t
 383 draw (cairo_t *cr, int width, int height)
 384 {
 385     cairo_set_source_rgb (cr, 1, 1, 1);
 386     cairo_paint (cr);
 387
 388 #ifdef REFERENCE
 389     cairo_set_source_rgb (cr, 0, 0, 0);
 390     thick_splines (cr, 5);
 391
 392     cairo_set_source_rgb (cr, 1, 1, 1);
 393     thin_splines (cr);
 394 #endif
 395
 396     /*
 397      * Use a high tolerance to reduce dependence upon algorithm used for
 398      * spline decomposition.
 399      */
 400     cairo_set_tolerance (cr, 0.001);
 401
 402     cairo_set_line_width (cr, 10);
 403     cairo_set_source_rgb (cr, 0, 0, 0);
 404     stroke_splines (cr);
 405     cairo_set_line_width (cr, 2);
 406     cairo_set_source_rgb (cr, 1, 1, 1);
 407     stroke_splines (cr);
 408
 409     return CAIRO_TEST_SUCCESS;
 410 }
 411
 412 int
 413 main (void)
 414 {
 415     return cairo_test (&test);
 416 }