1 /*

     2  * Copyright (c) 2007, 2011, 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 static java.lang.Math.PI;

    30 import static java.lang.Math.cos;

    31 import static java.lang.Math.sqrt;

    32 import static java.lang.Math.cbrt;

    33 import static java.lang.Math.acos;

    34 

    35 

    36 final class Helpers {

    37     private Helpers() {

    38         throw new Error("This is a non instantiable class");

    39     }

    40 

    41     static boolean within(final float x, final float y, final float err) {

    42         final float d = y - x;

    43         return (d <= err && d >= -err);

    44     }

    45 

    46     static boolean within(final double x, final double y, final double err) {

    47         final double d = y - x;

    48         return (d <= err && d >= -err);

    49     }

    50 

    51     static int quadraticRoots(final float a, final float b,

    52                               final float c, float[] zeroes, final int off)

    53     {

    54         int ret = off;

    55         float t;

    56         if (a != 0f) {

    57             final float dis = b*b - 4*a*c;

    58             if (dis > 0) {

    59                 final float sqrtDis = (float)Math.sqrt(dis);

    60                 // depending on the sign of b we use a slightly different

    61                 // algorithm than the traditional one to find one of the roots

    62                 // so we can avoid adding numbers of different signs (which

    63                 // might result in loss of precision).

    64                 if (b >= 0) {

    65                     zeroes[ret++] = (2 * c) / (-b - sqrtDis);

    66                     zeroes[ret++] = (-b - sqrtDis) / (2 * a);

    67                 } else {

    68                     zeroes[ret++] = (-b + sqrtDis) / (2 * a);

    69                     zeroes[ret++] = (2 * c) / (-b + sqrtDis);

    70                 }

    71             } else if (dis == 0f) {

    72                 t = (-b) / (2 * a);

    73                 zeroes[ret++] = t;

    74             }

    75         } else {

    76             if (b != 0f) {

    77                 t = (-c) / b;

    78                 zeroes[ret++] = t;

    79             }

    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(float d, float a, float b, float c,

    86                               float[] pts, final int off,

    87                               final float A, final float B)

    88     {

    89         if (d == 0) {

    90             int num = quadraticRoots(a, b, c, pts, off);

    91             return filterOutNotInAB(pts, off, num, A, B) - off;

    92         }

    93         // From Graphics Gems:

    94         // http://tog.acm.org/resources/GraphicsGems/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         a /= d;

   101         b /= d;

   102         c /= d;

   103 

   104         //  substitute x = y - A/3 to eliminate quadratic term:

   105         //     x^3 +Px + Q = 0

   106         //

   107         // Since we actually need P/3 and Q/2 for all of the

   108         // calculations that follow, we will calculate

   109         // p = P/3

   110         // q = Q/2

   111         // instead and use those values for simplicity of the code.

   112         double sq_A = a * a;

   113         double p = 1.0/3 * (-1.0/3 * sq_A + b);

   114         double q = 1.0/2 * (2.0/27 * a * sq_A - 1.0/3 * a * b + c);

   115 

   116         /* use Cardano's formula */

   117 

   118         double cb_p = p * p * p;

   119         double D = q * q + cb_p;

   120 

   121         int num;

   122         if (D < 0) {

   123             // see: http://en.wikipedia.org/wiki/Cubic_function#Trigonometric_.28and_hyperbolic.29_method

   124             final double phi = 1.0/3 * acos(-q / sqrt(-cb_p));

   125             final double t = 2 * sqrt(-p);

   126 

   127             pts[ off+0 ] =  (float)( t * cos(phi));

   128             pts[ off+1 ] =  (float)(-t * cos(phi + PI / 3));

   129             pts[ off+2 ] =  (float)(-t * cos(phi - PI / 3));

   130             num = 3;

   131         } else {

   132             final double sqrt_D = sqrt(D);

   133             final double u = cbrt(sqrt_D - q);

   134             final double v = - cbrt(sqrt_D + q);

   135 

   136             pts[ off ] = (float)(u + v);

   137             num = 1;

   138 

   139             if (within(D, 0, 1e-8)) {

   140                 pts[off+1] = -(pts[off] / 2);

   141                 num = 2;

   142             }

   143         }

   144 

   145         final float sub = 1.0f/3 * a;

   146 

   147         for (int i = 0; i < num; ++i) {

   148             pts[ off+i ] -= sub;

   149         }

   150 

   151         return filterOutNotInAB(pts, off, num, A, B) - off;

   152     }

   153 

   154     // These use a hardcoded factor of 2 for increasing sizes. Perhaps this

   155     // should be provided as an argument.

   156     static float[] widenArray(float[] in, final int cursize, final int numToAdd) {

   157         if (in.length >= cursize + numToAdd) {

   158             return in;

   159         }

   160         return Arrays.copyOf(in, 2 * (cursize + numToAdd));

   161     }

   162 

   163     static int[] widenArray(int[] in, final int cursize, final int numToAdd) {

   164         if (in.length >= cursize + numToAdd) {

   165             return in;

   166         }

   167         return Arrays.copyOf(in, 2 * (cursize + numToAdd));

   168     }

   169 

   170     static float evalCubic(final float a, final float b,

   171                            final float c, final float d,

   172                            final float t)

   173     {

   174         return t * (t * (t * a + b) + c) + d;

   175     }

   176 

   177     static float evalQuad(final float a, final float b,

   178                           final float c, final float t)

   179     {

   180         return t * (t * a + b) + c;

   181     }

   182 

   183     // returns the index 1 past the last valid element remaining after filtering

   184     static int filterOutNotInAB(float[] nums, final int off, final int len,

   185                                 final float a, final float b)

   186     {

   187         int ret = off;

   188         for (int i = off; i < off + len; i++) {

   189             if (nums[i] >= a && nums[i] < b) {

   190                 nums[ret++] = nums[i];

   191             }

   192         }

   193         return ret;

   194     }

   195 

   196     static float polyLineLength(float[] poly, final int off, final int nCoords) {

   197         assert nCoords % 2 == 0 && poly.length >= off + nCoords : "";

   198         float acc = 0;

   199         for (int i = off + 2; i < off + nCoords; i += 2) {

   200             acc += linelen(poly[i], poly[i+1], poly[i-2], poly[i-1]);

   201         }

   202         return acc;

   203     }

   204 

   205     static float linelen(float x1, float y1, float x2, float y2) {

   206         final float dx = x2 - x1;

   207         final float dy = y2 - y1;

   208         return (float)Math.sqrt(dx*dx + dy*dy);

   209     }

   210 

   211     static void subdivide(float[] src, int srcoff, float[] left, int leftoff,

   212                           float[] right, int rightoff, int type)

   213     {

   214         switch(type) {

   215         case 6:

   216             Helpers.subdivideQuad(src, srcoff, left, leftoff, right, rightoff);

   217             break;

   218         case 8:

   219             Helpers.subdivideCubic(src, srcoff, left, leftoff, right, rightoff);

   220             break;

   221         default:

   222             throw new InternalError("Unsupported curve type");

   223         }

   224     }

   225 

   226     static void isort(float[] a, int off, int len) {

   227         for (int i = off + 1; i < off + len; i++) {

   228             float ai = a[i];

   229             int j = i - 1;

   230             for (; j >= off && a[j] > ai; j--) {

   231                 a[j+1] = a[j];

   232             }

   233             a[j+1] = ai;

   234         }

   235     }

   236 

   237     // Most of these are copied from classes in java.awt.geom because we need

   238     // float versions of these functions, and Line2D, CubicCurve2D,

   239     // QuadCurve2D don't provide them.

   240     /**

   241      * Subdivides the cubic curve specified by the coordinates

   242      * stored in the {@code src} array at indices {@code srcoff}

   243      * through ({@code srcoff} + 7) and stores the

   244      * resulting two subdivided curves into the two result arrays at the

   245      * corresponding indices.

   246      * Either or both of the {@code left} and {@code right}

   247      * arrays may be {@code null} or a reference to the same array

   248      * as the {@code src} array.

   249      * Note that the last point in the first subdivided curve is the

   250      * same as the first point in the second subdivided curve. Thus,

   251      * it is possible to pass the same array for {@code left}

   252      * and {@code right} and to use offsets, such as {@code rightoff}

   253      * equals ({@code leftoff} + 6), in order

   254      * to avoid allocating extra storage for this common point.

   255      * @param src the array holding the coordinates for the source curve

   256      * @param srcoff the offset into the array of the beginning of the

   257      * the 6 source coordinates

   258      * @param left the array for storing the coordinates for the first

   259      * half of the subdivided curve

   260      * @param leftoff the offset into the array of the beginning of the

   261      * the 6 left coordinates

   262      * @param right the array for storing the coordinates for the second

   263      * half of the subdivided curve

   264      * @param rightoff the offset into the array of the beginning of the

   265      * the 6 right coordinates

   266      * @since 1.7

   267      */

   268     static void subdivideCubic(float src[], int srcoff,

   269                                float left[], int leftoff,

   270                                float right[], int rightoff)

   271     {

   272         float x1 = src[srcoff + 0];

   273         float y1 = src[srcoff + 1];

   274         float ctrlx1 = src[srcoff + 2];

   275         float ctrly1 = src[srcoff + 3];

   276         float ctrlx2 = src[srcoff + 4];

   277         float ctrly2 = src[srcoff + 5];

   278         float x2 = src[srcoff + 6];

   279         float y2 = src[srcoff + 7];

   280         if (left != null) {

   281             left[leftoff + 0] = x1;

   282             left[leftoff + 1] = y1;

   283         }

   284         if (right != null) {

   285             right[rightoff + 6] = x2;

   286             right[rightoff + 7] = y2;

   287         }

   288         x1 = (x1 + ctrlx1) / 2.0f;

   289         y1 = (y1 + ctrly1) / 2.0f;

   290         x2 = (x2 + ctrlx2) / 2.0f;

   291         y2 = (y2 + ctrly2) / 2.0f;

   292         float centerx = (ctrlx1 + ctrlx2) / 2.0f;

   293         float centery = (ctrly1 + ctrly2) / 2.0f;

   294         ctrlx1 = (x1 + centerx) / 2.0f;

   295         ctrly1 = (y1 + centery) / 2.0f;

   296         ctrlx2 = (x2 + centerx) / 2.0f;

   297         ctrly2 = (y2 + centery) / 2.0f;

   298         centerx = (ctrlx1 + ctrlx2) / 2.0f;

   299         centery = (ctrly1 + ctrly2) / 2.0f;

   300         if (left != null) {

   301             left[leftoff + 2] = x1;

   302             left[leftoff + 3] = y1;

   303             left[leftoff + 4] = ctrlx1;

   304             left[leftoff + 5] = ctrly1;

   305             left[leftoff + 6] = centerx;

   306             left[leftoff + 7] = centery;

   307         }

   308         if (right != null) {

   309             right[rightoff + 0] = centerx;

   310             right[rightoff + 1] = centery;

   311             right[rightoff + 2] = ctrlx2;

   312             right[rightoff + 3] = ctrly2;

   313             right[rightoff + 4] = x2;

   314             right[rightoff + 5] = y2;

   315         }

   316     }

   317 

   318 

   319     static void subdivideCubicAt(float t, float src[], int srcoff,

   320                                  float left[], int leftoff,

   321                                  float right[], int rightoff)

   322     {

   323         float x1 = src[srcoff + 0];

   324         float y1 = src[srcoff + 1];

   325         float ctrlx1 = src[srcoff + 2];

   326         float ctrly1 = src[srcoff + 3];

   327         float ctrlx2 = src[srcoff + 4];

   328         float ctrly2 = src[srcoff + 5];

   329         float x2 = src[srcoff + 6];

   330         float y2 = src[srcoff + 7];

   331         if (left != null) {

   332             left[leftoff + 0] = x1;

   333             left[leftoff + 1] = y1;

   334         }

   335         if (right != null) {

   336             right[rightoff + 6] = x2;

   337             right[rightoff + 7] = y2;

   338         }

   339         x1 = x1 + t * (ctrlx1 - x1);

   340         y1 = y1 + t * (ctrly1 - y1);

   341         x2 = ctrlx2 + t * (x2 - ctrlx2);

   342         y2 = ctrly2 + t * (y2 - ctrly2);

   343         float centerx = ctrlx1 + t * (ctrlx2 - ctrlx1);

   344         float centery = ctrly1 + t * (ctrly2 - ctrly1);

   345         ctrlx1 = x1 + t * (centerx - x1);

   346         ctrly1 = y1 + t * (centery - y1);

   347         ctrlx2 = centerx + t * (x2 - centerx);

   348         ctrly2 = centery + t * (y2 - centery);

   349         centerx = ctrlx1 + t * (ctrlx2 - ctrlx1);

   350         centery = ctrly1 + t * (ctrly2 - ctrly1);

   351         if (left != null) {

   352             left[leftoff + 2] = x1;

   353             left[leftoff + 3] = y1;

   354             left[leftoff + 4] = ctrlx1;

   355             left[leftoff + 5] = ctrly1;

   356             left[leftoff + 6] = centerx;

   357             left[leftoff + 7] = centery;

   358         }

   359         if (right != null) {

   360             right[rightoff + 0] = centerx;

   361             right[rightoff + 1] = centery;

   362             right[rightoff + 2] = ctrlx2;

   363             right[rightoff + 3] = ctrly2;

   364             right[rightoff + 4] = x2;

   365             right[rightoff + 5] = y2;

   366         }

   367     }

   368 

   369     static void subdivideQuad(float src[], int srcoff,

   370                               float left[], int leftoff,

   371                               float right[], int rightoff)

   372     {

   373         float x1 = src[srcoff + 0];

   374         float y1 = src[srcoff + 1];

   375         float ctrlx = src[srcoff + 2];

   376         float ctrly = src[srcoff + 3];

   377         float x2 = src[srcoff + 4];

   378         float y2 = src[srcoff + 5];

   379         if (left != null) {

   380             left[leftoff + 0] = x1;

   381             left[leftoff + 1] = y1;

   382         }

   383         if (right != null) {

   384             right[rightoff + 4] = x2;

   385             right[rightoff + 5] = y2;

   386         }

   387         x1 = (x1 + ctrlx) / 2.0f;

   388         y1 = (y1 + ctrly) / 2.0f;

   389         x2 = (x2 + ctrlx) / 2.0f;

   390         y2 = (y2 + ctrly) / 2.0f;

   391         ctrlx = (x1 + x2) / 2.0f;

   392         ctrly = (y1 + y2) / 2.0f;

   393         if (left != null) {

   394             left[leftoff + 2] = x1;

   395             left[leftoff + 3] = y1;

   396             left[leftoff + 4] = ctrlx;

   397             left[leftoff + 5] = ctrly;

   398         }

   399         if (right != null) {

   400             right[rightoff + 0] = ctrlx;

   401             right[rightoff + 1] = ctrly;

   402             right[rightoff + 2] = x2;

   403             right[rightoff + 3] = y2;

   404         }

   405     }

   406 

   407     static void subdivideQuadAt(float t, float src[], int srcoff,

   408                                 float left[], int leftoff,

   409                                 float right[], int rightoff)

   410     {

   411         float x1 = src[srcoff + 0];

   412         float y1 = src[srcoff + 1];

   413         float ctrlx = src[srcoff + 2];

   414         float ctrly = src[srcoff + 3];

   415         float x2 = src[srcoff + 4];

   416         float y2 = src[srcoff + 5];

   417         if (left != null) {

   418             left[leftoff + 0] = x1;

   419             left[leftoff + 1] = y1;

   420         }

   421         if (right != null) {

   422             right[rightoff + 4] = x2;

   423             right[rightoff + 5] = y2;

   424         }

   425         x1 = x1 + t * (ctrlx - x1);

   426         y1 = y1 + t * (ctrly - y1);

   427         x2 = ctrlx + t * (x2 - ctrlx);

   428         y2 = ctrly + t * (y2 - ctrly);

   429         ctrlx = x1 + t * (x2 - x1);

   430         ctrly = y1 + t * (y2 - y1);

   431         if (left != null) {

   432             left[leftoff + 2] = x1;

   433             left[leftoff + 3] = y1;

   434             left[leftoff + 4] = ctrlx;

   435             left[leftoff + 5] = ctrly;

   436         }

   437         if (right != null) {

   438             right[rightoff + 0] = ctrlx;

   439             right[rightoff + 1] = ctrly;

   440             right[rightoff + 2] = x2;

   441             right[rightoff + 3] = y2;

   442         }

   443     }

   444 

   445     static void subdivideAt(float t, float src[], int srcoff,

   446                             float left[], int leftoff,

   447                             float right[], int rightoff, int size)

   448     {

   449         switch(size) {

   450         case 8:

   451             subdivideCubicAt(t, src, srcoff, left, leftoff, right, rightoff);

   452             break;

   453         case 6:

   454             subdivideQuadAt(t, src, srcoff, left, leftoff, right, rightoff);

   455             break;

   456         }

   457     }

   458 }