[prev in list] [next in list] [prev in thread] [next in thread] 

List:       openjdk-2d-dev
Subject:    [OpenJDK 2D-Dev] X11 uniform scaled wide lines and dashed lines; STROKE_CONTROL in Pisces
From:       dlila () redhat ! com (Denis Lila)
Date:       2010-08-31 22:13:58
Message-ID: 979263116.3886571283292838724.JavaMail.root () zmail04 ! collab ! prod ! int ! phx2 ! redhat ! com
[Download RAW message or body]

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

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
-------------- next part --------------
A non-text attachment was scrubbed...
Name: Stroker.java
Type: text/x-java
Size: 41611 bytes
Desc: not available
Url : http://mail.openjdk.java.net/pipermail/2d-dev/attachments/20100831/ae847c81/attachment-0001.bin 

[prev in list] [next in list] [prev in thread] [next in thread]