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

[Jim Graham]

Whoops, one last optimization:

Line 1161 - "num > 1"?

One last suggestion:

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

A couple final comments:

Line 1173 - add "num > 1"?

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

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