A Navigation Mesh Map Representation Method Oriented to 3D Scene

Abstract

The invention provides a navigation grid map representation method for 3D scenes, which extracts walkable hierarchical planes in the 3D scene to obtain a set of walkable hierarchical planes, and removes isolated planes and non-walkable planes; abstracting the walkable hierarchical planes The initial impassable area of ​​the internal pathfinding character can abstract the model in the 3D scene into an impassable area; merge the polygons in the initial impassable area to obtain the final impassable area; merge the intersecting areas in the initial impassable area , forming a final impassable area. The constraints in the hierarchical plane are constrained by Delaunay triangulation to form a triangle set; all the triangle sets in the walkable hierarchical plane together constitute the final navigation mesh. The final navigation mesh can fully separate obstacles and walkable areas. The invention is applied in the field of digital media technology and effectively ensures the separation of obstacles and walkable areas.

Description

technical field [0001] The invention belongs to the technical field of digital media, in particular to a 3D scene-oriented navigation grid map representation method. Background technique [0002] The visual impact and experience that 3D large-scale scenes bring to users are incomparable to 2D scenes. With the continuous upgrading of hardware such as graphics cards in recent years, more and more large-scale 3D scene games are emerging. At the same time, artificial intelligence technology It is widely used in games and plays a vital role in improving the realism of games, and intelligent pathfinding technology is an important part of game artificial intelligence. However, traditional pathfinding technologies cannot adapt to the complexity of 3D scenes, and there is an urgent need for related technologies that can efficiently complete intelligent pathfinding in 3D scenes. [0003] The 3D scene is composed of a series of art models, and there is no specific relationship between...

AI Technical Summary

Problems solved by technology

The grid method is the most convenient representation method, but it can only adapt to early two-dimensional scenes, not three-dimensional scenes

The quadtree method is an improvement of the grid method based on the early two-dimensional scene, and it cannot adapt to the three-dimensional scene.

The representation method of the navigation grid adopts a collection of convex polygons, which can be triangles or hexagons, etc., but the triangle set is the most researched at present, because triangles are convex polygons with the least number of sides, and the division granularity is small. Cover the entire walking area and reduce the number of irregular convex polygons, but the navigation grid representation also has some disadvantages. One is that it needs to consume a lot of memory to store nodes

Second, it is difficult to adapt to dynamic scenes

It can be seen that the above-mentioned traditional scene map representation method can only adapt to 2D scenes and early simple 3D scenes, but cannot adapt to large 3D scenes

Images