Hi, Please review Marlin/FX upgrades that provide an efficient path clipper in Stroker (float / double variants) fixing the bug JDK8184429Marlin2D patch (jdk10): http://cr.openjdk.java.net/~lbourges/marlin/marlin080.0/ MarlinFX patch (openjfx10): http://cr.openjdk.java.net/~lbourges/marlinFX/marlin080.0/ Path Clipper in (D)Stroker:  it uses outcode computation (cohen  sutherland) for segment edges (2 for lines, 3 for quads, 4 for cubics)  it opens the path when a segment is invisible ie special moveTo() and ignore invisible joins; it does not compute any intersection (line / curve), it just skips useless segment for better performance and accuracy  the ClosedPathDetector is needed to infer if the path is closed or not (call to closePath) to produce caps when appropriate. It reuses the former PolyStack (moved into Helper classes) to store the forward segments  the clip rectangle is adjusted either in Stroker but also in Transformer2D to take into account the mitter limit, stroker width and also the Renderer offset That's why it can not be applied to closed paths (fill operations) as the path must remain closed in such case (concave polygon). This could be implemented later as it needs to insert corner points when needed to avoid artefacts; so the algorithm seem more complicated to me. Marlin2D / FX Patches are slightly different to handle the Renderer offsets. I tested these patches against my MapBench test with a small clip and several affine transforms: it does not produce any artefact (0 pixel difference between clip=true/false) PS: I also improved the accuracy of Renderer's AFD by using the kaham compensatedsum approach (later patch) Cheers, Laurent Bourgès 
Hi Laurent,
I'm just reading through the code now to get a handle on the nature of the changes...(and starting with the 2D version)... [D]Dasher.java  why the changes from (firstSegIdx > 0) to (firstSegIdx != 0)? [D]Dasher.java  why is there a new goto_starting() which is only used from one place? To be able to add final to the parameters? [D]Dasher.java, line 268ish  why move the call to out.moveto() down a line? [D]Stroker.java, line 170ish  you added final to the float params, but not the double [D]Stroker.java, line 196ish  why are ROUND treated differently. You have a question on that as well in a comment. [D]Stroker.java, line 196ish  CAP_SQUARE would require more than lw/2 padding. I think it needs lw*sqrt(2)/2 padding. I would think the padding would be (max of the CAP/JOIN values below): CAP_BUTT  lw/2 CAP_ROUND  lw/2 CAP_SQUARE  lw/2 * sqrt(2) JOIN_BEVEL  lw/2 JOIN_ROUND  lw/2 JOIN_MITER  max(lw/2, miter_limit * lw) In other words:  lw/2 by default  if CAP_SQUARE then multiply that by sqrt(2)  if JOIN_MITER then max it with limit I'm still looking through the management of the closed path detection coordinates, but I thought I'd get at least these questions out first before the weekend... ...jim On 8/25/17 1:09 PM, Laurent Bourgès wrote: > Hi, > > Please review Marlin/FX upgrades that provide an efficient path clipper in > Stroker (float / double variants) fixing the bug JDK8184429 > <https://bugs.openjdk.java.net/browse/JDK8184429> > > Marlin2D patch (jdk10): > http://cr.openjdk.java.net/~lbourges/marlin/marlin080.0/ > MarlinFX patch (openjfx10): > http://cr.openjdk.java.net/~lbourges/marlinFX/marlin080.0/ > > Path Clipper in (D)Stroker: >  it uses outcode computation (cohen  sutherland) for segment edges (2 for > lines, 3 for quads, 4 for cubics) >  it opens the path when a segment is invisible ie special moveTo() and > ignore invisible joins; it does not compute any intersection (line / > curve), it just skips useless segment for better performance and accuracy >  the ClosedPathDetector is needed to infer if the path is closed or not > (call to closePath) to produce caps when appropriate. It reuses the former > PolyStack (moved into Helper classes) to store the forward segments >  the clip rectangle is adjusted either in Stroker but also in > Transformer2D to take into account the mitter limit, stroker width and also > the Renderer offset > > That's why it can not be applied to closed paths (fill operations) as the > path must remain closed in such case (concave polygon). > This could be implemented later as it needs to insert corner points when > needed to avoid artefacts; so the algorithm seem more complicated to me. > > Marlin2D / FX Patches are slightly different to handle the Renderer offsets. > > I tested these patches against my MapBench test with a small clip and > several affine transforms: it does not produce any artefact (0 pixel > difference between clip=true/false) > > PS: I also improved the accuracy of Renderer's AFD by using the kaham > compensatedsum approach (later patch) > > Cheers, > Laurent Bourgès > 
Hi Jim, Thanks for your comments, it helped refining the webrev.Here are my answers: 20170826 2:22 GMT+02:00 Jim Graham <[hidden email]>: [D]Dasher.java  why the changes from (firstSegIdx > 0) to (firstSegIdx != 0)? As firstSegIdx is initialized to 0, I prefer testing (firstSegIdx != 0) as it looks more obvious. For me, (firstSegIdx > 0) indicates that the sign has a particular meaning and that firstSegIdx may be negative. [D]Dasher.java  why is there a new goto_starting() which is only used from one place? To be able to add final to the parameters? For inlining purposes, the JITWatch jarscan tool reported that this (hotspot) method is larger than 325 byte codes so I wanted to split it in smaller parts. [D]Dasher.java, line 268ish  why move the call to out.moveto() down a line? To set the needsMoveTo flag just below the condition: if (needsMoveTo) { needsMoveTo = false; ...} [D]Stroker.java, line 170ish  you added final to the float params, but not the double Fixed. I also fixed all (D)PathConsumer2D methods overriden in Dasher, Stroker & Renderer. [D]Stroker.java, line 196ish  why are ROUND treated differently. You have a question on that as well in a comment. I found the answer: C = 4/3 * (SQRT(2)  1) is used to compute the control points (cubics) to approximate a circle. I fixed the constant estimation according to the math formula. [D]Stroker.java, line 196ish  CAP_SQUARE would require more than lw/2 padding. I think it needs lw*sqrt(2)/2 padding. Exactly, good point ! I would think the padding would be (max of the CAP/JOIN values below): I agree your new rules. I fixed the (D)Stroker init() methods according the latter rules and tested again. Probably I should write a new Clip test rendering Z shapes with all (cap / join) combinations and their bounds aligned to the Stroker's outside clip rules. Here is an updated webrev (Marlin2D only): PS: I can send you an updated MarlinFX patch (when you need it). Cheers, Laurent I'm still looking through the management of the closed path detection coordinates, but I thought I'd get at least these questions out first before the weekend...  
Laurent Bourgès 
Hi Laurent,
On 8/28/17 2:09 PM, Laurent Bourgès wrote: > Hi Jim, > > Thanks for your comments, it helped refining the webrev. > > Here are my answers: > > 20170826 2:22 GMT+02:00 Jim Graham <[hidden email] <mailto:[hidden email]>>: > > [D]Dasher.java  why the changes from (firstSegIdx > 0) to (firstSegIdx != 0)? > > As firstSegIdx is initialized to 0, I prefer testing (firstSegIdx!= 0) as it looks more obvious. > For me, (firstSegIdx > 0) indicates that the sign has a particular meaning and that firstSegIdxmay be negative. Interesting, I'm used to != 0 being only used in contexts where the value might have some specific reason for being negative, but I can see why you did that. > [D]Stroker.java, line 196ish  why are ROUND treated differently. You have a question on that as well in a comment. > > I found the answer: C = 4/3 * (SQRT(2)  1) is used to compute the control points (cubics) to approximate a circle. I > fixed the constant estimation according to the math formula. The control points don't control how far the path gets from the line, though  that measurement is arbitrary compared to the clipping operation. The correct distance from the vertex to the edge of the drawn path is lw/2. > I agree your new rules. > I fixed the (D)Stroker init() methods according the latter rules and tested again. Looks good. > Probably I should write a new Clip test rendering Z shapes with all (cap / join) combinations and their bounds aligned > to the Stroker's outside clip rules. > > Here is an updated webrev (Marlin2D only): > http://cr.openjdk.java.net/~lbourges/marlin/marlin080.1/ > > PS: I can send you an updated MarlinFX patch (when you need it). Not yet until I've had a chance to review the guts of the algorithm. So far I've only looked at a few boundary changes. I'll get to that soon... ...jim 
Jim,
FYI I am working on a more general clipper for filled shapes (only non zero winding rule) that ignores useless segments on left / right sides but leaves the path closed for filling primitives. It is more tricky... to handle turning points (corners) but I think it could be applied later to the Stroker case to avoid opening the path (and require ClosedPathDetector). Should I look at the Area class that performs such clipping but is known to be extremely slow ? If you think it is useful, I could optimize it as I did in Marlin (array caching...). What is your opinion ? Is Area used in the java2d pipeline ? That would improve the overall performance. PS: I wonder if curves should be subdivided at inflexion / root points in this (too) basic fill pipeline to improve cubic / quad accuracy (as it is the case in Stroker) and have monotonic curves. I studied AFD accuracy (inc/dec thresholds) but did not try curve subdivision to guarantee the special point accuracy (cups...) Cheers, Laurent Le 29 août 2017 2:58 AM, "Jim Graham" <[hidden email]> a écrit : Hi Laurent, 
Hi Laurent,
Area is overkill for this as it tries to find exact intersection points of arbitrary geometry. You simply need something that will trace accurately around the outside of a clip to get from an exit point back to an entry point. That is a much simpler operation. The performance issues with Area, btw, have nothing to do with array caching, they have to do with the numerical instabilities in performing an operation which boils down to be numerically equivalent to solving a 9th order equation. While you are welcome to investigate that, it will involve a much different set of techniques than what was applied to Marlin... :( Also, I thought that the Renderer already did basic clipping along the lines that you indicate. It does that on a persegment basis, but all it would take is a simple test at the top of quadTo() and curveTo() to completely reject all curves that lie outside the fill region (and simply shadow any part that is entirely to the left so that we maintain the proper crossings count)... ...jim On 8/31/17 12:43 AM, Laurent Bourgès wrote: > Jim, > > FYI I am working on a more general clipper for filled shapes (only non zero winding rule) that ignores useless segments > on left / right sides but leaves the path closed for filling primitives. > > It is more tricky... to handle turning points (corners) but I think it could be applied later to the Stroker case to > avoid opening the path (and require ClosedPathDetector). > > Should I look at the Area class that performs such clipping but is known to be extremely slow ? If you think it is > useful, I could optimize it as I did in Marlin (array caching...). What is your opinion ? Is Area used in the java2d > pipeline ? That would improve the overall performance. > > PS: I wonder if curves should be subdivided at inflexion / root points in this (too) basic fill pipeline to improve > cubic / quad accuracy (as it is the case in Stroker) and have monotonic curves. > I studied AFD accuracy (inc/dec thresholds) but did not try curve subdivision to guarantee the special point accuracy > (cups...) > > Hope you will have time soon to look at the webrev, your feedback may help a lot. > > Cheers, > Laurent > > Le 29 août 2017 2:58 AM, "Jim Graham" <[hidden email] <mailto:[hidden email]>> a écrit : > > Hi Laurent, > > > On 8/28/17 2:09 PM, Laurent Bourgès wrote: > > Hi Jim, > > Thanks for your comments, it helped refining the webrev. > > Here are my answers: > > 20170826 2:22 GMT+02:00 Jim Graham <[hidden email] <mailto:[hidden email]> > <mailto:[hidden email] <mailto:[hidden email]>>>: > > > [D]Dasher.java  why the changes from (firstSegIdx > 0) to (firstSegIdx != 0)? > > As firstSegIdx is initialized to 0, I prefer testing (firstSegIdx!= 0) as it looks more obvious. > > For me, (firstSegIdx > 0) indicates that the sign has a particular meaning and that firstSegIdxmay be negative. > > > Interesting, I'm used to != 0 being only used in contexts where the value might have some specific reason for being > negative, but I can see why you did that. > > > [D]Stroker.java, line 196ish  why are ROUND treated differently. You have a question on that as well in a > comment. > > I found the answer: C = 4/3 * (SQRT(2)  1) is used to compute the control points (cubics) to approximate a > circle. I fixed the constant estimation according to the math formula. > > > The control points don't control how far the path gets from the line, though  that measurement is arbitrary > compared to the clipping operation. The correct distance from the vertex to the edge of the drawn path is lw/2. > > > I agree your new rules. > I fixed the (D)Stroker init() methods according the latter rules and tested again. > > > Looks good. > > > Probably I should write a new Clip test rendering Z shapes with all (cap / join) combinations and their bounds > aligned to the Stroker's outside clip rules. > > Here is an updated webrev (Marlin2D only): > http://cr.openjdk.java.net/~lbourges/marlin/marlin080.1/ > <http://cr.openjdk.java.net/~lbourges/marlin/marlin080.1/> > > PS: I can send you an updated MarlinFX patch (when you need it). > > > Not yet until I've had a chance to review the guts of the algorithm. So far I've only looked at a few boundary > changes. I'll get to that soon... > > ...jim > > 
To be clear, all that would be needed in cubicTo would be:
if (y0 > bot && y1 > bot && y2 > bot && y3 > bot) { xy0 = xy3; return; } if (y0 < top && y1 < top && y2 < top && y3 < top) { xy0 = xy3; return; } if (x0 > rgt && x1 > rgt && x2 > rgt && x3 > rgt) { xy0 = xy3; return; } if (x0 < lft && x1 < lft && x2 < lft && x3 < lft) { // Needed to keep incoming crossings counts from the left accurate addLine(x0, y0, x3, y3); x0 = x3; y0 = y3; return; } // (Or this could be expressed as nested ifs: if (y0 < bot  ...  y3 < bot) { if (y0 > top  ...  y3 > top) { if (x0 < rgt  ...  x3 < rgt) { if (x0 > lft  ...  x3 > lft) { DDA stuff } else { addLine(x0,y0,x3,y3); } } } } x0 = x3; y0 = y3; Can a prefilter save any more work than that? Note that if any coordinate isn't trivially rejected by these tests then you are going to have to do some kind of work to follow the curve to figure out which pieces are in or out and I think that the DDA stuff is just as good as any other technique for accomplishing that and since we have to do the DDA stuff anyway, we can just piggyback off of that. When it calls addLine(), we will reject each of its pieces individually... ...jim On 8/31/17 12:45 PM, Jim Graham wrote: > Hi Laurent, > > Area is overkill for this as it tries to find exact intersection points of arbitrary geometry. You simply need > something that will trace accurately around the outside of a clip to get from an exit point back to an entry point. That > is a much simpler operation. > > The performance issues with Area, btw, have nothing to do with array caching, they have to do with the numerical > instabilities in performing an operation which boils down to be numerically equivalent to solving a 9th order equation. > While you are welcome to investigate that, it will involve a much different set of techniques than what was applied to > Marlin... :( > > Also, I thought that the Renderer already did basic clipping along the lines that you indicate. It does that on a > persegment basis, but all it would take is a simple test at the top of quadTo() and curveTo() to completely reject all > curves that lie outside the fill region (and simply shadow any part that is entirely to the left so that we maintain the > proper crossings count)... > > ...jim > > On 8/31/17 12:43 AM, Laurent Bourgès wrote: >> Jim, >> >> FYI I am working on a more general clipper for filled shapes (only non zero winding rule) that ignores useless >> segments on left / right sides but leaves the path closed for filling primitives. >> >> It is more tricky... to handle turning points (corners) but I think it could be applied later to the Stroker case to >> avoid opening the path (and require ClosedPathDetector). >> >> Should I look at the Area class that performs such clipping but is known to be extremely slow ? If you think it is >> useful, I could optimize it as I did in Marlin (array caching...). What is your opinion ? Is Area used in the java2d >> pipeline ? That would improve the overall performance. >> >> PS: I wonder if curves should be subdivided at inflexion / root points in this (too) basic fill pipeline to improve >> cubic / quad accuracy (as it is the case in Stroker) and have monotonic curves. >> I studied AFD accuracy (inc/dec thresholds) but did not try curve subdivision to guarantee the special point accuracy >> (cups...) >> >> Hope you will have time soon to look at the webrev, your feedback may help a lot. >> >> Cheers, >> Laurent >> >> Le 29 août 2017 2:58 AM, "Jim Graham" <[hidden email] <mailto:[hidden email]>> a écrit : >> >> Hi Laurent, >> >> >> On 8/28/17 2:09 PM, Laurent Bourgès wrote: >> >> Hi Jim, >> >> Thanks for your comments, it helped refining the webrev. >> >> Here are my answers: >> >> 20170826 2:22 GMT+02:00 Jim Graham <[hidden email] <mailto:[hidden email]> >> <mailto:[hidden email] <mailto:[hidden email]>>>: >> >> >> [D]Dasher.java  why the changes from (firstSegIdx > 0) to (firstSegIdx != 0)? >> >> As firstSegIdx is initialized to 0, I prefer testing (firstSegIdx!= 0) as it looks more obvious. >> >> For me, (firstSegIdx > 0) indicates that the sign has a particular meaning and that firstSegIdxmay be negative. >> >> >> Interesting, I'm used to != 0 being only used in contexts where the value might have some specific reason for being >> negative, but I can see why you did that. >> >> >> [D]Stroker.java, line 196ish  why are ROUND treated differently. You have a question on that as well in a >> comment. >> >> I found the answer: C = 4/3 * (SQRT(2)  1) is used to compute the control points (cubics) to approximate a >> circle. I fixed the constant estimation according to the math formula. >> >> >> The control points don't control how far the path gets from the line, though  that measurement is arbitrary >> compared to the clipping operation. The correct distance from the vertex to the edge of the drawn path is lw/2. >> >> >> I agree your new rules. >> I fixed the (D)Stroker init() methods according the latter rules and tested again. >> >> >> Looks good. >> >> >> Probably I should write a new Clip test rendering Z shapes with all (cap / join) combinations and their bounds >> aligned to the Stroker's outside clip rules. >> >> Here is an updated webrev (Marlin2D only): >> http://cr.openjdk.java.net/~lbourges/marlin/marlin080.1/ >> <http://cr.openjdk.java.net/~lbourges/marlin/marlin080.1/> >> >> PS: I can send you an updated MarlinFX patch (when you need it). >> >> >> Not yet until I've had a chance to review the guts of the algorithm. So far I've only looked at a few boundary >> changes. I'll get to that soon... >> >> ...jim >> >> 
In reply to this post by Jim Graham5
Hi Jim, I am answering your first message: Area is overkill for this as it tries to find exact intersection points of arbitrary geometry. You simply need something that will trace accurately around the outside of a clip to get from an exit point back to an entry point. That is a much simpler operation. OK, I started such approach but as it skips segments on the left side, it will not preserve crossing counts for the evenodd winding rule, I suppose. The key point is to reduce the edges / crossings processed by the Renderer in the left and right sides of the clip at every scanlines. For example, it will be worth when rendering a large text as a transformed shapes as many letter (closed paths) will be out the L/R sides... Top/Bottom clipping in Renderer already ignores such edges (except for curves). Moreover I agree Marlin does not need a proper path clipper (intersections) but just needs skipping useless segments like a path simplifier as I did in the Stroker. Another case: you provided a Test class using a path made with 10000 line segments on the left side. If it is converted by createStrokedShape(), then the Renderer will again deal with thousands crossings and it will be slow again. Also, I thought that the Renderer already did basic clipping along the lines that you indicate. It does that on a persegment basis, but all it would take is a simple test at the top of quadTo() and curveTo() to completely reject all curves that lie outside the fill region (and simply shadow any part that is entirely to the left so that we maintain the proper crossings count)... Agreed but closed subpaths can also be ignored on either left or right sides like circles, letters... What do you mean by shadow any part on the left ? For the Evenodd filling rule, I think it needs exact segment intersections on the left side, so I am focused on the Nonzero filling rule for now. Finally I tried two approach:  basic subpath outside test (derived from the ClosedPathDetector) to ignore closed subpaths outside of the clip.  more general clipper that follows the path, detect enter/exit the clip but it needs to insert/remove corner points. I am improving this latter approach. Thanks for your advices, Laurent 
First, consider what is handled inside the guts of the Renderer process.
 It doesn't need to process any segments above or below the clip, they have no impact on the rendered pieces inside the clip  It needs to process segments that are outleft only in so far as it needs to come up with a proper crossings count for the first pixel inside the clip, nothing else about that geometry matters  It needs to process segments inside the leftright part of the clip on any scanline it is computing and it needs to know the X locations of each crossing and how the crossing count affects insideness and outsideness  It can stop processing when it reaches the right edge of the clip as the crossings out there have no impact on anything that will be rendered All of this is already computed on a segmentbysegment basis inside addLine(). The only thing missing for curves is that they might be rejected in their entirety, or we might be able to pare them down to only the pieces that need to be processed. Currently they will be rejected as they feed their pieces to addLine() and it rejects each segment in turn, but we might be able to short circuit the process by looking at their control points up front before we run DDA on them. If a curve is entirely out/below/right, then Renderer can outright reject it and doesn't need to deal with connecting pieces of the path, it is only concerned about what ends up in its list of segments  nothing else. A prefilter noticing the same thing about that segment will know that the result that it wants is for the Renderer to ignore it, but it will need to deal with complicated logic of how to omit that segment in a way that the subpath/closepath logic of the Renderer is managed correctly. In other words, it has work to do because it isn't simply inside the Renderer where we can drop path pieces on the floor with impunity. If a curve is more complicated in how it interacts with the top/bot/left/right clip coordinates, then it might still be rejected, or it might need to be partially rendered. Something is going to need to do some computation to figure that out. If we try to do those computations before we get to the Renderer, then whatever computations we use to do that will likely be just as complicated as the DDA work done inside the Renderer. That work as a "prefilter" will also be complicated in that it will then need to express its results as a "simplified, but connected" path rather than simply dropping pieces on the floor as the Renderer can do. Now, it is possible that we could subdivide a curve that has no simple outcode rejection criteria  for example a curve that starts above the clip, but horizontally "over" it, extends around the upperright corner of the clip to a position that is to the right of the clip, but within its vertical bounds. Such a curve would not be rejected by any "all Y<top" or "all X>right" tests. It might be true that you could cut it at some point on the curve (and you might even be lucky enough that a midpoint cut would suffice) and each half of the curve would then pass the rejection criteria, but you'd have to analyze the curve to figure that out. It is just as likely that while the control points follow the pattern I outlined at the start of this paragraph, the actual traced outline goes inside the clip. You won't know until you perform some calculations. In the meantime, the Renderer already does a pretty fast DDA subsection of the curve and those pieces are then rejected by addLine() each in turn. How sure can you be that you can find a computation for such curves that will be successful in enough cases that you will save time over DDA? How often are curves even in this particular situation in the first place? If only .1% of curves ever benefit from this analysis then you might slow down the common case to be slightly faster in a rare case. Finally, if there is some calculation that could be performed on such "not immediately rejectable, but possibly outside" curves to simplify their processing, the best place for those calculations is still in the Renderer where its response to finding a piece of a curve that is trivially rejectable is to just skip it, rather than a prefilter which will have to worry about how to connect the path around the skipped pieces. So, in the end, I don't see any situation  including any calculation that you think could help reject pieces faster  that would be better served as a filter run ahead of Renderer that can't be more optimally done by adding code to the Renderer and simply dropping pieces on the floor...? On 8/31/17 1:34 PM, Laurent Bourgès wrote: > Another case: you provided a Test class using a path made with 10000 line segments on the left side. If it is converted > by createStrokedShape(), then the Renderer will again deal with thousands crossings and it will be slow again. Such a case will already be handled by the clipping in the Stroker, though  work that you've already done in these webrevs. > Also, I thought that the Renderer already did basic clipping along the lines that you indicate. It does that on a > persegment basis, but all it would take is a simple test at the top of quadTo() and curveTo() to completely reject > all curves that lie outside the fill region (and simply shadow any part that is entirely to the left so that we > maintain the proper crossings count)... > > Agreed but closed subpaths can also be ignored on either left or right sides like circles, letters... > What do you mean by shadow any part on the left ? The only thing that is interesting about pieces of the path that are to the left of the clip are how they contribute to the winding count at the left edge of the clip. They can all be replaced by segments that simply have the same Y range and a fixed X coordinate of leftepsilon (actually, even epsilon==0 works fine). This can be accomplished using addLine(Ystart, clipLeftX, Yend, clipLeftX). It makes the inner loop process a segment to compute the count, though, but you need that count somehow. > For the Evenodd filling rule, I think it needs exact segment intersections on the left side, so I am focused on the > Nonzero filling rule for now. They are identical. All that matters is that you have the proper starting winding count as you enter the clip from the left. They could be replaced by either a segment with the same "Y range" as I mention above, or they could be replaced by having a value in the segments list that is "starting count", so if you have a segment that is outleft and it goes from Y=10 to Y=20, you simply add (or subtract for reversed lines) one to the "starting count" field for all scanlines from 10>20. > Finally I tried two approach: >  basic subpath outside test (derived from the ClosedPathDetector) to ignore closed subpaths outside of the clip. >  more general clipper that follows the path, detect enter/exit the clip but it needs to insert/remove corner points. I > am improving this latter approach. Consider that your filter that works ahead of the Renderer will need to deal with the following issues:  detecting if the segments are outtop/bottom/right and drop them  A filter will then need to worry how to connect those paths back to the rest  Renderer can just drop them, end of story  detecting if the segments are outleft and manage the winding counts  A filter will need to manage that plus it will have to connect the paths  Renderer can just do addLine() or adjust "scanlinestartingcount", end of story  worrying about paths that loop around the entire clip, perhaps winding several times around the clip before they dive back into the clip rectangle  A filter has to construct a meaningful path to represent that same outcome  Renderer just discards all pieces that aren't outleft and just manages the "starting count" for just the outleft parts If you look at it, you will find that a clip filter for filling paths is a superset of, with more work required than, proper early rejection logic inside the Renderer fooTo() methods... ...jim 
I had another thought here.
If you have some plan where you can identify incoming paths as "probably benefiting from more aggressive clipping logic" vs others that are classified as "most likely will have little to no clipping" and you want to avoid the overhead of having the earlyrejection clipping logic on all paths, then a simple tweak to the design of the Renderer would make it much easier. Right now Renderer is both a "bag of segments with a scanline sampling loop" and it is also a PathConsumer2D. If you want to insert something ahead of it, it makes logical sense to have that delegating class communicate downstream to the Renderer via PathConsumer2D. But, we could remove the PathConsumer2D from Renderer and turn it into just a "bag of segments" that is managed by an external PathConsumer2D helper class. Basically, take all of the PC2D methods in Renderer and move them into an UnclippedFiller class  just cut and paste. The new class will need a pointer to a Renderer object and it will only call r.addLine() and r.fooBreakIntoLines*() calls. It would actually be a very small class since the PC2D interface was such a tiny portion of what Renderer implemented. The new helper class will manage all subpath/moveto/closepath awareness on its own with the Renderer being unaware of such distinctions. This should be computationally identical to the Renderer we have now  no new methods are inserted, they are just moved to a different class. But by separating out the PC2D methods into a separate class, we have the flexibility to have different ways for the PC2D chain to interact with the Renderer. This would let us create an analogous sister class  ClippedFiller  that does the same thing, but adds some early rejection computations as well. This is a simpler design than what you are attempting now because its output is only "segments to add to the bag of segments", not "wellbehaved PC2D paths". But, if there is no easy way to identify paths up front as "we should preclip this" or "not" then this isn't really needed  just add the necessary logic to Renderer instead... ...jim On 8/31/17 4:15 PM, Jim Graham wrote: > First, consider what is handled inside the guts of the Renderer process. > >  It doesn't need to process any segments above or below the clip, they have no impact on the rendered pieces inside the > clip >  It needs to process segments that are outleft only in so far as it needs to come up with a proper crossings count for > the first pixel inside the clip, nothing else about that geometry matters >  It needs to process segments inside the leftright part of the clip on any scanline it is computing and it needs to > know the X locations of each crossing and how the crossing count affects insideness and outsideness >  It can stop processing when it reaches the right edge of the clip as the crossings out there have no impact on > anything that will be rendered > > All of this is already computed on a segmentbysegment basis inside addLine(). > > The only thing missing for curves is that they might be rejected in their entirety, or we might be able to pare them > down to only the pieces that need to be processed. Currently they will be rejected as they feed their pieces to > addLine() and it rejects each segment in turn, but we might be able to short circuit the process by looking at their > control points up front before we run DDA on them. > > If a curve is entirely out/below/right, then Renderer can outright reject it and doesn't need to deal with connecting > pieces of the path, it is only concerned about what ends up in its list of segments  nothing else. A prefilter > noticing the same thing about that segment will know that the result that it wants is for the Renderer to ignore it, but > it will need to deal with complicated logic of how to omit that segment in a way that the subpath/closepath logic of > the Renderer is managed correctly. In other words, it has work to do because it isn't simply inside the Renderer where > we can drop path pieces on the floor with impunity. > > If a curve is more complicated in how it interacts with the top/bot/left/right clip coordinates, then it might still be > rejected, or it might need to be partially rendered. Something is going to need to do some computation to figure that > out. If we try to do those computations before we get to the Renderer, then whatever computations we use to do that > will likely be just as complicated as the DDA work done inside the Renderer. That work as a "prefilter" will also be > complicated in that it will then need to express its results as a "simplified, but connected" path rather than simply > dropping pieces on the floor as the Renderer can do. > > Now, it is possible that we could subdivide a curve that has no simple outcode rejection criteria  for example a > curve that starts above the clip, but horizontally "over" it, extends around the upperright corner of the clip to a > position that is to the right of the clip, but within its vertical bounds. Such a curve would not be rejected by any > "all Y<top" or "all X>right" tests. It might be true that you could cut it at some point on the curve (and you might > even be lucky enough that a midpoint cut would suffice) and each half of the curve would then pass the rejection > criteria, but you'd have to analyze the curve to figure that out. It is just as likely that while the control points > follow the pattern I outlined at the start of this paragraph, the actual traced outline goes inside the clip. You won't > know until you perform some calculations. In the meantime, the Renderer already does a pretty fast DDA subsection of > the curve and those pieces are then rejected by addLine() each in turn. How sure can you be that you can find a > computation for such curves that will be successful in enough cases that you will save time over DDA? How often are > curves even in this particular situation in the first place? If only .1% of curves ever benefit from this analysis then > you might slow down the common case to be slightly faster in a rare case. > > Finally, if there is some calculation that could be performed on such "not immediately rejectable, but possibly outside" > curves to simplify their processing, the best place for those calculations is still in the Renderer where its response > to finding a piece of a curve that is trivially rejectable is to just skip it, rather than a prefilter which will have > to worry about how to connect the path around the skipped pieces. > > So, in the end, I don't see any situation  including any calculation that you think could help reject pieces faster  > that would be better served as a filter run ahead of Renderer that can't be more optimally done by adding code to the > Renderer and simply dropping pieces on the floor...? > > On 8/31/17 1:34 PM, Laurent Bourgès wrote: >> Another case: you provided a Test class using a path made with 10000 line segments on the left side. If it is >> converted by createStrokedShape(), then the Renderer will again deal with thousands crossings and it will be slow again. > > Such a case will already be handled by the clipping in the Stroker, though  work that you've already done in these > webrevs. > >> Also, I thought that the Renderer already did basic clipping along the lines that you indicate. It does that on a >> persegment basis, but all it would take is a simple test at the top of quadTo() and curveTo() to completely reject >> all curves that lie outside the fill region (and simply shadow any part that is entirely to the left so that we >> maintain the proper crossings count)... >> >> Agreed but closed subpaths can also be ignored on either left or right sides like circles, letters... >> What do you mean by shadow any part on the left ? > > The only thing that is interesting about pieces of the path that are to the left of the clip are how they contribute to > the winding count at the left edge of the clip. They can all be replaced by segments that simply have the same Y range > and a fixed X coordinate of leftepsilon (actually, even epsilon==0 works fine). This can be accomplished using > addLine(Ystart, clipLeftX, Yend, clipLeftX). It makes the inner loop process a segment to compute the count, though, > but you need that count somehow. > >> For the Evenodd filling rule, I think it needs exact segment intersections on the left side, so I am focused on the >> Nonzero filling rule for now. > > They are identical. All that matters is that you have the proper starting winding count as you enter the clip from the > left. They could be replaced by either a segment with the same "Y range" as I mention above, or they could be replaced > by having a value in the segments list that is "starting count", so if you have a segment that is outleft and it goes > from Y=10 to Y=20, you simply add (or subtract for reversed lines) one to the "starting count" field for all scanlines > from 10>20. > >> Finally I tried two approach: >>  basic subpath outside test (derived from the ClosedPathDetector) to ignore closed subpaths outside of the clip. >>  more general clipper that follows the path, detect enter/exit the clip but it needs to insert/remove corner points. >> I am improving this latter approach. > > Consider that your filter that works ahead of the Renderer will need to deal with the following issues: > >  detecting if the segments are outtop/bottom/right and drop them >  A filter will then need to worry how to connect those paths back to the rest >  Renderer can just drop them, end of story >  detecting if the segments are outleft and manage the winding counts >  A filter will need to manage that plus it will have to connect the paths >  Renderer can just do addLine() or adjust "scanlinestartingcount", end of story >  worrying about paths that loop around the entire clip, perhaps winding several times around the clip before they dive > back into the clip rectangle >  A filter has to construct a meaningful path to represent that same outcome >  Renderer just discards all pieces that aren't outleft and > just manages the "starting count" for just the outleft parts > > If you look at it, you will find that a clip filter for filling paths is a superset of, with more work required than, > proper early rejection logic inside the Renderer fooTo() methods... > > ...jim 
In reply to this post by Jim Graham5
I want to elaborate on winding count issues for segments to the left of the clip for both winding modes.
All curves have the property that the winding count of any sample point to the right of them is identical to the winding count of a line from their starting point to their ending point. Consider a quad. If it is monotonic, then the observation should be fairly obvious as the curve only ever has one crossing for any scanline and only the X location of that crossing varies and it only varies within the bounds of the X coordinates of all of 3 defining points. Once you are to the right of all 3 X coordinates, the winding count is uniformly a single value over the entire Y range of the (monotonic) quad. Consider a quad with a vertical reversal. If one of the endpoints is higher than the other, then in the area between the Y coordinates of the endpoints it will increase or decrease the winding count by only 1, and the sign of that winding count change will be identical to a segment that connects the two endpoints. For the rest of the quad, the part where it doubles back on itself, those 2 parts of the path cancel each other out. You either have a downward portion that curves into an upward portion, or vice versa. In both cases, that portion has a resulting winding count of 0 because the direction of those 2 parts of the curve are opposite. A cubic is more complicated with more cases to consider, but if you diagram it out you can see that the winding count contribution off to the right of the cubic will be identical in all cases to the winding count contribution of a line segment joining the two endpoints. You can have up to 3 reversals, but all reversals that are above or below the end points will be paired with each other and all reversals within the Y range of the end points will either result in 1 or 3 competing pieces and the 1 or the majority of the 3 will be in the same direction/sign as the direction/sign of the segment between the endpoints. If there are 3 then 2 will cancel out and the remaining one will be the same direction as the endpoint line segment. So, all path segments, regardless of line/quad/cubic that lie entirely to the left of the clip have identical winding count to a simple line segment. And with the proper winding count computed, the winding mode has no impact, the same winding count is appropriate and accurate whether the entire path is EO or NZ... ...jim On 8/31/17 4:15 PM, Jim Graham wrote: >> For the Evenodd filling rule, I think it needs exact segment intersections on the left side, so I am focused on the >> Nonzero filling rule for now. > > They are identical. All that matters is that you have the proper starting winding count as you enter the clip from the > left. They could be replaced by either a segment with the same "Y range" as I mention above, or they could be replaced > by having a value in the segments list that is "starting count", so if you have a segment that is outleft and it goes > from Y=10 to Y=20, you simply add (or subtract for reversed lines) one to the "starting count" field for all scanlines > from 10>20. 
In reply to this post by Jim Graham5
CCing the mailinglists
Hi Jim, On 8/31/17 4:15 PM, Jim Graham wrote:  It can stop processing when it reaches the right edge of the clip as the crossings out there have no impact on anything that will be rendered Not exactly, the Renderer needs at least one crossing on the right side to determine the current span end. However, I added a shortcut to quickly exit from the loop on the right side. To act as you said, a post loop code should be added to see if the count is > 0 and that would mean the current span should be emitted until the right side. The only thing missing for curves is that they might be rejected in their entirety, or we might be able to pare them down to only the pieces that need to be processed. Currently they will be rejected as they feed their pieces to addLine() and it rejects each segment in turn, but we might be able to short circuit the process by looking at their control points up front before we run DDA on them. I totally agree and I already implemented such quad/curve shortcut in my own Renderer variant (minor gain) and that could benefit to either Stroker and the filling case notably on the left / right sides. If a curve is more complicated in how it interacts with the top/bot/left/right clip coordinates, then it might still be rejected, or it might need to be partially rendered. Something is going to need to do some computation to figure that out. If we try to do those computations before we get to the Renderer, then whatever computations we use to do that will likely be just as complicated as the DDA work done inside the Renderer. That work as a "prefilter" will also be complicated in that it will then need to express its results as a "simplified, but connected" path rather than simply dropping pieces on the floor as the Renderer can do. Agreed. I do not want to duplicate such complicated code, only 80% gain (pareto rule) so my current PathClipFilter only rejects trivial segments and rely on the Renderer to efficiently deal with more complex cases. Now, it is possible that we could subdivide a curve that has no simple outcode rejection criteria  for example a curve that starts above the clip, but horizontally "over" it, extends around the upperright corner of the clip to a position that is to the right of the clip, but within its vertical bounds. Such a curve would not be rejected by any "all Y<top" or "all X>right" tests. It might be true that you could cut it at some point on the curve (and you might even be lucky enough that a midpoint cut would suffice) and each half of the curve would then pass the rejection criteria, but you'd have to analyze the curve to figure that out. It is just as likely that while the control points follow the pattern I outlined at the start of this paragraph, the actual traced outline goes inside the clip. You won't know until you perform some calculations. In the meantime, the Renderer already does a pretty fast DDA subsection of the curve and those pieces are then rejected by addLine() each in turn. How sure can you be that you can find a computation for such curves that will be successful in enough cases that you will save time over DDA? How often are curves even in this particular situation in the first place? If only .1% of curves ever benefit from this analysis then you might slow down the common case to be slightly faster in a rare case. As I said, let's try to Keep It Simple Silly for now. Although, I could later perform one subdivision step (line, quad, curve)
for TOP <> LEFT <> BOTTOM <> RIGHT transitions and
try again a trivial reject test (all control points outside) but only
for large enough curves / lines. It will benefit to large filled circles but I agree it is a corner case. Finally, if there is some calculation that could be performed on such "not immediately rejectable, but possibly outside" curves to simplify their processing, the best place for those calculations is still in the Renderer where its response to finding a piece of a curve that is trivially rejectable is to just skip it, rather than a prefilter which will have to worry about how to connect the path around the skipped pieces. I disagree: the Renderer class has already several variants (maintainability issue) and it very complex so I want to leave it untouched as most as possible and externalize that supplementary stage into the rendering pipeline. The Stroker webrev works like a charm and it already performs path filtering. Modifying the Renderer will mean that the path filtering will be done twice or that Stroker should indicate to not filter twice the segments ! So, in the end, I don't see any situation  including any calculation that you think could help reject pieces faster  that would be better served as a filter run ahead of Renderer that can't be more optimally done by adding code to the Renderer and simply dropping pieces on the floor...? I already tried to explain an interesting case: closed subpaths on the left or right sides are bringing lots of edges into the Renderer bag that cost a lot due to the scanline processing (crossing inc, sort, spans ...). I prefer coding an external simplifier compatible with Renderer, than complexifying the Renderer itself to record subpaths, test outcodes that would add more complexity, code lines...
Yes that works well with Stroker. As I explained such huge polyline can be converted to a polygon by calling createStrokedShape() and then rendered by fill(shape):  unclipped: 300ms  (experimental) clipped path: 4ms (twice slower than Stroker as there is twice more segments as the shape was completely stroked) For the Evenodd filling rule, I think it needs exact segment intersections on the left side, so I am focused on the Nonzero filling rule for now. I am still very skeptic with EO rule as I am not sure it was equivalent as shapes can have self intersections ... or curve / line intersections on the left side that could lead to different accumulated count. After reading several times your explanations, I understand that on the left side (outside):  curves / quads can be simplified to a simple line (P0 to P3), but what about intersections in the middle of the curves ? should the Y range be set to min(curveY), max(curveY) that is not easy to solve ...  quad/curve/line segments can not be skipped with the EO rule to preserve the Y ranges properly. Am I right ? Maybe your later approach is interesting to introduce a new starting_counts array along the Y axis to increment / decrement and then it would be possible to totally ignore invisible segments on the left side ? Finally I tried two approach: On right side, Renderer need a 'closing' span edge.  detecting if the segments are outleft and manage the winding counts But addLine() is the origin of the performance issue = extra cost of processing extra crossings !  worrying about paths that loop around the entire clip, perhaps winding several times around the clip before they dive back into the clip rectangle Thanks for the filter specifications I am working on. I will find a compromise between rejecting segments and preserving accuracy while providing better performance for the NZ rule as EO seems too complicated to me (later ?). 20170901 1:37 GMT+02:00 Jim Graham <[hidden email]>: I had another thought here. My Stroker webrev relies on the current Renderer ability to clip properly top/bottom and manages the shape boundaries. My PathClipFiller is only applied in the filling case (low overhead). As your approach is very generic, it would be a good idea to extract that clip part for better maintainability and simplify the Renderer code. However, the Renderer deals with subpixel coordinates so its clip is scaled and both addLine() and fooBreakIntoLines() should be adapted to handle the subpixel scaling factors. 20170901 1:55 GMT+02:00 Jim Graham <[hidden email]>: I want to elaborate on winding count issues for segments to the left of the clip for both winding modes. Thanks as it is not obvious to me ! All curves have the property that the winding count of any sample point to the right of them is identical to the winding count of a line from their starting point to their ending point. But if the polygon has self intersections, then a line can cross the vertical reversal and its position will depend on the exact curve, so the accumulated winding count will be different along the Y axis. A cubic is more complicated with more cases to consider, but if you diagram it out you can see that the winding count contribution off to the right of the cubic will be identical in all cases to the winding count contribution of a line segment joining the two endpoints. You can have up to 3 reversals, but all reversals that are above or below the end points will be paired with each other and all reversals within the Y range of the end points will either result in 1 or 3 competing pieces and the 1 or the majority of the 3 will be in the same direction/sign as the direction/sign of the segment between the endpoints. If there are 3 then 2 will cancel out and the remaining one will be the same direction as the endpoint line segment. But that also means that in the EO case, it is not possible to ignore any line segment on the left side ? And with the proper winding count computed, the winding mode has no impact, the same winding count is appropriate and accurate whether the entire path is EO or NZ... I am still skeptical on the winding rules ... will try to study some concrete examples. Thanks again, Laurent  
Laurent Bourgès 
In reply to this post by Jim Graham5
Jim, Here is the current code for my experimental PathClipFilter only to show you what I have done so far: DMarlingRenderingEngine.getAATileGenerator(): ... // fill shape: final PathIterator pi = norm.getNormalizingPathIterator(rdrCtx, s.getPathIterator(_at)); final int windingRule = pi.getWindingRule(); // note: Winding rule may be EvenOdd ONLY for fill operations ! r = rdrCtx.renderer.init(clip.getLoX(), clip.getLoY(), clip.getWidth(), clip.getHeight(), windingRule); if (windingRule == WIND_NON_ZERO) { DPathConsumer2D pc2d = r; if (rdrCtx.doClip) { pc2d = rdrCtx.transformerPC2D.pathClipper(pc2d); } // TODO: subdivide quad/cubic curves into monotonic curves ? pathTo(rdrCtx, pi, pc2d); }  PathClipper: static final class GeneralPathClipper implements DPathConsumer2D { private DPathConsumer2D out; // Bounds of the drawing region, at pixel precision. private final double[] clipRect; // the outcode of the starting point private int sOutCode = 0; // the current outcode of the current sub path private int cOutCode = 0; GeneralPathClipper(final DRendererContext rdrCtx) { this.clipRect = rdrCtx.clipRect; } GeneralPathClipper init(final DPathConsumer2D out) { this.out = out; // Adjust the clipping rectangle with the renderer offsets final double rdrOffX = DRenderer.RDR_OFFSET_X; final double rdrOffY = DRenderer.RDR_OFFSET_Y; final double[] _clipRect = this.clipRect; _clipRect[0] += rdrOffY; _clipRect[1] += rdrOffY; _clipRect[2] += rdrOffX; _clipRect[3] += rdrOffX; return this; // fluent API } @Override public void pathDone() { out.pathDone(); } @Override public void closePath() { out.closePath(); this.cOutCode = sOutCode; } private void finish() { if (outside) { this.outside = false; out.lineTo(cx0, cy0); } } @Override public void moveTo(final double x0, final double y0) { final int outcode = DHelpers.outcode(x0, y0, clipRect); // basic rejection criteria this.sOutCode = outcode; this.cOutCode = outcode; this.outside = false; out.moveTo(x0, y0); } boolean outside = false; double cx0, cy0; @Override public void lineTo(final double x1, final double y1) { final int outcode0 = this.cOutCode; final int outcode1 = DHelpers.outcode(x1, y1, clipRect); this.cOutCode = outcode1; final int sidecode = (outcode0 & outcode1); // basic rejection criteria: if (sidecode != 0) { // top or bottom or same: if ((outcode0 == outcode1)  ((sidecode & DHelpers.OUTCODE_MASK_T_B) != 0) ) { // corner or crossboundary this.outside = true; // TODO: add to outside stack (throw if never enter again ?) this.cx0 = x1; this.cy0 = y1; return; } else { // corner or crossboundary on left or right side: // TODO: add to outside stack (throw if never enter again ?) // line(P0P1) } } finish(); // clipping disabled: out.lineTo(x1, y1); } @Override public void curveTo(final double x1, final double y1, final double x2, final double y2, final double x3, final double y3) { final int outcode0 = this.cOutCode; final int outcode3 = DHelpers.outcode(x3, y3, clipRect); this.cOutCode = outcode3; // TODO: optimize ? final int outcode1 = DHelpers.outcode(x1, y1, clipRect); final int outcode2 = DHelpers.outcode(x2, y2, clipRect); // basic rejection criteria if ((outcode0 & outcode1 & outcode2 & outcode3) != 0) { // Different quadrant ? if ((outcode0 == outcode3) && (outcode0 == outcode1) && (outcode0 == outcode2)) { // corner or crossboundary this.outside = true; // TODO: add to outside stack (throw if never enter again ?) this.cx0 = x3; this.cy0 = y3; return; } else { // corner or crossboundary // TODO: add to outside stack (throw if never enter again ?) // line(P0P1) finish(); // clipping disabled: out.lineTo(x3, y3); return; } } finish(); // clipping disabled: out.curveTo(x1, y1, x2, y2, x3, y3); } @Override public void quadTo(final double x1, final double y1, final double x2, final double y2) { final int outcode0 = this.cOutCode; final int outcode2 = DHelpers.outcode(x2, y2, clipRect); this.cOutCode = outcode2; // TODO: optimize ? final int outcode1 = DHelpers.outcode(x1, y1, clipRect); // basic rejection criteria if ((outcode0 & outcode1 & outcode2) != 0) { // Different quadrant ? if ((outcode0 == outcode2) && (outcode0 == outcode1)) { // corner or crossboundary this.outside = true; // TODO: add to outside stack (throw if never enter again ?) this.cx0 = x2; this.cy0 = y2; return; } else { // corner or crossboundary // TODO: add to outside stack (throw if never enter again ?) // line(P0P1) finish(); // clipping disabled: out.lineTo(x2, y2); return; } } finish(); // clipping disabled: out.quadTo(x1, y1, x2, y2); } @Override public long getNativeConsumer() { throw new InternalError("Not using a native peer"); } } Here is a screenshot illustrating the remaining paths in Renderer after clipping a 4000x4000 spiral converted as stroked shape: You can see all rounds arround the clip that I expect soon to ignore too as I plan to use a corner stack to remember turining points until the path enters again or go back in reverse order... clip off: ~ 145ms clip on: ~ 106ms 20170901 22:09 GMT+02:00 Laurent Bourgès <[hidden email]>:
 
Laurent Bourgès 
Hi Jim, I made good progress on my PathClipFilter that works now perfectly with many test maps for the NZ rule (EO has artefacts if I enable the filter in that case). PathClipFilter: static final class PathClipFilter implements DPathConsumer2D { private DPathConsumer2D out; // Bounds of the drawing region, at pixel precision. private final double[] clipRect; private final double[] corners = new double[8]; private boolean init_corners = false; private final IndexStack stack; // the outcode of the starting point private int sOutCode = 0; // the current outcode of the current sub path private int cOutCode = 0; private boolean outside = false; private double cx0, cy0; PathClipFilter(final DRendererContext rdrCtx) { this.clipRect = rdrCtx.clipRect; this.stack = (rdrCtx.stats != null) ? new IndexStack(rdrCtx, rdrCtx.stats.stat_pcf_idxstack_indices, rdrCtx.stats.hist_pcf_idxstack_indices, rdrCtx.stats.stat_array_pcf_idxstack_indices) : new IndexStack(rdrCtx); } PathClipFilter init(final DPathConsumer2D out) { this.out = out; // Adjust the clipping rectangle with the renderer offsets final double rdrOffX = DRenderer.RDR_OFFSET_X; final double rdrOffY = DRenderer.RDR_OFFSET_Y; // add a small rounding error: final double margin = 1e3d; final double[] _clipRect = this.clipRect; _clipRect[0] = margin  rdrOffY; _clipRect[1] += margin + rdrOffY; _clipRect[2] = margin  rdrOffX; _clipRect[3] += margin + rdrOffX; init_corners = true; return this; // fluent API } /** * Disposes this instance: * clean up before reusing this instance */ void dispose() { stack.dispose(); } @Override public void pathDone() { out.pathDone(); // TODO: fix possible leak if exception happened // Dispose this instance: dispose(); } @Override public void closePath() { if (outside) { this.outside = false; if (sOutCode == 0) { finish(); } else { stack.reset(); } } out.closePath(); this.cOutCode = sOutCode; } private void finish() { if (!stack.isEmpty()) { if (init_corners) { init_corners = false; // Top Left (0): corners[0] = clipRect[2]; corners[1] = clipRect[0]; // Bottom Left (1): corners[2] = clipRect[2]; corners[3] = clipRect[1]; // Top right (2): corners[4] = clipRect[3]; corners[5] = clipRect[0]; // Bottom Right (3): corners[6] = clipRect[3]; corners[7] = clipRect[1]; } stack.pullAll(corners, out); } out.lineTo(cx0, cy0); } @Override public void moveTo(final double x0, final double y0) { final int outcode = DHelpers.outcode(x0, y0, clipRect); this.sOutCode = outcode; this.cOutCode = outcode; this.outside = false; out.moveTo(x0, y0); } @Override public void lineTo(final double xe, final double ye) { final int outcode0 = this.cOutCode; final int outcode1 = DHelpers.outcode(xe, ye, clipRect); this.cOutCode = outcode1; final int sideCode = (outcode0 & outcode1); // basic rejection criteria: if (sideCode != 0) { // keep last point coordinate before entering the clip again: this.outside = true; this.cx0 = xe; this.cy0 = ye; clip(sideCode, outcode0, outcode1); return; } if (outside) { this.outside = false; finish(); } // clipping disabled: out.lineTo(xe, ye); } private void clip(final int sideCode, final int outcode0, final int outcode1) { // corner or crossboundary on left or right side: if ((outcode0 != outcode1) && ((sideCode & DHelpers.OUTCODE_MASK_T_B) != 0)) { // combine outcodes: final int mergeCode = (outcode0  outcode1); final int tbCode = mergeCode & DHelpers.OUTCODE_MASK_T_B; final int lrCode = mergeCode & DHelpers.OUTCODE_MASK_L_R; // add corners to outside stack: final int off = (lrCode == DHelpers.OUTCODE_LEFT) ? 0 : 2; switch (tbCode) { case DHelpers.OUTCODE_TOP: stack.push(off); // top return; case DHelpers.OUTCODE_BOTTOM: stack.push(off + 1); // bottom return; default: // both TOP / BOTTOM: if ((outcode0 & DHelpers.OUTCODE_TOP) != 0) { // top to bottom stack.push(off); // top stack.push(off + 1); // bottom } else { // bottom to top stack.push(off + 1); // bottom stack.push(off); // top } } } } @Override public void curveTo(final double x1, final double y1, final double x2, final double y2, final double xe, final double ye) { final int outcode0 = this.cOutCode; final int outcode3 = DHelpers.outcode(xe, ye, clipRect); this.cOutCode = outcode3; int sideCode = outcode0 & outcode3; if (sideCode != 0) { sideCode &= DHelpers.outcode(x1, y1, clipRect); sideCode &= DHelpers.outcode(x2, y2, clipRect); // basic rejection criteria: if (sideCode != 0) { // keep last point coordinate before entering the clip again: this.outside = true; this.cx0 = xe; this.cy0 = ye; clip(sideCode, outcode0, outcode3); return; } } if (outside) { this.outside = false; finish(); } // clipping disabled: out.curveTo(x1, y1, x2, y2, xe, ye); } @Override public void quadTo(final double x1, final double y1, final double xe, final double ye) { final int outcode0 = this.cOutCode; final int outcode2 = DHelpers.outcode(xe, ye, clipRect); this.cOutCode = outcode2; int sideCode = outcode0 & outcode2; if (outcode2 != 0) { sideCode &= DHelpers.outcode(x1, y1, clipRect); // basic rejection criteria: if (sideCode != 0) { // keep last point coordinate before entering the clip again: this.outside = true; this.cx0 = xe; this.cy0 = ye; clip(sideCode, outcode0, outcode2); return; } } if (outside) { this.outside = false; finish(); } // clipping disabled: out.quadTo(x1, y1, xe, ye); } @Override public long getNativeConsumer() { throw new InternalError("Not using a native peer"); } }  DHelpers.IndexStack: // a stack of integer indices static final class IndexStack { // integer capacity = edges count / 4 ~ 1024 private static final int INITIAL_COUNT = INITIAL_EDGES_COUNT >> 2; private int end; private int[] indices; // indices ref (dirty) private final IntArrayCache.Reference indices_ref; // used marks (stats only) private int indicesUseMark; private final StatLong stat_idxstack_indices; private final Histogram hist_idxstack_indices; private final StatLong stat_array_idxstack_indices; IndexStack(final DRendererContext rdrCtx) { this(rdrCtx, null, null, null); } IndexStack(final DRendererContext rdrCtx, final StatLong stat_idxstack_indices, final Histogram hist_idxstack_indices, final StatLong stat_array_idxstack_indices) { indices_ref = rdrCtx.newDirtyIntArrayRef(INITIAL_COUNT); // 4K indices = indices_ref.initial; end = 0; if (DO_STATS) { indicesUseMark = 0; } this.stat_idxstack_indices = stat_idxstack_indices; this.hist_idxstack_indices = hist_idxstack_indices; this.stat_array_idxstack_indices = stat_array_idxstack_indices; } /** * Disposes this PolyStack: * clean up before reusing this instance */ void dispose() { end = 0; if (DO_STATS) { stat_idxstack_indices.add(indicesUseMark); hist_idxstack_indices.add(indicesUseMark); // reset marks indicesUseMark = 0; } // Return arrays: // values is kept dirty indices = indices_ref.putArray(indices); } boolean isEmpty() { return (end == 0); } void reset() { end = 0; } void push(final int v) { // remove redundant values (reverse order): int[] _values = indices; final int nc = end; if (nc != 0) { if (_values[nc  1] == v) { // remove both duplicated values: end; return; } } if (_values.length <= nc) { if (DO_STATS) { stat_array_idxstack_indices.add(nc + 1); } indices = _values = indices_ref.widenArray(_values, nc, nc + 1); } _values[end++] = v; if (DO_STATS) { // update used marks: if (end > indicesUseMark) { indicesUseMark = end; } } } void pullAll(final double[] points, final DPathConsumer2D io) { final int nc = end; if (nc == 0) { return; } final int[] _values = indices; for (int i = 0, j; i < nc; i++) { j = _values[i] << 1; io.lineTo(points[j], points[j + 1]); } end = 0; } }
Now all useless rounds are totally discarded from the path sent to the Renderer (removing lots of edges on the left/right sides)
clip on: ~ 68ms for this huge filled spiral ~ 50% faster Could you answer my previous email on EO questions ? How to deal with self intersections or is it possible to skip left segments in the EO case or not ? (I am a bit lost) I need a simple path to test clipping with the EO rule (redudant segments); any idea ? Cheers, Laurent 
Hi all, As Jim is no more available to review & answer my questions on java2d / computer graphics, I need another reviewer on this webrev implementing path clipping in Marlin (huge potential gains). Do you know someone else who can help me in the 2d / prism fields to improve the Marlin renderer even more ? Thanks, Laurent Le 5 sept. 2017 22:41, "Laurent Bourgès" <[hidden email]> a écrit :

Hi Laurent,
Some combination of Phil, Sergey, and I will take a look at this when we can. Perhaps there might be others on these two lists who could lend a helping hand?  Kevin Laurent Bourgès wrote: > Hi all, > > As Jim is no more available to review & answer my questions on java2d / > computer graphics, I need another reviewer on this webrev implementing path > clipping in Marlin (huge potential gains). > > Do you know someone else who can help me in the 2d / prism fields to > improve the Marlin renderer even more ? > > Thanks, > Laurent > > > Le 5 sept. 2017 22:41, "Laurent Bourgès" <[hidden email]> a > écrit : > > >> Hi Jim, >> >> I made good progress on my PathClipFilter that works now perfectly with >> many test maps for the NZ rule (EO has artefacts if I enable the filter in >> that case). >> >> Here is the updated code below to illustrate the approach: >>  use a new IndexStack in (D)Helpers to store only corner indexes (0/1 for >> Top/Bottom Left, 2/3 for Top/Bottom Right) >>  when the segment is out, I now check (L/R case) if the segment ends have >> different outcodes to insert needed corners that can be removed later if a >> segment does the same in the reverse order (same repeated corner is >> cancelled out): see IndexStack.push(int) >> >>  PathClipFilter: >> >> static final class PathClipFilter implements DPathConsumer2D { >> >> private DPathConsumer2D out; >> >> // Bounds of the drawing region, at pixel precision. >> private final double[] clipRect; >> >> private final double[] corners = new double[8]; >> private boolean init_corners = false; >> >> private final IndexStack stack; >> >> // the outcode of the starting point >> private int sOutCode = 0; >> >> // the current outcode of the current sub path >> private int cOutCode = 0; >> >> private boolean outside = false; >> private double cx0, cy0; >> >> PathClipFilter(final DRendererContext rdrCtx) { >> this.clipRect = rdrCtx.clipRect; >> this.stack = (rdrCtx.stats != null) ? >> new IndexStack(rdrCtx, >> rdrCtx.stats.stat_pcf_idxstack_indices, >> rdrCtx.stats.hist_pcf_idxstack_indices, >> rdrCtx.stats.stat_array_pcf_idxstack_indices) >> : new IndexStack(rdrCtx); >> } >> >> PathClipFilter init(final DPathConsumer2D out) { >> this.out = out; >> >> // Adjust the clipping rectangle with the renderer offsets >> final double rdrOffX = DRenderer.RDR_OFFSET_X; >> final double rdrOffY = DRenderer.RDR_OFFSET_Y; >> >> // add a small rounding error: >> final double margin = 1e3d; >> >> final double[] _clipRect = this.clipRect; >> _clipRect[0] = margin  rdrOffY; >> _clipRect[1] += margin + rdrOffY; >> _clipRect[2] = margin  rdrOffX; >> _clipRect[3] += margin + rdrOffX; >> >> init_corners = true; >> >> return this; // fluent API >> } >> >> /** >> * Disposes this instance: >> * clean up before reusing this instance >> */ >> void dispose() { >> stack.dispose(); >> } >> >> @Override >> public void pathDone() { >> out.pathDone(); >> >> // TODO: fix possible leak if exception happened >> // Dispose this instance: >> dispose(); >> } >> >> @Override >> public void closePath() { >> if (outside) { >> this.outside = false; >> >> if (sOutCode == 0) { >> finish(); >> } else { >> stack.reset(); >> } >> } >> out.closePath(); >> this.cOutCode = sOutCode; >> } >> >> private void finish() { >> if (!stack.isEmpty()) { >> if (init_corners) { >> init_corners = false; >> // Top Left (0): >> corners[0] = clipRect[2]; >> corners[1] = clipRect[0]; >> // Bottom Left (1): >> corners[2] = clipRect[2]; >> corners[3] = clipRect[1]; >> // Top right (2): >> corners[4] = clipRect[3]; >> corners[5] = clipRect[0]; >> // Bottom Right (3): >> corners[6] = clipRect[3]; >> corners[7] = clipRect[1]; >> } >> stack.pullAll(corners, out); >> } >> out.lineTo(cx0, cy0); >> } >> >> @Override >> public void moveTo(final double x0, final double y0) { >> final int outcode = DHelpers.outcode(x0, y0, clipRect); >> this.sOutCode = outcode; >> this.cOutCode = outcode; >> this.outside = false; >> out.moveTo(x0, y0); >> } >> >> @Override >> public void lineTo(final double xe, final double ye) { >> final int outcode0 = this.cOutCode; >> final int outcode1 = DHelpers.outcode(xe, ye, clipRect); >> this.cOutCode = outcode1; >> >> final int sideCode = (outcode0 & outcode1); >> >> // basic rejection criteria: >> if (sideCode != 0) { >> // keep last point coordinate before entering the clip >> again: >> this.outside = true; >> this.cx0 = xe; >> this.cy0 = ye; >> >> clip(sideCode, outcode0, outcode1); >> return; >> } >> if (outside) { >> this.outside = false; >> finish(); >> } >> // clipping disabled: >> out.lineTo(xe, ye); >> } >> >> private void clip(final int sideCode, >> final int outcode0, >> final int outcode1) >> { >> // corner or crossboundary on left or right side: >> if ((outcode0 != outcode1) >> && ((sideCode & DHelpers.OUTCODE_MASK_T_B) != 0)) >> { >> // combine outcodes: >> final int mergeCode = (outcode0  outcode1); >> final int tbCode = mergeCode & DHelpers.OUTCODE_MASK_T_B; >> final int lrCode = mergeCode & DHelpers.OUTCODE_MASK_L_R; >> // add corners to outside stack: >> final int off = (lrCode == DHelpers.OUTCODE_LEFT) ? 0 : 2; >> >> switch (tbCode) { >> case DHelpers.OUTCODE_TOP: >> stack.push(off); // top >> return; >> case DHelpers.OUTCODE_BOTTOM: >> stack.push(off + 1); // bottom >> return; >> default: >> // both TOP / BOTTOM: >> if ((outcode0 & DHelpers.OUTCODE_TOP) != 0) { >> // top to bottom >> stack.push(off); // top >> stack.push(off + 1); // bottom >> } else { >> // bottom to top >> stack.push(off + 1); // bottom >> stack.push(off); // top >> } >> } >> } >> } >> >> @Override >> public void curveTo(final double x1, final double y1, >> final double x2, final double y2, >> final double xe, final double ye) >> { >> final int outcode0 = this.cOutCode; >> final int outcode3 = DHelpers.outcode(xe, ye, clipRect); >> this.cOutCode = outcode3; >> >> int sideCode = outcode0 & outcode3; >> >> if (sideCode != 0) { >> sideCode &= DHelpers.outcode(x1, y1, clipRect); >> sideCode &= DHelpers.outcode(x2, y2, clipRect); >> >> // basic rejection criteria: >> if (sideCode != 0) { >> // keep last point coordinate before entering the clip >> again: >> this.outside = true; >> this.cx0 = xe; >> this.cy0 = ye; >> >> clip(sideCode, outcode0, outcode3); >> return; >> } >> } >> if (outside) { >> this.outside = false; >> finish(); >> } >> // clipping disabled: >> out.curveTo(x1, y1, x2, y2, xe, ye); >> } >> >> @Override >> public void quadTo(final double x1, final double y1, >> final double xe, final double ye) >> { >> final int outcode0 = this.cOutCode; >> final int outcode2 = DHelpers.outcode(xe, ye, clipRect); >> this.cOutCode = outcode2; >> >> int sideCode = outcode0 & outcode2; >> >> if (outcode2 != 0) { >> sideCode &= DHelpers.outcode(x1, y1, clipRect); >> >> // basic rejection criteria: >> if (sideCode != 0) { >> // keep last point coordinate before entering the clip >> again: >> this.outside = true; >> this.cx0 = xe; >> this.cy0 = ye; >> >> clip(sideCode, outcode0, outcode2); >> return; >> } >> } >> if (outside) { >> this.outside = false; >> finish(); >> } >> // clipping disabled: >> out.quadTo(x1, y1, xe, ye); >> } >> >> @Override >> public long getNativeConsumer() { >> throw new InternalError("Not using a native peer"); >> } >> } >> >>  DHelpers.IndexStack: >> // a stack of integer indices >> static final class IndexStack { >> >> // integer capacity = edges count / 4 ~ 1024 >> private static final int INITIAL_COUNT = INITIAL_EDGES_COUNT >> 2; >> >> private int end; >> private int[] indices; >> >> // indices ref (dirty) >> private final IntArrayCache.Reference indices_ref; >> >> // used marks (stats only) >> private int indicesUseMark; >> >> private final StatLong stat_idxstack_indices; >> private final Histogram hist_idxstack_indices; >> private final StatLong stat_array_idxstack_indices; >> >> IndexStack(final DRendererContext rdrCtx) { >> this(rdrCtx, null, null, null); >> } >> >> IndexStack(final DRendererContext rdrCtx, >> final StatLong stat_idxstack_indices, >> final Histogram hist_idxstack_indices, >> final StatLong stat_array_idxstack_indices) >> { >> indices_ref = rdrCtx.newDirtyIntArrayRef(INITIAL_COUNT); // 4K >> indices = indices_ref.initial; >> end = 0; >> >> if (DO_STATS) { >> indicesUseMark = 0; >> } >> this.stat_idxstack_indices = stat_idxstack_indices; >> this.hist_idxstack_indices = hist_idxstack_indices; >> this.stat_array_idxstack_indices = >> stat_array_idxstack_indices; >> } >> >> /** >> * Disposes this PolyStack: >> * clean up before reusing this instance >> */ >> void dispose() { >> end = 0; >> >> if (DO_STATS) { >> stat_idxstack_indices.add(indicesUseMark); >> hist_idxstack_indices.add(indicesUseMark); >> >> // reset marks >> indicesUseMark = 0; >> } >> >> // Return arrays: >> // values is kept dirty >> indices = indices_ref.putArray(indices); >> } >> >> boolean isEmpty() { >> return (end == 0); >> } >> >> void reset() { >> end = 0; >> } >> >> void push(final int v) { >> // remove redundant values (reverse order): >> int[] _values = indices; >> final int nc = end; >> if (nc != 0) { >> if (_values[nc  1] == v) { >> // remove both duplicated values: >> end; >> return; >> } >> } >> if (_values.length <= nc) { >> if (DO_STATS) { >> stat_array_idxstack_indices.add(nc + 1); >> } >> indices = _values = indices_ref.widenArray(_values, nc, >> nc + 1); >> } >> _values[end++] = v; >> >> if (DO_STATS) { >> // update used marks: >> if (end > indicesUseMark) { >> indicesUseMark = end; >> } >> } >> } >> >> void pullAll(final double[] points, final DPathConsumer2D io) { >> final int nc = end; >> if (nc == 0) { >> return; >> } >> final int[] _values = indices; >> >> for (int i = 0, j; i < nc; i++) { >> j = _values[i] << 1; >> io.lineTo(points[j], points[j + 1]); >> } >> end = 0; >> } >> } >> >> >> Here is a screenshot illustrating the remaining paths in Renderer after >> >>> clipping a 4000x4000 spiral converted as stroked shape: >>> http://cr.openjdk.java.net/~lbourges/png/SpiralTestdashfalse.ser.png >>> >>> >> Now all useless rounds are totally discarded from the path sent to the >> Renderer (removing lots of edges on the left/right sides) >> >> >> >>> clip off: ~ 145ms >>> clip on: ~ 106ms >>> >>> >> clip on: ~ 68ms for this huge filled spiral ~ 50% faster >> >> >> Could you answer my previous email on EO questions ? >> How to deal with self intersections or is it possible to skip left >> segments in the EO case or not ? >> (I am a bit lost) >> >> I need a simple path to test clipping with the EO rule (redudant >> segments); any idea ? >> >> Cheers, >> Laurent >> >> 
Hi Kevin, Ok I propose to withdraw or postpone this review after JavaOne where we will be able to discuss in a face to face meeting about Marlin & MarlinFX changes for JDK10. I hope the 2d / jfx groups have other Graphics Guru to help, as good as Jim Graham. Cheers, Laurent Le 6 sept. 2017 16:23, "Kevin Rushforth" <[hidden email]> a écrit : Hi Laurent, 
Kevin & Phil, Some news on that issue:I fixed few remaining bugs in either Stroker (1) and in PathClipFilter (2) to have proper & tested clipping in Marlin renderer (2D). It now works perfectly with either NZ or EO winding rules. I need some time to synchronize MarlinFX and then with either OpenJDK forrest (new) or OpenJFX10. If you want the new automated test (long run ~ 20 minutes), I need some time to refactor it as it uses some code from my MapBench tool and have a standalone test class. Will you have time to review such (medium) changes in Marlin2D (Phil ?) and / or MarlinFX (Kevin ?) before the deadline (dec 14th) ? I said 'medium' as the code is quite simple to read but the new CG algorithms to ignore / discard useless path elements are cool but not obvious. Please tell me if you have time and if you prefer a combined (JDK / JFX) webrev or start with 2D or JFX. Cheers, Laurent 20170907 8:52 GMT+02:00 Laurent Bourgès <[hidden email]>:

I think they should be separate webrevs sent to the separate lists
and you should start with 2D
as I can then run the JDK regression tests on it. I know you can theoretically run the open regression tests too (are you ?) but there are some random scattered closed regression tests that so far as I can see can be open sourced .. that I can run but you can't .. I'll at least run the automated ones. I wouldn't call them anything very focused on testing rasterization but I can at least check off that concern .. And yes, I'll make time to review it. phil. On 11/08/2017 01:55 PM, Laurent Bourgès
wrote:

And once we are happy with the 2D webrev, it should be pretty
straightforward to review it for FX.
 Kevin Phil Race wrote: I think they should be separate webrevs sent to the separate lists and you should start with 2D 
Free forum by Nabble  Edit this page 