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

[Jim Graham]

Hi Denis,

Curve.java

line 242 - remove "both"

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

Dasher.java

LengthIterator comment - any reason to delete it?  Too hard to keep it 
up to date?

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.

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

line 87 - should this be commented out at some point?

line 135 - "NEXT and OR" and "indices"

line 176 and 183-186 - does Math.scalb() go faster for these?

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

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?