Re: [boost] Formal Review: Boost.Polygon starts today August 24, 2009

Subject: Re: [boost] Formal Review: Boost.Polygon starts today August 24, 2009
From: Simonson, Lucanus J (lucanus.j.simonson_at_[hidden])
Date: 2009-08-30 22:39:50

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