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

[Denis Lila]

Hi Jim.

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

Hmm... I think I agree with that. I've removed most of the "final"s.
I left them alone in the declarations of A, B, C, but I think they're
helpful there since they're at the top of a long method and they're
used in a lot of places in that method, so it helps to say they'll never
change.

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

I did some testing and it turns out that the caps are not needed. I have
removed them.

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

Yeah, you're right.

I also added a lot of comments.

Thanks for reviewing,
Denis.

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

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

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