On Fri, 12 Nov 2021 05:47:12 GMT, Jeremy <[email protected]> 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
