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

[Jim Graham]

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.

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.

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