[prev in list] [next in list] [prev in thread] [next in thread] 

List:       openjdk-2d-dev
Subject:    [OpenJDK 2D-Dev] Fix for drawing round endcaps on scaled lines.
From:       dlila () redhat ! com (Denis Lila)
Date:       2010-07-15 23:49:18
Message-ID: 316281134.425161279237758070.JavaMail.root () zmail04 ! collab ! prod ! int ! phx2 ! redhat ! com
[Download RAW message or body]

Hello Jim.

Thanks for reviewing it.

That part confused me too, so I skimmed through it and wrote
drawBezRoundJoin to just compute the control points for an arc with
centre at (x,y), going from (x+omx, y+omy) to (x+mx, y+my). I also took
rev into account, but it's late and I don't remember exactly how right now.
However, I tested it with many randomly generated polylines and other shapes,
and it works. The caps are a bit funny looking for widths 10-17 
inclusive (but strangely, not for <=9) but it's not because of how the control
points are computed, because when, say, a (5,5) scale is used, everything looks
good.

I finished converting Stroker and Dasher to floating point arithmetic. I've been
working on Renderer for the last 3 days, and I finished it (sort of) but a number
of issues have come up.
The most important is that I have been unable to make it work with the current
algorithm for computing scanline crossings. What it does now is it goes through
the drawing surface in strips, and computes crossings for edges in that strip.
It does this to save memory. When I simply convert everything to doubles,
dashed lines aren't rendered properly. Some angles are skewed, and there are small
gaps in the solid segments.
It works if I simply compute the crossings for every edge and forget about strips,
but if a large GeneralPath is being rendered, this tends to consume too much memory.

Regards, 
Denis.

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

> Argh.  Not enough coffee.  The variable is "joinSegment", but the 
> comment mentions "internal joins".  Either way, that code is only 
> invoked when the upstream path iterator doesn't indicate that a join
> is 
> needed.
> 
> BTW, that code is currently not executed because the code upstream
> from 
> this class is using a regular flattening path iterator and just
> calling 
> "lineJoin" on every segment, whether it came from the original path or
> 
> whether it was implicitly calculated from a flattened curve.  It won't
> 
> make a noticeable difference because most joins should work fine for a
> 
> properly flattened curve, but the logic to always do a round join for
> 
> implicit vertices will never be invoked the way we are doing it
> now...
> 
> 			...jim
> 
> Jim Graham wrote:
> > 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.
> >>>>>>>>>>>

[prev in list] [next in list] [prev in thread] [next in thread]