Thomas Klimpel wrote:
- The references to the paper and the presentation are very welcome, and really add value to the documentation. But what is meant by "Performance of GTL could be improved by up to 10X with further work on the arbitrary-angle Booleans"???
If you look at slide 15 of the presentation "Manhattan Benchmarking" there is greater than 10X performance delta between gtl and gtl45. I consider the gtl45 algorithm to be something of a lower bound on performance that I could get in the arbitray angle case. Based upon the observation that 90% of runtime is spent in the sub-optimal line segment intersection phase, which could be done at a constant factor additional cost if incorporated into the sweep-line that performs the boolean and the potential to speed that sweep-line up for the 2-input case by applying different data structures I think that given several weeks of effort the algorithm could be sped up ~10X.
I also notice that the library is not intended to directly handle real GDSII or OASIS layout data, which is typically stored in hierarchical form. (This hierarchical form means more or less that some basis shapes are directly defined as polygons, and the more complex shapes are defined by reference to basis shapes or already defined more complex shapes.)
We have propriatary OASIS and GDSII reader/writers. GDSII is simple to parse, but OASIS is quite involved and requires code comparable in scale to the Boost.Polygon library. Reading these data formats imply a hierarchical geometry data model that they are read into. Implementing such and the basic capabilities one would expect of it is also involved. A system with GDSII/OASIS reading and writing, a hierarchical data model with query capabilities plus Boost.Polygon geometry library could easily run 250 KLOC of C++. If you investigate the OpenAccess http://www.si2.org/openeda.si2.org/ data model you will find that Cadence has already released its hierarchical data model and file format reader/writers as open source, and is pushing a million lines. Notably absent in the OpenAccess system are the capabilities present in the Boost.Polygon library.
So I finally have to thank Lucanus Simonson and it's employer for writing this excellent library and proposing it as a boost library.
Thank you Thomas for all your work reviewing it, Luke