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

[Jim Graham]

Hi Denis,

Sorry for being so distracted (on the other hand, it was for JavaOne 
;-), but it looks like you made some incredible progress in the meantime!

On 9/22/2010 2:22 PM, Denis Lila wrote:
> I also ran a 2D graphics test suite: http://icedtea.classpath.org/hg/gfx-test/
> icedtea6 version 1.8, openjdk7 with my patch does much better. The number of
> generated images that are identical to closed java has more than doubled. No

Woohoo!

> I should give a high level overview of how things have changed:
> 1) Antialiasing uses adaptive forward differencing. Now I rasterize each curve
> as soon as I receive it and store the crossings instead of storing curves and computing
> the crossings as needed. This is faster, but not as memory friendly so I'm a bit uneasy
> about this decision. What do you think?

How much faster?  I'm worried about this, especially given our tiled 
approach to requesting the data.  What was the bottleneck before?  (It's 
been a while since I visited the code - we weren't computing the 
crossings for every curve in the path for every tile being generated 
were we?)

> 2) In Dasher.java I implemented the buffer to store initial segments.
> 3) For dashing, I compute curve lengths using the algorithm you told me about.

Cool.  Keep in mind that I never did an exhaustive search for "best way 
to measure curve length" so we may very well find a better algorithm if 
we need to.

> 4) Transforms are handled differently. We used to transform everything before feeding
> it to pisces. Since pisces has to compute offsets, it needed to know about these
> transforms. This made things very confusing. I have introduced a class which Stroker
> and Dasher use for IO that knows about transformations. So, when a shape is being
> rendered its path iterator transforms the points. These transformed points are
> then normalized (if normalization is on). Then they are passed through this IO
> handler which untransforms the points and feeds them to Dasher or Stroker, which
> pass their output through the IO handler again which transforms them. Unfortunately,
> this will do many more transformations than before. The reason I did this is to
> avoid going back and forth between user space and device space coordinates in the
> same file.

I can see your points here.  I think there are solutions to avoid much 
of the untransforming we can consider, but your solution works well so 
let's get it in and then we can look at optimizations if we feel they 
are causing a measurable problem later.

> 5) In stroker, we used to keep variables that stored the previous point (px0,py0)
> and the second point (sx1 and sy1, I think). I eliminated these. They were
> misleading and unnecessary and just don't make sense if we have curves. They were
> misleading because the only way they were ever used was to get tangent vectors at
> the start and current position in the path. I replaced them with variables that
> hold these tangents. This is much clearer and saves us many subtractions. Because
> of this some of the methods parameters have changed. The computeMiter parameters
> are a good example of ones that should have changed but didn't because I didn't
> have time to refactor it. This should be done because if we use vectors it will
> be clearer and will help with 9).

Cool!

> 6) 0 length curves and lines were being ignored. This isn't what proprietary java
> does (which is drawing caps/joins as if a tiny horizontal line going right had
> just been drawn). I "fixed" this to match the behaviour of proprietary java.
> Because of the change above, this turned out to be a 3 liner.

I'm glad these restructuring changes are starting to pay off.  Hopefully 
a lot more tweaks will get easier in the future.

> 7) I put code that draws joins in its own method (drawJoin). This made the close
> and finish methods much clearer and allowed me to fix this createStrokedShape
> issue: http://bugs.openjdk.java.net/show_bug.cgi?id=100046

Saner outlines are a good indication of cleaner internal processes.

> 8) To compute cubic offset curves first I subdivide the original curve at points
> where it starts bending too much (i.e. more than 90 degrees since the last
> subdivision), has inflection points, and where one of the offset curves has
> cusps (see comments in the file for more on this). Finding the offset cusps was
> the main reason for 4, since if we worked with transformed coordinates there
> could be shears and the linewidth would not be constant (we need the line width
> because offset cusps occur when the radius of curvature is equal to the width).
> Then for each of these curves, I find a left offset and a right offset using
> constraints that the curve and the offsets must have parallel tangents at t=0
> and t=1 and that the computed offsets at t=0.5 must be equal to the ideal
> true offsets at t=0.5.

Note that these kinds of heuristics are the kinds of things that people 
could probably create dissertations on, so my hat is off to you. 
Hopefully I'll be able to wrap my head around it without too much trouble.

> 9) To compute quadratic offsets I subdivide as above (except for the inflection
> points, of which there are none). Then for each subdivision I compute the start
> and end point in the obvious manner, and I compute the control point as the
> intersection of the lines that go through the end points and are parallel to
> the tangents at the end points.

I'm not sure I understand the reasoning of the control point 
calculation.  I'll have to look at the code to register an opinion.

> 10) I have included my old patch for drawing round joins using bezier curves.

Yay!

> 11) The side and isCCW methods have changed are are almost exactly the same
> as each other. I still keep them both so that round joins can be drawn in cases
> such as: p.moveTo(x,y);p.lineTo(x+c,y);p.lineTo(x,y). Proprietary java does not
> do this, but I think it should, since joins are meant to join different segments
> in a path. In the example above there are 2 segments, and it is possible to
> draw a round join, so why not? Does the specification say anything about this case?
> I changed the side() algorithm because I think what I use now also works (or at
> least it certainly works for all cases in which we use it), it is faster and
> it is more accurate.

It sounds like you are correct here.  What does the closed source code draw?

> I think the above are all the important changes.
> Some things I wanted to discuss:
> 1. Should I change antialiasing and make it store the curves instead of the crossings?

It's a topic for discussion.  I'm wary of the memory footprint, but I 
don't want to kill performance.  Is it a simple change to switch?  I'm 
also a fan of "get what you have in now as a stake in the ground and 
then deal with some of these issues as follow-on optimizations".

> 2. I'm not completely comfortable with the way special cases are handled in
> the somethingTo, computeOffsetQuad, and computeOffsetCubic methods in Stroker.java
> ("special cases" being very tiny curves).

I'll take a look and report my comfort level too.

> 3. From tests it looks to me like offsets for quads might not be good enough. It's
> barely visible, but I don't know if I'm comfortable with it (fixing this would be
> pretty simple - either add some subdivisions, or approximate quad curves with cubics
> (the latter might be especially nice, since we could use the same code for both
> curve types)).

I'll need to look at code here too before I can comment.

>>> 3. Should line 862 in Stroker be enabled (I give some reasons for wanting to
>>> in a comment below it).
>> That'll take me a day or two just to understand and figure out...
>> <crosseyed smiley>
> I'm sorry, I should have explained it. That line was a check for lineWidth2>  1.5&&
> subdivisionsSoFar<  5. It was meant to avoid trying to find points where the offset
> curves have cusps if we already have "enough" subdivisions. Now I always try to find
> these points because I don't think this procedure is expensive enough to jeopardize
> rendering quality.

Are you saying that I can ignore that question now?

> I would very much appreciate any comments or suggestions.

I'm afraid to make too many more before you get a chance to check in 
what you have now and at least get us several concrete steps towards a 
quality implementation.

I don't think I've given much in the way of counter-opinions above so if 
you are comfortable with my answers above then let's work on reviewing 
the code with an eye towards getting it in as an important milestone 
before we muck with it too much more...

			...jim