There is a new toy "boolopsnew" in 2Geom's source repository  it computes an union of two paths using my new boolops code based on the GreinerHormann 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 arcarc and arcBezier cases. Currently they throw UnimplementedError.  Handling of degeneracies and secondorder 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 evenodd 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 (pathintersection.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 "boolopsnew" in 2Geom's source repository  it computes an union of two paths using my new boolops code based on the GreinerHormann algorithm.
What works:
 Union
 Intersection
 Adding difference and XOR is trivial
Perhaps someone else could implement them as a learnthecode 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 arcarc and arcBezier 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 secondorder 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 evenodd
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 (pathintersection.h, shape.h, region.h and the like), I'm going to remove them to reduce cruft.
Please do!
Very exciting work!
njh
20150420 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 selfintersections 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 evenodd 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 arcarc and arcBezier 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 arcBezier 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 19Apr2015 17:04, Krzysztof Kosiński wrote:
There is a new toy "boolopsnew" in 2Geom's source repository  it computes an union of two paths using my new boolops code based on the GreinerHormann 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
20150420 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, 20150420 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:
20150420 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 selfintersections 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 arcBezier 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 nonzerofill shapes. The best way to handle them will be to convert them to evenodd 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 selfintersections 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
20150426 6:10 GMT+02:00 Nathan Hurst <njh@...1927...>:
On Mon, Apr 20, 2015 at 02:18:36PM +0200, Krzysztof Kosiński wrote:
20150420 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 selfintersections 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 arcBezier 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 nonzerofill shapes. The best way to handle them will be to convert them to evenodd 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 selfintersections 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
20150426 6:10 GMT+02:00 Nathan Hurst <njh@...1927...>:
On Mon, Apr 20, 2015 at 02:18:36PM +0200, Krzysztof Kosiński wrote:
20150420 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 selfintersections 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 arcBezier 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
20150531 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 ellipseline 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 evenodd 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, 20150601 at 15:05 +0200, Krzysztof Kosiński wrote:
20150531 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 ellipseline 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 evenodd 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
Lib2geomdevel mailing list Lib2geomdevel@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/lib2geomdevel
Not much to report unfortunately  I was taking care of final exams for the past ~3 weeks.
Right now my first Inkscaperelated 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 evenodd fills.
Regards, Krzysztof
20150703 10:32 GMT+02:00 Tavmjong Bah <tavmjong@...8...>:
Any updates?
On Mon, 20150601 at 15:05 +0200, Krzysztof Kosiński wrote:
20150531 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 ellipseline 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 evenodd 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
Lib2geomdevel mailing list Lib2geomdevel@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/lib2geomdevel
participants (5)

Krzysztof Kosiński

Martin Owens

mathog

Nathan Hurst

Tavmjong Bah