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

[Jim Graham]

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" <james.graham at oracle.com <mailto:james.graham at oracle.com>> 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 <james.graham at oracle.com <mailto:james.graham at oracle.com>
>>         <mailto:james.graham at oracle.com <mailto:james.graham at oracle.com>>>:
>>
>>
>>              [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
>>
>>