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

Denis Lila dlila at redhat.com
Wed Sep 1 14:51:51 PDT 2010

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

```