rosapps/smartpdf/fitz/raster/pathstroke.c

   1 #include "fitz-base.h"
   2 #include "fitz-world.h"
   3 #include "fitz-draw.h"
   4
   5 enum { BUTT = 0, ROUND = 1, SQUARE = 2, MITER = 0, BEVEL = 2 };
   6
   7 struct sctx
   8 {
   9         fz_gel *gel;
  10         fz_matrix *ctm;
  11         float flatness;
  12
  13         int linecap;
  14         int linejoin;
  15         float linewidth;
  16         float miterlimit;
  17         fz_point beg[2];
  18         fz_point seg[2];
  19         int sn, bn;
  20         int dot;
  21
  22         fz_dash *dash;
  23         int toggle;
  24         int offset;
  25         float phase;
  26         fz_point cur;
  27 };
  28
  29 static fz_error *
  30 line(struct sctx *s, float x0, float y0, float x1, float y1)
  31 {
  32         float tx0 = s->ctm->a * x0 + s->ctm->c * y0 + s->ctm->e;
  33         float ty0 = s->ctm->b * x0 + s->ctm->d * y0 + s->ctm->f;
  34         float tx1 = s->ctm->a * x1 + s->ctm->c * y1 + s->ctm->e;
  35         float ty1 = s->ctm->b * x1 + s->ctm->d * y1 + s->ctm->f;
  36         return fz_insertgel(s->gel, tx0, ty0, tx1, ty1);
  37 }
  38
  39 static fz_error *
  40 arc(struct sctx *s,
  41                 float xc, float yc,
  42                 float x0, float y0,
  43                 float x1, float y1)
  44 {
  45         fz_error *error;
  46         float th0, th1, r;
  47         float theta;
  48         float ox, oy, nx, ny;
  49         int n, i;
  50
  51         r = fabs(s->linewidth);
  52         theta = 2 * M_SQRT2 * sqrt(s->flatness / r);
  53         th0 = atan2(y0, x0);
  54         th1 = atan2(y1, x1);
  55
  56         if (r > 0)
  57         {
  58                 if (th0 < th1)
  59                         th0 += M_PI * 2;
  60                 n = ceil((th0 - th1) / theta);
  61         }
  62         else
  63         {
  64                 if (th1 < th0)
  65                         th1 += M_PI * 2;
  66                 n = ceil((th1 - th0) / theta);
  67         }
  68
  69         ox = x0;
  70         oy = y0;
  71         for (i = 1; i < n; i++)
  72         {
  73                 theta = th0 + (th1 - th0) * i / n;
  74                 nx = cos(theta) * r;
  75                 ny = sin(theta) * r;
  76                 error = line(s, xc + ox, yc + oy, xc + nx, yc + ny);
  77                 if (error) return error;
  78                 ox = nx;
  79                 oy = ny;
  80         }
  81
  82         error = line(s, xc + ox, yc + oy, xc + x1, yc + y1);
  83         if (error) return error;
  84
  85         return nil;
  86 }
  87
  88 static fz_error *
  89 linestroke(struct sctx *s, fz_point a, fz_point b)
  90 {
  91         fz_error *error;
  92
  93         float dx = b.x - a.x;
  94         float dy = b.y - a.y;
  95         float scale = s->linewidth / sqrt(dx * dx + dy * dy);
  96         float dlx = dy * scale;
  97         float dly = -dx * scale;
  98
  99         error = line(s, a.x - dlx, a.y - dly, b.x - dlx, b.y - dly);
 100         if (error) return error;
 101
 102         error = line(s, b.x + dlx, b.y + dly, a.x + dlx, a.y + dly);
 103         if (error) return error;
 104
 105         return nil;
 106 }
 107
 108 static fz_error *
 109 linejoin(struct sctx *s, fz_point a, fz_point b, fz_point c)
 110 {
 111         fz_error *error;
 112         float miterlimit = s->miterlimit;
 113         float linewidth = s->linewidth;
 114         int linejoin = s->linejoin;
 115         float dx0, dy0;
 116         float dx1, dy1;
 117         float dlx0, dly0;
 118         float dlx1, dly1;
 119         float dmx, dmy;
 120         float dmr2;
 121         float scale;
 122         float cross;
 123
 124         dx0 = b.x - a.x;
 125         dy0 = b.y - a.y;
 126
 127         dx1 = c.x - b.x;
 128         dy1 = c.y - b.y;
 129
 130         if (dx0 * dx0 + dy0 * dy0 < FLT_EPSILON)
 131                 return nil;
 132         if (dx1 * dx1 + dy1 * dy1 < FLT_EPSILON)
 133                 return nil;
 134
 135         scale = linewidth / sqrt(dx0 * dx0 + dy0 * dy0);
 136         dlx0 = dy0 * scale;
 137         dly0 = -dx0 * scale;
 138
 139         scale = linewidth / sqrt(dx1 * dx1 + dy1 * dy1);
 140         dlx1 = dy1 * scale;
 141         dly1 = -dx1 * scale;
 142
 143         cross = dx1 * dy0 - dx0 * dy1;
 144
 145         dmx = (dlx0 + dlx1) * 0.5;
 146         dmy = (dly0 + dly1) * 0.5;
 147         dmr2 = dmx * dmx + dmy * dmy;
 148
 149         if (cross * cross < FLT_EPSILON && dx0 * dx1 + dy0 * dy1 >= 0)
 150                 linejoin = BEVEL;
 151
 152         if (linejoin == MITER)
 153                 if (dmr2 * miterlimit * miterlimit < linewidth * linewidth)
 154                         linejoin = BEVEL;
 155
 156         if (linejoin == BEVEL)
 157         {
 158                 error = line(s, b.x - dlx0, b.y - dly0, b.x - dlx1, b.y - dly1);
 159                 if (error) return error;
 160                 error = line(s, b.x + dlx1, b.y + dly1, b.x + dlx0, b.y + dly0);
 161                 if (error) return error;
 162         }
 163
 164         if (linejoin == MITER)
 165         {
 166                 scale = linewidth * linewidth / dmr2;
 167                 dmx *= scale;
 168                 dmy *= scale;
 169
 170                 if (cross < 0)
 171                 {
 172                         error = line(s, b.x - dlx0, b.y - dly0, b.x - dlx1, b.y - dly1);
 173                         if (error) return error;
 174                         error = line(s, b.x + dlx1, b.y + dly1, b.x + dmx, b.y + dmy);
 175                         if (error) return error;
 176                         error = line(s, b.x + dmx, b.y + dmy, b.x + dlx0, b.y + dly0);
 177                         if (error) return error;
 178                 }
 179                 else
 180                 {
 181                         error = line(s, b.x + dlx1, b.y + dly1, b.x + dlx0, b.y + dly0);
 182                         if (error) return error;
 183                         error = line(s, b.x - dlx0, b.y - dly0, b.x - dmx, b.y - dmy);
 184                         if (error) return error;
 185                         error = line(s, b.x - dmx, b.y - dmy, b.x - dlx1, b.y - dly1);
 186                         if (error) return error;
 187                 }
 188         }
 189
 190         if (linejoin == ROUND)
 191         {
 192                 if (cross < 0)
 193                 {
 194                         error = line(s, b.x - dlx0, b.y - dly0, b.x - dlx1, b.y - dly1);
 195                         if (error) return error;
 196                         error = arc(s, b.x, b.y, dlx1, dly1, dlx0, dly0);
 197                         if (error) return error;
 198                 }
 199                 else
 200                 {
 201                         error = line(s, b.x + dlx1, b.y + dly1, b.x + dlx0, b.y + dly0);
 202                         if (error) return error;
 203                         error = arc(s, b.x, b.y, -dlx0, -dly0, -dlx1, -dly1);
 204                         if (error) return error;
 205                 }
 206         }
 207
 208         return nil;
 209 }
 210
 211 static fz_error *
 212 linecap(struct sctx *s, fz_point a, fz_point b)
 213 {
 214         fz_error *error;
 215         float flatness = s->flatness;
 216         float linewidth = s->linewidth;
 217         int linecap = s->linecap;
 218
 219         float dx = b.x - a.x;
 220         float dy = b.y - a.y;
 221
 222         float scale = linewidth / sqrt(dx * dx + dy * dy);
 223         float dlx = dy * scale;
 224         float dly = -dx * scale;
 225
 226         if (linecap == BUTT)
 227                 return line(s, b.x - dlx, b.y - dly, b.x + dlx, b.y + dly);
 228
 229         if (linecap == ROUND)
 230         {
 231                 int i;
 232                 int n = ceil(M_PI / (2.0 * M_SQRT2 * sqrt(flatness / linewidth)));
 233                 float ox = b.x - dlx;
 234                 float oy = b.y - dly;
 235                 for (i = 1; i < n; i++)
 236                 {
 237                         float theta = M_PI * i / n;
 238                         float cth = cos(theta);
 239                         float sth = sin(theta);
 240                         float nx = b.x - dlx * cth - dly * sth;
 241                         float ny = b.y - dly * cth + dlx * sth;
 242                         error = line(s, ox, oy, nx, ny);
 243                         if (error) return error;
 244                         ox = nx;
 245                         oy = ny;
 246                 }
 247                 error = line(s, ox, oy, b.x + dlx, b.y + dly);
 248                 if (error) return error;
 249         }
 250
 251         if (linecap == SQUARE)
 252         {
 253                 error = line(s, b.x - dlx, b.y - dly,
 254                                                 b.x - dlx - dly,
 255                                                 b.y - dly + dlx);
 256                 if (error) return error;
 257                 error = line(s, b.x - dlx - dly,
 258                                                 b.y - dly + dlx,
 259                                                 b.x + dlx - dly,
 260                                                 b.y + dly + dlx);
 261                 if (error) return error;
 262                 error = line(s, b.x + dlx - dly,
 263                                                 b.y + dly + dlx,
 264                                                 b.x + dlx, b.y + dly);
 265                 if (error) return error;
 266         }
 267
 268         return nil;
 269 }
 270
 271 static fz_error *
 272 linedot(struct sctx *s, fz_point a)
 273 {
 274         fz_error *error;
 275         float flatness = s->flatness;
 276         float linewidth = s->linewidth;
 277         int n = ceil(M_PI / (M_SQRT2 * sqrt(flatness / linewidth)));
 278         float ox = a.x - linewidth;
 279         float oy = a.y;
 280         int i;
 281         for (i = 1; i < n; i++)
 282         {
 283                 float theta = M_PI * 2 * i / n;
 284                 float cth = cos(theta);
 285                 float sth = sin(theta);
 286                 float nx = a.x - cth * linewidth;
 287                 float ny = a.y + sth * linewidth;
 288                 error = line(s, ox, oy, nx, ny);
 289                 if (error) return error;
 290                 ox = nx;
 291                 oy = ny;
 292         }
 293         error = line(s, ox, oy, a.x - linewidth, a.y);
 294         if (error) return error;
 295         return nil;
 296 }
 297
 298 static fz_error *
 299 strokeflush(struct sctx *s)
 300 {
 301         fz_error *error;
 302
 303         if (s->sn == 2)
 304         {
 305                 error = linecap(s, s->beg[1], s->beg[0]);
 306                 if (error) return error;
 307                 error = linecap(s, s->seg[0], s->seg[1]);
 308                 if (error) return error;
 309         }
 310         else if (s->dot)
 311         {
 312                 error = linedot(s, s->beg[0]);
 313                 if (error) return error;
 314         }
 315
 316         s->dot = 0;
 317
 318         return nil;
 319 }
 320
 321 static fz_error *
 322 strokemoveto(struct sctx *s, fz_point cur)
 323 {
 324         fz_error *error;
 325
 326         error = strokeflush(s);
 327         if (error) return error;
 328
 329         s->seg[0] = cur;
 330         s->beg[0] = cur;
 331         s->sn = 1;
 332         s->bn = 1;
 333
 334         return nil;
 335 }
 336
 337 static fz_error *
 338 strokelineto(struct sctx *s, fz_point cur)
 339 {
 340         fz_error *error;
 341
 342         float dx = cur.x - s->seg[s->sn-1].x;
 343         float dy = cur.y - s->seg[s->sn-1].y;
 344
 345         if (dx * dx + dy * dy < s->flatness * s->flatness * 0.25)
 346         {
 347                 s->dot = 1;
 348                 return nil;
 349         }
 350
 351         error = linestroke(s, s->seg[s->sn-1], cur);
 352         if (error) return error;
 353
 354         if (s->sn == 2)
 355         {
 356                 error = linejoin(s, s->seg[0], s->seg[1], cur);
 357                 if (error) return error;
 358
 359                 s->seg[0] = s->seg[1];
 360                 s->seg[1] = cur;
 361         }
 362
 363         if (s->sn == 1)
 364                 s->seg[s->sn++] = cur;
 365         if (s->bn == 1)
 366                 s->beg[s->bn++] = cur;
 367
 368         return nil;
 369 }
 370
 371 static fz_error *
 372 strokeclosepath(struct sctx *s)
 373 {
 374         fz_error *error;
 375
 376         if (s->sn == 2)
 377         {
 378                 error = strokelineto(s, s->beg[0]);
 379                 if (error) return error;
 380
 381                 if (s->seg[1].x == s->beg[0].x && s->seg[1].y == s->beg[0].y)
 382                         error = linejoin(s, s->seg[0], s->beg[0], s->beg[1]);
 383                 else
 384                         error = linejoin(s, s->seg[1], s->beg[0], s->beg[1]);
 385                 if (error) return error;
 386         }
 387
 388         else if (s->dot)
 389         {
 390                 error = linedot(s, s->beg[0]);
 391                 if (error) return error;
 392         }
 393
 394         s->bn = 0;
 395         s->sn = 0;
 396         s->dot = 0;
 397
 398         return nil;
 399 }
 400
 401 static fz_error *
 402 strokebezier(struct sctx *s,
 403         float xa, float ya,
 404         float xb, float yb,
 405         float xc, float yc,
 406         float xd, float yd)
 407 {
 408         fz_error *error;
 409         float dmax;
 410         float xab, yab;
 411         float xbc, ybc;
 412         float xcd, ycd;
 413         float xabc, yabc;
 414         float xbcd, ybcd;
 415         float xabcd, yabcd;
 416
 417         /* termination check */
 418         dmax = ABS(xa - xb);
 419         dmax = MAX(dmax, ABS(ya - yb));
 420         dmax = MAX(dmax, ABS(xd - xc));
 421         dmax = MAX(dmax, ABS(yd - yc));
 422         if (dmax < s->flatness) {
 423                 fz_point p;
 424                 p.x = xd;
 425                 p.y = yd;
 426                 return strokelineto(s, p);
 427         }
 428
 429         xab = xa + xb;
 430         yab = ya + yb;
 431         xbc = xb + xc;
 432         ybc = yb + yc;
 433         xcd = xc + xd;
 434         ycd = yc + yd;
 435
 436         xabc = xab + xbc;
 437         yabc = yab + ybc;
 438         xbcd = xbc + xcd;
 439         ybcd = ybc + ycd;
 440
 441         xabcd = xabc + xbcd;
 442         yabcd = yabc + ybcd;
 443
 444         xab *= 0.5f; yab *= 0.5f;
 445         xbc *= 0.5f; ybc *= 0.5f;
 446         xcd *= 0.5f; ycd *= 0.5f;
 447
 448         xabc *= 0.25f; yabc *= 0.25f;
 449         xbcd *= 0.25f; ybcd *= 0.25f;
 450
 451         xabcd *= 0.125f; yabcd *= 0.125f;
 452
 453         error = strokebezier(s, xa, ya, xab, yab, xabc, yabc, xabcd, yabcd);
 454         if (error)
 455                 return error;
 456
 457         return strokebezier(s, xabcd, yabcd, xbcd, ybcd, xcd, ycd, xd, yd);
 458 }
 459
 460 fz_error *
 461 fz_strokepath(fz_gel *gel, fz_pathnode *path, fz_matrix ctm, float flatness)
 462 {
 463         fz_error *error;
 464         struct sctx s;
 465         fz_point p0, p1, p2, p3;
 466         int i;
 467
 468         s.gel = gel;
 469         s.ctm = &ctm;
 470         s.flatness = flatness;
 471
 472         s.linecap = path->linecap;
 473         s.linejoin = path->linejoin;
 474         s.linewidth = path->linewidth * 0.5;
 475         s.miterlimit = path->miterlimit;
 476         s.sn = 0;
 477         s.bn = 0;
 478         s.dot = 0;
 479
 480         i = 0;
 481
 482         while (i < path->len)
 483         {
 484                 switch (path->els[i++].k)
 485                 {
 486                 case FZ_MOVETO:
 487                         p1.x = path->els[i++].v;
 488                         p1.y = path->els[i++].v;
 489                         error = strokemoveto(&s, p1);
 490                         if (error)
 491                                 return error;
 492                         p0 = p1;
 493                         break;
 494
 495                 case FZ_LINETO:
 496                         p1.x = path->els[i++].v;
 497                         p1.y = path->els[i++].v;
 498                         error = strokelineto(&s, p1);
 499                         if (error)
 500                                 return error;
 501                         p0 = p1;
 502                         break;
 503
 504                 case FZ_CURVETO:
 505                         p1.x = path->els[i++].v;
 506                         p1.y = path->els[i++].v;
 507                         p2.x = path->els[i++].v;
 508                         p2.y = path->els[i++].v;
 509                         p3.x = path->els[i++].v;
 510                         p3.y = path->els[i++].v;
 511                         error = strokebezier(&s, p0.x, p0.y, p1.x, p1.y, p2.x, p2.y, p3.x, p3.y);
 512                         if (error)
 513                                 return error;
 514                         p0 = p3;
 515                         break;
 516
 517                 case FZ_CLOSEPATH:
 518                         error = strokeclosepath(&s);
 519                         if (error)
 520                                 return error;
 521                         break;
 522                 }
 523         }
 524
 525         return strokeflush(&s);
 526 }
 527
 528 static fz_error *
 529 dashmoveto(struct sctx *s, fz_point a)
 530 {
 531         s->toggle = 1;
 532         s->offset = 0;
 533         s->phase = s->dash->phase;
 534
 535         while (s->phase >= s->dash->array[s->offset])
 536         {
 537                 s->toggle = !s->toggle;
 538                 s->phase -= s->dash->array[s->offset];
 539                 s->offset ++;
 540                 if (s->offset == s->dash->len)
 541                         s->offset = 0;
 542         }
 543
 544         s->cur = a;
 545
 546         if (s->toggle)
 547                 return strokemoveto(s, a);
 548
 549         return nil;
 550 }
 551
 552 static fz_error *
 553 dashlineto(struct sctx *s, fz_point b)
 554 {
 555         fz_error *error;
 556         float dx, dy;
 557         float total, used, ratio;
 558         fz_point a;
 559         fz_point m;
 560
 561         a = s->cur;
 562         dx = b.x - a.x;
 563         dy = b.y - a.y;
 564         total = sqrt(dx * dx + dy * dy);
 565         used = 0;
 566
 567         while (total - used > s->dash->array[s->offset] - s->phase)
 568         {
 569                 used += s->dash->array[s->offset] - s->phase;
 570                 ratio = used / total;
 571                 m.x = a.x + ratio * dx;
 572                 m.y = a.y + ratio * dy;
 573
 574                 if (s->toggle)
 575                         error = strokelineto(s, m);
 576                 else
 577                         error = strokemoveto(s, m);
 578                 if (error)
 579                         return error;
 580
 581                 s->toggle = !s->toggle;
 582                 s->phase = 0;
 583                 s->offset ++;
 584                 if (s->offset == s->dash->len)
 585                         s->offset = 0;
 586         }
 587
 588         s->phase += total - used;
 589
 590         s->cur = b;
 591
 592         if (s->toggle)
 593                 return strokelineto(s, b);
 594
 595         return nil;
 596 }
 597
 598 static fz_error *
 599 dashbezier(struct sctx *s,
 600         float xa, float ya,
 601         float xb, float yb,
 602         float xc, float yc,
 603         float xd, float yd)
 604 {
 605         fz_error *error;
 606         float dmax;
 607         float xab, yab;
 608         float xbc, ybc;
 609         float xcd, ycd;
 610         float xabc, yabc;
 611         float xbcd, ybcd;
 612         float xabcd, yabcd;
 613
 614         /* termination check */
 615         dmax = ABS(xa - xb);
 616         dmax = MAX(dmax, ABS(ya - yb));
 617         dmax = MAX(dmax, ABS(xd - xc));
 618         dmax = MAX(dmax, ABS(yd - yc));
 619         if (dmax < s->flatness) {
 620                 fz_point p;
 621                 p.x = xd;
 622                 p.y = yd;
 623                 return dashlineto(s, p);
 624         }
 625
 626         xab = xa + xb;
 627         yab = ya + yb;
 628         xbc = xb + xc;
 629         ybc = yb + yc;
 630         xcd = xc + xd;
 631         ycd = yc + yd;
 632
 633         xabc = xab + xbc;
 634         yabc = yab + ybc;
 635         xbcd = xbc + xcd;
 636         ybcd = ybc + ycd;
 637
 638         xabcd = xabc + xbcd;
 639         yabcd = yabc + ybcd;
 640
 641         xab *= 0.5f; yab *= 0.5f;
 642         xbc *= 0.5f; ybc *= 0.5f;
 643         xcd *= 0.5f; ycd *= 0.5f;
 644
 645         xabc *= 0.25f; yabc *= 0.25f;
 646         xbcd *= 0.25f; ybcd *= 0.25f;
 647
 648         xabcd *= 0.125f; yabcd *= 0.125f;
 649
 650         error = dashbezier(s, xa, ya, xab, yab, xabc, yabc, xabcd, yabcd);
 651         if (error) return error;
 652         return dashbezier(s, xabcd, yabcd, xbcd, ybcd, xcd, ycd, xd, yd);
 653 }
 654
 655 fz_error *
 656 fz_dashpath(fz_gel *gel, fz_pathnode *path, fz_matrix ctm, float flatness)
 657 {
 658         fz_error *error;
 659         struct sctx s;
 660         fz_point p0, p1, p2, p3, beg;
 661         int i;
 662
 663         s.gel = gel;
 664         s.ctm = &ctm;
 665         s.flatness = flatness;
 666
 667         s.linecap = path->linecap;
 668         s.linejoin = path->linejoin;
 669         s.linewidth = path->linewidth * 0.5;
 670         s.miterlimit = path->miterlimit;
 671         s.sn = 0;
 672         s.bn = 0;
 673         s.dot = 0;
 674
 675         s.dash = path->dash;
 676         s.toggle = 0;
 677         s.offset = 0;
 678         s.phase = 0;
 679
 680         i = 0;
 681
 682         while (i < path->len)
 683         {
 684                 switch (path->els[i++].k)
 685                 {
 686                 case FZ_MOVETO:
 687                         p1.x = path->els[i++].v;
 688                         p1.y = path->els[i++].v;
 689                         error = dashmoveto(&s, p1);
 690                         if (error)
 691                                 return error;
 692                         beg = p0 = p1;
 693                         break;
 694
 695                 case FZ_LINETO:
 696                         p1.x = path->els[i++].v;
 697                         p1.y = path->els[i++].v;
 698                         error = dashlineto(&s, p1);
 699                         if (error)
 700                                 return error;
 701                         p0 = p1;
 702                         break;
 703
 704                 case FZ_CURVETO:
 705                         p1.x = path->els[i++].v;
 706                         p1.y = path->els[i++].v;
 707                         p2.x = path->els[i++].v;
 708                         p2.y = path->els[i++].v;
 709                         p3.x = path->els[i++].v;
 710                         p3.y = path->els[i++].v;
 711                         error = dashbezier(&s, p0.x, p0.y, p1.x, p1.y, p2.x, p2.y, p3.x, p3.y);
 712                         if (error)
 713                                 return error;
 714                         p0 = p3;
 715                         break;
 716
 717                 case FZ_CLOSEPATH:
 718                         error = dashlineto(&s, beg);
 719                         if (error)
 720                                 return error;
 721                         break;
 722                 }
 723         }
 724
 725         return strokeflush(&s);
 726 }
 727