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:
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
