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

[Jim Graham]

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

			...jim