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 }