[OpenJDK 2D-Dev] X11 uniform scaled wide lines and dashed lines; STROKE_CONTROL in Pisces

Denis Lila dlila at redhat.com
Thu Sep 2 21:43:01 UTC 2010


Hello Jim.

> Either way, hopefully the performance is much better now that the 
> dashing and widening code has to process a lot fewer segments.  Is
> it?

In some cases, it's as much as 20x better. I wrote a small program to
draw extremely high numbers of random curves, so that I could test 
performance, and notice obvious mistakes. This function split a 
1000x1000 frame in 100 100x100 squares drew 20 random curves in each of them.
I set a stroke with line width = 2, so that pisces would get used. The 
operation took about 18-20 seconds per frame on my machine. Then I tried
a very early version of this changeset (the one where the subdivisions were
uniformly spaced, with 5 curves per side), and it took less than 2 seconds.

That algorithm was faster, so we can't expect the same gains with the current
version (which is actually correct (I think)), but after we do some optimizations
it should be close.

Actually, I had a question about the test I wrote which takes 20 seconds. When
I turned antialiasing on, the test dropped from 20 seconds to 2.5. This is very
puzzling, since antialiasing is a generalization of non-antialiased rendering
(a generalization where we pretend there are 64 times more pixels than there
actually are). Of course, the paths followed after pisces for AA and non-AA are
completely different, but whatever came after pisces in the non-AA case would
have the same input as Renderer has in the AA case (input gotten from Stroker).
Can you take a guess as to what was causing such a large difference?

> Are quarter circles easy to detect?  Their 2 angles should both be 45 
> degrees and their lengths should be similar (I don't think the middle 
> control segment is the same length as the outer 2, but there is probably 
> some tolerance where a single subdivision works fine).

What I'm doing now is that for every curve, I rotate it so that p2-p1 is 
parallel to the x-axis. So if the curve was a quarter circle, after the
rotation it should be monotonic in both x and y. This is similar to
detecting quarter circles by looking at the angles, but it's more general.
And, I think, it has the same numerical problems. Because of this, I don't
think we should treat them as a special case.
But anyway, this isn't a big deal. My main concern with ignoring dx/dt and
dy/dt roots outside of (0.001,0.999) was a stylistic one, but it won't
really affect correctness much. The worst that can happen is that a curve
that bends a tiny bit more than 90 degrees will be widened by 1 curve, 
instead of 2, which is what we would like.

Regards,
Denis.

----- "Jim Graham" <james.graham at oracle.com> wrote:
> 			...jim
> 
> On 9/2/2010 7:08 AM, Denis Lila wrote:
> > Hello Jim.
> >
> > Sorry for all the e-mails.
> > I implemented the rotating version. The rotation introduces small
> > numerical errors, so when I solve for the roots of dx/dt and dy/dt,
> > the values of t I get are slightly off. So for a rotated quarter
> > circle, what happens is that it gives me a root at, say,
> t=0.9996...
> > so I still end up subdividing quarter circles. I "fixed" this by
> > ignoring all roots outside of (0.001,0.999), instead of ignoring
> > roots outside of (0,1) which is the ideal solution. I don't like
> > hardcoding constants like this. Add to this the higher complexity
> > of the rotation, and I'm tempted to say it might be better to just
> > bite the bullet on rotated quarter circles and widen them using 2
> > curves per side.
> >
> > I had one question: what do you think of widening all curves using
> > quadratic curves? Their great simplicity might make things safer.
> We
> > can guarantee that none of the strange behaviour I've seen and
> described
> > with cubic curves will arise (but we'd have to use more of them).
> >
> > Also, I've tested the current implementation with a few hundred
> random
> > cubic paths, and everything looks good so far.
> >
> > Thanks,
> > Denis.
> >
> > ----- "Denis Lila"<dlila at redhat.com>  wrote:
> >
> >> Hello Jim.
> >>
> >>> I think this would actually ensure that every resulting curve can
> >>> be rotated to be made monotonic in both x and y (at least after
> >>> inflections are eliminated), which means it's at least as good as
> >>> what I have now.
> >>
> >> While that first statement is true, it unfortunately does not mean
> >> it's
> >> "at least as good as" breaking the curve into monotonic pieces. I
> >> implemented the angle checking method, and the problem is that for
> >> curves like (0,0),(1000,1),(-1000,1),(0,0) it is very bad. That's
> >> because I implemented it by subdividing at t=0.5, so the angles
> >> in the resulting curves' polygons are still wide. After enough
> >> subdivisions the polygons would have angles below 45, but that
> would
> >> defeat the point, since we're trying to minimize the number of
> output
> >> curves.
> >> I can't think of a good way to chose the subdivision t so that
> >> this method is as good as the rotation and make monotonic one
> (nothing
> >> with any properties I can prove, anyway), so I'll implement the
> >> rotating version, as much as I don't like it. At least it gives a
> good
> >> upper bound in the number of output curves.
> >>
> >> Regards,
> >> Denis.
> >>
> >> ----- "Denis Lila"<dlila at redhat.com>  wrote:
> >>
> >>> Hello Jim.
> >>> Thanks for taking the time to think about this.
> >>>
> >>> I implemented a few different offsetting schemes. On well behaved
> >>> curves, my original "parallel first and last control vectors and
> go
> >>> through B(0.5)" algorithm was by far the best. Theoretically it
> is
> >>> also somewhat better justified than the others (some of which
> were
> >>> like Apache Harmony's way - offsetting p2 and p3), since we're
> >>> interpolating instead of just using some heuristic. It is also
> >>> the only one I've encountered that widens quarter circles
> optimally,
> >>> and it only needs one curve per side too (i.e. if we have to
> widen
> >>> the path of a PathIterator of a circle with radius r, using width
> w,
> >>> Pisces' output will be identical to the output of the
> PathIterators
> >>> of 2 circles with radii r+w and r-w (perhaps not identical
> >> identical,
> >>> since PathIterators can use doubles, and we only use floats in
> >> pisces,
> >>> but... that's nitpicking)).
> >>>
> >>> As I've said before, the only 2 problems with it were that it was
> >> bad
> >>> on high curvatures (but this was fixed by breaking down the
> curves
> >>> into
> >>> monotonic ones), and it was bad on curves like
> >>> p.moveTo(0,0);p.curveTo(100,100,0,100,100,1). I thought the
> latter
> >> was
> >>> fixable with the "d1/(d1+d2)" algorithm I suggested in my
> previous
> >>> e-mail.
> >>> I implemented it, and it turns out I was wrong. Then I came up
> with
> >> my
> >>> own
> >>> variation of that algorithm (the original one I used was from Don
> >>> Lancaster's
> >>> website) that did sort of work. But then I implemented your
> >> suggestion
> >>> of
> >>> splitting the curve at the inflection points as well as breaking
> it
> >>> into
> >>> monotonic pieces, and the problem was gone. I didn't even have to
> >> use
> >>> the
> >>> fancy variation of the "d1/(d1 + d2)" algorithm - just the plain
> old
> >>> interpolation one worked (I should say that the fancy one is
> still
> >>> probably
> >>> better, but undetectably so, now that we break at inflection
> points
> >>> and at
> >>> xy direction changes, so the added complexity is probably not
> worth
> >>> it).
> >>>
> >>> I've attached my latest Stroker.java, if you want to take a look
> at
> >>> these
> >>> algorithms (they're in computeOffsetWay1 (for the old
> interpolation)
> >>> and
> >>> computeOffsetWay3 (for the fancy version). There are 2 more, but
> >> these
> >>> aren't as good, and one is just shameful). I didn't make a webrev
> >>> because
> >>> I still need to fix how it handles cusps (which should be easy),
> and
> >> I
> >>> need to implement a way to avoid subdividing a rotated quarter
> >> circle.
> >>> I can do this either by rotating curves so that p2-p1 is parallel
> to
> >>> the
> >>> x axis and then subdivide like I do now (i.e. make monotonic,
> break
> >> at
> >>> inflections) or get rid of the monotonic subdivision, and instead
> >>> subdivide
> >>> by checking the angles of the control polygon. I could make it so
> it
> >>> subdivides whenever the angles between p2-p1 and p3-p2 or p3-p2
> and
> >>> p4-p3
> >>> are greater than 45 degrees.
> >>>
> >>> Very well. I've convinced myself. I'll implement the latter.
> >>>
> >>> Thanks,
> >>> Denis.
> >>>
> >>> ----- "Jim Graham"<james.graham at oracle.com>  wrote:
> >>>
> >>>> Hi Denis,
> >>>>
> >>>> Just to let you know that I've seen this and I'm thinking.
> >>>>
> >>>> But it will take a bit of "more thinking" when I have time for
> >> more.
> >>>> Hopefully in a couple of days.
> >>>>
> >>>> For one thing, it sounds like you already understand the Apache
> >>>> Harmony
> >>>> approach quite a bit better than I ever did and, in particular,
> >> why
> >>> it
> >>>>
> >>>> didn't work well - which is encouraging.  Hopefully your
> solution
> >>> will
> >>>>
> >>>> sound pretty good when I get around to wrapping my head around
> >> it...
> >>>>
> >>>> 			...jim
> >>>>
> >>>> On 8/30/2010 3:03 PM, Denis Lila wrote:
> >>>>> Hello Jim.
> >>>>>
> >>>>>> One way in which they may not break enough is that I think
> that
> >>>>>> inflections also need to be broken in order to find a parallel
> >>>> curve
> >>>>>> (though I suppose a very tiny inflection might still be
> >>>> approximated by
> >>>>>> a parallel curve easily) and inflections can happen at any
> >> angle
> >>>> without
> >>>>>> going horizontal or vertical.
> >>>>>
> >>>>>       It wouldn't be hard to add additional breaks at the
> >>> inflection
> >>>> points.
> >>>>>
> >>>>>> Secondly, although a circle tends to be represented by
> quadrant
> >>>> sections
> >>>>>> which are monotonic, a circle rotated by 45 degrees would have
> >>>>>> horizontal and vertical sections in the middle of each
> quadrant
> >>> and
> >>>> you
> >>>>>> would split those, but really they can be made parallel
> >>> regardless
> >>>> of
> >>>>>> angle so these would be unnecessary splits.
> >>>>>
> >>>>>       That's true, and it's one reason I didn't like my method
> >> very
> >>>> much when I sent
> >>>>> my previous e-mail. However, what if we rotated curves so that
> >>> B'(0)
> >>>> is
> >>>>> parallel to the x-axis before splitting at points where dx/dt
> or
> >>>> dy/dt are 0?
> >>>>> This would certainly get rid of this problem for circles, and
> >>>> probably for
> >>>>> other curves. All it would cost is 1 Math.cos and 1 Math.sin
> and
> >> a
> >>>> few
> >>>>> multiplications and additions per curve.
> >>>>>
> >>>>> The biggest problem with my implementation was that some curves
> >>> that
> >>>> were almost
> >>>>> lines were drawn horribly. I computed the parallel (p1', p2',
> >> p3',
> >>>> p4') of
> >>>>> a given curve (p1, p2, p3, p4) by making p2'-p1' parallel to
> >>> p2-p1,
> >>>>> making p4'-p3' parallel to p4-p3. This leaves a 2 unknowns, so
> >> to
> >>>> get 2 more
> >>>>> equations I made the computed parallel at t=0.5 equal to the
> >> ideal
> >>>> parallel
> >>>>> at t=0.5. The problem was that for some curves (ones with very
> >>> high
> >>>> curvature)
> >>>>> p2'-p1' and p4'-p3' were parallel to p2-p1 and p4-p3 but their
> >>>> directions were
> >>>>> opposite, so you can imagine what the computed "parallel"
> looked
> >>>> like.
> >>>>> However, I am almost certain that the problem was caused by
> >> making
> >>>> C(0.5) = P(0.5)
> >>>>> (where C is the computed curve, and P is the ideal parallel). A
> >>> much
> >>>> better
> >>>>> restriction, that I think would eliminate the problem would be
> >>>> C(d1/(d1 + d2)) = P(0.5).
> >>>>> where d1 = ||P(0.5)-P(0)|| and d2 = ||P(1)-P(0.5)||.
> >>>>>
> >>>>>> My belief is that lengths and angles of the control polygon
> >> help
> >>>>>> determine if it is well-behaved and can be made parallel
> simply
> >>> by
> >>>>>> offsetting.  Some formula involving those values would likely
> >> be
> >>>> happy
> >>>>>> with circle sections regardless of their angle of rotation.  I
> >>>> believe
> >>>>>> the Apache Harmony version of BasicStroke used those
> >> criteria...
> >>>>>
> >>>>>       I've been reading the Apache Harmony file. The way they
> do
> >> it
> >>>> is compute
> >>>>> the tangent of an angle using the line width and a predefined
> >>>> constant
> >>>>> (which doesn't seem to be related to the curve's polygon - it's
> >>> just
> >>>> a decreasing
> >>>>> function with the range (-1,1)), and if some angles in the
> >> polygon
> >>>> are smaller than
> >>>>> the computed angle, offset curves are computed. Otherwise the
> >>> curve
> >>>> is subdivided.
> >>>>> However, I can't understand how offsets for the control points
> >> are
> >>>> computed (i.e.
> >>>>> why they use the equations they use, and why they work).
> >>>>> If we're using the widening of quarter circles as a yard stick,
> >>> then
> >>>> Apache Harmony's
> >>>>> BasicStroke does not do very well. If we have a quarter circle
> >>> from
> >>>> (1,0) to (0,1),
> >>>>> then the control points c1 and c2 should be (1,k) and (k,1)
> >> where
> >>> k
> >>>> = 4*(sqrt(2)-1)/3.
> >>>>> A parallel curve w away from this quarter circle should have
> >>> control
> >>>> points
> >>>>> (1+w,k+k*w) and (k+k*w,1+w). I traced Apache Harmony's
> >>> computations
> >>>> on a quarter
> >>>>> circle, and this is not what it outputs. Furthermore, all
> >> quarter
> >>>> circles with line
> >>>>> width<   9.65 will be subdivided. My method with the
> >> modifications
> >>>> suggested above
> >>>>> doesn't have these problems.
> >>>>>
> >>>>>       But perhaps it's better to not interpolate through P(0.5)
> >>> after
> >>>> all.
> >>>>> In addition to making p4'-p3' and p2'-p1' parallel to p4-p3 and
> >>>> p2-p1, we could
> >>>>> also make p3'-p2' parallel to p3-p2. These constraints leave
> >> just
> >>>> one unknown, which
> >>>>> needs to be eliminated. I am not sure how to do this. I thought
> >>>> about making the line
> >>>>> (p2',p3') be a distance of w from (p2,p3) (which is exactly
> what
> >>>> needs to be done for
> >>>>> (p1',p2') and (p3',p4')) but this doesn't get us what we want
> >> for
> >>>> quarter circles. So, finding
> >>>>> the control points would boil down to finding intersections of
> 3
> >>>> lines.
> >>>>>
> >>>>> Do you have any suggestions on how to do the offsetting for the
> >>>> control points?
> >>>>>
> >>>>> Thank you,
> >>>>> Denis.
> >>>>>
> >>>>> ----- "Jim Graham"<james.graham at oracle.com>   wrote:
> >>>>>
> >>>>>> Hi Denis,
> >>>>>>
> >>>>>> At the bottom-most rendering level monotonic curves can be
> cool
> >>> to
> >>>> deal
> >>>>>> with, but I'm dubious that they help with widening.  For one
> >>>> things, I
> >>>>>> think you need more breaks than they would give you and also
> >> they
> >>>> might
> >>>>>> sometimes break a curve when it doesn't need it.
> >>>>>>
> >>>>>> 		...jim
> >>>>>>
> >>>>>> On 8/25/2010 2:36 PM, Denis Lila wrote:
> >>>>>>> Hello Jim.
> >>>>>>>
> >>>>>>>> I think a more dynamic approach that looked at how "regular"
> >>> the
> >>>>>> curve
> >>>>>>>> was would do better.  Regular is hard to define, but for
> >>>> instance
> >>>>>> a
> >>>>>>>> bezier section of a circle could have parallel curves
> >> computed
> >>>>>> very
> >>>>>>>> easily without having to flatten or subdivide further.
> >> Curves
> >>>>>> with
> >>>>>>>> inflections probably require subdividing to get an accurate
> >>>>>> parallel
> >>>>>>>> curve.
> >>>>>>>
> >>>>>>> I'm not sure if you read it, but after the email with the
> >> webrev
> >>>>>> link
> >>>>>>> I sent another describing a different method of widening:
> >> split
> >>>> the
> >>>>>>> curve at every t where dx/dt == 0 and dy/dt == 0. This
> >>> guarantees
> >>>>>> that
> >>>>>>> there will be no more than 5 curves per side, and since each
> >>>> curve
> >>>>>> will
> >>>>>>> be monotonic in both x and y the curve that interpolates its
> >>>>>> parallel
> >>>>>>> should do a pretty good job.
> >>>>>>>
> >>>>>>> This is far better than interpolating at regular t intervals,
> >>> but
> >>>>>> I'm
> >>>>>>> trying to find a better way. I don't like this because the
> >> split
> >>>>>>> depend not only on the curve itself, but also on the axes.
> The
> >>>> axes
> >>>>>> are
> >>>>>>> arbitrary, so this is not good. For example a curve like this
> >>>>>>> |
> >>>>>>> \_ would get widened by 1 curve per side (which is good and
> >>>>>> optimal), but
> >>>>>>> if we rotate this curve by, say, 30 degrees it would be
> >> widened
> >>> by
> >>>> 2
> >>>>>> curves
> >>>>>>> per side.
> >>>>>>> It also doesn't handle cusps and locations of high curvature
> >>> very
> >>>>>> well (although
> >>>>>>> I think the latter is a numerical issue that could be made
> >>> better
> >>>> by
> >>>>>> using
> >>>>>>> doubles).
> >>>>>>>
> >>>>>>> Regards,
> >>>>>>> Denis.
> >>>>>>>
> >>>>>>> ----- "Jim Graham"<james.graham at oracle.com>    wrote:
> >>>>>>>
> >>>>>>>> Hi Denis,
> >>>>>>>>
> >>>>>>>> On 8/23/2010 4:18 PM, Denis Lila wrote:
> >>>>>>>>>         To widen cubic curves, I use a cubic spline with a
> >>> fixed
> >>>>>> number
> >>>>>>>> of curves for
> >>>>>>>>> each curve to be widened. This was meant to be temporary,
> >>> until
> >>>> I
> >>>>>>>> could find a
> >>>>>>>>> better algorithm for determining the number of curves in
> the
> >>>>>> spline,
> >>>>>>>> but I
> >>>>>>>>> discovered today that that won't do it.
> >>>>>>>>>         For example, the curve
> p.moveTo(0,0),p.curveTo(84.0,
> >>>> 62.0,
> >>>>>>>> 32.0, 34.0, 28.0, 5.0)
> >>>>>>>>> looks bad all the way up to ~200 curves. Obviously, this is
> >>>>>>>> unacceptable.
> >>>>>>>>>
> >>>>>>>>> It would be great if anyone has any better ideas for how to
> >> go
> >>>>>> about
> >>>>>>>> this.
> >>>>>>>>> To me it seems like the problem is that in the webrev I
> chop
> >>> up
> >>>>>> the
> >>>>>>>> curve to be
> >>>>>>>>> interpolated at equal intervals of the parameter.
> >>>>>>>
> >>>>>>>>
> >>>>>>>> Perhaps looking at the rate of change of the slope (2nd
> >> and/or
> >>>> 3rd
> >>>>>>>> derivatives) would help to figure out when a given section
> of
> >>>>>> curve
> >>>>>>>> can
> >>>>>>>> be approximated with a parallel version?
> >>>>>>>>
> >>>>>>>> I believe that the BasicStroke class of Apache Harmony
> >> returns
> >>>>>> widened
> >>>>>>>>
> >>>>>>>> curves, but when I tested it it produced a lot more curves
> >> than
> >>>>>> Ductus
> >>>>>>>>
> >>>>>>>> (still, probably a lot less than the lines that would be
> >>>> produced
> >>>>>> by
> >>>>>>>> flattening) and it had some numerical problems.  In the end
> I
> >>>>>> decided
> >>>>>>>> to
> >>>>>>>> leave our Ductus stuff in there until someone could come up
> >>> with
> >>>> a
> >>>>>>>> more
> >>>>>>>> reliable Open Source replacement, but hopefully that code is
> >>>> close
> >>>>>>>> enough to be massaged into working order.
> >>>>>>>>
> >>>>>>>> You can search the internet for "parallel curves" and find
> >> lots
> >>>> of
> >>>>>>>> literature on the subject.  I briefly looked through the web
> >>>>>> sites,
> >>>>>>>> but
> >>>>>>>> didn't have enough time to remember enough calculus and
> >>>>>> trigonometry
> >>>>>>>> to
> >>>>>>>> garner a solution out of it all with the time that I had.
> >>> Maybe
> >>>>>>>> you'll
> >>>>>>>> have better luck following the algorithms... ;-)
> >>>>>>>>
> >>>>>>>> As far as flattening at the lowest level when doing scanline
> >>>>>>>> conversion,
> >>>>>>>> I like the idea of using forward differencing as it can
> >> create
> >>>> an
> >>>>>>>> algorithm that doesn't require all of the intermediate
> >> storage
> >>>> that
> >>>>>> a
> >>>>>>>>
> >>>>>>>> subdividing flattener requires.  One reference that
> describes
> >>>> the
> >>>>>>>> technique is on Dr. Dobbs site, though I imagine there are
> >> many
> >>>>>>>> others:
> >>>>>>>>
> >>>>>>>>
> >>>>>>
> >>>>
> >>>
> >>
> http://www.drdobbs.com/184403417;jsessionid=O5N5MDJRDMIKHQE1GHOSKH4ATMY32JVN
> >>>>>>>>
> >>>>>>>> You can also look at the code in
> >>>>>>>> src/share/native/sun/java2d/pipe/ProcessPath.c for some
> >>> examples
> >>>>>> of
> >>>>>>>> forward differencing in use (and that code also has similar
> >>>>>> techniques
> >>>>>>>>
> >>>>>>>> to what you did to first chop the path into vertical
> pieces).
> >>>> BUT
> >>>>>>>> (*Nota Bene*), I must warn you that the geometry of the path
> >> is
> >>>>>>>> somewhat
> >>>>>>>> perturbed in that code since it tries to combine "path
> >>>>>> normalization"
> >>>>>>>>
> >>>>>>>> and rasterization into a single process.  It's not rendering
> >>>> pure
> >>>>>>>> geometry, it is rendering tweaked geometry which tries to
> >> make
> >>>>>> non-AA
> >>>>>>>>
> >>>>>>>> circles look round and other such aesthetics-targeted
> >>>> impurities.
> >>>>>>>> While
> >>>>>>>> the code does have good examples of how to set up and
> >> evaluate
> >>>>>> forward
> >>>>>>>>
> >>>>>>>> differencing equations, don't copy too many of the details
> or
> >>>> you
> >>>>>>>> might
> >>>>>>>> end up copying some of the tweaks and the results will look
> >>>>>> strange
> >>>>>>>> under AA.  The Dr. Dobbs article should be your numerical
> >>>>>> reference
> >>>>>>>> and
> >>>>>>>> that reference code a practical, but incompatible,
> example...
> >>>>>>>>
> >>>>>>>> 			...jim



More information about the 2d-dev mailing list