[OpenJDK 2D-Dev] [OpenJDK Rasterizer] Path2d needRoom very slow for huge paths

[Jim Graham]

Hi Laurent,

Before we take a long time to implement a solution that prefilters the 
geometry as the applications do, we should see how much gain we can get 
from simply doing early rejection in the renderers (that has been 
missing since they were created and likely led to the need at the 
application level).  Early rejection should be a task of a few days...

			...jim

On 4/8/15 9:30 AM, Laurent Bourgès wrote:
> Jim,
>
> thanks for your long and detailled response.
>
> As previously said, working on polygon clipping is a new R&D task that
> will take a lot of time to implement & test for a general usage or in
> particular for pisces / marlin renderers. For 2 years, it remains in my
> TODO list ... as many applications already have their own (custom) solution.
>
> Please read my comments below:
> Le 7 avr. 2015 00:38, "Jim Graham" <james.graham at oracle.com
> <mailto:james.graham at oracle.com>> a écrit :
>
>
>     On 4/4/15 3:15 AM, Laurent Bourgès wrote:
>
>         I may look at this implementation to get some idea or maybe I should
>         just optimize openjdk's Area class that has also a clipping
>         implementation but is known too be very slow as the shape complexity
>         increases !
>
>
>     The Area class is mostly a red herring.  It doesn't usually get
>     involved in basic rendering of shapes.  In particular:
>
>     - rectangular clips never touch it
>     - shaped clips never touch it as long as they are the only clip involved
>     - clipping to multiple shapes at least one of which is
>     non-rectangular will involve Area only in bookkeeping in the SG2D
>     class and the Area class won't be necessary for the rendering phase
>     at all
>
>     Basically SG2D has an API contract for getClip() to satisfy.  It has
>     been returning geometrical representations of the intersection of
>     all clips, in user space.  For actual rendering we boil the shapes
>     down into a Region object which is a list of pixel rectangles.  If
>     all clip() calls are subclasses of Rectangle2D then we just do basic
>     Rectangle2D intersections which are fast and we compute the pixels
>     that fall within that geometric rectangle and save that as a
>     Region.  If there is a single call to clip() or setClip() with a
>     non-rectangular shape then we just save (a copy of) that Shape for
>     returning from getClip() and we rasterize it to a Region for actual
>     clipping.
>
>     Only when someone does something like "setClip(circle); clip(other
>     shape);" do we use Area to compute the intersection of the two once,
>     then we remember that geometry for getClip() and we rasterize it to
>     a Region for the rendering routines.
>
>     Either way, that is likely orthogonal to the issue that many of the
>     applications here face which is that they use basic rectangular
>     clipping (or even if they use just a single shape for clipping) and
>     then they render huge paths that are zoomed in and we perform
>     computation in the dasher/stroker that doesn't affect the pixels
>     rendered.  That has nothing to do with the work that we did with Area.
>
>
> First I mentioned the Area class because it seems to me it is the only
> public Java2D API able to clip a complex polygon against any shape using
> Area.intersect(Area): javadoc says 'Sets the shape of this |Area| to the
> intersection of its current shape and the shape of the specified |Area|'.
>
> To answer Andrea's first needs, is there any public JDK API able to
> efficiently clip a complex polygon to a rectangular area ? Having such
> an implementation in the JDK would avoid using third-party libraries ...
> and could be used in the Java2D pipeline too.
>
> In think that the polygon simplification is already implemented by
> Path2D.getPathIterator(flatness) ?
>
>
> I will focus now on clipping polygon at the renderer level (not public
> API) to render shapes as fast as possible:
>
>     But, again, that optimization is independent of dasher/stroker doing
>     extra work on a zoomed shape.
>
>
> As andrea explained, any application can clip / simplify its shapes
> before rendering or let the renderer do the job.
>
> If a shape is already clipped (within bounds), there will be a
> performance overhead to clip it again !
>
>
>         Jim, could you point all clipping implentations in openjdk (java
>         or c)
>         that I can study to create my own ?
>
>
>     For filled paths, the Pisces and Marlin renderers already deal with
>     clipping in the Renderer, but it is at the addLine() level.  For a
>     quad or cubic that is entirely above or below or to the right of the
>     clip we could just return early from addQuad and addCubic.  For
>     curves to the left, we only need to insert a token line between the
>     endpoints so that the line scanning code can determine the correct
>     winding count as segments enter the clip from the left.  It won't
>     save much on memory since all of the resulting addLine() calls from
>     those addQuad() and addCubic() calls get dropped on the floor
>     anyway, so this just saves computation.
>
>
> Pisces / Marlin only performs clipping on Y range [boundsMinY;
> boundsMaxY [ but keeps all extra edges on the left or right side !
> So a better clipping algorithm (criteria) could give benefits but of
> course, less than in the following use case:
>
>     But, for stroked paths, we ignore the clip entirely as we dash and
>     widen the path and for these use cases of extremely large paths or
>     complicated paths that might be viewed under a large scale we end up
>     doing a lot of unnecessary computation and generate intermediate
>     path segments for a lot of segments that never appear.
>
>
> As you said, both Stroker and Dasher are creating a lot of segments that
> may be ignored at the Renderer level (Y range clip); but I think it is
> very critical with dash strokes.
>
> For example, if you render a dashed box [0 0 1000 10] displayed at a
> high zoom level (X 100), you will have its pixel coordinates = [0 0
> 100000 1000]; with a 1px dash, it will generate 100k dashes on the x-axis.
>
> On a typical 2000px wide image, it represents a lot of cpu waste: the
> clipped dashed box would be only 2000 px ie only 2% dashes !
>
> I agree the dash phase is problematic but in such situation, who really
> cares (decoration) ?
> Let's use the Java2D quality rendering hint (speed or quality) to adapt
> the clipping strategy ?
>
> Anyway you're right, that the dasher could iterate but only emit a
> "visible" dashes (clipping).
>
>     I'm not sure that existing clipping code applies, but the following
>     may prove helpful:
>     - ShapeSpanIterator.c has a non-AA rasterizer that does early
>     elimination in the subdivideQuad/Cubic functions
>     - DrawPath.c and FillPath.c use ProcessPath.c - I've never been a
>     fan of the complexity in this renderer since complexity often
>     correlates with missing something in the bigger picture, but I'll
>     note that it also eliminates quads and cubics early as it iterates
>     through them.  Also, this rendering engine only deals with thin
>     1-pixel strokes, it doesn't handle wide lines and paths.
>     - DrawLine.c and LineUtils.h contain some basic outcode logic for
>     single bresenham line segments
>
>
> So there is no Java clipping code other than the Area class ?
>
> Thanks for the info: I will have a look and see if I can understand
> curve clipping as it seems to me quite complex !
>
>
> Few more comments:
> - the output rectangle clip (image) is NOT the input clip when affine
> transforms are in use: translation and scaling is fine but rotation or
> shearing introduce rectangle deformations !
> => I like the Cohen-Sutherland algorithm but it will not work (rectangle
> expected) but the Cohen–Sutherland or Cyrus-Beck algorithms should be
> better (parametric edge equations)
>
> - affine transforms modify the stroke width and may lead to cap / join
> deformations ... so the clipping algorithm must use a "safe" margin
> arround the clip rectangle (tolerance) ...
>
> Finally I hope it is possible to implement such a polygon clipping
> algorithm as a new PathConsumer with a 4-stage pipeline (top, left,
> right, bottom) to avoid memory overhead and only emit clipped segments
> (and curves) in the renderer pipeline.
>
> Laurent