/hg/icedtea6: CubicCurve2D backports: S4493128, S4645692, S4724552.
dlila at icedtea.classpath.org
dlila at icedtea.classpath.org
Tue Feb 1 11:28:50 PST 2011
changeset eee57a146340 in /hg/icedtea6
details: http://icedtea.classpath.org/hg/icedtea6?cmd=changeset;node=eee57a146340
author: dlila
date: Tue Feb 01 14:21:02 2011 -0500
CubicCurve2D backports: S4493128, S4645692, S4724552.
diffstat:
6 files changed, 993 insertions(+), 1 deletion(-)
ChangeLog | 8
Makefile.am | 5
NEWS | 3
patches/openjdk/4493128-CubicCurve2D.patch | 213 +++++
patches/openjdk/4645692-CubicCurve2D.solveCubic.patch | 717 +++++++++++++++++
patches/openjdk/4724552-CubicCurve2D.patch | 48 +
diffs (truncated from 1033 to 500 lines):
diff -r 82d83ff8b150 -r eee57a146340 ChangeLog
--- a/ChangeLog Tue Feb 01 18:22:19 2011 +0000
+++ b/ChangeLog Tue Feb 01 14:21:02 2011 -0500
@@ -1,3 +1,11 @@ 2011-02-01 Andrew John Hughes <ahughes
+2011-02-01 Denis Lila <dlila at redhat.com>
+
+ * NEWS: Update with the 3 backports
+ * Makefile.am (ICEDTEA_PATCHES): Add the patches
+ * patches/openjdk/4493128-CubicCurve2D.patch: New file.
+ * patches/openjdk/4645692-CubicCurve2D.solveCubic.patch: Likewise.
+ * patches/openjdk/4724552-CubicCurve2D.patch: Likewise.
+
2011-02-01 Andrew John Hughes <ahughes at redhat.com>
* NEWS: Add announcements for 1.7.8,
diff -r 82d83ff8b150 -r eee57a146340 Makefile.am
--- a/Makefile.am Tue Feb 01 18:22:19 2011 +0000
+++ b/Makefile.am Tue Feb 01 14:21:02 2011 -0500
@@ -276,7 +276,10 @@ ICEDTEA_PATCHES = \
patches/openjdk/6736649-text_bearings.patch \
patches/openjdk/6797139-jbutton_truncation.patch \
patches/openjdk/6883341-text_bearing_exception.patch \
- patches/jtreg-png-reader.patch
+ patches/jtreg-png-reader.patch \
+ patches/openjdk/4724552-CubicCurve2D.patch \
+ patches/openjdk/4493128-CubicCurve2D.patch \
+ patches/openjdk/4645692-CubicCurve2D.solveCubic.patch
if !WITH_ALT_HSBUILD
ICEDTEA_PATCHES += \
diff -r 82d83ff8b150 -r eee57a146340 NEWS
--- a/NEWS Tue Feb 01 18:22:19 2011 +0000
+++ b/NEWS Tue Feb 01 14:21:02 2011 -0500
@@ -403,6 +403,9 @@ New in release 1.10 (2011-XX-XX):
- S6736649: test/closed/javax/swing/JMenuItem/6458123/ManualBug6458123.java fails on Linux
- S6797139: JButton title is truncating for some strings irrespective of preferred size.
- S6883341: SWAT: jdk7-b72 swat build(2009-09-17) threw exceptions when running Java2D demo by clicking Paint ta
+ - S4493128: CubicCurve2D intersects method fails
+ - S4724552: CubicCurve2D.contains(Rectangle2D) returns true when partially contained.
+ - S4645692: CubicCurve2D.solveCubic does not return all solutions.
* Bug fixes
- RH661505: JPEGs with sRGB IEC61966-2.1 color profiles have wrong colors
diff -r 82d83ff8b150 -r eee57a146340 patches/openjdk/4493128-CubicCurve2D.patch
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/patches/openjdk/4493128-CubicCurve2D.patch Tue Feb 01 14:21:02 2011 -0500
@@ -0,0 +1,213 @@
+--- openjdk/jdk/src/share/classes/java/awt/geom/CubicCurve2D.java.old 2011-01-31 12:38:24.340733697 -0500
++++ openjdk/jdk/src/share/classes/java/awt/geom/CubicCurve2D.java 2011-01-31 12:54:27.462601773 -0500
+@@ -1387,203 +1387,13 @@
+ return false;
+ }
+
+- // Trivially accept if either endpoint is inside the rectangle
+- // (not on its border since it may end there and not go inside)
+- // Record where they lie with respect to the rectangle.
+- // -1 => left, 0 => inside, 1 => right
+- double x1 = getX1();
+- double y1 = getY1();
+- int x1tag = getTag(x1, x, x+w);
+- int y1tag = getTag(y1, y, y+h);
+- if (x1tag == INSIDE && y1tag == INSIDE) {
+- return true;
+- }
+- double x2 = getX2();
+- double y2 = getY2();
+- int x2tag = getTag(x2, x, x+w);
+- int y2tag = getTag(y2, y, y+h);
+- if (x2tag == INSIDE && y2tag == INSIDE) {
+- return true;
+- }
+-
+- double ctrlx1 = getCtrlX1();
+- double ctrly1 = getCtrlY1();
+- double ctrlx2 = getCtrlX2();
+- double ctrly2 = getCtrlY2();
+- int ctrlx1tag = getTag(ctrlx1, x, x+w);
+- int ctrly1tag = getTag(ctrly1, y, y+h);
+- int ctrlx2tag = getTag(ctrlx2, x, x+w);
+- int ctrly2tag = getTag(ctrly2, y, y+h);
+-
+- // Trivially reject if all points are entirely to one side of
+- // the rectangle.
+- if (x1tag < INSIDE && x2tag < INSIDE &&
+- ctrlx1tag < INSIDE && ctrlx2tag < INSIDE)
+- {
+- return false; // All points left
+- }
+- if (y1tag < INSIDE && y2tag < INSIDE &&
+- ctrly1tag < INSIDE && ctrly2tag < INSIDE)
+- {
+- return false; // All points above
+- }
+- if (x1tag > INSIDE && x2tag > INSIDE &&
+- ctrlx1tag > INSIDE && ctrlx2tag > INSIDE)
+- {
+- return false; // All points right
+- }
+- if (y1tag > INSIDE && y2tag > INSIDE &&
+- ctrly1tag > INSIDE && ctrly2tag > INSIDE)
+- {
+- return false; // All points below
+- }
+-
+- // Test for endpoints on the edge where either the segment
+- // or the curve is headed "inwards" from them
+- // Note: These tests are a superset of the fast endpoint tests
+- // above and thus repeat those tests, but take more time
+- // and cover more cases
+- if (inwards(x1tag, x2tag, ctrlx1tag) &&
+- inwards(y1tag, y2tag, ctrly1tag))
+- {
+- // First endpoint on border with either edge moving inside
+- return true;
+- }
+- if (inwards(x2tag, x1tag, ctrlx2tag) &&
+- inwards(y2tag, y1tag, ctrly2tag))
+- {
+- // Second endpoint on border with either edge moving inside
+- return true;
+- }
+-
+- // Trivially accept if endpoints span directly across the rectangle
+- boolean xoverlap = (x1tag * x2tag <= 0);
+- boolean yoverlap = (y1tag * y2tag <= 0);
+- if (x1tag == INSIDE && x2tag == INSIDE && yoverlap) {
+- return true;
+- }
+- if (y1tag == INSIDE && y2tag == INSIDE && xoverlap) {
+- return true;
+- }
+-
+- // We now know that both endpoints are outside the rectangle
+- // but the 4 points are not all on one side of the rectangle.
+- // Therefore the curve cannot be contained inside the rectangle,
+- // but the rectangle might be contained inside the curve, or
+- // the curve might intersect the boundary of the rectangle.
+-
+- double[] eqn = new double[4];
+- double[] res = new double[4];
+- if (!yoverlap) {
+- // Both y coordinates for the closing segment are above or
+- // below the rectangle which means that we can only intersect
+- // if the curve crosses the top (or bottom) of the rectangle
+- // in more than one place and if those crossing locations
+- // span the horizontal range of the rectangle.
+- fillEqn(eqn, (y1tag < INSIDE ? y : y+h), y1, ctrly1, ctrly2, y2);
+- int num = solveCubic(eqn, res);
+- num = evalCubic(res, num, true, true, null,
+- x1, ctrlx1, ctrlx2, x2);
+- // odd counts imply the crossing was out of [0,1] bounds
+- // otherwise there is no way for that part of the curve to
+- // "return" to meet its endpoint
+- return (num == 2 &&
+- getTag(res[0], x, x+w) * getTag(res[1], x, x+w) <= 0);
+- }
+-
+- // Y ranges overlap. Now we examine the X ranges
+- if (!xoverlap) {
+- // Both x coordinates for the closing segment are left of
+- // or right of the rectangle which means that we can only
+- // intersect if the curve crosses the left (or right) edge
+- // of the rectangle in more than one place and if those
+- // crossing locations span the vertical range of the rectangle.
+- fillEqn(eqn, (x1tag < INSIDE ? x : x+w), x1, ctrlx1, ctrlx2, x2);
+- int num = solveCubic(eqn, res);
+- num = evalCubic(res, num, true, true, null,
+- y1, ctrly1, ctrly2, y2);
+- // odd counts imply the crossing was out of [0,1] bounds
+- // otherwise there is no way for that part of the curve to
+- // "return" to meet its endpoint
+- return (num == 2 &&
+- getTag(res[0], y, y+h) * getTag(res[1], y, y+h) <= 0);
+- }
+-
+- // The X and Y ranges of the endpoints overlap the X and Y
+- // ranges of the rectangle, now find out how the endpoint
+- // line segment intersects the Y range of the rectangle
+- double dx = x2 - x1;
+- double dy = y2 - y1;
+- double k = y2 * x1 - x2 * y1;
+- int c1tag, c2tag;
+- if (y1tag == INSIDE) {
+- c1tag = x1tag;
+- } else {
+- c1tag = getTag((k + dx * (y1tag < INSIDE ? y : y+h)) / dy, x, x+w);
+- }
+- if (y2tag == INSIDE) {
+- c2tag = x2tag;
+- } else {
+- c2tag = getTag((k + dx * (y2tag < INSIDE ? y : y+h)) / dy, x, x+w);
+- }
+- // If the part of the line segment that intersects the Y range
+- // of the rectangle crosses it horizontally - trivially accept
+- if (c1tag * c2tag <= 0) {
+- return true;
+- }
+-
+- // Now we know that both the X and Y ranges intersect and that
+- // the endpoint line segment does not directly cross the rectangle.
+- //
+- // We can almost treat this case like one of the cases above
+- // where both endpoints are to one side, except that we may
+- // get one or three intersections of the curve with the vertical
+- // side of the rectangle. This is because the endpoint segment
+- // accounts for the other intersection in an even pairing. Thus,
+- // with the endpoint crossing we end up with 2 or 4 total crossings.
+- //
+- // (Remember there is overlap in both the X and Y ranges which
+- // means that the segment itself must cross at least one vertical
+- // edge of the rectangle - in particular, the "near vertical side"
+- // - leaving an odd number of intersections for the curve.)
+- //
+- // Now we calculate the y tags of all the intersections on the
+- // "near vertical side" of the rectangle. We will have one with
+- // the endpoint segment, and one or three with the curve. If
+- // any pair of those vertical intersections overlap the Y range
+- // of the rectangle, we have an intersection. Otherwise, we don't.
+-
+- // c1tag = vertical intersection class of the endpoint segment
+- //
+- // Choose the y tag of the endpoint that was not on the same
+- // side of the rectangle as the subsegment calculated above.
+- // Note that we can "steal" the existing Y tag of that endpoint
+- // since it will be provably the same as the vertical intersection.
+- c1tag = ((c1tag * x1tag <= 0) ? y1tag : y2tag);
+-
+- // Now we have to calculate an array of solutions of the curve
+- // with the "near vertical side" of the rectangle. Then we
+- // need to sort the tags and do a pairwise range test to see
+- // if either of the pairs of crossings spans the Y range of
+- // the rectangle.
+- //
+- // Note that the c2tag can still tell us which vertical edge
+- // to test against.
+- fillEqn(eqn, (c2tag < INSIDE ? x : x+w), x1, ctrlx1, ctrlx2, x2);
+- int num = solveCubic(eqn, res);
+- num = evalCubic(res, num, true, true, null, y1, ctrly1, ctrly2, y2);
+-
+- // Now put all of the tags into a bucket and sort them. There
+- // is an intersection iff one of the pairs of tags "spans" the
+- // Y range of the rectangle.
+- int tags[] = new int[num+1];
+- for (int i = 0; i < num; i++) {
+- tags[i] = getTag(res[i], y, y+h);
+- }
+- tags[num] = c1tag;
+- Arrays.sort(tags);
+- return ((num >= 1 && tags[0] * tags[1] <= 0) ||
+- (num >= 3 && tags[2] * tags[3] <= 0));
++ int numCrossings = rectCrossings(x, y, w, h);
++ // the intended return value is
++ // numCrossings != 0 || numCrossings == Curve.RECT_INTERSECTS
++ // but if (numCrossings != 0) numCrossings == INTERSECTS won't matter
++ // and if !(numCrossings != 0) then numCrossings == 0, so
++ // numCrossings != RECT_INTERSECT
++ return numCrossings != 0;
+ }
+
+ /**
diff -r 82d83ff8b150 -r eee57a146340 patches/openjdk/4645692-CubicCurve2D.solveCubic.patch
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/patches/openjdk/4645692-CubicCurve2D.solveCubic.patch Tue Feb 01 14:21:02 2011 -0500
@@ -0,0 +1,717 @@
+diff -Nr --unified=3 ./openjdk.old/jdk/src/share/classes/java/awt/geom/CubicCurve2D.java ./openjdk/jdk/src/share/classes/java/awt/geom/CubicCurve2D.java
+--- ./openjdk.old/jdk/src/share/classes/java/awt/geom/CubicCurve2D.java 2011-02-01 10:52:21.560149275 -0500
++++ ./openjdk/jdk/src/share/classes/java/awt/geom/CubicCurve2D.java 2011-02-01 10:52:37.112148647 -0500
+@@ -31,6 +31,10 @@
+ import java.io.Serializable;
+ import sun.awt.geom.Curve;
+
++import static java.lang.Math.abs;
++import static java.lang.Math.max;
++import static java.lang.Math.ulp;
++
+ /**
+ * The <code>CubicCurve2D</code> class defines a cubic parametric curve
+ * segment in {@code (x,y)} coordinate space.
+@@ -1083,95 +1087,286 @@
+ * @since 1.3
+ */
+ public static int solveCubic(double eqn[], double res[]) {
+- // From Numerical Recipes, 5.6, Quadratic and Cubic Equations
+- double d = eqn[3];
+- if (d == 0.0) {
+- // The cubic has degenerated to quadratic (or line or ...).
++ // From Graphics Gems:
++ // http://tog.acm.org/resources/GraphicsGems/gems/Roots3And4.c
++ final double d = eqn[3];
++ if (d == 0) {
+ return QuadCurve2D.solveQuadratic(eqn, res);
+ }
+- double a = eqn[2] / d;
+- double b = eqn[1] / d;
+- double c = eqn[0] / d;
+- int roots = 0;
+- double Q = (a * a - 3.0 * b) / 9.0;
+- double R = (2.0 * a * a * a - 9.0 * a * b + 27.0 * c) / 54.0;
+- double R2 = R * R;
+- double Q3 = Q * Q * Q;
+- a = a / 3.0;
+- if (R2 < Q3) {
+- double theta = Math.acos(R / Math.sqrt(Q3));
+- Q = -2.0 * Math.sqrt(Q);
++
++ /* normal form: x^3 + Ax^2 + Bx + C = 0 */
++ final double A = eqn[2] / d;
++ final double B = eqn[1] / d;
++ final double C = eqn[0] / d;
++
++
++ // substitute x = y - A/3 to eliminate quadratic term:
++ // x^3 +Px + Q = 0
++ //
++ // Since we actually need P/3 and Q/2 for all of the
++ // calculations that follow, we will calculate
++ // p = P/3
++ // q = Q/2
++ // instead and use those values for simplicity of the code.
++ double sq_A = A * A;
++ double p = 1.0/3 * (-1.0/3 * sq_A + B);
++ double q = 1.0/2 * (2.0/27 * A * sq_A - 1.0/3 * A * B + C);
++
++ /* use Cardano's formula */
++
++ double cb_p = p * p * p;
++ double D = q * q + cb_p;
++
++ final double sub = 1.0/3 * A;
++
++ int num;
++ if (D < 0) { /* Casus irreducibilis: three real solutions */
++ // see: http://en.wikipedia.org/wiki/Cubic_function#Trigonometric_.28and_hyperbolic.29_method
++ double phi = 1.0/3 * Math.acos(-q / Math.sqrt(-cb_p));
++ double t = 2 * Math.sqrt(-p);
++
+ if (res == eqn) {
+- // Copy the eqn so that we don't clobber it with the
+- // roots. This is needed so that fixRoots can do its
+- // work with the original equation.
+- eqn = new double[4];
+- System.arraycopy(res, 0, eqn, 0, 4);
++ eqn = Arrays.copyOf(eqn, 4);
+ }
+- res[roots++] = Q * Math.cos(theta / 3.0) - a;
+- res[roots++] = Q * Math.cos((theta + Math.PI * 2.0)/ 3.0) - a;
+- res[roots++] = Q * Math.cos((theta - Math.PI * 2.0)/ 3.0) - a;
+- fixRoots(res, eqn);
+- } else {
+- boolean neg = (R < 0.0);
+- double S = Math.sqrt(R2 - Q3);
+- if (neg) {
+- R = -R;
++
++ res[ 0 ] = ( t * Math.cos(phi));
++ res[ 1 ] = (-t * Math.cos(phi + Math.PI / 3));
++ res[ 2 ] = (-t * Math.cos(phi - Math.PI / 3));
++ num = 3;
++
++ for (int i = 0; i < num; ++i) {
++ res[ i ] -= sub;
+ }
+- double A = Math.pow(R + S, 1.0 / 3.0);
+- if (!neg) {
+- A = -A;
++
++ } else {
++ // Please see the comment in fixRoots marked 'XXX' before changing
++ // any of the code in this case.
++ double sqrt_D = Math.sqrt(D);
++ double u = Math.cbrt(sqrt_D - q);
++ double v = - Math.cbrt(sqrt_D + q);
++ double uv = u+v;
++
++ num = 1;
++
++ double err = 1200000000*ulp(abs(uv) + abs(sub));
++ if (iszero(D, err) || within(u, v, err)) {
++ if (res == eqn) {
++ eqn = Arrays.copyOf(eqn, 4);
++ }
++ res[1] = -(uv / 2) - sub;
++ num = 2;
+ }
+- double B = (A == 0.0) ? 0.0 : (Q / A);
+- res[roots++] = (A + B) - a;
++ // this must be done after the potential Arrays.copyOf
++ res[ 0 ] = uv - sub;
+ }
+- return roots;
++
++ if (num > 1) { // num == 3 || num == 2
++ num = fixRoots(eqn, res, num);
++ }
++ if (num > 2 && (res[2] == res[1] || res[2] == res[0])) {
++ num--;
++ }
++ if (num > 1 && res[1] == res[0]) {
++ res[1] = res[--num]; // Copies res[2] to res[1] if needed
++ }
++ return num;
++ }
++
++ // preconditions: eqn != res && eqn[3] != 0 && num > 1
++ // This method tries to improve the accuracy of the roots of eqn (which
++ // should be in res). It also might eliminate roots in res if it decideds
++ // that they're not real roots. It will not check for roots that the
++ // computation of res might have missed, so this method should only be
++ // used when the roots in res have been computed using an algorithm
++ // that never underestimates the number of roots (such as solveCubic above)
++ private static int fixRoots(double[] eqn, double[] res, int num) {
++ double[] intervals = {eqn[1], 2*eqn[2], 3*eqn[3]};
++ int critCount = QuadCurve2D.solveQuadratic(intervals, intervals);
++ if (critCount == 2 && intervals[0] == intervals[1]) {
++ critCount--;
++ }
++ if (critCount == 2 && intervals[0] > intervals[1]) {
++ double tmp = intervals[0];
++ intervals[0] = intervals[1];
++ intervals[1] = tmp;
++ }
++
++ // below we use critCount to possibly filter out roots that shouldn't
++ // have been computed. We require that eqn[3] != 0, so eqn is a proper
++ // cubic, which means that its limits at -/+inf are -/+inf or +/-inf.
++ // Therefore, if critCount==2, the curve is shaped like a sideways S,
++ // and it could have 1-3 roots. If critCount==0 it is monotonic, and
++ // if critCount==1 it is monotonic with a single point where it is
++ // flat. In the last 2 cases there can only be 1 root. So in cases
++ // where num > 1 but critCount < 2, we eliminate all roots in res
++ // except one.
++
++ if (num == 3) {
++ double xe = getRootUpperBound(eqn);
++ double x0 = -xe;
++
++ Arrays.sort(res, 0, num);
++ if (critCount == 2) {
++ // this just tries to improve the accuracy of the computed
++ // roots using Newton's method.
++ res[0] = refineRootWithHint(eqn, x0, intervals[0], res[0]);
++ res[1] = refineRootWithHint(eqn, intervals[0], intervals[1], res[1]);
++ res[2] = refineRootWithHint(eqn, intervals[1], xe, res[2]);
++ return 3;
++ } else if (critCount == 1) {
++ // we only need fx0 and fxe for the sign of the polynomial
++ // at -inf and +inf respectively, so we don't need to do
++ // fx0 = solveEqn(eqn, 3, x0); fxe = solveEqn(eqn, 3, xe)
++ double fxe = eqn[3];
++ double fx0 = -fxe;
++
++ double x1 = intervals[0];
++ double fx1 = solveEqn(eqn, 3, x1);
++
++ // if critCount == 1 or critCount == 0, but num == 3 then
++ // something has gone wrong. This branch and the one below
++ // would ideally never execute, but if they do we can't know
++ // which of the computed roots is closest to the real root;
++ // therefore, we can't use refineRootWithHint. But even if
++ // we did know, being here most likely means that the
++ // curve is very flat close to two of the computed roots
++ // (or maybe even all three). This might make Newton's method
++ // fail altogether, which would be a pain to detect and fix.
++ // This is why we use a very stable bisection method.
++ if (oppositeSigns(fx0, fx1)) {
++ res[0] = bisectRootWithHint(eqn, x0, x1, res[0]);
++ } else if (oppositeSigns(fx1, fxe)) {
++ res[0] = bisectRootWithHint(eqn, x1, xe, res[2]);
++ } else /* fx1 must be 0 */ {
++ res[0] = x1;
++ }
++ // return 1
++ } else if (critCount == 0) {
++ res[0] = bisectRootWithHint(eqn, x0, xe, res[1]);
++ // return 1
++ }
++ } else if (num == 2 && critCount == 2) {
++ // XXX: here we assume that res[0] has better accuracy than res[1].
++ // This is true because this method is only used from solveCubic
++ // which puts in res[0] the root that it would compute anyway even
++ // if num==1. If this method is ever used from any other method, or
++ // if the solveCubic implementation changes, this assumption should
++ // be reevaluated, and the choice of goodRoot might have to become
++ // goodRoot = (abs(eqn'(res[0])) > abs(eqn'(res[1]))) ? res[0] : res[1]
++ // where eqn' is the derivative of eqn.
++ double goodRoot = res[0];
++ double badRoot = res[1];
++ double x1 = intervals[0];
++ double x2 = intervals[1];
++ // If a cubic curve really has 2 roots, one of those roots must be
++ // at a critical point. That can't be goodRoot, so we compute x to
++ // be the farthest critical point from goodRoot. If there are two
++ // roots, x must be the second one, so we evaluate eqn at x, and if
++ // it is zero (or close enough) we put x in res[1] (or badRoot, if
++ // |solveEqn(eqn, 3, badRoot)| < |solveEqn(eqn, 3, x)| but this
++ // shouldn't happen often).
++ double x = abs(x1 - goodRoot) > abs(x2 - goodRoot) ? x1 : x2;
++ double fx = solveEqn(eqn, 3, x);
++
++ if (iszero(fx, 10000000*ulp(x))) {
More information about the distro-pkg-dev
mailing list