J. Duke | 319a3b9 | 2007-12-01 00:00:00 +0000 | [diff] [blame^] | 1 | /* |
| 2 | * Copyright 1998-2006 Sun Microsystems, Inc. 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. Sun designates this |
| 8 | * particular file as subject to the "Classpath" exception as provided |
| 9 | * by Sun 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 Sun Microsystems, Inc., 4150 Network Circle, Santa Clara, |
| 22 | * CA 95054 USA or visit www.sun.com if you need additional information or |
| 23 | * have any questions. |
| 24 | */ |
| 25 | |
| 26 | package sun.awt.geom; |
| 27 | |
| 28 | import java.awt.geom.Rectangle2D; |
| 29 | import java.awt.geom.PathIterator; |
| 30 | import java.awt.geom.QuadCurve2D; |
| 31 | import java.util.Vector; |
| 32 | |
| 33 | final class Order2 extends Curve { |
| 34 | private double x0; |
| 35 | private double y0; |
| 36 | private double cx0; |
| 37 | private double cy0; |
| 38 | private double x1; |
| 39 | private double y1; |
| 40 | private double xmin; |
| 41 | private double xmax; |
| 42 | |
| 43 | private double xcoeff0; |
| 44 | private double xcoeff1; |
| 45 | private double xcoeff2; |
| 46 | private double ycoeff0; |
| 47 | private double ycoeff1; |
| 48 | private double ycoeff2; |
| 49 | |
| 50 | public static void insert(Vector curves, double tmp[], |
| 51 | double x0, double y0, |
| 52 | double cx0, double cy0, |
| 53 | double x1, double y1, |
| 54 | int direction) |
| 55 | { |
| 56 | int numparams = getHorizontalParams(y0, cy0, y1, tmp); |
| 57 | if (numparams == 0) { |
| 58 | // We are using addInstance here to avoid inserting horisontal |
| 59 | // segments |
| 60 | addInstance(curves, x0, y0, cx0, cy0, x1, y1, direction); |
| 61 | return; |
| 62 | } |
| 63 | // assert(numparams == 1); |
| 64 | double t = tmp[0]; |
| 65 | tmp[0] = x0; tmp[1] = y0; |
| 66 | tmp[2] = cx0; tmp[3] = cy0; |
| 67 | tmp[4] = x1; tmp[5] = y1; |
| 68 | split(tmp, 0, t); |
| 69 | int i0 = (direction == INCREASING)? 0 : 4; |
| 70 | int i1 = 4 - i0; |
| 71 | addInstance(curves, tmp[i0], tmp[i0 + 1], tmp[i0 + 2], tmp[i0 + 3], |
| 72 | tmp[i0 + 4], tmp[i0 + 5], direction); |
| 73 | addInstance(curves, tmp[i1], tmp[i1 + 1], tmp[i1 + 2], tmp[i1 + 3], |
| 74 | tmp[i1 + 4], tmp[i1 + 5], direction); |
| 75 | } |
| 76 | |
| 77 | public static void addInstance(Vector curves, |
| 78 | double x0, double y0, |
| 79 | double cx0, double cy0, |
| 80 | double x1, double y1, |
| 81 | int direction) { |
| 82 | if (y0 > y1) { |
| 83 | curves.add(new Order2(x1, y1, cx0, cy0, x0, y0, -direction)); |
| 84 | } else if (y1 > y0) { |
| 85 | curves.add(new Order2(x0, y0, cx0, cy0, x1, y1, direction)); |
| 86 | } |
| 87 | } |
| 88 | |
| 89 | /* |
| 90 | * Return the count of the number of horizontal sections of the |
| 91 | * specified quadratic Bezier curve. Put the parameters for the |
| 92 | * horizontal sections into the specified <code>ret</code> array. |
| 93 | * <p> |
| 94 | * If we examine the parametric equation in t, we have: |
| 95 | * Py(t) = C0*(1-t)^2 + 2*CP*t*(1-t) + C1*t^2 |
| 96 | * = C0 - 2*C0*t + C0*t^2 + 2*CP*t - 2*CP*t^2 + C1*t^2 |
| 97 | * = C0 + (2*CP - 2*C0)*t + (C0 - 2*CP + C1)*t^2 |
| 98 | * Py(t) = (C0 - 2*CP + C1)*t^2 + (2*CP - 2*C0)*t + (C0) |
| 99 | * If we take the derivative, we get: |
| 100 | * Py(t) = At^2 + Bt + C |
| 101 | * dPy(t) = 2At + B = 0 |
| 102 | * 2*(C0 - 2*CP + C1)t + 2*(CP - C0) = 0 |
| 103 | * 2*(C0 - 2*CP + C1)t = 2*(C0 - CP) |
| 104 | * t = 2*(C0 - CP) / 2*(C0 - 2*CP + C1) |
| 105 | * t = (C0 - CP) / (C0 - CP + C1 - CP) |
| 106 | * Note that this method will return 0 if the equation is a line, |
| 107 | * which is either always horizontal or never horizontal. |
| 108 | * Completely horizontal curves need to be eliminated by other |
| 109 | * means outside of this method. |
| 110 | */ |
| 111 | public static int getHorizontalParams(double c0, double cp, double c1, |
| 112 | double ret[]) { |
| 113 | if (c0 <= cp && cp <= c1) { |
| 114 | return 0; |
| 115 | } |
| 116 | c0 -= cp; |
| 117 | c1 -= cp; |
| 118 | double denom = c0 + c1; |
| 119 | // If denom == 0 then cp == (c0+c1)/2 and we have a line. |
| 120 | if (denom == 0) { |
| 121 | return 0; |
| 122 | } |
| 123 | double t = c0 / denom; |
| 124 | // No splits at t==0 and t==1 |
| 125 | if (t <= 0 || t >= 1) { |
| 126 | return 0; |
| 127 | } |
| 128 | ret[0] = t; |
| 129 | return 1; |
| 130 | } |
| 131 | |
| 132 | /* |
| 133 | * Split the quadratic Bezier stored at coords[pos...pos+5] representing |
| 134 | * the paramtric range [0..1] into two subcurves representing the |
| 135 | * parametric subranges [0..t] and [t..1]. Store the results back |
| 136 | * into the array at coords[pos...pos+5] and coords[pos+4...pos+9]. |
| 137 | */ |
| 138 | public static void split(double coords[], int pos, double t) { |
| 139 | double x0, y0, cx, cy, x1, y1; |
| 140 | coords[pos+8] = x1 = coords[pos+4]; |
| 141 | coords[pos+9] = y1 = coords[pos+5]; |
| 142 | cx = coords[pos+2]; |
| 143 | cy = coords[pos+3]; |
| 144 | x1 = cx + (x1 - cx) * t; |
| 145 | y1 = cy + (y1 - cy) * t; |
| 146 | x0 = coords[pos+0]; |
| 147 | y0 = coords[pos+1]; |
| 148 | x0 = x0 + (cx - x0) * t; |
| 149 | y0 = y0 + (cy - y0) * t; |
| 150 | cx = x0 + (x1 - x0) * t; |
| 151 | cy = y0 + (y1 - y0) * t; |
| 152 | coords[pos+2] = x0; |
| 153 | coords[pos+3] = y0; |
| 154 | coords[pos+4] = cx; |
| 155 | coords[pos+5] = cy; |
| 156 | coords[pos+6] = x1; |
| 157 | coords[pos+7] = y1; |
| 158 | } |
| 159 | |
| 160 | public Order2(double x0, double y0, |
| 161 | double cx0, double cy0, |
| 162 | double x1, double y1, |
| 163 | int direction) |
| 164 | { |
| 165 | super(direction); |
| 166 | // REMIND: Better accuracy in the root finding methods would |
| 167 | // ensure that cy0 is in range. As it stands, it is never |
| 168 | // more than "1 mantissa bit" out of range... |
| 169 | if (cy0 < y0) { |
| 170 | cy0 = y0; |
| 171 | } else if (cy0 > y1) { |
| 172 | cy0 = y1; |
| 173 | } |
| 174 | this.x0 = x0; |
| 175 | this.y0 = y0; |
| 176 | this.cx0 = cx0; |
| 177 | this.cy0 = cy0; |
| 178 | this.x1 = x1; |
| 179 | this.y1 = y1; |
| 180 | xmin = Math.min(Math.min(x0, x1), cx0); |
| 181 | xmax = Math.max(Math.max(x0, x1), cx0); |
| 182 | xcoeff0 = x0; |
| 183 | xcoeff1 = cx0 + cx0 - x0 - x0; |
| 184 | xcoeff2 = x0 - cx0 - cx0 + x1; |
| 185 | ycoeff0 = y0; |
| 186 | ycoeff1 = cy0 + cy0 - y0 - y0; |
| 187 | ycoeff2 = y0 - cy0 - cy0 + y1; |
| 188 | } |
| 189 | |
| 190 | public int getOrder() { |
| 191 | return 2; |
| 192 | } |
| 193 | |
| 194 | public double getXTop() { |
| 195 | return x0; |
| 196 | } |
| 197 | |
| 198 | public double getYTop() { |
| 199 | return y0; |
| 200 | } |
| 201 | |
| 202 | public double getXBot() { |
| 203 | return x1; |
| 204 | } |
| 205 | |
| 206 | public double getYBot() { |
| 207 | return y1; |
| 208 | } |
| 209 | |
| 210 | public double getXMin() { |
| 211 | return xmin; |
| 212 | } |
| 213 | |
| 214 | public double getXMax() { |
| 215 | return xmax; |
| 216 | } |
| 217 | |
| 218 | public double getX0() { |
| 219 | return (direction == INCREASING) ? x0 : x1; |
| 220 | } |
| 221 | |
| 222 | public double getY0() { |
| 223 | return (direction == INCREASING) ? y0 : y1; |
| 224 | } |
| 225 | |
| 226 | public double getCX0() { |
| 227 | return cx0; |
| 228 | } |
| 229 | |
| 230 | public double getCY0() { |
| 231 | return cy0; |
| 232 | } |
| 233 | |
| 234 | public double getX1() { |
| 235 | return (direction == DECREASING) ? x0 : x1; |
| 236 | } |
| 237 | |
| 238 | public double getY1() { |
| 239 | return (direction == DECREASING) ? y0 : y1; |
| 240 | } |
| 241 | |
| 242 | public double XforY(double y) { |
| 243 | if (y <= y0) { |
| 244 | return x0; |
| 245 | } |
| 246 | if (y >= y1) { |
| 247 | return x1; |
| 248 | } |
| 249 | return XforT(TforY(y)); |
| 250 | } |
| 251 | |
| 252 | public double TforY(double y) { |
| 253 | if (y <= y0) { |
| 254 | return 0; |
| 255 | } |
| 256 | if (y >= y1) { |
| 257 | return 1; |
| 258 | } |
| 259 | return TforY(y, ycoeff0, ycoeff1, ycoeff2); |
| 260 | } |
| 261 | |
| 262 | public static double TforY(double y, |
| 263 | double ycoeff0, double ycoeff1, double ycoeff2) |
| 264 | { |
| 265 | // The caller should have already eliminated y values |
| 266 | // outside of the y0 to y1 range. |
| 267 | ycoeff0 -= y; |
| 268 | if (ycoeff2 == 0.0) { |
| 269 | // The quadratic parabola has degenerated to a line. |
| 270 | // ycoeff1 should not be 0.0 since we have already eliminated |
| 271 | // totally horizontal lines, but if it is, then we will generate |
| 272 | // infinity here for the root, which will not be in the [0,1] |
| 273 | // range so we will pass to the failure code below. |
| 274 | double root = -ycoeff0 / ycoeff1; |
| 275 | if (root >= 0 && root <= 1) { |
| 276 | return root; |
| 277 | } |
| 278 | } else { |
| 279 | // From Numerical Recipes, 5.6, Quadratic and Cubic Equations |
| 280 | double d = ycoeff1 * ycoeff1 - 4.0 * ycoeff2 * ycoeff0; |
| 281 | // If d < 0.0, then there are no roots |
| 282 | if (d >= 0.0) { |
| 283 | d = Math.sqrt(d); |
| 284 | // For accuracy, calculate one root using: |
| 285 | // (-ycoeff1 +/- d) / 2ycoeff2 |
| 286 | // and the other using: |
| 287 | // 2ycoeff0 / (-ycoeff1 +/- d) |
| 288 | // Choose the sign of the +/- so that ycoeff1+d |
| 289 | // gets larger in magnitude |
| 290 | if (ycoeff1 < 0.0) { |
| 291 | d = -d; |
| 292 | } |
| 293 | double q = (ycoeff1 + d) / -2.0; |
| 294 | // We already tested ycoeff2 for being 0 above |
| 295 | double root = q / ycoeff2; |
| 296 | if (root >= 0 && root <= 1) { |
| 297 | return root; |
| 298 | } |
| 299 | if (q != 0.0) { |
| 300 | root = ycoeff0 / q; |
| 301 | if (root >= 0 && root <= 1) { |
| 302 | return root; |
| 303 | } |
| 304 | } |
| 305 | } |
| 306 | } |
| 307 | /* We failed to find a root in [0,1]. What could have gone wrong? |
| 308 | * First, remember that these curves are constructed to be monotonic |
| 309 | * in Y and totally horizontal curves have already been eliminated. |
| 310 | * Now keep in mind that the Y coefficients of the polynomial form |
| 311 | * of the curve are calculated from the Y coordinates which define |
| 312 | * our curve. They should theoretically define the same curve, |
| 313 | * but they can be off by a couple of bits of precision after the |
| 314 | * math is done and so can represent a slightly modified curve. |
| 315 | * This is normally not an issue except when we have solutions near |
| 316 | * the endpoints. Since the answers we get from solving the polynomial |
| 317 | * may be off by a few bits that means that they could lie just a |
| 318 | * few bits of precision outside the [0,1] range. |
| 319 | * |
| 320 | * Another problem could be that while the parametric curve defined |
| 321 | * by the Y coordinates has a local minima or maxima at or just |
| 322 | * outside of the endpoints, the polynomial form might express |
| 323 | * that same min/max just inside of and just shy of the Y coordinate |
| 324 | * of that endpoint. In that case, if we solve for a Y coordinate |
| 325 | * at or near that endpoint, we may be solving for a Y coordinate |
| 326 | * that is below that minima or above that maxima and we would find |
| 327 | * no solutions at all. |
| 328 | * |
| 329 | * In either case, we can assume that y is so near one of the |
| 330 | * endpoints that we can just collapse it onto the nearest endpoint |
| 331 | * without losing more than a couple of bits of precision. |
| 332 | */ |
| 333 | // First calculate the midpoint between y0 and y1 and choose to |
| 334 | // return either 0.0 or 1.0 depending on whether y is above |
| 335 | // or below the midpoint... |
| 336 | // Note that we subtracted y from ycoeff0 above so both y0 and y1 |
| 337 | // will be "relative to y" so we are really just looking at where |
| 338 | // zero falls with respect to the "relative midpoint" here. |
| 339 | double y0 = ycoeff0; |
| 340 | double y1 = ycoeff0 + ycoeff1 + ycoeff2; |
| 341 | return (0 < (y0 + y1) / 2) ? 0.0 : 1.0; |
| 342 | } |
| 343 | |
| 344 | public double XforT(double t) { |
| 345 | return (xcoeff2 * t + xcoeff1) * t + xcoeff0; |
| 346 | } |
| 347 | |
| 348 | public double YforT(double t) { |
| 349 | return (ycoeff2 * t + ycoeff1) * t + ycoeff0; |
| 350 | } |
| 351 | |
| 352 | public double dXforT(double t, int deriv) { |
| 353 | switch (deriv) { |
| 354 | case 0: |
| 355 | return (xcoeff2 * t + xcoeff1) * t + xcoeff0; |
| 356 | case 1: |
| 357 | return 2 * xcoeff2 * t + xcoeff1; |
| 358 | case 2: |
| 359 | return 2 * xcoeff2; |
| 360 | default: |
| 361 | return 0; |
| 362 | } |
| 363 | } |
| 364 | |
| 365 | public double dYforT(double t, int deriv) { |
| 366 | switch (deriv) { |
| 367 | case 0: |
| 368 | return (ycoeff2 * t + ycoeff1) * t + ycoeff0; |
| 369 | case 1: |
| 370 | return 2 * ycoeff2 * t + ycoeff1; |
| 371 | case 2: |
| 372 | return 2 * ycoeff2; |
| 373 | default: |
| 374 | return 0; |
| 375 | } |
| 376 | } |
| 377 | |
| 378 | public double nextVertical(double t0, double t1) { |
| 379 | double t = -xcoeff1 / (2 * xcoeff2); |
| 380 | if (t > t0 && t < t1) { |
| 381 | return t; |
| 382 | } |
| 383 | return t1; |
| 384 | } |
| 385 | |
| 386 | public void enlarge(Rectangle2D r) { |
| 387 | r.add(x0, y0); |
| 388 | double t = -xcoeff1 / (2 * xcoeff2); |
| 389 | if (t > 0 && t < 1) { |
| 390 | r.add(XforT(t), YforT(t)); |
| 391 | } |
| 392 | r.add(x1, y1); |
| 393 | } |
| 394 | |
| 395 | public Curve getSubCurve(double ystart, double yend, int dir) { |
| 396 | double t0, t1; |
| 397 | if (ystart <= y0) { |
| 398 | if (yend >= y1) { |
| 399 | return getWithDirection(dir); |
| 400 | } |
| 401 | t0 = 0; |
| 402 | } else { |
| 403 | t0 = TforY(ystart, ycoeff0, ycoeff1, ycoeff2); |
| 404 | } |
| 405 | if (yend >= y1) { |
| 406 | t1 = 1; |
| 407 | } else { |
| 408 | t1 = TforY(yend, ycoeff0, ycoeff1, ycoeff2); |
| 409 | } |
| 410 | double eqn[] = new double[10]; |
| 411 | eqn[0] = x0; |
| 412 | eqn[1] = y0; |
| 413 | eqn[2] = cx0; |
| 414 | eqn[3] = cy0; |
| 415 | eqn[4] = x1; |
| 416 | eqn[5] = y1; |
| 417 | if (t1 < 1) { |
| 418 | split(eqn, 0, t1); |
| 419 | } |
| 420 | int i; |
| 421 | if (t0 <= 0) { |
| 422 | i = 0; |
| 423 | } else { |
| 424 | split(eqn, 0, t0 / t1); |
| 425 | i = 4; |
| 426 | } |
| 427 | return new Order2(eqn[i+0], ystart, |
| 428 | eqn[i+2], eqn[i+3], |
| 429 | eqn[i+4], yend, |
| 430 | dir); |
| 431 | } |
| 432 | |
| 433 | public Curve getReversedCurve() { |
| 434 | return new Order2(x0, y0, cx0, cy0, x1, y1, -direction); |
| 435 | } |
| 436 | |
| 437 | public int getSegment(double coords[]) { |
| 438 | coords[0] = cx0; |
| 439 | coords[1] = cy0; |
| 440 | if (direction == INCREASING) { |
| 441 | coords[2] = x1; |
| 442 | coords[3] = y1; |
| 443 | } else { |
| 444 | coords[2] = x0; |
| 445 | coords[3] = y0; |
| 446 | } |
| 447 | return PathIterator.SEG_QUADTO; |
| 448 | } |
| 449 | |
| 450 | public String controlPointString() { |
| 451 | return ("("+round(cx0)+", "+round(cy0)+"), "); |
| 452 | } |
| 453 | } |