Shulou(Shulou.com)06/02 Report--

This article introduces the relevant knowledge of "the principle of NavMesh generation". In the operation of actual cases, many people will encounter such a dilemma. Next, let the editor lead you to learn how to deal with these situations. I hope you can read it carefully and be able to achieve something!

Brief introduction

This article introduces the core processing flow of NMGen. NMGen is used to generate polygonal data that represents the surface of the navigation mesh. There are many ways to generate grids, but they all include the following steps.

The main process is as follows:

1. Voxel. A solid height field is constructed from the source geometry to represent the unwalkable space.

two。 Generate region. The continuous intervals in the upper surface of the solid height field are merged into regions.

3. Generate an outline. Detect the outline of the area and construct a simple polygon.

4. Generate a polygon mesh. The outline is divided into convex polygons.

5. Generate a high level of detail. Triangulate the polygon mesh to get a high degree of detail.

1. Voxelization (voxel)

Core class: Heightfield

In the voxel stage (a voxel is a large point in space), the source geometry is converted into a height field, which is used to represent the unwalkable space. Some unwalkable surfaces will be removed at this stage (such as those with excessive slopes).

For each triangle on the source geometry, the conservative voxel algorithm (Conservative Voxelization) is used to divide it into voxels and add them to the height field. The conservative voxel algorithm ensures that each triangular face is completely surrounded by the generated voxels.

After the voxel stage, the solid height field (solid heightfield) contains many span, covering all the faces on the source geometry.

2. Region Generation (generating region)

Core class: CompactHeightfield

The goal of this phase is to further define which parts of the solid surface are walkable and to divide these walkable parts into contiguous areas that can eventually form simple polygons.

First of all, the solid height field is converted into an open height field (open heightfield), which is used to represent the walking parts of the solid surface. An open height field that represents the part of the surface located on the surface of a solid space.

In the following figure, the green part represents the surface in the open area (span). This is equivalent to all the walkable upper surfaces of the solid height field. Note that the walls, the areas under the table, and the narrower areas on the corridor handrails have been removed when the solid height field is generated. Some non-walkable areas, such as desktops, stair handrails, and narrower positions beside the walls, are still displayed as walkable.

Then, further remove the unwalkable areas. When the calculation is complete, those parts of the open interval that are thought to be able to walk should pass the following test:

-this area cannot be close to obstacles (e.g., walls, furniture, etc.) (use WalkableRadius as the distance threshold)

+ this area does not have enough open space above the surface (non-collision area). (people can move legally without colliding with other objects) (use WalkableHeight as the height threshold)

Generate adjacency information for all remaining intervals, which is used to merge them into one large patch. The algorithm uses a maximum vertical step size (WalkableStep4) to determine which intervals can be joined together. This allows some special structures to be considered, such as stairs, roadsides, desktops, etc. For example, the sections that make up the ladder can be connected as neighbors, while the sections on the desktop cannot be connected to the floor.

The following picture shows the area. Pay attention to the areas on the ladder, although the intervals are not directly connected. It is also important to note that the tables, stair handrails, and all other non-walkable faces on the solid height field have been successfully removed after this stage (black indicates the removed interval).

After this stage, these connected areas represent walkable surfaces.

3. Contour Generation (generate outline)

Core class: ContourSet

The outline is to "walk" along the edge of the area, forming a simple polygon. This is the first step in converting voxel space back to vector space.

First, very fine polygons are generated from the region.

Then, use a variety of algorithms to complete the following steps:

+ simplify the edges of adjacent polygons (the part between regions)

+ simplified boundaries (boundaries are contours with no adjacencies or obstacles) (EdgeMaxDeviation)

+ optimize the length of the boundary. (if the boundary is too long, you can't get the optimal triangle)

The following figure shows the outline after executing this algorithm

At the end of this phase, simple polygons represent walkable surfaces.

4. Convex Polygon Generation (generate convex polygons)

Core class: PolyMesh

Many algorithms can only be used for convex polygons. Therefore, this step requires the conversion of a simple polygon composed of contours into a convex polygon mesh.

In the following illustration, you can see the convex polygons formed by contours.

At the end of this phase, a convex polygon mesh represents a walking surface.

5. Height Detail Generation (generate high level of detail)

Core class: PolyMeshDetail

In this final stage, the convex polygon mesh is triangulated by the Delaunay triangulation algorithm, so a high level of detail can be added. Add vertices to the interior or edge of the polygon to ensure that the mesh is equivalent to the surface of the original geometry. (DetailSampleDistance and DetailMaxDeviation)

This is the end of the introduction of "the principle of NavMesh Generation". Thank you for your reading. If you want to know more about the industry, you can follow the website, the editor will output more high-quality practical articles for you!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.