Hi Jim.
Thanks for all your suggestions. I fixed the edge array indexing
issue, the moveTo bug (not assigning x0), and the double
initialization issue. I also improved the emission of the last row
to what you said. The link is the same as the last one I sent.
I considered one more optimization for the scan line iteration:
instead of keeping a crossings array and Arrays.sort'ing it for
every scanline, utilize the fact that the crossings information is
already in the active list, and doesn't need to be copied, so we could
just keep the active list sorted by increasing x crossing (this is the
way things are done in ShapeSpanIterator, which is where I got the idea from).
An added benefit of this (so I thought) would be that the order of the
edges sorted by x crossing would not change very often, and not very much,
in which case keeping it sorted by insertion sort would have (on average)
linear time complexity per scan line, instead of nlogn which is what
Arrays.sort has.
After implementing this, I tested it, and unfortunately it turns out not
to be as good as I expected. It is faster in some tests, but it is a lot
slower in some others.
It's a shame because it simplified things quite a bit (the file became
just 440 lines). With it I was able to remove about 4 or 5 variables from
Renderer,
flips among them so we no longer needed to keep track of orientations, since
we only do that to determine the size of the crossings array.
> For now, it might be simpler to ignore this and revisit that later
> since it isn't going to be common to have large such jumps in the
> middle of most paths.
I agree. Not only that, but even if there are gaps I don't think it
will be much of a problem since very little work has to be done
to traverse scan lines with no crossings.
> Filling the alpha row. I had an interesting optimization here that I
>
> never got around to. Instead of filling the array entries with the
> alpha values, fill them with the deltas of the alpha values. The
> inner
> loop in endRendering then becomes something like:
>
> alpha[pix_x0 ] += NUM_POS - (x0 & MASK);
> alpha[pix_x0+1] += (x0 & MASK);
> alpha[pix_x1 ] -= NUM_POS - (x1 & MASK);
> alpha[pix_x1+1] -= (x1 & MASK);
That's a good idea. I implemented it but I think we should use it whether
it offers big savings or not. It's just a nicer algorithm.
Although, the way it is now, it is a bit misleading (the name of the array is
alpha). I should have commented this a bit more. I don't have time now, I'll do
it on Monday.
Thanks,
Denis.
----- "Jim Graham" <james.gra...@oracle.com> wrote:
> Hi Denis,
>
> More thoughts on Renderer.java.
>
> -- Skipping gaps (minor optimization) --
>
> If there is a gap in the edges in Y, say if a path consists of two
> subpaths, one that covers y=[0..10] and another that covers
> y=[1000..1010], then I think you will iterate over each y value from
> 10
> to 1000, but have no work to do on each scan line. That could
> possibly
> waste a bit of time.
>
> On the other hand, fixing that would have to take into account whether
>
> or not you are done with a given alpha row, so the "NextY" function
> can't simply skip - the skipping has to be done at the higher level in
>
> endRendering - or at least with the cooperation of endRendering.
> Since
> it asks what the "current Y" is near the top of the loop, it could
> detect if the current Y jumped out of the given alpha row, emit it,
> and
> prepare for a new alpha row starting at the new Y...?
>
>
> -- Done with skipping gaps --
>
> -- Alpha accumulation opt --
>
>
> The [pix+1] lines were the gotcha that always confused me when I tried
>
> to do this in the past. Basically if you enter an inside region at 1
>
> subpixel before the end of a pixel then you need to add one to the
> coverage for that pixel. But, starting with the next pixel you want
> the
> total contribution of the interior region to be NUM_POS per pixel, but
>
> you've only added 1 so far - so you have to add the additional amount
> so
> that the total amount added for each "enter" crossing ends up being
> NUM_POS. Similarly, when you decrement for the "exit" crossing you
> need
> to ensure that the total negative delta sums to NUM_POS across the
> pixel
> where the exit happens and the following pixel. Does that make
> sense?
>
> Note that you could still have the "single pixel" optimization which
> would look like:
>
> alpha[pix_x0 ] += (x1 - x0);
> alpha[pix_x0+1] -= (x1 - x0);
>
> and is equivalent to the above 4 lines.
>
> then when you do the RLE, you simply have to use an accumulation as
> you
> scan the alpha row:
>
> byte nextVal = startVal + alphaRow[i];
>
> So, for the cost of an add per pixel as you do the RLE you can avoid
> having to do the loop in the "multiple pixel section" when filling the
>
> alpha array.
>
> I don't think I've ever quantified this optimization so it might be
> better to investigate it after the current code goes in and adopt it
> only if it shows a big savings.
>
> -- Done with alpha accumulation opt --
>
> Something about the "emit last row" code bothers me. First, I would
> guess that the "y == boundsMaxY - 1" test would have already flushed
> the
> row, right? Also, why do the for loop? Why not just flush the row if
>
> it isn't flushed? I kind of feel like the "y == boundsMaxY-1" test
> could be removed from inside the loop and simply test if there is
> unflushed data in the alpha array then just make a call to emitRow()
> with the appropriate values after the loop.
>
> while (hasNext()) {
> ...
> if ((y & MASK) == MASK) {
> emitRow(...);
> pix_min,max = MAX,MIN;
> }
> }
> if (pix_min < pix_max) {
> emitRow(...);
> }
>
> Am I missing something?
>
> So, the upshot is that I didn't find anything wrong. You can take or
>
> leave my suggestions for improvements as you see fit and maybe save
> some
> of them for a second round after this goes back...
>
> ...jim
>
> On 7/29/2010 2:16 PM, Denis Lila wrote:
> > Hello Jim.
> >
> > I made the changes you point out, except for your second point
> > (I don't have time to think about it right now).
> >
> > I stopped precomputing m00_2_m01_2 because it was only being
> > used in one place. But I guess it worth it to precompute it
> > if it's going to be used often (and computeOffset is called
> > for every line).
> >
> > The new webrev is at
> http://icedtea.classpath.org/~dlila/webrevs/fpBetterAAv2/webrev/
> >
> > Thanks,
> > Denis.
