# [OpenJDK 2D-Dev] Fix for drawing round endcaps on scaled lines.

Denis Lila dlila at redhat.com
Tue Jun 22 19:15:48 UTC 2010

```I also have two questions about computing a good bezier approximation
to circle arcs.

1. Given the arc (1,0)->(cos(a),sin(a)) where 0<a<pi/2, will it result
in a good approximation to find the control points p1, p2 by solving
the equations imposed by the requirements B(1/3) = (cos(a/3), sin(a/3)
and B(2/3) = (cos(2a/3), sin(2a/3)). In other words, requiring that the
bezier curve go through two evenly spaced points in the arc.

2. If we have an affine transformation A which turns the circle arc in an
ellipse arc will the transformed control points Ap0, Ap1, Ap2, Ap3 define
a good bezier approximation to the ellipse arc?

Thank you,
Denis.

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

> That's true.
>
> Well, if we're worried about the generated paths being verbose
> and taking long to process then the problem extends beyond just
> drawing round end caps. As far as I can see, whenever a path is
> drawn that doesn't consist only of straight lines (i.e. an ellipse),
> a flattening path iterator is being used to feed Stroker. So all
> the bezier curves are still broken down into tiny straight lines,
> just not by Stroker itself.
>
> So, my question is, given a bezier curve C and a number w, is
> there a way of quickly computing the control points of two bezier
> curves C1, C2 such that the stuff between C1 and C2 is the widened
> path?
> More formally: compute the control points of C1, C2, where
> C1 = {(x,y) + N(x,y)*(w/2)  | (x,y) in C}
> C1 = {(x,y) - N(x,y)*(w/2)  | (x,y) in C}, where N(x,y) is the normal
> of C at (x,y).
>
> If we could do this easily, then we can just make a new class that
> outputs bezier curves that is similar in purpose to Stroker, but that
> is used only when the output can handle bezier curves. This way, the
> only use left for Stroker would be when anti-aliasing, and for
> every thing else we wouldn't have to use a flattening path iterator.
>
> Thanks,
> Denis.
>
> ----- "Jim Graham" <james.graham at oracle.com> wrote:
>
> > Hi Denis,
> >
> > Consider the case of using BasicStroke.createStrokedShape().  How do
> > you
> > know how many pixels the resulting path will occupy?  You can't
> reduce
> >
> > to concrete samples if you don't know the transform.
> >
> > So, for rendering, then you may be correct.  But for cases where the
> > path is being asked for then beziers are the only responsible
> > solution...
> >
> > 			...jim
> >
> > Denis Lila wrote:
> > > Hello Jim.
> > >
> > > I thought about checking the output and changing the behaviour
> > > depending on whether the output is a PC2D or a LineSink, but I
> > didn't
> > > implement it because I thought the point was to get rid of the
> > sampling
> > > at this stage. However, if performance is the issue, then I guess
> > I'll
> > > start working on it.
> > >
> > > Although, I wonder whether it is really worth it. I think most
> lines
> > drawn
> > > won't be wider than about 5 pixels, which means that the current
> way
> > will
> > > emit about 7 lines, so that's 14 coordinates. 2 bezier quarter
> > circles will
> > > require 12 coordinates. In terms of storage, there isn't much
> > difference, and
> > > for lines of width 4 or smaller the current method is more
> > efficient.
> > >
> > > I'm also guessing that it's harder for the rasterizer to deal with
> > bezier
> > > curves than with straight lines, so is it possible that replacing
> > the
> > > 3.14*lineWidth/2 lines generated by the current method with 2
> bezier
> >
> > > quarter circles isn't worth it (for small lineWidths)?
> > >
> > > Thanks,
> > > Denis.
> > >
> > > ----- "Jim Graham" <james.graham at oracle.com> wrote:
> > >
> > >> Sigh - that makes sense.  One issue is that the resulting paths
> it
> >
> > >> generates are much more "verbose" than they need to be.  This
> would
> >
> > >> generally mean that it takes far more storage than it would
> > otherwise
> > >>
> > >> need - and it means that if the result needs to be transformed
> then
> > it
> > >>
> > >> would take many more computations to transform each segment than
> > the
> > >> bezier.
> > >>
> > >> So, perhaps it would be worth having it check the type of the
> > output
> > >> and
> > >> do either a bezier or a bunch of lines depending on if it is a
> PC2D
> > or
> > >> a
> > >> LineSink?
> > >>
> > >> Also, it isn't really that difficult to for Renderer to include
> > its
> > >> own
> > >> Cubic/Quadratic flattening code, but it might involve more
> > >> calculations
> > >> than the round-cap code since it would have to be written for
> > >> arbitrary
> > >> beziers whereas if you know it is a quarter circle then it is
> > easier
> > >> to
> > >> know how far to subdivide...  :-(
> > >>
> > >> 			...jim
> > >>
> > >> Denis Lila wrote:
> > >>> way to do it that wouldn't involve heavy changes to Pisces.
> > >>>
> > >>> In order for Stroker to generate Bezier quarter circles, it
> would
> > >>> have to implement a curveTo method, which means Stroker should
> > >>> start implementing PathConsumer2D and instead of using a
> LineSink
> > >>> output it would have to use a PathConsumer2D output (either
> that,
> > >> or
> > >>> LineSink should include a curveTo method, but then there won't
> > >> really
> > >>> be any difference between a LineSink and a PathConsumer2D. By
> the
> > >> way,
> > >>> LineSink doesn't have any implemented methods, so why is it an
> > >> abstract
> > >>> class as opposed to an interface?)
> > >>>
> > >>> Stroker is used in 3 ways:
> > >>> 1. As an implementation of BasicStroke's createStrokedShape
> > method.
> > >> This
> > >>> uses a Path2D object as output.
> > >>> 2. As a way of feeding a PathConsumer2D without calling
> > >> createStrokedShape
> > >>> to generate an intermediate Shape. This uses a PathConsumer2D
> > >> output.
> > >>> 3. As a way of feeding lines to a Renderer object, which
> > generates
> > >> alpha
> > >>> tiles used for anti-aliasing that are fed to a cache and
> > extracted
> > >> as needed
> > >>> by an AATileGenerator. Obviously, Stroker's output here is a
> > >> Renderer.
> > >>> 1 and 2 aren't problems, because the underlying output objects
> > >> support
> > >>> Bezier curves. 3, however, doesn't, and it seems like
> implementing
> > a
> > >>> curveTo method for Renderer would be very difficult because the
> > way
> > >> it
> > >>> generates alpha tiles is by scanning the drawn edges with
> > >> horizontal
> > >>> scan lines, and for each scan line finding the x-intersections
> of
> > >> the scan
> > >>> lines and the edges. Then it determines the alpha values (I'm
> not
> > >> too sure
> > >>> how it does this).
> > >>> In order to implement Bezier curves in Renderer, we would have
> to
> > >> have
> > >>> a quick way of computing, for each scan line, all its
> > intersections
> > >> with
> > >>> however many Bezier curves are being drawn.
> > >>>
> > >>> I haven't given much thought to how this could be done, as I am
> > not
> > >> very
> > >>> familiar with Bezier curves, but it doesn't seem easy enough to
> > >> justify
> > >>> fixing such a small bug.
> > >>>
> > >>> ----- Original Message -----
> > >>> From: "Jim Graham" <james.graham at oracle.com>
> > >>> To: "Denis Lila" <dlila at redhat.com>
> > >>> Cc: 2d-dev at openjdk.java.net
> > >>> Sent: Wednesday, June 9, 2010 7:42:33 PM GMT -05:00 US/Canada
> > >> Eastern
> > >>> Subject: Re: [OpenJDK 2D-Dev] Fix for drawing round endcaps on
> > >> scaled lines.
> > >>> I don't understand - why do we generate sample points based on
> > the
> > >> size
> > >>> of the cap?  Why not generate a pair of bezier quarter-circles
> > and
> > >> let
> > >>> the rasterizer deal with sampling?
> > >>>
> > >>> 			...jim
> > >>>
> > >>> Denis Lila wrote:
> > >>>> Hello.
> > >>>>
> > >>>> I think I have a fix for this bug:
> > >>>> http://icedtea.classpath.org/bugzilla/show_bug.cgi?id=506
> > >>>>
> > >>>> Basically, the problem is that if there is a magnifying affine
> > >> transformation set on the graphics object and one tries to draw a
> > line
> > >> with small thickness and round end caps, the end caps appear
> > jagged.
> > >> This is because the computation of the length of the array that
> > >> contains the points on the "pen" with which the decoration is
> > drawn
> > >> does not take into account the size of the pen after the
> > magnification
> > >> of the affine transformation. So, for example, if the line length
> > was
> > >> set to 1, and the transformation was a scaling by 10, the
> > resulting
> > >> pen would have a diameter of 10, but only 3 pen points would be
> > >> computed (pi*untransformedLineWidth), so the end cap looks like a
> > >> triangle.
> > >>>> My fix computes an approximation of the circumference of the
> > >> transformed pen (which is an ellipse) and uses that as the number
> > of
> > >> points on the pen. The approximation is crude, but it is simple,
> > >> faster than alternatives
> > >> (http://en.wikipedia.org/wiki/Ellipse#Circumference), and I can
> > say
> > >> from observations that it works fairly well.
> > >>>> There is also icing on the cake, in the form of slight
> > improvements
> > >> in performance when the scaling is a zooming out. Example: if the
> > >> original line width was 100, but g2d.scale(0.1,0.1) was set, then
> > the
> > >> resulting line would have a width of 10, so only ~31 points are
> > >> necessary for the decoration to look like a circle, but without
> > this
> > >> patch, about 314 points are computed (and a line is emitted to
> > each
> > >> one of them).
> > >>>> I appreciate any feedback.
> > >>>>
> > >>>> Regards,
> > >>>> Denis Lila.
> > >>>>

```