Re: [OpenJDK 2D-Dev] X11 uniform scaled wide lines and dashed lines; STROKE_CONTROL in Pisces
Hi Jim. Woohoo! :) How often do we end up needing getTCloseTo in practice? It depends on the ratios of the lengths of the sides of the control polygon. The closer they are to 1, the less we need it. I'm not sure how to answer more precisely - for that I would need a representative sample of curves drawn in practice. I was thinking of, say, when applied to a circle. Does that get by without needing getTCloseTo? I tested it on a couple of quarter circles of greatly varying radii, and surprisingly, it does get by without needing getTCloseTo (or its equivalent, after your flattening proposal in your previous e-mail). Good job! Well, thanks for all your help. Denis.
Re: [OpenJDK 2D-Dev] X11 uniform scaled wide lines and dashed lines; STROKE_CONTROL in Pisces
Hi Jim. With respect to finding a cubic root, currently you are doing that in 2 dimensions, but what if we converted to 1 dimension? Consider that the control polygon is fairly linear. What if we rotated our perspective so that it was horizontal and then squashed it flat? Consider instead a 1 dimensional bezier with control values of: (where |mn| is the length of the m-n control polygon of the original curve - sum of all segments from point m to point n) 0.0, |01|, |02|, |03| I had thought of something like this but I was afraid that the loss of Curve.java:141-152 would hurt accuracy. I implemented this though, and testing shows that that's not a problem. This should also double the performance of the computation since we only run one cubic root finder, and that was the major bottleneck. I updated the webrev. Should I remove some no longer needed methods, like getTCloseTo? Solve that 1 dimensional bezier for v=(leaflen*polylen)/linelen... Don't you mean (targetLength - lenAtLastT) * polylen / leaflen? Regards, Denis.
Re: [OpenJDK 2D-Dev] X11 uniform scaled wide lines and dashed lines; STROKE_CONTROL in Pisces
Hi again. I found an implementation of a closed form cubic root solver (from graphics gems): http://read.pudn.com/downloads21/sourcecode/graph/71499/gems/Roots3And4.c__.htm I did some micro benchmarks, and it's about 25% slower than the one I have. I'm thinking we should use it anyway because it's much better in every other way: it finds all roots, it doesn't make its callers give it a root array that is longer than the total number of roots, and most importantly, it doesn't fail because of an iteration upper bound. From my testing, I noticed that this happens too frequently for comfort in my cubicRootsInAB. I haven't noticed any rendering artifacts caused by this, but I also haven't tried rendering every possible curve and it's better to prevent bugs than fix them. What do you think? Regards, Denis.
Re: [OpenJDK 2D-Dev] X11 uniform scaled wide lines and dashed lines; STROKE_CONTROL in Pisces
Very nice! How does it compare to CubicCurve.solveCubic() (which I know has issues with the 2 root case, but I got it from a reliable source - some textbook on Numerical Recipes)? Also, one area that I had issues with the version I used in CC2D was that it chose a hard cutoff to classify the number of points and floating point errors might cause a given cubic to jump over that point despite the fact that the equation was of the other form. Hopefully that jumping between root counts only happens when two roots are very close to each other so that the choice is between listing N or N+epsilon and N-epsilon - I can live with that inaccuracy, but it seemed like the version in CC2D might choose between it's either a single root of 4.25, or three roots of -127.3, 23.5, and 42.6 and I would scratch my head and think - wow, what a difference a bit made! Luckily I don't think we actually ever relied on CC2D.solveCubic for correctness in any of our code, but it would be nice to fix it if a more stable method is available. ...jim On 12/13/2010 12:23 PM, Denis Lila wrote: Hi again. I found an implementation of a closed form cubic root solver (from graphics gems): http://read.pudn.com/downloads21/sourcecode/graph/71499/gems/Roots3And4.c__.htm I did some micro benchmarks, and it's about 25% slower than the one I have. I'm thinking we should use it anyway because it's much better in every other way: it finds all roots, it doesn't make its callers give it a root array that is longer than the total number of roots, and most importantly, it doesn't fail because of an iteration upper bound. From my testing, I noticed that this happens too frequently for comfort in my cubicRootsInAB. I haven't noticed any rendering artifacts caused by this, but I also haven't tried rendering every possible curve and it's better to prevent bugs than fix them. What do you think? Regards, Denis.
Re: [OpenJDK 2D-Dev] X11 uniform scaled wide lines and dashed lines; STROKE_CONTROL in Pisces
Hi Denis, Those sound like just the kind of problems I believed existed in the CC2D algorithm. You might want to submit it as a separate push and get credit for fixing 4645692 (solveCubic doesn't return all answers), and maybe even the following failures in the containment methods (which could be closed as dups if this fixes the problems) as well: 4724552 4493128 4074742 4724556 (etc. Those were just the bugs I found on the first 2 pages of a bug database search) Double (triple, etc.) credit - woohoo! ;-) ...jim On 12/13/2010 2:30 PM, Denis Lila wrote: Very nice! How does it compare to CubicCurve.solveCubic() (which I know has issues with the 2 root case, but I got it from a reliable source - some textbook on Numerical Recipes)? I wrote a tests that generated 2559960 polynomials, and in 2493075 of those, the computed roots were identical to within 1e-9. They were different in the remaining 66885 cases, so that's 97.4% agreement. I've looked through some of the differences, and in every case the function from graphics gems is better in one of two ways: 1. the gg version will report more roots than the cc2d version, in which case the polynomial has a double root and the cc2d version completely misses it (example poly: a=19.00, b=-20.00, c=-17.00, d=18.00, where cc2d misses the root at 1). 2. the gg version will report fewer roots than the cc2d version, in which case there was a 0 root and the cc2d version incorrectly split it into -1e-163 and 1e-163. So, the graphics gems version seems to be much more stable. It does have a problem where it can return NaN sometimes, because it assumes that the polynomial is not a quadratic one, but that can easily be fixed. So, should I put this new cubic root finder in CubicCurve.solveCubic and use that in pisces? Regards, Denis.
