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

[Jim Graham]

Hi Denis,

On 1/12/2011 2:33 PM, Denis Lila wrote:
> Hi Jim.
>
>> 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.
>
> It turns out that that test actually slows it down a bit. It was helping
> us when we were using the PathIterator, but after the introduction of
> the rectCrossings method you suggested, it's faster in all cases (even (1))
> to just do the general thing all the time. I've updated the webrev with this.

Great news!  After reading the previous email I was going to ask that 
question, but you've already done the work.

> Eliminating the PathIterator also had a large impact on the intersect(rect)
> method. Now it's about 20% faster in cases (1) and (3). (2) is still slower
> but only by a factor of 2-3. Here's the webrev for it:
> http://icedtea.classpath.org/~dlila/webrevs/intersectsFix/webrev/

I'm not sure how frequently we run into case 2 in practice, and the code 
being simpler and based on a mechanism that has survived testing pretty 
well is a big win.  I'm willing to go with this.  Plus, if we find ways 
to make the Curve methods go faster then it will help a lot of shape types.

Have you used more than one case to test the performance differential, 
or did you find a single case that gave the intended result and then run 
just that one case N times?  If so, then perhaps the performance 
differential is largely an idiosyncrasy of the particular test case?

Either way, I think the existing patch is a good compromise and possibly 
close to being a fairly reliable win depending on what kind of 
performance testing you did.

The following is for further optimization experiments...

> I think the reason (2) is slow is because rectCrossingsForCubic recursively
> searches through subdivisions of the input curve starting at t=0 and
> in increasing t. Do you think it would be worth it to switch the order
> of the recursive calls depending on the distances of the two
> subdivided curves relative to the rectangle (so that perhaps we would get
> to the subdivided curve that crosses one of the rectangle sides sooner)?

Not sure - how would you gauge "distance to the rectangle"?  How about 
this quick test:

if ((y0 <= y1) == (ymid <= ymin)) {
     // Either rightside up and first half is likely a fast rejection
     // or upside down and first half is possibly a reject
     do second half first
} else {
     do first half first
}

Either way, it only saves a few tests for the branch that isn't taken. 
What if we optimized the fast rejection cases (which would make all test 
cases go faster) by trying to do some trivial min/max sharing for the Y 
case rejections.  Minimally if the first Y rejection test finds that y0 
 >= ymax then there is no need to test y0 <= ymin in the second set of 
rejection tests, so the following would cost no more than what we do now:

// Assuming ymin strictly < ymax
if (y0 >= ymax) {
     if (all others >= ymax) {
         return crossings;
     }
     // No need to do ymin testing since the first test would fail
} else if (all <= ymin) {
     return crossings;
}

I'm not sure how many tests it might save in practice, though, but it 
would never cost any more tests (and the compiler can't optimize it away 
since it doesn't understand that we can require ymin<ymax as part of the 
method contract).

Another solution:

if (y0 <= y1) {
     // y0 is above if y1 is above
     // y1 is below if y0 is below
     test y1, yc1 and yc0 above
     test y0, yc0 and yc1 below
} else {
     // reverse assumptions as above
     test y0, yc0 and yc1 above
     test y1, yc1, and yc0 below
}

(Note that it leads off every case above with a test of y0 or y1 since 
those tests are testing 2 rejection points against the rectangle, but 
the yc0 and yc1 tests only test a single point against the rectangle.) 
It only eliminates a total of 1 test, though since you still have to 
test y0 against y1.  You can take it another step further by comparing 
yc0 against yc1:

if (y0 <= y1) {
     // y0 is above if y1 is above
     // y1 is below if y0 is below
     if (yc0 <= yc1) {
         // similar assumptions about yc0,yc1 ordering
         test y1, yc1 above
         test y0, yc0 below
     } else {
         test y1, yc0 above
         test y0, yc1 below
     }
} else {
/* similar */
}

One downside with these "ordering the control points" approaches, 
though, is that the minimum number of tests in the rejection portion may 
go up, even if the max number goes down.  It may simply be trading off 
average for consistency.

Another idea: Once a curve is monotonic in Y then we can do very fast 
rejections.  It might be worth testing for monotonicity (in Y mainly) 
along with the above/below rejections and switch to a faster monotonic 
method when that case occurs:

if (y0 <= yc0 && yc0 <= yc1 && yc1 <= y1) {
     return rectCrossingsForMonotonicCubic(crossings, ...);
} else if (reverse monotonic tests) {
     return 0 - rectCrossingsForMonotonicCubic(0 - crossings,
                                               reverse curve);
}
// Standard y rejection tests...etc

			...jim