Re: [OpenJDK 2D-Dev] X11 uniform scaled wide lines and dashed lines; STROKE_CONTROL in Pisces
FYI - we have a bug to integrate some optimizations from JDK6 for wide lines and transformed rectangles. In 6 I did some work a year ago or so to detect simply wide lines and transformed rectangles and to issue a "fillParallelogram" internal method. OGL and D3D can then implement these directly and I wrote new software loops for doing pgrams as well. We are right now going through our list or 6 bugs and integrating them into 7 so this code should get integrated in the next month or so. At that point I think that horizontal lines may be moot... ...jim On 11/10/2010 2:01 PM, Denis Lila wrote: Hi Jim. - get rid of edgeMxy in all methods but addLine() - addLine computes min/max of first/lastScanline - addLine also computes min/max of x1,x2 values this turned out to be just about the same speed for my FX rendering version (which I believe is more sensitive than the way it is integrated into JDK, so it should be even less noticeable in JDK). It also paved the way for a couple of other optimizations that ended up netting about 1FPS for my current test case that I use so I'm happy for now. The code is a lot simpler now... I also implemented what you describe and those are exactly my results too. I implemented my ideas for optimizing edgeM[in|ax]Y too, but it turned out not to make any difference whatsoever. I should note that my benchmarks say the performance on horizontal lines has decreased by 32% compared to the version where we qsorted everything. The benchmark report says the overall performance has stayed the same because every test other than horizontal lines is performing better by about 2-6%. Regards, Denis. - "Jim Graham" wrote: I ended up going with: ...jim On 11/9/2010 3:26 PM, Denis Lila wrote: Hi again. I just thought of this: if we're really concerned about the accuracy of the edgeMinX edgeMaxX variables, we could find the curves' critical points and use them to compute the min/max X values. After all, we're creating (or rather "setting") the Curve objects anyway. This isn't as fast as using the bounding boxes, but it's close and much more accurate. Regards, Denis. - "Denis Lila" wrote: Hi Jim. All lines generated from a given "allegedly monotonic" curve are recorded with the same "or" (orientation) value. But, if the curves are not truly monotonic then it might be theoretically possible to generate a line that is backwards with respect to the expected orientation. It would then get recorded in the edges array with the wrong orientation and slope and then rasterization might unravel. I see. In that case, I think it's a good idea if we don't make curves "monotonic". I already did this, by moving the edgeMin/axX/Y handling and orientation computations in addLine. This did make it slower compared to the file you sent me, but only by very, very little. Curves were affected the most, and they were only 1% slower. I think we can handle this, especially since lines were about 1% faster. The code is also 70 lines shorter. The edgeM* members are used only so we don't have to iterate through every scanline if this is not necessary, and so that we can tell PiscesCache that the bounding box is smaller than what Renderer is given. However, now that we keep the bucket list, I think it would be more efficient if we got rid if EdgeM[in|ax]Y and simply computed the y bounds by looking at the head and tail of the bucket list. Also, perhaps we can keep track of edgeM[in|ax]X using the bounding boxes of curves, instead of the lines in the flattened curves. This would not be accurate, but I don't think it would affect rendering. It would simply result in a few more alpha boxes than necessary. I don't think these would be too bad, because mostly they're just going to be all 0 so they will be skipped because getTypicalAlpha() is now implemented. How do you think we should handle these 4 variables? Thank you, Denis. - "Jim Graham" wrote: Hi Denis, On 11/8/2010 2:39 PM, Denis Lila wrote: Finally, I discovered (while testing for other problems) that the curves are not truly monotonic after slicing them. I realized this years ago when I was writing my Area code (see sun.awt.geom.Curve) and put in tweaking code to make them monotonic after they were split. They are never off by more than a few bits, but you can't trust the curve splitting math to generate purely monotonic segments based on a t generated by some unrelated math. Sometimes the truly horizontal or vertical t value requires more precision than a float (or even a double) can provide and splitting at the highest representable float less than the t value produces a pair of curves on one side of the hill and splitting at the next float value (which is greater than the true t value) produces curves on the other side of the hill. Also, when the curve has been split a few times already,
Re: [OpenJDK 2D-Dev] X11 uniform scaled wide lines and dashed lines; STROKE_CONTROL in Pisces
Hi Jim. > - get rid of edgeMxy in all methods but addLine() > - addLine computes min/max of first/lastScanline > - addLine also computes min/max of x1,x2 values > > this turned out to be just about the same speed for my FX rendering > version (which I believe is more sensitive than the way it is > integrated > into JDK, so it should be even less noticeable in JDK). It also paved > the way for a couple of other optimizations that ended up netting > about 1FPS for my current test case that I use so I'm happy for now. > The code is a lot simpler now... I also implemented what you describe and those are exactly my results too. I implemented my ideas for optimizing edgeM[in|ax]Y too, but it turned out not to make any difference whatsoever. I should note that my benchmarks say the performance on horizontal lines has decreased by 32% compared to the version where we qsorted everything. The benchmark report says the overall performance has stayed the same because every test other than horizontal lines is performing better by about 2-6%. Regards, Denis. - "Jim Graham" wrote: > I ended up going with: > > ...jim > > On 11/9/2010 3:26 PM, Denis Lila wrote: > > Hi again. > > > > I just thought of this: if we're really concerned about the > accuracy > > of the edgeMinX edgeMaxX variables, we could find the curves' > > critical points and use them to compute the min/max X values. After > all, > > we're creating (or rather "setting") the Curve objects anyway. This > isn't > > as fast as using the bounding boxes, but it's close and much more > accurate. > > > > Regards, > > Denis. > > > > - "Denis Lila" wrote: > > > >> Hi Jim. > >> > >>> All lines generated from a given "allegedly monotonic" curve are > >>> recorded with the same "or" (orientation) value. But, if the > curves > >>> are not truly monotonic then it might be theoretically possible > to > >>> generate a line that is backwards with respect to the expected > >> orientation. It > >>> would then get recorded in the edges array with the wrong > >> orientation > >>> and slope and then rasterization might unravel. > >> > >> I see. In that case, I think it's a good idea if we don't make > curves > >> "monotonic". I already did this, by moving the edgeMin/axX/Y > handling > >> and orientation computations in addLine. This did make it slower > >> compared > >> to the file you sent me, but only by very, very little. Curves > were > >> affected the most, and they were only 1% slower. I think we can > handle > >> this, especially since lines were about 1% faster. The code is also > 70 > >> lines shorter. > >> > >> The edgeM* members are used only so we don't have to iterate > through > >> every > >> scanline if this is not necessary, and so that we can tell > PiscesCache > >> that the bounding box is smaller than what Renderer is given. > However, > >> now > >> that we keep the bucket list, I think it would be more efficient if > we > >> got rid if EdgeM[in|ax]Y and simply computed the y bounds by > looking > >> at the > >> head and tail of the bucket list. > >> Also, perhaps we can keep track of edgeM[in|ax]X using the > bounding > >> boxes > >> of curves, instead of the lines in the flattened curves. This > would > >> not > >> be accurate, but I don't think it would affect rendering. It would > >> simply > >> result in a few more alpha boxes than necessary. I don't think > these > >> would > >> be too bad, because mostly they're just going to be all 0 so they > will > >> be skipped because getTypicalAlpha() is now implemented. > >> How do you think we should handle these 4 variables? > >> > >> Thank you, > >> Denis. > >> > >> - "Jim Graham" wrote: > >> > >>> Hi Denis, > >>> > >>> On 11/8/2010 2:39 PM, Denis Lila wrote: > > Finally, I discovered (while testing for other problems) that > the > > curves are not truly monotonic after slicing them. I realized > >> this > >>> years ago > > when I was writing my Area code (see sun.awt.geom.Curve) and > put > >>> in > > tweaking code to make them monotonic after they were split. > They > >>> are > > never off by more than a few bits, but you can't trust the > curve > > splitting math to generate purely monotonic segments based on a > t > > generated by some unrelated math. Sometimes the truly > horizontal > >>> or > > vertical t value requires more precision than a float (or even > a > > double) can provide and splitting at the highest representable > >>> float less than > > the t value produces a pair of curves on one side of the hill > and > > splitting at the next float value (which is greater than the > true > >>> t > > value) produces curves on the other side of the hill. Also, > when > >>> the > > curve has been split a few times already, the t values loose > >>> accuracy > > with each split. This will all be moot if I can eliminate the > > splitting code from the renderer, but it may also play a factor > >>
Re: [OpenJDK 2D-Dev] X11 uniform scaled wide lines and dashed lines; STROKE_CONTROL in Pisces
Hi Jim. > Did you have to modify the AFD code for this (in terms of changing > their limit constants to get good results)? No, I didn't. By handling non monotonic curves, the AFD algorithm is going through more iterations, but the only way in which this could be a problem is through accumulation of numerical inaccuracies, and I don't think we do enough iterations for this to start causing perceptible problems. I haven't noticed anything in all my testing. Regards, Denis. - "Jim Graham" wrote: > Hi Denis, > > On 11/9/2010 3:06 PM, Denis Lila wrote: > > I see. In that case, I think it's a good idea if we don't make > curves > > "monotonic". I already did this, by moving the edgeMin/axX/Y > handling > > and orientation computations in addLine. This did make it slower > compared > > to the file you sent me, but only by very, very little. Curves were > > affected the most, and they were only 1% slower. I think we can > handle > > this, especially since lines were about 1% faster. The code is also > 70 > > lines shorter. > > > The edgeM* members are used only so we don't have to iterate through > every > > scanline if this is not necessary, and so that we can tell > PiscesCache > > that the bounding box is smaller than what Renderer is given. > However, now > > that we keep the bucket list, I think it would be more efficient if > we > > got rid if EdgeM[in|ax]Y and simply computed the y bounds by looking > at the > > head and tail of the bucket list. > > That makes sense. We calculate that per-edge anyway so the edgeMy > constants are redundant. > > > Also, perhaps we can keep track of edgeM[in|ax]X using the bounding > boxes > > of curves, instead of the lines in the flattened curves. This would > not > > be accurate, but I don't think it would affect rendering. It would > simply > > result in a few more alpha boxes than necessary. I don't think these > would > > be too bad, because mostly they're just going to be all 0 so they > will > > be skipped because getTypicalAlpha() is now implemented. > > How do you think we should handle these 4 variables? > > I think this is probably OK, but let me play with it a bit and see > what > I come up with. For one thing, the extra "slop" may not be large > enough > to trigger a full tile of 0's - there would have to be 32-pixel > borders > for that to happen. > > If we get rid of the redundant edgeMy calculations then we might be > able > to do edgeMx calculations on each edge without losing any > performance... > > ...jim
