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

Jim Graham james.graham at oracle.com
Fri May 3 22:57:38 UTC 2013

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

More information about the 2d-dev mailing list