Another update:
Boolops are now working correctly with elliptical arc segments. I will now work on ensuring that degenerate cases give sensible results.
A big remaining gap is the handling of nonzero-fill shapes. The best way to handle them will be to convert them to even-odd fill rule first. This will require adding a new method that checks whether an edge is inside or outside (I have this figured out) and methods that find self-intersections on Bezier curves of order 3 and higher (This is straightforward).
In the process, I fleshed out several classes, such as Ellipse and Circle, and added some new functionality to Line and AngleInterval.
The following intersection combinations are now implemented. Each of these methods returns std::vector of appropriate intersection structures that contain two time values and a cached intersection point that can be more precise than direct evaluation.
- Line - Line - Line - LineSegment - Line - Ray - LineSegment - LineSegment - LineSegment - BezierCurve - LineSegment - EllipticalArc - BezierCurve - LineSegment - BezierCurve - EllipticalArc - BezierCurve - BezierCurve - EllipticalArc - LineSegment - EllipticalArc - BezierCurve - EllipticalArc - EllipticalArc - Circle - Line - Circle - LineSegment - Circle - Circle - Ellipse - Line - Ellipse - LineSegment - Ellipse - Ellipse - Ellipse - D2<Bezier>
The code used for ellipse intersection is analytic and should generalize to other conic sections - it can be moved to the conic section class once conicsec.h is refactored. I'm also considering creating classes such as LineEquation, CircleEquation and EllipseEquation to store the implicit representation of those shapes.
Regards, Krzysztof
2015-04-26 6:10 GMT+02:00 Nathan Hurst <njh@...1927...>:
On Mon, Apr 20, 2015 at 02:18:36PM +0200, Krzysztof Kosiński wrote:
2015-04-20 7:15 GMT+02:00 Nathan Hurst <njh@...1927...>:
- Linear and Bezier segments of arbitrary degree
- Code is fairly clean and understandable
- Reasonably good performance, even though there are very few
optimizations
This is almost certainly an improvement on what we have, to gain confidence can you also write some unit tests that capture the various edge cases as per that svg (and anything else you can think of).
The results will be slightly different than in that SVG, because the algorithm I used does not require uncrossing as a preprocessing step. I think this is a nice feature, since it preserves self-intersections in places where they don't affect the result. I wrote a short summary of the underlying algorithm on Wikipedia recently: https://en.wikipedia.org/wiki/Greiner%E2%80%93Hormann_clipping_algorithm
Nice!
For the arc-Bezier case, my thesis advisor suggested to convert elliptical arcs to four rational quadratic Beziers, each representing 1/4 of the ellipse between its conjugate diameters and intersect that using well known algorithms, then go back to the elliptical arc representation by using the fact that the weight of the middle control point is related to the time on the elliptical arc (the angle in the untransformed unit circle). I'm not sure about this. I'll first try the conic equation route, since it's the simplest and requires minimal new code.
Yeah, I think that is wise. I'd forgotten about rational beziers representing conics.
The conic code implements some interesting stuff that I could use, but it needs to be refactored first. I'm pretty certain that If I hadn't spent substantial time on refactoring, writing unit tests for existing stuff and fixing the uncovered bugs, I wouldn't have managed to get this far.
Yes, this work has desperately need to be done. I didn't grok the value of unit tests when I wrote the initial code. Now I do. Please refactor and unit test, it will make the library so much more trustworthy.
njh