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

[Jim Graham]

Sorry, ignore this message.  I was misinterpreting the field 
"internalJoins" to mean "joins on the inside of the path (!ccw)".  It 
actually means "implicit joins in the middle of a flattened curve" and I 
can see why those are always done round, so the code makes sense now 
(naming of the variable notwithstanding)...

			...jim

Jim Graham wrote:
> Hi Denis,
> 
> In looking through this code, I can see where it emits the proper join 
> for ccw turns, but it looks like it just emits a round join for cw 
> turns.  Is that true?  Doesn't this mean that a cw path will always have 
> round joins?  Or am I missing something?
> 
> My expectation was that the code would emit the proper joins for both 
> ccw and cw turns, but it would either place it in the outgoing or the 
> return path depending on whether the turn was ccw, no?  I don't see how 
> that happens (but I haven't actually tested the code)...
> 
>             ...jim
> 
> Denis Lila wrote:
>> 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.
>>>>>>>>>>