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.Iterator;

    29 

    30 class Curve {

    31 

    32     float ax, ay, bx, by, cx, cy, dx, dy;

    33     float dax, day, dbx, dby;

    34 

    35     Curve() {

    36     }

    37 

    38     void set(float[] points, int type) {

    39         switch(type) {

    40         case 8:

    41             set(points[0], points[1],

    42                 points[2], points[3],

    43                 points[4], points[5],

    44                 points[6], points[7]);

    45             break;

    46         case 6:

    47             set(points[0], points[1],

    48                 points[2], points[3],

    49                 points[4], points[5]);

    50             break;

    51         default:

    52             throw new InternalError("Curves can only be cubic or quadratic");

    53         }

    54     }

    55 

    56     void set(float x1, float y1,

    57              float x2, float y2,

    58              float x3, float y3,

    59              float x4, float y4)

    60     {

    61         ax = 3 * (x2 - x3) + x4 - x1;

    62         ay = 3 * (y2 - y3) + y4 - y1;

    63         bx = 3 * (x1 - 2 * x2 + x3);

    64         by = 3 * (y1 - 2 * y2 + y3);

    65         cx = 3 * (x2 - x1);

    66         cy = 3 * (y2 - y1);

    67         dx = x1;

    68         dy = y1;

    69         dax = 3 * ax; day = 3 * ay;

    70         dbx = 2 * bx; dby = 2 * by;

    71     }

    72 

    73     void set(float x1, float y1,

    74              float x2, float y2,

    75              float x3, float y3)

    76     {

    77         ax = ay = 0f;

    78 

    79         bx = x1 - 2 * x2 + x3;

    80         by = y1 - 2 * y2 + y3;

    81         cx = 2 * (x2 - x1);

    82         cy = 2 * (y2 - y1);

    83         dx = x1;

    84         dy = y1;

    85         dax = 0; day = 0;

    86         dbx = 2 * bx; dby = 2 * by;

    87     }

    88 

    89     float xat(float t) {

    90         return t * (t * (t * ax + bx) + cx) + dx;

    91     }

    92     float yat(float t) {

    93         return t * (t * (t * ay + by) + cy) + dy;

    94     }

    95 

    96     float dxat(float t) {

    97         return t * (t * dax + dbx) + cx;

    98     }

    99 

   100     float dyat(float t) {

   101         return t * (t * day + dby) + cy;

   102     }

   103 

   104     private float ddxat(float t) {

   105         return 2 * dax * t + dbx;

   106     }

   107 

   108     private float ddyat(float t) {

   109         return 2 * day * t + dby;

   110     }

   111 

   112     int dxRoots(float[] roots, int off) {

   113         return Helpers.quadraticRoots(dax, dbx, cx, roots, off);

   114     }

   115 

   116     int dyRoots(float[] roots, int off) {

   117         return Helpers.quadraticRoots(day, dby, cy, roots, off);

   118     }

   119 

   120     int infPoints(float[] pts, int off) {

   121         // inflection point at t if -f'(t)x*f''(t)y + f'(t)y*f''(t)x == 0

   122         // Fortunately, this turns out to be quadratic, so there are at

   123         // most 2 inflection points.

   124         final float a = dax * dby - dbx * day;

   125         final float b = 2 * (cy * dax - day * cx);

   126         final float c = cy * dbx - cx * dby;

   127 

   128         return Helpers.quadraticRoots(a, b, c, pts, off);

   129     }

   130 

   131     // finds points where the first and second derivative are

   132     // perpendicular. This happens when g(t) = f'(t)*f''(t) == 0 (where

   133     // * is a dot product). Unfortunately, we have to solve a cubic.

   134     private int perpendiculardfddf(float[] pts, int off, final float err) {

   135         assert pts.length >= off + 4;

   136 

   137         // these are the coefficients of g(t):

   138         final float a = 2*(dax*dax + day*day);

   139         final float b = 3*(dax*dbx + day*dby);

   140         final float c = 2*(dax*cx + day*cy) + dbx*dbx + dby*dby;

   141         final float d = dbx*cx + dby*cy;

   142         // TODO: We might want to divide the polynomial by a to make the

   143         // coefficients smaller. This won't change the roots.

   144         return Helpers.cubicRootsInAB(a, b, c, d, pts, off, err, 0f, 1f);

   145     }

   146 

   147     // Tries to find the roots of the function ROC(t)-w in [0, 1). It uses

   148     // a variant of the false position algorithm to find the roots. False

   149     // position requires that 2 initial values x0,x1 be given, and that the

   150     // function must have opposite signs at those values. To find such

   151     // values, we need the local extrema of the ROC function, for which we

   152     // need the roots of its derivative; however, it's harder to find the

   153     // roots of the derivative in this case than it is to find the roots

   154     // of the original function. So, we find all points where this curve's

   155     // first and second derivative are perpendicular, and we pretend these

   156     // are our local extrema. There are at most 3 of these, so we will check

   157     // at most 4 sub-intervals of (0,1). ROC has asymptotes at inflection

   158     // points, so roc-w can have at least 6 roots. This shouldn't be a

   159     // problem for what we're trying to do (draw a nice looking curve).

   160     int rootsOfROCMinusW(float[] roots, int off, final float w, final float err) {

   161         // no OOB exception, because by now off<=6, and roots.length >= 10

   162         assert off <= 6 && roots.length >= 10;

   163         int ret = off;

   164         int numPerpdfddf = perpendiculardfddf(roots, off, err);

   165         float t0 = 0, ft0 = ROCsq(t0) - w*w;

   166         roots[off + numPerpdfddf] = 1f; // always check interval end points

   167         numPerpdfddf++;

   168         for (int i = off; i < off + numPerpdfddf; i++) {

   169             float t1 = roots[i], ft1 = ROCsq(t1) - w*w;

   170             if (ft0 == 0f) {

   171                 roots[ret++] = t0;

   172             } else if (ft1 * ft0 < 0f) { // have opposite signs

   173                 // (ROC(t)^2 == w^2) == (ROC(t) == w) is true because

   174                 // ROC(t) >= 0 for all t.

   175                 roots[ret++] = falsePositionROCsqMinusX(t0, t1, w*w, err);

   176             }

   177             t0 = t1;

   178             ft0 = ft1;

   179         }

   180 

   181         return ret - off;

   182     }

   183 

   184     private static float eliminateInf(float x) {

   185         return (x == Float.POSITIVE_INFINITY ? Float.MAX_VALUE :

   186             (x == Float.NEGATIVE_INFINITY ? Float.MIN_VALUE : x));

   187     }

   188 

   189     // A slight modification of the false position algorithm on wikipedia.

   190     // This only works for the ROCsq-x functions. It might be nice to have

   191     // the function as an argument, but that would be awkward in java6.

   192     // It is something to consider for java7, depending on how closures

   193     // and function objects turn out. Same goes for the newton's method

   194     // algorithm in Helpers.java

   195     private float falsePositionROCsqMinusX(float x0, float x1,

   196                                            final float x, final float err)

   197     {

   198         final int iterLimit = 100;

   199         int side = 0;

   200         float t = x1, ft = eliminateInf(ROCsq(t) - x);

   201         float s = x0, fs = eliminateInf(ROCsq(s) - x);

   202         float r = s, fr;

   203         for (int i = 0; i < iterLimit && Math.abs(t - s) > err * Math.abs(t + s); i++) {

   204             r = (fs * t - ft * s) / (fs - ft);

   205             fr = ROCsq(r) - x;

   206             if (fr * ft > 0) {// have the same sign

   207                 ft = fr; t = r;

   208                 if (side < 0) {

   209                     fs /= (1 << (-side));

   210                     side--;

   211                 } else {

   212                     side = -1;

   213                 }

   214             } else if (fr * fs > 0) {

   215                 fs = fr; s = r;

   216                 if (side > 0) {

   217                     ft /= (1 << side);

   218                     side++;

   219                 } else {

   220                     side = 1;

   221                 }

   222             } else {

   223                 break;

   224             }

   225         }

   226         return r;

   227     }

   228 

   229     // returns the radius of curvature squared at t of this curve

   230     // see http://en.wikipedia.org/wiki/Radius_of_curvature_(applications)

   231     private float ROCsq(final float t) {

   232         final float dx = dxat(t);

   233         final float dy = dyat(t);

   234         final float ddx = ddxat(t);

   235         final float ddy = ddyat(t);

   236         final float dx2dy2 = dx*dx + dy*dy;

   237         final float ddx2ddy2 = ddx*ddx + ddy*ddy;

   238         final float ddxdxddydy = ddx*dx + ddy*dy;

   239         float ret = ((dx2dy2*dx2dy2) / (dx2dy2 * ddx2ddy2 - ddxdxddydy*ddxdxddydy))*dx2dy2;

   240         return ret;

   241     }

   242 

   243     // curve to be broken should be in pts[0]

   244     // this will change the contents of both pts and Ts

   245     // TODO: There's no reason for Ts to be an array. All we need is a sequence

   246     // of t values at which to subdivide. An array statisfies this condition,

   247     // but is unnecessarily restrictive. Ts should be an Iterator<Float> instead.

   248     // Doing this will also make dashing easier, since we could easily make

   249     // LengthIterator an Iterator<Float> and feed it to this function to simplify

   250     // the loop in Dasher.somethingTo.

   251     static Iterator<float[]> breakPtsAtTs(final float[][] pts, final int type,

   252                                           final float[] Ts, final int numTs)

   253     {

   254         assert pts.length >= 2 && pts[0].length >= 8 && numTs <= Ts.length;

   255         return new Iterator<float[]>() {

   256             int nextIdx = 0;

   257             int nextCurveIdx = 0;

   258             float prevT = 0;

   259 

   260             @Override public boolean hasNext() {

   261                 return nextCurveIdx < numTs + 1;

   262             }

   263 

   264             @Override public float[] next() {

   265                 float[] ret;

   266                 if (nextCurveIdx < numTs) {

   267                     float curT = Ts[nextCurveIdx];

   268                     float splitT = (curT - prevT) / (1 - prevT);

   269                     Helpers.subdivideAt(splitT,

   270                                         pts[nextIdx], 0,

   271                                         pts[nextIdx], 0,

   272                                         pts[1-nextIdx], 0, type);

   273                     updateTs(Ts, Ts[nextCurveIdx], nextCurveIdx + 1, numTs - nextCurveIdx - 1);

   274                     ret = pts[nextIdx];

   275                     nextIdx = 1 - nextIdx;

   276                 } else {

   277                     ret = pts[nextIdx];

   278                 }

   279                 nextCurveIdx++;

   280                 return ret;

   281             }

   282 

   283             @Override public void remove() {}

   284         };

   285     }

   286 

   287     // precondition: ts[off]...ts[off+len-1] must all be greater than t.

   288     private static void updateTs(float[] ts, final float t, final int off, final int len) {

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

   290             ts[i] = (ts[i] - t) / (1 - t);

   291         }

   292     }

   293 }

   294