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

[Jim Graham]

Thanks Denis,

The code changes look good to go.  As for regression test...

I'm guessing there is no regression test for this as it is entirely 
performance.  If this fixes any quality or correctness bugs it would be 
nice to develop an automated test case to go back with it, but if it is 
just performance then they don't usually have tests...

			...jim

On 2/3/2011 5:13 PM, Denis Lila wrote:
> Hi Jim.
>
>> breakPtsAtTs - [whine]I sort of feel as if this method is trying to
>> abstract something that is not really that bad to just do inline and
>> in
>> trying to apply the abstraction it might make the calling code
>> slightly
>> simpler, but it created a mess here by trying to shoehorn a natural
>> inline process into an "Iterator" paradigm. :-( [/whine] Having said
>> that, the new changes to this look good. ;-)
>
> I agree that the complexity of the abstraction is higher than what it saves
> in the calling code (but I also think it makes the calling code more than
> slightly simpler since it saves us one or two local variables in the caller).
> The reason I wrote this method was because I was hoping to perhaps use it in
> Dasher too (like I describe in the TODO), and I think I was using it in some
> other place at the time. Now the only calling function is in Stroker, so I
> could inline it if you want, but I'm not too eager to do that, because what
> we have works, and we wouldn't gain much from inlining.
>
>> LengthIterator comment - any reason to delete it? Too hard to keep it
>> up to date?
>
> I reintroduced it. I don't even remember deleting it, or why I did so :/
>
>> line 342 - 0/0 == NaN which fails all tests, but should be considered
>> to
>> have low acceleration, no? Also, what about the test:
>> within(len1, len2, len2*err)
>> would that have similar properties? The only advantage here is that
>> multiplies are usually faster than divides.
>
> They are equivalent. I'm using your version now. This also fixes the 0/0
> problem.
>
>> line 176 and 183-186 - does Math.scalb() go faster for these?
>
> scalb is slightly slower on my machine (by about 5%).
>
>> line 190 - what happened to the adjustment that used to be at line 359
>> (i.e. dx,dy greater than INC_BND)? Did it not save very many lines in
>> the output?
>
> I eliminated it because of how the dx and ddx values change for quadratic
> curves. I don't remember exactly what was going on, but one of them stays
> constant so every test had the same outcome and was therefore a waste.
> A better explanation can be found in ProcesPath.c (which is one of the
> palces from where I got the algorithm).
>
>> line 80 - technically "ecur>= 0" would work as well and would
>> probably
>> be cheaper on most architectures if the condition codes are already
>> set
>> by the fetch - if not then comparing to 0 is usually cheaper than
>> comparing to a number. Though, I prefer using 0 as the terminator
>> since
>> it doesn't require an Arrays.fill() (though it does require biasing
>> the
>> stored indices by +1 so that they aren't null which may offset some of
>> the array fill savings).
>
> I didn't implement this because of your last point. I could, if you
> think the benefits would definitely be worth it.
>
> I've implemented all your other suggestions.
>
> Thank you,
> Denis.
>
> ----- Original Message -----
>> Hi Denis,
>>
>> Curve.java
>>
>> line 242 - remove "both"
>>
>
>>
>> Dasher.java
>>
>>
>
>>
>> line 385 - cache the "haveLowAccel" return value until the curve is
>> redivided?
>>
>> caching flatLeafCoef - If you add cache[3] and save the value to
>> muliply
>> by t (either -z or -y) then you wouldn't need to recalculate x,y,z
>> every
>> time:
>> if (cache[2]<  0) {
>> float x = ..., y = ...;
>> if (type == 8) {
>> float z = ...;
>> cache[0..2] = ...;
>> cache[3] = -z;
>> } else {
>> cache[0..2] = ...;
>> cache[3] = -y;
>> }
>> }
>> float a=...;
>> float b=...;
>> float c=...;
>> float d=t*...;
>>
>> Helpers.java
>>
>> line 147 {}
>>
>> PiscesRE.java
>>
>> lines 286,288 - (dog whimpers) I noticed that the two lines you've
>> modified are the only 2 lines in the comment that have apostrophes
>> that
>> my gnuemacs is allergic to. Any chance you'd get rid of them for me?
>> ;-)
>>
>> Renderer.java
>>
>
>>
>> line 87 - should this be commented out at some point?
>>
>> line 135 - "NEXT and OR" and "indices"
>>
>
>>
>> line 188 - it might look cleaner to just declare these inside the loop
>> and add them from x0,y0 rather than +=. I'm not sure if it will make a
>> difference in performance, though, given the vagaries of FPU
>> scheduling.
>>
>
>>
>> line 286 - in my version I moved the calculation of slope up above
>> here
>> and just used the sign of the slope as the test for x ordering. Note
>> that if the slope calculations immediately precedes the "if (slope<
>> 0)"
>> test then the condition codes are likely already set as a side effect
>> of
>> the previous operation. I also just put the "edgeMinMaxX" tests in the
>> two halves of the "if" statement and avoided the need for the extra
>> minX,maxX variables, though with a slight duplication of code.
>>
>> line 442 - the code actually adds "2"
>>
>> line 480 - interesting math trick which avoids a conditional:
>> crorientation = ((curxo&  0x1)<<  1) - 1;
>>
>> ...jim
>>
>> On 2/1/2011 6:16 PM, Denis Lila wrote:
>>> Ah, I'm sorry. I forgot to CC the list.
>>>
>>> ----- Forwarded Message -----
>>> From: "Denis Lila"<dlila at redhat.com>
>>> To: "Jim Graham"<james.graham at oracle.com>
>>> Sent: Tuesday, February 1, 2011 6:04:09 PM
>>> Subject: Re: [OpenJDK 2D-Dev] CubicCurve2D.solveCubic and
>>> containment/intersection bugs.
>>>
>>> Hi Jim.
>>>
>>> The webrev for the performance improvement is here:
>>> http://icedtea.classpath.org/~dlila/webrevs/perfWebrev/webrev/
>>>
>>> I have changed a few things since the last time you looked at it.
>>> The largest change is in Curve.java in breakPtsAtTs. I changed its
>>> return
>>> from an Iterator<float[]>  to an Iterator<Integer>, which allowed me
>>> to
>>> change middle in Stroker from a float[2][8] to a float[16]. I also
>>> eliminated the call to updateTs and the bouncing back and forth of
>>> the
>>> subdivided curves in breakPtsAtTs.
>>>
>>> The other major change is the implementation of the cubic solver in
>>> Helpers.java (which is used in Dasher.LengthIterator). It's almost
>>> identical to what I just commited to awt.geom.CubicCurve2D. I'm not
>>> using the version in awt.geom because I want to avoid the array
>>> creations
>>> but most importantly because we don't need anything even close to
>>> the
>>> accuracy that CubicCurve2D provides. In fact, most of the time*,
>>> LengthIterator's arguments to solveCubic are such that there is only
>>> one solution, so I considered removing the 2 root case altogether
>>> just
>>> to skip the within(D, 0, 1e-8) call (I haven't done this yet because
>>> I wanted to check with you first).
>>>
>>> * "most of the time" is a bit of an understatement. I've tested this
>>> with
>>> tens of thousands of Dasher.curveTo calls, and I've never seen a
>>> case
>>> where there is more than one root.
>>>
>>> Regards,
>>> Denis.
>>>
>>> ----- Original Message -----
>>>> Actually, if you just want to type up a quick "description" I'll
>>>> file
>>>> the bug...
>>>>
>>>> ...jim
>>>>
>>>> On 1/27/2011 2:26 PM, Jim Graham wrote:
>>>>> On 1/27/2011 2:03 PM, Denis Lila wrote:
>>>>>> Well, it is pushed. Now all that's left on my end is the
>>>>>> performance
>>>>>> improvement for pisces (dashing in particular). Could you please
>>>>>> file
>>>>>> a performance regression bug for it?
>>>>>
>>>>> What are we regressing from? Is it slower than the previous
>>>>> OpenJDK
>>>>> rasterizer?