GTL - geometric template library - determining interest
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
Suto, Gyuszi wrote:
I am trying to determine interest to submit GTL to boost.
I'm definitely interested. We are currently looking for exactly this kind of library for our landscape visualization system for GIS operations (polygon clipping etc.). Since this currently academic project will be used in a commercial context, the Boost license would be a very big plus. Btw, does GTL have any kind of support for rasterization? Malte
Malte Clasen wrote:
Btw, does GTL have any kind of support for rasterization?
Malte
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
You can get your resulting polygons or polygon sets as a collection of rectangles oriented H or V. Mapping the rectangles to a raster grid is a simple step from there. Gyuszi
I am trying to determine interest to submit GTL to boost.
Looks good. Please show us the code! Currently, I do this sort of thing with my own fixed-point class (which has been discussed here before) and some not-good-enough-for-Boost-yet 2D container types. Do you have containers with e.g. rectangular-range iterators? Regards, Phil.
Phil Endecott wrote:
I am trying to determine interest to submit GTL to boost.
Looks good. Please show us the code! Currently, I do this sort of thing with my own fixed-point class (which has been discussed here before) and some not-good-enough-for-Boost-yet 2D container types. Do you have containers with e.g. rectangular-range iterators?
I cannot release code or full documentation (yet). We tried to write the fastest polygon booleans. We avoided any lazy iterators because they slowed us down. You can get all the resulting rectangles in a collection then iterate thru them. Gyuszi
Hi,
GTL is a geometric library that implements basic rectilinear, fixed point 1D, 2D and 3D types.
I think most readers here don't know what "rectilinear" means. Most likely, they will simply ignore the qualifier even though is central to the nature of this library. I also think most readers don't what "isotropic API", "directional types", etc means. In the presentation below you assume the reader is familiar with this type of geometry, its core concepts and operations. But I'm sure most people here don't, even worse, know it *differently* and will misunderstand the library.. So, what are the core concepts of this type of geometry?
* parametrized fixed-precision cartesian coordinates
What is parametrized exactly?
* massive capacity
What does this mean?
* isotropic API
And this? I could extrapolate what you mean by "isotropic API" from the examples below, but then I'm curious why you call it isotropic?
Implemented Rectilinear Types ========================================= 1D Types: Interval
Is this a geometric primitive or a numerical primitive, or none? (see Boost.Interval)
2D Types: Point, Segment, Rectangle, Polygon, PolygonSet 3D Types: Point3D, Segment3D, LayeredRectangle, RectangularPrism
Polygons ========
"Polygons" here mean the layout of primitive rectangles right?
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)
Here is an important question: What algorithm do you use? Isn't it dependent on the central fact that polygons are the overlay of rectangles? Doesn't the algorithm decompose a poygon in rectangular regions? If yes, then is important to state that this library probably won't scale nicely to general polygons.
2. runtime (all n*log(n) or better) - it is at par or better than other implementations that we're aware of
How do you handle the robustness of clipping? Is it based on the fixed-point arithmetic alone or there is something else?
5. providing polygon set type that's complete
complete means that operations are regularized? (that is that you never returned an "invalid" polygon having a region with no interior, like an antenna)
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
What is a directional type and what those constants mean?
A set of operations on these types like: forward(), backward(), toward(), left(), turn(), perpendicular(), etc.
Which do what?
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.
My un-informed (so far) opinion is that this interface looks a bit bloated and that it can probably be factored out better.
Have you considered separatring vectors from points? (and categorizing vectors as normals, directions, etc) Best -- Fernando Cacciola SciSoft http://fcacciola.50webs.com
Fernando Cacciola wrote:
What is parametrized exactly?
Say you have your user data class UserData{ private: int a, b, c; int x, y, z; float f, g, h; }; and you want to interpret 4 data members as the 4 coordinates of a gtl::Rectangl. You would write a few lines of template specialization to implement 3 basic functoins: get() set() create() #include <Gtl.h> template <> class gtl::RectangleInterface<UserData> { // need to write 3 functions only !! }; .then in the user code would look like: #include <Gtl.h> typedef gtl::RectangleImpl<UserData> Rectangle; // notice the specialization of gtl to user data // from this point on you can use gtl::Rectangle with its full API Rectangle r1(10, 20, 30, 40); std::cout << r1.get(gtl::EAST) << std::endl; // prints 20 -
* massive capacity
creating polygons and polygon sets from ~10M rectangles. Doing booleans on them. Getting the results back in the form of rectangles, also in the 10M range.
What does this mean?
* isotropic API
And this?
I could extrapolate what you mean by "isotropic API" from the examples below, but then I'm curious why you call it isotropic?
I'm using the term isotropic denoting the fact that none of the function names have any X, Y, Z, horizontal, vertical, etc in them. If that would be the case, then once you are using a function p.getHighXValues() for example, then there is some piece of code that does similar things on Y and Z values. This may be trivially bad for the boost audience, but the fact is that most of the geometric code I've seen out there was written like that. It was bad because of code duplication, code size, readability, inflexibility, lots of if and switch statements all over. In GTL, if a functoin needs to operate on a direction or orientation, it has a function argument for it. The resulting code is much smaller (sometimes 4x smaller) more readable, more flexible. Let's consider the example below. // Unisotropic example // counting the concave corners of a rectilinear // polygon. a,, b, c are 3 adjacent vertices // iterating clockwise around the polygon int concave = 0; ... // trying to find the following pattern: // // c ------ b // | // | // a if( ( a.x == b.x && a.y < b.y && b.y == c.y && b.x < c.x ) || // trying to find the following pattern: // // b ---- a // | // | // c ( a.y == b.y && a.x < b.x && b.x == c.x && b.y > c.y ) || // and so on for the other two patterns: // // a // | // | // b -----c // // and // // c // | // | // a ------b This code was present in several code instances that I was exposed to. Translating this to gtl isotropic code: concave += (a.towards(b).left() == b.towards(c)); Notice that it's just one line. And more flexible too, if you want to count the covex instead of concave corners, just change left to right: convex += (a.towards(b).right() == b.towards(c)); It also has the advantage of being immune to collinear vertices (assume that the polygon in question does allow them), whereas the non-isotropic code may have to account for that specifically. Judging on the developers I'm familiar with, once you start programming based on isotropy, you'll never write the old-style code again. There could well be other, more advanced techniques out there, but so far this served us very well Gyuszi
Hello Gyuszi,
Fernando Cacciola wrote:
What is parametrized exactly?
Say you have your user data class UserData{ private: int a, b, c; int x, y, z; float f, g, h; };
OK.
* massive capacity
creating polygons and polygon sets from ~10M rectangles. Doing booleans on them. Getting the results back in the form of rectangles, also in the 10M range.
But how is this a property of the library? Are the data structures and algorithms specifically optimized for storage and/or speed? If yes, it might be better to state this fact instead, and outline how.
What does this mean?
* isotropic API
And this?
I could extrapolate what you mean by "isotropic API" from the examples below, but then I'm curious why you call it isotropic?
I'm using the term isotropic denoting the fact that none of the function names have any X, Y, Z, horizontal, vertical, etc in them. If that would be the case, then once you are using a function p.getHighXValues() for example, then there is some piece of code that does similar things on Y and Z values.
You said "none" of the functions. Is that so? What if I really need to so something on the X or Y etc?
Let's consider the example below.
[really bad code ommitted]
Translating this to gtl isotropic code:
concave += (a.towards(b).left() == b.towards(c));
OK. So you are calling isotropic what I know as "coordinate free operations". Notice that I could implement the above as: concave += ( cross_product((b-a),(c-a)) < 0 ) ; using basic algebraic stuff (and this would work for non-rectilinear edges as well). So as I said in a previous post I fear this API can be somewhat bloated, but anyway, the "idea" of a coordinate free/isotropic approach is certianly sound (most geometry libraries I know follow it, in fact).
Notice that it's just one line. And more flexible too, if you want to count the covex instead of concave corners, just change left to right:
convex += (a.towards(b).right() == b.towards(c));
Right. But using basic algebra that becomes: convex += ( cross_product((b-a),(c-a)) > 0 ) ; Notice that the lhs expression is the exact same code. In your case one needs to change ".left()" for ".right()". That's is what I mean with interface bloat. But let's not digress until we can see some code and docs.
It also has the advantage of being immune to collinear vertices (assume that the polygon in question does allow them), whereas the non-isotropic code may have to account for that specifically.
How so exactly? Can you show how this API would handle the case if a==b or b==c and also if a==b==c?
Judging on the developers I'm familiar with, once you start programming based on isotropy, you'll never write the old-style code again.
Right. I think you should know that this is the approached followed by most modern geometry libraries. But granted, end-users tend to write the sort of code you shown above, so a good geometry library is a must.
There could well be other, more advanced techniques out there, but so far this served us very well
There are even higher level approaches on top of coordinate-free operations that are important in a geometry library. But we can discuss that after I've seen the code and dosc. Best -- Fernando Cacciola SciSoft http://fcacciola.50webs.com
On Sun, 7 Oct 2007, Fernando Cacciola wrote: [...]
Let's consider the example below.
[really bad code ommitted]
Translating this to gtl isotropic code:
concave += (a.towards(b).left() == b.towards(c));
OK. So you are calling isotropic what I know as "coordinate free operations".
Notice that I could implement the above as:
concave += ( cross_product((b-a),(c-a)) < 0 ) ;
using basic algebraic stuff (and this would work for non-rectilinear edges as well). [...]
convex += (a.towards(b).right() == b.towards(c));
Right. But using basic algebra that becomes:
convex += ( cross_product((b-a),(c-a)) > 0 ) ; [...]
Just one thing: in linear algebra, cross product returns a vector. Then how can you compare that result with a scalar? -- Francois Duranleau
François Duranleau wrote:
On Sun, 7 Oct 2007, Fernando Cacciola wrote:
[...]
Let's consider the example below.
[really bad code ommitted]
Translating this to gtl isotropic code:
concave += (a.towards(b).left() == b.towards(c));
OK. So you are calling isotropic what I know as "coordinate free operations".
Notice that I could implement the above as:
concave += ( cross_product((b-a),(c-a)) < 0 ) ;
using basic algebraic stuff (and this would work for non-rectilinear edges as well). [...]
convex += (a.towards(b).right() == b.towards(c));
Right. But using basic algebra that becomes:
convex += ( cross_product((b-a),(c-a)) > 0 ) ; [...]
Just one thing: in linear algebra, cross product returns a vector. Then how can you compare that result with a scalar?
OK, OK, you are right. This is such an old trick that I often forget it is formally incorrect ;) (it even appears in the CGA FAQ) The cross product, as you now, is defined in 3D, not in 2D, but these are 2D vectors. Since the cross product doesn't actually exist at all in 2D, there's an old-school trick: 1.pretend these vectors are in 3D (adding z=0) 2.take their cross product. The result is a vector of the form (0,0,z) 3.return z alone (a scalar) Many geometry toolboxes define such a 2D pseudo-cross-product that returns the z component of the actual product. But this is formally wrong... old habits die hard I guess. But we don't want to perpetuate this blasfemy here in boost :) So, the correct "orientation test" is to use the determinant of a matrix formed with those two vectors (which works in 3D too). So I shoud have wrote that as: ( determinant((b-a),(c-a)) > 0 ) Best Fernando Cacciola
Fernando Cacciola wrote:
But using basic algebra that becomes:
convex += ( cross_product((b-a),(c-a)) > 0 ) ; [...]
But we don't want to perpetuate this blasfemy here in boost :) So, the correct "orientation test" is to use the determinant of a matrix formed with those two vectors (which works in 3D too). So I shoud have wrote that as:
( determinant((b-a),(c-a)) > 0 )
The following line (admittedly is rectinilear specific) concave += (a.towards(b).left() == b.towards(c)); translates into just a handful of assembly instructions. We did use cross product in the past but it couldn't compete on runtime Gyuszi
participants (6)
-
Fernando Cacciola -
François Duranleau -
Malte Clasen -
Michael Marcin -
Phil Endecott -
Suto, Gyuszi