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.
Regards, Krzysztof
I'm very impressed. For the other readers out there, this is a problem that has stumped a long line of very smart people (including professional mathematicians and academia) and CGAL, a widely cited geometry library, has a broken implementation. This is a surprisingly hard problem to solve correctly. I agree it's publication worthy.
More importantly, this is not some theoretically wonderful implementation, this is a working, practical implementation.
It also enables many interesting other tools which have either had to work around the existing broken boolops, or have had hacks to approximate sepecial cases. Being both fast and robust makes so many things practical.
On Mon, Apr 20, 2015 at 02:04:32AM +0200, Krzysztof Kosiński wrote:
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
Perhaps someone else could implement them as a learn-the-code experience, Jabier?
- 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).
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.
Two directions to consider:
use the implicit formula for conics (AX^2 + BXY + CY^2 + DX + EY + F = 0) that we have code to generate, then substitute in the bezier for X, Y, and use roots(). This will double the degree of the curve, but should be quite stable.
Or you could try and write something similar to bezier clipping algorithm by projecting a linear approximation of the bezier against the ellipse or vice versa. More fiddly but potentially more accurate.
Intersecting conics is already in 2geom I think.
- Handling of degeneracies and second-order intersections. I have this
mostly planned out, except for a few nasty cases with overlapping Bezier segments.
Also useful are the various combinations with 1d topology - given paths A and B it is useful to compute the set ops between A*B, dA*B and dA*dB (where d refers to the outline). This code implements A*B, and we already have dA*dB.
- Add &, |, / operators to PathVector. I think / will be better than
minus for set subtraction.
Agreed. It's sets, not arithmetic.
- 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.
And uncross.
I observed no crashes or hangs, though when two pathvectors overlap exactly, some paths can be skipped in the output.
Yep, my inextensive testing with the toy also didn't crash (or suddenly take mysterious amounts of time).
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.
Please do!
Very exciting work!
njh
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
My modification is different in that it evaluates the even-odd rule for every portion between two intersections. However, the extra robustness this gives isn't used yet. I could have simply assigned alternating flags like in the original algorithm, but at least now I know that doing it this way won't be prohibitively expensive.
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.
Two directions to consider:
use the implicit formula for conics (AX^2 + BXY + CY^2 + DX + EY + F = 0) that we have code to generate, then substitute in the bezier for X, Y, and use roots(). This will double the degree of the curve, but should be quite stable.
Or you could try and write something similar to bezier clipping algorithm by projecting a linear approximation of the bezier against the ellipse or vice versa. More fiddly but potentially more accurate.
Intersecting conics is already in 2geom I think.
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.
Regards, Krzysztof
On 19-Apr-2015 17:04, Krzysztof Kosiński wrote:
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
How does this relate to livarot? A while back (2012?) I needed these sorts of boolean path functions, and 2geom's variants were too badly broken to use, so I made splivarot.cpp's sp_pathvector_boolop() function and used that instead. suv committed that for me, it was this one, I think:
http://bazaar.launchpad.net/~inkscape.dev/inkscape/trunk/revision/11668.1.3
This is employed, for instance, in the code which emulates gradients in EMF output, by replacing a gradient fill in an arbitrarily shaped path (including holes) with a collection of thin rectangles with gradient colors ANDed with the path. As far as I know only EMF and WMF use this function. Is the goal to eventually remove livarot and just use 2geom's equivalent functions for this sort of thing?
Thanks,
David Mathog mathog@...1176... Manager, Sequence Analysis Facility, Biology Division, Caltech
2015-04-20 18:39 GMT+02:00 mathog <mathog@...1176...>:
How does this relate to livarot? A while back (2012?) I needed these sorts of boolean path functions, and 2geom's variants were too badly broken to use, so I made splivarot.cpp's sp_pathvector_boolop() function and used that instead. suv committed that for me, it was this one, I think:
http://bazaar.launchpad.net/~inkscape.dev/inkscape/trunk/revision/11668.1.3
This is employed, for instance, in the code which emulates gradients in EMF output, by replacing a gradient fill in an arbitrarily shaped path (including holes) with a collection of thin rectangles with gradient colors ANDed with the path. As far as I know only EMF and WMF use this function. Is the goal to eventually remove livarot and just use 2geom's equivalent functions for this sort of thing?
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.
Livarot uses an inferior algorithm for boolops that requires snapping node coordinates to a grid to work correctly, see e.g. this bug: https://bugs.launchpad.net/inkscape/+bug/168158
Regards, Krzysztof
On Mon, 2015-04-20 at 18:55 +0200, Krzysztof Kosiński wrote:
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.
It also sounds like what happens to people who /really/ like whisky in english. Liver Rot. Lovely.
Martin,
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
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
Did you come up with the mu intersection approach? that's rather neat.
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.
njh
On Sat, May 23, 2015 at 03:26:00PM +0200, Krzysztof Kosiński wrote:
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
Any updates?
On Mon, 2015-06-01 at 15:05 +0200, Krzysztof Kosiński wrote:
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@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/lib2geom-devel
Not much to report unfortunately - I was taking care of final exams for the past ~3 weeks.
Right now my first Inkscape-related priority is to finally commit the 2Geom sync, to avoid any further bitrot; then I will implement handling of overlapping segments, and after that - attempt to implement the conversion from nonzero fills to even-odd fills.
Regards, Krzysztof
2015-07-03 10:32 GMT+02:00 Tavmjong Bah <tavmjong@...8...>:
Any updates?
On Mon, 2015-06-01 at 15:05 +0200, Krzysztof Kosiński wrote:
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@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/lib2geom-devel
participants (5)
-
Krzysztof Kosiński -
Martin Owens -
mathog -
Nathan Hurst -
Tavmjong Bah