A Navigation Mesh Map Representation Method Oriented to 3D Scene

Abstract

The invention provides a method for representing navigation grid map for 3D scene, comprising the following steps: extracting the walking hierarchy planes in a 3D scene; obtaining a set of the walking hierarchy planes; removing the isolated planes and the non-walking planes; abstracting the initial non-passable regions of a way-finding role in the walking hierarchy planes so as to abstracting the models in the 3D scene as non-passable regions; conducting region combination to the polygons in the initial non-passable regions so as to obtain a final non-passable region; combining the intersecting regions in the initial non-passable regions to form a final non-passable region; performing constrained Delaunay triangulation to the constraints of the hierarchy planes to form a triangular set; and structuring a final navigation grid by the triangular sets of all walking hierarchy planes. The final navigation grid capable of fully separating obstacles from walking regions. The invention is applied to the technical field of a digital media and can effectively ensure that obstacles are separated from walking regions.

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