Hello
The midterm evaluations are near due, so here's a public update on my GSoC project.
The schedule this year was very bad for me, and dealing with university stuff ate most of my time in the first half of the project, so I didn't do nearly as much as I hoped for. I have however made a prototype CGAL-based implementation of boolops. It is available in 2Geom trunk; you have to have CGAL installed, its headers available in your default include path, and set the CMake option CGAL_TOYS=ON to compile it. Saying "sudo apt-get install libcgal-dev" suffices to satisfy the first two requirements on Ubuntu 14.04.
The results of playing with this toy are rather disappointing. CGAL produces visibly imprecise results even for simple shapes (see attached pictures), and for some inputs (e.g. when sliding two bananas over each other so that they nearly match) it crashes with an assertion. It seems that its boolean operation algorithm for Beziers is of very poor quality. This means I will have to write the boolops code from scratch.
I've found a MIT-licensed Objective-C library that implements boolops on Bezier paths, which may serve as an inspiration. https://bitbucket.org/andyfinnell/vectorboolean
During the remaining time before midterm, I'll work on path-related APIs in 2Geom. This will be useful when implementing boolops, and will allow us to get rid of ugly ancient stuff in Inkscape, such as SPCurve. After the midterm, I will have to complete a final assignment at the university, and should have much more time to get useful work done in the second half of the project.
Regards, Krzysztof
Hey Krzysztof,
Thank you for the update. After playing with that cgal toy here, it is indeed disappointing... definitely a shame their implementation wasn't more robust. Given that the first half of GSoC has had a lot of unexpected time eaten up by University stuff, in addition to API related tasks you've designated, would you be willing to put forth an estimated timeline for what you would expect to accomplish in the second half?
Cheers, Josh
On Wed, Jun 25, 2014 at 5:51 AM, Krzysztof Kosiński <tweenk.pl@...972.....> wrote:
Hello
The midterm evaluations are near due, so here's a public update on my GSoC project.
The schedule this year was very bad for me, and dealing with university stuff ate most of my time in the first half of the project, so I didn't do nearly as much as I hoped for. I have however made a prototype CGAL-based implementation of boolops. It is available in 2Geom trunk; you have to have CGAL installed, its headers available in your default include path, and set the CMake option CGAL_TOYS=ON to compile it. Saying "sudo apt-get install libcgal-dev" suffices to satisfy the first two requirements on Ubuntu 14.04.
The results of playing with this toy are rather disappointing. CGAL produces visibly imprecise results even for simple shapes (see attached pictures), and for some inputs (e.g. when sliding two bananas over each other so that they nearly match) it crashes with an assertion. It seems that its boolean operation algorithm for Beziers is of very poor quality. This means I will have to write the boolops code from scratch.
I've found a MIT-licensed Objective-C library that implements boolops on Bezier paths, which may serve as an inspiration. https://bitbucket.org/andyfinnell/vectorboolean
During the remaining time before midterm, I'll work on path-related APIs in 2Geom. This will be useful when implementing boolops, and will allow us to get rid of ugly ancient stuff in Inkscape, such as SPCurve. After the midterm, I will have to complete a final assignment at the university, and should have much more time to get useful work done in the second half of the project.
Regards, Krzysztof
Open source business process management suite built on Java and Eclipse Turn processes into business applications with Bonita BPM Community Edition Quickly connect people, data, and systems into organized workflows Winner of BOSSIE, CODIE, OW2 and Gartner awards http://p.sf.net/sfu/Bonitasoft _______________________________________________ Inkscape-devel mailing list Inkscape-devel@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/inkscape-devel
2014-06-25 17:41 GMT+02:00 Josh Andler <scislac@...400...>:
Hey Krzysztof,
Thank you for the update. After playing with that cgal toy here, it is indeed disappointing... definitely a shame their implementation wasn't more robust. Given that the first half of GSoC has had a lot of unexpected time eaten up by University stuff, in addition to API related tasks you've designated, would you be willing to put forth an estimated timeline for what you would expect to accomplish in the second half?
In the next two days, I want to complete some of the path API rewrite. I want to do at least some of the following: 1. Rename Path to SubPath, 2. Rename PathVector to Path, 3. Convert Path to a real class, 4. Improve PathSink and related classes, 5. Convert the pathv_to_linear_and_cubic_beziers() function to a derived PathSink and put it in 2Geom, 6. Create a more efficient storage format for curve data (I'll post the details in the 2Geom mailing list).
After that, I'll have one more university assignment to complete, and I'm attending an NMR-related conference between June 29 and July 4. Once I return, the rough plan is:
1. Create generic curve intersection APIs. 2. Improve the APIs for determining winding numbers. 3. Implement a sweepline-based intersector for collections of curves. 4. Based on the above, implement uncrossing.
Further work will depend on how much success I have with uncrossing and handling its corner cases.
I estimate that the first three items (intersection, winding, sweepline intersector) should be done until mid-July.
Regards, Krzysztof
Hi Krzysz, I was thinking about some Visitor pattern for traversing a Path's Curves, e.g. to get rid of all the dynamic_casting going on when converting curves to svgd. What do you think?
cheers, Johan
On 25-6-2014 20:19, Krzysztof Kosiński wrote:
2014-06-25 17:41 GMT+02:00 Josh Andler <scislac@...400...>:
Hey Krzysztof,
Thank you for the update. After playing with that cgal toy here, it is indeed disappointing... definitely a shame their implementation wasn't more robust. Given that the first half of GSoC has had a lot of unexpected time eaten up by University stuff, in addition to API related tasks you've designated, would you be willing to put forth an estimated timeline for what you would expect to accomplish in the second half?
In the next two days, I want to complete some of the path API rewrite. I want to do at least some of the following:
- Rename Path to SubPath,
- Rename PathVector to Path,
- Convert Path to a real class,
- Improve PathSink and related classes,
- Convert the pathv_to_linear_and_cubic_beziers() function to a
derived PathSink and put it in 2Geom, 6. Create a more efficient storage format for curve data (I'll post the details in the 2Geom mailing list).
After that, I'll have one more university assignment to complete, and I'm attending an NMR-related conference between June 29 and July 4. Once I return, the rough plan is:
- Create generic curve intersection APIs.
- Improve the APIs for determining winding numbers.
- Implement a sweepline-based intersector for collections of curves.
- Based on the above, implement uncrossing.
Further work will depend on how much success I have with uncrossing and handling its corner cases.
I estimate that the first three items (intersection, winding, sweepline intersector) should be done until mid-July.
Regards, Krzysztof
Open source business process management suite built on Java and Eclipse Turn processes into business applications with Bonita BPM Community Edition Quickly connect people, data, and systems into organized workflows Winner of BOSSIE, CODIE, OW2 and Gartner awards http://p.sf.net/sfu/Bonitasoft _______________________________________________ Inkscape-devel mailing list Inkscape-devel@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/inkscape-devel
2014-06-25 20:35 GMT+02:00 Johan Engelen <jbc.engelen@...2592...>:
Hi Krzysz, I was thinking about some Visitor pattern for traversing a Path's Curves, e.g. to get rid of all the dynamic_casting going on when converting curves to svgd. What do you think?
PathSink is a visitor object. We would only need to add a virtual method called sink(PathSink &) to each Curve. This looks like a good suggestion and would simplify the implementation of the methods that feed a path or pathvector to the sink.
BTW, 2Geom doesn't have any code to actually write svgd strings, only to parse them. There is such code in Inkscape, but it needs to be rewritten in terms of a PathSink and improved so that the last non-linear segment before a closepath command is always written out using absolute coordinates, to fix this bug: https://bugs.launchpad.net/inkscape/+bug/515237
Regards, Krzysztof
On 25-6-2014 20:19, Krzysztof Kosiński wrote:
2014-06-25 17:41 GMT+02:00 Josh Andler <scislac@...400...>:
Hey Krzysztof,
Thank you for the update. After playing with that cgal toy here, it is indeed disappointing... definitely a shame their implementation wasn't more robust. Given that the first half of GSoC has had a lot of unexpected time eaten up by University stuff, in addition to API related tasks you've designated, would you be willing to put forth an estimated timeline for what you would expect to accomplish in the second half?
In the next two days, I want to complete some of the path API rewrite. I want to do at least some of the following:
- Rename Path to SubPath,
- Rename PathVector to Path,
I agree that PathVector is a poor name (plus I am not sure if inheriting from std::vector is allowed..., definitely needs improvement as you've planned). But I think we should not rename Path. I think it is a better name than SubPath, which could be taken to mean a part of a contiguous path, instead of its intent "contiguous path". It would be strange for a user that only works with contiguous paths to use SubPath instead of Path, I think. (let's not make 2Geom too SVG-biased in naming) So let's come up with a better name for PathVector. Some names that come to mind: MultiPath PathSet
anyone?
regards, Johan
On Wed, Jun 25, 2014 at 08:49:40PM +0200, Johan Engelen wrote:
On 25-6-2014 20:19, Krzysztof Kosiński wrote:
2014-06-25 17:41 GMT+02:00 Josh Andler <scislac@...400...>:
Hey Krzysztof,
Thank you for the update. After playing with that cgal toy here, it is indeed disappointing... definitely a shame their implementation wasn't more robust. Given that the first half of GSoC has had a lot of unexpected time eaten up by University stuff, in addition to API related tasks you've designated, would you be willing to put forth an estimated timeline for what you would expect to accomplish in the second half?
In the next two days, I want to complete some of the path API rewrite. I want to do at least some of the following:
- Rename Path to SubPath,
- Rename PathVector to Path,
I agree that PathVector is a poor name (plus I am not sure if inheriting from std::vector is allowed..., definitely needs improvement as you've planned).
Inheriting instead of lifting is definitely an antipattern (it's a shame it's such a pain to lift in c++). We should definitely fix this.
But I think we should not rename Path. I think it is a better name than SubPath, which could be taken to mean a part of a contiguous path, instead of its intent "contiguous path". It would be strange for a user that only works with contiguous paths to use SubPath instead of Path, I think. (let's not make 2Geom too SVG-biased in naming) So let's come up with a better name for PathVector. Some names that come to mind: MultiPath
A little vague.
PathSet
It's an ordered set.
PathVector is my vote :)
njh
On 25-6-2014 21:20, Nathan Hurst wrote:
On Wed, Jun 25, 2014 at 08:49:40PM +0200, Johan Engelen wrote:
On 25-6-2014 20:19, Krzysztof Kosiński wrote:
2014-06-25 17:41 GMT+02:00 Josh Andler <scislac@...400...>:
Hey Krzysztof,
Thank you for the update. After playing with that cgal toy here, it is indeed disappointing... definitely a shame their implementation wasn't more robust. Given that the first half of GSoC has had a lot of unexpected time eaten up by University stuff, in addition to API related tasks you've designated, would you be willing to put forth an estimated timeline for what you would expect to accomplish in the second half?
In the next two days, I want to complete some of the path API rewrite. I want to do at least some of the following:
- Rename Path to SubPath,
- Rename PathVector to Path,
I agree that PathVector is a poor name (plus I am not sure if inheriting from std::vector is allowed..., definitely needs improvement as you've planned).
Inheriting instead of lifting is definitely an antipattern (it's a shame it's such a pain to lift in c++). We should definitely fix this.
But I think we should not rename Path. I think it is a better name than SubPath, which could be taken to mean a part of a contiguous path, instead of its intent "contiguous path". It would be strange for a user that only works with contiguous paths to use SubPath instead of Path, I think. (let's not make 2Geom too SVG-biased in naming) So let's come up with a better name for PathVector. Some names that come to mind: MultiPath
A little vague.
PathSet
It's an ordered set.
PathVector is my vote :)
If anything, keeping the name means less work for 2Geom's users...
-Johan
2014-06-25 21:20 GMT+02:00 Nathan Hurst <njh@...1927...>:
But I think we should not rename Path. I think it is a better name than SubPath, which could be taken to mean a part of a contiguous path, instead of its intent "contiguous path". It would be strange for a user that only works with contiguous paths to use SubPath instead of Path, I think. (let's not make 2Geom too SVG-biased in naming) So let's come up with a better name for PathVector. Some names that come to mind: MultiPath
A little vague.
PathSet
It's an ordered set.
PathVector is my vote :)
What about PathSequence? CompoundPath also sounds interesting.
For now I will keep the existing class name and clean up the interface.
Regards, Krzysztof
What about "CompoundPath"?
Didn't know this beforehand, but try googling for compound path: apparently this name is being used in Illustrator too.
Diederik
On Wed, Jun 25, 2014 at 8:49 PM, Johan Engelen <jbc.engelen@...2592...> wrote:
On 25-6-2014 20:19, Krzysztof Kosiński wrote:
2014-06-25 17:41 GMT+02:00 Josh Andler <scislac@...400...>:
Hey Krzysztof,
Thank you for the update. After playing with that cgal toy here, it is indeed disappointing... definitely a shame their implementation wasn't
more
robust. Given that the first half of GSoC has had a lot of unexpected
time
eaten up by University stuff, in addition to API related tasks you've designated, would you be willing to put forth an estimated timeline for
what
you would expect to accomplish in the second half?
In the next two days, I want to complete some of the path API rewrite. I want to do at least some of the following:
- Rename Path to SubPath,
- Rename PathVector to Path,
I agree that PathVector is a poor name (plus I am not sure if inheriting from std::vector is allowed..., definitely needs improvement as you've planned). But I think we should not rename Path. I think it is a better name than SubPath, which could be taken to mean a part of a contiguous path, instead of its intent "contiguous path". It would be strange for a user that only works with contiguous paths to use SubPath instead of Path, I think. (let's not make 2Geom too SVG-biased in naming) So let's come up with a better name for PathVector. Some names that come to mind: MultiPath PathSet
anyone?
regards, Johan
Open source business process management suite built on Java and Eclipse Turn processes into business applications with Bonita BPM Community Edition Quickly connect people, data, and systems into organized workflows Winner of BOSSIE, CODIE, OW2 and Gartner awards http://p.sf.net/sfu/Bonitasoft _______________________________________________ Inkscape-devel mailing list Inkscape-devel@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/inkscape-devel
participants (5)
-
Diederik van Lierop -
Johan Engelen -
Josh Andler -
Krzysztof Kosiński -
Nathan Hurst