< prev index next >

modules/javafx.graphics/src/main/java/com/sun/marlin/DHelpers.java

Print this page


   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>&nbsp;+&nbsp;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>&nbsp;+&nbsp;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;


< prev index next >