BOOLOPS Proposal
Boolean Operations
The project I would like to undertake is to write code to perform robust and fast intersections of two dimensional shapes.
For the past year or so I have worked on the lib2geom project, a library for inkscape, among other programs. I plan to implement the shape intersection code as functionality within lib2geom, and use much of that library's sophisticated infrastructure for representing and manipulating curves. Among other things, I implemented the class for piecewise composition in lib2geom.
The current license for lib2geom is GPL/LGPL/MPL tri-license, chosen largely because full-featured SVG implementations need the kind of vector operations that lib2geom provides, and it is hoped that the Mozilla SVG implementation will adopt the library. However, if this license proves less than ideal, the lib2geom team is willing to consider other unrestrictive licenses. Other potential clients include FontForge, the server side of fontly.com (a web-based font editor).
My approach to completing this project will be to deal with it in logical chunks:
- Intersection algorithms on closed, simple paths.
- An intermediary data structure with topological invariants suitable for the boolean operations. The downside of this is that many applications will require conversions from discontinuous or self-intersecting paths.
- Boolean operations implemented upon these intersection algorithms and data structures.
Each of these items will first be implemented as simply and clearly as possible, to be later optimized and improved. Hopefully the design will allow for multiple implementations of each component, such that they may be used in different combinations. Also, if I only succeed during the project in implementing some of the goals, the work will still be useful, and should serve as a good start for the more ambitious goal of fully general and numerically robust shape intersection.
This underlying task is quite challenging, and I only have about 8 weeks - the code will not be able to deal with every degenerate case. However, by the end of this time I will have rudimentary boolean operations upon paths, written with clear, logical code, allowing for future experimentation, extension, and refinement.