This page describes the third stage in building a navigation mesh, the generation of simple polygons (convex and concave) that represent the traversable surface area of the source geometry. The contours are still represented in the units of voxel space, but this is the first step from voxel space back to vector space.
If you need an overview of what is performed in this stage, please refer back to the high level process.
Searching for Region Edges
The biggest conceptual change when moving from an open heightfield structure to a contour structure is the switch from concentrating on the surface of spans to concentrating on the edges of spans.
For contours, we care about the edges of the spans. There are two types of edges: region and internal. Region edges are span edges across which the neighbor is in another region. Internal edges are span edges across which the neighbor is in the same region.
The next several examples only deal with 2D for easy of visualization. We will get back to 3D later.
During this step we want to categorize edges as either region edges or internal edges. This information is easy to find. We iterate all spans. For each span we check all axis-neighbors. If an axis-neighbor is not in the same region as the current span, the edge is flagged as a region edge.
Once we have information on which span edges are region edges, we can build a contour by "walking the edges". Once again we iterate the spans. If a span is found that has a region edge, we do the following:
Start by facing the known region edge. Add it to the contour.
Rotate in 90 degree increments, adding region edges to the contour, until we find an internal edge. Step forward into the neighbor span.
Rotate 90 degrees counter-clockwise and re-perform the previous step. Continue until we return to the starting span, facing the starting direction.
Moving from Edges to Vertices
We need vertices, not edges, if we want to move back into vector space. The (x, z) values of the vertices are easy to determine. For each edge, we take the (x, z) values of the corner of the top of the span in the clockwise direction from the edge. (When viewed from inside the span.)
All edge vertices have up to four potential y-values. The highest y-value is selected for two reasons: It ensures that the final vertex (x, y, z) is above the surface of the source mesh. It also provides a common selection mechanism so that all contours that use the vertex will use the same height.
Simplifying the Contours
At this point we have generated contours for all regions. The contours are made up of vertices derived from the corners of spans. Follows is a macroscopic view.
Note that there are two types of contour sections. Sections that represent the portal between two adjoining regions, and sections that border on "empty" space. In the code documentation empty space is referred to as the "null region". I will use the same term here.
Do there really need to be so many vertices? Even on the straight contours there is a vertex for every span that makes up the edge. Obviously, the answer is no. The only truly mandatory vertices are the vertices where there is a change in region connection. I.e. The vertices at the edge of region portals.
The simplification of region-region portals is easy. We discard all but the mandatory vertices.
Things get a little more complex for the connections to the null region. Two algorithms are used.
The first is the Douglas-Peucker algorithm implemented by MatchNullRegionEdges. It uses the edgeMaxDeviation parameter to decide which vertices to discard to get simplified line segments. It starts off with the mandatory vertices, then adds vertices back such that none of the original vertices are farther than edgeMaxDeviation distance from the simplified edges.
Step-by-Step: Start with the simplest possible edge.
Find the farthest point from the simplified edge. If it exceeds edgeMaxDeviation, add the vertex back to the contour.
Repeat the process until no more vertices exceed the allowed distance from the simplified edges.
An example of simplified contours...
As mentioned earlier, one more algorithm is used for edges that connect to the null region. The first algorithm can generate long line segments that can result in long thin triangles later in the mesh generation process. The second algorithm, implemented by NullRegionMaxEdge, uses the maxEdgeLength parameter to re-insert vertices to ensure that no line segment exceeds a maximum length. It does this by detecting long edges, then splitting them in half. It continues this until no more excessively long edges are detected.
For an example of the impact on the final mesh, before...
Where We Are
At the end of this stage we have contours that form simplified polygons. The vertices are still in voxel space. But we are well on our way back to vector space.