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

[Laurent Bourgès]

On Tue, 9 Nov 2021 10:43:40 GMT, Laurent Bourgès <lbourges at openjdk.org> wrote:

>> 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.

@prrace @mrserb what do you think on this bug in terms of precision requirements?
- should bbox always include control points ?
- should ideal shape always fit in bbox ? So I propose to add a margin > numerical inaccuracies.

I can develop a numerical approach based on fuzzy testing:
- generate random curves (high magnitude changes on control points)
- use both this algorithm (double) and implement the same with BigDecimal
- estimate the extrema error = max distance(pts big decimal, pts double)

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

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