On Tue, 16 Nov 2021 05:22:13 GMT, Jeremy <d...@openjdk.java.net> wrote:
>> src/java.desktop/share/classes/java/awt/geom/Path2D.java line 2124:
>>
>>> 2122: // a box that is slightly too small. But the contract of this
>>> method
>>> 2123: // says we should err on the side of being too large.
>>> 2124: // So to address this: we take the difference between the
>>> control
>>
>> This is my alternative proposal to use the polynomial error as base error
>> (cubic case is more tricky as solveQuadratic is problematic too for huge
>> curves):
>>
>> // So to address this: we take using the upper limit of numerical
>> error
>> // caused by the polynomial evaluation (horner scheme).
>>
>> for (; !pi.isDone(); pi.next()) {
>> final int type = pi.currentSegment(coords);
>> switch (type) {
>> case PathIterator.SEG_MOVETO:
>> if (!started) {
>> started = true;
>> leftX = rightX = coords[0];
>> topY = bottomY = coords[1];
>> } else {
>> if (coords[0] < leftX) {
>> leftX = coords[0];
>> }
>> if (coords[0] > rightX) {
>> rightX = coords[0];
>> }
>> if (coords[1] < topY) {
>> topY = coords[1];
>> }
>> if (coords[1] > bottomY) {
>> bottomY = coords[1];
>> }
>> }
>> lastX = coords[0];
>> lastY = coords[1];
>> break;
>> case PathIterator.SEG_LINETO:
>> if (coords[0] < leftX) {
>> leftX = coords[0];
>> }
>> if (coords[0] > rightX) {
>> rightX = coords[0];
>> }
>> if (coords[1] < topY) {
>> topY = coords[1];
>> }
>> if (coords[1] > bottomY) {
>> bottomY = coords[1];
>> }
>> lastX = coords[0];
>> lastY = coords[1];
>> break;
>> case PathIterator.SEG_QUADTO:
>> if (coords[2] < leftX) {
>> leftX = coords[2];
>> }
>> if (coords[2] > rightX) {
>> rightX = coords[2];
>> }
>> if (coords[3] < topY) {
>> topY = coords[3];
>> }
>> if (coords[3] > bottomY) {
>> bottomY = coords[3];
>> }
>>
>> if (coords[0] < leftX || coords[0] > rightX) {
>> final double dx21 = (coords[0] - lastX);
>> coeff[2] = (coords[2] - coords[0]) - dx21; // A =
>> P3 - P0 - 2 P2
>> coeff[1] = 2.0 * dx21; // B = 2
>> (P2 - P1)
>> coeff[0] = lastX; // C = P1
>>
>> deriv_coeff[0] = coeff[1];
>> deriv_coeff[1] = 2.0 * coeff[2];
>>
>> double t = -deriv_coeff[0] / deriv_coeff[1];
>> if (t > 0.0 && t < 1.0) {
>> double x = coeff[0] + t * (coeff[1] + t *
>> coeff[2]);
>>
>> // error condition = sum ( abs (coeff) ):
>> final double margin = Math.ulp(
>> Math.abs(coeff[0])
>> + Math.abs(coeff[1]) +
>> Math.abs(coeff[2]));
>>
>> if (x - margin < leftX) {
>> leftX = x - margin;
>> }
>> if (x + margin > rightX) {
>> rightX = x + margin;
>> }
>> }
>> }
>> if (coords[1] < topY || coords[1] > bottomY) {
>> final double dy21 = (coords[1] - lastY);
>> coeff[2] = (coords[3] - coords[1]) - dy21;
>> coeff[1] = 2.0 * dy21;
>> coeff[0] = lastY;
>>
>> deriv_coeff[0] = coeff[1];
>> deriv_coeff[1] = 2.0 * coeff[2];
>>
>> double t = -deriv_coeff[0] / deriv_coeff[1];
>> if (t > 0.0 && t < 1.0) {
>> double y = coeff[0] + t * (coeff[1] + t *
>> coeff[2]);
>>
>> // error condition = sum ( abs (coeff) ):
>> final double margin = Math.ulp(
>> Math.abs(coeff[0])
>> + Math.abs(coeff[1]) +
>> Math.abs(coeff[2]));
>>
>> if (y - margin < topY) {
>> topY = y - margin;
>> }
>> if (y + margin > bottomY) {
>> bottomY = y + margin;
>> }
>> }
>> }
>> lastX = coords[2];
>> lastY = coords[3];
>> break;
>> case PathIterator.SEG_CUBICTO:
>> if (coords[4] < leftX) {
>> leftX = coords[4];
>> }
>> if (coords[4] > rightX) {
>> rightX = coords[4];
>> }
>> if (coords[5] < topY) {
>> topY = coords[5];
>> }
>> if (coords[5] > bottomY) {
>> bottomY = coords[5];
>> }
>>
>> if (coords[0] < leftX || coords[0] > rightX || coords[2]
>> < leftX || coords[2] > rightX) {
>> final double dx32 = 3.0 * (coords[2] - coords[0]);
>> final double dx21 = 3.0 * (coords[0] - lastX);
>> coeff[3] = (coords[4] - lastX) - dx32; // A = P3 -
>> P0 - 3 (P2 - P1) = (P3 - P0) + 3 (P1 - P2)
>> coeff[2] = (dx32 - dx21); // B = 3 (P2
>> - P1) - 3(P1 - P0) = 3 (P2 + P0) - 6 P1
>> coeff[1] = dx21; // C = 3 (P1
>> - P0)
>> coeff[0] = lastX; // D = P0
>>
>> deriv_coeff[0] = coeff[1];
>> deriv_coeff[1] = 2.0 * coeff[2];
>> deriv_coeff[2] = 3.0 * coeff[3];
>>
>> // solveQuadratic should be improved to get correct
>> t extrema (1 ulp):
>> final int tExtremaCount =
>> QuadCurve2D.solveQuadratic(deriv_coeff, tExtrema);
>> if (tExtremaCount > 0) {
>> // error condition = sum ( abs (coeff) ):
>> final double margin = Math.ulp(Math.abs(coeff[0])
>> + Math.abs(coeff[1]) + Math.abs(coeff[2])
>> + Math.abs(coeff[3]));
>>
>> for (int i = 0; i < tExtremaCount; i++) {
>> final double t = tExtrema[i];
>> if (t > 0.0 && t < 1.0) {
>> double x = coeff[0] + t * (coeff[1] + t
>> * (coeff[2] + t * coeff[3]));
>> if (x - margin < leftX) {
>> leftX = x - margin;
>> }
>> if (x + margin > rightX) {
>> rightX = x + margin;
>> }
>> }
>> }
>> }
>> }
>> if (coords[1] < topY || coords[1] > bottomY || coords[3]
>> < topY || coords[3] > bottomY) {
>> final double dy32 = 3.0 * (coords[3] - coords[1]);
>> final double dy21 = 3.0 * (coords[1] - lastY);
>> coeff[3] = (coords[5] - lastY) - dy32;
>> coeff[2] = (dy32 - dy21);
>> coeff[1] = dy21;
>> coeff[0] = lastY;
>>
>> deriv_coeff[0] = coeff[1];
>> deriv_coeff[1] = 2.0 * coeff[2];
>> deriv_coeff[2] = 3.0 * coeff[3];
>>
>> int tExtremaCount =
>> QuadCurve2D.solveQuadratic(deriv_coeff, tExtrema);
>> if (tExtremaCount > 0) {
>> // error condition = sum ( abs (coeff) ):
>> final double margin = Math.ulp(Math.abs(coeff[0])
>> + Math.abs(coeff[1]) + Math.abs(coeff[2])
>> + Math.abs(coeff[3]));
>>
>> for (int i = 0; i < tExtremaCount; i++) {
>> double t = tExtrema[i];
>> if (t > 0.0 && t < 1.0) {
>> double y = coeff[0] + t * (coeff[1] + t
>> * (coeff[2] + t * coeff[3]));
>> if (y - margin < topY) {
>> topY = y - margin;
>> }
>> if (y + margin > bottomY) {
>> bottomY = y + margin;
>> }
>> }
>> }
>> }
>> }
>> lastX = coords[4];
>> lastY = coords[5];
>> break;
>> case PathIterator.SEG_CLOSE:
>> default:
>> }
>> }
>
> Looks good, and it passes all the unit tests. I pushed an update with this
> code. (Although immediately after that I pushed a refactor for readability
> that you previously requested -- so the logic/margin is in the branch now but
> it looks a little different already...)
Here is the test result in marlin-math proving the margin condition is
satisfied from small to huge cubic curves:
https://github.com/bourgesl/marlin-math/blob/main/results/findExtrema/jdk17-2021-11-14-edge-cubic.log
Inaccuracies are within margin ~ 0.5 proved.
-------------
PR: https://git.openjdk.java.net/jdk/pull/6227
