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

[Jim Graham]

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.

Still, there is an optimization to be made there.  I'm not sure if I 
ever submitted a bug against it, but the use of Area is only to 
facilitate getClip() and even then, it is only to facilitate iterating 
the geometry of that return value.  That call is extremely rarely used 
and when it is used, it is often to save the clip so it can be set back 
on the graphics, but the caller never independently iterates its 
geometry.  To that end, we could modify SG2D's clipping code to perform 
Region intersections instead and simply save copies of all input clips 
and lazily compute the geometry only if someone actually retrieved and 
iterated it manually.  Even setClip(getClip()) could avoid Area by 
simply returning an "IntersectedList" object that listed all of the 
component shapes - it would use Area only if someone called 
getPathIterator() on it - and when we see it again in setClip() we 
simply extract its component shapes rather than reading its geometry.

But, again, that optimization is independent of dasher/stroker doing 
extra work on a zoomed shape.

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

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

				...jim