RFR: 8176501: Method Shape.getBounds2D() incorrectly includes Bezier pts

[Laurent Bourgès]

On Wed, 3 Nov 2021 07:27:03 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.

This issue relates to improving the bounding box of curves and general paths (Path2D). The former approach was based on the simple convex hull of curves (enclosing control points) but I agree it is sub-optimal for curves.
To obtain the more-close bounding box, finding curve extrema (cubic or quad only) is necessary, so I agree the problem consists in finding roots of the (dx/dy) curve that is:
- a 2nd order polynom for cubic curves,
- a 1th order polynom for quad curves.

1. I agree CubicCurve2D and QuadCurve2D should be improved too.
2. I looked at your code and tried to compare your approach with the Marlin renderer. 
It looks very similar. See Curve / Helpers class:
https://github.com/openjdk/jdk/blob/684edbb4c884cbc3e05118e4bc9808b5d5b71a74/src/java.desktop/share/classes/sun/java2d/marlin/Curve.java#L115
https://github.com/openjdk/jdk/blob/684edbb4c884cbc3e05118e4bc9808b5d5b71a74/src/java.desktop/share/classes/sun/java2d/marlin/Helpers.java#L56

Your code converts any Cubic or Quad curve to a cubic equation (abcd coefficients) for both x / y equations, then you derive the dx/dy equations and finally find roots of the quadratic equations.
The Marlin renderer approach looks more direct:
- set curve (abcd coefficients + their derivatives da db)
- get derivative roots by calling dxRoots/dyRoots:

     int dxRoots(final double[] roots, final int off) {
        return Helpers.quadraticRoots(dax, dbx, cx, roots, off);
    }

used in Helpers.findSubdivPoints():
see https://github.com/openjdk/jdk/blob/684edbb4c884cbc3e05118e4bc9808b5d5b71a74/src/java.desktop/share/classes/sun/java2d/marlin/Helpers.java#L238

I suggest your solution could be more direct and rename Curve.getPossibleExtremaInCubicEquation() to Curve.findExtrema():
- use the convention t for the parametric variable x(t),y(t)
- determine the derivatives da / db
- solve the quadratic equation using QuadCurve2d.solveQuadratic() or like Helpers.quadraticRoots()
- degenerated cases are causing troubles: t must in ]0,1[ so do not use any threshold like 0.1 or 10^-4 like in Marlin.

Syntax / typos:
- always use braces for x = (a < b) ? ...
- always use double-precision constants in math or logical operations: (2 * x => 2.0 * x) and (coefficients[3] != 0) => (coefficients[3] != 0.0)

Hope it helps,
Laurent

-------------

PR: https://git.openjdk.java.net/jdk/pull/6227