Convex Polygon Generation
This page describes the forth stage in building a navigation mesh, the generation of convex polygons from the simple polygons represented by contours. This is also where we move back into vector space, leaving voxel space behind.
If you need an overview of what is performed in this stage, please refer back to the high level process.
The High Level
The main tasks of this stage are as follows:
- The vertices of the contours are in voxel space, which means their coordinates are in integer format and represent distance from the heightfield's origin. So the contour vertex data is converted into the vector space coordinates of the original source geometry.
- Each contour is completely independent of all other contours. During this stage we merge duplicate data and combine everything into a single mesh.
- The contours are only guaranteed to represent simple polygons, which include both convex and concave polygons. Concave polygons are not useful for navigation meshes. So we sub-divide the contours as needed to get convex polygons.
- We gather connection information indicating which edges of each polygon connect to another polygon. (Polygon neighbor information.)
Coordinate conversion and vertex data merging are relatively simple processes. So I don't go over them here. You can look at the well documented source code if you are interested in those algorithms. Instead, we will concentrate on the sub-division of the convex polygons. The following steps are performed for each contour:
- Triangulate each contour.
- Merge triangles to form the largest possible convex polygons.
We end the stage by generating neighbor connection information.
Triangulation is performed by walking the edges of the contour and, for each group of three vertices, determining whether a valid internal triangle can be formed. From all potential candidates, select the one with the shortest new edge. New edges are called "partition edges", or "partitions" for short. The process continues with the remaining vertices until triangulation is complete.
To improve performance, triangulation is run on the xz-plane projection of the contour.
Step-by-Step: Find potential partitions.
Select the shortest partition and form a triangle. Get rid of invalidated partitions and generate new potential partitions.
...until triangulation is complete.
Detecting Valid Partitions
Two algorithms are used to determine whether a group of three vertices can form a valid internal triangle. The first algorithm is fast and can quickly cull partitions that lie entirely outside of the polygon. If the partition is inside the polygon a more expensive algorithm is used to make sure it doesn't intersect any existing polygon edges.
This algorithm can be a little difficult to describe. So here are some examples. First, a valid partition. For the vertices A, B, and C, where AB is the potential partition...
Cast two rays out along the edges connected to vertex A. The interior angle is the angle in the direction of the polygon. If the partition endpoint (vertex B) is within the interior angle, then it is a potential valid partition.
This second example is the same scenario with different vertices. Since the partition endpoint (vertex B) is outside the interior angle, it can't be a valid partition.
The Edge Intersection Algorithm
This algorithm is much easier to understand. It simply loops through all edges in the polygon and checks to see if the potential partition intersects with any of them. If it does, it isn't a valid partition.
Only if both algorithms pass is the partition considered valid.
Merging can only occur between the polygons created from a single contour. No attempt is made to merge polygons from adjacent contours.
Note that I have switched to the general form "polygon" rather than triangle. While initial merging will be between triangles, as the merge process proceeds non-triangle polygons may be merged with each other.
The process works as follows:
- Find all polygons that can be merged.
- From this list, select the two polygons with the longest shared edge and merge them.
- Repeat until there are no further allowed merges.
Two polygons can be merged if all of the following conditions are met:
- The polygons share an edge.
- The resulting polygon will still be convex.
- The resulting polygon will not have more edges than allowed by the maxVertsPerPoly parameter.
Detecting shared edges and determining the merged edge count are both easy. Determining whether the merged polygon will be convex is a little more complex. The key to this check is the shared vertices. Both are checked for what they will look like after the merge. If both will form internal acute angles, then the merged polygon will still be convex. We determine this for each shared vertex as follows:
- Create a directed reference line formed by the vertices just before and just after the shared vertex.
- If the shared vertex is to the left of its reference line, then is forms an acute angle.
It is best to use visualizations. The first example demonstrates a valid merge.
If the shared vertex is labeled A, then the reference line will be from vertex A-1 to vertex A+1. Is vertex A to the left of the reference line?
Now check the second shared vertex. Is it to the left of its reference line?
In this next example, the merge is invalid since one of the shared vertices will form an obtuse internal angle if the merge occurs.
If you are unfamiliar with the algorithm used to check the position of a point relative to a directed line, a good explanation is given at Soft Surfer. The core algorithm is implemented by the getSignedAreaX2() operation in the PolyMeshFieldBuilder.
The last step in this stage is to iterate through all the polygons in the entire mesh and generate connection information. While the algorithm is optimized, at its most basic level it simply steps through all the polygon edges and looks for other polygons that have an edge with the same vertices.
Where We Are
We are finally back into vector space and have a mesh of convex polygons.