1 /* 2 * Copyright (c) 2007, 2017, Oracle and/or its affiliates. All rights reserved. 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4 * 5 * This code is free software; you can redistribute it and/or modify it 6 * under the terms of the GNU General Public License version 2 only, as 7 * published by the Free Software Foundation. Oracle designates this 8 * particular file as subject to the "Classpath" exception as provided 9 * by Oracle in the LICENSE file that accompanied this code. 10 * 11 * This code is distributed in the hope that it will be useful, but WITHOUT 12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14 * version 2 for more details (a copy is included in the LICENSE file that 15 * accompanied this code). 16 * 17 * You should have received a copy of the GNU General Public License version 18 * 2 along with this work; if not, write to the Free Software Foundation, 19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 20 * 21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 22 * or visit www.oracle.com if you need additional information or have any 23 * questions. 24 */ 25 26 package com.sun.marlin; 27 28 import static java.lang.Math.PI; 29 import java.util.Arrays; 30 import com.sun.marlin.stats.Histogram; 31 import com.sun.marlin.stats.StatLong; 32 33 final class DHelpers implements MarlinConst { 34 35 private DHelpers() { 36 throw new Error("This is a non instantiable class"); 37 } 38 39 static boolean within(final double x, final double y, final double err) { 40 final double d = y - x; 41 return (d <= err && d >= -err); 42 } 43 44 static int quadraticRoots(final double a, final double b, 45 final double c, double[] zeroes, final int off) 46 { 47 int ret = off; 48 double t; 49 if (a != 0.0d) { 50 final double dis = b*b - 4*a*c; 51 if (dis > 0.0d) { 52 final double sqrtDis = Math.sqrt(dis); 53 // depending on the sign of b we use a slightly different 54 // algorithm than the traditional one to find one of the roots 55 // so we can avoid adding numbers of different signs (which 56 // might result in loss of precision). 57 if (b >= 0.0d) { 58 zeroes[ret++] = (2.0d * c) / (-b - sqrtDis); 59 zeroes[ret++] = (-b - sqrtDis) / (2.0d * a); 60 } else { 61 zeroes[ret++] = (-b + sqrtDis) / (2.0d * a); 62 zeroes[ret++] = (2.0d * c) / (-b + sqrtDis); 63 } 64 } else if (dis == 0.0d) { 65 t = (-b) / (2.0d * a); 66 zeroes[ret++] = t; 67 } 68 } else { 69 if (b != 0.0d) { 70 t = (-c) / b; 71 zeroes[ret++] = t; 72 } 73 } 74 return ret - off; 75 } 76 77 // find the roots of g(t) = d*t^3 + a*t^2 + b*t + c in [A,B) 78 static int cubicRootsInAB(double d, double a, double b, double c, 79 double[] pts, final int off, 80 final double A, final double B) 81 { 82 if (d == 0.0d) { 83 int num = quadraticRoots(a, b, c, pts, off); 84 return filterOutNotInAB(pts, off, num, A, B) - off; 85 } 86 // From Graphics Gems: 87 // http://tog.acm.org/resources/GraphicsGems/gems/Roots3And4.c 88 // (also from awt.geom.CubicCurve2D. But here we don't need as 89 // much accuracy and we don't want to create arrays so we use 90 // our own customized version). 91 92 // normal form: x^3 + ax^2 + bx + c = 0 93 a /= d; 94 b /= d; 95 c /= d; 96 97 // substitute x = y - A/3 to eliminate quadratic term: 98 // x^3 +Px + Q = 0 99 // 100 // Since we actually need P/3 and Q/2 for all of the 101 // calculations that follow, we will calculate 102 // p = P/3 103 // q = Q/2 104 // instead and use those values for simplicity of the code. 105 double sq_A = a * a; 106 double p = (1.0d/3.0d) * ((-1.0d/3.0d) * sq_A + b); 107 double q = (1.0d/2.0d) * ((2.0d/27.0d) * a * sq_A - (1.0d/3.0d) * a * b + c); 108 109 // use Cardano's formula 110 111 double cb_p = p * p * p; 112 double D = q * q + cb_p; 113 114 int num; 115 if (D < 0.0d) { 116 // see: http://en.wikipedia.org/wiki/Cubic_function#Trigonometric_.28and_hyperbolic.29_method 117 final double phi = (1.0d/3.0d) * Math.acos(-q / Math.sqrt(-cb_p)); 118 final double t = 2.0d * Math.sqrt(-p); 119 120 pts[ off+0 ] = ( t * Math.cos(phi)); 121 pts[ off+1 ] = (-t * Math.cos(phi + (PI / 3.0d))); 122 pts[ off+2 ] = (-t * Math.cos(phi - (PI / 3.0d))); 123 num = 3; 124 } else { 125 final double sqrt_D = Math.sqrt(D); 126 final double u = Math.cbrt(sqrt_D - q); 127 final double v = - Math.cbrt(sqrt_D + q); 128 129 pts[ off ] = (u + v); 130 num = 1; 131 132 if (within(D, 0.0d, 1e-8d)) { 133 pts[off+1] = -(pts[off] / 2.0d); 134 num = 2; 135 } 136 } 137 138 final double sub = (1.0d/3.0d) * a; 139 140 for (int i = 0; i < num; ++i) { 141 pts[ off+i ] -= sub; 142 } 143 144 return filterOutNotInAB(pts, off, num, A, B) - off; 145 } 146 147 static double evalCubic(final double a, final double b, 148 final double c, final double d, 149 final double t) 150 { 151 return t * (t * (t * a + b) + c) + d; 152 } 153 154 static double evalQuad(final double a, final double b, 155 final double c, final double t) 156 { 157 return t * (t * a + b) + c; 158 } 159 160 // returns the index 1 past the last valid element remaining after filtering 161 static int filterOutNotInAB(double[] nums, final int off, final int len, 162 final double a, final double b) 163 { 164 int ret = off; 165 for (int i = off, end = off + len; i < end; i++) { 166 if (nums[i] >= a && nums[i] < b) { 167 nums[ret++] = nums[i]; 168 } 169 } 170 return ret; 171 } 172 173 static double linelen(double x1, double y1, double x2, double y2) { 174 final double dx = x2 - x1; 175 final double dy = y2 - y1; 176 return Math.sqrt(dx*dx + dy*dy); 177 } 178 179 static void subdivide(double[] src, int srcoff, double[] left, int leftoff, 180 double[] right, int rightoff, int type) 181 { 182 switch(type) { 183 case 6: 184 DHelpers.subdivideQuad(src, srcoff, left, leftoff, right, rightoff); 185 return; 186 case 8: 187 DHelpers.subdivideCubic(src, srcoff, left, leftoff, right, rightoff); 188 return; 189 default: 190 throw new InternalError("Unsupported curve type"); 191 } 192 } 193 194 static void isort(double[] a, int off, int len) { 195 for (int i = off + 1, end = off + len; i < end; i++) { 196 double ai = a[i]; 197 int j = i - 1; 198 for (; j >= off && a[j] > ai; j--) { 199 a[j+1] = a[j]; 200 } 201 a[j+1] = ai; 202 } 203 } 204 205 // Most of these are copied from classes in java.awt.geom because we need 206 // both single and double precision variants of these functions, and Line2D, 207 // CubicCurve2D, QuadCurve2D don't provide them. 208 /** 209 * Subdivides the cubic curve specified by the coordinates 210 * stored in the <code>src</code> array at indices <code>srcoff</code> 211 * through (<code>srcoff</code> + 7) and stores the 212 * resulting two subdivided curves into the two result arrays at the 213 * corresponding indices. 214 * Either or both of the <code>left</code> and <code>right</code> 215 * arrays may be <code>null</code> or a reference to the same array 216 * as the <code>src</code> array. 217 * Note that the last point in the first subdivided curve is the 218 * same as the first point in the second subdivided curve. Thus, 219 * it is possible to pass the same array for <code>left</code> 220 * and <code>right</code> and to use offsets, such as <code>rightoff</code> 221 * equals (<code>leftoff</code> + 6), in order 222 * to avoid allocating extra storage for this common point. 223 * @param src the array holding the coordinates for the source curve 224 * @param srcoff the offset into the array of the beginning of the 225 * the 6 source coordinates 226 * @param left the array for storing the coordinates for the first 227 * half of the subdivided curve 228 * @param leftoff the offset into the array of the beginning of the 229 * the 6 left coordinates 230 * @param right the array for storing the coordinates for the second 231 * half of the subdivided curve 232 * @param rightoff the offset into the array of the beginning of the 233 * the 6 right coordinates 234 * @since 1.7 235 */ 236 static void subdivideCubic(double[] src, int srcoff, 237 double[] left, int leftoff, 238 double[] right, int rightoff) 239 { 240 double x1 = src[srcoff + 0]; 241 double y1 = src[srcoff + 1]; 242 double ctrlx1 = src[srcoff + 2]; 243 double ctrly1 = src[srcoff + 3]; 244 double ctrlx2 = src[srcoff + 4]; 245 double ctrly2 = src[srcoff + 5]; 246 double x2 = src[srcoff + 6]; 247 double y2 = src[srcoff + 7]; 248 if (left != null) { 249 left[leftoff + 0] = x1; 250 left[leftoff + 1] = y1; 251 } 252 if (right != null) { 253 right[rightoff + 6] = x2; 254 right[rightoff + 7] = y2; 255 } 256 x1 = (x1 + ctrlx1) / 2.0d; 257 y1 = (y1 + ctrly1) / 2.0d; 258 x2 = (x2 + ctrlx2) / 2.0d; 259 y2 = (y2 + ctrly2) / 2.0d; 260 double centerx = (ctrlx1 + ctrlx2) / 2.0d; 261 double centery = (ctrly1 + ctrly2) / 2.0d; 262 ctrlx1 = (x1 + centerx) / 2.0d; 263 ctrly1 = (y1 + centery) / 2.0d; 264 ctrlx2 = (x2 + centerx) / 2.0d; 265 ctrly2 = (y2 + centery) / 2.0d; 266 centerx = (ctrlx1 + ctrlx2) / 2.0d; 267 centery = (ctrly1 + ctrly2) / 2.0d; 268 if (left != null) { 269 left[leftoff + 2] = x1; 270 left[leftoff + 3] = y1; 271 left[leftoff + 4] = ctrlx1; 272 left[leftoff + 5] = ctrly1; 273 left[leftoff + 6] = centerx; 274 left[leftoff + 7] = centery; 275 } 276 if (right != null) { 277 right[rightoff + 0] = centerx; 278 right[rightoff + 1] = centery; 279 right[rightoff + 2] = ctrlx2; 280 right[rightoff + 3] = ctrly2; 281 right[rightoff + 4] = x2; 282 right[rightoff + 5] = y2; 283 } 284 } 285 286 287 static void subdivideCubicAt(double t, double[] src, int srcoff, 288 double[] left, int leftoff, 289 double[] right, int rightoff) 290 { 291 double x1 = src[srcoff + 0]; 292 double y1 = src[srcoff + 1]; 293 double ctrlx1 = src[srcoff + 2]; 294 double ctrly1 = src[srcoff + 3]; 295 double ctrlx2 = src[srcoff + 4]; 296 double ctrly2 = src[srcoff + 5]; 297 double x2 = src[srcoff + 6]; 298 double y2 = src[srcoff + 7]; 299 if (left != null) { 300 left[leftoff + 0] = x1; 301 left[leftoff + 1] = y1; 302 } 303 if (right != null) { 304 right[rightoff + 6] = x2; 305 right[rightoff + 7] = y2; 306 } 307 x1 = x1 + t * (ctrlx1 - x1); 308 y1 = y1 + t * (ctrly1 - y1); 309 x2 = ctrlx2 + t * (x2 - ctrlx2); 310 y2 = ctrly2 + t * (y2 - ctrly2); 311 double centerx = ctrlx1 + t * (ctrlx2 - ctrlx1); 312 double centery = ctrly1 + t * (ctrly2 - ctrly1); 313 ctrlx1 = x1 + t * (centerx - x1); 314 ctrly1 = y1 + t * (centery - y1); 315 ctrlx2 = centerx + t * (x2 - centerx); 316 ctrly2 = centery + t * (y2 - centery); 317 centerx = ctrlx1 + t * (ctrlx2 - ctrlx1); 318 centery = ctrly1 + t * (ctrly2 - ctrly1); 319 if (left != null) { 320 left[leftoff + 2] = x1; 321 left[leftoff + 3] = y1; 322 left[leftoff + 4] = ctrlx1; 323 left[leftoff + 5] = ctrly1; 324 left[leftoff + 6] = centerx; 325 left[leftoff + 7] = centery; 326 } 327 if (right != null) { 328 right[rightoff + 0] = centerx; 329 right[rightoff + 1] = centery; 330 right[rightoff + 2] = ctrlx2; 331 right[rightoff + 3] = ctrly2; 332 right[rightoff + 4] = x2; 333 right[rightoff + 5] = y2; 334 } 335 } 336 337 static void subdivideQuad(double[] src, int srcoff, 338 double[] left, int leftoff, 339 double[] right, int rightoff) 340 { 341 double x1 = src[srcoff + 0]; 342 double y1 = src[srcoff + 1]; 343 double ctrlx = src[srcoff + 2]; 344 double ctrly = src[srcoff + 3]; 345 double x2 = src[srcoff + 4]; 346 double y2 = src[srcoff + 5]; 347 if (left != null) { 348 left[leftoff + 0] = x1; 349 left[leftoff + 1] = y1; 350 } 351 if (right != null) { 352 right[rightoff + 4] = x2; 353 right[rightoff + 5] = y2; 354 } 355 x1 = (x1 + ctrlx) / 2.0d; 356 y1 = (y1 + ctrly) / 2.0d; 357 x2 = (x2 + ctrlx) / 2.0d; 358 y2 = (y2 + ctrly) / 2.0d; 359 ctrlx = (x1 + x2) / 2.0d; 360 ctrly = (y1 + y2) / 2.0d; 361 if (left != null) { 362 left[leftoff + 2] = x1; 363 left[leftoff + 3] = y1; 364 left[leftoff + 4] = ctrlx; 365 left[leftoff + 5] = ctrly; 366 } 367 if (right != null) { 368 right[rightoff + 0] = ctrlx; 369 right[rightoff + 1] = ctrly; 370 right[rightoff + 2] = x2; 371 right[rightoff + 3] = y2; 372 } 373 } 374 375 static void subdivideQuadAt(double t, double[] src, int srcoff, 376 double[] left, int leftoff, 377 double[] right, int rightoff) 378 { 379 double x1 = src[srcoff + 0]; 380 double y1 = src[srcoff + 1]; 381 double ctrlx = src[srcoff + 2]; 382 double ctrly = src[srcoff + 3]; 383 double x2 = src[srcoff + 4]; 384 double y2 = src[srcoff + 5]; 385 if (left != null) { 386 left[leftoff + 0] = x1; 387 left[leftoff + 1] = y1; 388 } 389 if (right != null) { 390 right[rightoff + 4] = x2; 391 right[rightoff + 5] = y2; 392 } 393 x1 = x1 + t * (ctrlx - x1); 394 y1 = y1 + t * (ctrly - y1); 395 x2 = ctrlx + t * (x2 - ctrlx); 396 y2 = ctrly + t * (y2 - ctrly); 397 ctrlx = x1 + t * (x2 - x1); 398 ctrly = y1 + t * (y2 - y1); 399 if (left != null) { 400 left[leftoff + 2] = x1; 401 left[leftoff + 3] = y1; 402 left[leftoff + 4] = ctrlx; 403 left[leftoff + 5] = ctrly; 404 } 405 if (right != null) { 406 right[rightoff + 0] = ctrlx; 407 right[rightoff + 1] = ctrly; 408 right[rightoff + 2] = x2; 409 right[rightoff + 3] = y2; 410 } 411 } 412 413 static void subdivideAt(double t, double[] src, int srcoff, 414 double[] left, int leftoff, 415 double[] right, int rightoff, int size) 416 { 417 switch(size) { 418 case 8: 419 subdivideCubicAt(t, src, srcoff, left, leftoff, right, rightoff); 420 return; 421 case 6: 422 subdivideQuadAt(t, src, srcoff, left, leftoff, right, rightoff); 423 return; 424 } 425 } 426 427 // From sun.java2d.loops.GeneralRenderer: 428 429 static int outcode(final double x, final double y, 430 final double[] clipRect) 431 { 432 int code; 433 if (y < clipRect[0]) { 434 code = OUTCODE_TOP; 435 } else if (y >= clipRect[1]) { 436 code = OUTCODE_BOTTOM; 437 } else { 438 code = 0; 439 } 440 if (x < clipRect[2]) { 441 code |= OUTCODE_LEFT; 442 } else if (x >= clipRect[3]) { 443 code |= OUTCODE_RIGHT; 590 } 591 if (DO_STATS) { 592 // update used marks: 593 if (numCurves > curveTypesUseMark) { 594 curveTypesUseMark = numCurves; 595 } 596 if (end > curvesUseMark) { 597 curvesUseMark = end; 598 } 599 } 600 final byte[] _curveTypes = curveTypes; 601 final double[] _curves = curves; 602 int e = 0; 603 604 for (int i = 0; i < nc; i++) { 605 switch(_curveTypes[i]) { 606 case TYPE_LINETO: 607 io.lineTo(_curves[e], _curves[e+1]); 608 e += 2; 609 continue; 610 case TYPE_QUADTO: 611 io.quadTo(_curves[e+0], _curves[e+1], 612 _curves[e+2], _curves[e+3]); 613 e += 4; 614 continue; 615 case TYPE_CUBICTO: 616 io.curveTo(_curves[e+0], _curves[e+1], 617 _curves[e+2], _curves[e+3], 618 _curves[e+4], _curves[e+5]); 619 e += 6; 620 continue; 621 default: 622 } 623 } 624 numCurves = 0; 625 end = 0; 626 } 627 628 void popAll(final DPathConsumer2D io) { 629 int nc = numCurves; 630 if (nc == 0) { 631 return; 632 } 633 if (DO_STATS) { 634 // update used marks: 635 if (numCurves > curveTypesUseMark) { 636 curveTypesUseMark = numCurves; 637 } 638 if (end > curvesUseMark) { 639 curvesUseMark = end; 640 } 641 } 642 final byte[] _curveTypes = curveTypes; 643 final double[] _curves = curves; 644 int e = end; 645 646 while (nc != 0) { 647 switch(_curveTypes[--nc]) { 648 case TYPE_LINETO: 649 e -= 2; 650 io.lineTo(_curves[e], _curves[e+1]); 651 continue; 652 case TYPE_QUADTO: 653 e -= 4; 654 io.quadTo(_curves[e+0], _curves[e+1], 655 _curves[e+2], _curves[e+3]); 656 continue; 657 case TYPE_CUBICTO: 658 e -= 6; 659 io.curveTo(_curves[e+0], _curves[e+1], 660 _curves[e+2], _curves[e+3], 661 _curves[e+4], _curves[e+5]); 662 continue; 663 default: 664 } 665 } 666 numCurves = 0; 667 end = 0; 668 } 669 670 @Override 671 public String toString() { 672 String ret = ""; 673 int nc = numCurves; 674 int last = end; 675 int len; 676 while (nc != 0) { 677 switch(curveTypes[--nc]) { 678 case TYPE_LINETO: 679 len = 2; 680 ret += "line: "; 681 break; | 1 /* 2 * Copyright (c) 2007, 2018, 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 import com.sun.marlin.stats.Histogram; 30 import com.sun.marlin.stats.StatLong; 31 32 final class DHelpers implements MarlinConst { 33 34 private DHelpers() { 35 throw new Error("This is a non instantiable class"); 36 } 37 38 static boolean within(final double x, final double y, final double err) { 39 final double d = y - x; 40 return (d <= err && d >= -err); 41 } 42 43 static double evalCubic(final double a, final double b, 44 final double c, final double d, 45 final double t) 46 { 47 return t * (t * (t * a + b) + c) + d; 48 } 49 50 static double evalQuad(final double a, final double b, 51 final double c, final double t) 52 { 53 return t * (t * a + b) + c; 54 } 55 56 static int quadraticRoots(final double a, final double b, final double c, 57 final double[] zeroes, final int off) 58 { 59 int ret = off; 60 if (a != 0.0d) { 61 final double dis = b*b - 4.0d * a * c; 62 if (dis > 0.0d) { 63 final double sqrtDis = Math.sqrt(dis); 64 // depending on the sign of b we use a slightly different 65 // algorithm than the traditional one to find one of the roots 66 // so we can avoid adding numbers of different signs (which 67 // might result in loss of precision). 68 if (b >= 0.0d) { 69 zeroes[ret++] = (2.0d * c) / (-b - sqrtDis); 70 zeroes[ret++] = (-b - sqrtDis) / (2.0d * a); 71 } else { 72 zeroes[ret++] = (-b + sqrtDis) / (2.0d * a); 73 zeroes[ret++] = (2.0d * c) / (-b + sqrtDis); 74 } 75 } else if (dis == 0.0d) { 76 zeroes[ret++] = -b / (2.0d * a); 77 } 78 } else if (b != 0.0d) { 79 zeroes[ret++] = -c / b; 80 } 81 return ret - off; 82 } 83 84 // find the roots of g(t) = d*t^3 + a*t^2 + b*t + c in [A,B) 85 static int cubicRootsInAB(final double d, double a, double b, double c, 86 final double[] pts, final int off, 87 final double A, final double B) 88 { 89 if (d == 0.0d) { 90 final int num = quadraticRoots(a, b, c, pts, off); 91 return filterOutNotInAB(pts, off, num, A, B) - off; 92 } 93 // From Graphics Gems: 94 // https://github.com/erich666/GraphicsGems/blob/master/gems/Roots3And4.c 95 // (also from awt.geom.CubicCurve2D. But here we don't need as 96 // much accuracy and we don't want to create arrays so we use 97 // our own customized version). 98 99 // normal form: x^3 + ax^2 + bx + c = 0 100 101 /* 102 * TODO: cleanup all that code after reading Roots3And4.c 103 */ 104 a /= d; 105 b /= d; 106 c /= d; 107 108 // substitute x = y - A/3 to eliminate quadratic term: 109 // x^3 +Px + Q = 0 110 // 111 // Since we actually need P/3 and Q/2 for all of the 112 // calculations that follow, we will calculate 113 // p = P/3 114 // q = Q/2 115 // instead and use those values for simplicity of the code. 116 final double sub = (1.0d / 3.0d) * a; 117 final double sq_A = a * a; 118 final double p = (1.0d / 3.0d) * ((-1.0d / 3.0d) * sq_A + b); 119 final double q = (1.0d / 2.0d) * ((2.0d / 27.0d) * a * sq_A - sub * b + c); 120 121 // use Cardano's formula 122 123 final double cb_p = p * p * p; 124 final double D = q * q + cb_p; 125 126 int num; 127 if (D < 0.0d) { 128 // see: http://en.wikipedia.org/wiki/Cubic_function#Trigonometric_.28and_hyperbolic.29_method 129 final double phi = (1.0d / 3.0d) * Math.acos(-q / Math.sqrt(-cb_p)); 130 final double t = 2.0d * Math.sqrt(-p); 131 132 pts[off ] = ( t * Math.cos(phi) - sub); 133 pts[off + 1] = (-t * Math.cos(phi + (Math.PI / 3.0d)) - sub); 134 pts[off + 2] = (-t * Math.cos(phi - (Math.PI / 3.0d)) - sub); 135 num = 3; 136 } else { 137 final double sqrt_D = Math.sqrt(D); 138 final double u = Math.cbrt(sqrt_D - q); 139 final double v = - Math.cbrt(sqrt_D + q); 140 141 pts[off ] = (u + v - sub); 142 num = 1; 143 144 if (within(D, 0.0d, 1e-8d)) { 145 pts[off + 1] = ((-1.0d / 2.0d) * (u + v) - sub); 146 num = 2; 147 } 148 } 149 150 return filterOutNotInAB(pts, off, num, A, B) - off; 151 } 152 153 // returns the index 1 past the last valid element remaining after filtering 154 static int filterOutNotInAB(final double[] nums, final int off, final int len, 155 final double a, final double b) 156 { 157 int ret = off; 158 for (int i = off, end = off + len; i < end; i++) { 159 if (nums[i] >= a && nums[i] < b) { 160 nums[ret++] = nums[i]; 161 } 162 } 163 return ret; 164 } 165 166 static double fastLineLen(final double x0, final double y0, 167 final double x1, final double y1) 168 { 169 final double dx = x1 - x0; 170 final double dy = y1 - y0; 171 172 // use manhattan norm: 173 return Math.abs(dx) + Math.abs(dy); 174 } 175 176 static double linelen(final double x0, final double y0, 177 final double x1, final double y1) 178 { 179 final double dx = x1 - x0; 180 final double dy = y1 - y0; 181 return Math.sqrt(dx * dx + dy * dy); 182 } 183 184 static double fastQuadLen(final double x0, final double y0, 185 final double x1, final double y1, 186 final double x2, final double y2) 187 { 188 final double dx1 = x1 - x0; 189 final double dx2 = x2 - x1; 190 final double dy1 = y1 - y0; 191 final double dy2 = y2 - y1; 192 193 // use manhattan norm: 194 return Math.abs(dx1) + Math.abs(dx2) 195 + Math.abs(dy1) + Math.abs(dy2); 196 } 197 198 static double quadlen(final double x0, final double y0, 199 final double x1, final double y1, 200 final double x2, final double y2) 201 { 202 return (linelen(x0, y0, x1, y1) 203 + linelen(x1, y1, x2, y2) 204 + linelen(x0, y0, x2, y2)) / 2.0d; 205 } 206 207 static double fastCurvelen(final double x0, final double y0, 208 final double x1, final double y1, 209 final double x2, final double y2, 210 final double x3, final double y3) 211 { 212 final double dx1 = x1 - x0; 213 final double dx2 = x2 - x1; 214 final double dx3 = x3 - x2; 215 final double dy1 = y1 - y0; 216 final double dy2 = y2 - y1; 217 final double dy3 = y3 - y2; 218 219 // use manhattan norm: 220 return Math.abs(dx1) + Math.abs(dx2) + Math.abs(dx3) 221 + Math.abs(dy1) + Math.abs(dy2) + Math.abs(dy3); 222 } 223 224 static double curvelen(final double x0, final double y0, 225 final double x1, final double y1, 226 final double x2, final double y2, 227 final double x3, final double y3) 228 { 229 return (linelen(x0, y0, x1, y1) 230 + linelen(x1, y1, x2, y2) 231 + linelen(x2, y2, x3, y3) 232 + linelen(x0, y0, x3, y3)) / 2.0d; 233 } 234 235 // finds values of t where the curve in pts should be subdivided in order 236 // to get good offset curves a distance of w away from the middle curve. 237 // Stores the points in ts, and returns how many of them there were. 238 static int findSubdivPoints(final DCurve c, final double[] pts, 239 final double[] ts, final int type, 240 final double w2) 241 { 242 final double x12 = pts[2] - pts[0]; 243 final double y12 = pts[3] - pts[1]; 244 // if the curve is already parallel to either axis we gain nothing 245 // from rotating it. 246 if ((y12 != 0.0d && x12 != 0.0d)) { 247 // we rotate it so that the first vector in the control polygon is 248 // parallel to the x-axis. This will ensure that rotated quarter 249 // circles won't be subdivided. 250 final double hypot = Math.sqrt(x12 * x12 + y12 * y12); 251 final double cos = x12 / hypot; 252 final double sin = y12 / hypot; 253 final double x1 = cos * pts[0] + sin * pts[1]; 254 final double y1 = cos * pts[1] - sin * pts[0]; 255 final double x2 = cos * pts[2] + sin * pts[3]; 256 final double y2 = cos * pts[3] - sin * pts[2]; 257 final double x3 = cos * pts[4] + sin * pts[5]; 258 final double y3 = cos * pts[5] - sin * pts[4]; 259 260 switch(type) { 261 case 8: 262 final double x4 = cos * pts[6] + sin * pts[7]; 263 final double y4 = cos * pts[7] - sin * pts[6]; 264 c.set(x1, y1, x2, y2, x3, y3, x4, y4); 265 break; 266 case 6: 267 c.set(x1, y1, x2, y2, x3, y3); 268 break; 269 default: 270 } 271 } else { 272 c.set(pts, type); 273 } 274 275 int ret = 0; 276 // we subdivide at values of t such that the remaining rotated 277 // curves are monotonic in x and y. 278 ret += c.dxRoots(ts, ret); 279 ret += c.dyRoots(ts, ret); 280 281 // subdivide at inflection points. 282 if (type == 8) { 283 // quadratic curves can't have inflection points 284 ret += c.infPoints(ts, ret); 285 } 286 287 // now we must subdivide at points where one of the offset curves will have 288 // a cusp. This happens at ts where the radius of curvature is equal to w. 289 ret += c.rootsOfROCMinusW(ts, ret, w2, 0.0001d); 290 291 ret = filterOutNotInAB(ts, 0, ret, 0.0001d, 0.9999d); 292 isort(ts, ret); 293 return ret; 294 } 295 296 // finds values of t where the curve in pts should be subdivided in order 297 // to get intersections with the given clip rectangle. 298 // Stores the points in ts, and returns how many of them there were. 299 static int findClipPoints(final DCurve curve, final double[] pts, 300 final double[] ts, final int type, 301 final int outCodeOR, 302 final double[] clipRect) 303 { 304 curve.set(pts, type); 305 306 // clip rectangle (ymin, ymax, xmin, xmax) 307 int ret = 0; 308 309 if ((outCodeOR & OUTCODE_LEFT) != 0) { 310 ret += curve.xPoints(ts, ret, clipRect[2]); 311 } 312 if ((outCodeOR & OUTCODE_RIGHT) != 0) { 313 ret += curve.xPoints(ts, ret, clipRect[3]); 314 } 315 if ((outCodeOR & OUTCODE_TOP) != 0) { 316 ret += curve.yPoints(ts, ret, clipRect[0]); 317 } 318 if ((outCodeOR & OUTCODE_BOTTOM) != 0) { 319 ret += curve.yPoints(ts, ret, clipRect[1]); 320 } 321 isort(ts, ret); 322 return ret; 323 } 324 325 static void subdivide(final double[] src, 326 final double[] left, final double[] right, 327 final int type) 328 { 329 switch(type) { 330 case 8: 331 subdivideCubic(src, left, right); 332 return; 333 case 6: 334 subdivideQuad(src, left, right); 335 return; 336 default: 337 throw new InternalError("Unsupported curve type"); 338 } 339 } 340 341 static void isort(final double[] a, final int len) { 342 for (int i = 1, j; i < len; i++) { 343 final double ai = a[i]; 344 j = i - 1; 345 for (; j >= 0 && a[j] > ai; j--) { 346 a[j + 1] = a[j]; 347 } 348 a[j + 1] = ai; 349 } 350 } 351 352 // Most of these are copied from classes in java.awt.geom because we need 353 // both single and double precision variants of these functions, and Line2D, 354 // CubicCurve2D, QuadCurve2D don't provide them. 355 /** 356 * Subdivides the cubic curve specified by the coordinates 357 * stored in the <code>src</code> array at indices <code>srcoff</code> 358 * through (<code>srcoff</code> + 7) and stores the 359 * resulting two subdivided curves into the two result arrays at the 360 * corresponding indices. 361 * Either or both of the <code>left</code> and <code>right</code> 362 * arrays may be <code>null</code> or a reference to the same array 363 * as the <code>src</code> array. 364 * Note that the last point in the first subdivided curve is the 365 * same as the first point in the second subdivided curve. Thus, 366 * it is possible to pass the same array for <code>left</code> 367 * and <code>right</code> and to use offsets, such as <code>rightoff</code> 368 * equals (<code>leftoff</code> + 6), in order 369 * to avoid allocating extra storage for this common point. 370 * @param src the array holding the coordinates for the source curve 371 * @param left the array for storing the coordinates for the first 372 * half of the subdivided curve 373 * @param right the array for storing the coordinates for the second 374 * half of the subdivided curve 375 * @since 1.7 376 */ 377 static void subdivideCubic(final double[] src, 378 final double[] left, 379 final double[] right) 380 { 381 double x1 = src[0]; 382 double y1 = src[1]; 383 double cx1 = src[2]; 384 double cy1 = src[3]; 385 double cx2 = src[4]; 386 double cy2 = src[5]; 387 double x2 = src[6]; 388 double y2 = src[7]; 389 390 left[0] = x1; 391 left[1] = y1; 392 393 right[6] = x2; 394 right[7] = y2; 395 396 x1 = (x1 + cx1) / 2.0d; 397 y1 = (y1 + cy1) / 2.0d; 398 x2 = (x2 + cx2) / 2.0d; 399 y2 = (y2 + cy2) / 2.0d; 400 401 double cx = (cx1 + cx2) / 2.0d; 402 double cy = (cy1 + cy2) / 2.0d; 403 404 cx1 = (x1 + cx) / 2.0d; 405 cy1 = (y1 + cy) / 2.0d; 406 cx2 = (x2 + cx) / 2.0d; 407 cy2 = (y2 + cy) / 2.0d; 408 cx = (cx1 + cx2) / 2.0d; 409 cy = (cy1 + cy2) / 2.0d; 410 411 left[2] = x1; 412 left[3] = y1; 413 left[4] = cx1; 414 left[5] = cy1; 415 left[6] = cx; 416 left[7] = cy; 417 418 right[0] = cx; 419 right[1] = cy; 420 right[2] = cx2; 421 right[3] = cy2; 422 right[4] = x2; 423 right[5] = y2; 424 } 425 426 static void subdivideCubicAt(final double t, 427 final double[] src, final int offS, 428 final double[] pts, final int offL, final int offR) 429 { 430 double x1 = src[offS ]; 431 double y1 = src[offS + 1]; 432 double cx1 = src[offS + 2]; 433 double cy1 = src[offS + 3]; 434 double cx2 = src[offS + 4]; 435 double cy2 = src[offS + 5]; 436 double x2 = src[offS + 6]; 437 double y2 = src[offS + 7]; 438 439 pts[offL ] = x1; 440 pts[offL + 1] = y1; 441 442 pts[offR + 6] = x2; 443 pts[offR + 7] = y2; 444 445 x1 = x1 + t * (cx1 - x1); 446 y1 = y1 + t * (cy1 - y1); 447 x2 = cx2 + t * (x2 - cx2); 448 y2 = cy2 + t * (y2 - cy2); 449 450 double cx = cx1 + t * (cx2 - cx1); 451 double cy = cy1 + t * (cy2 - cy1); 452 453 cx1 = x1 + t * (cx - x1); 454 cy1 = y1 + t * (cy - y1); 455 cx2 = cx + t * (x2 - cx); 456 cy2 = cy + t * (y2 - cy); 457 cx = cx1 + t * (cx2 - cx1); 458 cy = cy1 + t * (cy2 - cy1); 459 460 pts[offL + 2] = x1; 461 pts[offL + 3] = y1; 462 pts[offL + 4] = cx1; 463 pts[offL + 5] = cy1; 464 pts[offL + 6] = cx; 465 pts[offL + 7] = cy; 466 467 pts[offR ] = cx; 468 pts[offR + 1] = cy; 469 pts[offR + 2] = cx2; 470 pts[offR + 3] = cy2; 471 pts[offR + 4] = x2; 472 pts[offR + 5] = y2; 473 } 474 475 static void subdivideQuad(final double[] src, 476 final double[] left, 477 final double[] right) 478 { 479 double x1 = src[0]; 480 double y1 = src[1]; 481 double cx = src[2]; 482 double cy = src[3]; 483 double x2 = src[4]; 484 double y2 = src[5]; 485 486 left[0] = x1; 487 left[1] = y1; 488 489 right[4] = x2; 490 right[5] = y2; 491 492 x1 = (x1 + cx) / 2.0d; 493 y1 = (y1 + cy) / 2.0d; 494 x2 = (x2 + cx) / 2.0d; 495 y2 = (y2 + cy) / 2.0d; 496 cx = (x1 + x2) / 2.0d; 497 cy = (y1 + y2) / 2.0d; 498 499 left[2] = x1; 500 left[3] = y1; 501 left[4] = cx; 502 left[5] = cy; 503 504 right[0] = cx; 505 right[1] = cy; 506 right[2] = x2; 507 right[3] = y2; 508 } 509 510 static void subdivideQuadAt(final double t, 511 final double[] src, final int offS, 512 final double[] pts, final int offL, final int offR) 513 { 514 double x1 = src[offS ]; 515 double y1 = src[offS + 1]; 516 double cx = src[offS + 2]; 517 double cy = src[offS + 3]; 518 double x2 = src[offS + 4]; 519 double y2 = src[offS + 5]; 520 521 pts[offL ] = x1; 522 pts[offL + 1] = y1; 523 524 pts[offR + 4] = x2; 525 pts[offR + 5] = y2; 526 527 x1 = x1 + t * (cx - x1); 528 y1 = y1 + t * (cy - y1); 529 x2 = cx + t * (x2 - cx); 530 y2 = cy + t * (y2 - cy); 531 cx = x1 + t * (x2 - x1); 532 cy = y1 + t * (y2 - y1); 533 534 pts[offL + 2] = x1; 535 pts[offL + 3] = y1; 536 pts[offL + 4] = cx; 537 pts[offL + 5] = cy; 538 539 pts[offR ] = cx; 540 pts[offR + 1] = cy; 541 pts[offR + 2] = x2; 542 pts[offR + 3] = y2; 543 } 544 545 static void subdivideLineAt(final double t, 546 final double[] src, final int offS, 547 final double[] pts, final int offL, final int offR) 548 { 549 double x1 = src[offS ]; 550 double y1 = src[offS + 1]; 551 double x2 = src[offS + 2]; 552 double y2 = src[offS + 3]; 553 554 pts[offL ] = x1; 555 pts[offL + 1] = y1; 556 557 pts[offR + 2] = x2; 558 pts[offR + 3] = y2; 559 560 x1 = x1 + t * (x2 - x1); 561 y1 = y1 + t * (y2 - y1); 562 563 pts[offL + 2] = x1; 564 pts[offL + 3] = y1; 565 566 pts[offR ] = x1; 567 pts[offR + 1] = y1; 568 } 569 570 static void subdivideAt(final double t, 571 final double[] src, final int offS, 572 final double[] pts, final int offL, final int type) 573 { 574 // if instead of switch (perf + most probable cases first) 575 if (type == 8) { 576 subdivideCubicAt(t, src, offS, pts, offL, offL + type); 577 } else if (type == 4) { 578 subdivideLineAt(t, src, offS, pts, offL, offL + type); 579 } else { 580 subdivideQuadAt(t, src, offS, pts, offL, offL + type); 581 } 582 } 583 584 // From sun.java2d.loops.GeneralRenderer: 585 586 static int outcode(final double x, final double y, 587 final double[] clipRect) 588 { 589 int code; 590 if (y < clipRect[0]) { 591 code = OUTCODE_TOP; 592 } else if (y >= clipRect[1]) { 593 code = OUTCODE_BOTTOM; 594 } else { 595 code = 0; 596 } 597 if (x < clipRect[2]) { 598 code |= OUTCODE_LEFT; 599 } else if (x >= clipRect[3]) { 600 code |= OUTCODE_RIGHT; 747 } 748 if (DO_STATS) { 749 // update used marks: 750 if (numCurves > curveTypesUseMark) { 751 curveTypesUseMark = numCurves; 752 } 753 if (end > curvesUseMark) { 754 curvesUseMark = end; 755 } 756 } 757 final byte[] _curveTypes = curveTypes; 758 final double[] _curves = curves; 759 int e = 0; 760 761 for (int i = 0; i < nc; i++) { 762 switch(_curveTypes[i]) { 763 case TYPE_LINETO: 764 io.lineTo(_curves[e], _curves[e+1]); 765 e += 2; 766 continue; 767 case TYPE_CUBICTO: 768 io.curveTo(_curves[e], _curves[e+1], 769 _curves[e+2], _curves[e+3], 770 _curves[e+4], _curves[e+5]); 771 e += 6; 772 continue; 773 case TYPE_QUADTO: 774 io.quadTo(_curves[e], _curves[e+1], 775 _curves[e+2], _curves[e+3]); 776 e += 4; 777 continue; 778 default: 779 } 780 } 781 numCurves = 0; 782 end = 0; 783 } 784 785 void popAll(final DPathConsumer2D io) { 786 int nc = numCurves; 787 if (nc == 0) { 788 return; 789 } 790 if (DO_STATS) { 791 // update used marks: 792 if (numCurves > curveTypesUseMark) { 793 curveTypesUseMark = numCurves; 794 } 795 if (end > curvesUseMark) { 796 curvesUseMark = end; 797 } 798 } 799 final byte[] _curveTypes = curveTypes; 800 final double[] _curves = curves; 801 int e = end; 802 803 while (nc != 0) { 804 switch(_curveTypes[--nc]) { 805 case TYPE_LINETO: 806 e -= 2; 807 io.lineTo(_curves[e], _curves[e+1]); 808 continue; 809 case TYPE_CUBICTO: 810 e -= 6; 811 io.curveTo(_curves[e], _curves[e+1], 812 _curves[e+2], _curves[e+3], 813 _curves[e+4], _curves[e+5]); 814 continue; 815 case TYPE_QUADTO: 816 e -= 4; 817 io.quadTo(_curves[e], _curves[e+1], 818 _curves[e+2], _curves[e+3]); 819 continue; 820 default: 821 } 822 } 823 numCurves = 0; 824 end = 0; 825 } 826 827 @Override 828 public String toString() { 829 String ret = ""; 830 int nc = numCurves; 831 int last = end; 832 int len; 833 while (nc != 0) { 834 switch(curveTypes[--nc]) { 835 case TYPE_LINETO: 836 len = 2; 837 ret += "line: "; 838 break; |