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

Denis Lila dlila at redhat.com
Mon Jul 12 14:22:02 UTC 2010 

Hello Jim.

I'm terribly sorry about that.
I fixed it. Now the only highlighted lines in the webrev should be
lines I actually changed.
Please take another look at it.
(link is still the same: http://icedtea.classpath.org/~dlila/webrevs/bezierRoundJoins/webrev/)

Thanks,
Denis.

PS: I added a new method: emitReverse, that goes through the reverse list
and emits it. It's used in 2 methods which used to just do it themselves.

----- "Jim Graham" <james.graham at oracle.com> wrote:

> Hi Denis,
> 
> You moved some code around without modifying it.  This makes it hard
> to 
> see what changed and what didn't and verify that the changes are 
> accurate.  Also, it adds diffs to the file that are unrelated to the 
> fixing of the bug.  Was there a practical reason for why you moved the
> 
> code around?  In particular I refer to:
> 
> - the setup code that deals with "if (joinStyle == JOIN_MITER)"
> 
> - the setOutput method - which not only moved, but lost its javadocs
> 
> - computeMiter() and drawMiter()
> 
> All of that code "appears" to be unchanged at first glance, but it is
> 
> hard to tell from the webrevs.  Also, a couple of stylistic issues:
> 
> - you changed the declarations of isCCW which moved its arguments
> over, 
> but the continuation lines aren't indented to match
> 
> - The two "flavors" of emitCurveTo() should probably be next to each 
> other (i.e. not have emitLineTo() between them or fall between the two
> 
> flavors of emitLineTo()).
> 
> In general I think the changes are OK, but I'm still reviewing them
> and 
> the above issues sprung to mind on a first pass (and/or they are 
> complicating the "contextual" review) so I thought I'd mention them 
> earlier than later...
> 
> 			...jim
> 
> Denis Lila wrote:
> > Hello.
> > 
> > I just noticed that approximation of circle arcs by bezier curves
> > had already been implemented in ArcIterator by Jim Graham. 
> > 
> > It computes the same control points as my solution, but it does so
> > more straightforwardly, without any rotation, so it is faster and
> > clearer. I have updated my solution to include this.
> > 
> > The link remains the same.
> > 
> > Thanks,
> > Denis.
> > 
> > ----- "Denis Lila" <dlila at redhat.com> wrote:
> > 
> >> Hello.
> >>
> >> I think I got this working. The webrev is at:
> >>
> http://icedtea.classpath.org/~dlila/webrevs/bezierRoundJoins/webrev/
> >> (NOTE: this is not a final version. I have included 2 versions
> >> of 2 methods. Only one set should be kept. See below for more.)
> >>
> >> My Changes:
> >> -----------
> >> 1.
> >>     I've made LineSink into an interface, rather than an abstract
> >> class,
> >> because all of its methods were abstract, so it makes more sense
> this
> >> way.
> >>
> >> 2.
> >>     I've introduced a new interface that extends LineSink called
> >> PathSink,
> >> which allows the curveTo method, so there have been no changes to
> >> Stroker's public interface. When someone wants to create a Stroker
> >> with a PathSink output, it simply passes its constructor a
> PathSink,
> >> so the only changes outside of Stroker are in
> PiscesRenderingEngine,
> >> where the methods that handle Path2D and PathConsumer2D objects
> >> create nameless PathSinks instead of nameless LineSinks.
> >>
> >> 3. In Stroker:
> >>     I've introduced a method called drawBezRoundJoin, analogous to
> >> computeRoundJoin. In drawRoundJoin I detect whether the output is
> >> a PathSink. If it is, I call drawBezRoundJoin, otherwise
> everything
> >> proceeds as it used to. drawBezRoundJoin uses computeBezierPoints
> to
> >> compute the control points. computeBezierPoints computes the
> control
> >> points
> >> for an arc of t radians, starting at angle a, with radius r
> >> by computing the control points of an arc of radius 1 of t radians
> >> that
> >> starts at angle -t/2. This is done by solving the equations
> resulting
> >> from the constraints that (P3-P2) and (P1-P0) must be parallel to
> the
> >> arc's tangents at P3 and P0 respectively, and that B(1/2)=(1,0).
> Then
> >> the
> >> points are scaled by r, and rotated counter clockwise by a+t/2.
> >> Then drawBezRoundJoin emits the curve.
> >>     All this is done in a loop which is used to break up large
> arcs
> >> into
> >> more than one bezier curve. Through the iterations, the computed
> >> control
> >> points don't change - the only thing that changes is how they're
> >> rotated.
> >>     So a good alternative approach would be to do the rotation
> outside
> >> of
> >> computeBezierPoints, and call computeBezierPoints once outside of
> the
> >> loop,
> >> so that the control points aren't recomputed unnecessarily.
> >> I have included code for this in the methods computeBezierPoints2
> and
> >> drawBezRoundJoin2. This is my favoured approach, since it is
> almost
> >> as clear as the other one, and it is faster.
> >>
> >>     There is one more optimization that can be made, and I've
> included
> >> it
> >> in a comment in line 703.
> >>
> >>     I would very much appreciate any comments about any of this,
> but
> >> especially
> >> about the idea in line 703 and about
> >> computeBezierPoints2,drawBezRoundJoin2
> >> vs. computeBezierPoints,drawBezRoundJoin.
> >>
> >> 4.
> >>     Stroker used to only have lines, but now it can emit lines and
> >> curves, so
> >> I needed to change the format of reverse, to not only store
> >> coordinates, but
> >> to also tag them as belonging to a line or a curve.
> >>
> >>
> >> Other Approaches:
> >> -----------------
> >> 1.
> >>     Since what needed to be done was to alter the behaviour of one
> >> part of Stroker (drawing of round joins/caps) depending on the
> type
> >> of the output object, I thought it would be appropriate to make
> >> Stroker
> >> an abstract factory, turn the methods that draw round joins/caps
> into
> >> abstract ones, put all the common functionality in concrete
> methods
> >> in Stroker, and put all the join/cap drawing methods in overriding
> >> methods
> >> in concrete children of Stroker (instances of which were returned
> >> by static factories in Stroker).
> >>     However, this was a bad approach, because the round cap/join
> >> drawing
> >> methods are private, so the only way to call them in Stroker's
> >> children
> >> from public methods in Stroker is to cast "this". So the code
> became
> >> littered with instanceof operators and casts. Not to mention that
> >> Stroker's
> >> public interface had to change, and some functionality was lost:
> >> Stroker
> >> allows changing it's output, so it is possible to use just 1
> Stroker
> >> object
> >> to widen paths going to many different outputs (but not at the
> same
> >> time).
> >> This could no longer be supported with this approach.
> >> The way I did it has none of these weaknesses.
> >>
> >> 2. As for algorithms for the circle approximation, I considered 2:
> >>     a. Compute the control points using the constraints that
> >> B(1/3)=A(a+t/3)
> >> and B(2/3) = A(a+2t/3) (i.e. make the arc and the bezier curve
> >> coincide at 2
> >> evenly spaced points in the arc). This didn't work very well: some
> of
> >> the end
> >> caps looked more like triangles.
> >>     b. Let B(1/2) = A(a+t/2), and B'(1/2) = A'(a+t/2). This worked
> >> better, but
> >> still not good enough.
> >>
> >> If anyone knows of any better ways to compute the control points,
> >> please let
> >> me know.
> >>
> >> I'm sorry for the length of this. I tried to make it shorter.
> >>
> >> Thank you very much,
> >> 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:
> >>>>>> So, I have been thinking about this, and I can't see a good
> >>>>>> 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.
> >>>>>>>

More information about the 2d-dev mailing list