[OpenJDK 2D-Dev] java.awt.geom.Area produces extraneous short segments (original) (raw)
Jim Graham james.graham at oracle.com
Tue Mar 6 23:53:08 UTC 2012
- Previous message: [OpenJDK 2D-Dev] java.awt.geom.Area produces extraneous short segments
- Next message: [OpenJDK 2D-Dev] java.awt.geom.Area produces extraneous short segments
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Hi Alex,
Are you interested in working on Area? I'd love to see some improvements made to this, but it can get to be a bit like whack-a-bug at times with a fix here causing problems over there. Some areas where it could use some "love" would be:
trying to keep original vertex values around so that when a curve is sliced up and then meets copies of itself, they can be mended back into larger curves to reduce the amount of "geometry dust" created. This is a subtle improvement, but helps with a lot of repeated operations. Basically, when we come up with a new set of curves for the result of an operation we may subdivide a curve, but a subsequent Area op might require us to compare that new piece of the curve against a piece of another curve that we already found the intersection point for. Due to slight rounding errors when subdividing both of the original curves the math of comparing them might find a slightly different intersection point causing us to subdivide them further - even when those curves were not in contention during the subsequent operation. My thought was that if the original vertices were kept around and all comparisons done on the original curves (plus start and end t parameters) then the answers would remain stable over repeated operations - we'd then do the actual subdivision only when force to iterate the answer in a PathIterator.
caching results of finding the intersection between pairs of curves
faster convergence on intersection points (or non-intersection) of very close, but not quite parallel, curves due to better curve comparison math and algorithms
finally tuning isClose() as a last resort if the above don't help with many of the current problems, but I'm hoping that they will help enough that isClose() will no longer be seen as the culprit and can remain at a high precision
My original test case for working on this code was a basher that combined dozens or hundreds of displaced circles orbiting a central point (sort of like spirograph except it was many circles rather than a spiral) and you could see the performance bog down as the number of circles increased. Test cases with a number of "circle minus arc-of-same-circle" tests would also be useful since that is a common operation that people try and eventually give up on because we don't always notice that the curves are essentially the same with IEEE rounding errors...
...jimOn 3/5/2012 6:06 AM, Alex Lam S.L. wrote:
I have been using java.awt.geom.Area extensively in my project and have been hit hard by the problems due to rounding:
http://bugs.sun.com/bugdatabase/viewbug.do?bugid=4818309 http://bugs.sun.com/bugdatabase/viewbug.do?bugid=4724141 There may be a few other reported issues as well which I missed. I have since found a workaround which at least works well for me - by modifying AreaIterator (see attached). Obvious place for improvement would be to isClose(), as it is hard-coded to handle a fixed precision for now.
Regards, Alex.
- Previous message: [OpenJDK 2D-Dev] java.awt.geom.Area produces extraneous short segments
- Next message: [OpenJDK 2D-Dev] java.awt.geom.Area produces extraneous short segments
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]