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" <dl...@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.gra...@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.gra...@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.gra...@oracle.com> > > >>> To: "Denis Lila" <dl...@redhat.com> > > >>> Cc: 2d-dev@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. > > >>>>
