RFR JDK-8184429: Path clipper added in Marlin2D & MarlinFX 0.8.0

classic Classic list List threaded Threaded
28 messages Options
12
Reply | Threaded
Open this post in threaded view
|

RFR JDK-8184429: Path clipper added in Marlin2D & MarlinFX 0.8.0

Laurent Bourgès
Hi,

Please review Marlin/FX upgrades that provide an efficient path clipper in Stroker (float / double variants) fixing the bug JDK-8184429

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 compensated-sum approach (later patch)

Cheers,
Laurent Bourgès
Reply | Threaded
Open this post in threaded view
|

Re: RFR JDK-8184429: Path clipper added in Marlin2D & MarlinFX 0.8.0

Jim Graham-5
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 JDK-8184429
> <https://bugs.openjdk.java.net/browse/JDK-8184429>
>
> Marlin2D patch (jdk10):
> http://cr.openjdk.java.net/~lbourges/marlin/marlin-080.0/
> MarlinFX patch (openjfx10):
> http://cr.openjdk.java.net/~lbourges/marlinFX/marlin-080.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
> compensated-sum approach (later patch)
>
> Cheers,
> Laurent Bourgès
>
Reply | Threaded
Open this post in threaded view
|

Re: RFR JDK-8184429: Path clipper added in Marlin2D & MarlinFX 0.8.0

Laurent Bourgès
Hi Jim,

Thanks for your comments, it helped refining the webrev.

Here are my answers:

2017-08-26 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):
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 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...

                                ...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 JDK-8184429
<https://bugs.openjdk.java.net/browse/JDK-8184429>


Marlin2D patch (jdk10):
http://cr.openjdk.java.net/~lbourges/marlin/marlin-080.0/
MarlinFX patch (openjfx10):
http://cr.openjdk.java.net/~lbourges/marlinFX/marlin-080.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
compensated-sum approach (later patch)

Cheers,
Laurent Bourgès




--
--
Laurent Bourgès
Reply | Threaded
Open this post in threaded view
|

Re: RFR JDK-8184429: Path clipper added in Marlin2D & MarlinFX 0.8.0

Jim Graham-5
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:
>
> 2017-08-26 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/marlin-080.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

Reply | Threaded
Open this post in threaded view
|

Re: RFR JDK-8184429: Path clipper added in Marlin2D & MarlinFX 0.8.0

Laurent Bourgès
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]> 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:

2017-08-26 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/marlin-080.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


Reply | Threaded
Open this post in threaded view
|

Re: RFR JDK-8184429: Path clipper added in Marlin2D & MarlinFX 0.8.0

Jim Graham-5
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
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)...

                        ...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:
>
>         2017-08-26 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/marlin-080.1/
>         <http://cr.openjdk.java.net/~lbourges/marlin/marlin-080.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
>
>
Reply | Threaded
Open this post in threaded view
|

Re: RFR JDK-8184429: Path clipper added in Marlin2D & MarlinFX 0.8.0

Jim Graham-5
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 pre-filter 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 piggy-back 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
> 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)...
>
>              ...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:
>>
>>         2017-08-26 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/marlin-080.1/
>>         <http://cr.openjdk.java.net/~lbourges/marlin/marlin-080.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
>>
>>
Reply | Threaded
Open this post in threaded view
|

Re: RFR JDK-8184429: Path clipper added in Marlin2D & MarlinFX 0.8.0

Laurent Bourgès
In reply to this post by Jim Graham-5
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 even-odd 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 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 ?

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.

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.

Thanks for your advices,
Laurent
Reply | Threaded
Open this post in threaded view
|

Re: RFR JDK-8184429: Path clipper added in Marlin2D & MarlinFX 0.8.0

Jim Graham-5
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
Reply | Threaded
Open this post in threaded view
|

Re: RFR JDK-8184429: Path clipper added in Marlin2D & MarlinFX 0.8.0

Jim Graham-5
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
Reply | Threaded
Open this post in threaded view
|

Re: RFR JDK-8184429: Path clipper added in Marlin2D & MarlinFX 0.8.0

Jim Graham-5
In reply to this post by Jim Graham-5
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 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.
Reply | Threaded
Open this post in threaded view
|

Fwd: RFR JDK-8184429: Path clipper added in Marlin2D & MarlinFX 0.8.0

Laurent Bourgès
In reply to this post by Jim Graham-5
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 <[hidden email]>:
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 <[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.

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
Reply | Threaded
Open this post in threaded view
|

Re: RFR JDK-8184429: Path clipper added in Marlin2D & MarlinFX 0.8.0

Laurent Bourgès
In reply to this post by Jim Graham-5
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 cross-boundary
                    this.outside = true;
                    // TODO: add to outside stack (throw if never enter again ?)
                    this.cx0 = x1;
                    this.cy0 = y1;
                    return;
                } else {
                    // corner or cross-boundary on left or right side:
                    // TODO: add to outside stack (throw if never enter again ?)
//                    line(P0-P1)
                }
            }
            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 cross-boundary
                    this.outside = true;
                    // TODO: add to outside stack (throw if never enter again ?)
                    this.cx0 = x3;
                    this.cy0 = y3;
                    return;
                } else {
                    // corner or cross-boundary
                    // TODO: add to outside stack (throw if never enter again ?)
//                    line(P0-P1)

                    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 cross-boundary
                    this.outside = true;
                    // TODO: add to outside stack (throw if never enter again ?)
                    this.cx0 = x2;
                    this.cy0 = y2;
                    return;
                } else {
                    // corner or cross-boundary
                    // TODO: add to outside stack (throw if never enter again ?)
//                    line(P0-P1)

                    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

TODO: handle corner points & turns arround / reverse the clip

Cheers,
Laurent


2017-09-01 22:09 GMT+02:00 Laurent Bourgès <[hidden email]>:
Dear Jim,

I am not so good at explaining my early solution for NZ rule in english:
- it mimics the Stroker approach
- it skips all intermediate segments outside (except at corners ie different outcodes)
- preserve only the last point of the entering segment

So mostly invisible segments on the left and right sides are skipped from the original that makes the Renderer only processing visible segments like in the Stroker case where I opened the path.

It improves the performance as less left / right segments are processed in addLine(). For now the Renderer accepts all segments and only rejects top/bottom parts and keeps all left/right edges in its processing: that costs a lot.

I think we are discussing two different things.  I thought you were considering a separate filter for clipping filled only paths.  I agree that the Stroker webrev is still needed for stroked paths.  We should also create one for dashed paths that will clip before dashing.  There are multiple stages at which we can clip to reduce processing.

Exactly I also like the pipeline approach that decouples stages into different parts.

I take that case into account.  How is a prefilter that excludes those segments any simpler than the Renderer rejecting them itself?

Keep in mind that they are already rejected.  Renderer.addLine() already does this.  In the case of a polygon, there isn't much code you can reduce because it goes from the loop that feeds the path in the rendering engine directly to Renderer.move/lineTo() which goes directly to addLine() which rejects all of those segments.

Not on the left / right side.
Closed subpaths or extra segments can be ignored for NZ rule = only keeping the path closed properly matters.

Will send you the current code to illustrate the basic filter asap.

In the case of curves, the path is nearly as direct, but first you run a DDA on it to break it into lines.  Simply modifying Renderer.quadTo and cubicTo to perform quick-rejection would be a very simple change (certainly simpler than adding a new class to do that) and would reject all of those curved segments much faster...

Agreed, I have done it in the past and can provide the change.

Laurent




--
--
Laurent Bourgès
Reply | Threaded
Open this post in threaded view
|

Re: RFR JDK-8184429: Path clipper added in Marlin2D & MarlinFX 0.8.0

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

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 = 1e-3d;

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

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
Reply | Threaded
Open this post in threaded view
|

Re: RFR JDK-8184429: Path clipper added in Marlin2D & MarlinFX 0.8.0

Laurent Bourgès
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 = 1e-3d;

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

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
Reply | Threaded
Open this post in threaded view
|

Re: RFR JDK-8184429: Path clipper added in Marlin2D & MarlinFX 0.8.0

Kevin Rushforth
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 = 1e-3d;
>>
>>             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 cross-boundary 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/SpiralTest-dash-false.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
>>
>>    
Reply | Threaded
Open this post in threaded view
|

Re: RFR JDK-8184429: Path clipper added in Marlin2D & MarlinFX 0.8.0

Laurent Bourgès
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,

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 = 1e-3d;

            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 cross-boundary 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/SpiralTest-dash-false.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

   
Reply | Threaded
Open this post in threaded view
|

Re: RFR JDK-8184429: Path clipper added in Marlin2D & MarlinFX 0.8.0

Laurent Bourgès
Kevin & Phil,

Some news on that issue:
I successfully managed to finish the Path clipping support in Marlin 0.8.2 (release last week):

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.

To ensure detecting any artefact between Clipping Off vs On, I implemented a 'basher' test (as recommended by Jim) that renderers 10 000 random polygons (5 -> 9 -> 50 line segments or mixed with line / quads / cubics) ( whose point coordinates are in [-50 to 150] ) to a 100x100 buffered image with or without clipping enabled (using a system property at runtime). Of course, all output pixels are compared and any pixel difference is considered as a failure.

The new ShapeClipTests tests all stroke combinations (cap / join / with or without dashes / closed or not / EO or NZ rule) and also fills (closed or not / EO or NZ rule) => 170 tests run OK

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


2017-09-07 8:52 GMT+02:00 Laurent Bourgès <[hidden email]>:
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,

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
Reply | Threaded
Open this post in threaded view
|

Re: RFR JDK-8184429: Path clipper added in Marlin2D & MarlinFX 0.8.0

Phil Race
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:
Kevin & Phil,

Some news on that issue:
I successfully managed to finish the Path clipping support in Marlin 0.8.2 (release last week):

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.

To ensure detecting any artefact between Clipping Off vs On, I implemented a 'basher' test (as recommended by Jim) that renderers 10 000 random polygons (5 -> 9 -> 50 line segments or mixed with line / quads / cubics) ( whose point coordinates are in [-50 to 150] ) to a 100x100 buffered image with or without clipping enabled (using a system property at runtime). Of course, all output pixels are compared and any pixel difference is considered as a failure.

The new ShapeClipTests tests all stroke combinations (cap / join / with or without dashes / closed or not / EO or NZ rule) and also fills (closed or not / EO or NZ rule) => 170 tests run OK

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


2017-09-07 8:52 GMT+02:00 Laurent Bourgès <[hidden email]>:
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,

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

Reply | Threaded
Open this post in threaded view
|

Re: RFR JDK-8184429: Path clipper added in Marlin2D & MarlinFX 0.8.0

Kevin Rushforth
And once we are happy with the 2D webrev, it should be pretty straight-forward 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
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:
Kevin & Phil,

Some news on that issue:
I successfully managed to finish the Path clipping support in Marlin 0.8.2 (release last week):

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.

To ensure detecting any artefact between Clipping Off vs On, I implemented a 'basher' test (as recommended by Jim) that renderers 10 000 random polygons (5 -> 9 -> 50 line segments or mixed with line / quads / cubics) ( whose point coordinates are in [-50 to 150] ) to a 100x100 buffered image with or without clipping enabled (using a system property at runtime). Of course, all output pixels are compared and any pixel difference is considered as a failure.

The new ShapeClipTests tests all stroke combinations (cap / join / with or without dashes / closed or not / EO or NZ rule) and also fills (closed or not / EO or NZ rule) => 170 tests run OK

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


2017-09-07 8:52 GMT+02:00 Laurent Bourgès <[hidden email]>:
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,

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

12