RFR: 8176501: Method Shape.getBounds2D() incorrectly includes Bezier control points in bounding box [v7]
Laurent Bourgès
lbourges at openjdk.java.net
Mon Nov 15 20:54:40 UTC 2021
On Fri, 12 Nov 2021 05:47:12 GMT, Jeremy <duke at openjdk.java.net> wrote:
>> This removes code that relied on consulting the Bezier control points to calculate the Rectangle2D bounding box. Instead it's pretty straight-forward to convert the Bezier control points into the x & y parametric equations. At their most complex these equations are cubic polynomials, so calculating their extrema is just a matter of applying the quadratic formula to calculate their extrema. (Or in path segments that are quadratic/linear/constant: we do even less work.)
>>
>> The bug writeup indicated they wanted Path2D#getBounds2D() to be more accurate/concise. They didn't explicitly say they wanted CubicCurve2D and QuadCurve2D to become more accurate too. But a preexisting unit test failed when Path2D#getBounds2D() was updated and those other classes weren't. At this point I considered either:
>> A. Updating CubicCurve2D and QuadCurve2D to use the new more accurate getBounds2D() or
>> B. Updating the unit test to forgive the discrepancy.
>>
>> I chose A. Which might technically be seen as scope creep, but it feels like a more holistic/better approach.
>>
>> Other shapes in java.awt.geom should not require updating, because they already identify concise bounds.
>>
>> This also includes a new unit test (in Path2D/UnitTest.java) that fails without the changes in this commit.
>
> Jeremy has updated the pull request incrementally with three additional commits since the last revision:
>
> - 8176501: Method Shape.getBounds2D() incorrectly includes Bezier control points in bounding box
>
> This adds a new unit test that calculates a high-precision bounding box (using BigDecimals), and then makes sure our double-based logic contains that high-precision bounds.
>
> This restores getBounds2D() to its original contract: it should only ever be *larger* than the actual bounds -- it should never be smaller.
>
> Also we want to only apply this margin (aka "padding") when we deal with polynomial-based extrema. We should never apply it to line-based polygons. For ex: a Path2D that represents an int-based rectangle should return the same bounds as before 8176501 was addressed.
>
> This test currently only addresses very small cubic curves.
>
> I experimented with very large cubic & quadratic curves, but I didn't come up with a unit test that failed before and after this commit. Adding unit tests for large curve segments is a possible area of improvement.
> - 8176501: Method Shape.getBounds2D() incorrectly includes Bezier control points in bounding box
>
> Addressing code review comments: given current code structure we don't need separate data structures for x and y equations.
> - 8176501: Method Shape.getBounds2D() incorrectly includes Bezier control points in bounding box
>
> Removing accidental leftover code. This should have been removed in a recent previous commit. The preceding code already defines these values.
src/java.desktop/share/classes/java/awt/geom/Path2D.java line 2124:
> 2122: // a box that is slightly too small. But the contract of this method
> 2123: // says we should err on the side of being too large.
> 2124: // So to address this: we take the difference between the control
This is my alternative proposal to use the polynomial error as base error (cubic case is more tricky as solveQuadratic is problematic too for huge curves):
// So to address this: we take using the upper limit of numerical error
// caused by the polynomial evaluation (horner scheme).
for (; !pi.isDone(); pi.next()) {
final int type = pi.currentSegment(coords);
switch (type) {
case PathIterator.SEG_MOVETO:
if (!started) {
started = true;
leftX = rightX = coords[0];
topY = bottomY = coords[1];
} else {
if (coords[0] < leftX) {
leftX = coords[0];
}
if (coords[0] > rightX) {
rightX = coords[0];
}
if (coords[1] < topY) {
topY = coords[1];
}
if (coords[1] > bottomY) {
bottomY = coords[1];
}
}
lastX = coords[0];
lastY = coords[1];
break;
case PathIterator.SEG_LINETO:
if (coords[0] < leftX) {
leftX = coords[0];
}
if (coords[0] > rightX) {
rightX = coords[0];
}
if (coords[1] < topY) {
topY = coords[1];
}
if (coords[1] > bottomY) {
bottomY = coords[1];
}
lastX = coords[0];
lastY = coords[1];
break;
case PathIterator.SEG_QUADTO:
if (coords[2] < leftX) {
leftX = coords[2];
}
if (coords[2] > rightX) {
rightX = coords[2];
}
if (coords[3] < topY) {
topY = coords[3];
}
if (coords[3] > bottomY) {
bottomY = coords[3];
}
if (coords[0] < leftX || coords[0] > rightX) {
final double dx21 = (coords[0] - lastX);
coeff[2] = (coords[2] - coords[0]) - dx21; // A = P3 - P0 - 2 P2
coeff[1] = 2.0 * dx21; // B = 2 (P2 - P1)
coeff[0] = lastX; // C = P1
deriv_coeff[0] = coeff[1];
deriv_coeff[1] = 2.0 * coeff[2];
double t = -deriv_coeff[0] / deriv_coeff[1];
if (t > 0.0 && t < 1.0) {
double x = coeff[0] + t * (coeff[1] + t * coeff[2]);
// error condition = sum ( abs (coeff) ):
final double margin = Math.ulp( Math.abs(coeff[0])
+ Math.abs(coeff[1]) + Math.abs(coeff[2]));
if (x - margin < leftX) {
leftX = x - margin;
}
if (x + margin > rightX) {
rightX = x + margin;
}
}
}
if (coords[1] < topY || coords[1] > bottomY) {
final double dy21 = (coords[1] - lastY);
coeff[2] = (coords[3] - coords[1]) - dy21;
coeff[1] = 2.0 * dy21;
coeff[0] = lastY;
deriv_coeff[0] = coeff[1];
deriv_coeff[1] = 2.0 * coeff[2];
double t = -deriv_coeff[0] / deriv_coeff[1];
if (t > 0.0 && t < 1.0) {
double y = coeff[0] + t * (coeff[1] + t * coeff[2]);
// error condition = sum ( abs (coeff) ):
final double margin = Math.ulp( Math.abs(coeff[0])
+ Math.abs(coeff[1]) + Math.abs(coeff[2]));
if (y - margin < topY) {
topY = y - margin;
}
if (y + margin > bottomY) {
bottomY = y + margin;
}
}
}
lastX = coords[2];
lastY = coords[3];
break;
case PathIterator.SEG_CUBICTO:
if (coords[4] < leftX) {
leftX = coords[4];
}
if (coords[4] > rightX) {
rightX = coords[4];
}
if (coords[5] < topY) {
topY = coords[5];
}
if (coords[5] > bottomY) {
bottomY = coords[5];
}
if (coords[0] < leftX || coords[0] > rightX || coords[2] < leftX || coords[2] > rightX) {
final double dx32 = 3.0 * (coords[2] - coords[0]);
final double dx21 = 3.0 * (coords[0] - lastX);
coeff[3] = (coords[4] - lastX) - dx32; // A = P3 - P0 - 3 (P2 - P1) = (P3 - P0) + 3 (P1 - P2)
coeff[2] = (dx32 - dx21); // B = 3 (P2 - P1) - 3(P1 - P0) = 3 (P2 + P0) - 6 P1
coeff[1] = dx21; // C = 3 (P1 - P0)
coeff[0] = lastX; // D = P0
deriv_coeff[0] = coeff[1];
deriv_coeff[1] = 2.0 * coeff[2];
deriv_coeff[2] = 3.0 * coeff[3];
// solveQuadratic should be improved to get correct t extrema (1 ulp):
final int tExtremaCount = QuadCurve2D.solveQuadratic(deriv_coeff, tExtrema);
if (tExtremaCount > 0) {
// error condition = sum ( abs (coeff) ):
final double margin = Math.ulp(Math.abs(coeff[0])
+ Math.abs(coeff[1]) + Math.abs(coeff[2])
+ Math.abs(coeff[3]));
for (int i = 0; i < tExtremaCount; i++) {
final double t = tExtrema[i];
if (t > 0.0 && t < 1.0) {
double x = coeff[0] + t * (coeff[1] + t * (coeff[2] + t * coeff[3]));
if (x - margin < leftX) {
leftX = x - margin;
}
if (x + margin > rightX) {
rightX = x + margin;
}
}
}
}
}
if (coords[1] < topY || coords[1] > bottomY || coords[3] < topY || coords[3] > bottomY) {
final double dy32 = 3.0 * (coords[3] - coords[1]);
final double dy21 = 3.0 * (coords[1] - lastY);
coeff[3] = (coords[5] - lastY) - dy32;
coeff[2] = (dy32 - dy21);
coeff[1] = dy21;
coeff[0] = lastY;
deriv_coeff[0] = coeff[1];
deriv_coeff[1] = 2.0 * coeff[2];
deriv_coeff[2] = 3.0 * coeff[3];
int tExtremaCount = QuadCurve2D.solveQuadratic(deriv_coeff, tExtrema);
if (tExtremaCount > 0) {
// error condition = sum ( abs (coeff) ):
final double margin = Math.ulp(Math.abs(coeff[0])
+ Math.abs(coeff[1]) + Math.abs(coeff[2])
+ Math.abs(coeff[3]));
for (int i = 0; i < tExtremaCount; i++) {
double t = tExtrema[i];
if (t > 0.0 && t < 1.0) {
double y = coeff[0] + t * (coeff[1] + t * (coeff[2] + t * coeff[3]));
if (y - margin < topY) {
topY = y - margin;
}
if (y + margin > bottomY) {
bottomY = y + margin;
}
}
}
}
}
lastX = coords[4];
lastY = coords[5];
break;
case PathIterator.SEG_CLOSE:
default:
}
}
-------------
PR: https://git.openjdk.java.net/jdk/pull/6227
More information about the client-libs-dev
mailing list