[boost] GTL - geometric template library - determining interest

From: Suto, Gyuszi (gyuszi.suto_at_[hidden])
Date: 2007-09-28 20:05:11

> Hello,
> 
> I am trying to determine interest to submit GTL to boost.
> 
> History/Background
> ==================
> GTL is a geometric library that implements basic rectilinear, fixed
> point 1D, 2D and 3D types. It was developed over the past decade
> inside Intel's own EDA CAD department mainly to support advanced
> physical design tools that create/check/manipulate the massive layout
> that goes into our microprocessors. GTL comes from a codestream that
> successfully weathered through several major microprocessor tapeouts.
> The management agreed to pursue the open-sourcing of GTL via boost
> (with the boost license) - with all the obvious benefits of doing so.
> 
Comparison to other geometric libraries
=============================
We are aware of the various other libraries available. What GTL brings
to the table:
* parametrized fixed-precision cartesian coordinates 
* industrial strength code base
* directly usable on any user type via template traits - based on C++
concepts
* massive capacity
* bone-crushing speed
* isotropic API
* ease of use

> Implemented Rectilinear Types
> =========================================
> 1D Types: Interval
> 2D Types: Point, Segment, Rectangle, Polygon, PolygonSet
> 3D Types: Point3D, Segment3D, LayeredRectangle, RectangularPrism
> 
Polygons
========
This is by far the most algorithmically advanced type and functionality
that we have.
1. full set of boolean operations on polygon sets (or, and, subtract,
xor, etc)
2. runtime (all n*log(n) or better) - it is at par or better than other
implementations that we're aware of 
3. ease of use - simple, intuitive API functions
4. no memory management required by user
5. providing polygon set type that's complete
6. isotropic API

// example 1
// construct default empty polygons sets that will be rectangularized
// in the given orientation (on demand)
gtl::PolygonSet a(VERTICAL), b(HORIZONTAL), c(VERTICAL);
a += gtl::Rectangle(4, 5, 60, 70); // add a rectangle to polygon set a
a += gtl::Rectangle(gtl::Interval(20, 30), gtl::Interval(40, 100)); //
construct a rectangle from 2 intervals, add it to a
// .. similar additions to b and c
// intersect a with b (with a boolean and) - subtract from it a
rectangle, 
// bloat the north edges of the result by 55 units
c += ((a * b) - gtl::Rectangle(10, 10, 2000, 3000)).bloat(NORTH, 55);

std::vector<gtl::Rectangle> v;
c.get(v); // populate v with the vertical rectangles that make up c

> Isotropy
> ========
> A variety of directional types in 1D, 2D, 3D with states like: LOW,
> HIGH, NORTH, HORIZONTAL, UP, etc
> A set of operations on these types like: forward(), backward(),
> toward(), left(), turn(), perpendicular(), etc.
> 
> All API functions are isotropic, i.e. they take arguments of
> directions/orientations. None of the function names contain words like
> X, Y, Up, deltaX, horizontal, etc. With isotropy, you can do elegant
> things like:
> 
> // example 2
> gtl::Rectangle a, b;
> 
> // bloat rectangle of a toward rectangle b by b's half delta in that
> orientation
> // do nothing if no trivial direction from a to b exists
> a.bloatInDirection(a.toward(b), b.delta(a.toward(b))/2); 
> 
> Writing this example in a non-isotropic fashion requires much more
> lines of code, lots of if statements, four to eight different
> scenarios, etc. Much more code, much less readable, not flexible at
> all.
> 
> Functionality
> =============
> GTL has pretty much all the functionality that one would expect from
> these types. You can get/set components, you can do booleans (ands,
> ors) subtractions, bloats, shrinks. You can construct a rectangle out
> of 2 points, 2 intervals, 4 coordinates, etc. You can  construct a
> polygon set from n rectangles, from a polgyon or a polygon set. You
> can get the polygon as a set of rectangles (rectangularized
> horizontally or vertically), etc.
> 
> // example 3
> gtl::Rectangle a;
> gtl::Segment s = a.get(EAST); // returns the right (vertical) edge of
> the rectangle as a 2D segment.
> // get the north edge of rectangle a as a segment
> // get generalized intersection with segment s - as a rectangle
> // bloat the rectangle's EAST side by 5
> // get the center of that rectangle as a point
> a.get(NORTH).getGeneralizedIntersection(s).bloat(EAST, 5).getCenter();
> 
> 
> Data decoupling via template specialization 
> ===========================================
> GTL can operate on any user data without the need for copying. User
> will need to write a tiny, template specialization interface to his
> data, that makes GTL interpret user data as the GTL type of interest.
> This makes the use of GTL in existing applications trivial.
> 
> // example 4
> class UserData{
>   int a, b, c;
>   int x, y, z;
> };
>   
> // if user wants gtl to interpret a, c, x, z 
> // as the coordinates of a rectangle, he will write  
> #include <Gtl.h>
> template <>
> class gtl::RectangleInterface<UserData> {
> // need to write 3 functions only - get(), set(), create()
> };
> 
> typedef gtl::RectangleImpl<UserData> Rectangle;
> Rectangle r1(10, 20, 30, 40);
> std::cout << r1.get(gtl::SOUTH) << std::endl; // prints 20 - y low
> coordinate
> 
> 
> David Abrahams suggested to write this description as a brief email. I
> just realized that I'm past 2 pages already. There's much more to say
> about GTL. Will do that when/if appropriate. We're eager to get
> feedback from you.
> thanks,
> Gyuszi Suto
> Intel, Hillsboro, Oregon
>