[OpenJDK 2D-Dev] Various fixes to pisces stroke widening code

[Denis Lila]

> >> 721 - Arrays.sort()
> > 
> >     I thought about using this, but I did some measurements, and it
> turns out that 
> > Arrays.sort() is a bit slower if the portion of the array being
> sorted has fewer
> > than about 70 elements.
> 
> I wonder what the typical number of elements is.  Is this sorting 
> crossings per line?  Then simple primitives like circles should only 
> have 2 per line, right?  Is it worth testing for really small numbers of 
> elements (much lower than 70) and doing a manual sort?  Or am I 
> misunderstanding what is being sorted there?

    That's correct. For every scan line, we're sorting the crossings on that
scan line, so filling a circle would have 2 per line (drawing it would have
4 per line (for most lines, anyway)).

    I'm not sure if it's worth it. On one hand, the performance benefits would be
minimal (because for small numbers of elements, just about anything will be fast
and even if insertionSort is 200% faster than quicksort it won't make much difference).
    On the other hand, checking for, say crossingIndices[i] - start < 50 doesn't cost
us much, and I already implemented and tested insertionSort.

    I think we should just use Arrays.sort all the time, just to keep the file as small as
possible.

> If you look for something like the native code for 
> sun/java2d/pipe/ShapeSpanIterator.c you will see the way I typically 
> like to do edge setup and enumeration.
> 
> That code uses the "half open interval" approach for both X and Y
> intervals.
> 
> I then sort the edge list by "leading Y" and then move through the
> edges 
> using the following manner (kind of like an inch worm eating the
> edges, 
> maintaining a pointer to the beginning and end of an "active list" of
> 
> edges that are in play at any given time by virtue of having their Y 
> range intersect the current sampling Y).  Note that I use an array of
> 
> edges and then a parallel array of pointers into the edges so that I
> can 
> sort just the pointers and avoid moving tons of edge data around. 
> Also, 
> later when I eliminate edges from the active list I just move their 
> pointers into and out of view rather than having to copy the edge
> data. 
>   It is harder to do an array of pointers in Java, though - perhaps an
> 
> array of indices?  Here is some basic pseudocode:
> 
> start with lo and hi pointing at index 0 in edge list.
> until edge list is exhausted {
>      process edges between lo and hi (empty on first pass)
>      scan from hi to lo and toss any edges that are exhausted
>          (compacting remaining pointers towards hi)
>      keep incrementing hi to accept any new edges coming into play
>      process edges between lo and hi to increment to the next Y
>          (note that new edges from previous step may not
>           need any processing in this stage if their starting
>           Y equals the next Y to be sampled)
> }
> 
> Gradually lo and hi make their way through the list.  The edges above
> hi 
> are always sorted in order of when they may come into play as we move
> 
> downward in Y.  The edges between lo and hi are also usually kept
> sorted 
> by their current X so that the stage that processes them into spans
> can 
> just run through them.  The edges below lo are usually random garbage
> 
> because no care was taken during the "pruning" step to worry about
> what 
> happens to the pointer table down there as lo is incremented (the 
> algorithm only ever looks up the array of pointers).
> 
> I hope that helps...

That does help.
Thanks a lot,
Denis.