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

[Laurent Bourgès]

On Tue, 9 Nov 2021 10:28:45 GMT, Jeremy <duke at openjdk.java.net> wrote:

>> Ideally the compensated-horner scheme should be used to guarantee optimal precision (2x slower):
>> paper: 
>> https://www-pequan.lip6.fr/~jmc/polycopies/Compensation-horner.pdf
>> 
>> See julia code: 
>> https://discourse.julialang.org/t/more-accurate-evalpoly/45932/6
>
> I don't think I can implement that on my own. Even if I fully understood the julia code, I assume I'd want to use the Math.fma(..) method. That method uses BigDecimals, which I assume (?) we don't want to use in a loop like this for performance reasons.
> 
> If this level of high-precision is considered essential to resolving this bug: then personally I'm at an impasse and we should either close this PR or I'll need some external help.
> 
> Or possible compromises might include:
> 
> A. Add a method like this in Curve.java:
> 
> public double evaluateCubicPolynomial(double a, double b, double c, double d, double t) {
>     return d + t * (c + t * (b + t * a)));
> }
> 
> 
> And add a ticket that someone else can address separately to improve the accuracy of that method. (Also maybe other areas in the AWT codebase should use the same method? Like `Order3#XforT`?)
> 
> B. We can modify my new method signature from:
> `public static Rectangle2D getBounds2D(PathIterator pi)`
> to:
> `public static Rectangle2D getBounds2D(PathIterator pi, boolean highPrecision)`
> 
> Where if `highPrecision` is true we use the new implementation *which may suffer rounding errors and be a few ulps too small*. And if it is false then we use the old implementation which suffers from the original bug. This has the benefit of definitely not breaking any existing code in existence. The downside is it puts the responsibility on developers to learn about and implement this new method. But at least it would exist.
> 
> Thoughts?

I agree it is out of the scope of this issue to implement high-precision polynom evaluation (compensated horder scheme), that I or anybody else could implement it later.
To ensure bounds2D are enclosing the shape entirely, I propose to add a small margin (10 ulps or more) to ascertain precision is good enough.
To determine the precision level, using fuzzy testing is the good approach : generate lots ofrandom paths => check bounds2D accuracy in ulp units.

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

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