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

[Denis Lila]

Hi Jim.

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

For case (1) I call contains/intersects on 2x2 rectangles that
are outside of the bounding box of the curve. For (2) I created
N 2x2 rectangles with their top lefts on the curve. (3) was like
(1) but with the rectangles inside the curve. I always used the
same curve: (0, 0, 0, 1000, 1000, 1000, 1000, 0) so the rectangles
were extremely small compared to the curve. Changing the size of
the rectangles improved the performance for (2) by about 50%, since
fewer subdivisions had to be made to find that some point of the
curve was inside the rectangle.

I also wrote another test ({intersect,contain}sBigTest) that tests
both correctness and performance. It does the former by creating an
Area(CubicCurve2D) object and using the results of its
contains/intersects methods as reference results. Like the above tests
it uses a fixed curve for every call, but the rectangles have random dimensions
and positions. On 10000000 rectangles, the intersection version of this
test runs in about 8 seconds using the old intersects algorithm, and 1.4s
using the new one. Even better, this test finds disagreements between
the old CubicCurve2D.intersects and Area.intersects, but not between
the new CubicCurve2D.intersects and Area.intersects.
This is very good. Almost too good, which is why I've attached the file
with the tests.

I have yet to think about the optimizations, so I'll send an e-mail later
about those.

Regards,
Denis.

----- Original Message -----
> 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/
> 

> 
> 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
-------------- next part --------------
A non-text attachment was scrubbed...
Name: CubicSolver.java
Type: text/x-java
Size: 33672 bytes
Desc: not available
URL: <http://mail.openjdk.java.net/pipermail/2d-dev/attachments/20110113/fb9db78e/CubicSolver.java>