[OpenJDK 2D-Dev] X11 uniform scaled wide lines and dashed lines; STROKE_CONTROL in Pisces

[Denis Lila]

Hi Jim.

I removed the cubic and quadratic lists and am now flattening
everything as it comes in, like you suggested. I ran some AA
benchmarks and the curves test was about 15% faster.

Then I started using your insertion sort in the only edges version
and re ran the benchmarks. Curves improved from 15% better to 20-22%
and lines improved from nothing to 2-20%, depending on how vertical
the lines were.

I didn't expect that the sorting would make this much difference.
But, it does, so I think it is worth it to work more on it; therefore,
next I will implement the bucket sort you suggested.

> If we moved to a Curve class or some other way to 
> consolidate the 3 lists (may be easier in native code), this might win
> in more cases...

Does that mean you no longer think we should flatten every curve as soon
as we get it?

Regards,
Denis.

----- "Jim Graham" <james.graham at oracle.com> wrote:

> Hi Denis,
> 
> On 10/26/2010 6:58 AM, Denis Lila wrote:
> >> 90% (guesstimate) of the time edges do not cross each other, thus
> if
> >> you sort the crossings without reordering the active edges then you
> just
> >> end up doing the same sorting work (same swaps) on the next
> scanline.  My
> >> SpanShapeIterator code actually reordered the edges on every
> sample
> >> line to match their current X coordinates in a way that involved 1
> compare
> >> per edge that was processed and only occasionally a swap of 2 edge
> >> pointers.  It would basically eliminate the sort at line 149 at
> the
> >> cost of only doing a compare in the nextY processing for the very
> very
> >> common case.
> >
> > I also implemented this some time ago. I didn't keep it because it
> slowed
> > things down a bit. However, I only tested it with very complex and
> large
> > paths, and in hindsight, I shouldn't have based my decision on that,
> so I
> > will re-implement it.
> 
> I tried using this new rasterizer in FX and I had a test case which
> had 
> a few shapes that were essentially zig-zaggy shapes on the top and 
> bottom and fills between the zigzags (kind of like a seismic chart
> with 
> fills between the pen squiggles).
> 
> When I added a simple sort of the linear edges the performance nearly
> 
> doubled in speed.  Here is the code I replaced your quad-next-edge
> loop 
> with:
> 
>              for (int i = elo; i < ehi; i++) {
>                  int ptr = edgePtrs[i];
>                  int cross = ((int) edges[ptr+CURX]) << 1;
>                  if (edges[ptr+OR] > 0) {
>                      cross |= 1;
>                  }
>                  edges[ptr+CURY] += 1;
>                  edges[ptr+CURX] += edges[ptr+SLOPE];
>                  int j = crossingIdx;
>                  while (--j >= 0) {
>                      int jcross = crossings[j];
>                      if (cross >= jcross) {
>                          break;
>                      }
>                      crossings[j+1] = jcross;
>                      edgePtrs[elo+j+1] = edgePtrs[elo+j];
>                  }
>                  crossings[j+1] = cross;
>                  edgePtrs[elo+j+1] = ptr;
>                  crossingIdx++;
>              }
> 
> I then did a conditional sort, moved to right after the qlo->qhi and 
> clo->chi loops:
> 
>              for (int i = qlo; i < qhi; i++) {
>                  // same stuff
>              }
>              for (int i = clo; i < chi; i++) {
>                  // same stuff
>              }
>              if (qhi > qlo || chi > clo) {
>                  Arrays.sort(crossings, 0, crossingIdx);
>              }
> 
> In the case of my test case where I only had a polygon to fill, the 
> performance doubled.  Obviously I didn't do much for the case where 
> there were curves because this was just a quick hack to see the value
> of sorting the edges.
> 
> 			...jim