Re: [OpenJDK 2D-Dev] Various fixes to pisces stroke widening code
Hello Jim. This one performs almost identically to what is already there in openjdk6 and 7, since it's exactly what I sent for review last week, but with all the changes you suggested implemented. I would actually like to ask you to not look at either one of them. First of all, there is an ArrayIndexOutOfBoundsException possible in emitRow. And secondly, even if there wasn't, last night I implemented your algorithm from ShapeSpanIterator.c to iterate through the edges. I have yet to debug it, but it makes everything much, much simpler, and it should make it far faster, so we get the best of both worlds. Thanks, Denis. - Jim Graham james.gra...@oracle.com wrote: Hi Denis, I'll try to get through both versions and see if I can find anything that was hurting performance with your EdgeLists. I'm guessing that this version was created because of the performance issues you found with the EdgeList version? Does this perform more closely to the existing code than the EdgeList version? ...jim Denis Lila wrote: Hello again. This attachmet is a can of worms implementation without all the fancy (and slow) iteration. It also includes all of the other suggestions you sent in your first review of Dasher and Renderer last week (most importantly, the firstOrientation issue, horizontal lines filtering, and adding prefixes to variable names to make it clear whether they refer to pixels, or subpixels). Regards, Denis. - Denis Lila dl...@redhat.com wrote: Hello Jim. I implemented your can of worms idea. It works, and it got rid of the biasing. I wasn't able to send a webrev, but there are many changes and a side by side comparison would probably be useless, so I just attached the file. I hope this is ok. I also implemented a better iterating structure for the lines and the strips and crossings. I think it is better in every way, except performance. The new file is more than 200 lines smaller than the old one. The only members of Renderer are now the AA variables and the position variables (sx*, sy*, x*, y*). What I've done is I added an EdgeList class, which encapsulates all the edge related variables in the old Renderer. At first, I had an Edge class in addition to the EdgeList class, and while this was much nicer, it turned out to be too expensive (see last paragraph). I've also added a ScanLineIterator, so instead of _endRendering iterating through strips, and then calling renderStrip() which iterates through the scanlines in that strip, and then through the crossings in that scanline, what happens now is that _endRendering uses the IteratorScanLine to iterate through each scanline, get get its crossings and iterate through them to accumulate the alpha. By the way, a ScanLine is a type defined by an interface which exports methods for getting the y coord of the line, the number of crossings in it, the ith crossing, and a method for sorting its crossings. The class that implements ScanLine is ScanLineIterator itself. I made a ScanLine class, but I was afraid performance would suffer because of all the object creations (this turned out not to be an issue, after I switched to the current way, and remeasured things). I did not switch back because this is only slightly worse. As for performance: I wrote a simple program that tries to draw a dashed path that consists of about 160 dashed lines of width 1 and length 3, going from the centre of the frame to some point. On my machine, this takes about 4.9 seconds in openjdk6, and 26 seconds using the attached file. Back when I was using the Edge class it took about 39 seconds. Everything without hundres of thousands of edges is not much slower I have not changed any of the algorithms. ScanLineIterator still goes through strips of the same size and computes crossings in every strip using the same method as before, so I don't know why it's so slow. It can't be because of anything happening in _endRendering, because there are only about 9000 scanlines and for each of them I've just added a few calls to one line getters (which used to be direct accesses into arrays). Thanks, Denis. - Jim Graham james.gra...@oracle.com wrote: Denis Lila wrote: Hello Jim. Thank you very much for taking the time to read through this. 169 - if origLen reaches the end of the dash exactly (the == case) You're right, I should. I can't just replace = with == though, because the results will be the same: in the equal case origLen will become 0, and on the next iteration, the (origLen dash[idx]-phase) will be true, and we will do a goTo(x1,y1), which is what we just did in the previous iteration (unless dash[idx] is 0, in which case the results will be even worse). The best solution to this is
Re: [OpenJDK 2D-Dev] Various fixes to pisces stroke widening code
Woohoo, Denis! I look forward to seeing the new version! ...jim On 7/28/2010 5:51 AM, Denis Lila wrote: Hello Jim. This one performs almost identically to what is already there in openjdk6 and 7, since it's exactly what I sent for review last week, but with all the changes you suggested implemented. I would actually like to ask you to not look at either one of them. First of all, there is an ArrayIndexOutOfBoundsException possible in emitRow. And secondly, even if there wasn't, last night I implemented your algorithm from ShapeSpanIterator.c to iterate through the edges. I have yet to debug it, but it makes everything much, much simpler, and it should make it far faster, so we get the best of both worlds. Thanks, Denis. - Jim Grahamjames.gra...@oracle.com wrote: Hi Denis, I'll try to get through both versions and see if I can find anything that was hurting performance with your EdgeLists. I'm guessing that this version was created because of the performance issues you found with the EdgeList version? Does this perform more closely to the existing code than the EdgeList version? ...jim Denis Lila wrote: Hello again. This attachmet is a can of worms implementation without all the fancy (and slow) iteration. It also includes all of the other suggestions you sent in your first review of Dasher and Renderer last week (most importantly, the firstOrientation issue, horizontal lines filtering, and adding prefixes to variable names to make it clear whether they refer to pixels, or subpixels). Regards, Denis. - Denis Liladl...@redhat.com wrote: Hello Jim. I implemented your can of worms idea. It works, and it got rid of the biasing. I wasn't able to send a webrev, but there are many changes and a side by side comparison would probably be useless, so I just attached the file. I hope this is ok. I also implemented a better iterating structure for the lines and the strips and crossings. I think it is better in every way, except performance. The new file is more than 200 lines smaller than the old one. The only members of Renderer are now the AA variables and the position variables (sx*, sy*, x*, y*). What I've done is I added an EdgeList class, which encapsulates all the edge related variables in the old Renderer. At first, I had an Edge class in addition to the EdgeList class, and while this was much nicer, it turned out to be too expensive (see last paragraph). I've also added a ScanLineIterator, so instead of _endRendering iterating through strips, and then calling renderStrip() which iterates through the scanlines in that strip, and then through the crossings in that scanline, what happens now is that _endRendering uses the IteratorScanLine to iterate through each scanline, get get its crossings and iterate through them to accumulate the alpha. By the way, a ScanLine is a type defined by an interface which exports methods for getting the y coord of the line, the number of crossings in it, the ith crossing, and a method for sorting its crossings. The class that implements ScanLine is ScanLineIterator itself. I made a ScanLine class, but I was afraid performance would suffer because of all the object creations (this turned out not to be an issue, after I switched to the current way, and remeasured things). I did not switch back because this is only slightly worse. As for performance: I wrote a simple program that tries to draw a dashed path that consists of about 160 dashed lines of width 1 and length 3, going from the centre of the frame to some point. On my machine, this takes about 4.9 seconds in openjdk6, and 26 seconds using the attached file. Back when I was using the Edge class it took about 39 seconds. Everything without hundres of thousands of edges is not much slower I have not changed any of the algorithms. ScanLineIterator still goes through strips of the same size and computes crossings in every strip using the same method as before, so I don't know why it's so slow. It can't be because of anything happening in _endRendering, because there are only about 9000 scanlines and for each of them I've just added a few calls to one line getters (which used to be direct accesses into arrays). Thanks, Denis. - Jim Grahamjames.gra...@oracle.com wrote: Denis Lila wrote: Hello Jim. Thank you very much for taking the time to read through this. 169 - if origLen reaches the end of the dash exactly (the == case) You're right, I should. I can't just replace= with == though, because the results will be the same: in the equal case origLen will become 0, and on the next iteration, the (origLen dash[idx]-phase) will be true, and we will do a goTo(x1,y1), which is what we just did in the previous iteration (unless dash[idx] is 0, in which case the results will be even worse). The best solution to this is to just do a nested check for the == case. Ah, right -
Re: [OpenJDK 2D-Dev] Various fixes to pisces stroke widening code
Hi Denis, Only some minor comments so far: Stroker.java: - Should det be precomputed and saved? (You calculate it in the constructor anyway, but don't save it.) - Should test for uniform scale be precomputed? - (Is test for uniform scale too strict? Can a rotated uniform scale use the same code as upright uniform scale?) - Why are m00_2_m01_2 et al no longer precomputed (they only need to be precomputed if scale is not uniform which isn't common)? - lineLength method is user space length isn't it? - a more descriptive name might help avoid confusion if someone is modifying code here later. - line 614 - missing space Dasher.java: - Line 187 - use leftInThisDashSegment here? I still have to look at Renderer.java in depth, but I thought I'd send these minor comments along while they are fresh in my email buffer... ...jim Denis Lila wrote: Hello. And, here it is: http://icedtea.classpath.org/~dlila/webrevs/fpBetterAA/webrev/ Just as I thought, it's way faster than the original. I made a new test, which is supposed to be more realistic than drawing 3 length lines. It consists of splitting a 1000x1000 frame in 100 10x10 squares and in each square drawing 20 or so curves with random start/end/control points in that square. In this case it's at least twice faster (~0.85 versus ~1.95 seconds). Unfortunately I've had to do a lot of the same optimizations that I was trying to remove (i.e. making everything a global variable). I tried writing a higher level version of it, but it completely negated the performance gains of the new algorithm. Anyway, it's still not as bad as before because the algorithm is inherently clearer and we only iterate through scan lines instead of iterating through strips and then scanlines in that strip, and then edges, all in the same method. It's also better organized, and logically separate parts of the code don't really touch each other's variables much. And it's definitely better commented. I also made some minor changes outside of Renderer that did not appear in the first version of this patch last week: 1. I fixed the issue Jim pointed out in Dasher, where if (origLen == leftInThisDashSegment) the dash index was not being incremented. 2. In dasher, I no longer copy the dash array. 3. I removed files PiscesMath.java and Transform4.java because they are no longer needed. Thanks, Denis. - Jim Graham james.gra...@oracle.com wrote: Woohoo, Denis! I look forward to seeing the new version! ...jim On 7/28/2010 5:51 AM, Denis Lila wrote: Hello Jim. This one performs almost identically to what is already there in openjdk6 and 7, since it's exactly what I sent for review last week, but with all the changes you suggested implemented. I would actually like to ask you to not look at either one of them. First of all, there is an ArrayIndexOutOfBoundsException possible in emitRow. And secondly, even if there wasn't, last night I implemented your algorithm from ShapeSpanIterator.c to iterate through the edges. I have yet to debug it, but it makes everything much, much simpler, and it should make it far faster, so we get the best of both worlds. Thanks, Denis. - Jim Grahamjames.gra...@oracle.com wrote: Hi Denis, I'll try to get through both versions and see if I can find anything that was hurting performance with your EdgeLists. I'm guessing that this version was created because of the performance issues you found with the EdgeList version? Does this perform more closely to the existing code than the EdgeList version? ...jim Denis Lila wrote: Hello again. This attachmet is a can of worms implementation without all the fancy (and slow) iteration. It also includes all of the other suggestions you sent in your first review of Dasher and Renderer last week (most importantly, the firstOrientation issue, horizontal lines filtering, and adding prefixes to variable names to make it clear whether they refer to pixels, or subpixels). Regards, Denis. - Denis Liladl...@redhat.com wrote: Hello Jim. I implemented your can of worms idea. It works, and it got rid of the biasing. I wasn't able to send a webrev, but there are many changes and a side by side comparison would probably be useless, so I just attached the file. I hope this is ok. I also implemented a better iterating structure for the lines and the strips and crossings. I think it is better in every way, except performance. The new file is more than 200 lines smaller than the old one. The only members of Renderer are now the AA variables and the position variables (sx*, sy*, x*, y*). What I've done is I added an EdgeList class, which encapsulates all the edge related variables in the old Renderer. At first, I had an Edge class in addition to the EdgeList class, and while this was much nicer, it turned out to be too expensive (see last paragraph). I've also added a ScanLineIterator, so