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

[Jim Graham]

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

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

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