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.

Objective C Is Completely Freaking Weird

Well, its memory management policy is, at least.

If you are like me (a C/C++ programmer who has to write small amounts of Objective C for a certain mobile platform), this document contains pretty much all of the answers you need regarding the question "am I leaking memory?"

I'll try to limit the ranting - but there are definitely some surprising things here, particularly if you are used to a more traditional reference-counted environment.  Key points:

• Reference counting is not automatic like Java, so you absolutely can screw it up.
• You are expected to not create cyclic reference-count dependencies - see "weak vs. strong" references.
• Apple's naming conventions are very consistent, once you understand them.  This is important because the rules for memory allocation vary in a way that make the APIs more convenient, but less consistent.  (That is, sometimes objects are retained or auto-retained for you.  Lacking automatic reference counting of everything in the language, this is necessary to keep code from coming completely bloated.  But it means that you, the programmer, have to be able to look at an Obj-C method and go "I [don't] need to retain" and get the answer right 100% of the time.
• autorelease basically acts as a deferred release, similar to a deferred-destroyer idiom in C++.

Compiling a 10.4u Application with GCC 4.2 on OS X

It turns out you can build an OS X 10.4 compatible application using GCC 4.2.  The trick is: you need to install GCC 4.2 Developer Preview 1, available as a download from Apple via ADC.

The developer preview has the GCC 4.2 support files for Darwin 9 (that is, OS X 10.5) in the 10.4u SDK.

XPTools - A Thing of Beauty

I'm going to start blogging about the X-Plane Scenery Tools code tree here...the source code is too technical of a subject for my scenery blog, which is aimed at authors, not programmers. Now that the repository has been cleaned up, other programmers can start working with the code pretty easily...if they Google for answers maybe some of these posts will show up.

Let me show something that I think is really quite beautiful:

http://dev.x-plane.com/cgit/cgit.cgi/xptools.git/tree/?h=master

That is the root level of the X-Plane Scenery Tools code tree, after a week of Janos and myself bashing at it. A ton of legacy code has been ripped out, file names normalized, library systems standardized across builds, etc. If you want to work with the scenery tools code, you can now do so without going crazy from the mess of random code floating around.

(You will still go crazy trying to understand how the hell the algorithms work. :-)

Here's another thing that I think looks good:

src/MeshTool/MeshTool_Create.h

That's the cleaned version of the brains of "MeshTool".  Having it pulled out means that I can now add usability features, like more automated handling of orthophotos quickly and easily.  In fact, so could you!

One more...

src/XESCore/MapDefsCGAL.h

Okay - that one doesn't even make sense to me.  The polygon code in the scenery tools had this horrible hack called "dominance" - Andrew can testify to how ugly it was.  The polygon code uses a DCEL as its data structure for polygons.  This means that for every "edge" (line) in the map, there are actually two "half-edges", lines in opposite directions that overlap.

The problem: which one contains the road data?  The old solution was dominance - exactly one was flagged as "dominant" and held the metadata.  The dominance flag helped code figure out where to look/store the data to avoid double-storage.

What a gross hack.  Dominance has been fully removed from the code.  And the data?  It is now possibly stored on either half-edge.  This isn't just a way to remove dominance, it's necessary. A road segment is now stored on the half-edge that goes in the direction of traffic.  So I can now import one-way street grids and the directional information is preserved.

Trust No One

Here is my "new" approach to topological integration of the planar map for X-Plane scenery.  (I say new because it's new to the code, not because this is a new approach.)

Trust no one.

Basically:

• Topological data is never read from disk.  It is never imported.  We don't trust TIGER or VMAP0 to be correctly integrated.  In the case of VMAP0, I can tell you for a fact that it has errors.  (I've never caught TIGER, but the older code wasn't very sensitive.
• Instead, all data is imported and sanitized on input by CGAL.
• Once CGAL has the data, we are home free; the 3.3.1 Planar map with an exact numeric type is rock solid.

Of course, this means integrating the data every time we use it, which means my big bad new workstation isn't as big and bad as you'd think, relative to a much more expensive problem.

The advantages of this are:

• It's as good as CGAL is (and CGAL is very, very good). Bad data can't ruin the party.
• Because bad data can't ruin the party, it's safe for third party use - that is, the tools can handle third party data that hasn't been "degunked".

CGAL on OS X - Compiler Settings

I was getting random precondition failures with CGAL's arrangement_2.  (Arrangement_2 is a set of C++ templates that manage planar intersections.  It is totally wicked awesome.)

Turns out that the Mac does not default with -frounding-math on, and, well, CGAL needs that.

Uber-Shaders: Evolution or Optimization

Let's just imagine that you have an uber-shader, and an uber-interface for it.  The uber-shader can do about 100 cool shading tricks, and is set with a struct like this:

struct shader {
 int tex_mode;
 int tex_ref;
 int want_shadows;
 int want_emissive_tex;
 int lit_ref;
 ...
};

A single function "setup" takes a shader struct and sets all of the OpenGL parameters to make it happen.  This function knows what the GLSL code looks like and does the right thing.

This design has been a win for us with X-Plane because:

• The encapsulated setup function can deal with hw-specific issues.  For example, if you can approximate the shader state request using the fixed-function pipeline on old hardware, this gets hidden in "setup" and client code doesn't care.
• Since you have access to all state at the same time, you can do things like pick from a set of customized shaders based on state combinations.  (In other words, you can create a large number of highly optimized shaders for specific cases.)

Evolution

What do you do if you need to change one parameter of the shader?  The naive answer is:

reset(&shader);
shader.tex_ref=something;
setup(&shader);

In other words, you tear down OpenGL state, change the request, then build it up again.

Well, that seems inefficient, doesn't it?  What if there is a fast path?  (For example, if all you are changing is polygon offset, all you really need to do is call glPolygonOffset.

One extension to the uber-shader interface is a series of 'evolution' APIs that change a single parameter, e.g.

change_tex(&shader,something);

Naively this is equivalent to the reset/change/setup code above, but the implementation might do something clever, like only rebind the texture unit but leave the shader object alone.

Is this a win?  It seems reasonable to hope so.  For example, if the state being changed is effectively a uniform passed to the GPU (or GPU state not related to shading), we might be a lot closer to minimal state change.

Optimization

What happens when your shader gets really big and complex?  One problem is that the logic in client code that sets up the shader gets big and complex.  For example: if the source texture has no alpha channel and there is no overlay texture, you can disable alpha blending.  Disabling alpha blending might be a huge performance win - maybe your app is bottlenecked on raster ops.  But having this logic everywhere in the client code isn't good - it means that you're not sure that you have ideal optimization at every shader point.

One way around this is to write an optimization function as part of the uber-shader code, e.g.

optimize(&shader);

The optimizer goes through all the requested shader state and "harmonizes" it.  Because the optimizer is part of the shader setup code, the knowledge of how the shader really works is now isolated to the one place in the app that should know such things.  Now you can put fairly complex logic in place to detect fast paths and take them every time.

Clash of Optimizations

The problem with optimization vs. evolution is they don't play nice together.  The evolution functions assume that you know the start state of your shader before you change it.  But the optimization API might have changed your shader in an unexpected way.  For example:

• You set up a shader with a texture and blending.
• You run the optimizer on it.  The optimizer turns off blending because the texture doesn't actually have an alpha channel.
• You run the evolution API to change to a texture that does have an alpha channel.

At this point you're screwed: blending has been turned off and is gone.

My solution to this is a bit crude but goes like this:

• There are no evolution APIs.
• Changing state requires changing the original shader and re-optimizing.
• Inside the shader, all state changes are lazy and tracked (e.g. we only change GL state if we really need to).
• We never reset state while in the middle of shader ops.

So in the above case what's going to happen is:

1. We calculate the optimal shader for filling.
2. When we go to change state, the "reset" of the shader actually does nothing.
3. We calculate a new optimal shader.
4. When we go to set up that new shader, almost all of the GL state change is a no-op.  In particular, if we could have "evolved" (E.g. really we only need to change the texture) that's all we will really change.

This design isn't perfect - it's burning CPU to calculate ideal GL state change at runtime rather than compile time.  That's the down-side.  The up-side is that we get optimal GL state under all conditions.