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

Wed Apr 8 16:30:33 UTC 2015

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> 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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.openjdk.java.net/pipermail/2d-dev/attachments/20150408/015667fb/attachment.html>