RFR: 8176501: Method Shape.getBounds2D() incorrectly includes Bezier control points in bounding box [v2]

[Laurent Bourgès]

On Fri, 5 Nov 2021 04:41:34 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 one additional commit since the last revision:
> 
>   8176501: Method Shape.getBounds2D() incorrectly includes Bezier control points in bounding box
>   
>   Addressing some of Laurent's code review recommendations/comments:
>   
>   1. use the convention t for the parametric variable x(t),y(t)
>   2. solve the quadratic equation using QuadCurve2d.solveQuadratic() or like Helpers.quadraticRoots()
>   3. always use braces for x = (a < b) ? ...
>   4. always use double-precision constants in math or logical operations: (2 * x => 2.0 * x) and (coefficients[3] != 0) => (coefficients[3] != 0.0)
>   
>   (There are two additional recommendations not in this commit that I'll ask about shortly.)
>   
>   See https://github.com/openjdk/jdk/pull/6227#issuecomment-959757954

src/java.desktop/share/classes/java/awt/geom/Path2D.java line 2105:

> 2103:         // define x and y parametric coefficients where:
> 2104:         // x(t) = x_coeff[0] + x_coeff[1] * t + x_coeff[2] * t^2 + x_coeff[3] * t^3
> 2105:         double[] x_coeff = new double[4];

make arrays final to be obvious (dirty arrays)

src/java.desktop/share/classes/java/awt/geom/Path2D.java line 2118:

> 2116:         double lastY = 0.0;
> 2117: 
> 2118:         pathIteratorLoop : while (!pi.isDone()) {

remove the label `pathIteratorLoop` (trivial)

src/java.desktop/share/classes/java/awt/geom/Path2D.java line 2152:

> 2150:             }
> 2151: 
> 2152:             // here's the slightly trickier part: examine quadratic and cubic

add a shortcut test for better readability:
`if ((type == PathIterator.SEG_QUADTO) || (type == PathIterator.SEG_CUBICTO)) {`

src/java.desktop/share/classes/java/awt/geom/Path2D.java line 2155:

> 2153:             // segments for extrema where t is between (0, 1):
> 2154: 
> 2155:             boolean definedParametricEquations;

useless with the shortcut test

src/java.desktop/share/classes/java/awt/geom/Path2D.java line 2159:

> 2157:                 definedParametricEquations = true;
> 2158: 
> 2159:                 x_coeff[3] = 0.0;

after computing coefficients (abcd), also compute (da db c) needed by root finding next

src/java.desktop/share/classes/java/awt/geom/Path2D.java line 2188:

> 2186:                 for(int i = 0; i < tExtremaCount; i++) {
> 2187:                     double t = tExtrema[i];
> 2188:                     if (t > 0 && t < 1) {

use `if (t > 0.0 && t < 1.0) {`

src/java.desktop/share/classes/java/awt/geom/Path2D.java line 2189:

> 2187:                     double t = tExtrema[i];
> 2188:                     if (t > 0 && t < 1) {
> 2189:                         double x = x_coeff[0] + t * (x_coeff[1] + t * (x_coeff[2] + t * x_coeff[3]));

using 3rd order polynom is only useful for cubic curves, for quads 2nd order is enough.
How to improve precision on (abcd) or (bcd) polynomial evaluation ?

src/java.desktop/share/classes/java/awt/geom/Path2D.java line 2205:

> 2203:                 }
> 2204:             }
> 2205: 

close the shortcut test
`}`

src/java.desktop/share/classes/sun/awt/geom/Curve.java line 759:

> 757:         }
> 758: 
> 759:         if (coefficients[3] > -.01 && coefficients[3] < .01 && coefficients[2] != 0.0) {

do not test coefficients[3] within 0.1 !
Always use QuadCurve2D.solveQuadratic() that handles the case coefficient(x^2) = 0.
Finally this method findExtrema() is only necessary if control points (x or y) are given to determine the dx , dy polynoms and return roots... I prefer moving this code directly in getBounds2D() to have a more efficient implementation (= 1 method with 1 loop) to avoid allocation of the array double[] eqn = new double[].

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

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