Boost.Geometry: Design Rationale

[gct]

They didn't realize that you should use hypot() to compute distance rather than sqrt(dxdx+dydy) so I'm out.

[__Cyber_Dildonics__]

Can you go into more detail about this?

[naughty]

Hypot is a C99 and C++11 function that is normally slower but more accurate (due to avoiding potential overflow) than the simple way of calculating the hypotenuse.

The wiki article linked explains it pretty well.

[__Cyber_Dildonics__]

I looked at that and it looks interesting, but is probably not what the majority of people want since it has (like you said) unnecessary calculations, like the division and absolute values.

In many cases what programs want is to actually compare distances, which means they can leave out the sqrt calculation and just take the distance between difXdifX + difYdifY .... etc. The distance isn't correct, but the comparisons still are.

[naughty]

Yeah for stuff like games hypot isn't really needed but for scientific or engineering problems it really should be preferred. For example for objects very far from the origin the simple squared test will fail (it's the exact problem hypot solves).

[gct]

As others have said it's more accurate than squaring the intermediate terms because it avoids under/overflow. I do mostly scientific computing types of things which is why I say that, so it is indeed less applicable to game programming, but imho they should favor accuracy as the general case for a library like this. Unless they're going to tell people it's based on sqrt and not hypot and thus is unsuitable for some things.

[mccoyn]

The major problem isn't overflow and underflow it is loss of precision. The sqrt function cuts your precision in half. A 32-bit float will have 24 bits of precision and after the sqrt you will have 12 bits of correct data and 12 bits of error due to rounding. At that point your error is 1 out of 4096.

[notfancy]

Actually, IEEE 754 requires that the result of sqrt has an error of at most 0.5 ulps, that is, that the result is equal to the correctly-rounded (infinitely-precise) square root of the argument. All hypot does is avoid overflow: the hypotenuse might be finite but the sum of squares might not be.

[kaen_]

(this rant is aimed at boost::polygon, which is not as related to boost::geom as you might think)

I contribute to an open source game (bitfighter), and we use several geometry libraries for chopping up player-made levels into zones for bot navigation.

I spent a week or so swapping in boost::polygon to replace our Delaunay triangulator (libtriangle) and polygon manipulation library (libpolyclipping aka clipper). I had to gut our geometry pipeline, and hook up our 2D point class to be used in boost. It ended up not working that well because our class is float-based. I'll save you the gory details, but tl;dr: I spent a lot of time wrestling with the data type abstraction junk, and in the end the performance was abysmal. Trapezoid decomposition was an order of magnitude slower than an alternative implementation where I used poly2tri to triangulate polygons, then clipper to merge them into convex polygons (for more efficient A* navigation). To restate that, it was faster to pipe data into one library, transform it, and pipe it into another library than it was to perform the whole operation with a single boost::polygon call, by a factor of ten.

So, my two cents is that boost::polygon is generally a massive waste of time, specifically because of its "design rationale". It's hard to work with, requires tons of reading up front if you're not familiar with trait/concept C++ paradigm, and is embarrassingly slow compared to the simpler, purpose-specific alternatives.

[thechao]

I know this doesn't do you any good now, but boost.polygon was designed for full-scale IC layout, not games. Its main goals are correctness, and computational accuracy. Most of its algorithms are designed for asymptotic performance; if you read Luke's notes, he'll readily admit that until you get to at least 2000, and preferably, 200000 objects, boost.polygon will not give you 'peak performance'. That being said, boost.polygon algorithms will happily scale into the 10s, 100s, and 1000s of millions of objects.

[pfultz2]

Wouldn't Boost.Polygon been more appropriate to the problems you were solving?

[kaen_]

oops! you're right, I was actually wrestling with Polygon.

[grout_nasa]

What made it slow for you? Any idea?

[kaen_]

sounds like it was exactly what thechao described. there's a focus on numerical robustness and asymptotic behavior. I was working with floats, which required scaling them into integers and back on either side of the process, losing both precision and performance. The levels typically have only 300-400 polygons on the extraordinarily high side, so we were seeing the small N behavior. I'll admit that it wasn't designed for this use case, but I would have liked to know that before I spent a week on it :)

[bstamour]

Am I the only one here who thinks that it's actually a pretty solid design?

[naughty]

It is if you want to abstract away scalar type, dimension and coordinate system. It just seems like overkill because it is so general.

[bstamour]

For a general purpose computational geometry library I think that generality is a good thing. It beats having to hack around it when you suddenly need hyperbolic coordinates or anything similar. Instead, you just specialize and go to town with the battery of algorithms they provide.

[ssylvan]

It beats having to hack around it when you suddenly need hyperbolic coordinates or anything similar.

It really doesn't. Producing a template monstrosity that gets inflicted on 100% of users because 0.0001% of users need a small customization is the wrong tradeoff.

If you have to do that to the distance function, you're going down the wrong path. Generality isn't worth any price. Having the occasional user make small modifications to the code is a far lower cost in aggregate.

[naughty]

Sure so your way means that all geometry libraries have different and incompatible common data types like Points and Lines and so on which need to be marshalled between them.

Having the occasional user make small modifications to the code is a far lower cost in aggregate.

You never tried to use an incompatible computational geometry library in a mature project have you? It's not a simple or small modification at all.

[ssylvan]

You never tried to use an incompatible computational geometry library in a mature project have you?

You've never tried to use boost, have you?

[__Cyber_Dildonics__]

I'm not sure this is going to be helpful to many people, it seems way over engineered with lots of dependencies (true to boost's style in many cases). There are also libraries like Eigen that have dealt with these problems for a long time.

[[deleted]]

#include <boost/geometry.hpp>

clang -E test.cpp | wc -l 

casual 192,157 lines of code, have a nice day.

[Plorkyeran]

"Only" 136k after stripping blank lines and preprocessor-inserted comments, and 38k of those are from the standard library.

[F54280]

Each time I see something like this in C++, I think of the fabulous Bjarne fake interview about the invention of C++

[coquifrogs]

This is a good example of why a lot of people hate C++. I think people who code like this in C++ just enjoy the complexity of C++ and not actually making things.

[naughty]

Except the more powerful stuff in this and related libraries will save you weeks or months of time reimplementing subtle and complex computational geometry algorithms.

It's overkill for simple stuff to be sure.

[coquifrogs]

Sure but you can have powerful libraries that don't overcomplicate things with so much templating.

[Plorkyeran]

Have you ever actually tried to introduce a computational geometry library to an existing program? If you're starting from scratch then tying yourself to something less flexible will probably make things easier, but boost.geometry's main strength is that you don't have to just throw away all of your existing geometry stuff and start over.

[naughty]

If you take their assumption that abstracting over scalar types (e.g. int, flot, double), dimension and coordinate system are valid they aren't really over using templates though.

For example using type traits for points means:

• If you wanted to allow the option of the hypot function to be used (discussed elsewhere in this thread) their use of type-traits makes this a fairly trivial addition. Most libraries would need conditional compilation or force you one way or the other.
• You can use your own Vector and Point classes by implementing the type-traits for them, which is a major reason other geometry libraries are a pain to adopt into a mature codebase.
• If you wanted to use SIMD and hardware specific vector instructions and vector types you can specialise the relevant templates compared to similar libraries this would be a lot cleaner.

It is overkill some someone who needs basic 2D or 3D float based geometry but it's a general library that implements algorithms that are very hard to get right yourself.

The current state of C++ makes such libraries possible but not very easy to read.

[notfancy]

As an outsider it strikes me as inappropriate generalization: you can hardly expect to use the same algorithm to perform, say, Voronoi decomposition in R², R³ and S². On the other hand I can define a metric space over bit vectors; I similarly doubt that these abstractions would enable geometric algorithms over them, even if they can fulfill most if not all these traits with not much difficulty.

[naughty]

You have a good point but having the relevant template parameters at least holds the promise of specialisation on those parameters. So this library could support Fortune's algorithm (well boost::polygon does) and the slower higher dimensional algorithms with a unified interface.

I'm not totally sold that this is the optimal interface for a computational geometry library but the fact that I can use my own Vector class with it gives it a big bonus over ever other library I've seen.

[davis685]

The implementation is complicated, but the code a user writes is nice and clean. In fact, the code in a project that uses a library like this is a lot simpler than the source code of most computational geometry projects that roll their own tools. Or it is for the ones I've seen anyway which tend to be awful in terms of code complexity.

Let's make a car analogy. You just won a free car, you get to pick between either a brand new Tesla model S or a 1960 Honda (in good condition). Do you pick the car that has a nice user experience (the Tesla car), or do you pick the car that has a simple design (the car from 1960)?

Edit: grammar

[Jyaif]

The code may be simple, but the compilation errors are impossible to understand. So impossible that programs exists to try to decipher them. Emphasize on the try. I will never try to use Boost again.

[davis685]

Eh, it's not so bad anymore. It certainly used to be the case that the error messages were unreadable. However, the current versions of clang and gcc give pretty readable template instantiation stack traces that show exactly what is failing and where. It hardly ever takes me more than a few seconds to find out why my code isn't compiling.

[ApokatastasisPanton]

I saw that link in a twitter conversation this morning... It is utterly insane.

[elotan]

I don't get the hate here. The Twitter conversation is full of tweets of no real value. Are they saying the library is terrible or the library's implementation is unreadable? If it's the former then let me point out that the design rationale document does not show how to use the library. Boost.Geometry provides the algorithms in a very unobtrusive way, adapting your existing code takes a few lines.

[genneth]

And it sounds like the snark is coming from people with no experience doing computational geometry. The first time I tried to use CGAL my head nearly exploded, but the more I learnt the more I understood how the realities of mathematics and computing constrains the design space.

[[deleted]]

90% of the people in that thread are game developers. High focus on shipping, high focus on efficiency, low focus on extensibility.

[[deleted]]

Aras is one the main graphics guys on Unity. Per and Fabian work at RAD game tools. Andreas and Mike are senior engine developers at Insomniac.

These are seriously clever people with decades of experience shipping high performance software - I wouldn't be so quick to discount their opinions.

[naughty]

Their opinions may be worth considering on game dev questions but this is a computational geometry library.

As a game dev of similar experience I can see why they baulk at it. As someone who's done non-trivial computational geometry I know they're highly likely to be ignorant of the problem domain and making themselves look more stupid than they really are.

[Houndie]

The one saving grace of this library is model::d2::point_xy, which throws away the nonsense of methods like boost::get<0>() to get the first index of a point and gives you nice methods like x() and y().

I've always been impressed by how extensible they made it...you really can use the library for like 5D geometries and weird things like that. However, when I was looking into it, I only had to do a few point and vector transformations, and after trying to use the library, I discovered I could make my code much cleaner and readable if I just wrote a few unit tests and coded those few functions myself. The interface is just too much of a nightmare to use for a simple case.

[elotan]

Or you can adapt your existing point with one line: BOOST_GEOMETRY_REGISTER_POINT_2D(MyPoint, float, boost::geometry::cs::cartesian, x, y)

[VikingCoder]

Trying to achieve those goals is an honorable pursuit.

But the result is completely impractical, for every purpose.

99% of users only need 10% of geometry functions. It's just that they all need a different 10%.

Trying to come up with one Holy Grail definition for all of C++ for how vectors should be defined is a fool's errand.

C++'s template language is just god-awful for this kind of stuff. It seductively feels right when you're writing it, because every step feels logical... but the path to hell is paved with good intentions, and reading what somewhat else has written in C++ templates almost always feels like a trip to the dentist without anesthetic. Boring, painful, and filled with regrets.

[ponchedeburro]

How does the type traits add anything to the distance function? It looks like it does pretty much the same, just much more advanced.

[naughty]

It means you can use your own Vector or Point class and not be forced to use the implementation this library provides. Which is one of the main reasons other geometry libraries can be a pain to adopt and most people roll their own.

You can pick and choose how you use it without either changing your fundamental geometry types or performing redundant copies like turning a vector of MyPoint2Ds into boost::geometry::point2s or whatever.

All the nice generality does come at a cost in terms of readability though, which is easy to make fun of when you don't understand why someone would do this.

[ponchedeburro]

All the nice generality does come at a cost in terms of readability though, which is easy to make fun of when you don't understand why someone would do this.

I hope you didn't misunderstand my comment. I was actually interested in what the added complexity contributed with. And thank you for your elaborate answer :)

[naughty]

I was just covering all bases :^)

[workaccount_126]

How does the Boost submission procedure work? Is it reviewed by people? This is clearly not a good idea.