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
