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

[Jim Graham]

On 1/26/2011 7:31 AM, Denis Lila wrote:
>> 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.

It doesn't really affect anything.  I can get used to it, but I'm 
worried that it might raise a "Why did the previous engineer make this 
final?  Is it OK if I have to make it non-final?" maintenance question 
that might make a future bug fixer stumble a little.  It might also 
convey the message to new Java engineers who see this technique that 
their code needs to use final variables for some practical reason.

I'm not going to object to it - I was just curious about it.  I do feel 
like it is unnecessary pomp, but I can see how it might clarify the 
nature of the values.

>> 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)?

I'm happy with that description.  If you think it needs a cap then I can 
go along with that.  One thing, though, if you found root count errors 
with a smaller scale factor, then won't capping the error for larger 
polynomials introduce the same root count errors for them?

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

OK, I see.  I was imagining a parabola-like curve when critCount==1, but 
I can see that with a cubic that would never happen because it must go 
towards +/- infinity at the ends.  It might be worth adding a comment 
that explains how the critCount describes the shape of the curve.  It's 
either a sideways S (critCount==2), or a monotonic curve (critCount==0), 
or a monotonic curve with a single isolated horizontal tangent 
(critCount==1).

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

With my understanding of critCount from above I get it better now.  It 
might also help to add a comment as to why res[0] is goodRoot and why 
you know that without having to vet them.

So, critCount == 2 is the only case that even allows for the second root 
so it is the only case where you will try and save the second root.  For 
all other critCounts you will just ignore the second root since it 
shouldn't typically exist.  I think I get that now, and it would have 
been easier with a few key added comments like above.

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

I'd just add a comment that all we need is the sgn(lim(...)) and the 
coefficient is an excellent approximation (and 0 isn't allowed).

Also, why does critCount==0,1 use bisectRoot but critCount==2 uses 
refineRoot?  A note explaining that might help.

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

1105 should now use P,Q instead of p,q right?

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

Looks good, other than the minor issues above (most of which are 
requests for comments)...

			...jim