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
