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

Jeremy duke at openjdk.java.net
Thu Nov 11 09:44:15 UTC 2021


> 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
  
  This adds an exploratory algorithm that tries to identify how to expand the double-based bounding box. It is currently problematic, but I'm committing it for review/feedback. Maybe this will look like a familiar problem to someone more familiar with this subject? Once we settle on how to address machine error: I'll either adapt this file into a more proper unit test or delete it.
  
  This is an attempt to explore Laurent's comments here:
  https://github.com/openjdk/jdk/pull/6227#discussion_r746450132
  
  The problem is our double-based approach can be a little bit too small because of machine error. We need it to only ever err on the side of being too large.
  
  Currently in this class we're applying a `margin` as follows:
  ```
         double x = coeff[0] + t * (coeff[1] + t * coeff[2]);
         double margin = marginMultiplier * Math.ulp(x);
         if (x - margin < leftX) leftX = x - margin;
         if (x + margin> rightX) rightX = x + margin;
  ```
  
  This class tests a million shapes and tries to identify the smallest constant `marginMultiplier` that always returns an appropriate bounding box.
  
  The current problem is this constant is multiplied by the ulp of a value. So as the value (for ex: the left x-value) approaches zero the ulp becomes increasingly small, so the multiplier has to become extremely large. Currently this algorithm settles on a multiplier of: 7.864956084850002E10
  
  If we treat the constant as a multiplier of the x-value itself (for ex: `margin = multiplier * Math.abs(x)``), then this algorithm settles on 0.000013173867835580114.
  
  What is a good way to evaluate `margin` in the code snippet above?
  
  Or at some point we could switch back to using the bezier control point: what fuzzy sliding scale logic do we use to determine when to use "the old way" and when to use "the new way"?

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

Changes:
  - all: https://git.openjdk.java.net/jdk/pull/6227/files
  - new: https://git.openjdk.java.net/jdk/pull/6227/files/b7ca69c8..4b9d87d6

Webrevs:
 - full: https://webrevs.openjdk.java.net/?repo=jdk&pr=6227&range=05
 - incr: https://webrevs.openjdk.java.net/?repo=jdk&pr=6227&range=04-05

  Stats: 452 lines in 1 file changed: 452 ins; 0 del; 0 mod
  Patch: https://git.openjdk.java.net/jdk/pull/6227.diff
  Fetch: git fetch https://git.openjdk.java.net/jdk pull/6227/head:pull/6227

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



More information about the client-libs-dev mailing list