1 /*

     2  * Copyright (c) 2007, 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 

    30 final class Helpers {

    31     private Helpers() {

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

    33     }

    34 

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

    36         final float d = y - x;

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

    38     }

    39 

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

    41         final double d = y - x;

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

    43     }

    44 

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

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

    47     {

    48         int ret = off;

    49         float t;

    50         if (a != 0f) {

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

    52             if (dis > 0) {

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

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

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

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

    57                 // might result in loss of precision).

    58                 if (b >= 0) {

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

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

    61                 } else {

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

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

    64                 }

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

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

    67                 zeroes[ret++] = t;

    68             }

    69         } else {

    70             if (b != 0f) {

    71                 t = (-c) / b;

    72                 zeroes[ret++] = t;

    73             }

    74         }

    75         return ret - off;

    76     }

    77 

    78     // find the roots of g(t) = a*t^3 + b*t^2 + c*t + d in [A,B)

    79     // We will not use Cardano's method, since it is complicated and

    80     // involves too many square and cubic roots. We will use Newton's method.

    81     // TODO: this should probably return ALL roots. Then the user can do

    82     // his own filtering of roots outside [A,B).

    83     static int cubicRootsInAB(final float a, final float b,

    84                               final float c, final float d,

    85                               float[] pts, final int off, final float E,

    86                               final float A, final float B)

    87     {

    88         if (a == 0) {

    89             return quadraticRoots(b, c, d, pts, off);

    90         }

    91         // the coefficients of g'(t). no dc variable because dc=c

    92         // we use these to get the critical points of g(t), which

    93         // we then use to chose starting points for Newton's method. These

    94         // should be very close to the actual roots.

    95         final float da = 3 * a;

    96         final float db = 2 * b;

    97         int numCritPts = quadraticRoots(da, db, c, pts, off+1);

    98         numCritPts = filterOutNotInAB(pts, off+1, numCritPts, A, B) - off - 1;

    99         // need them sorted.

   100         if (numCritPts == 2 && pts[off+1] > pts[off+2]) {

   101             float tmp = pts[off+1];

   102             pts[off+1] = pts[off+2];

   103             pts[off+2] = tmp;

   104         }

   105 

   106         int ret = off;

   107 

   108         // we don't actually care much about the extrema themselves. We

   109         // only use them to ensure that g(t) is monotonic in each

   110         // interval [pts[i],pts[i+1] (for i in off...off+numCritPts+1).

   111         // This will allow us to determine intervals containing exactly

   112         // one root.

   113         // The end points of the interval are always local extrema.

   114         pts[off] = A;

   115         pts[off + numCritPts + 1] = B;

   116         numCritPts += 2;

   117 

   118         float x0 = pts[off], fx0 = evalCubic(a, b, c, d, x0);

   119         for (int i = off; i < off + numCritPts - 1; i++) {

   120             float x1 = pts[i+1], fx1 = evalCubic(a, b, c, d, x1);

   121             if (fx0 == 0f) {

   122                 pts[ret++] = x0;

   123             } else if (fx1 * fx0 < 0f) { // have opposite signs

   124                 pts[ret++] = CubicNewton(a, b, c, d,

   125                         x0 + fx0 * (x1 - x0) / (fx0 - fx1), E);

   126             }

   127             x0 = x1;

   128             fx0 = fx1;

   129         }

   130         return ret - off;

   131     }

   132 

   133     // precondition: the polynomial to be evaluated must not be 0 at x0.

   134     static float CubicNewton(final float a, final float b,

   135                              final float c, final float d,

   136                              float x0, final float err)

   137     {

   138         // considering how this function is used, 10 should be more than enough

   139         final int itlimit = 10;

   140         float fx0 = evalCubic(a, b, c, d, x0);

   141         float x1;

   142         int count = 0;

   143         while(true) {

   144             x1 = x0 - (fx0 / evalCubic(0, 3 * a, 2 * b, c, x0));

   145             if (Math.abs(x1 - x0) < err * Math.abs(x1 + x0) || count == itlimit) {

   146                 break;

   147             }

   148             x0 = x1;

   149             fx0 = evalCubic(a, b, c, d, x0);

   150             count++;

   151         }

   152         return x1;

   153     }

   154 

   155     // fills the input array with numbers 0, INC, 2*INC, ...

   156     static void fillWithIdxes(final float[] data, final int[] idxes) {

   157         if (idxes.length > 0) {

   158             idxes[0] = 0;

   159             for (int i = 1; i < idxes.length; i++) {

   160                 idxes[i] = idxes[i-1] + (int)data[idxes[i-1]];

   161             }

   162         }

   163     }

   164 

   165     static void fillWithIdxes(final int[] idxes, final int inc) {

   166         if (idxes.length > 0) {

   167             idxes[0] = 0;

   168             for (int i = 1; i < idxes.length; i++) {

   169                 idxes[i] = idxes[i-1] + inc;

   170             }

   171         }

   172     }

   173 

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

   175     // should be provided as an argument.

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

   177         if (in == null) {

   178             return new float[5 * numToAdd];

   179         }

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

   181             return in;

   182         }

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

   184     }

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

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

   187             return in;

   188         }

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

   190     }

   191 

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

   193                            final float c, final float d,

   194                            final float t)

   195     {

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

   197     }

   198 

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

   200                           final float c, final float t)

   201     {

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

   203     }

   204 

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

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

   207                                 final float a, final float b)

   208     {

   209         int ret = off;

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

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

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

   213             }

   214         }

   215         return ret;

   216     }

   217 

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

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

   220         float acc = 0;

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

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

   223         }

   224         return acc;

   225     }

   226 

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

   228         return (float)Math.hypot(x2 - x1, y2 - y1);

   229     }

   230 

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

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

   233     {

   234         switch(type) {

   235         case 6:

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

   237             break;

   238         case 8:

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

   240             break;

   241         default:

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

   243         }

   244     }

   245 

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

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

   248             float ai = a[i];

   249             int j = i - 1;

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

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

   252             }

   253             a[j+1] = ai;

   254         }

   255     }

   256 

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

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

   259     // QuadCurve2D don't provide them.

   260     /**

   261      * Subdivides the cubic curve specified by the coordinates

   262      * stored in the <code>src</code> array at indices <code>srcoff</code>

   263      * through (<code>srcoff</code>&nbsp;+&nbsp;7) and stores the

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

   265      * corresponding indices.

   266      * Either or both of the <code>left</code> and <code>right</code>

   267      * arrays may be <code>null</code> or a reference to the same array

   268      * as the <code>src</code> array.

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

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

   271      * it is possible to pass the same array for <code>left</code>

   272      * and <code>right</code> and to use offsets, such as <code>rightoff</code>

   273      * equals (<code>leftoff</code> + 6), in order

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

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

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

   277      * the 6 source coordinates

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

   279      * half of the subdivided curve

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

   281      * the 6 left coordinates

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

   283      * half of the subdivided curve

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

   285      * the 6 right coordinates

   286      * @since 1.7

   287      */

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

   289                                float left[], int leftoff,

   290                                float right[], int rightoff)

   291     {

   292         float x1 = src[srcoff + 0];

   293         float y1 = src[srcoff + 1];

   294         float ctrlx1 = src[srcoff + 2];

   295         float ctrly1 = src[srcoff + 3];

   296         float ctrlx2 = src[srcoff + 4];

   297         float ctrly2 = src[srcoff + 5];

   298         float x2 = src[srcoff + 6];

   299         float y2 = src[srcoff + 7];

   300         if (left != null) {

   301             left[leftoff + 0] = x1;

   302             left[leftoff + 1] = y1;

   303         }

   304         if (right != null) {

   305             right[rightoff + 6] = x2;

   306             right[rightoff + 7] = y2;

   307         }

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

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

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

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

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

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

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

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

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

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

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

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

   320         if (left != null) {

   321             left[leftoff + 2] = x1;

   322             left[leftoff + 3] = y1;

   323             left[leftoff + 4] = ctrlx1;

   324             left[leftoff + 5] = ctrly1;

   325             left[leftoff + 6] = centerx;

   326             left[leftoff + 7] = centery;

   327         }

   328         if (right != null) {

   329             right[rightoff + 0] = centerx;

   330             right[rightoff + 1] = centery;

   331             right[rightoff + 2] = ctrlx2;

   332             right[rightoff + 3] = ctrly2;

   333             right[rightoff + 4] = x2;

   334             right[rightoff + 5] = y2;

   335         }

   336     }

   337 

   338 

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

   340                                  float left[], int leftoff,

   341                                  float right[], int rightoff)

   342     {

   343         float x1 = src[srcoff + 0];

   344         float y1 = src[srcoff + 1];

   345         float ctrlx1 = src[srcoff + 2];

   346         float ctrly1 = src[srcoff + 3];

   347         float ctrlx2 = src[srcoff + 4];

   348         float ctrly2 = src[srcoff + 5];

   349         float x2 = src[srcoff + 6];

   350         float y2 = src[srcoff + 7];

   351         if (left != null) {

   352             left[leftoff + 0] = x1;

   353             left[leftoff + 1] = y1;

   354         }

   355         if (right != null) {

   356             right[rightoff + 6] = x2;

   357             right[rightoff + 7] = y2;

   358         }

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

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

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

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

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

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

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

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

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

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

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

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

   371         if (left != null) {

   372             left[leftoff + 2] = x1;

   373             left[leftoff + 3] = y1;

   374             left[leftoff + 4] = ctrlx1;

   375             left[leftoff + 5] = ctrly1;

   376             left[leftoff + 6] = centerx;

   377             left[leftoff + 7] = centery;

   378         }

   379         if (right != null) {

   380             right[rightoff + 0] = centerx;

   381             right[rightoff + 1] = centery;

   382             right[rightoff + 2] = ctrlx2;

   383             right[rightoff + 3] = ctrly2;

   384             right[rightoff + 4] = x2;

   385             right[rightoff + 5] = y2;

   386         }

   387     }

   388 

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

   390                               float left[], int leftoff,

   391                               float right[], int rightoff)

   392     {

   393         float x1 = src[srcoff + 0];

   394         float y1 = src[srcoff + 1];

   395         float ctrlx = src[srcoff + 2];

   396         float ctrly = src[srcoff + 3];

   397         float x2 = src[srcoff + 4];

   398         float y2 = src[srcoff + 5];

   399         if (left != null) {

   400             left[leftoff + 0] = x1;

   401             left[leftoff + 1] = y1;

   402         }

   403         if (right != null) {

   404             right[rightoff + 4] = x2;

   405             right[rightoff + 5] = y2;

   406         }

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

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

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

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

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

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

   413         if (left != null) {

   414             left[leftoff + 2] = x1;

   415             left[leftoff + 3] = y1;

   416             left[leftoff + 4] = ctrlx;

   417             left[leftoff + 5] = ctrly;

   418         }

   419         if (right != null) {

   420             right[rightoff + 0] = ctrlx;

   421             right[rightoff + 1] = ctrly;

   422             right[rightoff + 2] = x2;

   423             right[rightoff + 3] = y2;

   424         }

   425     }

   426 

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

   428                                 float left[], int leftoff,

   429                                 float right[], int rightoff)

   430     {

   431         float x1 = src[srcoff + 0];

   432         float y1 = src[srcoff + 1];

   433         float ctrlx = src[srcoff + 2];

   434         float ctrly = src[srcoff + 3];

   435         float x2 = src[srcoff + 4];

   436         float y2 = src[srcoff + 5];

   437         if (left != null) {

   438             left[leftoff + 0] = x1;

   439             left[leftoff + 1] = y1;

   440         }

   441         if (right != null) {

   442             right[rightoff + 4] = x2;

   443             right[rightoff + 5] = y2;

   444         }

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

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

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

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

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

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

   451         if (left != null) {

   452             left[leftoff + 2] = x1;

   453             left[leftoff + 3] = y1;

   454             left[leftoff + 4] = ctrlx;

   455             left[leftoff + 5] = ctrly;

   456         }

   457         if (right != null) {

   458             right[rightoff + 0] = ctrlx;

   459             right[rightoff + 1] = ctrly;

   460             right[rightoff + 2] = x2;

   461             right[rightoff + 3] = y2;

   462         }

   463     }

   464 

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

   466                             float left[], int leftoff,

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

   468     {

   469         switch(size) {

   470         case 8:

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

   472             break;

   473         case 6:

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

   475             break;

   476         }

   477     }

   478 }