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

[Denis Lila]

Hi Jim.

> You make a lot of local variables final - is that for performance?
> Does
> it actually have any impact (I've only ever used final on a local
> variable when it was required for an anonymous inner class to work).

Not really - I just like using final for variables that aren't supposed
to change. I guess it's not as important for local variables as it is
for members, so I can remove them if you want.

> Line 1142 - that's a huge error allowance. Do we really need that
> much?

I think we do. For numbers in (-10, 10) it's not actually that large. It
turns out to be about 1e-9 - 1e-8, which is what the original implementation
of this algorithm had. I spent some time reducing that constant as much as
possible, and this was the lowest I could find that didn't miss any roots.
Still, I am a bit worried about the growth rate of this error allowance for
polynomials with very large coefficients (>100000), so what if I made this
err = min(err, 0.1)?

> Line 1192 - this case ends up returning "1", but can't we enter here
> with 2 roots? "critCount==1" can happen if there are 2 roots, no?
---
> Line 1219 - We can get here if "num == 2, critCount == 1" which means
> we may actually have 2 valid roots, no?

If critCount==1 that means the polynomial looks something like x^3
i.e. it's strictly increasing or decreasing at every point, except one where
it is locally flat, so it can only have 1 root. The reason I do this
is because I trust the accuracy of solveQuadratic much more than the accuracy
of any of the computations we've done, so if solveQuadratic tells me there's
only 1 root, I go with it.

> Line 1206 - I don't understand what this case is trying to accomplish?

It's trying to refine the accuracy of the "bad" root in the num==2 case,
and possibly eliminate it if solveQuadratic says it's not really a root.
This may be stating the obvious, but I'm not sure how to give a better
answer. Could you be a bit more specific?

> Line 1182 - I don't understand why this is -1 or 1, why not solveEqn?
> Or is it because you only care about the sign of the function there?
> Is it really that predictable? Also, what about just using "-eqn[3]" as
> the "sign approximator"? (Not helpful if eqn[3] == 0, but we wouldn't
> be here if that was the case.)

Yeah, we only care about the sign. I do think it's predictable. Much more
so than solveEqn in fact, since that could potentially just return 0 for
very flat polynomials, while eqn[3] will always give the correct sign
of lim{x->+inf}eqn(x). As for why I'm using 1 instead of eqn[3]... I'm not
sure. I remember there used to be a good reason, but the way the code is now
it's not there anymore, so I've changed this.

> Line 1104, I though we were going to add a comment that clarified that
> the values we computed were actually p/3 and q/2.
---
> Line 1123 - it has no bearing on the correctness, but logically I
> think
> this would read better as "eqn = Arrays.copyOf(eqn, 4)" since it is
> "saving eqn", but the way you wrote it looks like it is "saving res"
> (which happens to == eqn).
---
> Line 1131 - {}
---
> Lines 1178 - 1180 - only used inside "num == 3" case?
> Lines 1182,1183 - only used in "num == 3, critcount == 1" case?
---
> Line 1386 - It looks like you moved this function from below which
> just generates some unnecessary diffs - is there a reason for that?
---
> Line 1283 - move this just inside the while? (And eliminate 1295?)
---
> Line 1230 - could be declared on line 1233?

Done.

> Line 1340 - M += 1 + ulp(M) would save a max operation and work as
> well, wouldn't it?

Good point.

> Line 1179 - isn't that already done in getRUB()? (And see my comment
> about eliminating the "max()")

Yeah. This is a leftover from when I used to compute RUB inline.

The URL is the same:
http://icedtea.classpath.org/~dlila/webrevs/cc2d/webrev/

Regards,
Denis.

----- Original Message -----
> Hi Denis,

> ...jim
> 
> On 1/25/2011 3:45 PM, Denis Lila wrote:
> >>  From that email on we started diving into the containment methods
> >> instead of solveCubic and the email you refer to doesn't have a
> >> webrev
> >> link to the code with your changes. Is there a final webrev for the
> >> solveCubic changes?
> >
> > I made a webrev, along with 3 regression tests (2 for my previous 2
> > pushes
> > and one for solveCubic):
> > http://icedtea.classpath.org/~dlila/webrevs/cc2d/webrev/
> >
> > The regression test for solveCubic just tests the equation {0, 0, 1,
> > 1}
> > for which we used to find only 1 root. I thought about including a
> > randomized stress test based your trySolve method that you sent a
> > while
> > ago, but I'm not a big fan of regression tests that have a small
> > chance of
> > failing even when nothing is wrong. What do you think about this?
> >
> > Regards,
> > Denis.