CGLA: Abusing merge_edge

The CGAL arrangement_2 operation "merge_edge" takes two connected half-edges (connected by a vertex of degree 2) and makes them one. Useful! But there is some fine print:

merge_edge is only meant to be used when the new combined curve covers the exact same path as the old curve. If you are using line segments as your curves, this means the three vertices involved (the middle vertex is the one to be deleted) are collinear.

Can merge_edge be abused to remove edges that bend? Yes, sort of, if you are very careful:

1. You must verify that the new combined edge does not cross any other edges, and will be in the same face as the existing two edges. This limits how much you can move an edge by combining. Basically merge_edge can't change topology!
2. The two half-edges being merged must go in the same direction! Otherwise, the half-edge direction flag could be wrong after the merge.

None of this is very safe - safer (but slower) is to simply add the new edge and delete the two old ones.

STL Priority Queue

The STL on my Mac seems to have a "priority queue", but it's not quite what I want - it's just a wrapper around a heap.  What I want in a priority queue is:

1. log-time insertion of elements.
   
2. Constant time popping of the front.  (Actually, I can live with log-time here.)
   
3. The ability to reprioritize a single item in log time, based on the item itself.
   
4. Priorities stored with the elements (rather than calculated by a comparator).
   
5. Ability to put items into the queue without adding special "helper" fields.

Those last two points aren't critical, but they are very convenient.

Item 3 is what makes things interesting...for a lot of priority queue algorithms, the algorithm is only fast if you can reprioritize just a few affected other items without going over the entire queue.  (Doing an entire-queue operation will typically give you N-squared time, because you hit the entire queue to reprioritize every time you process a single item.)

There are two ways I've used to do this:

1. If I store the priority in the item itself (violates the last two points), I can just insert the items into an STL multi-map by priority.  To reprioritize an item, I find it by doing an equal_range query on its current priority, erase it, then reinsert it at the new priority.
2. To meet all the point, I use a map from priority to item, but then maintain a separate "back-link" map from items to iterators into the original map.  This gives me the ability to find an item by value and remove it from the priority queue and reinsert it.

The system can be made more efficient by using a hash map instead of a regular map for the back links, but it requires a hashing operator to be defined for the values, rather than just operator<.

User Clip Planes and GLSL

To combine a GLSL shader and user clip planes, you need to do two things:

1. Set up your clip plane normally using glClipPlane and glEnable(GL_CLIP_PLANEx).
2. Make sure to write the eye-space transformed vertex position to gl_ClipVertex in your vertex shader.

You do not have to do the clipping yourself - you just need to output an eye space vertex from your vertex shader so that the GPU can do it for you.  (Remember, normally your shader outputs only clip-space coordinates, potentially skipping eye-space entirely.)

And this should make sense - the shape of a clipped triangle may not be a triangle - it could be a quadrilateral which must then be decomposed into two triangles for the setup-engine.  So clipping needs to be done by dedicated hardware - your shader just has to give it access to eye-space coordinates.

(Clip planes are similar to eye-space tex-gen and lights in that you specify your input in object space, but the clip plane is then transformed to eye space at input time.  This means that the clip plane is stored "camera relative" and will not move as you move the model view matrix. This is a good thing - clip planes are typically global in nature, so we don't want them to move each time we move the original to draw a car or some other moving mesh.)

EDIT: of course, you'll get software render if you touch gl_ClipVertex on most hardware.  Your options:

• Use fixed function pipeline.
• Use pre-writing the Z buffer if you can.
• Case this out by card.

CGAL Arrangements - How Do You Find Your Edges?

A fundamental client problem with the CGAL arrangement_2 class: how do you recover handles to the edges you insert?  Note that the insertion APIs do not return halfedge handles unless you use very specialized (read: limited) functions.

I have found basically two strategies:

If you can afford to iterate across every single half-edge in the arrangement, use Arr_consolidated_curve_data_traits_2 to tag your input curves with an index number back to the original source data.  

After the insert (and you can use any kind of bulk insert you want), simply iterate across all edges (remember, a single curve is shared between two halfedges), pull out your key, and you now have a link from half-edge to original curve.  This is a many-to-many relationship - the consolidated cure traits will make sure that multiple keys make it to a half-edge if needed.

If you are doing a small amount of incremental work, attach an observer.  You will need to override the following observer messages:

• after_create_edge to detect new half-edges induced for your insertion.
• after_modify_edge to detect cases where your edge completely overlaps an existing half-edge.
• after_split_edge to detect the case where your edge partly overlaps an existing edge.  (The existing edge will be split so that there is a vertex at the end of your inserted curve.)
• If the curves you are inserting intersect with each other, after_split_edge also needs to detect the case where an edge you previously inserted and care about is split in two.

I use the former strategy for the bulk creation of a map from source data - I'm going to have to apply traits to every edge, so I might as well let the bulk insertion run without a ton of individual callbacks, then go through later.

I use the latter strategy to detect induced rings when I am adding small areas and not using the sweep-line algorithm.

Future work: I have not had time to analyze whether incremental observation is better/worse for performance than bulk insertion with consolidated data keys.

To Sweep or Not To Sweep

I've spent the week porting the X-Plane scenery generation code back to CGAL.  I will describe the history of this code and its constant battle with robustness in another post, but for now I will just mention that credit goes (besides obviously to the authors of CGAL, who are geniuses of the Nth degree) to Andrew McGregor for a lot of the ideas on how to use CGAL with the scenery generation code - the final design is really just a refinement of his work.

The X-Plane scenery generation code (which we just call "the render farm") is the code that turns hundreds of GB of GIS data into scenery.  At its heart is a topologically integrated planar map of all vector features in a given tile - every road, river, coastline, change of terrain type, etc. is baked into one map.  A typical map might have half a million edges, covering a 1 x 1 degree area.

For X-Plane 8.20 and 9.0 we shipped using a planar map I wrote myself.  While the planar map didn't work very well, it had a few special cases that were highly optimized.  In particular, given two sub-regions of two maps, with an identical ring of half-edges identifying them (identical meaning identical coordinates) you could swap the interiors of the two regions in time proportional to only the number of elements inside the ring.

It turns out that this is a really useful trick for a few things:

• If you have a huge map you want to tile, you simply induce the cut lines, and swap each single tile with an empty map.
• If you want to "overlay" a polygon, or even a sub-map (destroying what is below) you simply induce a border ring in both polygons and swap.
• You can crop a map's interior or exterior by inducing a ring and swapping with a blank map.

This was an operation where the devil is in the details - because components are swapped "in-place" the swap doesn't have to copy, allocate, or deallocate the map, so it turns out to be fast in pracatice.  In terms of time complexity, it's very fast for very small operations on a huge map, which turns out to be an important case for us.

Now CGAL's arrangement_2 gives me some power tools* that are very useful - in particular, sweep-line algorithms.  The link shows a good explanation.  Basically the power of the link is to process a set of line segments in a lot less than O(N^2).

But there's a slight problem with sweep-line - it has to iterate over the entire set of edges in a map, including the ones already in the map.  That means that inserting a small number of edges into a complex map is surprisingly slow.

So in some cases I now have two implementations of various map operations:

• Sweep-based implementations, which are good when we're inserting a lot of data at once.
• Incremental implementations - theoretically much worse, but acceptable to keep the size of our data set down.

So far, incremental operations are proving to be a big win when "burning airports" - that is, merging or overlaying very small airport boundary areas into a full map.

* Of course, the real advantage of CGAL is that it is robust and doesn't randomly blow up during operations!