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
