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

[Denis Lila]

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?