[OpenJDK 2D-Dev] sun.java2D.Pisces renderer Performance and Memory enhancements

[Jim Graham]

Hi Laurent,

On 5/2/13 1:48 AM, Laurent Bourgès wrote:
>     xc = computed crossing value for the current scan line;
>     ceil(xc - 0.5);
>
>
> Agreed; however, pisces code never performs such rounding: for me,
> ceil(x - 0.5) means (int) Math.round(x).

(int) Math.round(x) is almost the same function, but the 0.5's map the 
wrong way.  3.5 gets mapped to 4 which implies that pixel #4 is the 
first on, or first off.  But, the first pixel to change is pixel #3 in 
that case.  For all other values it is the same.  ceil(x-0.5) reverses 
the "open interval of rounding" to bias halfway points down instead of up.

>     I wanted to get that out to see if we were on the same page or if
>     there was another way of doing the math that you are familiar with
>     that might also make things easier.
>
> Perfect and very clear. I will then check pisces rounding either on
> pixel coordinates (px, py) or AA (virtual) pixel coordinates (spx, spy).

With respect to applying the "center of pixel insideness" rules to the 
subpixels...

I have a vague memory of having the same discussion with Denis, but it 
seems that either he found a clever way of implementing it that I can't 
find, or he didn't find it helped on the quality vs. performance scale. 
  Keep in mind that our "pixel centers include pixels" rules are 
described in a context that is considering a binary "is this pixel 
inside or not" decision, but AA processing is a different animal and an 
attempt to represent approximate coverages.  So, applying that rule on 
the sub-pixel sample level of an AA rasterizer is on the gray line of 
blind dogmatic adherence to a philosophy from a related area.  I'm not 
convinced that one could consider Pisces "non-compliant" with that rule 
since I don't think it was ever promised that the rule would apply to 
this case.

> I am perplex and I am going to check pisces code against your given
> approach.

If for no other reason that to make sure that there aren't two parts of 
the system trying to communicate with different philosophies.  You don't 
want a caller to hand a closed interval to a method which treats the 
values as half-open, for instance.  If the rounding is "different, but 
consistent", then I think we can leave it for now and treat it as a 
future refinement to check if it makes any practical difference and 
correct.  But, if it shows up a left-hand-not-talking-to-right-hand bug, 
then that would be good to fix sooner rather than later.

I think it is OK to focus on your current task of performance and memory 
turmoil, but I wanted to give you the proper background to try to 
understand what you were reading primarily, and possibly to get you 
interested in cleaning up the code as you went as a secondary consideration.

>     Perhaps lastCrossing is misnamed.  I think it represents the end of
>     the interval which is half-open.  Does that match the rest of the
>     operations done on it?
>
>     If every coordinate has already been biased by the -0.5 then ceil is
>     just the tail end of the rounding equation I gave above.
>
>
> That's not the case => buggy:  x1, y1 and x2, y2 are directly the point
> coordinates as float values.

Then using the ceil() on both is still consistent with half-open 
intervals, it just has a different interpretation of where the sampling 
cut-off lies within the subpixel sample.  When you determine where the 
"crossings" lie, then it would be proper to do the same ceil(y +/- some 
offset) operation to compute the first crossing that is included and the 
first crossing that is excluded.  In this case it appears that the 
offset if just 0.0 which doesn't really meet my expectations, but is a 
minor issue.  These crossings then become a half-open interval of 
scanline indices in which to compute the value.

> FYI, firstCrossing is used to compute the first X intersection for that
> Y coordinate and determine the bucketIdx:
>          _edges[ptr+CURX] = x1 + (firstCrossing - y1) * slope;
> ...
>          final int bucketIdx = firstCrossing - boundsMinY;
> ...
>          _edges[ptr+NEXT] = edgeBuckets[bucketIdx];
>
> lastCrossing is used to give the YMax edge coordinate and edgedBucketCounts:
>          _edges[ptr+YMAX] = lastCrossing;
> ...
>          edgeBucketCounts[lastCrossing - boundsMinY] |= 1;
>
> I think rounding errors can lead to pixel / shape rasterization
> deformations ... ?

As long as the test is "y < _edges[ptr+YMAX]" then that is consistent 
with a half-open interval sampled at the top of every sub-pixel region, 
isn't it?  I agree with the half-open part of it, but would have 
preferred a "center of sub-pixel" offset for the actual sampling.

>     If not, then the half-open considerations still apply if you use the
>     same rounding for both the top and the bottom of the segment.  If
>     lastCrossing represents the "bottom of the shape" then it should not
>     be included.  If the next segment continues on from it, then its y1
>     will be computed in the first equation and will represent the first
>     scanline that the next segment participates in.
>
>
>         => firstCrossing / lastCrossing should use lower and upper integer
>         values (rounding issues) ?
>
>
>     Do they make sense now given my explanation above?  Perhaps they
>     should be renamed to indicate their half-openness?
>
>
> I am a bit embarrassed to verify maths performed in
> ScanLineIterator.next() which use edges and edgeBucketCounts arrays ...
> could you have a look ?
> Apparently, it uses the following for loop that respects the semi-open
> interval philosophy:
>              for (int i = 0, ecur, j, k; i < count; i++) {
> ...

I'll come back to that at a later time, but it sounds like you are 
starting to get a handle on the design here.

> However, I am not sure if the edges "linked list" is traversed correctly ...

That one took me a few tries to understand myself as well.

>               boolean endRendering() {
>                   // TODO: perform shape clipping to avoid dealing with
>         segments
>         out of bounding box
>
>                   // Ensure shape edges are within bbox:
>                   if (edgeMinX > edgeMaxX || edgeMaxX < 0f) {
>                       return false; // undefined X bounds or negative Xmax
>                   }
>                   if (edgeMinY > edgeMaxY || edgeMaxY < 0f) {
>                       return false; // undefined Y bounds or negative Ymax
>                   }
>
>
>     I'd use min >= max since if min==max then I think nothing gets
>     generated as a result of all edges having both the in and out
>     crossings on the same coordinate.  Also, why not test against the
>     clip bounds instead? The code after that will clip the edgeMinMaxXY
>     values against the boundsMinMax values.  If you do this kind of test
>     after that clipping is done (on spminmaxxy) then you can discover if
>     all of the coordinates are outside the clip or the region of interest.
>
>
> I tried here to perform few "fast" checks before doing float to int
> conversions (costly because millions are performed): I think it can be
> still improved: edgeMinX > edgeMaxX only ensures edgeMinX is defined and
> both are positive !

endRendering is called once per shape.  I don't think moving tests above 
its conversions to int will affect our throughput compared to 
calculations done per-vertex.

I'm going to have to review the rest of this email at a future time, my 
apologies...

> PS: I have more free time until sunday (children are away), so I would
> like to talk to you using skype if it is possible ?
> If yes, could you give me your skype account and work times (GMT time
> please) ?
> I am living in Grenoble, France (GMT+1)

Unfortunately, this time frame isn't good for me.  :(

			...jim