Why CGAL?

The X-Plane scenery tools use CGAL as a base library for most geometry calculations.  This post attempts to explain the situation.

For The Impatient

CGAL uses precise numeric types - replacements for normal floating point math that don't have rounding errors. You can treat the data types that come from CGAL as "opaque" - they aren't really opaque, but their implementation is complex enough that you're better off not looking inside it.  The main things to know:

• Point_2 has members .x() and .y() that return the X and Y coordinates.  You need to use CGAL::to_double to convert these opaque (but precise) numeric to a double.
• Be warned: the conversion to_double is not exact!  You may get rounding errors 'just because'.
• You can't change a Point_2 (or any other CGAL geometric primitive) once it is created.  Instead you would construct a new Point_2 that is based on the original Point_2.

No Rounding Errors?  How?!?

Here's a very brief sketch of how you can have floating point that doesn't create rounding errors.  There are basically two cases we have to look at:

• For multiplication, addition and subtraction, the risk is that we might run out of mantissa and have to round.  To work around this, we build an object that can dynamically allocate memory for the mantissa.  If we run out of space, we just allocate more.
• For division, that's not good enough; 1/3 is a repeating decimal (in base 10 or binary) no matter how many digits you have.  So we store the numerator and denominator separately (both having arbitrary mantissa).

Those two techniques give us a numeric type that is capable of performing +, -, * and / without rounding errors, which is actually enough to implement most geometry algorithms.

What CGAL actually does is a lot more sophisticated and well-optimized.  Arbitrary precision math is slow (think of what happens if you replace every FPU operation with a dynamic memory operation).  CGAL can pool and reference count number "objects", use real FPU approximations (switching to slow precise math only when necessary) and has a number of wrappers that defer expensive computations, avoiding unnecessary work.

Ben, Did You Take an H-Bomb to a Knife Fight?

The big question here is perhaps: is it worth it?  CGAL is heavy-weight complex heavily templated machinery and there are penalties for using it (in terms of performance, memory footprint, ease-of-debugging, etc).  Well?

Yes - I can say unequivocally that CGAL is worth it - I know because I have tried building the scenery tools both ways, and the CGAL way is much, much easier.

There is a fundamental problem with the kinds of algorithms that the scenery tools must do (finding the union of polygons, etc.): rounding error.

An algorithm that is correct in principle according to the rules of geometry becomes wrong when coded in floating point; imagine if the mid-point between two points is not actually collinear with the original points...that kind of thing happens all the time with floating point. (Other fun phenomena include points that are not on either side of a line, nor are they on the line itself, and triangles that are neither clockwise nor counterclockwise.)

We have only two real options to deal with this:

1. Recognize when floating point has failed us and code a reasonable alternative.
2. Get better floating point.  (This is exactly what CGAL does.)

Now I like CGAL because it has algorithms right out of the box that I need, coded a lot better than I would ever do...examples:

• Fast incremental constrained Delaunay triangulation.
• Union and intersection of large numbers of polygons in optimal computation time.

But the big win of CGAL (to me) is in avoiding edge cases.  The scenery code involves a lot of "constructive" geometry - that is, code where I go in and compute some new shapes based loosely on input data in a way that "looks nice" for X-Plane.  These are big blocks of code using fundamental geometric operations...finding the intersection of lines, adding vectors to points, and testing side-of-line.

Thus option 1 (detect edge cases) isn't really viable.  It would mean asking 'how can this blow up' for pretty much every single line of code I write, and in some cases there isn't a really great answer if something goes wrong.

By using exact floating point, CGAL provides exact constructive geometry, which means that I can go write big fat piles of constructive scenery-creation code and trust that the results are what I think they should be regardless of how weird the input data is.