You can subscribe to this list here.
2007 
_{Jan}
(2) 
_{Feb}
(3) 
_{Mar}
(4) 
_{Apr}
(27) 
_{May}
(5) 
_{Jun}

_{Jul}
(14) 
_{Aug}

_{Sep}
(1) 
_{Oct}
(4) 
_{Nov}
(19) 
_{Dec}


2008 
_{Jan}
(8) 
_{Feb}
(1) 
_{Mar}
(4) 
_{Apr}
(28) 
_{May}
(77) 
_{Jun}
(79) 
_{Jul}
(112) 
_{Aug}
(36) 
_{Sep}
(33) 
_{Oct}
(19) 
_{Nov}
(9) 
_{Dec}
(11) 
2009 
_{Jan}

_{Feb}

_{Mar}
(12) 
_{Apr}
(11) 
_{May}
(13) 
_{Jun}
(23) 
_{Jul}
(5) 
_{Aug}
(25) 
_{Sep}
(9) 
_{Oct}
(22) 
_{Nov}
(16) 
_{Dec}
(5) 
2010 
_{Jan}
(23) 
_{Feb}
(12) 
_{Mar}
(5) 
_{Apr}
(29) 
_{May}
(4) 
_{Jun}
(9) 
_{Jul}
(22) 
_{Aug}
(2) 
_{Sep}
(10) 
_{Oct}
(6) 
_{Nov}
(8) 
_{Dec}

2011 
_{Jan}
(2) 
_{Feb}
(44) 
_{Mar}

_{Apr}
(4) 
_{May}

_{Jun}
(9) 
_{Jul}
(5) 
_{Aug}
(4) 
_{Sep}
(7) 
_{Oct}

_{Nov}

_{Dec}
(10) 
2012 
_{Jan}
(16) 
_{Feb}
(8) 
_{Mar}
(9) 
_{Apr}
(5) 
_{May}
(3) 
_{Jun}
(3) 
_{Jul}
(6) 
_{Aug}
(10) 
_{Sep}
(48) 
_{Oct}
(6) 
_{Nov}

_{Dec}

2013 
_{Jan}

_{Feb}

_{Mar}

_{Apr}

_{May}

_{Jun}

_{Jul}

_{Aug}
(19) 
_{Sep}
(3) 
_{Oct}
(5) 
_{Nov}
(35) 
_{Dec}
(3) 
2014 
_{Jan}

_{Feb}
(3) 
_{Mar}
(4) 
_{Apr}
(12) 
_{May}
(6) 
_{Jun}
(16) 
_{Jul}
(25) 
_{Aug}
(16) 
_{Sep}
(3) 
_{Oct}

_{Nov}
(7) 
_{Dec}

2015 
_{Jan}
(3) 
_{Feb}
(1) 
_{Mar}
(21) 
_{Apr}
(10) 
_{May}
(6) 
_{Jun}
(3) 
_{Jul}
(2) 
_{Aug}
(4) 
_{Sep}
(4) 
_{Oct}

_{Nov}
(2) 
_{Dec}

From: Stuart Axon <stuaxo2@ya...>  20151114 17:00:24

Hi all Thought I'd have a go at building 2geom, it got stuck on beziertest though.. I grabbed the latest version with bzr then did mkdir buildcd buildcmake ..make output on pastebin: 2geom build output  Pastebin.com            2geom build output  Pastebin.com$ make [ 0%] Building CXX object src/2geom/CMakeFiles/2geom.dir/bezierclipping.cpp.o [ 1%] Building CXX object src/2geom/CMakeFiles/2geom.dir/bezierc...     View on pastebin.com  Preview by Yahoo      S++ 
From: Jenkins (build tester) <inkscape.jenkins@gm...>  20151105 09:25:55

Hi developers, I found a problem with one of the builds: 2Geom_trunk_unittests  Build # 57  Failure: Check console output at http://jenkins.inkscape.org/job/2Geom_trunk_unittests/57/ to view the results. Your friend, Jenkins http://jenkins.inkscape.org 
From: Johan Engelen <jbc.engelen@sw...>  20150913 17:31:38

No worries. It was me working on gettings things running again. I removed the failures because they weren't. cheers, Johan On 1292015 17:40, Krzysztof Kosiński wrote: > This is strange  these failing builds #41 and #42 are missing from > the Jenkins web interface. Probably a Jenkins error? > > Regards, Krzysztof > > 20150911 22:42 GMT+02:00 Jenkins (build tester) <inkscape.jenkins@...>: >> Hi developers, >> I found a problem with one of the builds: >> 2Geom_trunk_scanbuild  Build # 42  Failure: >> >> Check console output at http://jenkins.inkscape.org/job/2Geom_trunk_scanbuild/42/ to view the results. >> >> Your friend, >> Jenkins >> http://jenkins.inkscape.org >>  >> >> _______________________________________________ >> Lib2geomdevel mailing list >> Lib2geomdevel@... >> https://lists.sourceforge.net/lists/listinfo/lib2geomdevel >> >  > _______________________________________________ > Lib2geomdevel mailing list > Lib2geomdevel@... > https://lists.sourceforge.net/lists/listinfo/lib2geomdevel > 
From: Krzysztof Kosiński <tweenk.pl@gm...>  20150912 15:40:59

This is strange  these failing builds #41 and #42 are missing from the Jenkins web interface. Probably a Jenkins error? Regards, Krzysztof 20150911 22:42 GMT+02:00 Jenkins (build tester) <inkscape.jenkins@...>: > Hi developers, > I found a problem with one of the builds: > 2Geom_trunk_scanbuild  Build # 42  Failure: > > Check console output at http://jenkins.inkscape.org/job/2Geom_trunk_scanbuild/42/ to view the results. > > Your friend, > Jenkins > http://jenkins.inkscape.org >  > > _______________________________________________ > Lib2geomdevel mailing list > Lib2geomdevel@... > https://lists.sourceforge.net/lists/listinfo/lib2geomdevel > 
From: Jenkins (build tester) <inkscape.jenkins@gm...>  20150911 20:42:08

Hi developers, I found a problem with one of the builds: 2Geom_trunk_scanbuild  Build # 42  Failure: Check console output at http://jenkins.inkscape.org/job/2Geom_trunk_scanbuild/42/ to view the results. Your friend, Jenkins http://jenkins.inkscape.org 
From: Jenkins (build tester) <inkscape.jenkins@gm...>  20150911 20:20:27

Hi developers, I found a problem with one of the builds: 2Geom_trunk_scanbuild  Build # 41  Failure: Check console output at http://jenkins.inkscape.org/job/2Geom_trunk_scanbuild/41/ to view the results. Your friend, Jenkins http://jenkins.inkscape.org 
From: Krzysztof Kosiński <tweenk.pl@gm...>  20150813 14:41:44

Okay, I'll get this patched then. 20150813 16:39 GMT+02:00 Alvin Penner <penner@...>: > Sounds like a good idea, a somewhat similar problem occurred recently in > https://bugs.launchpad.net/inkscape/+bug/1473317 > > Unfortunately, I don't know how to actually do this. My C programming skills > are limited to microprocessors that are 15 years old and still use integer > arithmetic. > > Alvin > > > At 08:50 AM 8/13/2015, Krzysztof KosiÅ„ski wrote: >> >> Instead of changing the unary minus operator, the default constructor >> for SBasis should be changed so that it creates an SBasis that is >> identically zero (i.e. contains only one Linear(0, 0)). Null values >> should not be representable in the SBasis object, and there should >> assertions everywhere verifying that there is at least one element; no >> member functions should ever remove the last Linear. >> >> Regards, Krzysztof >> >> 20150813 2:11 GMT+02:00 Alvin Penner <penner@...>: >> > Hi, >> > this is a request for comment on a proposed fix for Bug 1482806. >> > The >> > bug is apparently caused by returning a null value when attempting to >> > take the unary negative of an sbasis which is zero. The proposed code >> > returns the original sbasis instead. Any comments on whether this is >> > acceptable? The code is fairly deeply embedded, so it may have >> > implications elsewhere. >> > >> > Alvin Penner >> > >> > >> > >> >  >> > _______________________________________________ >> > Lib2geomdevel mailing list >> > Lib2geomdevel@... >> > https://lists.sourceforge.net/lists/listinfo/lib2geomdevel > > 
From: Alvin Penner <penner@va...>  20150813 14:39:52

Sounds like a good idea, a somewhat similar problem occurred recently in https://bugs.launchpad.net/inkscape/+bug/1473317 Unfortunately, I don't know how to actually do this. My C programming skills are limited to microprocessors that are 15 years old and still use integer arithmetic. Alvin At 08:50 AM 8/13/2015, Krzysztof KosiÅski wrote: >Instead of changing the unary minus operator, the default constructor >for SBasis should be changed so that it creates an SBasis that is >identically zero (i.e. contains only one Linear(0, 0)). Null values >should not be representable in the SBasis object, and there should >assertions everywhere verifying that there is at least one element; no >member functions should ever remove the last Linear. > >Regards, Krzysztof > >20150813 2:11 GMT+02:00 Alvin Penner <penner@...>: > > Hi, > > this is a request for comment on a > proposed fix for Bug 1482806. The > > bug is apparently caused by returning a null value when attempting to > > take the unary negative of an sbasis which is zero. The proposed code > > returns the original sbasis instead. Any comments on whether this is > > acceptable? The code is fairly deeply embedded, so it may have > > implications elsewhere. > > > > Alvin Penner > > > > > > >  > > _______________________________________________ > > Lib2geomdevel mailing list > > Lib2geomdevel@... > > https://lists.sourceforge.net/lists/listinfo/lib2geomdevel 
From: Krzysztof Kosiński <tweenk.pl@gm...>  20150813 12:50:50

Instead of changing the unary minus operator, the default constructor for SBasis should be changed so that it creates an SBasis that is identically zero (i.e. contains only one Linear(0, 0)). Null values should not be representable in the SBasis object, and there should assertions everywhere verifying that there is at least one element; no member functions should ever remove the last Linear. Regards, Krzysztof 20150813 2:11 GMT+02:00 Alvin Penner <penner@...>: > Hi, > this is a request for comment on a proposed fix for Bug 1482806. The > bug is apparently caused by returning a null value when attempting to > take the unary negative of an sbasis which is zero. The proposed code > returns the original sbasis instead. Any comments on whether this is > acceptable? The code is fairly deeply embedded, so it may have > implications elsewhere. > > Alvin Penner > > >  > _______________________________________________ > Lib2geomdevel mailing list > Lib2geomdevel@... > https://lists.sourceforge.net/lists/listinfo/lib2geomdevel 
From: Alvin Penner <penner@va...>  20150813 00:31:09

Hi, this is a request for comment on a proposed fix for Bug 1482806. The bug is apparently caused by returning a null value when attempting to take the unary negative of an sbasis which is zero. The proposed code returns the original sbasis instead. Any comments on whether this is acceptable? The code is fairly deeply embedded, so it may have implications elsewhere. Alvin Penner 
From: Krzysztof Kosiński <tweenk.pl@gm...>  20150704 00:12:14

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@...>: > > Any updates? > > > On Mon, 20150601 at 15:05 +0200, Krzysztof Kosiński wrote: >> 20150531 3:21 GMT+02:00 Nathan Hurst <njh@...>: >> > 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@... >> https://lists.sourceforge.net/lists/listinfo/lib2geomdevel > > 
From: Tavmjong Bah <tavmjong@fr...>  20150703 08:33:01

Any updates? On Mon, 20150601 at 15:05 +0200, Krzysztof Kosiński wrote: > 20150531 3:21 GMT+02:00 Nathan Hurst <njh@...>: > > 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@... > https://lists.sourceforge.net/lists/listinfo/lib2geomdevel 
From: Nathan Hurst <njh@nj...>  20150603 18:06:24

I think I had a response to your earlier post but I don't think I ever sent it. Anyway, looks promising. Why not implement it and we can see how well it performs in practice. That's always the real test :) If you can get a reasonably tight bound root polishing will work well. roots() is very fast for low order polynomials (e.g. cubic) btw (100 ns). I would suggest transforming problems into roots() and benchmarking before spending time on other approaches, as it's very hard to beat. hausdorf distance turns out to be a bad measure for curve comparison because it induces zigzags. https://en.wikipedia.org/wiki/Fr%C3%A9chet_distance is much better in this regard. I might be missing something, but you are computing and approximation of argmin_t p(t)  q(t), but what you actually need is argmin_{s,t} p(s)  q(t). Consider a line broken into two touching segments: although the distance is 0, your algorithm will find the distance to be the length of the curve. This could be solved with some kind of subdivision algorithm, but then you're back to the frechet polygon problem, with bounds. njh On Wed, Jun 03, 2015 at 04:10:11PM +0200, Alexander Brock wrote: > On 07/04/15 10:51, Alexander Brock wrote: > > https://github.com/abrock/optimization (I'll give push rights to anyone > > who asks) > > I have two new estimations of the maximum distance, both do not depend > on finding roots of polynomials (sections 0.3 and 0.4). > > Regards > Alexander > >  > _______________________________________________ > Lib2geomdevel mailing list > Lib2geomdevel@... > https://lists.sourceforge.net/lists/listinfo/lib2geomdevel 
From: Alexander Brock <Brock.A<lexander@we...>  20150603 14:10:19

On 07/04/15 10:51, Alexander Brock wrote: > https://github.com/abrock/optimization (I'll give push rights to anyone > who asks) I have two new estimations of the maximum distance, both do not depend on finding roots of polynomials (sections 0.3 and 0.4). Regards Alexander 
From: Krzysztof Kosiński <tweenk.pl@gm...>  20150601 13:05:41

20150531 3:21 GMT+02:00 Nathan Hurst <njh@...>: > 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 
From: Nathan Hurst <njh@nj...>  20150531 01:21:21

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@...>: > > On Mon, Apr 20, 2015 at 02:18:36PM +0200, Krzysztof Kosiński wrote: > >> 20150420 7:15 GMT+02:00 Nathan Hurst <njh@...>: > >> >>  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 
From: Krzysztof Kosiński <tweenk.pl@gm...>  20150523 13:26:09

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@...>: > On Mon, Apr 20, 2015 at 02:18:36PM +0200, Krzysztof Kosiński wrote: >> 20150420 7:15 GMT+02:00 Nathan Hurst <njh@...>: >> >>  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 
From: Jabier Arraiza <jabier.arraiza@ma...>  20150520 13:39:00

Great! I can focus in my current work in "switch" code. Regards, Jabier. On Wed, 20150520 at 15:06 +0200, Krzysztof Kosiński wrote: > 20150519 21:33 GMT+02:00 Jabiertxo Arraiza Cenoz <jabier.arraiza@...>: > > El sáb, 16052015 a las 08:15 +0000, > > lib2geomdevelrequest@... escribió: > >> > What works: > >> >  Union > >> >  Intersection > >> >  Adding difference and XOR is trivial > >> > >> Perhaps someone else could implement them as a learnthecode > >> experience, Jabier? > > > > Hi Nathan. Not sure if my basic math could do it but i could try. Still > > on TODO? > > > > Regards, Jabier. > > I went ahead and added those already, sorry :( > > Boolops should be complete now, with the exception of handling > degenerate cases such as overlapping segments and nodes exactly at > segments. I will be working on that next. > > Regards, Krzysztof 
From: Krzysztof Kosiński <tweenk.pl@gm...>  20150520 13:06:11

20150519 21:33 GMT+02:00 Jabiertxo Arraiza Cenoz <jabier.arraiza@...>: > El sáb, 16052015 a las 08:15 +0000, > lib2geomdevelrequest@... escribió: >> > What works: >> >  Union >> >  Intersection >> >  Adding difference and XOR is trivial >> >> Perhaps someone else could implement them as a learnthecode >> experience, Jabier? > > Hi Nathan. Not sure if my basic math could do it but i could try. Still > on TODO? > > Regards, Jabier. I went ahead and added those already, sorry :( Boolops should be complete now, with the exception of handling degenerate cases such as overlapping segments and nodes exactly at segments. I will be working on that next. Regards, Krzysztof 
From: Jabiertxo Arraiza Cenoz <jabier.arraiza@ma...>  20150519 19:34:05

El sáb, 16052015 a las 08:15 +0000, lib2geomdevelrequest@... escribió: > > What works: > >  Union > >  Intersection > >  Adding difference and XOR is trivial > > Perhaps someone else could implement them as a learnthecode > experience, Jabier? Hi Nathan. Not sure if my basic math could do it but i could try. Still on TODO? Regards, Jabier. 
From: Jenkins (build tester) <inkscape.jenkins@gm...>  20150516 08:15:19

Hi developers, I found a problem with one of the builds: 2Geom_trunk_scanbuild  Build # 28  Failure: Check console output at http://jenkins.inkscape.org/job/2Geom_trunk_scanbuild/28/ to view the results. Your friend, Jenkins http://jenkins.inkscape.org 
From: Jenkins (build tester) <inkscape.jenkins@gm...>  20150427 08:24:47

Hi developers, I found a problem with one of the builds: 2Geom_trunk_unittests  Build # 22  Failure: Check console output at http://jenkins.inkscape.org/job/2Geom_trunk_unittests/22/ to view the results. Your friend, Jenkins http://jenkins.inkscape.org 
From: Nathan Hurst <njh@nj...>  20150426 04:10:47

On Mon, Apr 20, 2015 at 02:18:36PM +0200, Krzysztof Kosiński wrote: > 20150420 7:15 GMT+02:00 Nathan Hurst <njh@...>: > >>  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 
From: Krzysztof Kosiński <tweenk.pl@gm...>  20150420 12:18:44

20150420 7:15 GMT+02:00 Nathan Hurst <njh@...>: >>  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 
From: Nathan Hurst <njh@nj...>  20150420 05:16:04

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 