Subversion Repositories Kolibri OS

Rev

Go to most recent revision | Blame | Compare with Previous | Last modification | View Log | RSS feed

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