[OpenJDK 2D-Dev] RFR JDK-8184429: Path clipper added in Marlin2D & MarlinFX 0.8.0

[Jim Graham]

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 early-rejection 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 scan-line 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 sub-path/moveto/close-path 
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 "well-behaved PC2D paths".

But, if there is no easy way to identify paths up front as "we should pre-clip 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 out-left 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 left-right 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 segment-by-segment 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 pre-filter 
> 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 sub-path/close-path 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 "pre-filter" 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 sub-divide a curve that has no simple out-code rejection criteria - for example a 
> curve that starts above the clip, but horizontally "over" it, extends around the upper-right 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 pre-filter 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
>>     per-segment 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 left-epsilon (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 Even-odd filling rule, I think it needs exact segment intersections on the left side, so I am focused on the 
>> Non-zero 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 out-left 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 sub-paths 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 out-top/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 out-left 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 "scanline-starting-count", 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 out-left and
>       just manages the "starting count" for just the out-left parts
> 
> If you look at it, you will find that a clip filter for filling paths is a super-set of, with more work required than, 
> proper early rejection logic inside the Renderer fooTo() methods...
> 
>                  ...jim