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

[Laurent Bourgès]

On Fri, 5 Nov 2021 19:51:18 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 more of Laurent's code review recommendations/comments:
>   
>   1. solve the quadratic equation using QuadCurve2d.solveQuadratic() or like Helpers.quadraticRoots()
>   
>   (I was pleasantly surprised to see QuadCurve2D.solveQuadratic(..) does well for the unit test where the t^2 coefficient approaches zero. We still get an extra root, but it's greater than 10^13, so it is ignored by our (0,1) bounds check later.)
>   
>   2. determine the derivatives da / db
>   
>   We now define x_deriv_coeff and y_deriv_coeff.
>   
>   3. remove the label pathIteratorLoop
>   
>   4. use `for (final PathIterator it = shape.getPathIterator(null); !it.isDone(); it.next()) {`
>   
>   (The initial statement is empty in this case because PathIterator is an argument.)
>   
>   5. make arrays final to be obvious
>   
>   6. add a shortcut test for better readability / close the shortcut test
>   
>   7. after computing coefficients (abcd), also compute (da db c) needed by root finding next
>   
>   8. useless with the shortcut test (re "definedParametricEquations" boolean)
>   
>   9. use if (t > 0.0 && t < 1.0)
>   
>   (Sorry, that got lost in the prev refactor.)
>   
>   10. add explicitely the SEG_CLOSE case (skip = continue) before the default case
>   
>   This commit does not address comments about accuracy/precision. I'll explore those separately later.

Looks going in good shape !
I agree accuracy is tricky as bbox may be smaller (undershoot) than ideal curve as roots or computed points are approximations != exact values. Maybe adding a small margin could help ...

I noticed javafx uses an optimization to only process quad / cubic curves if control points are out of the current bbox,  it can reduce a lot the extra overhead to find extrema... if useless.
See the test:

if (bbox[0] > coords[0] || bbox[2] < coords[0] ||
                        bbox[0] > coords[2] || bbox[2] < coords[2])
                    {
                        accumulateCubic(bbox, 0, x0, coords[0], coords[2], x1);
                    }

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

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