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

[Jim Graham]

(For the record, I got that algorithm from the web... ;-)

			...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.
>>>>>>>