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

[Jim Graham]

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