**0**

# Followup: 6DOF Navigation Meshes

My last entry here talked about a method for merging multiple navigation meshes in 6-degree-of-freedom space for creating navigation environments from individual components. As is often the case with real software development, a couple of weeks worth of refinement has gone into the method, and some additional tidbits have come to light.

I mentioned originally doing a k-nearest-neighbor search when selecting points for joining the connected components of the navmesh in process; this can be especially critical when you need to support parallel travel of heavy volumes of agent traffic without artificial bottlenecking at mesh merge locations. In our particular situation this turned out to be far more important than I originally guessed, and in fact required revisiting the entire merge process to yield a more robust "stitching" of the meshes.

At the time I wrote the first article, I was using a kd-tree to accelerate the nearest-pair lookup and produce the final selection of points used in the connection algorithm. When it came time to adjust the code to produce more stitches, I encountered some severe performance issues - on the order of a 10-40x speed drop depending on the data being fed into the algorithm, for only an order of magnitude increase in the number of requested stitches.

To make a long and mostly dull story short, I eventually wound up dumping the entire stitching half of the algorithm and starting from scratch, doing a naive brute-force search for the nearest neighbors used in the stitching process. My initial logic looked something like this:

While there are more than one connected components in the graph

Select an arbitrary pair of connected components, CC1 and CC2

For each node N1 in CC1

For each node N2 in CC2

Compute distance from N1 to N2

Insert the pair (N1, N2) into a list, sorted by the distance value

While the list is larger than k elements

Remove the furthest-sorted pair from the list

For each pair in the final list

Create a stitched edge

Mark the two connected components as merged

Obviously this was painfully slow (on the order of many minutes to merge the test meshes) and has terrible overall performance characteristics. But what do you expect - it's a naive implementation, after all [wink]

My first observation was that this led to a lot of duplicate edges. I added a simple blacklist that prevented a node from being used in more than one stitch, which added a minor speed boost (only a few seconds - remember this was taking several minutes!) and improved the visual results substantially.

The second key observation followed from there: I was much more interested in prioritizing the

*blacklist*than the actual distance constraint! In other words, it was primarily important that the stitches not end up all joining the same nodes; the actual distance between stitched nodes was largely irrelevant. I only cared about the distance as a sort of heuristic to try and keep really wildly disjoint nodes from being stitched together and creating paths through boring, empty space.

At this point, it was easy enough to realize that the entire idea of doing a k-nearest-neighbor search (or more accurately, a k-nearest-unique-pair search) was a total red herring. All I needed was a set of seed points that was relatively "close" together, and the stitching could proceed from there.

This led directly to the next refinement of the logic, which (with only minor tweaks) ended up being the final incarnation of the algorithm, which is currently slumbering safely in our version control repository:

While there are more than one connected components in the graph

Construct a bounding box surrounding each connected component

Find the two components C1 and C2 whose bounding box centers are closest

Find the k1 number of points in C1 which lie closest to the center of C2's bounding box

Find the k1 number of points in C2 which lie closest to the center of C1's bounding box

Pair up each point in P1 with the corresponding point in P2 (based on index alone, no other criteria needed)

Sort the pairs by their separation distance

Select the k2 closest pairs, pruning pairs which create edges that intersect collision geometry

Create edges for the selected k2 pairs

Mark C1 and C2 as merged into a single connected component

This allows us to fine-tune the number of candidate pairings (k1) and then select the best from those (k2), which gives us a really easy switch for controlling how much time we trade off in the heuristic search phase (assembling the candidate pair list) with time spend actually stitching edges (connecting the k2 selected candidate pairs).

Net results? A mesh merge now runs in an average of ~0.55 seconds on our test data set, with a mere 0.22 seconds spent in the stitching phase. That means the majority of the time is actually spent shuffling storage around to hold the newly created, larger navigation mesh. With some tuning to our allocation strategy, we could probably drop this time even further - but for now, it's already a factor of 3 faster than the old method, and produces superior results.

I call that a pretty solid win.

Note: GameDev.net moderates comments.