[OpenJDK 2D-Dev] CubicCurve2D.solveCubic and containment/intersection bugs.

[Denis Lila]

Hi Jim.

> I'm all in favor of simplification by using the new crossings code. I
> originally balked at using it because I thought it might be slower,
> but I didn't do any benchmarks to back that up. Have you benchmarked
> the changes at all?

As of now, yes. I tested 3 cases: (1) when the rectangle is clearly out of
bounds of the control polynomial, (2) when the rectangle is partially
contained in the curve, and (3) when it is fully contained in the curve.
I tested both contains() and intersects() with these three cases.

contains():
For cases (2) and (3), the timings were practically unchanged. Case (1)
was about 10 times slower. I reintroduced the statement
        
        if (!(contains(x, y) &&
              contains(x + w, y) &&
              contains(x + w, y + h) &&
              contains(x, y + h))) {
            return false;
        }

and that fixed the problem with (1), but it made (3) worse. But then I
noticed a bug in the above test: it makes

CubicCurve2D c = new CubicCurve2D.Double(0, 0, -100, 0, -100, 100, 0, 100);
c.contains(-10, 10, 10, 10);

return false when it should return true (because (x+w,y) and (x+w,y+h) are
not part of the rectangle). BTW, is this really a bug, or am I wrong
somewhere? If yes, should we file it? I replaced that test with 

        if (!getBounds2D().contains(x, y, w, h)) {
        	return false;
        }

and that fixed both the bug and the performance of (1) without making
(3) worse. Actually, (1) is faster with the above line because
rectangle-rectangle containment is faster than 4 calls of
CubicCurve2D.contains(Point). I made a separate webrev for this:
http://icedtea.classpath.org/~dlila/webrevs/containsFix/webrev/
because it's a separate bug from the intersects() problems.
One more thing: I used your suggestion of replacing
rectCrossings(getPath().getIterator()) with a utility method and cases
(2) and (3) became 2 and 4 times faster. I'm not sure if it's because we're
saving the object creations and gc or because of possibly earlier
short circuiting (because unlike rectCrossingsForPath I'm calling
rectCrossingsForLine(x1, y1, x2, y2) first, then I call
rectCrossingsForCubic(x2, y2, x2c, y2c, x1c, y1c, x1, y1)), but I guess
it doesn't matter.


intersects():
The news here isn't as good. I can make (1) not be any worse compared to
the version that uses solveCubic (by doing cheap tests and returning false
early), but (2) and (3) have become about 4-6 times slower.
I'm still working on this.

> BTW, I would replace rectCrossings(getPath().getIterator()) with a
> utility function that calls the rectCrossingsForLine/Cubic() methods
> directly for the 2 elements of the path. (Remember to check if
> crossings is RECT_INTERSECTS after the first call as that is a
> short-circuit answer.)

That's a good idea.

Thank you,
Denis.