[OpenJDK 2D-Dev] RFR JDK-8184429: Path clipper added in Marlin2D & MarlinFX 0.8.0
james.graham at oracle.com
Thu Aug 31 23:15:05 UTC 2017
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
- 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
> 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...
More information about the 2d-dev