1 /*
   2  * Copyright (c) 2007, 2010, 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 sun.java2d.pisces;
  27 
  28 import java.util.Arrays;
  29 import java.util.Iterator;
  30 
  31 import sun.awt.geom.PathConsumer2D;
  32 
  33 // TODO: some of the arithmetic here is too verbose and prone to hard to
  34 // debug typos. We should consider making a small Point/Vector class that
  35 // has methods like plus(Point), minus(Point), dot(Point), cross(Point)and such
  36 public class Stroker implements PathConsumer2D {
  37 
  38     private static final int MOVE_TO = 0;
  39     private static final int DRAWING_OP_TO = 1; // ie. curve, line, or quad
  40     private static final int CLOSE = 2;
  41 
  42     /**
  43      * Constant value for join style.
  44      */
  45     public static final int JOIN_MITER = 0;
  46 
  47     /**
  48      * Constant value for join style.
  49      */
  50     public static final int JOIN_ROUND = 1;
  51 
  52     /**
  53      * Constant value for join style.
  54      */
  55     public static final int JOIN_BEVEL = 2;
  56 
  57     /**
  58      * Constant value for end cap style.
  59      */
  60     public static final int CAP_BUTT = 0;
  61 
  62     /**
  63      * Constant value for end cap style.
  64      */
  65     public static final int CAP_ROUND = 1;
  66 
  67     /**
  68      * Constant value for end cap style.
  69      */
  70     public static final int CAP_SQUARE = 2;
  71 
  72     private final PathConsumer2D out;
  73 
  74     private final int capStyle;
  75     private final int joinStyle;
  76 
  77     private final float lineWidth2;
  78 
  79     private final float[][] offset = new float[3][2];
  80     private final float[] miter = new float[2];
  81     private final float miterLimitSq;
  82 
  83     private int prev;
  84 
  85     // The starting point of the path, and the slope there.
  86     private float sx0, sy0, sdx, sdy;
  87     // the current point and the slope there.
  88     private float cx0, cy0, cdx, cdy; // c stands for current
  89     // vectors that when added to (sx0,sy0) and (cx0,cy0) respectively yield the
  90     // first and last points on the left parallel path. Since this path is
  91     // parallel, it's slope at any point is parallel to the slope of the
  92     // original path (thought they may have different directions), so these
  93     // could be computed from sdx,sdy and cdx,cdy (and vice versa), but that
  94     // would be error prone and hard to read, so we keep these anyway.
  95     private float smx, smy, cmx, cmy;
  96 
  97     private final PolyStack reverse = new PolyStack();
  98 
  99     /**
 100      * Constructs a <code>Stroker</code>.
 101      *
 102      * @param pc2d an output <code>PathConsumer2D</code>.
 103      * @param lineWidth the desired line width in pixels
 104      * @param capStyle the desired end cap style, one of
 105      * <code>CAP_BUTT</code>, <code>CAP_ROUND</code> or
 106      * <code>CAP_SQUARE</code>.
 107      * @param joinStyle the desired line join style, one of
 108      * <code>JOIN_MITER</code>, <code>JOIN_ROUND</code> or
 109      * <code>JOIN_BEVEL</code>.
 110      * @param miterLimit the desired miter limit
 111      */
 112     public Stroker(PathConsumer2D pc2d,
 113                    float lineWidth,
 114                    int capStyle,
 115                    int joinStyle,
 116                    float miterLimit)
 117     {
 118         this.out = pc2d;
 119 
 120         this.lineWidth2 = lineWidth / 2;
 121         this.capStyle = capStyle;
 122         this.joinStyle = joinStyle;
 123 
 124         float limit = miterLimit * lineWidth2;
 125         this.miterLimitSq = limit*limit;
 126 
 127         this.prev = CLOSE;
 128     }
 129 
 130     private static void computeOffset(final float lx, final float ly,
 131                                       final float w, final float[] m)
 132     {
 133         final float len = (float)Math.hypot(lx, ly);
 134         if (len == 0) {
 135             m[0] = m[1] = 0;
 136         } else {
 137             m[0] = (ly * w)/len;
 138             m[1] = -(lx * w)/len;
 139         }
 140     }
 141 
 142     // Returns true if the vectors (dx1, dy1) and (dx2, dy2) are
 143     // clockwise (if dx1,dy1 needs to be rotated clockwise to close
 144     // the smallest angle between it and dx2,dy2).
 145     // This is equivalent to detecting whether a point q is on the right side
 146     // of a line passing through points p1, p2 where p2 = p1+(dx1,dy1) and
 147     // q = p2+(dx2,dy2), which is the same as saying p1, p2, q are in a
 148     // clockwise order.
 149     // NOTE: "clockwise" here assumes coordinates with 0,0 at the bottom left.
 150     private static boolean isCW(final float dx1, final float dy1,
 151                                 final float dx2, final float dy2)
 152     {
 153         return dx1 * dy2 <= dy1 * dx2;
 154     }
 155 
 156     // pisces used to use fixed point arithmetic with 16 decimal digits. I
 157     // didn't want to change the values of the constant below when I converted
 158     // it to floating point, so that's why the divisions by 2^16 are there.
 159     private static final float ROUND_JOIN_THRESHOLD = 1000/65536f;
 160 
 161     private void drawRoundJoin(float x, float y,
 162                                float omx, float omy, float mx, float my,
 163                                boolean rev,
 164                                float threshold)
 165     {
 166         if ((omx == 0 && omy == 0) || (mx == 0 && my == 0)) {
 167             return;
 168         }
 169 
 170         float domx = omx - mx;
 171         float domy = omy - my;
 172         float len = domx*domx + domy*domy;
 173         if (len < threshold) {
 174             return;
 175         }
 176 
 177         if (rev) {
 178             omx = -omx;
 179             omy = -omy;
 180             mx = -mx;
 181             my = -my;
 182         }
 183         drawRoundJoin(x, y, omx, omy, mx, my, rev);
 184     }
 185 
 186     private void drawRoundJoin(float cx, float cy,
 187                                float omx, float omy,
 188                                float mx, float my,
 189                                boolean rev)
 190     {
 191         // The sign of the dot product of mx,my and omx,omy is equal to the
 192         // the sign of the cosine of ext
 193         // (ext is the angle between omx,omy and mx,my).
 194         double cosext = omx * mx + omy * my;
 195         // If it is >=0, we know that abs(ext) is <= 90 degrees, so we only
 196         // need 1 curve to approximate the circle section that joins omx,omy
 197         // and mx,my.
 198         final int numCurves = cosext >= 0 ? 1 : 2;
 199 
 200         switch (numCurves) {
 201         case 1:
 202             drawBezApproxForArc(cx, cy, omx, omy, mx, my, rev);
 203             break;
 204         case 2:
 205             // we need to split the arc into 2 arcs spanning the same angle.
 206             // The point we want will be one of the 2 intersections of the
 207             // perpendicular bisector of the chord (omx,omy)->(mx,my) and the
 208             // circle. We could find this by scaling the vector
 209             // (omx+mx, omy+my)/2 so that it has length=lineWidth2 (and thus lies
 210             // on the circle), but that can have numerical problems when the angle
 211             // between omx,omy and mx,my is close to 180 degrees. So we compute a
 212             // normal of (omx,omy)-(mx,my). This will be the direction of the
 213             // perpendicular bisector. To get one of the intersections, we just scale
 214             // this vector that its length is lineWidth2 (this works because the
 215             // perpendicular bisector goes through the origin). This scaling doesn't
 216             // have numerical problems because we know that lineWidth2 divided by
 217             // this normal's length is at least 0.5 and at most sqrt(2)/2 (because
 218             // we know the angle of the arc is > 90 degrees).
 219             float nx = my - omy, ny = omx - mx;
 220             float nlen = (float)Math.sqrt(nx*nx + ny*ny);
 221             float scale = lineWidth2/nlen;
 222             float mmx = nx * scale, mmy = ny * scale;
 223 
 224             // if (isCW(omx, omy, mx, my) != isCW(mmx, mmy, mx, my)) then we've
 225             // computed the wrong intersection so we get the other one.
 226             // The test above is equivalent to if (rev).
 227             if (rev) {
 228                 mmx = -mmx;
 229                 mmy = -mmy;
 230             }
 231             drawBezApproxForArc(cx, cy, omx, omy, mmx, mmy, rev);
 232             drawBezApproxForArc(cx, cy, mmx, mmy, mx, my, rev);
 233             break;
 234         }
 235     }
 236 
 237     // the input arc defined by omx,omy and mx,my must span <= 90 degrees.
 238     private void drawBezApproxForArc(final float cx, final float cy,
 239                                      final float omx, final float omy,
 240                                      final float mx, final float my,
 241                                      boolean rev)
 242     {
 243         float cosext2 = (omx * mx + omy * my) / (2 * lineWidth2 * lineWidth2);
 244         // cv is the length of P1-P0 and P2-P3 divided by the radius of the arc
 245         // (so, cv assumes the arc has radius 1). P0, P1, P2, P3 are the points that
 246         // define the bezier curve we're computing.
 247         // It is computed using the constraints that P1-P0 and P3-P2 are parallel
 248         // to the arc tangents at the endpoints, and that |P1-P0|=|P3-P2|.
 249         float cv = (float)((4.0 / 3.0) * Math.sqrt(0.5-cosext2) /
 250                            (1.0 + Math.sqrt(cosext2+0.5)));
 251         // if clockwise, we need to negate cv.
 252         if (rev) { // rev is equivalent to isCW(omx, omy, mx, my)
 253             cv = -cv;
 254         }
 255         final float x1 = cx + omx;
 256         final float y1 = cy + omy;
 257         final float x2 = x1 - cv * omy;
 258         final float y2 = y1 + cv * omx;
 259 
 260         final float x4 = cx + mx;
 261         final float y4 = cy + my;
 262         final float x3 = x4 + cv * my;
 263         final float y3 = y4 - cv * mx;
 264 
 265         emitCurveTo(x1, y1, x2, y2, x3, y3, x4, y4, rev);
 266     }
 267 
 268     private void drawRoundCap(float cx, float cy, float mx, float my) {
 269         final float C = 0.5522847498307933f;
 270         // the first and second arguments of the following two calls
 271         // are really will be ignored by emitCurveTo (because of the false),
 272         // but we put them in anyway, as opposed to just giving it 4 zeroes,
 273         // because it's just 4 additions and it's not good to rely on this
 274         // sort of assumption (right now it's true, but that may change).
 275         emitCurveTo(cx+mx,      cy+my,
 276                     cx+mx-C*my, cy+my+C*mx,
 277                     cx-my+C*mx, cy+mx+C*my,
 278                     cx-my,      cy+mx,
 279                     false);
 280         emitCurveTo(cx-my,      cy+mx,
 281                     cx-my-C*mx, cy+mx-C*my,
 282                     cx-mx-C*my, cy-my+C*mx,
 283                     cx-mx,      cy-my,
 284                     false);
 285     }
 286 
 287     // Return the intersection point of the lines (x0, y0) -> (x1, y1)
 288     // and (x0p, y0p) -> (x1p, y1p) in m[0] and m[1]
 289     private void computeMiter(final float x0, final float y0,
 290                               final float x1, final float y1,
 291                               final float x0p, final float y0p,
 292                               final float x1p, final float y1p,
 293                               final float[] m, int off)
 294     {
 295         float x10 = x1 - x0;
 296         float y10 = y1 - y0;
 297         float x10p = x1p - x0p;
 298         float y10p = y1p - y0p;
 299 
 300         // if this is 0, the lines are parallel. If they go in the
 301         // same direction, there is no intersection so m[off] and
 302         // m[off+1] will contain infinity, so no miter will be drawn.
 303         // If they go in the same direction that means that the start of the
 304         // current segment and the end of the previous segment have the same
 305         // tangent, in which case this method won't even be involved in
 306         // miter drawing because it won't be called by drawMiter (because
 307         // (mx == omx && my == omy) will be true, and drawMiter will return
 308         // immediately).
 309         float den = x10*y10p - x10p*y10;
 310         float t = x10p*(y0-y0p) - y10p*(x0-x0p);
 311         t /= den;
 312         m[off++] = x0 + t*x10;
 313         m[off] = y0 + t*y10;
 314     }
 315 
 316     private void drawMiter(final float pdx, final float pdy,
 317                            final float x0, final float y0,
 318                            final float dx, final float dy,
 319                            float omx, float omy, float mx, float my,
 320                            boolean rev)
 321     {
 322         if ((mx == omx && my == omy) ||
 323             (pdx == 0 && pdy == 0) ||
 324             (dx == 0 && dy == 0)) {
 325             return;
 326         }
 327 
 328         if (rev) {
 329             omx = -omx;
 330             omy = -omy;
 331             mx = -mx;
 332             my = -my;
 333         }
 334 
 335         computeMiter((x0 - pdx) + omx, (y0 - pdy) + omy, x0 + omx, y0 + omy,
 336                      (dx + x0) + mx, (dy + y0) + my, x0 + mx, y0 + my,
 337                      miter, 0);
 338 
 339         float lenSq = (miter[0]-x0)*(miter[0]-x0) + (miter[1]-y0)*(miter[1]-y0);
 340 
 341         if (lenSq < miterLimitSq) {
 342             emitLineTo(miter[0], miter[1], rev);
 343         }
 344     }
 345 
 346     public void moveTo(float x0, float y0) {
 347         if (prev == DRAWING_OP_TO) {
 348             finish();
 349         }
 350         this.sx0 = this.cx0 = x0;
 351         this.sy0 = this.cy0 = y0;
 352         this.cdx = this.sdx = 1;
 353         this.cdy = this.sdy = 0;
 354         this.prev = MOVE_TO;
 355     }
 356 
 357     public void lineTo(float x1, float y1) {
 358         float dx = x1 - cx0;
 359         float dy = y1 - cy0;
 360         if (dx == 0f && dy == 0f) {
 361             dx = 1;
 362         }
 363         computeOffset(dx, dy, lineWidth2, offset[0]);
 364         float mx = offset[0][0];
 365         float my = offset[0][1];
 366 
 367         drawJoin(cdx, cdy, cx0, cy0, dx, dy, cmx, cmy, mx, my);
 368 
 369         emitLineTo(cx0 + mx, cy0 + my);
 370         emitLineTo(x1 + mx, y1 + my);
 371 
 372         emitLineTo(cx0 - mx, cy0 - my, true);
 373         emitLineTo(x1 - mx, y1 - my, true);
 374 
 375         this.cmx = mx;
 376         this.cmy = my;
 377         this.cdx = dx;
 378         this.cdy = dy;
 379         this.cx0 = x1;
 380         this.cy0 = y1;
 381         this.prev = DRAWING_OP_TO;
 382     }
 383 
 384     public void closePath() {
 385         if (prev != DRAWING_OP_TO) {
 386             if (prev == CLOSE) {
 387                 return;
 388             }
 389             emitMoveTo(cx0, cy0 - lineWidth2);
 390             this.cmx = this.smx = 0;
 391             this.cmy = this.smy = -lineWidth2;
 392             this.cdx = this.sdx = 1;
 393             this.cdy = this.sdy = 0;
 394             finish();
 395             return;
 396         }
 397 
 398         if (cx0 != sx0 || cy0 != sy0) {
 399             lineTo(sx0, sy0);
 400         }
 401 
 402         drawJoin(cdx, cdy, cx0, cy0, sdx, sdy, cmx, cmy, smx, smy);
 403 
 404         emitLineTo(sx0 + smx, sy0 + smy);
 405 
 406         emitMoveTo(sx0 - smx, sy0 - smy);
 407         emitReverse();
 408 
 409         this.prev = CLOSE;
 410         emitClose();
 411     }
 412 
 413     private void emitReverse() {
 414         while(!reverse.isEmpty()) {
 415             reverse.pop(out);
 416         }
 417     }
 418 
 419     public void pathDone() {
 420         if (prev == DRAWING_OP_TO) {
 421             finish();
 422         }
 423 
 424         out.pathDone();
 425         // this shouldn't matter since this object won't be used
 426         // after the call to this method.
 427         this.prev = CLOSE;
 428     }
 429 
 430     private void finish() {
 431         if (capStyle == CAP_ROUND) {
 432             drawRoundCap(cx0, cy0, cmx, cmy);
 433         } else if (capStyle == CAP_SQUARE) {
 434             emitLineTo(cx0 - cmy + cmx, cy0 + cmx + cmy);
 435             emitLineTo(cx0 - cmy - cmx, cy0 + cmx - cmy);
 436         }
 437 
 438         emitReverse();
 439 
 440         if (capStyle == CAP_ROUND) {
 441             drawRoundCap(sx0, sy0, -smx, -smy);
 442         } else if (capStyle == CAP_SQUARE) {
 443             emitLineTo(sx0 + smy - smx, sy0 - smx - smy);
 444             emitLineTo(sx0 + smy + smx, sy0 - smx + smy);
 445         }
 446 
 447         emitClose();
 448     }
 449 
 450     private void emitMoveTo(final float x0, final float y0) {
 451         out.moveTo(x0, y0);
 452     }
 453 
 454     private void emitLineTo(final float x1, final float y1) {
 455         out.lineTo(x1, y1);
 456     }
 457 
 458     private void emitLineTo(final float x1, final float y1,
 459                             final boolean rev)
 460     {
 461         if (rev) {
 462             reverse.pushLine(x1, y1);
 463         } else {
 464             emitLineTo(x1, y1);
 465         }
 466     }
 467 
 468     private void emitQuadTo(final float x0, final float y0,
 469                             final float x1, final float y1,
 470                             final float x2, final float y2, final boolean rev)
 471     {
 472         if (rev) {
 473             reverse.pushQuad(x0, y0, x1, y1);
 474         } else {
 475             out.quadTo(x1, y1, x2, y2);
 476         }
 477     }
 478 
 479     private void emitCurveTo(final float x0, final float y0,
 480                              final float x1, final float y1,
 481                              final float x2, final float y2,
 482                              final float x3, final float y3, final boolean rev)
 483     {
 484         if (rev) {
 485             reverse.pushCubic(x0, y0, x1, y1, x2, y2);
 486         } else {
 487             out.curveTo(x1, y1, x2, y2, x3, y3);
 488         }
 489     }
 490 
 491     private void emitClose() {
 492         out.closePath();
 493     }
 494 
 495     private void drawJoin(float pdx, float pdy,
 496                           float x0, float y0,
 497                           float dx, float dy,
 498                           float omx, float omy,
 499                           float mx, float my)
 500     {
 501         if (prev != DRAWING_OP_TO) {
 502             emitMoveTo(x0 + mx, y0 + my);
 503             this.sdx = dx;
 504             this.sdy = dy;
 505             this.smx = mx;
 506             this.smy = my;
 507         } else {
 508             boolean cw = isCW(pdx, pdy, dx, dy);
 509             if (joinStyle == JOIN_MITER) {
 510                 drawMiter(pdx, pdy, x0, y0, dx, dy, omx, omy, mx, my, cw);
 511             } else if (joinStyle == JOIN_ROUND) {
 512                 drawRoundJoin(x0, y0,
 513                               omx, omy,
 514                               mx, my, cw,
 515                               ROUND_JOIN_THRESHOLD);
 516             }
 517             emitLineTo(x0, y0, !cw);
 518         }
 519         prev = DRAWING_OP_TO;
 520     }
 521 
 522     private static boolean within(final float x1, final float y1,
 523                                   final float x2, final float y2,
 524                                   final float ERR)
 525     {
 526         assert ERR > 0 : "";
 527         // compare taxicab distance. ERR will always be small, so using
 528         // true distance won't give much benefit
 529         return (Helpers.within(x1, x2, ERR) &&  // we want to avoid calling Math.abs
 530                 Helpers.within(y1, y2, ERR)); // this is just as good.
 531     }
 532 
 533     private void getLineOffsets(float x1, float y1,
 534                                 float x2, float y2,
 535                                 float[] left, float[] right) {
 536         computeOffset(x2 - x1, y2 - y1, lineWidth2, offset[0]);
 537         left[0] = x1 + offset[0][0];
 538         left[1] = y1 + offset[0][1];
 539         left[2] = x2 + offset[0][0];
 540         left[3] = y2 + offset[0][1];
 541         right[0] = x1 - offset[0][0];
 542         right[1] = y1 - offset[0][1];
 543         right[2] = x2 - offset[0][0];
 544         right[3] = y2 - offset[0][1];
 545     }
 546 
 547     private int computeOffsetCubic(float[] pts, final int off,
 548                                    float[] leftOff, float[] rightOff)
 549     {
 550         // if p1=p2 or p3=p4 it means that the derivative at the endpoint
 551         // vanishes, which creates problems with computeOffset. Usually
 552         // this happens when this stroker object is trying to winden
 553         // a curve with a cusp. What happens is that curveTo splits
 554         // the input curve at the cusp, and passes it to this function.
 555         // because of inaccuracies in the splitting, we consider points
 556         // equal if they're very close to each other.
 557         final float x1 = pts[off + 0], y1 = pts[off + 1];
 558         final float x2 = pts[off + 2], y2 = pts[off + 3];
 559         final float x3 = pts[off + 4], y3 = pts[off + 5];
 560         final float x4 = pts[off + 6], y4 = pts[off + 7];
 561 
 562         float dx4 = x4 - x3;
 563         float dy4 = y4 - y3;
 564         float dx1 = x2 - x1;
 565         float dy1 = y2 - y1;
 566 
 567         // if p1 == p2 && p3 == p4: draw line from p1->p4, unless p1 == p4,
 568         // in which case ignore if p1 == p2
 569         final boolean p1eqp2 = within(x1,y1,x2,y2, 6 * Math.ulp(y2));
 570         final boolean p3eqp4 = within(x3,y3,x4,y4, 6 * Math.ulp(y4));
 571         if (p1eqp2 && p3eqp4) {
 572             getLineOffsets(x1, y1, x4, y4, leftOff, rightOff);
 573             return 4;
 574         } else if (p1eqp2) {
 575             dx1 = x3 - x1;
 576             dy1 = y3 - y1;
 577         } else if (p3eqp4) {
 578             dx4 = x4 - x2;
 579             dy4 = y4 - y2;
 580         }
 581 
 582         // if p2-p1 and p4-p3 are parallel, that must mean this curve is a line
 583         float dotsq = (dx1 * dx4 + dy1 * dy4);
 584         dotsq = dotsq * dotsq;
 585         float l1sq = dx1 * dx1 + dy1 * dy1, l4sq = dx4 * dx4 + dy4 * dy4;
 586         if (Helpers.within(dotsq, l1sq * l4sq, 4 * Math.ulp(dotsq))) {
 587             getLineOffsets(x1, y1, x4, y4, leftOff, rightOff);
 588             return 4;
 589         }
 590 
 591 //      What we're trying to do in this function is to approximate an ideal
 592 //      offset curve (call it I) of the input curve B using a bezier curve Bp.
 593 //      The constraints I use to get the equations are:
 594 //
 595 //      1. The computed curve Bp should go through I(0) and I(1). These are
 596 //      x1p, y1p, x4p, y4p, which are p1p and p4p. We still need to find
 597 //      4 variables: the x and y components of p2p and p3p (i.e. x2p, y2p, x3p, y3p).
 598 //
 599 //      2. Bp should have slope equal in absolute value to I at the endpoints. So,
 600 //      (by the way, the operator || in the comments below means "aligned with".
 601 //      It is defined on vectors, so when we say I'(0) || Bp'(0) we mean that
 602 //      vectors I'(0) and Bp'(0) are aligned, which is the same as saying
 603 //      that the tangent lines of I and Bp at 0 are parallel. Mathematically
 604 //      this means (I'(t) || Bp'(t)) <==> (I'(t) = c * Bp'(t)) where c is some
 605 //      nonzero constant.)
 606 //      I'(0) || Bp'(0) and I'(1) || Bp'(1). Obviously, I'(0) || B'(0) and
 607 //      I'(1) || B'(1); therefore, Bp'(0) || B'(0) and Bp'(1) || B'(1).
 608 //      We know that Bp'(0) || (p2p-p1p) and Bp'(1) || (p4p-p3p) and the same
 609 //      is true for any bezier curve; therefore, we get the equations
 610 //          (1) p2p = c1 * (p2-p1) + p1p
 611 //          (2) p3p = c2 * (p4-p3) + p4p
 612 //      We know p1p, p4p, p2, p1, p3, and p4; therefore, this reduces the number
 613 //      of unknowns from 4 to 2 (i.e. just c1 and c2).
 614 //      To eliminate these 2 unknowns we use the following constraint:
 615 //
 616 //      3. Bp(0.5) == I(0.5). Bp(0.5)=(x,y) and I(0.5)=(xi,yi), and I should note
 617 //      that I(0.5) is *the only* reason for computing dxm,dym. This gives us
 618 //          (3) Bp(0.5) = (p1p + 3 * (p2p + p3p) + p4p)/8, which is equivalent to
 619 //          (4) p2p + p3p = (Bp(0.5)*8 - p1p - p4p) / 3
 620 //      We can substitute (1) and (2) from above into (4) and we get:
 621 //          (5) c1*(p2-p1) + c2*(p4-p3) = (Bp(0.5)*8 - p1p - p4p)/3 - p1p - p4p
 622 //      which is equivalent to
 623 //          (6) c1*(p2-p1) + c2*(p4-p3) = (4/3) * (Bp(0.5) * 2 - p1p - p4p)
 624 //
 625 //      The right side of this is a 2D vector, and we know I(0.5), which gives us
 626 //      Bp(0.5), which gives us the value of the right side.
 627 //      The left side is just a matrix vector multiplication in disguise. It is
 628 //
 629 //      [x2-x1, x4-x3][c1]
 630 //      [y2-y1, y4-y3][c2]
 631 //      which, is equal to
 632 //      [dx1, dx4][c1]
 633 //      [dy1, dy4][c2]
 634 //      At this point we are left with a simple linear system and we solve it by
 635 //      getting the inverse of the matrix above. Then we use [c1,c2] to compute
 636 //      p2p and p3p.
 637 
 638         float x = 0.125f * (x1 + 3 * (x2 + x3) + x4);
 639         float y = 0.125f * (y1 + 3 * (y2 + y3) + y4);
 640         // (dxm,dym) is some tangent of B at t=0.5. This means it's equal to
 641         // c*B'(0.5) for some constant c.
 642         float dxm = x3 + x4 - x1 - x2, dym = y3 + y4 - y1 - y2;
 643 
 644         // this computes the offsets at t=0, 0.5, 1, using the property that
 645         // for any bezier curve the vectors p2-p1 and p4-p3 are parallel to
 646         // the (dx/dt, dy/dt) vectors at the endpoints.
 647         computeOffset(dx1, dy1, lineWidth2, offset[0]);
 648         computeOffset(dxm, dym, lineWidth2, offset[1]);
 649         computeOffset(dx4, dy4, lineWidth2, offset[2]);
 650         float x1p = x1 + offset[0][0]; // start
 651         float y1p = y1 + offset[0][1]; // point
 652         float xi  = x + offset[1][0]; // interpolation
 653         float yi  = y + offset[1][1]; // point
 654         float x4p = x4 + offset[2][0]; // end
 655         float y4p = y4 + offset[2][1]; // point
 656 
 657         float invdet43 = 4f / (3f * (dx1 * dy4 - dy1 * dx4));
 658 
 659         float two_pi_m_p1_m_p4x = 2*xi - x1p - x4p;
 660         float two_pi_m_p1_m_p4y = 2*yi - y1p - y4p;
 661         float c1 = invdet43 * (dy4 * two_pi_m_p1_m_p4x - dx4 * two_pi_m_p1_m_p4y);
 662         float c2 = invdet43 * (dx1 * two_pi_m_p1_m_p4y - dy1 * two_pi_m_p1_m_p4x);
 663 
 664         float x2p, y2p, x3p, y3p;
 665         x2p = x1p + c1*dx1;
 666         y2p = y1p + c1*dy1;
 667         x3p = x4p + c2*dx4;
 668         y3p = y4p + c2*dy4;
 669 
 670         leftOff[0] = x1p; leftOff[1] = y1p;
 671         leftOff[2] = x2p; leftOff[3] = y2p;
 672         leftOff[4] = x3p; leftOff[5] = y3p;
 673         leftOff[6] = x4p; leftOff[7] = y4p;
 674 
 675         x1p = x1 - offset[0][0]; y1p = y1 - offset[0][1];
 676         xi = xi - 2 * offset[1][0]; yi = yi - 2 * offset[1][1];
 677         x4p = x4 - offset[2][0]; y4p = y4 - offset[2][1];
 678 
 679         two_pi_m_p1_m_p4x = 2*xi - x1p - x4p;
 680         two_pi_m_p1_m_p4y = 2*yi - y1p - y4p;
 681         c1 = invdet43 * (dy4 * two_pi_m_p1_m_p4x - dx4 * two_pi_m_p1_m_p4y);
 682         c2 = invdet43 * (dx1 * two_pi_m_p1_m_p4y - dy1 * two_pi_m_p1_m_p4x);
 683 
 684         x2p = x1p + c1*dx1;
 685         y2p = y1p + c1*dy1;
 686         x3p = x4p + c2*dx4;
 687         y3p = y4p + c2*dy4;
 688 
 689         rightOff[0] = x1p; rightOff[1] = y1p;
 690         rightOff[2] = x2p; rightOff[3] = y2p;
 691         rightOff[4] = x3p; rightOff[5] = y3p;
 692         rightOff[6] = x4p; rightOff[7] = y4p;
 693         return 8;
 694     }
 695 
 696     // compute offset curves using bezier spline through t=0.5 (i.e.
 697     // ComputedCurve(0.5) == IdealParallelCurve(0.5))
 698     // return the kind of curve in the right and left arrays.
 699     private int computeOffsetQuad(float[] pts, final int off,
 700                                   float[] leftOff, float[] rightOff)
 701     {
 702         final float x1 = pts[off + 0], y1 = pts[off + 1];
 703         final float x2 = pts[off + 2], y2 = pts[off + 3];
 704         final float x3 = pts[off + 4], y3 = pts[off + 5];
 705 
 706         float dx3 = x3 - x2;
 707         float dy3 = y3 - y2;
 708         float dx1 = x2 - x1;
 709         float dy1 = y2 - y1;
 710 
 711         // if p1=p2 or p3=p4 it means that the derivative at the endpoint
 712         // vanishes, which creates problems with computeOffset. Usually
 713         // this happens when this stroker object is trying to winden
 714         // a curve with a cusp. What happens is that curveTo splits
 715         // the input curve at the cusp, and passes it to this function.
 716         // because of inaccuracies in the splitting, we consider points
 717         // equal if they're very close to each other.
 718 
 719         // if p1 == p2 && p3 == p4: draw line from p1->p4, unless p1 == p4,
 720         // in which case ignore.
 721         final boolean p1eqp2 = within(x1,y1,x2,y2, 6 * Math.ulp(y2));
 722         final boolean p2eqp3 = within(x2,y2,x3,y3, 6 * Math.ulp(y3));
 723         if (p1eqp2 || p2eqp3) {
 724             getLineOffsets(x1, y1, x3, y3, leftOff, rightOff);
 725             return 4;
 726         }
 727 
 728         // if p2-p1 and p4-p3 are parallel, that must mean this curve is a line
 729         float dotsq = (dx1 * dx3 + dy1 * dy3);
 730         dotsq = dotsq * dotsq;
 731         float l1sq = dx1 * dx1 + dy1 * dy1, l3sq = dx3 * dx3 + dy3 * dy3;
 732         if (Helpers.within(dotsq, l1sq * l3sq, 4 * Math.ulp(dotsq))) {
 733             getLineOffsets(x1, y1, x3, y3, leftOff, rightOff);
 734             return 4;
 735         }
 736 
 737         // this computes the offsets at t=0, 0.5, 1, using the property that
 738         // for any bezier curve the vectors p2-p1 and p4-p3 are parallel to
 739         // the (dx/dt, dy/dt) vectors at the endpoints.
 740         computeOffset(dx1, dy1, lineWidth2, offset[0]);
 741         computeOffset(dx3, dy3, lineWidth2, offset[1]);
 742         float x1p = x1 + offset[0][0]; // start
 743         float y1p = y1 + offset[0][1]; // point
 744         float x3p = x3 + offset[1][0]; // end
 745         float y3p = y3 + offset[1][1]; // point
 746 
 747         computeMiter(x1p, y1p, x1p+dx1, y1p+dy1, x3p, y3p, x3p-dx3, y3p-dy3, leftOff, 2);
 748         leftOff[0] = x1p; leftOff[1] = y1p;
 749         leftOff[4] = x3p; leftOff[5] = y3p;
 750         x1p = x1 - offset[0][0]; y1p = y1 - offset[0][1];
 751         x3p = x3 - offset[1][0]; y3p = y3 - offset[1][1];
 752         computeMiter(x1p, y1p, x1p+dx1, y1p+dy1, x3p, y3p, x3p-dx3, y3p-dy3, rightOff, 2);
 753         rightOff[0] = x1p; rightOff[1] = y1p;
 754         rightOff[4] = x3p; rightOff[5] = y3p;
 755         return 6;
 756     }
 757 
 758     // This is where the curve to be processed is put. We give it
 759     // enough room to store 2 curves: one for the current subdivision, the
 760     // other for the rest of the curve.
 761     private float[][] middle = new float[2][8];
 762     private float[] lp = new float[8];
 763     private float[] rp = new float[8];
 764     private static final int MAX_N_CURVES = 11;
 765     private float[] subdivTs = new float[MAX_N_CURVES - 1];
 766 
 767     private void somethingTo(final int type) {
 768         // need these so we can update the state at the end of this method
 769         final float xf = middle[0][type-2], yf = middle[0][type-1];
 770         float dxs = middle[0][2] - middle[0][0];
 771         float dys = middle[0][3] - middle[0][1];
 772         float dxf = middle[0][type - 2] - middle[0][type - 4];
 773         float dyf = middle[0][type - 1] - middle[0][type - 3];
 774         switch(type) {
 775         case 6:
 776             if ((dxs == 0f && dys == 0f) ||
 777                 (dxf == 0f && dyf == 0f)) {
 778                dxs = dxf = middle[0][4] - middle[0][0];
 779                dys = dyf = middle[0][5] - middle[0][1];
 780             }
 781             break;
 782         case 8:
 783             boolean p1eqp2 = (dxs == 0f && dys == 0f);
 784             boolean p3eqp4 = (dxf == 0f && dyf == 0f);
 785             if (p1eqp2) {
 786                 dxs = middle[0][4] - middle[0][0];
 787                 dys = middle[0][5] - middle[0][1];
 788                 if (dxs == 0f && dys == 0f) {
 789                     dxs = middle[0][6] - middle[0][0];
 790                     dys = middle[0][7] - middle[0][1];
 791                 }
 792             }
 793             if (p3eqp4) {
 794                 dxf = middle[0][6] - middle[0][2];
 795                 dyf = middle[0][7] - middle[0][3];
 796                 if (dxf == 0f && dyf == 0f) {
 797                     dxf = middle[0][6] - middle[0][0];
 798                     dyf = middle[0][7] - middle[0][1];
 799                 }
 800             }
 801         }
 802         if (dxs == 0f && dys == 0f) {
 803             // this happens iff the "curve" is just a point
 804             lineTo(middle[0][0], middle[0][1]);
 805             return;
 806         }
 807         // if these vectors are too small, normalize them, to avoid future
 808         // precision problems.
 809         if (Math.abs(dxs) < 0.1f && Math.abs(dys) < 0.1f) {
 810             double len = Math.hypot(dxs, dys);
 811             dxs = (float)(dxs / len);
 812             dys = (float)(dys / len);
 813         }
 814         if (Math.abs(dxf) < 0.1f && Math.abs(dyf) < 0.1f) {
 815             double len = Math.hypot(dxf, dyf);
 816             dxf = (float)(dxf / len);
 817             dyf = (float)(dyf / len);
 818         }
 819 
 820         computeOffset(dxs, dys, lineWidth2, offset[0]);
 821         final float mx = offset[0][0];
 822         final float my = offset[0][1];
 823         drawJoin(cdx, cdy, cx0, cy0, dxs, dys, cmx, cmy, mx, my);
 824 
 825         int nSplits = findSubdivPoints(middle[0], subdivTs, type,lineWidth2);
 826 
 827         int kind = 0;
 828         Iterator<float[]> it = Curve.breakPtsAtTs(middle, type, subdivTs, nSplits);
 829         while(it.hasNext()) {
 830             float[] curCurve = it.next();
 831 
 832             kind = 0;
 833             switch (type) {
 834             case 8:
 835                 kind = computeOffsetCubic(curCurve, 0, lp, rp);
 836                 break;
 837             case 6:
 838                 kind = computeOffsetQuad(curCurve, 0, lp, rp);
 839                 break;
 840             }
 841             if (kind != 0) {
 842                 emitLineTo(lp[0], lp[1]);
 843                 switch(kind) {
 844                 case 8:
 845                     emitCurveTo(lp[0], lp[1], lp[2], lp[3], lp[4], lp[5], lp[6], lp[7], false);
 846                     emitCurveTo(rp[0], rp[1], rp[2], rp[3], rp[4], rp[5], rp[6], rp[7], true);
 847                     break;
 848                 case 6:
 849                     emitQuadTo(lp[0], lp[1], lp[2], lp[3], lp[4], lp[5], false);
 850                     emitQuadTo(rp[0], rp[1], rp[2], rp[3], rp[4], rp[5], true);
 851                     break;
 852                 case 4:
 853                     emitLineTo(lp[2], lp[3]);
 854                     emitLineTo(rp[0], rp[1], true);
 855                     break;
 856                 }
 857                 emitLineTo(rp[kind - 2], rp[kind - 1], true);
 858             }
 859         }
 860 
 861         this.cmx = (lp[kind - 2] - rp[kind - 2]) / 2;
 862         this.cmy = (lp[kind - 1] - rp[kind - 1]) / 2;
 863         this.cdx = dxf;
 864         this.cdy = dyf;
 865         this.cx0 = xf;
 866         this.cy0 = yf;
 867         this.prev = DRAWING_OP_TO;
 868     }
 869 
 870     // finds values of t where the curve in pts should be subdivided in order
 871     // to get good offset curves a distance of w away from the middle curve.
 872     // Stores the points in ts, and returns how many of them there were.
 873     private static Curve c = new Curve();
 874     private static int findSubdivPoints(float[] pts, float[] ts,
 875                                         final int type, final float w)
 876     {
 877         final float x12 = pts[2] - pts[0];
 878         final float y12 = pts[3] - pts[1];
 879         // if the curve is already parallel to either axis we gain nothing
 880         // from rotating it.
 881         if (y12 != 0f && x12 != 0f) {
 882             // we rotate it so that the first vector in the control polygon is
 883             // parallel to the x-axis. This will ensure that rotated quarter
 884             // circles won't be subdivided.
 885             final float hypot = (float)Math.sqrt(x12 * x12 + y12 * y12);
 886             final float cos = x12 / hypot;
 887             final float sin = y12 / hypot;
 888             final float x1 = cos * pts[0] + sin * pts[1];
 889             final float y1 = cos * pts[1] - sin * pts[0];
 890             final float x2 = cos * pts[2] + sin * pts[3];
 891             final float y2 = cos * pts[3] - sin * pts[2];
 892             final float x3 = cos * pts[4] + sin * pts[5];
 893             final float y3 = cos * pts[5] - sin * pts[4];
 894             switch(type) {
 895             case 8:
 896                 final float x4 = cos * pts[6] + sin * pts[7];
 897                 final float y4 = cos * pts[7] - sin * pts[6];
 898                 c.set(x1, y1, x2, y2, x3, y3, x4, y4);
 899                 break;
 900             case 6:
 901                 c.set(x1, y1, x2, y2, x3, y3);
 902                 break;
 903             }
 904         } else {
 905             c.set(pts, type);
 906         }
 907 
 908         int ret = 0;
 909         // we subdivide at values of t such that the remaining rotated
 910         // curves are monotonic in x and y.
 911         ret += c.dxRoots(ts, ret);
 912         ret += c.dyRoots(ts, ret);
 913         // subdivide at inflection points.
 914         if (type == 8) {
 915             // quadratic curves can't have inflection points
 916             ret += c.infPoints(ts, ret);
 917         }
 918 
 919         // now we must subdivide at points where one of the offset curves will have
 920         // a cusp. This happens at ts where the radius of curvature is equal to w.
 921         ret += c.rootsOfROCMinusW(ts, ret, w, 0.0001f);
 922         ret = Helpers.filterOutNotInAB(ts, 0, ret, 0.0001f, 0.9999f);
 923         Helpers.isort(ts, 0, ret);
 924         return ret;
 925     }
 926 
 927     @Override public void curveTo(float x1, float y1,
 928                                   float x2, float y2,
 929                                   float x3, float y3)
 930     {
 931         middle[0][0] = cx0; middle[0][1] = cy0;
 932         middle[0][2] = x1; middle[0][3] = y1;
 933         middle[0][4] = x2; middle[0][5] = y2;
 934         middle[0][6] = x3; middle[0][7] = y3;
 935         somethingTo(8);
 936     }
 937 
 938     @Override public long getNativeConsumer() {
 939         throw new InternalError("Stroker doesn't use a native consumer");
 940     }
 941 
 942     @Override public void quadTo(float x1, float y1, float x2, float y2) {
 943         middle[0][0] = cx0; middle[0][1] = cy0;
 944         middle[0][2] = x1; middle[0][3] = y1;
 945         middle[0][4] = x2; middle[0][5] = y2;
 946         somethingTo(6);
 947     }
 948 
 949     // a stack of polynomial curves where each curve shares endpoints with
 950     // adjacent ones.
 951     private static final class PolyStack {
 952         float[] curves;
 953         int end;
 954         int[] curveTypes;
 955         int numCurves;
 956 
 957         private static final int INIT_SIZE = 50;
 958 
 959         PolyStack() {
 960             curves = new float[8 * INIT_SIZE];
 961             curveTypes = new int[INIT_SIZE];
 962             end = 0;
 963             numCurves = 0;
 964         }
 965 
 966         public boolean isEmpty() {
 967             return numCurves == 0;
 968         }
 969 
 970         private void ensureSpace(int n) {
 971             if (end + n >= curves.length) {
 972                 int newSize = (end + n) * 2;
 973                 curves = Arrays.copyOf(curves, newSize);
 974             }
 975             if (numCurves >= curveTypes.length) {
 976                 int newSize = numCurves * 2;
 977                 curveTypes = Arrays.copyOf(curveTypes, newSize);
 978             }
 979         }
 980 
 981         public void pushCubic(float x0, float y0,
 982                               float x1, float y1,
 983                               float x2, float y2)
 984         {
 985             ensureSpace(6);
 986             curveTypes[numCurves++] = 8;
 987             // assert(x0 == lastX && y0 == lastY)
 988 
 989             // we reverse the coordinate order to make popping easier
 990             curves[end++] = x2;    curves[end++] = y2;
 991             curves[end++] = x1;    curves[end++] = y1;
 992             curves[end++] = x0;    curves[end++] = y0;
 993         }
 994 
 995         public void pushQuad(float x0, float y0,
 996                              float x1, float y1)
 997         {
 998             ensureSpace(4);
 999             curveTypes[numCurves++] = 6;
1000             // assert(x0 == lastX && y0 == lastY)
1001             curves[end++] = x1;    curves[end++] = y1;
1002             curves[end++] = x0;    curves[end++] = y0;
1003         }
1004 
1005         public void pushLine(float x, float y) {
1006             ensureSpace(2);
1007             curveTypes[numCurves++] = 4;
1008             // assert(x0 == lastX && y0 == lastY)
1009             curves[end++] = x;    curves[end++] = y;
1010         }
1011 
1012         @SuppressWarnings("unused")
1013         public int pop(float[] pts) {
1014             int ret = curveTypes[numCurves - 1];
1015             numCurves--;
1016             end -= (ret - 2);
1017             System.arraycopy(curves, end, pts, 0, ret - 2);
1018             return ret;
1019         }
1020 
1021         public void pop(PathConsumer2D io) {
1022             numCurves--;
1023             int type = curveTypes[numCurves];
1024             end -= (type - 2);
1025             switch(type) {
1026             case 8:
1027                 io.curveTo(curves[end+0], curves[end+1],
1028                            curves[end+2], curves[end+3],
1029                            curves[end+4], curves[end+5]);
1030                 break;
1031             case 6:
1032                 io.quadTo(curves[end+0], curves[end+1],
1033                            curves[end+2], curves[end+3]);
1034                  break;
1035             case 4:
1036                 io.lineTo(curves[end], curves[end+1]);
1037             }
1038         }
1039 
1040         @Override
1041         public String toString() {
1042             String ret = "";
1043             int nc = numCurves;
1044             int end = this.end;
1045             while (nc > 0) {
1046                 nc--;
1047                 int type = curveTypes[numCurves];
1048                 end -= (type - 2);
1049                 switch(type) {
1050                 case 8:
1051                     ret += "cubic: ";
1052                     break;
1053                 case 6:
1054                     ret += "quad: ";
1055                     break;
1056                 case 4:
1057                     ret += "line: ";
1058                     break;
1059                 }
1060                 ret += Arrays.toString(Arrays.copyOfRange(curves, end, end+type-2)) + "\n";
1061             }
1062             return ret;
1063         }
1064     }
1065 }