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

[Denis Lila]

Hello Jim.

So, I've now implemented both suggestions you had for implementing
stroke control: an intermediate normalizing path iterator, and 
doing flattening in pisces at the lowest level. Respectively,
the webrevs are:
http://icedtea.classpath.org/~dlila/webrevs/fpWithStrokeControl/webrev/
http://icedtea.classpath.org/~dlila/webrevs/fpWithSCandPiscesFlattening/webrev/

Again, these include the floating point conversion changes, but all of the
changes relevant to this e-mail are in PiscesRenderingEngine.java.

As for performance, the version with low level flattening is faster, but this
is only noticeable when pisces is run on it's own i.e. not actually drawing
anything (by the way, I've included a commented out main method in the second
webrev. This allowed me to run pisces on it's own which was useful for debugging
and performance testing). 
However, when drawing stuff, whatever happens after pisces takes up so much
time that it's hard to tell the difference.

Nevertheless, it might be worth to keep the somewhat ugly, low level version.
It might be useful for antialiasing if Stroker moves to outputting curves instead
of just lines (because AA still needs to flatten, unless someone comes up with an
algorithm to do it without flattening, but I can't think of anything).

I'm sorry to ask you specifically for all these reviews - you've already spent
a lot of time looking at my work, but no one else has replied to any of my pisces
inquiries (except Clemens Eisserer, on this issue). Anyway, I would appreciate it
if you, or anyone, could take a look at one or both of the above webrevs.

Or maybe we could leave it for when the floating point conversion has been pushed.
Then the webrevs would have a lot less clutter.

Thanks,
Denis.

----- "Denis Lila" <dlila at redhat.com> wrote:

> Hi Jim.
> 
> I implemented STROKE_CONTROL today. I used the intermediate
> NormalizingPathIterator, instead of implementing flattening in
> pisces, because I wanted to get something working asap, and this
> would be the easiest way.
> 
> The webrev is
> http://icedtea.classpath.org/~dlila/webrevs/fpWithStrokeControl/webrev/
> 
> I guess I'm not asking that you take a look at it, because it's
> probably
> not the way we're going to end up doing things, but I wrote it, so
> I'm sending the link just in case anyone wants to see it.
> 
> The webrev is big because it includes the floating point conversion,
> but all the
> STROKE_CONTROL changes are in PiscesRenderingEngine.java.
> 
> Thanks,
> Denis.
> 
> ----- "Jim Graham" <james.graham at oracle.com> wrote:
> 
> > Hi Denis,
> >
> > It would be ill-advised to normalize the coordinates after
> flattening.
> >
> > The quality would be really bad.
> >
> > Perhaps this is a good reason to start looking at updating Pisces to
> > take curves and flatten at the lowest level?
> >
> > Or, I suppose we could get a non-flattened iterator from the source
> > path, send it through a "normalizing" filter, and then through a
> > flattening filter (the way many of the existing objects do
> flattening
> > is
> > to just get their regular iterator and run it through an instance of
> > FlatteningPathIterator so we could do this manually with an
> > intervening
> > "NormalizingPathIterator" if normalization is needed)...
> >
> > 			...jim
> >
> > Denis Lila wrote:
> > > Hello Jim.
> > >
> > > Thanks for that. I'll get to work on implementing it.
> > >
> > > One thing though, about normalizing the control points of bezier
> > > curves: pisces never gets any bezier curves as input. It only gets
> > > lines that are the product of flattening bezier curves.
> > >
> > > Pisces receives its input from flattening path iterators which get
> > it
> > > from other path iterators. Of course we can't require these to
> send
> > out
> > > normalized points. In order to normalize the control points we
> need
> > to
> > > be able to look at the bezier curves in Pisces, so we can't just
> > take
> > > all the input from the flattener. However, pisces can't handle
> > curves
> > > (yet, hopefully), so after the normalization, they must be
> > flattened, and
> > > this is the problem. I think it's a pretty good idea to do this by
> > > storing the input form the iterator into pisces (after
> > normalization),
> > > creating a nameless path iterator that just iterates through all
> > that,
> > > and using this iterator to create a flattening iterator, which
> then
> > > is used as before.
> > >
> > > Does anyone have any other ideas?
> > >
> > > Thank you,
> > > Denis.
> > >
> > >
> > > ----- "Jim Graham" <james.graham at oracle.com> wrote:
> > >
> > >> For AA this is exactly what we do (round to nearest pixel centers
> > for
> > >>
> > >> strokes).  Note that this is done prior to any line widening code
> > is
> > >> executed.
> > >>
> > >> For non-AA we normalize coordinates to, I believe the (0.25,
> 0.25)
> >
> > >> sub-pixel location.  This is so that the transitions between
> > widening
> > >> of
> > >> lines occurs evenly (particularly for horizontal and vertical
> wide
> >
> > >> lines).  If you round to pixel edges then you have the following
> > >> progression (note that the line width grows by half on either
> side
> > of
> > >>
> > >> the original geometry so you have to consider the "line widths"
> > where
> > >>
> > >> you encounter the pixel centers to your left and right (or above
> > and
> > >> below) which govern when that column (or row) of pixels first
> > turns
> > >> on):
> > >>
> > >> width 0.00 => 0.99      nothing drawn (except we kludge this)
> > >> width 1.00 => 1.00      1 pixel wide (col to left turns on)
> > >> width 1.01 => 2.99      2 pixels wide (col to right turns on)
> > >> width 3.00 => 3.00      3 pixels wide (etc.)
> > >> width 3.01 => 4.99      4 pixels wide
> > >>
> > >> Note that it is nearly impossible to get an odd-width line.  You
> > >> basically have to have exactly an integer width to get an
> odd-width
> >
> > >> line.  This is because at the odd widths you reach the "half
> pixel"
> >
> > >> locations on both sides of the line at the same time.  Due to the
> > >> "half-open" insideness rules only one of the pixels will be
> chosen
> > to
> > >> be
> > >> inside this path.  Just below these sizes and you fail to hit
> > either
> > >> pixel center.  Just at the integer size you reach both pixel
> > centers
> > >> at
> > >> the same time.  Just slightly larger than that width and now
> you've
> >
> > >> fully enclosed both pixel centers and the line width has to
> > increase
> > >> by
> > >> nearly 2.0 until you reach the next pixel centers.
> > >>
> > >> (The kludge I talk about above is that we set a minimum pen width
> > so
> > >> that we never fail to draw a line even if the line width is set
> to
> > >> 0.0,
> > >> but the above table was a theoretical description of the absolute
> > >> rules.)
> > >>
> > >> If we rounded them to pixel centers, then the transitions look
> > like
> > >> this:
> > >>
> > >> width 0.00 => 0.00      nothing drawn (modulo kludge)
> > >> width 0.01 => 1.99      1 pixel wide (column you are in turns on)
> > >> width 2.00 => 2.00      2 pixels wide (column to left turns on)
> > >> width 2.01 => 3.99      3 pixels wide (column to right turns on)
> > >> width 4.00 => 4.00      4 pixels wide (etc.)
> > >> width 4.01 => 5.99      5 pixels wide
> > >>
> > >> We have a similar effect as above, but biased towards making even
> > line
> > >>
> > >> widths harder.
> > >>
> > >> So, by locating lines at (0.25, 0.25) subpixel location we end up
> > with
> > >> a
> > >>   very even progression:
> > >>
> > >> width 0.00 => 0.50      nothing drawn (modulo kludge)
> > >> width 0.51 => 1.50      1 pixel wide (column you are in turns on)
> > >> width 1.51 => 2.50      2 pixel wide (column to left gets added)
> > >> width 2.51 => 3.50      3 pixel wide (column to right gets added)
> > >> width 3.51 => 4.50      4 pixel wide (etc.)
> > >>
> > >> This gives us nice even and gradual widening of the lines as we
> > >> increase
> > >> the line width by sub-pixel amounts and the line widths are
> fairly
> >
> > >> stable around integer widths.
> > >>
> > >> Also, note that we don't say "when stroking" as you might want to
> > >> normalize both strokes and fills so that they continue to match. 
> I
> >
> > >> believe that we normalize both strokes and fills for non-AA and
> we
> > >> only
> > >> normalize strokes for AA (and leave AA fills as "pure").  AA is
> > less
> > >> problematic with respect to creating gaps if your stroke and fill
> > >> normalization are not consistent.
> > >>
> > >> The rounding equations are along the lines of:
> > >>
> > >> 	v = Math.floor(v + rval) + aval;
> > >>
> > >> For center of pixel you use (rval=0.0, aval=0.5)
> > >> For 0.25,0.25 rounding use  (rval=0.25, aval=0.25)
> > >> For edge of pixel you use   (rval=0.5, aval=0.0)
> > >>
> > >> Also, we came up with an interesting way of adjusting the control
> > >> points
> > >> of quads and cubics if we adjusted their end points, but I don't
> > know
> > >> if
> > >> what we did was really the best idea.  For quads we adjust the
> > control
> > >>
> > >> point by the average of the adjustments that we applied to its 2
> > end
> > >> points.  For cubics, we move the first control point by the same
> > >> amount
> > >> as we moved the starting endpoint and the second control point by
> > the
> > >>
> > >> amount we moved the final endpoint.  The jury is out on whether
> > that
> > >> is
> > >> the most aesthetic technique...
> > >>
> > >> 			...jim
> > >>
> > >> Denis Lila wrote:
> > >>> Regarding VALUE_STROKE_NORMALIZE the API says:
> > >>>                 Stroke normalization control hint value --
> > geometry
> > >> should
> > >>>                 be normalized to improve uniformity or spacing
> of
> > >> lines and
> > >>>                 overall aesthetics. Note that different
> > >> normalization
> > >>>                 algorithms may be more successful than others
> for
> > >> given
> > >>>                 input paths.
> > >>>
> > >>> I can only think of one example where VALUE_STROKE_NORMALIZE
> makes
> > a
> > >> visible
> > >>> difference between the closed source implementation and OpenJDK:
> > >>> when drawing anti-aliased horizontal or vertical lines of width
> > 1,
> > >> Pisces
> > >>> draws a 2 pixel wide line with half intensity (because integer
> > >> coordinates
> > >>> are between pixels). Sun's jdk with VALUE_SROKE_NORMALIZE turned
> > on
> > >> draws
> > >>> a 1 pixel line with full intensity. This could to achieved by
> > just
> > >>> checking for normalization and rounding coordinates to the
> > nearest
> > >> half
> > >>> pixel, but this solution seems too simple, and I'm not sure
> > whether
> > >> I'm missing
> > >>> anything. It would also probably cause problems when drawing
> > >> anti-aliased
> > >>> short lines (which is done when drawing any sort of curve)
> > >>> Unless, of course, this rounding was restricted to just
> > horizontal
> > >> and
> > >>> vertical lines.
> > >>>
> > >>> Regards,
> > >>> Denis.