Hi all! After some talk with Nathan Hurst I decided to apply for GSoC also this year. I would like to go on with the development of lib2geom that as I can see is now almost completely integrated into Inkscape. So, before submitting my project proposal to google I would like to know your opinions!
Kind Regards, Marco
=======================PROPOSAL START============================
Name: Marco Cecchetti
Project: lib2geom development
Abstract
Lib2geom has become the core geometric library of Inkscape and it is also an open source project on its own. My project aims to expand the library and give evidence of its skills through the implementation of ad hoc "toys": little interactive applications showing off the power of lib2geom. Moreover many of these toys could be suitable directly for live path effects.
Goals
(1) Complete the work on bezier clipping routines making them more robust, and implement more specialized intersection routines for the various curve types; (2) Adding support for more basic geometric shapes (triangle, regular polygon, ...) so making easier the development of educational and technical geometric tools. (3) Implementation of a new curve type (clothoid) to let 2geom supporting spiro tools into Inkscape; a clothoid toy showing off the feature of the implemented curve will be provided, too. (4) In case I have some time left after fulfilling the other goals I would like to implement a parallel version of some 2geom routine using a multi-thread library, and explore the possibility of exploiting vectorialized support (e.g. SSE2) provided by modern cpus.
Details
(1) Towards the end of my last year project I start developing routines that compute the intersection points and the collinear normals of two Bezier curves. Both these routines are based on the Bezier clipping technique as it is explained on Sederberg's book [1]. Though at 99% these routines work correctly there are still cases where they show some spurious behaviour. As they are really useful tools I think that spending some time in order to make them more roubust it is a worthwhile task. Moreover I would like to investigate the utility of implement specialized intersection routines for various curve tipes (bezier-conics), (conics-conics) (conics-line) and so on. This would save the time needed to convert them to symmetric power basis or to bernstein basis before computing the intersection and would make also the computation more robust by removing the possible approximation errors introduced by the conversion stage.
(2) In order to simplify the implementation of technical drawing tools or the development of a geometric educational version of inkscape, I think that it is useful to have direct support in lib2geom for simple geometric objects and the availability of geometric construction methods. In my last year project I implemented several tools, such as (infinite) line, ray, circle, ellipse, arcs and I provided routines for making up parallel line, perpendicular line, angle bisector, circle by 3 points, ellipse by 5 points. Now I want to go on adding new geometric objects such as triangle, regular polygon, and the left conic sections, moreover I want to implement other construction methods such as circle by 2 points and tangent to a line, inscribed and circumscribed circle of a triangle and of a regular polygon, conic section by 5 points and so on.
(3) A Clothoid, also known as Euler's spiral, is characterized by the property that its curvature varies linearly with the arc length. Because of this important property they are useful in the route design of highways and railways to achieve smooth transitions between lines. For the same reason they are also appreciated in the design of font types. I'll provide the Clothoid class with a complete implementation of all methods inherited by the abstract Curve class such as bounds computation, evaluation for a given parameter value, conversion to and from a s-power basis path, and so on. The Clothoid-Toy will provide the ability of interactively play with a clothoid curve by modifying the initial and the final clothoid arc points, set its length, watch the projection of an external point on the curve, and all other abilities that the Clothoid class will own.
(4) Several 2geom routines such as the bezier clipping algorithm and the curve-curve distance computation will benefit from a parallel implementation. The trick is in partitioning the work in several tasks that can be executed by different threads managed by a task scheduler. All that can be achieved using a multi-thread library like the Intel Threading Building Blocks (released under the GPL license) or through the Boost.ThreadPool library still in active developement. Likewise exploiting a vectorialized instruction set such as SSE2 will allow us to parallelize the computation of large amount of data by producing more compact assembly code, that is working on "packed" data we save a large number of clock cycles.
Benefits to Inkscape
My first goal is to simplify the development of technical drawing tools into Inkscape and the development of an educational version of Inkscape focused on geometry learning and here I think to programs like Cabri [2]. All the first 3 points of my project go in this direction. The geometric construction methods I want to implement will make possible to deploy new technical live path effects. Expecially the fulfil of the third point will simplify the design of a complete spiro tool into Inkscape (at present such functionality is supported by a live effect). Having a complete and robust api for curve intersections will be useful to simplify the implementation of cut path tools, and boolean shape operations. Finally, the fourth point will put the basis for exploiting the power of modern cpu architetures.
About me
I am a student in mathematics (University of Pisa, Italy) I am always been keen on computer graphics and I am interested in computational geometry. My main programming language is C++, but in the past I also programmed in pascal, fortran 90, assembler, java, javascript, actionscript, bash script. Moreover I am knowgeable about several Boost libraries, XML APIs and the Scalar Vector Graphics Markup Language.
Contributions to open source projects
My main contribution in the open source field is the Google Summer of Code Project I applied for the last year. It was about 2geom development. In the project time-frame I achieved the following goals: - Implementation of a new curve type that fulfils the traits of an SVG Elliptical Arc and of an "Elliptic Toy" for playing with this curve type. - Some basic GSL library wrapping classes such as Vector, VectorView, Matrix, MatrixView and a fitting tool. - Ellipse and Circle curves with the ability to be created or by the algebraic implicit equation, or by providing a sufficient number of points lying on the curve. - Nearest point routines for all curve types, computing the point on the curve nearest to a given external point. - A curve-curve distance routine. - A Polynomial class for symbolic computation. - Implicitization method for polynomial curve intersection, and Bezier clipping method for Bezier curve intersection and for collinear normal matching. - Several simple geometric objects and construction methods that I have already listed above.
I'm developing an extension of Boost.Function [3] in order to implement a model of function concept supporting multi-signature and so overloading. [4]
I contributed in the development of a proof of concept svg import filter for Open Office. This import filter has been developed mainly by Fridrich Strba at Novell, my contribute consists in having added svg text element support to the import filter. [5]
[1] Sederberg, Computer Aided Geometric Design [2] http://www.cabri.com/cabri-2-plus.html [3] http://www.boost.org/doc/html/function.html [4] source code: https://svn.boost.org/svn/boost/sandbox/overload/trunk documentation: http://docs.google.com/View?docid=dfxvjncs_1x6456m [5] source code: http://tinyurl.com/2es9cu
=======================PROPOSAL END==============================