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

[Jim Graham]

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