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

[Denis Lila]

> Line 1161 - "num > 1"?

Done.
Can the compiler take care of this sort of thing? It should be able to
figure out that the only possible values for num are {0, 1, 2, 3}.

> Line 1271 - if the vals are opposite sign, is it worth bisectRoot'ing?

Do you mean if badRootVal and fx are of opposite signs?
I don't think bisectRoot would be good here. It is far slower than what we
have, and in terms of accuracy we wouldn't really gain much because in
the two root case the polynomial is very flat at the second root and
evaluating solveEqn(eqn, 3, x), where x is all the doubles near the second
root, shows that the computed values change sign many, many times. BisectRoot
finds a root in an interval where the function is known to be monotonic and
has opposite signs at the end points. Monotonicity doesn't hold in this case,
so all bisectRoot would do is look for values in the interval where
solveEqn returns exactly 0, but that's not really any better than a random
sampling of the interval in the 2 root case.

> Line 1173 - add "num > 1"?

Ok.

> Line 1251 - a referring comment should be added to line 1154 and/or
> 1157
> otherwise someone might change the dependent code and not know that
> other code depends on it.
> 
> Line 1382 - Might want to at least include your OpenJDK username as
> reference so we know who we are trusting... ;-) (I suppose they can
> find it in change logs, but that takes some effort and might be
> eliminated if we ever change to a new revision system.)

Done.

> Oh, and I just looked at the tests now and they look good too...

Is it good to go now?

Thank you,
Denis.

----- Original Message -----
> Whoops, one last optimization:
> 

> 
> One last suggestion:
> 

> 
> A couple final comments:
> 

> 

> 
> ...jim
> 
> On 1/26/2011 12:29 PM, Denis Lila wrote:
> > 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