Hello
As promised, here is a description of the project I could do as a student.
The end goal of my MSc project is to write an OpenGL-based 2D scene graph library usable by Inkscape which is capable of displaying most of SVG. Unlike the Cairo OpenGL backend, this library would keep the data on the GPU as long as it's used, and only control points of the curves would be submitted to the GPU, which should give very good performance.
However, this project has several prerequisites. The OpenGL drawing algorithm I'm thinking about (Loop-Blinn) handles only quadratic and cubic Bezier fills, so it would require substantial support from 2Geom to render SVG. http://http.developer.nvidia.com/GPUGems3/gpugems3_ch25.html
For this GSoC, my proposal would be to implement boolean operations and the stroke-to-fill transformation in 2Geom (since I think the latter depends on the former). Some of the required code is already present, for example the code to compute the offset of a single curve, but it's not exposed in an usable form. The project would be both about implementing the missing parts and providing an easy to use API.
Here are the potential work-items: 1. Convert Geom::PathVector to a real class. 2. Investigate whether it is possible to store curve data in a more efficient format that does not store every curve endpoint point twice (as a start point and as an end point). 3. Provide and document an API to the existing intersection code. 4. Provide and document an API to the existing curve offset code. 5. Implement path uncrossing and monotonization. 6. Implement boolean operations, based on the algorithm used in CGAL. If necessary, add CGAL as a dependency - this is now acceptable, because CGAL in Debian no longer depends on Qt. 7. Implement stroke-to-path.
As a backup option, I'm considering changing my MSc project to implementing a Python scripting console for Inkscape. If I were to pick that instead, the GSoC project could involve a variety of refactoring tasks intended to simplify writing the Python bindings used by the console. In this case, I'm 100% sure that I could do it, whereas in the case of OpenGL I still have some doubts, mainly because I haven't programmed in OpenGL yet.
Regards, Krzysztof
Hi Krzysz, Two small comments below:
On 25-2-2014 19:17, Krzysztof Kosiński wrote:
Hello
As promised, here is a description of the project I could do as a student.
The end goal of my MSc project is to write an OpenGL-based 2D scene graph library usable by Inkscape which is capable of displaying most of SVG. Unlike the Cairo OpenGL backend, this library would keep the data on the GPU as long as it's used, and only control points of the curves would be submitted to the GPU, which should give very good performance.
However, this project has several prerequisites. The OpenGL drawing algorithm I'm thinking about (Loop-Blinn) handles only quadratic and cubic Bezier fills, so it would require substantial support from 2Geom to render SVG. http://http.developer.nvidia.com/GPUGems3/gpugems3_ch25.html
For this GSoC, my proposal would be to implement boolean operations and the stroke-to-fill transformation in 2Geom (since I think the latter depends on the former). Some of the required code is already present, for example the code to compute the offset of a single curve, but it's not exposed in an usable form. The project would be both about implementing the missing parts and providing an easy to use API.
Here are the potential work-items:
- Convert Geom::PathVector to a real class.
- Investigate whether it is possible to store curve data in a more
efficient format that does not store every curve endpoint point twice (as a start point and as an end point).
Variant: see if we can store a specialized path type in a vectorizable way (e.g. only curve segments with 4x2 doubles/floats, no virtual functions, etc.) with some specialized implementations using compiler's vector attributes. This to speed up LPE calculations.
- Provide and document an API to the existing intersection code.
- Provide and document an API to the existing curve offset code.
- Implement path uncrossing and monotonization.
- Implement boolean operations, based on the algorithm used in CGAL.
If necessary, add CGAL as a dependency - this is now acceptable, because CGAL in Debian no longer depends on Qt. 7. Implement stroke-to-path.
As a backup option, I'm considering changing my MSc project to implementing a Python scripting console for Inkscape. If I were to pick that instead, the GSoC project could involve a variety of refactoring tasks intended to simplify writing the Python bindings used by the console. In this case, I'm 100% sure that I could do it, whereas in the case of OpenGL I still have some doubts, mainly because I haven't programmed in OpenGL yet.
It'd be great to finish Python bindings for 2Geom, whichever way. I.e., remove the half-finished things we have now, make Python bindings work on popular platforms, and convert a few extensions to py2geom. Most important part of this project would be: *finishing* it. 100% complete 2geom functionality is not needed, but it has to work on all platforms (build instructions, installation instructions, etc). Adding methods is easy afterwards.
cheers, Johan
On Tue, 2014-02-25 at 19:17 +0100, Krzysztof Kosiński wrote:
As a backup option, I'm considering changing my MSc project to implementing a Python scripting console for Inkscape. If I were to pick that instead, the GSoC project could involve a variety of refactoring tasks intended to simplify writing the Python bindings used by the console.
Wouldn't it be better to complete the DBus bindings for inkscape? Python has a very good dbus implantation that could be effectively wrapped for such a thing allowing process separation between python code operating on drawings and inkscape codebase.
Then it's just a matter of launching extensions with the dbus drawing id and let the wrapper take care of interacting with inkscape. you could have a python shell, live drawing extensions... lots of things really.
The tricky point is getting dbus working on windows. http://www.freedesktop.org/wiki/Software/dbus/#index6h1 It should be possible to depend on the in-tree windows port from fdo's development branch if it works. Since it's windows we don't need to care too much if something is packaged or stable beyond stable enough for inkscape.
Martin,
2014-02-25 23:04 GMT+01:00 Martin Owens <doctormo@...400...>:
On Tue, 2014-02-25 at 19:17 +0100, Krzysztof Kosiński wrote:
As a backup option, I'm considering changing my MSc project to implementing a Python scripting console for Inkscape. If I were to pick that instead, the GSoC project could involve a variety of refactoring tasks intended to simplify writing the Python bindings used by the console.
Wouldn't it be better to complete the DBus bindings for inkscape? Python has a very good dbus implantation that could be effectively wrapped for such a thing allowing process separation between python code operating on drawings and inkscape codebase.
The main reason behind the existence of the DBus API would be programming language neutral, so you can theoretically write plugins in any language. However, language neutrality is actually not that great when it comes to plugins. To fix a bug in an existing script, you have to know its language, and it could be anything.
Moreover, binding things via DBus adds lots of complexity which simply don't exist in a simple Python binding. According to the "worse is better" principle, using the simpler solution will cause usable features to be developed much more quickly, even if this solution is not technically ideal.
Then it's just a matter of launching extensions with the dbus drawing id and let the wrapper take care of interacting with inkscape. you could have a python shell, live drawing extensions... lots of things really.
All of this would still work over IPC, so the performance wouldn't be that great. While implementing a new interactive tool in a Python plugin is entirely possible, doing it in a different process might be too much.
The tricky point is getting dbus working on windows. http://www.freedesktop.org/wiki/Software/dbus/#index6h1 It should be possible to depend on the in-tree windows port from fdo's development branch if it works. Since it's windows we don't need to care too much if something is packaged or stable beyond stable enough for inkscape.
Given the recent developments (kdbus), it seems to me that DBus is not really intended as a cross-platform solution.
Anyway, this is a backup project - my main idea is boolops / stroke-to-path.
Regards, Krzysztof
On Tue, Feb 25, 2014 at 3:42 PM, Krzysztof Kosiński <tweenk.pl@...400...>wrote:
Anyway, this is a backup project - my main idea is boolops / stroke-to-path.
I prefer your main idea for many reasons, but mostly because it will really open the door to better implementations of various things in Inkscape. :)
Cheers, Josh
On Wed, 2014-02-26 at 00:42 +0100, Krzysztof Kosiński wrote:
2014-02-25 23:04 GMT+01:00 Martin Owens <doctormo@...400...>:
On Tue, 2014-02-25 at 19:17 +0100, Krzysztof Kosiński wrote:
As a backup option, I'm considering changing my MSc project to implementing a Python scripting console for Inkscape. If I were to pick that instead, the GSoC project could involve a variety of refactoring tasks intended to simplify writing the Python bindings used by the console.
Wouldn't it be better to complete the DBus bindings for inkscape? Python has a very good dbus implantation that could be effectively wrapped for such a thing allowing process separation between python code operating on drawings and inkscape codebase.
The main reason behind the existence of the DBus API would be programming language neutral, so you can theoretically write plugins in any language. However, language neutrality is actually not that great when it comes to plugins. To fix a bug in an existing script, you have to know its language, and it could be anything.
Well, not quite. The main reason for the DBus API was to write a Python console for Inkscape :-) That's one of the reasons for its simplicity in that it was mostly targeted at simpler operations that giving the full functionality. But it is true that one of the reasons to use DBus was so that shells could be developed for different languages, the student doing it was specifically interested in a scheme console a la AutoCAD.
The tricky point is getting dbus working on windows. http://www.freedesktop.org/wiki/Software/dbus/#index6h1 It should be possible to depend on the in-tree windows port from fdo's development branch if it works. Since it's windows we don't need to care too much if something is packaged or stable beyond stable enough for inkscape.
Given the recent developments (kdbus), it seems to me that DBus is not really intended as a cross-platform solution.
libdbus will continue to choose which protocol works on the given system. So it won't change in that regard, it will just use kdbus if it's available.
Ted
On Tue, 2014-02-25 at 19:17 +0100, Krzysztof Kosiński wrote:
Hello
As promised, here is a description of the project I could do as a student.
The end goal of my MSc project is to write an OpenGL-based 2D scene graph library usable by Inkscape which is capable of displaying most of SVG. Unlike the Cairo OpenGL backend, this library would keep the data on the GPU as long as it's used, and only control points of the curves would be submitted to the GPU, which should give very good performance.
However, this project has several prerequisites. The OpenGL drawing algorithm I'm thinking about (Loop-Blinn) handles only quadratic and cubic Bezier fills, so it would require substantial support from 2Geom to render SVG. http://http.developer.nvidia.com/GPUGems3/gpugems3_ch25.html
For this GSoC, my proposal would be to implement boolean operations and the stroke-to-fill transformation in 2Geom (since I think the latter depends on the former). Some of the required code is already present, for example the code to compute the offset of a single curve, but it's not exposed in an usable form. The project would be both about implementing the missing parts and providing an easy to use API.
Here are the potential work-items:
- Convert Geom::PathVector to a real class.
- Investigate whether it is possible to store curve data in a more
efficient format that does not store every curve endpoint point twice (as a start point and as an end point). 3. Provide and document an API to the existing intersection code. 4. Provide and document an API to the existing curve offset code. 5. Implement path uncrossing and monotonization. 6. Implement boolean operations, based on the algorithm used in CGAL. If necessary, add CGAL as a dependency - this is now acceptable, because CGAL in Debian no longer depends on Qt. 7. Implement stroke-to-path.
This looks like a great project!
Two comments:
It would be nice if one could do boolean operations with paths with arcs and not have them turn into Beziers. It looks like CGAL supports this.
It would also be nice to be able to support CSS3 3d transforms (which already have some browser support for SVG), just as shown in the example in section 25.7 of the Nvidia GPUGems you referenced.
Tav
2014-02-26 16:37 GMT+01:00 Tavmjong Bah <tavmjong@...8...>:
It would be nice if one could do boolean operations with paths with arcs and not have them turn into Beziers. It looks like CGAL supports this.
The primary shortcoming of the CGAL algorithm is that is requires monotonization of the input curves, which leads to some unnecessary nodes being added, but this can be circumvented by storing pointers to the information about the original curve in the subdivided curves and then removing the superfluous subdivisions.
Even if we do end up depending on CGAL, I think there's still a lot of value in 2Geom, since at first glance the CGAL APIs look verbose and somewhat hard to use.
It would also be nice to be able to support CSS3 3d transforms (which already have some browser support for SVG), just as shown in the example in section 25.7 of the Nvidia GPUGems you referenced.
At the moment there is no support for projective transformations in 2Geom or Cairo, so this would be a longer term goal.
Regards, Krzysztof
On Wed, Feb 26, 2014 at 05:27:48PM +0100, Krzysztof Kosi??ski wrote:
2014-02-26 16:37 GMT+01:00 Tavmjong Bah <tavmjong@...8...>:
It would be nice if one could do boolean operations with paths with arcs and not have them turn into Beziers. It looks like CGAL supports this.
The primary shortcoming of the CGAL algorithm is that is requires monotonization of the input curves, which leads to some unnecessary nodes being added, but this can be circumvented by storing pointers to the information about the original curve in the subdivided curves and then removing the superfluous subdivisions.
Yes, and I think there is already code to do the monotonisation in 2Geom. It's very straightforward anyway - subdivide(roots(derivative(B))).
I'm excited about this project because already 3 or 4 people have had a go at it and not quite made it. It's surprisingly hard to implement. But cgal looks like it might get us there finally.
It would also be nice to be able to support CSS3 3d transforms (which already have some browser support for SVG), just as shown in the example in section 25.7 of the Nvidia GPUGems you referenced.
At the moment there is no support for projective transformations in 2Geom or Cairo, so this would be a longer term goal.
2Geom does have divide(curve, curve) so it's mostly about adding the matrix forms and providing a nice api.
njh
On Wed, Feb 26, 2014 at 05:27:48PM +0100, Krzysztof Kosiński wrote:
2014-02-26 16:37 GMT+01:00 Tavmjong Bah <tavmjong@...8...>:
It would be nice if one could do boolean operations with paths with arcs and not have them turn into Beziers. It looks like CGAL supports this.
The primary shortcoming of the CGAL algorithm is that is requires monotonization of the input curves, which leads to some unnecessary nodes being added, but this can be circumvented by storing pointers to the information about the original curve in the subdivided curves and then removing the superfluous subdivisions.
Even if we do end up depending on CGAL, I think there's still a lot of value in 2Geom, since at first glance the CGAL APIs look verbose and somewhat hard to use.
Could the CGAL algorithms you need be lifted and ported to 2geom?
It would also be nice to be able to support CSS3 3d transforms (which already have some browser support for SVG), just as shown in the example in section 25.7 of the Nvidia GPUGems you referenced.
At the moment there is no support for projective transformations in 2Geom or Cairo, so this would be a longer term goal.
Fwiw, I am working on projective transforms for Cairo. http://www.bryceharrington.org/files/projective-transform.ogv
Bryce
On Thu, 2014-02-27 at 01:56 -0800, Bryce Harrington wrote:
On Wed, Feb 26, 2014 at 05:27:48PM +0100, Krzysztof Kosiński wrote:
2014-02-26 16:37 GMT+01:00 Tavmjong Bah <tavmjong@...8...>:
It would also be nice to be able to support CSS3 3d transforms (which already have some browser support for SVG), just as shown in the example in section 25.7 of the Nvidia GPUGems you referenced.
At the moment there is no support for projective transformations in 2Geom or Cairo, so this would be a longer term goal.
Fwiw, I am working on projective transforms for Cairo. http://www.bryceharrington.org/files/projective-transform.ogv
Excellent!
Tav
2014-02-27 10:56 GMT+01:00 Bryce Harrington <bryce@...961...>:
The primary shortcoming of the CGAL algorithm is that is requires monotonization of the input curves, which leads to some unnecessary nodes being added, but this can be circumvented by storing pointers to the information about the original curve in the subdivided curves and then removing the superfluous subdivisions.
Even if we do end up depending on CGAL, I think there's still a lot of value in 2Geom, since at first glance the CGAL APIs look verbose and somewhat hard to use.
Could the CGAL algorithms you need be lifted and ported to 2geom?
CGAL evaluates things in arbitrary precision floating point arithmetic (using the MPFR library) if the result in doubles is ambiguous, which guarantees accurate results in edge cases. If the boolean algorithms depend on this, then it will be hard to extract all the necessary things into 2Geom, though I have not checked this yet. If they don't, it should be fairly simple.
CGAL also has a few other things I will need later when implementing the OpenGL renderer, for instance triangulation algorithms.
Regards, Krzysztof
On Thu, Feb 27, 2014 at 06:15:55PM +0100, Krzysztof Kosi??ski wrote:
CGAL evaluates things in arbitrary precision floating point arithmetic (using the MPFR library) if the result in doubles is ambiguous, which guarantees accurate results in edge cases. If the boolean algorithms depend on this, then it will be hard to extract all the necessary things into 2Geom, though I have not checked this yet. If they don't, it should be fairly simple.
Does the fact that 2Geom is templated across the numerical type help at all?
njh
2014-02-27 18:32 GMT+01:00 Nathan Hurst <njh@...1927...>:
On Thu, Feb 27, 2014 at 06:15:55PM +0100, Krzysztof Kosi??ski wrote:
CGAL evaluates things in arbitrary precision floating point arithmetic (using the MPFR library) if the result in doubles is ambiguous, which guarantees accurate results in edge cases. If the boolean algorithms depend on this, then it will be hard to extract all the necessary things into 2Geom, though I have not checked this yet. If they don't, it should be fairly simple.
Does the fact that 2Geom is templated across the numerical type help at all?
Is it? I don't see it. Points, matrices, fragments, etc. always use doubles. Some classes use Coord, which is a typedef of double, but others don't.
In any case, CGAL would be completely hidden from the user of 2Geom. Those two libraries have substantially different goals - CGAL emphasizes robustness and generality, while 2Geom emphasizes ease of use. If we could use some of CGAL's algorithms through the user-friendly 2Geom APIs we could have the best of both worlds.
Regards, Krzysztof
Em Ter, 2014-02-25 às 19:17 +0100, Krzysztof Kosiński escreveu:
The end goal of my MSc project is to write an OpenGL-based 2D scene graph library usable by Inkscape which is capable of displaying most of SVG. Unlike the Cairo OpenGL backend, this library would keep the data on the GPU as long as it's used, and only control points of the curves would be submitted to the GPU, which should give very good performance.
Looks interesting. Looking forward for your project.
One question: What openGL version will you target?
participants (9)
-
Bryce Harrington -
Johan Engelen -
Josh Andler -
Krzysztof Kosiński -
Martin Owens -
Nathan Hurst -
Tavmjong Bah -
Ted Gould -
Vinícius dos Santos Oliveira