1 /*
   2  * Copyright (c) 2007, 2017, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.  Oracle designates this
   8  * particular file as subject to the "Classpath" exception as provided
   9  * by Oracle in the LICENSE file that accompanied this code.
  10  *
  11  * This code is distributed in the hope that it will be useful, but WITHOUT
  12  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14  * version 2 for more details (a copy is included in the LICENSE file that
  15  * accompanied this code).
  16  *
  17  * You should have received a copy of the GNU General Public License version
  18  * 2 along with this work; if not, write to the Free Software Foundation,
  19  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  20  *
  21  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  22  * or visit www.oracle.com if you need additional information or have any
  23  * questions.
  24  */
  25 
  26 package com.sun.marlin;
  27 
  28 import java.util.Arrays;
  29 
  30 import com.sun.javafx.geom.PathConsumer2D;
  31 
  32 // TODO: some of the arithmetic here is too verbose and prone to hard to
  33 // debug typos. We should consider making a small Point/Vector class that
  34 // has methods like plus(Point), minus(Point), dot(Point), cross(Point)and such
  35 public final class Stroker implements PathConsumer2D, MarlinConst {
  36 
  37     private static final int MOVE_TO = 0;
  38     private static final int DRAWING_OP_TO = 1; // ie. curve, line, or quad
  39     private static final int CLOSE = 2;
  40 
  41     /**
  42      * Constant value for join style.
  43      */
  44     public static final int JOIN_MITER = 0;
  45 
  46     /**
  47      * Constant value for join style.
  48      */
  49     public static final int JOIN_ROUND = 1;
  50 
  51     /**
  52      * Constant value for join style.
  53      */
  54     public static final int JOIN_BEVEL = 2;
  55 
  56     /**
  57      * Constant value for end cap style.
  58      */
  59     public static final int CAP_BUTT = 0;
  60 
  61     /**
  62      * Constant value for end cap style.
  63      */
  64     public static final int CAP_ROUND = 1;
  65 
  66     /**
  67      * Constant value for end cap style.
  68      */
  69     public static final int CAP_SQUARE = 2;
  70 
  71     // pisces used to use fixed point arithmetic with 16 decimal digits. I
  72     // didn't want to change the values of the constant below when I converted
  73     // it to floating point, so that's why the divisions by 2^16 are there.
  74     private static final float ROUND_JOIN_THRESHOLD = 1000.0f/65536.0f;
  75 
  76     private static final float C = 0.5522847498307933f;
  77 
  78     private static final int MAX_N_CURVES = 11;
  79 
  80     private PathConsumer2D out;
  81 
  82     private int capStyle;
  83     private int joinStyle;
  84 
  85     private float lineWidth2;
  86     private float invHalfLineWidth2Sq;
  87 
  88     private final float[] offset0 = new float[2];
  89     private final float[] offset1 = new float[2];
  90     private final float[] offset2 = new float[2];
  91     private final float[] miter = new float[2];
  92     private float miterLimitSq;
  93 
  94     private int prev;
  95 
  96     // The starting point of the path, and the slope there.
  97     private float sx0, sy0, sdx, sdy;
  98     // the current point and the slope there.
  99     private float cx0, cy0, cdx, cdy; // c stands for current
 100     // vectors that when added to (sx0,sy0) and (cx0,cy0) respectively yield the
 101     // first and last points on the left parallel path. Since this path is
 102     // parallel, it's slope at any point is parallel to the slope of the
 103     // original path (thought they may have different directions), so these
 104     // could be computed from sdx,sdy and cdx,cdy (and vice versa), but that
 105     // would be error prone and hard to read, so we keep these anyway.
 106     private float smx, smy, cmx, cmy;
 107 
 108     private final PolyStack reverse;
 109 
 110     // This is where the curve to be processed is put. We give it
 111     // enough room to store all curves.
 112     private final float[] middle = new float[MAX_N_CURVES * 6 + 2];
 113     private final float[] lp = new float[8];
 114     private final float[] rp = new float[8];
 115     private final float[] subdivTs = new float[MAX_N_CURVES - 1];
 116 
 117     // per-thread renderer context
 118     final RendererContext rdrCtx;
 119 
 120     // dirty curve
 121     final Curve curve;
 122 
 123     /**
 124      * Constructs a <code>Stroker</code>.
 125      * @param rdrCtx per-thread renderer context
 126      */
 127     Stroker(final RendererContext rdrCtx) {
 128         this.rdrCtx = rdrCtx;
 129 
 130         this.reverse = new PolyStack(rdrCtx);
 131         this.curve = rdrCtx.curve;
 132     }
 133 
 134     /**
 135      * Inits the <code>Stroker</code>.
 136      *
 137      * @param pc2d an output <code>PathConsumer2D</code>.
 138      * @param lineWidth the desired line width in pixels
 139      * @param capStyle the desired end cap style, one of
 140      * <code>CAP_BUTT</code>, <code>CAP_ROUND</code> or
 141      * <code>CAP_SQUARE</code>.
 142      * @param joinStyle the desired line join style, one of
 143      * <code>JOIN_MITER</code>, <code>JOIN_ROUND</code> or
 144      * <code>JOIN_BEVEL</code>.
 145      * @param miterLimit the desired miter limit
 146      * @return this instance
 147      */
 148     public Stroker init(PathConsumer2D pc2d,
 149               float lineWidth,
 150               int capStyle,
 151               int joinStyle,
 152               float miterLimit)
 153     {
 154         this.out = pc2d;
 155 
 156         this.lineWidth2 = lineWidth / 2.0f;
 157         this.invHalfLineWidth2Sq = 1.0f / (2.0f * lineWidth2 * lineWidth2);
 158         this.capStyle = capStyle;
 159         this.joinStyle = joinStyle;
 160 
 161         float limit = miterLimit * lineWidth2;
 162         this.miterLimitSq = limit * limit;
 163 
 164         this.prev = CLOSE;
 165 
 166         rdrCtx.stroking = 1;
 167 
 168         return this; // fluent API
 169     }
 170 
 171     /**
 172      * Disposes this stroker:
 173      * clean up before reusing this instance
 174      */
 175     void dispose() {
 176         reverse.dispose();
 177 
 178         if (DO_CLEAN_DIRTY) {
 179             // Force zero-fill dirty arrays:
 180             Arrays.fill(offset0, 0.0f);
 181             Arrays.fill(offset1, 0.0f);
 182             Arrays.fill(offset2, 0.0f);
 183             Arrays.fill(miter, 0.0f);
 184             Arrays.fill(middle, 0.0f);
 185             Arrays.fill(lp, 0.0f);
 186             Arrays.fill(rp, 0.0f);
 187             Arrays.fill(subdivTs, 0.0f);
 188         }
 189     }
 190 
 191     private static void computeOffset(final float lx, final float ly,
 192                                       final float w, final float[] m)
 193     {
 194         float len = lx*lx + ly*ly;
 195         if (len == 0.0f) {
 196             m[0] = 0.0f;
 197             m[1] = 0.0f;
 198         } else {
 199             len = (float) Math.sqrt(len);
 200             m[0] =  (ly * w) / len;
 201             m[1] = -(lx * w) / len;
 202         }
 203     }
 204 
 205     // Returns true if the vectors (dx1, dy1) and (dx2, dy2) are
 206     // clockwise (if dx1,dy1 needs to be rotated clockwise to close
 207     // the smallest angle between it and dx2,dy2).
 208     // This is equivalent to detecting whether a point q is on the right side
 209     // of a line passing through points p1, p2 where p2 = p1+(dx1,dy1) and
 210     // q = p2+(dx2,dy2), which is the same as saying p1, p2, q are in a
 211     // clockwise order.
 212     // NOTE: "clockwise" here assumes coordinates with 0,0 at the bottom left.
 213     private static boolean isCW(final float dx1, final float dy1,
 214                                 final float dx2, final float dy2)
 215     {
 216         return dx1 * dy2 <= dy1 * dx2;
 217     }
 218 
 219     private void drawRoundJoin(float x, float y,
 220                                float omx, float omy, float mx, float my,
 221                                boolean rev,
 222                                float threshold)
 223     {
 224         if ((omx == 0.0f && omy == 0.0f) || (mx == 0.0f && my == 0.0f)) {
 225             return;
 226         }
 227 
 228         float domx = omx - mx;
 229         float domy = omy - my;
 230         float len = domx*domx + domy*domy;
 231         if (len < threshold) {
 232             return;
 233         }
 234 
 235         if (rev) {
 236             omx = -omx;
 237             omy = -omy;
 238             mx  = -mx;
 239             my  = -my;
 240         }
 241         drawRoundJoin(x, y, omx, omy, mx, my, rev);
 242     }
 243 
 244     private void drawRoundJoin(float cx, float cy,
 245                                float omx, float omy,
 246                                float mx, float my,
 247                                boolean rev)
 248     {
 249         // The sign of the dot product of mx,my and omx,omy is equal to the
 250         // the sign of the cosine of ext
 251         // (ext is the angle between omx,omy and mx,my).
 252         final float cosext = omx * mx + omy * my;
 253         // If it is >=0, we know that abs(ext) is <= 90 degrees, so we only
 254         // need 1 curve to approximate the circle section that joins omx,omy
 255         // and mx,my.
 256         final int numCurves = (cosext >= 0.0f) ? 1 : 2;
 257 
 258         switch (numCurves) {
 259         case 1:
 260             drawBezApproxForArc(cx, cy, omx, omy, mx, my, rev);
 261             break;
 262         case 2:
 263             // we need to split the arc into 2 arcs spanning the same angle.
 264             // The point we want will be one of the 2 intersections of the
 265             // perpendicular bisector of the chord (omx,omy)->(mx,my) and the
 266             // circle. We could find this by scaling the vector
 267             // (omx+mx, omy+my)/2 so that it has length=lineWidth2 (and thus lies
 268             // on the circle), but that can have numerical problems when the angle
 269             // between omx,omy and mx,my is close to 180 degrees. So we compute a
 270             // normal of (omx,omy)-(mx,my). This will be the direction of the
 271             // perpendicular bisector. To get one of the intersections, we just scale
 272             // this vector that its length is lineWidth2 (this works because the
 273             // perpendicular bisector goes through the origin). This scaling doesn't
 274             // have numerical problems because we know that lineWidth2 divided by
 275             // this normal's length is at least 0.5 and at most sqrt(2)/2 (because
 276             // we know the angle of the arc is > 90 degrees).
 277             float nx = my - omy, ny = omx - mx;
 278             float nlen = (float) Math.sqrt(nx*nx + ny*ny);
 279             float scale = lineWidth2/nlen;
 280             float mmx = nx * scale, mmy = ny * scale;
 281 
 282             // if (isCW(omx, omy, mx, my) != isCW(mmx, mmy, mx, my)) then we've
 283             // computed the wrong intersection so we get the other one.
 284             // The test above is equivalent to if (rev).
 285             if (rev) {
 286                 mmx = -mmx;
 287                 mmy = -mmy;
 288             }
 289             drawBezApproxForArc(cx, cy, omx, omy, mmx, mmy, rev);
 290             drawBezApproxForArc(cx, cy, mmx, mmy, mx, my, rev);
 291             break;
 292         default:
 293         }
 294     }
 295 
 296     // the input arc defined by omx,omy and mx,my must span <= 90 degrees.
 297     private void drawBezApproxForArc(final float cx, final float cy,
 298                                      final float omx, final float omy,
 299                                      final float mx, final float my,
 300                                      boolean rev)
 301     {
 302         final float cosext2 = (omx * mx + omy * my) * invHalfLineWidth2Sq;
 303 
 304         // check round off errors producing cos(ext) > 1 and a NaN below
 305         // cos(ext) == 1 implies colinear segments and an empty join anyway
 306         if (cosext2 >= 0.5f) {
 307             // just return to avoid generating a flat curve:
 308             return;
 309         }
 310 
 311         // cv is the length of P1-P0 and P2-P3 divided by the radius of the arc
 312         // (so, cv assumes the arc has radius 1). P0, P1, P2, P3 are the points that
 313         // define the bezier curve we're computing.
 314         // It is computed using the constraints that P1-P0 and P3-P2 are parallel
 315         // to the arc tangents at the endpoints, and that |P1-P0|=|P3-P2|.
 316         float cv = (float) ((4.0d / 3.0d) * Math.sqrt(0.5d - cosext2) /
 317                             (1.0d + Math.sqrt(cosext2 + 0.5d)));
 318         // if clockwise, we need to negate cv.
 319         if (rev) { // rev is equivalent to isCW(omx, omy, mx, my)
 320             cv = -cv;
 321         }
 322         final float x1 = cx + omx;
 323         final float y1 = cy + omy;
 324         final float x2 = x1 - cv * omy;
 325         final float y2 = y1 + cv * omx;
 326 
 327         final float x4 = cx + mx;
 328         final float y4 = cy + my;
 329         final float x3 = x4 + cv * my;
 330         final float y3 = y4 - cv * mx;
 331 
 332         emitCurveTo(x1, y1, x2, y2, x3, y3, x4, y4, rev);
 333     }
 334 
 335     private void drawRoundCap(float cx, float cy, float mx, float my) {
 336         final float Cmx = C * mx;
 337         final float Cmy = C * my;
 338         emitCurveTo(cx + mx - Cmy, cy + my + Cmx,
 339                     cx - my + Cmx, cy + mx + Cmy,
 340                     cx - my,       cy + mx);
 341         emitCurveTo(cx - my - Cmx, cy + mx - Cmy,
 342                     cx - mx - Cmy, cy - my + Cmx,
 343                     cx - mx,       cy - my);
 344     }
 345 
 346     // Return the intersection point of the lines (x0, y0) -> (x1, y1)
 347     // and (x0p, y0p) -> (x1p, y1p) in m[off] and m[off+1]
 348     private static void computeMiter(final float x0, final float y0,
 349                                      final float x1, final float y1,
 350                                      final float x0p, final float y0p,
 351                                      final float x1p, final float y1p,
 352                                      final float[] m, int off)
 353     {
 354         float x10 = x1 - x0;
 355         float y10 = y1 - y0;
 356         float x10p = x1p - x0p;
 357         float y10p = y1p - y0p;
 358 
 359         // if this is 0, the lines are parallel. If they go in the
 360         // same direction, there is no intersection so m[off] and
 361         // m[off+1] will contain infinity, so no miter will be drawn.
 362         // If they go in the same direction that means that the start of the
 363         // current segment and the end of the previous segment have the same
 364         // tangent, in which case this method won't even be involved in
 365         // miter drawing because it won't be called by drawMiter (because
 366         // (mx == omx && my == omy) will be true, and drawMiter will return
 367         // immediately).
 368         float den = x10*y10p - x10p*y10;
 369         float t = x10p*(y0-y0p) - y10p*(x0-x0p);
 370         t /= den;
 371         m[off++] = x0 + t*x10;
 372         m[off]   = y0 + t*y10;
 373     }
 374 
 375     // Return the intersection point of the lines (x0, y0) -> (x1, y1)
 376     // and (x0p, y0p) -> (x1p, y1p) in m[off] and m[off+1]
 377     private static void safeComputeMiter(final float x0, final float y0,
 378                                          final float x1, final float y1,
 379                                          final float x0p, final float y0p,
 380                                          final float x1p, final float y1p,
 381                                          final float[] m, int off)
 382     {
 383         float x10 = x1 - x0;
 384         float y10 = y1 - y0;
 385         float x10p = x1p - x0p;
 386         float y10p = y1p - y0p;
 387 
 388         // if this is 0, the lines are parallel. If they go in the
 389         // same direction, there is no intersection so m[off] and
 390         // m[off+1] will contain infinity, so no miter will be drawn.
 391         // If they go in the same direction that means that the start of the
 392         // current segment and the end of the previous segment have the same
 393         // tangent, in which case this method won't even be involved in
 394         // miter drawing because it won't be called by drawMiter (because
 395         // (mx == omx && my == omy) will be true, and drawMiter will return
 396         // immediately).
 397         float den = x10*y10p - x10p*y10;
 398         if (den == 0.0f) {
 399             m[off++] = (x0 + x0p) / 2.0f;
 400             m[off]   = (y0 + y0p) / 2.0f;
 401             return;
 402         }
 403         float t = x10p*(y0-y0p) - y10p*(x0-x0p);
 404         t /= den;
 405         m[off++] = x0 + t*x10;
 406         m[off] = y0 + t*y10;
 407     }
 408 
 409     private void drawMiter(final float pdx, final float pdy,
 410                            final float x0, final float y0,
 411                            final float dx, final float dy,
 412                            float omx, float omy, float mx, float my,
 413                            boolean rev)
 414     {
 415         if ((mx == omx && my == omy) ||
 416             (pdx == 0.0f && pdy == 0.0f) ||
 417             (dx == 0.0f && dy == 0.0f))
 418         {
 419             return;
 420         }
 421 
 422         if (rev) {
 423             omx = -omx;
 424             omy = -omy;
 425             mx  = -mx;
 426             my  = -my;
 427         }
 428 
 429         computeMiter((x0 - pdx) + omx, (y0 - pdy) + omy, x0 + omx, y0 + omy,
 430                      (dx + x0) + mx, (dy + y0) + my, x0 + mx, y0 + my,
 431                      miter, 0);
 432 
 433         final float miterX = miter[0];
 434         final float miterY = miter[1];
 435         float lenSq = (miterX-x0)*(miterX-x0) + (miterY-y0)*(miterY-y0);
 436 
 437         // If the lines are parallel, lenSq will be either NaN or +inf
 438         // (actually, I'm not sure if the latter is possible. The important
 439         // thing is that -inf is not possible, because lenSq is a square).
 440         // For both of those values, the comparison below will fail and
 441         // no miter will be drawn, which is correct.
 442         if (lenSq < miterLimitSq) {
 443             emitLineTo(miterX, miterY, rev);
 444         }
 445     }
 446 
 447     @Override
 448     public void moveTo(float x0, float y0) {
 449         if (prev == DRAWING_OP_TO) {
 450             finish();
 451         }
 452         this.sx0 = this.cx0 = x0;
 453         this.sy0 = this.cy0 = y0;
 454         this.cdx = this.sdx = 1.0f;
 455         this.cdy = this.sdy = 0.0f;
 456         this.prev = MOVE_TO;
 457     }
 458 
 459     @Override
 460     public void lineTo(float x1, float y1) {
 461         float dx = x1 - cx0;
 462         float dy = y1 - cy0;
 463         if (dx == 0.0f && dy == 0.0f) {
 464             dx = 1.0f;
 465         }
 466         computeOffset(dx, dy, lineWidth2, offset0);
 467         final float mx = offset0[0];
 468         final float my = offset0[1];
 469 
 470         drawJoin(cdx, cdy, cx0, cy0, dx, dy, cmx, cmy, mx, my);
 471 
 472         emitLineTo(cx0 + mx, cy0 + my);
 473         emitLineTo( x1 + mx,  y1 + my);
 474 
 475         emitLineToRev(cx0 - mx, cy0 - my);
 476         emitLineToRev( x1 - mx,  y1 - my);
 477 
 478         this.cmx = mx;
 479         this.cmy = my;
 480         this.cdx = dx;
 481         this.cdy = dy;
 482         this.cx0 = x1;
 483         this.cy0 = y1;
 484         this.prev = DRAWING_OP_TO;
 485     }
 486 
 487     @Override
 488     public void closePath() {
 489         if (prev != DRAWING_OP_TO) {
 490             if (prev == CLOSE) {
 491                 return;
 492             }
 493             emitMoveTo(cx0, cy0 - lineWidth2);
 494             this.cmx = this.smx = 0.0f;
 495             this.cmy = this.smy = -lineWidth2;
 496             this.cdx = this.sdx = 1.0f;
 497             this.cdy = this.sdy = 0.0f;
 498             finish();
 499             return;
 500         }
 501 
 502         if (cx0 != sx0 || cy0 != sy0) {
 503             lineTo(sx0, sy0);
 504         }
 505 
 506         drawJoin(cdx, cdy, cx0, cy0, sdx, sdy, cmx, cmy, smx, smy);
 507 
 508         emitLineTo(sx0 + smx, sy0 + smy);
 509 
 510         emitMoveTo(sx0 - smx, sy0 - smy);
 511         emitReverse();
 512 
 513         this.prev = CLOSE;
 514         emitClose();
 515     }
 516 
 517     private void emitReverse() {
 518         reverse.popAll(out);
 519     }
 520 
 521     @Override
 522     public void pathDone() {
 523         if (prev == DRAWING_OP_TO) {
 524             finish();
 525         }
 526 
 527         out.pathDone();
 528 
 529         // this shouldn't matter since this object won't be used
 530         // after the call to this method.
 531         this.prev = CLOSE;
 532 
 533         // Dispose this instance:
 534         dispose();
 535     }
 536 
 537     private void finish() {
 538         if (capStyle == CAP_ROUND) {
 539             drawRoundCap(cx0, cy0, cmx, cmy);
 540         } else if (capStyle == CAP_SQUARE) {
 541             emitLineTo(cx0 - cmy + cmx, cy0 + cmx + cmy);
 542             emitLineTo(cx0 - cmy - cmx, cy0 + cmx - cmy);
 543         }
 544 
 545         emitReverse();
 546 
 547         if (capStyle == CAP_ROUND) {
 548             drawRoundCap(sx0, sy0, -smx, -smy);
 549         } else if (capStyle == CAP_SQUARE) {
 550             emitLineTo(sx0 + smy - smx, sy0 - smx - smy);
 551             emitLineTo(sx0 + smy + smx, sy0 - smx + smy);
 552         }
 553 
 554         emitClose();
 555     }
 556 
 557     private void emitMoveTo(final float x0, final float y0) {
 558         out.moveTo(x0, y0);
 559     }
 560 
 561     private void emitLineTo(final float x1, final float y1) {
 562         out.lineTo(x1, y1);
 563     }
 564 
 565     private void emitLineToRev(final float x1, final float y1) {
 566         reverse.pushLine(x1, y1);
 567     }
 568 
 569     private void emitLineTo(final float x1, final float y1,
 570                             final boolean rev)
 571     {
 572         if (rev) {
 573             emitLineToRev(x1, y1);
 574         } else {
 575             emitLineTo(x1, y1);
 576         }
 577     }
 578 
 579     private void emitQuadTo(final float x1, final float y1,
 580                             final float x2, final float y2)
 581     {
 582         out.quadTo(x1, y1, x2, y2);
 583     }
 584 
 585     private void emitQuadToRev(final float x0, final float y0,
 586                                final float x1, final float y1)
 587     {
 588         reverse.pushQuad(x0, y0, x1, y1);
 589     }
 590 
 591     private void emitCurveTo(final float x1, final float y1,
 592                              final float x2, final float y2,
 593                              final float x3, final float y3)
 594     {
 595         out.curveTo(x1, y1, x2, y2, x3, y3);
 596     }
 597 
 598     private void emitCurveToRev(final float x0, final float y0,
 599                                 final float x1, final float y1,
 600                                 final float x2, final float y2)
 601     {
 602         reverse.pushCubic(x0, y0, x1, y1, x2, y2);
 603     }
 604 
 605     private void emitCurveTo(final float x0, final float y0,
 606                              final float x1, final float y1,
 607                              final float x2, final float y2,
 608                              final float x3, final float y3, final boolean rev)
 609     {
 610         if (rev) {
 611             reverse.pushCubic(x0, y0, x1, y1, x2, y2);
 612         } else {
 613             out.curveTo(x1, y1, x2, y2, x3, y3);
 614         }
 615     }
 616 
 617     private void emitClose() {
 618         out.closePath();
 619     }
 620 
 621     private void drawJoin(float pdx, float pdy,
 622                           float x0, float y0,
 623                           float dx, float dy,
 624                           float omx, float omy,
 625                           float mx, float my)
 626     {
 627         if (prev != DRAWING_OP_TO) {
 628             emitMoveTo(x0 + mx, y0 + my);
 629             this.sdx = dx;
 630             this.sdy = dy;
 631             this.smx = mx;
 632             this.smy = my;
 633         } else {
 634             boolean cw = isCW(pdx, pdy, dx, dy);
 635             if (joinStyle == JOIN_MITER) {
 636                 drawMiter(pdx, pdy, x0, y0, dx, dy, omx, omy, mx, my, cw);
 637             } else if (joinStyle == JOIN_ROUND) {
 638                 drawRoundJoin(x0, y0,
 639                               omx, omy,
 640                               mx, my, cw,
 641                               ROUND_JOIN_THRESHOLD);
 642             }
 643             emitLineTo(x0, y0, !cw);
 644         }
 645         prev = DRAWING_OP_TO;
 646     }
 647 
 648     private static boolean within(final float x1, final float y1,
 649                                   final float x2, final float y2,
 650                                   final float ERR)
 651     {
 652         assert ERR > 0 : "";
 653         // compare taxicab distance. ERR will always be small, so using
 654         // true distance won't give much benefit
 655         return (Helpers.within(x1, x2, ERR) &&  // we want to avoid calling Math.abs
 656                 Helpers.within(y1, y2, ERR)); // this is just as good.
 657     }
 658 
 659     private void getLineOffsets(float x1, float y1,
 660                                 float x2, float y2,
 661                                 float[] left, float[] right) {
 662         computeOffset(x2 - x1, y2 - y1, lineWidth2, offset0);
 663         final float mx = offset0[0];
 664         final float my = offset0[1];
 665         left[0] = x1 + mx;
 666         left[1] = y1 + my;
 667         left[2] = x2 + mx;
 668         left[3] = y2 + my;
 669         right[0] = x1 - mx;
 670         right[1] = y1 - my;
 671         right[2] = x2 - mx;
 672         right[3] = y2 - my;
 673     }
 674 
 675     private int computeOffsetCubic(float[] pts, final int off,
 676                                    float[] leftOff, float[] rightOff)
 677     {
 678         // if p1=p2 or p3=p4 it means that the derivative at the endpoint
 679         // vanishes, which creates problems with computeOffset. Usually
 680         // this happens when this stroker object is trying to widen
 681         // a curve with a cusp. What happens is that curveTo splits
 682         // the input curve at the cusp, and passes it to this function.
 683         // because of inaccuracies in the splitting, we consider points
 684         // equal if they're very close to each other.
 685         final float x1 = pts[off + 0], y1 = pts[off + 1];
 686         final float x2 = pts[off + 2], y2 = pts[off + 3];
 687         final float x3 = pts[off + 4], y3 = pts[off + 5];
 688         final float x4 = pts[off + 6], y4 = pts[off + 7];
 689 
 690         float dx4 = x4 - x3;
 691         float dy4 = y4 - y3;
 692         float dx1 = x2 - x1;
 693         float dy1 = y2 - y1;
 694 
 695         // if p1 == p2 && p3 == p4: draw line from p1->p4, unless p1 == p4,
 696         // in which case ignore if p1 == p2
 697         final boolean p1eqp2 = within(x1, y1, x2, y2, 6.0f * Math.ulp(y2));
 698         final boolean p3eqp4 = within(x3, y3, x4, y4, 6.0f * Math.ulp(y4));
 699         if (p1eqp2 && p3eqp4) {
 700             getLineOffsets(x1, y1, x4, y4, leftOff, rightOff);
 701             return 4;
 702         } else if (p1eqp2) {
 703             dx1 = x3 - x1;
 704             dy1 = y3 - y1;
 705         } else if (p3eqp4) {
 706             dx4 = x4 - x2;
 707             dy4 = y4 - y2;
 708         }
 709 
 710         // if p2-p1 and p4-p3 are parallel, that must mean this curve is a line
 711         float dotsq = (dx1 * dx4 + dy1 * dy4);
 712         dotsq *= dotsq;
 713         float l1sq = dx1 * dx1 + dy1 * dy1, l4sq = dx4 * dx4 + dy4 * dy4;
 714         if (Helpers.within(dotsq, l1sq * l4sq, 4.0f * Math.ulp(dotsq))) {
 715             getLineOffsets(x1, y1, x4, y4, leftOff, rightOff);
 716             return 4;
 717         }
 718 
 719 //      What we're trying to do in this function is to approximate an ideal
 720 //      offset curve (call it I) of the input curve B using a bezier curve Bp.
 721 //      The constraints I use to get the equations are:
 722 //
 723 //      1. The computed curve Bp should go through I(0) and I(1). These are
 724 //      x1p, y1p, x4p, y4p, which are p1p and p4p. We still need to find
 725 //      4 variables: the x and y components of p2p and p3p (i.e. x2p, y2p, x3p, y3p).
 726 //
 727 //      2. Bp should have slope equal in absolute value to I at the endpoints. So,
 728 //      (by the way, the operator || in the comments below means "aligned with".
 729 //      It is defined on vectors, so when we say I'(0) || Bp'(0) we mean that
 730 //      vectors I'(0) and Bp'(0) are aligned, which is the same as saying
 731 //      that the tangent lines of I and Bp at 0 are parallel. Mathematically
 732 //      this means (I'(t) || Bp'(t)) <==> (I'(t) = c * Bp'(t)) where c is some
 733 //      nonzero constant.)
 734 //      I'(0) || Bp'(0) and I'(1) || Bp'(1). Obviously, I'(0) || B'(0) and
 735 //      I'(1) || B'(1); therefore, Bp'(0) || B'(0) and Bp'(1) || B'(1).
 736 //      We know that Bp'(0) || (p2p-p1p) and Bp'(1) || (p4p-p3p) and the same
 737 //      is true for any bezier curve; therefore, we get the equations
 738 //          (1) p2p = c1 * (p2-p1) + p1p
 739 //          (2) p3p = c2 * (p4-p3) + p4p
 740 //      We know p1p, p4p, p2, p1, p3, and p4; therefore, this reduces the number
 741 //      of unknowns from 4 to 2 (i.e. just c1 and c2).
 742 //      To eliminate these 2 unknowns we use the following constraint:
 743 //
 744 //      3. Bp(0.5) == I(0.5). Bp(0.5)=(x,y) and I(0.5)=(xi,yi), and I should note
 745 //      that I(0.5) is *the only* reason for computing dxm,dym. This gives us
 746 //          (3) Bp(0.5) = (p1p + 3 * (p2p + p3p) + p4p)/8, which is equivalent to
 747 //          (4) p2p + p3p = (Bp(0.5)*8 - p1p - p4p) / 3
 748 //      We can substitute (1) and (2) from above into (4) and we get:
 749 //          (5) c1*(p2-p1) + c2*(p4-p3) = (Bp(0.5)*8 - p1p - p4p)/3 - p1p - p4p
 750 //      which is equivalent to
 751 //          (6) c1*(p2-p1) + c2*(p4-p3) = (4/3) * (Bp(0.5) * 2 - p1p - p4p)
 752 //
 753 //      The right side of this is a 2D vector, and we know I(0.5), which gives us
 754 //      Bp(0.5), which gives us the value of the right side.
 755 //      The left side is just a matrix vector multiplication in disguise. It is
 756 //
 757 //      [x2-x1, x4-x3][c1]
 758 //      [y2-y1, y4-y3][c2]
 759 //      which, is equal to
 760 //      [dx1, dx4][c1]
 761 //      [dy1, dy4][c2]
 762 //      At this point we are left with a simple linear system and we solve it by
 763 //      getting the inverse of the matrix above. Then we use [c1,c2] to compute
 764 //      p2p and p3p.
 765 
 766         float x = (x1 + 3.0f * (x2 + x3) + x4) / 8.0f;
 767         float y = (y1 + 3.0f * (y2 + y3) + y4) / 8.0f;
 768         // (dxm,dym) is some tangent of B at t=0.5. This means it's equal to
 769         // c*B'(0.5) for some constant c.
 770         float dxm = x3 + x4 - x1 - x2, dym = y3 + y4 - y1 - y2;
 771 
 772         // this computes the offsets at t=0, 0.5, 1, using the property that
 773         // for any bezier curve the vectors p2-p1 and p4-p3 are parallel to
 774         // the (dx/dt, dy/dt) vectors at the endpoints.
 775         computeOffset(dx1, dy1, lineWidth2, offset0);
 776         computeOffset(dxm, dym, lineWidth2, offset1);
 777         computeOffset(dx4, dy4, lineWidth2, offset2);
 778         float x1p = x1 + offset0[0]; // start
 779         float y1p = y1 + offset0[1]; // point
 780         float xi  = x  + offset1[0]; // interpolation
 781         float yi  = y  + offset1[1]; // point
 782         float x4p = x4 + offset2[0]; // end
 783         float y4p = y4 + offset2[1]; // point
 784 
 785         float invdet43 = 4.0f / (3.0f * (dx1 * dy4 - dy1 * dx4));
 786 
 787         float two_pi_m_p1_m_p4x = 2.0f * xi - x1p - x4p;
 788         float two_pi_m_p1_m_p4y = 2.0f * yi - y1p - y4p;
 789         float c1 = invdet43 * (dy4 * two_pi_m_p1_m_p4x - dx4 * two_pi_m_p1_m_p4y);
 790         float c2 = invdet43 * (dx1 * two_pi_m_p1_m_p4y - dy1 * two_pi_m_p1_m_p4x);
 791 
 792         float x2p, y2p, x3p, y3p;
 793         x2p = x1p + c1*dx1;
 794         y2p = y1p + c1*dy1;
 795         x3p = x4p + c2*dx4;
 796         y3p = y4p + c2*dy4;
 797 
 798         leftOff[0] = x1p; leftOff[1] = y1p;
 799         leftOff[2] = x2p; leftOff[3] = y2p;
 800         leftOff[4] = x3p; leftOff[5] = y3p;
 801         leftOff[6] = x4p; leftOff[7] = y4p;
 802 
 803         x1p = x1 - offset0[0]; y1p = y1 - offset0[1];
 804         xi = xi - 2.0f * offset1[0]; yi = yi - 2.0f * offset1[1];
 805         x4p = x4 - offset2[0]; y4p = y4 - offset2[1];
 806 
 807         two_pi_m_p1_m_p4x = 2.0f * xi - x1p - x4p;
 808         two_pi_m_p1_m_p4y = 2.0f * yi - y1p - y4p;
 809         c1 = invdet43 * (dy4 * two_pi_m_p1_m_p4x - dx4 * two_pi_m_p1_m_p4y);
 810         c2 = invdet43 * (dx1 * two_pi_m_p1_m_p4y - dy1 * two_pi_m_p1_m_p4x);
 811 
 812         x2p = x1p + c1*dx1;
 813         y2p = y1p + c1*dy1;
 814         x3p = x4p + c2*dx4;
 815         y3p = y4p + c2*dy4;
 816 
 817         rightOff[0] = x1p; rightOff[1] = y1p;
 818         rightOff[2] = x2p; rightOff[3] = y2p;
 819         rightOff[4] = x3p; rightOff[5] = y3p;
 820         rightOff[6] = x4p; rightOff[7] = y4p;
 821         return 8;
 822     }
 823 
 824     // compute offset curves using bezier spline through t=0.5 (i.e.
 825     // ComputedCurve(0.5) == IdealParallelCurve(0.5))
 826     // return the kind of curve in the right and left arrays.
 827     private int computeOffsetQuad(float[] pts, final int off,
 828                                   float[] leftOff, float[] rightOff)
 829     {
 830         final float x1 = pts[off + 0], y1 = pts[off + 1];
 831         final float x2 = pts[off + 2], y2 = pts[off + 3];
 832         final float x3 = pts[off + 4], y3 = pts[off + 5];
 833 
 834         final float dx3 = x3 - x2;
 835         final float dy3 = y3 - y2;
 836         final float dx1 = x2 - x1;
 837         final float dy1 = y2 - y1;
 838 
 839         // if p1=p2 or p3=p4 it means that the derivative at the endpoint
 840         // vanishes, which creates problems with computeOffset. Usually
 841         // this happens when this stroker object is trying to widen
 842         // a curve with a cusp. What happens is that curveTo splits
 843         // the input curve at the cusp, and passes it to this function.
 844         // because of inaccuracies in the splitting, we consider points
 845         // equal if they're very close to each other.
 846 
 847         // if p1 == p2 && p3 == p4: draw line from p1->p4, unless p1 == p4,
 848         // in which case ignore.
 849         final boolean p1eqp2 = within(x1, y1, x2, y2, 6.0f * Math.ulp(y2));
 850         final boolean p2eqp3 = within(x2, y2, x3, y3, 6.0f * Math.ulp(y3));
 851         if (p1eqp2 || p2eqp3) {
 852             getLineOffsets(x1, y1, x3, y3, leftOff, rightOff);
 853             return 4;
 854         }
 855 
 856         // if p2-p1 and p4-p3 are parallel, that must mean this curve is a line
 857         float dotsq = (dx1 * dx3 + dy1 * dy3);
 858         dotsq *= dotsq;
 859         float l1sq = dx1 * dx1 + dy1 * dy1, l3sq = dx3 * dx3 + dy3 * dy3;
 860         if (Helpers.within(dotsq, l1sq * l3sq, 4.0f * Math.ulp(dotsq))) {
 861             getLineOffsets(x1, y1, x3, y3, leftOff, rightOff);
 862             return 4;
 863         }
 864 
 865         // this computes the offsets at t=0, 0.5, 1, using the property that
 866         // for any bezier curve the vectors p2-p1 and p4-p3 are parallel to
 867         // the (dx/dt, dy/dt) vectors at the endpoints.
 868         computeOffset(dx1, dy1, lineWidth2, offset0);
 869         computeOffset(dx3, dy3, lineWidth2, offset1);
 870 
 871         float x1p = x1 + offset0[0]; // start
 872         float y1p = y1 + offset0[1]; // point
 873         float x3p = x3 + offset1[0]; // end
 874         float y3p = y3 + offset1[1]; // point
 875         safeComputeMiter(x1p, y1p, x1p+dx1, y1p+dy1, x3p, y3p, x3p-dx3, y3p-dy3, leftOff, 2);
 876         leftOff[0] = x1p; leftOff[1] = y1p;
 877         leftOff[4] = x3p; leftOff[5] = y3p;
 878 
 879         x1p = x1 - offset0[0]; y1p = y1 - offset0[1];
 880         x3p = x3 - offset1[0]; y3p = y3 - offset1[1];
 881         safeComputeMiter(x1p, y1p, x1p+dx1, y1p+dy1, x3p, y3p, x3p-dx3, y3p-dy3, rightOff, 2);
 882         rightOff[0] = x1p; rightOff[1] = y1p;
 883         rightOff[4] = x3p; rightOff[5] = y3p;
 884         return 6;
 885     }
 886 
 887     // finds values of t where the curve in pts should be subdivided in order
 888     // to get good offset curves a distance of w away from the middle curve.
 889     // Stores the points in ts, and returns how many of them there were.
 890     private static int findSubdivPoints(final Curve c, float[] pts, float[] ts,
 891                                         final int type, final float w)
 892     {
 893         final float x12 = pts[2] - pts[0];
 894         final float y12 = pts[3] - pts[1];
 895         // if the curve is already parallel to either axis we gain nothing
 896         // from rotating it.
 897         if (y12 != 0.0f && x12 != 0.0f) {
 898             // we rotate it so that the first vector in the control polygon is
 899             // parallel to the x-axis. This will ensure that rotated quarter
 900             // circles won't be subdivided.
 901             final float hypot = (float) Math.sqrt(x12 * x12 + y12 * y12);
 902             final float cos = x12 / hypot;
 903             final float sin = y12 / hypot;
 904             final float x1 = cos * pts[0] + sin * pts[1];
 905             final float y1 = cos * pts[1] - sin * pts[0];
 906             final float x2 = cos * pts[2] + sin * pts[3];
 907             final float y2 = cos * pts[3] - sin * pts[2];
 908             final float x3 = cos * pts[4] + sin * pts[5];
 909             final float y3 = cos * pts[5] - sin * pts[4];
 910 
 911             switch(type) {
 912             case 8:
 913                 final float x4 = cos * pts[6] + sin * pts[7];
 914                 final float y4 = cos * pts[7] - sin * pts[6];
 915                 c.set(x1, y1, x2, y2, x3, y3, x4, y4);
 916                 break;
 917             case 6:
 918                 c.set(x1, y1, x2, y2, x3, y3);
 919                 break;
 920             default:
 921             }
 922         } else {
 923             c.set(pts, type);
 924         }
 925 
 926         int ret = 0;
 927         // we subdivide at values of t such that the remaining rotated
 928         // curves are monotonic in x and y.
 929         ret += c.dxRoots(ts, ret);
 930         ret += c.dyRoots(ts, ret);
 931         // subdivide at inflection points.
 932         if (type == 8) {
 933             // quadratic curves can't have inflection points
 934             ret += c.infPoints(ts, ret);
 935         }
 936 
 937         // now we must subdivide at points where one of the offset curves will have
 938         // a cusp. This happens at ts where the radius of curvature is equal to w.
 939         ret += c.rootsOfROCMinusW(ts, ret, w, 0.0001f);
 940 
 941         ret = Helpers.filterOutNotInAB(ts, 0, ret, 0.0001f, 0.9999f);
 942         Helpers.isort(ts, 0, ret);
 943         return ret;
 944     }
 945 
 946     @Override public void curveTo(float x1, float y1,
 947                                   float x2, float y2,
 948                                   float x3, float y3)
 949     {
 950         final float[] mid = middle;
 951 
 952         mid[0] = cx0; mid[1] = cy0;
 953         mid[2] = x1;  mid[3] = y1;
 954         mid[4] = x2;  mid[5] = y2;
 955         mid[6] = x3;  mid[7] = y3;
 956 
 957         // need these so we can update the state at the end of this method
 958         final float xf = mid[6], yf = mid[7];
 959         float dxs = mid[2] - mid[0];
 960         float dys = mid[3] - mid[1];
 961         float dxf = mid[6] - mid[4];
 962         float dyf = mid[7] - mid[5];
 963 
 964         boolean p1eqp2 = (dxs == 0.0f && dys == 0.0f);
 965         boolean p3eqp4 = (dxf == 0.0f && dyf == 0.0f);
 966         if (p1eqp2) {
 967             dxs = mid[4] - mid[0];
 968             dys = mid[5] - mid[1];
 969             if (dxs == 0.0f && dys == 0.0f) {
 970                 dxs = mid[6] - mid[0];
 971                 dys = mid[7] - mid[1];
 972             }
 973         }
 974         if (p3eqp4) {
 975             dxf = mid[6] - mid[2];
 976             dyf = mid[7] - mid[3];
 977             if (dxf == 0.0f && dyf == 0.0f) {
 978                 dxf = mid[6] - mid[0];
 979                 dyf = mid[7] - mid[1];
 980             }
 981         }
 982         if (dxs == 0.0f && dys == 0.0f) {
 983             // this happens if the "curve" is just a point
 984             lineTo(mid[0], mid[1]);
 985             return;
 986         }
 987 
 988         // if these vectors are too small, normalize them, to avoid future
 989         // precision problems.
 990         if (Math.abs(dxs) < 0.1f && Math.abs(dys) < 0.1f) {
 991             float len = (float) Math.sqrt(dxs*dxs + dys*dys);
 992             dxs /= len;
 993             dys /= len;
 994         }
 995         if (Math.abs(dxf) < 0.1f && Math.abs(dyf) < 0.1f) {
 996             float len = (float) Math.sqrt(dxf*dxf + dyf*dyf);
 997             dxf /= len;
 998             dyf /= len;
 999         }
1000 
1001         computeOffset(dxs, dys, lineWidth2, offset0);
1002         drawJoin(cdx, cdy, cx0, cy0, dxs, dys, cmx, cmy, offset0[0], offset0[1]);
1003 
1004         final int nSplits = findSubdivPoints(curve, mid, subdivTs, 8, lineWidth2);
1005 
1006         float prevT = 0.0f;
1007         for (int i = 0, off = 0; i < nSplits; i++, off += 6) {
1008             final float t = subdivTs[i];
1009             Helpers.subdivideCubicAt((t - prevT) / (1.0f - prevT),
1010                                      mid, off, mid, off, mid, off + 6);
1011             prevT = t;
1012         }
1013 
1014         final float[] l = lp;
1015         final float[] r = rp;
1016 
1017         int kind = 0;
1018         for (int i = 0, off = 0; i <= nSplits; i++, off += 6) {
1019             kind = computeOffsetCubic(mid, off, l, r);
1020 
1021             emitLineTo(l[0], l[1]);
1022 
1023             switch(kind) {
1024             case 8:
1025                 emitCurveTo(l[2], l[3], l[4], l[5], l[6], l[7]);
1026                 emitCurveToRev(r[0], r[1], r[2], r[3], r[4], r[5]);
1027                 break;
1028             case 4:
1029                 emitLineTo(l[2], l[3]);
1030                 emitLineToRev(r[0], r[1]);
1031                 break;
1032             default:
1033             }
1034             emitLineToRev(r[kind - 2], r[kind - 1]);
1035         }
1036 
1037         this.cmx = (l[kind - 2] - r[kind - 2]) / 2.0f;
1038         this.cmy = (l[kind - 1] - r[kind - 1]) / 2.0f;
1039         this.cdx = dxf;
1040         this.cdy = dyf;
1041         this.cx0 = xf;
1042         this.cy0 = yf;
1043         this.prev = DRAWING_OP_TO;
1044     }
1045 
1046     @Override public void quadTo(float x1, float y1, float x2, float y2) {
1047         final float[] mid = middle;
1048 
1049         mid[0] = cx0; mid[1] = cy0;
1050         mid[2] = x1;  mid[3] = y1;
1051         mid[4] = x2;  mid[5] = y2;
1052 
1053         // need these so we can update the state at the end of this method
1054         final float xf = mid[4], yf = mid[5];
1055         float dxs = mid[2] - mid[0];
1056         float dys = mid[3] - mid[1];
1057         float dxf = mid[4] - mid[2];
1058         float dyf = mid[5] - mid[3];
1059         if ((dxs == 0.0f && dys == 0.0f) || (dxf == 0.0f && dyf == 0.0f)) {
1060             dxs = dxf = mid[4] - mid[0];
1061             dys = dyf = mid[5] - mid[1];
1062         }
1063         if (dxs == 0.0f && dys == 0.0f) {
1064             // this happens if the "curve" is just a point
1065             lineTo(mid[0], mid[1]);
1066             return;
1067         }
1068         // if these vectors are too small, normalize them, to avoid future
1069         // precision problems.
1070         if (Math.abs(dxs) < 0.1f && Math.abs(dys) < 0.1f) {
1071             float len = (float) Math.sqrt(dxs*dxs + dys*dys);
1072             dxs /= len;
1073             dys /= len;
1074         }
1075         if (Math.abs(dxf) < 0.1f && Math.abs(dyf) < 0.1f) {
1076             float len = (float) Math.sqrt(dxf*dxf + dyf*dyf);
1077             dxf /= len;
1078             dyf /= len;
1079         }
1080 
1081         computeOffset(dxs, dys, lineWidth2, offset0);
1082         drawJoin(cdx, cdy, cx0, cy0, dxs, dys, cmx, cmy, offset0[0], offset0[1]);
1083 
1084         int nSplits = findSubdivPoints(curve, mid, subdivTs, 6, lineWidth2);
1085 
1086         float prevt = 0.0f;
1087         for (int i = 0, off = 0; i < nSplits; i++, off += 4) {
1088             final float t = subdivTs[i];
1089             Helpers.subdivideQuadAt((t - prevt) / (1.0f - prevt),
1090                                     mid, off, mid, off, mid, off + 4);
1091             prevt = t;
1092         }
1093 
1094         final float[] l = lp;
1095         final float[] r = rp;
1096 
1097         int kind = 0;
1098         for (int i = 0, off = 0; i <= nSplits; i++, off += 4) {
1099             kind = computeOffsetQuad(mid, off, l, r);
1100 
1101             emitLineTo(l[0], l[1]);
1102 
1103             switch(kind) {
1104             case 6:
1105                 emitQuadTo(l[2], l[3], l[4], l[5]);
1106                 emitQuadToRev(r[0], r[1], r[2], r[3]);
1107                 break;
1108             case 4:
1109                 emitLineTo(l[2], l[3]);
1110                 emitLineToRev(r[0], r[1]);
1111                 break;
1112             default:
1113             }
1114             emitLineToRev(r[kind - 2], r[kind - 1]);
1115         }
1116 
1117         this.cmx = (l[kind - 2] - r[kind - 2]) / 2.0f;
1118         this.cmy = (l[kind - 1] - r[kind - 1]) / 2.0f;
1119         this.cdx = dxf;
1120         this.cdy = dyf;
1121         this.cx0 = xf;
1122         this.cy0 = yf;
1123         this.prev = DRAWING_OP_TO;
1124     }
1125 
1126     // a stack of polynomial curves where each curve shares endpoints with
1127     // adjacent ones.
1128     static final class PolyStack {
1129         private static final byte TYPE_LINETO  = (byte) 0;
1130         private static final byte TYPE_QUADTO  = (byte) 1;
1131         private static final byte TYPE_CUBICTO = (byte) 2;
1132 
1133         // curves capacity = edges count (8192) = edges x 2 (coords)
1134         private static final int INITIAL_CURVES_COUNT = INITIAL_EDGES_COUNT << 1;
1135 
1136         // types capacity = edges count (4096)
1137         private static final int INITIAL_TYPES_COUNT = INITIAL_EDGES_COUNT;
1138 
1139         float[] curves;
1140         int end;
1141         byte[] curveTypes;
1142         int numCurves;
1143 
1144         // per-thread renderer context
1145         final RendererContext rdrCtx;
1146 
1147         // curves ref (dirty)
1148         final FloatArrayCache.Reference curves_ref;
1149         // curveTypes ref (dirty)
1150         final ByteArrayCache.Reference curveTypes_ref;
1151 
1152         // used marks (stats only)
1153         int curveTypesUseMark;
1154         int curvesUseMark;
1155 
1156         /**
1157          * Constructor
1158          * @param rdrCtx per-thread renderer context
1159          */
1160         PolyStack(final RendererContext rdrCtx) {
1161             this.rdrCtx = rdrCtx;
1162 
1163             curves_ref = rdrCtx.newDirtyFloatArrayRef(INITIAL_CURVES_COUNT); // 32K
1164             curves     = curves_ref.initial;
1165 
1166             curveTypes_ref = rdrCtx.newDirtyByteArrayRef(INITIAL_TYPES_COUNT); // 4K
1167             curveTypes     = curveTypes_ref.initial;
1168             numCurves = 0;
1169             end = 0;
1170 
1171             if (DO_STATS) {
1172                 curveTypesUseMark = 0;
1173                 curvesUseMark = 0;
1174             }
1175         }
1176 
1177         /**
1178          * Disposes this PolyStack:
1179          * clean up before reusing this instance
1180          */
1181         void dispose() {
1182             end = 0;
1183             numCurves = 0;
1184 
1185             if (DO_STATS) {
1186                 rdrCtx.stats.stat_rdr_poly_stack_types.add(curveTypesUseMark);
1187                 rdrCtx.stats.stat_rdr_poly_stack_curves.add(curvesUseMark);
1188                 rdrCtx.stats.hist_rdr_poly_stack_curves.add(curvesUseMark);
1189 
1190                 // reset marks
1191                 curveTypesUseMark = 0;
1192                 curvesUseMark = 0;
1193             }
1194 
1195             // Return arrays:
1196             // curves and curveTypes are kept dirty
1197             curves     = curves_ref.putArray(curves);
1198             curveTypes = curveTypes_ref.putArray(curveTypes);
1199         }
1200 
1201         private void ensureSpace(final int n) {
1202             // use substraction to avoid integer overflow:
1203             if (curves.length - end < n) {
1204                 if (DO_STATS) {
1205                     rdrCtx.stats.stat_array_stroker_polystack_curves
1206                         .add(end + n);
1207                 }
1208                 curves = curves_ref.widenArray(curves, end, end + n);
1209             }
1210             if (curveTypes.length <= numCurves) {
1211                 if (DO_STATS) {
1212                     rdrCtx.stats.stat_array_stroker_polystack_curveTypes
1213                         .add(numCurves + 1);
1214                 }
1215                 curveTypes = curveTypes_ref.widenArray(curveTypes,
1216                                                        numCurves,
1217                                                        numCurves + 1);
1218             }
1219         }
1220 
1221         void pushCubic(float x0, float y0,
1222                        float x1, float y1,
1223                        float x2, float y2)
1224         {
1225             ensureSpace(6);
1226             curveTypes[numCurves++] = TYPE_CUBICTO;
1227             // we reverse the coordinate order to make popping easier
1228             final float[] _curves = curves;
1229             int e = end;
1230             _curves[e++] = x2;    _curves[e++] = y2;
1231             _curves[e++] = x1;    _curves[e++] = y1;
1232             _curves[e++] = x0;    _curves[e++] = y0;
1233             end = e;
1234         }
1235 
1236         void pushQuad(float x0, float y0,
1237                       float x1, float y1)
1238         {
1239             ensureSpace(4);
1240             curveTypes[numCurves++] = TYPE_QUADTO;
1241             final float[] _curves = curves;
1242             int e = end;
1243             _curves[e++] = x1;    _curves[e++] = y1;
1244             _curves[e++] = x0;    _curves[e++] = y0;
1245             end = e;
1246         }
1247 
1248         void pushLine(float x, float y) {
1249             ensureSpace(2);
1250             curveTypes[numCurves++] = TYPE_LINETO;
1251             curves[end++] = x;    curves[end++] = y;
1252         }
1253 
1254         void popAll(PathConsumer2D io) {
1255             if (DO_STATS) {
1256                 // update used marks:
1257                 if (numCurves > curveTypesUseMark) {
1258                     curveTypesUseMark = numCurves;
1259                 }
1260                 if (end > curvesUseMark) {
1261                     curvesUseMark = end;
1262                 }
1263             }
1264             final byte[]  _curveTypes = curveTypes;
1265             final float[] _curves = curves;
1266             int nc = numCurves;
1267             int e  = end;
1268 
1269             while (nc != 0) {
1270                 switch(_curveTypes[--nc]) {
1271                 case TYPE_LINETO:
1272                     e -= 2;
1273                     io.lineTo(_curves[e], _curves[e+1]);
1274                     continue;
1275                 case TYPE_QUADTO:
1276                     e -= 4;
1277                     io.quadTo(_curves[e+0], _curves[e+1],
1278                               _curves[e+2], _curves[e+3]);
1279                     continue;
1280                 case TYPE_CUBICTO:
1281                     e -= 6;
1282                     io.curveTo(_curves[e+0], _curves[e+1],
1283                                _curves[e+2], _curves[e+3],
1284                                _curves[e+4], _curves[e+5]);
1285                     continue;
1286                 default:
1287                 }
1288             }
1289             numCurves = 0;
1290             end = 0;
1291         }
1292 
1293         @Override
1294         public String toString() {
1295             String ret = "";
1296             int nc = numCurves;
1297             int last = end;
1298             int len;
1299             while (nc != 0) {
1300                 switch(curveTypes[--nc]) {
1301                 case TYPE_LINETO:
1302                     len = 2;
1303                     ret += "line: ";
1304                     break;
1305                 case TYPE_QUADTO:
1306                     len = 4;
1307                     ret += "quad: ";
1308                     break;
1309                 case TYPE_CUBICTO:
1310                     len = 6;
1311                     ret += "cubic: ";
1312                     break;
1313                 default:
1314                     len = 0;
1315                 }
1316                 last -= len;
1317                 ret += Arrays.toString(Arrays.copyOfRange(curves, last, last+len))
1318                                        + "\n";
1319             }
1320             return ret;
1321         }
1322     }
1323 }