There is a new toy "boolops-new" in 2Geom's source repository - it computes an union of two paths using my new boolops code based on the Greiner-Hormann algorithm. What works: - Union - Intersection - Adding difference and XOR is trivial

- Linear and Bezier segments of arbitrary degree - Code is fairly clean and understandable - Reasonably good performance, even though there are very few optimizations

What remains to be done: - Could be simplified a bit and better documented. - Intersection procedures for arc-arc and arc-Bezier cases. Currently they throw UnimplementedError.

- Handling of degeneracies and second-order intersections. I have this mostly planned out, except for a few nasty cases with overlapping Bezier segments.

- Add &, |, / operators to PathVector. I think / will be better than minus for set subtraction.

- Function that converts a nonzero winding pathvector to even-odd winding pathvector with the same filled areas. It's a lot easier to do this conversion than it is to do Booleans on nonzero winding fills.

I observed no crashes or hangs, though when two pathvectors overlap exactly, some paths can be skipped in the output.

Since this code is already a lot better than the old attempts present in 2Geom (path-intersection.h, shape.h, region.h and the like), I'm going to remove them to reduce cruft.

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

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.

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.

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

2015-05-31 3:21 GMT+02:00 Nathan Hurst <njh@...1927...>: > Did you come up with the mu intersection approach? that's rather neat. Nope, I mostly copied that from this document. No point reinventing the wheel :) http://maptools.home.comcast.net/~maptools/BivariateQuadratics.pdf It can still be improved a little - when two very thin and long ellipses intersect at two points, the results of one of the ellipse-line intersections will have much better accuracy, because the resulting line intersects it at less shallow angles. I could pick the ellipse where the cross product of the unit versor of the major axis and the unit versor of the line is larger, but it's not yet obvious to me that this always gives the better result. In any case, for now I'm focusing on how to solve the problem of overlapping segments, since it's the only major thing missing from the algorithm. Then I'll focus on testing various edge cases, and conversion from nonzero to even-odd fill rules. > Your approach made me wonder whether there is a nice analytic solution > for nearest_point for conic section pairs too. Basically you want to > find points with matched normals, which is, in your notation, > mu dQ + dR = 0. The derivative of an ellipse is another ellipse at the origin, so it would definitely be doable for ellipses. I'm not yet sure about other conic sections. Regards, Krzysztof ------------------------------------------------------------------------------ _______________________________________________ Lib2geom-devel mailing list Lib2geom-devel(a)lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/lib2geom-devel

There is a new toy "boolops-new" in 2Geom's source repository - it computes an union of two paths using my new boolops code based on the Greiner-Hormann algorithm. What works: - Union - Intersection - Adding difference and XOR is trivial - Linear and Bezier segments of arbitrary degree - Code is fairly clean and understandable - Reasonably good performance, even though there are very few optimizations

Livarot will eventually be killed with fire. Parts of it are written in French, it is hard to maintain, has no unit tests and the code is really convoluted in places.