RFR: 8176501: Method Shape.getBounds2D() incorrectly includes Bezier control points in bounding box [v7]
Jeremy
duke at openjdk.java.net
Tue Nov 16 05:27:41 UTC 2021
On Mon, 15 Nov 2021 20:52:00 GMT, Laurent Bourgès <lbourges at openjdk.org> wrote:
>> 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:
> }
> }
Looks good, and it passes all the unit tests. I pushed an update with this code. (Although immediately after that I pushed a refactor for readability that you previously requested -- so the logic/margin is in the branch now but it looks a little different already...)
-------------
PR: https://git.openjdk.java.net/jdk/pull/6227
More information about the client-libs-dev
mailing list