1 /*
   2  * Copyright (c) 2007, 2016, 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/65536f;
  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 * 8];
 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 / 2f;
 157         this.invHalfLineWidth2Sq = 1f / (2f * 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, 0f);
 181             Arrays.fill(offset1, 0f);
 182             Arrays.fill(offset2, 0f);
 183             Arrays.fill(miter, 0f);
 184             Arrays.fill(middle, 0f);
 185             Arrays.fill(lp, 0f);
 186             Arrays.fill(rp, 0f);
 187             Arrays.fill(subdivTs, 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 == 0f) {
 196             m[0] = 0f;
 197             m[1] = 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 == 0f && omy == 0f) || (mx == 0f && my == 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 >= 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.0 / 3.0) * Math.sqrt(0.5 - cosext2) /
 317                             (1.0 + Math.sqrt(cosext2 + 0.5)));
 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[0] and m[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[0] and m[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 == 0f) {
 399             m[off++] = (x0 + x0p) / 2f;
 400             m[off] = (y0 + y0p) / 2f;
 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 == 0f && pdy == 0f) ||
 417             (dx == 0f && dy == 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 = 1f;
 455         this.cdy = this.sdy = 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 == 0f && dy == 0f) {
 464             dx = 1f;
 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 = 0f;
 495             this.cmy = this.smy = -lineWidth2;
 496             this.cdx = this.sdx = 1f;
 497             this.cdy = this.sdy = 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 winden
 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, 6f * Math.ulp(y2));
 698         final boolean p3eqp4 = within(x3,y3,x4,y4, 6f * 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, 4f * 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 + 3f * (x2 + x3) + x4) / 8f;
 767         float y = (y1 + 3f * (y2 + y3) + y4) / 8f;
 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 = 4f / (3f * (dx1 * dy4 - dy1 * dx4));
 786 
 787         float two_pi_m_p1_m_p4x = 2f * xi - x1p - x4p;
 788         float two_pi_m_p1_m_p4y = 2f * 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 - 2f * offset1[0]; yi = yi - 2f * offset1[1];
 805         x4p = x4 - offset2[0]; y4p = y4 - offset2[1];
 806 
 807         two_pi_m_p1_m_p4x = 2f * xi - x1p - x4p;
 808         two_pi_m_p1_m_p4y = 2f * 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 winden
 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, 6f * Math.ulp(y2));
 850         final boolean p2eqp3 = within(x2,y2,x3,y3, 6f * 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, 4f * 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     // If this class is compiled with ecj, then Hotspot crashes when OSR
 888     // compiling this function. See bugs 7004570 and 6675699
 889     // TODO: until those are fixed, we should work around that by
 890     // manually inlining this into curveTo and quadTo.
 891 /******************************* WORKAROUND **********************************
 892     private void somethingTo(final int type) {
 893         // need these so we can update the state at the end of this method
 894         final float xf = middle[type-2], yf = middle[type-1];
 895         float dxs = middle[2] - middle[0];
 896         float dys = middle[3] - middle[1];
 897         float dxf = middle[type - 2] - middle[type - 4];
 898         float dyf = middle[type - 1] - middle[type - 3];
 899         switch(type) {
 900         case 6:
 901             if ((dxs == 0f && dys == 0f) ||
 902                 (dxf == 0f && dyf == 0f)) {
 903                dxs = dxf = middle[4] - middle[0];
 904                dys = dyf = middle[5] - middle[1];
 905             }
 906             break;
 907         case 8:
 908             boolean p1eqp2 = (dxs == 0f && dys == 0f);
 909             boolean p3eqp4 = (dxf == 0f && dyf == 0f);
 910             if (p1eqp2) {
 911                 dxs = middle[4] - middle[0];
 912                 dys = middle[5] - middle[1];
 913                 if (dxs == 0f && dys == 0f) {
 914                     dxs = middle[6] - middle[0];
 915                     dys = middle[7] - middle[1];
 916                 }
 917             }
 918             if (p3eqp4) {
 919                 dxf = middle[6] - middle[2];
 920                 dyf = middle[7] - middle[3];
 921                 if (dxf == 0f && dyf == 0f) {
 922                     dxf = middle[6] - middle[0];
 923                     dyf = middle[7] - middle[1];
 924                 }
 925             }
 926         }
 927         if (dxs == 0f && dys == 0f) {
 928             // this happens iff the "curve" is just a point
 929             lineTo(middle[0], middle[1]);
 930             return;
 931         }
 932         // if these vectors are too small, normalize them, to avoid future
 933         // precision problems.
 934         if (Math.abs(dxs) < 0.1f && Math.abs(dys) < 0.1f) {
 935             float len = (float) sqrt(dxs*dxs + dys*dys);
 936             dxs /= len;
 937             dys /= len;
 938         }
 939         if (Math.abs(dxf) < 0.1f && Math.abs(dyf) < 0.1f) {
 940             float len = (float) sqrt(dxf*dxf + dyf*dyf);
 941             dxf /= len;
 942             dyf /= len;
 943         }
 944 
 945         computeOffset(dxs, dys, lineWidth2, offset0);
 946         final float mx = offset0[0];
 947         final float my = offset0[1];
 948         drawJoin(cdx, cdy, cx0, cy0, dxs, dys, cmx, cmy, mx, my);
 949 
 950         int nSplits = findSubdivPoints(curve, middle, subdivTs, type, lineWidth2);
 951 
 952         int kind = 0;
 953         BreakPtrIterator it = curve.breakPtsAtTs(middle, type, subdivTs, nSplits);
 954         while(it.hasNext()) {
 955             int curCurveOff = it.next();
 956 
 957             switch (type) {
 958             case 8:
 959                 kind = computeOffsetCubic(middle, curCurveOff, lp, rp);
 960                 break;
 961             case 6:
 962                 kind = computeOffsetQuad(middle, curCurveOff, lp, rp);
 963                 break;
 964             }
 965             emitLineTo(lp[0], lp[1]);
 966             switch(kind) {
 967             case 8:
 968                 emitCurveTo(lp[2], lp[3], lp[4], lp[5], lp[6], lp[7]);
 969                 emitCurveToRev(rp[0], rp[1], rp[2], rp[3], rp[4], rp[5]);
 970                 break;
 971             case 6:
 972                 emitQuadTo(lp[2], lp[3], lp[4], lp[5]);
 973                 emitQuadToRev(rp[0], rp[1], rp[2], rp[3]);
 974                 break;
 975             case 4:
 976                 emitLineTo(lp[2], lp[3]);
 977                 emitLineTo(rp[0], rp[1], true);
 978                 break;
 979             }
 980             emitLineTo(rp[kind - 2], rp[kind - 1], true);
 981         }
 982 
 983         this.cmx = (lp[kind - 2] - rp[kind - 2]) / 2;
 984         this.cmy = (lp[kind - 1] - rp[kind - 1]) / 2;
 985         this.cdx = dxf;
 986         this.cdy = dyf;
 987         this.cx0 = xf;
 988         this.cy0 = yf;
 989         this.prev = DRAWING_OP_TO;
 990     }
 991 ****************************** END WORKAROUND *******************************/
 992 
 993     // finds values of t where the curve in pts should be subdivided in order
 994     // to get good offset curves a distance of w away from the middle curve.
 995     // Stores the points in ts, and returns how many of them there were.
 996     private static int findSubdivPoints(final Curve c, float[] pts, float[] ts,
 997                                         final int type, final float w)
 998     {
 999         final float x12 = pts[2] - pts[0];
1000         final float y12 = pts[3] - pts[1];
1001         // if the curve is already parallel to either axis we gain nothing
1002         // from rotating it.
1003         if (y12 != 0f && x12 != 0f) {
1004             // we rotate it so that the first vector in the control polygon is
1005             // parallel to the x-axis. This will ensure that rotated quarter
1006             // circles won't be subdivided.
1007             final float hypot = (float) Math.sqrt(x12 * x12 + y12 * y12);
1008             final float cos = x12 / hypot;
1009             final float sin = y12 / hypot;
1010             final float x1 = cos * pts[0] + sin * pts[1];
1011             final float y1 = cos * pts[1] - sin * pts[0];
1012             final float x2 = cos * pts[2] + sin * pts[3];
1013             final float y2 = cos * pts[3] - sin * pts[2];
1014             final float x3 = cos * pts[4] + sin * pts[5];
1015             final float y3 = cos * pts[5] - sin * pts[4];
1016 
1017             switch(type) {
1018             case 8:
1019                 final float x4 = cos * pts[6] + sin * pts[7];
1020                 final float y4 = cos * pts[7] - sin * pts[6];
1021                 c.set(x1, y1, x2, y2, x3, y3, x4, y4);
1022                 break;
1023             case 6:
1024                 c.set(x1, y1, x2, y2, x3, y3);
1025                 break;
1026             default:
1027             }
1028         } else {
1029             c.set(pts, type);
1030         }
1031 
1032         int ret = 0;
1033         // we subdivide at values of t such that the remaining rotated
1034         // curves are monotonic in x and y.
1035         ret += c.dxRoots(ts, ret);
1036         ret += c.dyRoots(ts, ret);
1037         // subdivide at inflection points.
1038         if (type == 8) {
1039             // quadratic curves can't have inflection points
1040             ret += c.infPoints(ts, ret);
1041         }
1042 
1043         // now we must subdivide at points where one of the offset curves will have
1044         // a cusp. This happens at ts where the radius of curvature is equal to w.
1045         ret += c.rootsOfROCMinusW(ts, ret, w, 0.0001f);
1046 
1047         ret = Helpers.filterOutNotInAB(ts, 0, ret, 0.0001f, 0.9999f);
1048         Helpers.isort(ts, 0, ret);
1049         return ret;
1050     }
1051 
1052     @Override public void curveTo(float x1, float y1,
1053                                   float x2, float y2,
1054                                   float x3, float y3)
1055     {
1056         final float[] mid = middle;
1057 
1058         mid[0] = cx0; mid[1] = cy0;
1059         mid[2] = x1;  mid[3] = y1;
1060         mid[4] = x2;  mid[5] = y2;
1061         mid[6] = x3;  mid[7] = y3;
1062 
1063         // inlined version of somethingTo(8);
1064         // See the TODO on somethingTo
1065 
1066         // need these so we can update the state at the end of this method
1067         final float xf = mid[6], yf = mid[7];
1068         float dxs = mid[2] - mid[0];
1069         float dys = mid[3] - mid[1];
1070         float dxf = mid[6] - mid[4];
1071         float dyf = mid[7] - mid[5];
1072 
1073         boolean p1eqp2 = (dxs == 0f && dys == 0f);
1074         boolean p3eqp4 = (dxf == 0f && dyf == 0f);
1075         if (p1eqp2) {
1076             dxs = mid[4] - mid[0];
1077             dys = mid[5] - mid[1];
1078             if (dxs == 0f && dys == 0f) {
1079                 dxs = mid[6] - mid[0];
1080                 dys = mid[7] - mid[1];
1081             }
1082         }
1083         if (p3eqp4) {
1084             dxf = mid[6] - mid[2];
1085             dyf = mid[7] - mid[3];
1086             if (dxf == 0f && dyf == 0f) {
1087                 dxf = mid[6] - mid[0];
1088                 dyf = mid[7] - mid[1];
1089             }
1090         }
1091         if (dxs == 0f && dys == 0f) {
1092             // this happens if the "curve" is just a point
1093             lineTo(mid[0], mid[1]);
1094             return;
1095         }
1096 
1097         // if these vectors are too small, normalize them, to avoid future
1098         // precision problems.
1099         if (Math.abs(dxs) < 0.1f && Math.abs(dys) < 0.1f) {
1100             float len = (float) Math.sqrt(dxs*dxs + dys*dys);
1101             dxs /= len;
1102             dys /= len;
1103         }
1104         if (Math.abs(dxf) < 0.1f && Math.abs(dyf) < 0.1f) {
1105             float len = (float) Math.sqrt(dxf*dxf + dyf*dyf);
1106             dxf /= len;
1107             dyf /= len;
1108         }
1109 
1110         computeOffset(dxs, dys, lineWidth2, offset0);
1111         drawJoin(cdx, cdy, cx0, cy0, dxs, dys, cmx, cmy, offset0[0], offset0[1]);
1112 
1113         final int nSplits = findSubdivPoints(curve, mid, subdivTs, 8, lineWidth2);
1114 
1115         float prevT = 0f;
1116         for (int i = 0, off = 0; i < nSplits; i++, off += 6) {
1117             final float t = subdivTs[i];
1118             Helpers.subdivideCubicAt((t - prevT) / (1f - prevT),
1119                                      mid, off, mid, off, mid, off + 6);
1120             prevT = t;
1121         }
1122 
1123         final float[] l = lp;
1124         final float[] r = rp;
1125 
1126         int kind = 0;
1127         for (int i = 0, off = 0; i <= nSplits; i++, off += 6) {
1128             kind = computeOffsetCubic(mid, off, l, r);
1129 
1130             emitLineTo(l[0], l[1]);
1131 
1132             switch(kind) {
1133             case 8:
1134                 emitCurveTo(l[2], l[3], l[4], l[5], l[6], l[7]);
1135                 emitCurveToRev(r[0], r[1], r[2], r[3], r[4], r[5]);
1136                 break;
1137             case 4:
1138                 emitLineTo(l[2], l[3]);
1139                 emitLineToRev(r[0], r[1]);
1140                 break;
1141             default:
1142             }
1143             emitLineToRev(r[kind - 2], r[kind - 1]);
1144         }
1145 
1146         this.cmx = (l[kind - 2] - r[kind - 2]) / 2f;
1147         this.cmy = (l[kind - 1] - r[kind - 1]) / 2f;
1148         this.cdx = dxf;
1149         this.cdy = dyf;
1150         this.cx0 = xf;
1151         this.cy0 = yf;
1152         this.prev = DRAWING_OP_TO;
1153     }
1154 
1155     @Override public void quadTo(float x1, float y1, float x2, float y2) {
1156         final float[] mid = middle;
1157 
1158         mid[0] = cx0; mid[1] = cy0;
1159         mid[2] = x1;  mid[3] = y1;
1160         mid[4] = x2;  mid[5] = y2;
1161 
1162         // inlined version of somethingTo(8);
1163         // See the TODO on somethingTo
1164 
1165         // need these so we can update the state at the end of this method
1166         final float xf = mid[4], yf = mid[5];
1167         float dxs = mid[2] - mid[0];
1168         float dys = mid[3] - mid[1];
1169         float dxf = mid[4] - mid[2];
1170         float dyf = mid[5] - mid[3];
1171         if ((dxs == 0f && dys == 0f) || (dxf == 0f && dyf == 0f)) {
1172             dxs = dxf = mid[4] - mid[0];
1173             dys = dyf = mid[5] - mid[1];
1174         }
1175         if (dxs == 0f && dys == 0f) {
1176             // this happens if the "curve" is just a point
1177             lineTo(mid[0], mid[1]);
1178             return;
1179         }
1180         // if these vectors are too small, normalize them, to avoid future
1181         // precision problems.
1182         if (Math.abs(dxs) < 0.1f && Math.abs(dys) < 0.1f) {
1183             float len = (float) Math.sqrt(dxs*dxs + dys*dys);
1184             dxs /= len;
1185             dys /= len;
1186         }
1187         if (Math.abs(dxf) < 0.1f && Math.abs(dyf) < 0.1f) {
1188             float len = (float) Math.sqrt(dxf*dxf + dyf*dyf);
1189             dxf /= len;
1190             dyf /= len;
1191         }
1192 
1193         computeOffset(dxs, dys, lineWidth2, offset0);
1194         drawJoin(cdx, cdy, cx0, cy0, dxs, dys, cmx, cmy, offset0[0], offset0[1]);
1195 
1196         int nSplits = findSubdivPoints(curve, mid, subdivTs, 6, lineWidth2);
1197 
1198         float prevt = 0f;
1199         for (int i = 0, off = 0; i < nSplits; i++, off += 4) {
1200             final float t = subdivTs[i];
1201             Helpers.subdivideQuadAt((t - prevt) / (1f - prevt),
1202                                     mid, off, mid, off, mid, off + 4);
1203             prevt = t;
1204         }
1205 
1206         final float[] l = lp;
1207         final float[] r = rp;
1208 
1209         int kind = 0;
1210         for (int i = 0, off = 0; i <= nSplits; i++, off += 4) {
1211             kind = computeOffsetQuad(mid, off, l, r);
1212 
1213             emitLineTo(l[0], l[1]);
1214 
1215             switch(kind) {
1216             case 6:
1217                 emitQuadTo(l[2], l[3], l[4], l[5]);
1218                 emitQuadToRev(r[0], r[1], r[2], r[3]);
1219                 break;
1220             case 4:
1221                 emitLineTo(l[2], l[3]);
1222                 emitLineToRev(r[0], r[1]);
1223                 break;
1224             default:
1225             }
1226             emitLineToRev(r[kind - 2], r[kind - 1]);
1227         }
1228 
1229         this.cmx = (l[kind - 2] - r[kind - 2]) / 2f;
1230         this.cmy = (l[kind - 1] - r[kind - 1]) / 2f;
1231         this.cdx = dxf;
1232         this.cdy = dyf;
1233         this.cx0 = xf;
1234         this.cy0 = yf;
1235         this.prev = DRAWING_OP_TO;
1236     }
1237 
1238     // a stack of polynomial curves where each curve shares endpoints with
1239     // adjacent ones.
1240     static final class PolyStack {
1241         private static final byte TYPE_LINETO  = (byte) 0;
1242         private static final byte TYPE_QUADTO  = (byte) 1;
1243         private static final byte TYPE_CUBICTO = (byte) 2;
1244 
1245         // curves capacity = edges count (8192) = edges x 2 (coords)
1246         private static final int INITIAL_CURVES_COUNT = INITIAL_EDGES_COUNT << 1;
1247 
1248         // types capacity = edges count (4096)
1249         private static final int INITIAL_TYPES_COUNT = INITIAL_EDGES_COUNT;
1250 
1251         float[] curves;
1252         int end;
1253         byte[] curveTypes;
1254         int numCurves;
1255 
1256         // per-thread renderer context
1257         final RendererContext rdrCtx;
1258 
1259         // curves ref (dirty)
1260         final FloatArrayCache.Reference curves_ref;
1261         // curveTypes ref (dirty)
1262         final ByteArrayCache.Reference curveTypes_ref;
1263 
1264         // used marks (stats only)
1265         int curveTypesUseMark;
1266         int curvesUseMark;
1267 
1268         /**
1269          * Constructor
1270          * @param rdrCtx per-thread renderer context
1271          */
1272         PolyStack(final RendererContext rdrCtx) {
1273             this.rdrCtx = rdrCtx;
1274 
1275             curves_ref = rdrCtx.newDirtyFloatArrayRef(INITIAL_CURVES_COUNT); // 32K
1276             curves     = curves_ref.initial;
1277 
1278             curveTypes_ref = rdrCtx.newDirtyByteArrayRef(INITIAL_TYPES_COUNT); // 4K
1279             curveTypes     = curveTypes_ref.initial;
1280             numCurves = 0;
1281             end = 0;
1282 
1283             if (DO_STATS) {
1284                 curveTypesUseMark = 0;
1285                 curvesUseMark = 0;
1286             }
1287         }
1288 
1289         /**
1290          * Disposes this PolyStack:
1291          * clean up before reusing this instance
1292          */
1293         void dispose() {
1294             end = 0;
1295             numCurves = 0;
1296 
1297             if (DO_STATS) {
1298                 rdrCtx.stats.stat_rdr_poly_stack_types.add(curveTypesUseMark);
1299                 rdrCtx.stats.stat_rdr_poly_stack_curves.add(curvesUseMark);
1300                 rdrCtx.stats.hist_rdr_poly_stack_curves.add(curvesUseMark);
1301 
1302                 // reset marks
1303                 curveTypesUseMark = 0;
1304                 curvesUseMark = 0;
1305             }
1306 
1307             // Return arrays:
1308             // curves and curveTypes are kept dirty
1309             curves     = curves_ref.putArray(curves);
1310             curveTypes = curveTypes_ref.putArray(curveTypes);
1311         }
1312 
1313         private void ensureSpace(final int n) {
1314             // use substraction to avoid integer overflow:
1315             if (curves.length - end < n) {
1316                 if (DO_STATS) {
1317                     rdrCtx.stats.stat_array_stroker_polystack_curves
1318                         .add(end + n);
1319                 }
1320                 curves = curves_ref.widenArray(curves, end, end + n);
1321             }
1322             if (curveTypes.length <= numCurves) {
1323                 if (DO_STATS) {
1324                     rdrCtx.stats.stat_array_stroker_polystack_curveTypes
1325                         .add(numCurves + 1);
1326                 }
1327                 curveTypes = curveTypes_ref.widenArray(curveTypes,
1328                                                        numCurves,
1329                                                        numCurves + 1);
1330             }
1331         }
1332 
1333         void pushCubic(float x0, float y0,
1334                        float x1, float y1,
1335                        float x2, float y2)
1336         {
1337             ensureSpace(6);
1338             curveTypes[numCurves++] = TYPE_CUBICTO;
1339             // we reverse the coordinate order to make popping easier
1340             final float[] _curves = curves;
1341             int e = end;
1342             _curves[e++] = x2;    _curves[e++] = y2;
1343             _curves[e++] = x1;    _curves[e++] = y1;
1344             _curves[e++] = x0;    _curves[e++] = y0;
1345             end = e;
1346         }
1347 
1348         void pushQuad(float x0, float y0,
1349                       float x1, float y1)
1350         {
1351             ensureSpace(4);
1352             curveTypes[numCurves++] = TYPE_QUADTO;
1353             final float[] _curves = curves;
1354             int e = end;
1355             _curves[e++] = x1;    _curves[e++] = y1;
1356             _curves[e++] = x0;    _curves[e++] = y0;
1357             end = e;
1358         }
1359 
1360         void pushLine(float x, float y) {
1361             ensureSpace(2);
1362             curveTypes[numCurves++] = TYPE_LINETO;
1363             curves[end++] = x;    curves[end++] = y;
1364         }
1365 
1366         void popAll(PathConsumer2D io) {
1367             if (DO_STATS) {
1368                 // update used marks:
1369                 if (numCurves > curveTypesUseMark) {
1370                     curveTypesUseMark = numCurves;
1371                 }
1372                 if (end > curvesUseMark) {
1373                     curvesUseMark = end;
1374                 }
1375             }
1376             final byte[]  _curveTypes = curveTypes;
1377             final float[] _curves = curves;
1378             int nc = numCurves;
1379             int e  = end;
1380 
1381             while (nc != 0) {
1382                 switch(_curveTypes[--nc]) {
1383                 case TYPE_LINETO:
1384                     e -= 2;
1385                     io.lineTo(_curves[e], _curves[e+1]);
1386                     continue;
1387                 case TYPE_QUADTO:
1388                     e -= 4;
1389                     io.quadTo(_curves[e+0], _curves[e+1],
1390                               _curves[e+2], _curves[e+3]);
1391                     continue;
1392                 case TYPE_CUBICTO:
1393                     e -= 6;
1394                     io.curveTo(_curves[e+0], _curves[e+1],
1395                                _curves[e+2], _curves[e+3],
1396                                _curves[e+4], _curves[e+5]);
1397                     continue;
1398                 default:
1399                 }
1400             }
1401             numCurves = 0;
1402             end = 0;
1403         }
1404 
1405         @Override
1406         public String toString() {
1407             String ret = "";
1408             int nc = numCurves;
1409             int last = end;
1410             int len;
1411             while (nc != 0) {
1412                 switch(curveTypes[--nc]) {
1413                 case TYPE_LINETO:
1414                     len = 2;
1415                     ret += "line: ";
1416                     break;
1417                 case TYPE_QUADTO:
1418                     len = 4;
1419                     ret += "quad: ";
1420                     break;
1421                 case TYPE_CUBICTO:
1422                     len = 6;
1423                     ret += "cubic: ";
1424                     break;
1425                 default:
1426                     len = 0;
1427                 }
1428                 last -= len;
1429                 ret += Arrays.toString(Arrays.copyOfRange(curves, last, last+len))
1430                                        + "\n";
1431             }
1432             return ret;
1433         }
1434     }
1435 }