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.gra...@oracle.com
<mailto:james.gra...@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
