apdf/server/path.cc

   1 #include <stdlib.h>
   2 #include <stdio.h>
   3 #include <math.h>
   4 #include "gfx.h"
   5
   6 #define PATHDB(x)       ;
   7 #define DEBUG_PARTS(x)  ;
   8 #define DEBUG_JOIN(x)   ;
   9 #define DEBUG_APATH(x)  ;
  10 #define DEBUG_SCAN(x)   ;
  11 #define DEBUG_ISRECT(x) ;
  12 #define DEBUG_LOOPS(x)
  13 #define DEBUG_BEZIER(x) ;
  14
  15 #define dprintf printf
  16
  17 inline double length(double x, double y) { return sqrt(x * x + y * y); }
  18
  19 #if DEBUG
  20
  21 void APath::print(const Part* parts)
  22 {
  23         for (const Part* p = parts; p; p = p->next)
  24         {
  25                 printf("\t%p ", p);
  26                 p->print();
  27                 printf(" x %f y %f", p->x, p->y);
  28                 if (p->close)
  29                         printf(" closed %p", p->close);
  30                 printf("\n");
  31         }
  32 }
  33
  34 void APath::print() const
  35 {
  36         printf("APath %p\n", this);
  37         print(parts);
  38 }
  39
  40 void APath::Move::print() const
  41 {
  42         printf("move");
  43 }
  44
  45 void APath::Line::print() const
  46 {
  47         printf("line");
  48 }
  49
  50 void APath::Bezier2::print() const
  51 {
  52         printf("bezier x1 %f y1 %f", x1, y1);
  53 }
  54
  55 void APath::Bezier3::print() const
  56 {
  57         printf("bezier x1 %f y1 %f x2 %f y2 %f", x1, y1, x2, y2);
  58 }
  59
  60 #endif
  61
  62 static inline int _iround(double x)
  63 {
  64         return int(x + 65536.5) - 65536;
  65 }
  66
  67 bool APath::is_rect(int& x1, int& y1, int& x2, int& y2) const
  68 {
  69         int x[4];
  70         int y[4];
  71         int i = 0;
  72         int j = 0;
  73         double x0, y0;
  74
  75         DEBUG_ISRECT(printf("is_rect:\n"); print());
  76
  77         Part *p = parts;
  78
  79         if (!p || !p->close || p->type != Part::type_move)
  80                 return false;
  81
  82         x0 = p->x;
  83         y0 = p->y;
  84         x[0] = _iround(x0);
  85         y[0] = _iround(y0);
  86         p = p->next;
  87         DEBUG_ISRECT(printf("\t%f,%f\t%d,%d\n", x0, y0, x[0], y[0]));
  88
  89         for (int k = 1; k < 4; ++k, p = p->next)
  90         {
  91                 if (!p || p->type != Part::type_line)
  92                         return false;
  93
  94                 x0 += p->x;
  95                 y0 += p->y;
  96                 x[k] = _iround(x0);
  97                 y[k] = _iround(y0);
  98                 DEBUG_ISRECT(printf("\t%f,%f\t%d,%d\n", x0, y0, x[k], y[k]));
  99
 100                 if (x[k] <= x[i] && y[k] <= y[i])
 101                         i = k;
 102
 103                 if (x[k] >= x[j] && y[k] >= y[j])
 104                         j = k;
 105         }
 106
 107         if (p && (p->next || p->type != Part::type_line ||
 108                                 _iround(x0 + p->x) != x[0] || _iround(y0 + p->y) != y[0]))
 109         {
 110                 DEBUG_ISRECT(printf("too many components\n"));
 111                 return false;
 112         }
 113
 114         DEBUG_ISRECT(printf("i %d j %d\n", i, j));
 115
 116         if (i != j && x[i] != x[j] && y[i] != y[j])
 117         {
 118                 if (j != ((i + 2) & 3))
 119                 {
 120                         return false;
 121                 }
 122
 123                 int k = (i + 1) & 3;
 124                 int l = (j + 1) & 3;
 125
 126                 if (x[k] == x[i])
 127                 {
 128                         int t = l; l = k; k = t;
 129                 }
 130
 131                 DEBUG_ISRECT(printf("k %d l %d\n", k, l));
 132
 133                 if (x[k] != x[j] || x[l] != x[i] || y[k] != y[i] || y[l] != y[j])
 134                         return false;
 135         }
 136
 137         x1 = x[i];
 138         y1 = y[i];
 139         x2 = x[j];
 140         y2 = y[j];
 141
 142         DEBUG_ISRECT(printf("-> ok: (%d,%d)-(%d,%d)\n", x1, y1, x2, y2));
 143
 144         return true;
 145 }
 146
 147 void APath::Scanner::scan(const APath* path)
 148 {
 149         DEBUG_SCAN(dprintf("APath::Scanner::scan: path %p\n", path));
 150         Part* end = NULL;
 151         for (Part* p = path->parts; p; p = p->next)
 152         {
 153                 if (p->close)
 154                 {
 155                         DEBUG_SCAN(dprintf("APath::Scanner::scan: open %p\n", p->close));
 156                         open(p->close);
 157                         end = p->close;
 158                 }
 159                 DEBUG_SCAN(dprintf("APath::Scanner::scan: %p\n", p));
 160                 p->callback(*this);
 161                 if (p == end)
 162                 {
 163                         DEBUG_SCAN(dprintf("APath::Scanner::scan: close\n"));
 164                         close();
 165                 }
 166         }
 167 }
 168
 169 void APath::Move::callback(CallBack& s) const
 170 {
 171         s.move(x, y);
 172 }
 173
 174 void APath::Line::callback(CallBack& s) const
 175 {
 176         s.line(x, y);
 177 }
 178
 179 void APath::Bezier2::callback(CallBack& s) const
 180 {
 181         s.bezier(x1, y1, x, y);
 182 }
 183
 184 void APath::Bezier3::callback(CallBack& s) const
 185 {
 186         s.bezier(x1, y1, x2, y2, x, y);
 187 }
 188
 189 APath::Part* APath::Move::validate(Part* start)
 190 {
 191         close = NULL;
 192         return this;
 193 }
 194
 195 APath::Part* APath::Part::validate(Part* start)
 196 {
 197         if (close && start)
 198         {
 199                 start->close = this;
 200                 start = NULL;
 201         }
 202         close = NULL;
 203         return start;
 204 }
 205
 206 APath::Part* APath::join(Part* p1, Part *p2)
 207 {
 208         DEBUG_JOIN(dprintf("APath::join: p1 %p p2 %p\n", p1, p2));
 209         if (p1 == NULL)
 210                 return p2;
 211         else if (p2 == NULL)
 212                 return p1;
 213         else
 214         {
 215                 p1->end->next = p2;
 216                 p1->end = p2->end;
 217                 p2->end = NULL;
 218                 return p1;
 219         }
 220 }
 221
 222 APath::Part* APath::join(Part* p1, APath* p2)
 223 {
 224         DEBUG_JOIN(dprintf("APath::join: p1 %p p2 %p\n", p1, p2));
 225         Part *r;
 226         if (p2 == NULL)
 227                 return p1;
 228         else if (p1 == NULL)
 229                 r = p2->parts;
 230         else
 231         {
 232                 p1->end->next = p2->parts;
 233                 p1->end = p2->parts->end;
 234                 p2->parts->end = NULL;
 235                 r = p1;
 236         }
 237         p2->parts = NULL;
 238         delete p2;
 239         return r;
 240 }
 241
 242
 243 APath::Part* APath::clone(Part* p)
 244 {
 245         if (p)
 246         {
 247                 Part* q = p->clone();
 248                 while (p = p->next)
 249                         q->join(p->clone());
 250                 return q;
 251         }
 252         else
 253                 return NULL;
 254 }
 255
 256 void APath::destroy(Part* p)
 257 {
 258         while (p)
 259         {
 260                 Part* q = p->next;
 261                 delete p;
 262                 p = q;
 263         }
 264 }
 265
 266 APath::Part* APath::close(Part* p)
 267 {
 268         if (p)
 269         {
 270                 double x = 0, y = 0;
 271                 for (Part* q = p->next; q; q = q->next)
 272                 {
 273                         x += q->x;
 274                         y += q->y;
 275                 }
 276                 if (x != 0 || y != 0)
 277                 {
 278                         Part* q = line(-x, -y);
 279                         p->end->next = q;
 280                         p->end = q;
 281                 }
 282                 p->end->close = p->end;
 283         }
 284         return p;
 285 }
 286
 287 void APath::move(Part* p, double x, double y)
 288 {
 289         p->x += x;
 290         p->y += y;
 291 }
 292
 293 APath::Move* APath::move(double x, double y)
 294 {
 295         DEBUG_APATH(printf("move(%f, %f)\n", x, y));
 296         return new Move(x, y);
 297 }
 298
 299 APath::Line* APath::line(double x, double y)
 300 {
 301         DEBUG_APATH(printf("line(%f, %f)\n", x, y));
 302         return new Line(x, y);
 303 }
 304
 305 APath::Bezier2* APath::bezier(double x1, double y1, double x2, double y2)
 306 {
 307         DEBUG_APATH(printf("bezier(%f, %f, %f, %f)\n", x1, y1, x2, y2));
 308         return new Bezier2(x1, y1, x2, y2);
 309 }
 310
 311 APath::Bezier3* APath::bezier(double x1, double y1, double x2, double y2, double x3, double y3)
 312 {
 313         DEBUG_APATH(printf("bezier(%f, %f, %f, %f, %f, %f)\n", x1, y1, x2, y2, x3, y3));
 314         return new Bezier3(x1, y1, x2, y2, x3, y3);
 315 }
 316
 317 APath::APath(Part* p)
 318 {
 319         DEBUG_APATH(dprintf("APath::ctor: parts %p\n", p));
 320         Part* start = NULL;
 321         for (Part* q = p; q; q = q->next)
 322         {
 323                 start = q->validate(start);
 324         }
 325
 326         parts = p;
 327 }
 328
 329 APath::~APath()
 330 {
 331         destroy(parts);
 332 }
 333
 334 void APath::get_delta(Part* parts, double& dx, double& dy)
 335 {
 336         double x = 0, y = 0;
 337         for (Part* p = parts; p; p = p->next)
 338         {
 339                 x += p->x;
 340                 y += p->y;
 341                 if (p->close)
 342                         p = p->close;
 343         }
 344         dx = x;
 345         dy = y;
 346 }
 347
 348 void APath::get_delta(double& dx, double& dy) const
 349 {
 350         get_delta(parts, dx, dy);
 351 }
 352
 353 class StrokePathBuilder : public APath::Scanner
 354 {
 355 public:
 356         StrokePathBuilder(double lw, CapStyle c, JoinStyle j, double ml)
 357         : full_path(NULL), path1(NULL), path2(NULL), first(true),
 358           x1(0), y1(0), totx(0), toty(0), line_width(lw / 2), is_closed(false),
 359           cap_style(c), join_style(j), miter_limit(ml), xe(0), ye(0) {}
 360
 361         virtual void move(double x, double y);
 362         virtual void line(double x, double y);
 363         virtual void bezier(double x1, double y1, double x2, double y2);
 364         virtual void bezier(double x1, double y1, double x2, double y2, double x3, double y3);
 365         virtual void open(APath::Part*);
 366
 367         void set_pos(double x, double y) { totx += x; toty += y; }
 368         void add_pos(double x, double y) { x1 += x; y1 += y; }
 369         void add_err(double x, double y) { xe += x; ye += y; }
 370         void set_dir(double x, double y);
 371         void start();
 372         void do_close();
 373         void join();
 374         APath* get() { return new APath(full_path); }
 375         void add1(APath::Part* p) { path1 = APath::join(path1, p); }
 376         void add2(APath::Part* p) { path2 = APath::join(p, path2); }
 377         void add_cap();
 378         void add_correction(double& x, double& y)
 379         {
 380                 x += xe; y += ye;
 381                 xe = ye = 0;
 382         }
 383 private:
 384
 385         class LastDir : public APath::CallBack
 386         {
 387         public:
 388                 virtual void line(double x, double y) { dx = x; dy = y; }
 389                 virtual void bezier(double x1, double y1, double x2, double y2)
 390                 {
 391                         dx = x2 - x1; dy = y2 - y1;
 392                 }
 393                 virtual void bezier(double x1, double y1, double x2, double y2,
 394                                 double x3, double y3)
 395                 {
 396                         dx = x3 - x2; dy = y3 - y2;
 397                 }
 398
 399                 double dx, dy;
 400         };
 401
 402         APath::Part* full_path;
 403         APath::Part* path1;
 404         APath::Part* path2;
 405         double x1, y1;
 406         double xe, ye;
 407         double dx1, dy1;
 408         double dx2, dy2;
 409         double totx, toty;
 410         const double line_width;
 411         double miter_limit;
 412         CapStyle cap_style;
 413         JoinStyle join_style;
 414         bool is_closed;
 415 public:
 416         bool first;
 417 };
 418
 419 void StrokePathBuilder::set_dir(double x, double y)
 420 {
 421         dx1 = dx2;
 422         dy1 = dy2;
 423         dx2 = x;
 424         dy2 = y;
 425 }
 426
 427 void StrokePathBuilder::start()
 428 {
 429         PATHDB(printf("starting (%f,%f), (%f,%f) closed %d\n", x1, y1, dx2, dy2, is_closed));
 430         if (is_closed)
 431         {
 432                 path1 = APath::move(x1 + dy1, y1 - dx1);
 433                 totx = dy1;
 434                 toty = -dx1;
 435                 join();
 436         }
 437         else
 438         {
 439                 switch(cap_style)
 440                 {
 441                         case cap_round:
 442                                 path1 = APath::move(x1 - dx2, y1 - dy2);
 443                                 path1->join(APath::bezier(dy2, -dx2, dx2 + dy2, dy2 - dx2));
 444                                 path2 = APath::bezier(-dx2, -dy2, dy2 - dx2, -dx2 - dy2);
 445                                 totx = dx2;
 446                                 toty = dy2;
 447                                 break;
 448                         case cap_projecting:
 449                                 path1 = APath::move(x1 + dy2 - dx2, y1 - dx2 - dy2);
 450                                 path1->join(APath::line(dx2, dy2));
 451                                 path2 = APath::line(-dx2, -dy2);
 452                                 totx = dx2 - dy2;
 453                                 toty = dx2 + dy2;
 454                                 break;
 455                         default: /* cap_butt */
 456                                 path1 = APath::move(x1 + dy2, y1 - dx2);
 457                                 totx = -dy2;
 458                                 toty = dx2;
 459                                 break;
 460                 }
 461         }
 462         x1 = 0;
 463         y1 = 0;
 464 }
 465
 466 void StrokePathBuilder::join()
 467 {
 468         double tdx1, tdy1, tdx2, tdy2;
 469         bool side = dx1 * dy2 - dy1 * dx2 < 0;
 470         tdx1 = dx1; tdy1 = dy1; tdx2 = dx2; tdy2 = dy2;
 471         PATHDB(printf("joining (%f,%f)-(%f,%f)\n", dx1, dy1, dx2, dy2));
 472         APath::Part* seg1 = NULL;
 473         APath::Part* seg2 = APath::line(tdy2 - tdy1, tdx1 - tdx2);
 474         switch(join_style)
 475         {
 476                 case join_round:
 477                         {
 478                                 double d = tdx2 * tdy1 - tdx1 * tdy2;
 479                                 if (fabs(d) > 0.0001)
 480                                 {
 481                                         double a = (tdx2 * (tdx1 - tdx2) - tdy2 * (tdy2 - tdy1)) / d;
 482                                         double x = a * tdx1;
 483                                         double y = a * tdy1;
 484                                         if (side)
 485                                                 seg1 = APath::bezier(tdy2 - tdy1 - x, tdx1 - tdx2 - y, tdy2 - tdy1, tdx1 - tdx2);
 486                                         else
 487                                                 seg1 = APath::bezier(x, y, tdy2 - tdy1, tdx1 - tdx2);
 488                                 }
 489                                 else
 490                                 {
 491                                         seg1 = APath::clone(seg2);
 492                                 }
 493                         }
 494                         break;
 495                 case join_miter:
 496                         {
 497                                 double d = tdx2 * tdy1 - tdx1 * tdy2;
 498                                 if (fabs(d * miter_limit) > line_width * line_width)
 499                                 {
 500                                         double a = (tdx2 * (tdx1 - tdx2) - tdy2 * (tdy2 - tdy1)) / d;
 501                                         double x = a * tdx1;
 502                                         double y = a * tdy1;
 503                                         APath::Part* p1 = APath::line(x, y);
 504                                         APath::Part* p2 = APath::line(tdy2 - tdy1 - x, tdx1 - tdx2 - y);
 505                                         if (side)
 506                                         {
 507                                                 APath::Part *t = p1; p1 = p2; p2 = t;
 508                                         }
 509                                         seg1 = p1->join(p2);
 510                                         break;
 511                                 }
 512                         } /*FALLTHROUGH*/
 513                 default: /*join_bevel*/
 514                         seg1 = APath::clone(seg2);
 515                         break;
 516         }
 517         if(side)
 518         {
 519                 APath::Part* t = seg1; seg1 = seg2; seg2 = t;
 520         }
 521         path1 = APath::join(path1, seg1);
 522         path2 = APath::join(seg2, path2);
 523 }
 524
 525 void StrokePathBuilder::do_close()
 526 {
 527         PATHDB(printf("closing (%f, %f) is_closed %d\n", dx2, dy2, is_closed));
 528         if (is_closed)
 529         {
 530                 path1 = APath::close(path1);
 531                 path2 = APath::close(APath::move(-2 * totx, -2 * toty)->join(path2));
 532                 path1 = APath::join(path1, path2);
 533         }
 534         else
 535         {
 536                 switch(cap_style)
 537                 {
 538                         case cap_round:
 539                                 path1 = APath::join(path1, APath::bezier(dx2, dy2, dx2 - dy2, dx2 + dy2));
 540                                 path1->join(APath::bezier(-dy2, dx2, -dx2 - dy2, dx2 - dy2));
 541                                 break;
 542                         case cap_projecting:
 543                                 path1 = APath::join(path1, APath::line(dx2, dy2));
 544                                 path1->join(APath::line(-2 * dy2, 2 * dx2));
 545                                 path1->join(APath::line(-dx2, -dy2));
 546                                 break;
 547                         default: /* cap_butt */
 548                                 path1 = APath::join(path1, APath::line(-2 * dy2, 2 * dx2));
 549                                 break;
 550                 }
 551                 path1 = APath::join(path1, path2);
 552                 path1 = APath::close(path1);
 553         }
 554         full_path = APath::join(full_path, path1);
 555         path1 = path2 = NULL;
 556         x1 = totx;
 557         y1 = toty;
 558         is_closed = false;
 559 }
 560
 561 void StrokePathBuilder::move(double x, double y)
 562 {
 563         PATHDB(printf("move(%f, %f) first %d\n", x, y, first));
 564         if (!first)
 565                 do_close();
 566         add_correction(x, y);
 567         add_pos(x, y);
 568         first = true;
 569 }
 570
 571 void StrokePathBuilder::open(APath::Part* end)
 572 {
 573         PATHDB(printf("open(%p)\n", end));
 574         if (!first)
 575                 do_close();
 576         first = true;
 577         LastDir dir;
 578         dir(end);
 579         double x = dir.dx;
 580         double y = dir.dy;
 581         double d = length(x, y);
 582         if (d >= 0.0001)
 583         {
 584                 d /= line_width;
 585                 set_dir(x / d, y / d);
 586                 is_closed = true;
 587         }
 588         else
 589                 add_err(x, y);
 590 }
 591
 592 void StrokePathBuilder::line(double x, double y)
 593 {
 594         PATHDB(printf("line(%f, %f)\n", x, y));
 595         add_correction(x, y);
 596         double d = length(x, y);
 597         if (d >= 0.0001)
 598         {
 599                 d /= line_width;
 600                 set_dir(x / d, y / d);
 601                 if (first)
 602                         start();
 603                 else
 604                         join();
 605                 add1(APath::line(x, y));
 606                 add2(APath::line(-x, -y));
 607                 set_pos(x, y);
 608                 first = false;
 609         }
 610         else
 611                 add_err(x, y);
 612 }
 613
 614 void StrokePathBuilder::bezier(double x1, double y1, double x, double y)
 615 {
 616         PATHDB(printf("bezier(%f, %f, %f, %f)\n", x1, y1, x, y));
 617         add_correction(x, y);
 618         double X1 = x1;
 619         double Y1 = y1;
 620         double X2 = x - x1;
 621         double Y2 = y - y1;
 622         double D1 = length(X1, Y1);
 623         double D2 = length(X2, Y2);
 624         if (D1 >= 0.0001 || D2 >= 0.0001)
 625         {
 626                 double DX1, DY1, DX2, DY2;
 627                 D1 /= line_width;
 628                 D2 /= line_width;
 629                 const double eps = 0.0001 / line_width;//1 / (line_width * 16);
 630                 if (D1 < eps)
 631                 {
 632                         DX1 = X2 / D2;
 633                         DY1 = Y2 / D2;
 634                 }
 635                 else
 636                 {
 637                         DX1 = X1 / D1;
 638                         DY1 = Y1 / D1;
 639                 }
 640                 if (D2 < eps)
 641                 {
 642                         DX2 = DX1;
 643                         DY2 = DY1;
 644                 }
 645                 else
 646                 {
 647                         DX2 = X2 / D2;
 648                         DY2 = Y2 / D2;
 649                 }
 650                 set_dir(DX1, DY1);
 651                 if (first)
 652                         start();
 653                 else
 654                         join();
 655                 set_dir(DX2, DY2);
 656                 //printf("(%f,%f) (%f,%f) (%f,%f) lw=%f\n",X1,Y1,X2,Y2,X3,Y3,lw);
 657                 //printf("dx1=%f dy1=%f dx2=%f dy2=%f dx3=%f dy3=%f\n",DX1,DY1,DX2,DY2,DX3,DY3);
 658                 double DX4, DY4;
 659                 double d = DX2 * DY1 - DY2 * DX1;
 660                 if (fabs(d) < 0.0001)
 661                 {
 662                         DX4 = DY1;
 663                         DY4 = -DX1;
 664                 }
 665                 else
 666                 {
 667                         double a = (DX2 * (Y1 + DX1 - DX2) - DY2 * (X1 + DY2 - DY1)) / d;
 668                         DX4 = DY1 + a * DX1 - X1;
 669                         DY4 = -DX1 + a * DY1 - Y1;
 670                 }
 671                 //printf("dx4=%f dy4=%f\n",DX4,DY4);
 672                 //printf("dx5=%f dy5=%f\n",DX5,DY5);
 673                 add1(APath::bezier(x1 + DX4 - DY1, y1 + DY4 + DX1,
 674                                         x + dy2 - dy1, y - dx2 + dx1));
 675                 add2(APath::bezier(x1 - x - DX4 + DY2, y1 - y - DY4 - DX2,
 676                                         dy2 - dy1 - x, dx1 - dx2 - y));
 677                 set_pos(x, y);
 678                 first = false;
 679         }
 680         else
 681                 add_err(x, y);
 682 }
 683
 684 void StrokePathBuilder::bezier(double x1, double y1, double x2, double y2, double x, double y)
 685 {
 686         const int max_levels = 13;
 687         struct
 688         {
 689                 double x;
 690                 double y;
 691         } *s, stack[max_levels];
 692
 693         s = stack;
 694
 695         for (;;)
 696         {
 697                 PATHDB(printf("bezier(%f, %f, %f, %f, %f, %f)\n", x1, y1, x2, y2, x, y));
 698
 699                 double X1 = x1;
 700                 double Y1 = y1;
 701                 double X2 = x2 - x1;
 702                 double Y2 = y2 - y1;
 703                 double X3 = x - x2;
 704                 double Y3 = y - y2;
 705                 double D1 = length(X1, Y1);
 706                 double D2 = length(X2, Y2);
 707                 double D3 = length(X3, Y3);
 708
 709                 if (s < stack + max_levels - 3 &&
 710                                 //(D1 >= 0.01 || D2 >= 0.01 || D3 >= 0.01) &&
 711                                 (X1 * X2 + Y1 * Y2 < -0.5 * D1 * D2 - 0.00005 ||
 712                                  X2 * X3 + Y2 * Y3 < -0.5 * D2 * D3 - 0.00005))
 713                 {
 714                         PATHDB(printf("split: (%f,%f) (%f,%f) (%f,%f)\n",
 715                                                 X1, Y1, X2, Y2, X3, Y3));
 716                         double xa = x1 / 2;
 717                         double ya = y1 / 2;
 718                         double xb = (x1 + x2) / 2;
 719                         double yb = (y1 + y2) / 2;
 720                         double xc = (x2 + x) / 2;
 721                         double yc = (y2 + y) / 2;
 722                         double xd = (xa + xb) / 2;
 723                         double yd = (ya + yb) / 2;
 724                         double xe = (xb + xc) / 2;
 725                         double ye = (yb + yc) / 2;
 726                         double xf = (xd + xe) / 2;
 727                         double yf = (yd + ye) / 2;
 728
 729                         s[0].x = xe - xf;
 730                         s[0].y = ye - yf;
 731                         s[1].x = xc - xf;
 732                         s[1].y = yc - yf;
 733                         s[2].x = x - xf;
 734                         s[2].y = y - yf;
 735                         s += 3;
 736
 737                         x = xf;
 738                         y = yf;
 739                         x1 = xa;
 740                         y1 = ya;
 741                         x2 = xd;
 742                         y2 = yd;
 743
 744                         continue;
 745                 }
 746
 747                 add_correction(x, y);
 748                 X3 = x - x2;
 749                 Y3 = y - y2;
 750                 D3 = length(X3, Y3);
 751                 if (D1 >= 0.01 || D2 >= 0.01 || D3 >= 0.01)
 752                 {
 753                         double DX1, DY1, DX2, DY2, DX3, DY3;
 754                         D1 /= line_width;
 755                         D2 /= line_width;
 756                         D3 /= line_width;
 757                         const double eps = 0.005 / line_width;//1 / (line_width * 16);
 758                         if (D1 < eps)
 759                         {
 760                                 if (D2 < eps)
 761                                 {
 762                                         DX1 = X3 / D3;
 763                                         DY1 = Y3 / D3;
 764                                 }
 765                                 else
 766                                 {
 767                                         DX1 = X2 / D2;
 768                                         DY1 = Y2 / D2;
 769                                 }
 770                         }
 771                         else
 772                         {
 773                                 DX1 = X1 / D1;
 774                                 DY1 = Y1 / D1;
 775                         }
 776                         if (D2 < eps)
 777                         {
 778                                 DX2 = DX1;
 779                                 DY2 = DY1;
 780                         }
 781                         else
 782                         {
 783                                 DX2 = X2 / D2;
 784                                 DY2 = Y2 / D2;
 785                         }
 786                         if (D3 < eps)
 787                         {
 788                                 DX3 = DX2;
 789                                 DY3 = DY2;
 790                         }
 791                         else
 792                         {
 793                                 DX3 = X3 / D3;
 794                                 DY3 = Y3 / D3;
 795                         }
 796                         set_dir(DX1, DY1);
 797                         if (first)
 798                                 start();
 799                         else
 800                                 join();
 801                         set_dir(DX3, DY3);
 802                         //printf("(%f,%f) (%f,%f) (%f,%f) lw=%f\n",X1,Y1,X2,Y2,X3,Y3,lw);
 803                         //printf("dx1=%f dy1=%f dx2=%f dy2=%f dx3=%f dy3=%f\n",DX1,DY1,DX2,DY2,DX3,DY3);
 804                         double DX4, DY4;
 805                         double d = DX2 * DY1 - DY2 * DX1;
 806                         if (fabs(d) < 0.01)
 807                         {
 808                                 DX4 = DY1;
 809                                 DY4 = -DX1;
 810                         }
 811                         else
 812                         {
 813                                 double a = (DX2 * (Y1 + DX1 - DX2) - DY2 * (X1 + DY2 - DY1)) / d;
 814                                 DX4 = DY1 + a * DX1 - X1;
 815                                 DY4 = -DX1 + a * DY1 - Y1;
 816                         }
 817                         //printf("dx4=%f dy4=%f\n",DX4,DY4);
 818                         double DX5, DY5;
 819                         d = DX3 * DY2 - DY3 * DX2;
 820                         if (fabs(d) < 0.01)
 821                         {
 822                                 DX5 = DY2;
 823                                 DY5 = -DX2;
 824                         }
 825                         else
 826                         {
 827                                 double a = (DX3 * (Y2 + DX2 - DX3) - DY3 * (X2 - DY2 + DY3)) / d;
 828                                 DX5 = DY2 + a * DX2 - X2;
 829                                 DY5 = -DX2 + a * DY2 - Y2;
 830                         }
 831                         //printf("dx5=%f dy5=%f\n",DX5,DY5);
 832                         add1(APath::bezier(x1 + DX4 - DY1, y1 + DY4 + DX1,
 833                                                 x2 + DX5 - DY1, y2 + DY5 + DX1,
 834                                                 x + dy2 - dy1, y - dx2 + dx1));
 835                         add2(APath::bezier(x2 - x - DX5 + DY3, y2 - y - DY5 - DX3,
 836                                                 x1 - x - DX4 + DY3, y1 - y - DY4 - DX3,
 837                                                 dy2 - dy1 - x, dx1 - dx2 - y));
 838                         set_pos(x, y);
 839                         first = false;
 840                 }
 841                 else
 842                         add_err(x, y);
 843
 844                 if (s == stack)
 845                         break;
 846
 847                 s -= 3;
 848                 x1 = s[0].x;
 849                 y1 = s[0].y;
 850                 x2 = s[1].x;
 851                 y2 = s[1].y;
 852                 x = s[2].x;
 853                 y = s[2].y;
 854         }
 855         PATHDB(printf("~bezier\n"));
 856 }
 857
 858 APath* APath::thicken(double lw, CapStyle cap_style, JoinStyle join_style, double miter_limit) const
 859 {
 860 #if 0//DEBUG
 861         printf("thicken(%f, %d, %d, %f)\n", lw, cap_style, join_style, miter_limit);
 862         print();
 863 #endif
 864         StrokePathBuilder builder(lw, cap_style, join_style, miter_limit);
 865
 866         builder.scan(this);
 867
 868         if (!builder.first)
 869                 builder.do_close();
 870
 871         APath* result = builder.get();
 872
 873 #if 0//DEBUG
 874         printf("result:\n");
 875         result->print();
 876 #endif
 877         return result;
 878 }
 879
 880
 881
 882 class DashPathBuilder : public APath::Scanner
 883 {
 884 public:
 885         DashPathBuilder(DashState& d)
 886         : path(NULL), ds(d)
 887         {
 888         }
 889
 890         virtual void move(double x, double y);
 891         virtual void line(double x, double y);
 892         virtual void bezier(double x1, double y1, double x2, double y2);
 893         virtual void bezier(double x1, double y1, double x2, double y2, double x3, double y3);
 894         //virtual void open(APath::Part*);
 895         virtual void close();
 896
 897         APath* get() { return new APath(path); }
 898
 899 private:
 900         APath::Part* path;
 901         DashState& ds;
 902 };
 903
 904 void DashPathBuilder::move(double x, double y)
 905 {
 906         PATHDB(printf("move(%f, %f) first %d\n", x, y, first));
 907         path = APath::join(path, APath::move(x, y));
 908 }
 909
 910 void DashPathBuilder::line(double x, double y)
 911 {
 912         PATHDB(printf("line(%f, %f)\n", x, y));
 913
 914         double l = sqrt(x * x + y * y);
 915         double ux = x / l;
 916         double uy = y / l;
 917         double totx = 0;
 918         double toty = 0;
 919
 920         for (;;)
 921         {
 922                 int cnt = ds.raw_count();
 923                 double l1 = double(cnt) / (1 << DashState::fract_bits);
 924
 925                 if (l1 >= l)
 926                         break;
 927
 928                 double x1 = ux * l1;
 929                 double y1 = uy * l1;
 930
 931                 APath::Part* p = ds.is_on() ? APath::line(x1, y1) : APath::move(x1, y1);
 932                 path = APath::join(path, p);
 933
 934                 totx += x1;
 935                 toty += y1;
 936
 937                 ds.advance(cnt);
 938                 l -= l1;
 939         }
 940
 941         x -= totx;
 942         y -= toty;
 943
 944         if (x || y)
 945         {
 946                 APath::Part* p = ds.is_on() ? APath::line(x, y) : APath::move(x, y);
 947                 path = APath::join(path, p);
 948                 ds.advance(int(l * (1 << DashState::fract_bits)));
 949         }
 950 }
 951
 952 void DashPathBuilder::bezier(double x1, double y1, double x, double y)
 953 {
 954         PATHDB(printf("bezier(%f, %f, %f, %f)\n", x1, y1, x, y));
 955
 956         const int max_levels = 15;
 957
 958         struct
 959         {
 960                 double x;
 961                 double y;
 962         } *s, stack[max_levels];
 963
 964         s = stack;
 965
 966         DEBUG_LOOPS(int n = 0);
 967
 968         for (;;)
 969         {
 970                 DEBUG_LOOPS(++n);
 971
 972                 DEBUG_BEZIER(printf("bezier: %f,%f %f,%f level %d\n",
 973                                         x1, y1, x, y, (s - stack) / 2));
 974
 975                 DEBUG_LOOPS(if (n > 200) printf("too many iterations: %f,%f %f,%f\n", x1,y1,x,y); else)
 976                 if (s < stack + max_levels - 2)
 977                 {
 978                         double dx = fabs(x - 2 * x1);
 979                         double dy = fabs(y - 2 * y1);
 980                         if (dx < dy) dx = dy;
 981
 982                         if (dx > 1)
 983                         {
 984                                 DEBUG_BEZIER(printf("bezier: split\n"));
 985                                 double x2 = (x1 + x) / 2;
 986                                 double y2 = (y1 + y) / 2;
 987                                 x1 /= 2;
 988                                 y1 /= 2;
 989                                 double x3 = (x1 + x2) / 2;
 990                                 double y3 = (y1 + y2) / 2;
 991                                 s->x = x - x3;
 992                                 s->y = y - y3;
 993                                 ++s;
 994                                 s->x = x2 - x3;
 995                                 s->y = y2 - y3;
 996                                 ++s;
 997                                 x = x3;
 998                                 y = y3;
 999                                 continue;
1000                         }
1001
1002                         double midx = (2 * x1 + x) / 4;
1003                         double midy = (2 * y1 + y) / 4;
1004
1005                         DEBUG_BEZIER(printf("bezier: line %f,%f + line %f,%f\n", midx, midy, x - midx, y - midy));
1006
1007                         line(midx, midy);
1008                         line(x - midx, y - midy);
1009                 }
1010
1011                 if (s == stack)
1012                         break;
1013
1014                 --s;
1015                 x1 = s->x;
1016                 y1 = s->y;
1017                 --s;
1018                 x = s->x;
1019                 y = s->y;
1020         }
1021
1022         DEBUG_BEZIER(printf("bezier: done\n"));
1023 }
1024
1025 void DashPathBuilder::bezier(double x1, double y1, double x2, double y2, double x, double y)
1026 {
1027         PATHDB(printf("bezier(%f, %f, %f, %f, %f, %f)\n", x1, y1, x2, y2, x, y));
1028
1029         const int max_levels = 22;
1030
1031         struct
1032         {
1033                 double x;
1034                 double y;
1035         } *s, stack[max_levels];
1036
1037         s = stack;
1038
1039         DEBUG_LOOPS(int n = 0);
1040
1041         for (;;)
1042         {
1043                 DEBUG_LOOPS(if (++n > 400) printf("too many iterations: %f,%f %f,%f %f,%f\n", x1,y1,x2,y2,x,y); else)
1044                 if (s < stack + max_levels - 3)
1045                 {
1046                         double dx = fabs(x - x1 - x2);
1047                         double dy = fabs(y - y1 - y2);
1048                         if (dx < dy) dx = dy;
1049
1050                         if (dx > 1)
1051                         {
1052                                 double xa = (x1 + x2) / 2;
1053                                 double ya = (y1 + y2) / 2;
1054                                 double xb = (x2 + x) / 2;
1055                                 double yb = (y2 + y) / 2;
1056                                 x1 /= 2;
1057                                 y1 /= 2;
1058                                 x2 = (xa + x1) / 2;
1059                                 y2 = (ya + y1) / 2;
1060                                 double xc = (xa + xb) / 2;
1061                                 double yc = (ya + yb) / 2;
1062                                 double xe = (x2 + xc) / 2;
1063                                 double ye = (y2 + yc) / 2;
1064                                 s->x = xc - xe;
1065                                 s->y = yc - ye;
1066                                 ++s;
1067                                 s->x = xb - xe;
1068                                 s->y = yb - ye;
1069                                 ++s;
1070                                 s->x = x - xe;
1071                                 s->y = y - ye;
1072                                 ++s;
1073                                 x = xe;
1074                                 y = ye;
1075                                 continue;
1076                         }
1077                 }
1078
1079                 double midx = (3 * (x1 + x2) + x) / 8;
1080                 double midy = (3 * (y1 + y2) + y) / 8;
1081
1082                 line(midx, midy);
1083                 line(x - midx, y - midy);
1084
1085                 if (s == stack)
1086                         break;
1087
1088                 --s;
1089                 x = s->x;
1090                 y = s->y;
1091                 --s;
1092                 x2 = s->x;
1093                 y2 = s->y;
1094                 --s;
1095                 x1 = s->x;
1096                 y1 = s->y;
1097         }
1098
1099         DEBUG_BEZIER(printf("bezier: done\n"));
1100 }
1101
1102 void DashPathBuilder::close()
1103 {
1104         path = APath::close(path);
1105 }
1106
1107 APath* APath::make_dashes(DashState& ds) const
1108 {
1109 #if 0//DEBUG
1110         printf("make_dashes\n");
1111         print();
1112 #endif
1113
1114         DashPathBuilder builder(ds);
1115
1116         builder.scan(this);
1117
1118         APath* result = builder.get();
1119
1120 #if 0//DEBUG
1121         printf("result:\n");
1122         result->print();
1123 #endif
1124         return result;
1125 }