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