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

Jim Graham james.graham at oracle.com
Sat Jul 10 00:17:52 UTC 2010 

Also, the Stroker() constructor, which was marked private in these 
webrevs, isn't used - it should probably just be deleted rather than 
made private...

			...jim

Jim Graham 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