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

[Jim Graham]

Hi Denis,

We need a lot of upgrades in this area, but they will come with some 
engineering cost.

Note that the Ductus line widening code widens curves to curves, but 
many (most?) line wideners flatten everything to do widening so they 
only have to deal with algorithms that widen and join lines.  I haven't 
applied myself to the task of creating an algorithm that can do their 
"direct curve widening" technique yet so I don't have a canned solution 
for that, but it would make the results of 
BasicStroke.createStrokedShape() much less verbose.

Also, for a practical matter the existing down-stream rendering classes 
that take the output from these widening classes only deal with lines, 
but if they took the curves directly then they might be able to do a 
more efficient job of flattening the segments.  Until then, the only 
case where it would matter much for these classes to output curves would 
be for BS.createStrokedShape() and even that would probably require some 
more plumbing from the code that feeds these classes.

But, I want to raise visibility of these issues here because we should 
not be blindly accepting flattening as the law when we consider upgrades 
to this part of the code.  It is currently an "easy way out" and as we 
spend time on the code we should provide resistance to accepting that 
philosophy by default...

			...jim

Denis Lila 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:
>>>>> 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.
>>>>>>