On Mon, 15 Nov 2021 20:52:00 GMT, Laurent Bourgès <[email protected]> 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
