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

[Laurent Bourgès]

CCing the mailing-lists

Hi Jim,

I read carefully your very good inputs on clipping / filtering in both
Renderer or PreFilter.

Here are my comments (in the discussion order):

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 "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.
>

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 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.
>

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 pre-filter 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...


>
> 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.
>

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 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.
>

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:
>> - 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
>

On right side, Renderer need a 'closing' span edge.


> - 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
>

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
>     - 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
>

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 ?).


2017-09-01 1:37 GMT+02:00 Jim Graham <james.graham at oracle.com>:

> 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...
>

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.


2017-09-01 1:55 GMT+02:00 Jim Graham <james.graham at oracle.com>:

> 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.
>
> 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.
>

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.
>
> 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.
>

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