problem with navmesh geometry input data

[AleksanderKamienski]

hello, we started using your library in our project (https://github.com/aamks/aamks) in which we create models for evacuating people from buildings during fires. At this point we are only using pathfinder/pyrvo. It is very helpful for us and we thank you for it. We would also like to use the NavmeshBaker class from your code for building navmesh and PathFinder class for human path-finding. Your code is in python, which would make our work easier because our backend is also in python and it will be easy to debug and find some possible problems. We currently use external programs to create navmesh and find paths. (https://github.com/arl/go-detour/ for building navmesh and https://github.com/layzerar/recastlib.git for finding paths). The input geometry file format in the current navmesh builder app we use is for example as follows:

o Face0
v 15.94 0.99 18.19
v 17.54 0.99 18.19
v 17.54 0.99 19.94
v 15.94 0.99 19.94
f 1//1 2//1 3//1 4//1

o Face1
v 21.99 0.99 14.59
v 23.79 0.99 14.59
v 23.79 0.99 15.59
v 21.99 0.99 15.59
f 5//1 6//1 7//1 8//1

o Face2
v 23.04 0.99 18.29
v 23.69 0.99 18.29
v 23.69 0.99 20.34
v 23.04 0.99 20.34
f 9//1 10//1 11//1 12//1

o Face3
v 26.99 0.99 18.29
v 29.09 0.99 18.29
v 29.09 0.99 19.79
v 26.99 0.99 19.79
f 13//1 14//1 15//1 16//1

o Face4
v 31.03 0.99 21.08
v 31.03 0.99 16.54
v 30.99 0.99 16.54
v 30.99 0.99 21.08
f 17//1 18//1 19//1 20//1

o Face5
v 24.74 0.99 21.08
v 24.74 0.99 21.04
v 15.48 0.99 21.04
v 15.48 0.99 21.08
f 21//1 22//1 23//1 24//1

o Face6
v 15.48 0.99 16.58
v 15.48 0.99 7.74
v 15.44 0.99 7.74
v 15.44 0.99 16.58
f 25//1 26//1 27//1 28//1

o Face7
v 24.74 0.99 7.78
v 24.74 0.99 7.74
v 15.48 0.99 7.74
v 15.48 0.99 7.78
f 29//1 30//1 31//1 32//1

o Face8
v 27.63 0.99 21.08
v 27.63 0.99 21.04
v 24.78 0.99 21.04
v 24.78 0.99 21.08
f 33//1 34//1 35//1 36//1

o Face9
v 30.99 0.99 21.08
v 30.99 0.99 21.04
v 28.49 0.99 21.04
v 28.49 0.99 21.08
f 37//1 38//1 39//1 40//1

o Face10
v 30.99 0.99 16.58
v 30.99 0.99 16.54
v 24.78 0.99 16.54
v 24.78 0.99 16.58
f 41//1 42//1 43//1 44//1

o Face11
v 15.48 0.99 21.08
v 15.48 0.99 16.54
v 15.44 0.99 16.54
v 15.44 0.99 21.08
f 45//1 46//1 47//1 48//1

o Face12
v 24.78 0.99 18.58
v 24.78 0.99 16.54
v 24.74 0.99 16.54
v 24.74 0.99 18.58
f 49//1 50//1 51//1 52//1

o Face13
v 24.78 0.99 21.08
v 24.78 0.99 19.44
v 24.74 0.99 19.44
v 24.74 0.99 21.08
f 53//1 54//1 55//1 56//1

o Face14
v 24.78 0.99 16.58
v 24.78 0.99 7.74
v 24.74 0.99 7.74
v 24.74 0.99 16.58
f 57//1 58//1 59//1 60//1

o Face15
v 20.59 0.99 16.54
v 20.59 0.99 16.58
v 24.74 0.99 16.58
v 24.74 0.99 16.54
f 61//1 62//1 63//1 64//1

o Face16
v 19.73 0.99 16.58
v 19.73 0.99 16.54
v 15.48 0.99 16.54
v 15.48 0.99 16.58
f 65//1 66//1 67//1 68//1

o Face17
v 18.59 0.99 10.64
v 21.59 0.99 10.64
v 21.59 0.99 13.64
v 18.59 0.99 13.64
f 69//1 70//1 71//1 72//1

o Face18
v 24.74 0.0 16.54
v 24.74 0.0 7.74
v 15.44 0.0 7.74
v 15.44 0.0 16.54
f 73//1 74//1 75//1 76//1

o Face19
v 24.74 0.0 21.04
v 24.74 0.0 16.54
v 15.44 0.0 16.54
v 15.44 0.0 21.04
f 77//1 78//1 79//1 80//1

o Face20
v 30.99 0.0 21.04
v 30.99 0.0 16.54
v 24.74 0.0 16.54
v 24.74 0.0 21.04
f 81//1 82//1 83//1 84//1

for better visualization when we draw above coordinates, we will get the following image:

which is simple plan of a building from which we can model evacuation. Geometry is made from polygons. The walls are very thin rectangles - 4 px width. Other rectangles represent entire rooms or obstacles. Those polygons inside rooms and corridor are obstacles which people should avoid during evacuation.

In your library, the required input data to NavmeshBaker (add_geometry function) is different - two lists of vertices and polygons, which build the space in which agents can move (without the obstacles that are in the room and the walls). This is a different geometry format than in navmesh builder we use so far (https://github.com/arl/go-detour/). Do you know a way to be able to enter geometry data into your program in the format we currently use to build navmesh in our project or any workaround?

[Tugcga]

add_geometry method of the NavmeshBaker object accept polygonal description of the level geometry (floor, walls, tables and other obstacles as polygonal object). And then by using bake method it generates polygonal description of the navigation mesh. It's easy to convert our obj-format of the geometry to required two arrays. You can add each polygon separately. For example, you create the baker object

baker = NavmeshBaker()

Then for adding the first polygon, you write

baker.add_geometry([(15.94, 0.99, 18.19), (17.54, 0.99, 18.19), (17.54, 0.99, 19.94), (15.94, 0.99, 19.94)], [[0, 1, 2, 3]])

This command add the first polygon. Then for the second

baker.add_geometry([(21.99, 0.99, 14.59), (23.79, 0.99, 14.59), (23.79, 0.99, 15.59), (21.99, 0.99, 15.59)], [[0, 1, 2, 3]])

Notice that in both cases polygon indexes are [[0, 1, 2, 3]] because these indexes should be local indexes in the vertex array from the first argument. Of course, you can gather all vertices from your geometry into one array, all polygons into another array, and then execute add_geometry function once. Additional note: your obj-format index vertices from 1, but for add_geometry method your should index vertices from 0 (in usual way).

Here is a simple function, which read obj-file with geometry and return arrays with vertices and polygons

class Polymesh:
    def __init__(self):
        self.vertices = []
        self.faces_vertex_count = []
        self.faces_definition = []

def import_obj(filename):
    # Creating an empty polymesh data structure
    polymesh = Polymesh()
    # Creating a vertex variable
    vertex = [0.0, 0.0, 0.0]
    # Open the file
    f = open(filename, 'r')
    lines = f.readlines()
    current_line_index = 0
    for line in lines:
        if line[0] == '#': pass
        elif line[0:2] == 'v ':
            # Found a vertex
            values = line[2:].split()
            # Setting new vertex coordinates
            vertex[0] = float(values[0])
            vertex[1] = float(values[1])
            vertex[2] = float(values[2])
            # Adding the new vertex
            polymesh.vertices.append(tuple(vertex))
        elif line[0:2] == 'f ':
            # Found a face
            values = line[2:].split()
            # values length is our number of vertices defining this face
            polymesh.faces_vertex_count.append(len(values))
            for vindex in values:
                # OBJ vertex indices starts at 1 instead of 0
                polymesh.faces_definition.append(int(vindex.split('/')[0]) - 1)
        current_line_index += 1
 
    f.close()
     
    return polymesh

Then you can use it as follows:

mesh = import_obj("path to obj file")

polygons = []
index = 0
for s in mesh.faces_vertex_count:
    polygon = []
    for i in range(s):
        polygon.append(mesh.faces_definition[index])
        index += 1
    polygons.append(polygon)

baker = nmb.NavmeshBaker()
baker.add_geometry(mesh.vertices, polygons)

[AleksanderKamienski]

Thank you for your help, now our application works on your libraries (navmesh baker, path finder, rvo2). We noticed that the navigation mesh in your library is built on the internal surface of the building at a distance of approximately cell_size + agent_radius from internal walls and obstacles. In previous libraries it was slightly different, the grid was built over a larger area. We will test and if we find any errors, we will contact you. Thank you again and all the best!

[Tugcga]

As I understand, you mean this gap between walls and actual walkable area

The baker adds this gap to prevent agents from intersecting with walls, even if an agent is placed near the boundary. The baking algorithm from Recast-Detour works in a similar way.

[AleksanderKamienski]

Yes, you're right, I described the problem badly. We previously used this library: https://github.com/layzerar/recastlib.git . This is a python interface to the https://github.com/recastnavigation/recastnavigation library. In the file https://github.com/layzerar/recastlib/blob/master/examples/simpletest.py you can see that there is a code that allows to find the path even if the coordinate (x,y,z) is slightly outside the built navigation mesh - the logic described in https://github.com/layzerar/recastlib/blob/master/examples/simpletest.py (query.findNearestPoly) will find and return the path in this case. It's a bit different in your library. For example, if I call the search_path((10,0,11),(30,0,20)) function from the pathfinder/navmesh file and the coordinate (10,0,11) is outside the built grid, the function will return an empty list. You don't have a findNearestPoly function that will allow to find the path if the agent's coordinate is outside the constructed grid, as in https://github.com/layzerar/recastlib/blob/master/examples/simpletest.py. This is a problem for us, because in our "aamks" software it sometimes happens that due to the relatively small area of ​​the navigation mesh compared to the dimensions of the for example corridor (when I set the NavmeshBaker::bake cell size to 0.05, agent_radius to 0,25 , a 90 cm wide corridor has a navigation grid only along the middle of the corridor and its width is about 30 cm) and due to the pushing of people using the rvo2 algorithm, the agent's coordinate passed to the search_path() function is sometimes outside the built navmesh and the function returns an empty array. Do you have an idea how to solve this problem? What comes to my mind is to add functions to you lib such as those in the library https://github.com/recastnavigation/recastnavigation, of course in Python, so that the logic presented in the file https://github.com/layzerar/recastlib/blob/master/examples/simpletest.py was possible to implement using your pynavmesh library. For example by adding some kind of findNearestPoly function?

[Tugcga]

There is no functionality in the Python module to solve your problem. You need a method that allows you to find the nearest point in the navmesh for any input spatial point. The data structures implemented in the module do not allow this. This task required additional structure within the Navmesh class.

The AssemblyScript version of the Pathfinder module (placed in this repo in the adjacent folder) contains the required functionality. It's the TriangleBVH class in \assemblyscript\assembly\navmesh\navmesh_bvh.ts and sample method of this class. This class is not very complex and it's possible to implement it in Python. Maybe I will find some time for it. But I do not promise anything. You can try to port this class to Python yourself. The constructor for this class accepts the simple array of triangle vertex coordinates (these triangles are triangles from the triangulation of the baked navigation mesh) and some delta radius. This radius allows you to find the closest point in any triangle, even if the input point is outside the AABB of the triangle. This is exactly what you need.

[AleksanderKamienski]

Thank you for the quick reply. So, as I understand it, I would have to create a TriangleBVH class and a sample method. Then the Navmesh class in the pathfinder/navmesh file would have the self._triangle_bvh variable instead of the self._bvh variable. Then in the sample_polygon and search_path functions in 3 places, instead of self._bvh.sample(xxx), I would call self._triangle_bvh.sample(xxx). Is my reasoning good? Should this work or are there could be any more problems? If it should work, I'll be happy to look into it and rewrite the ts code into Python to add the TriangleBVH class and try it. If it worked, it would make our job a lot easier.

[AleksanderKamienski]

I read the navmesh.ts code and the search_patch function. This is a bit more complicated than I described in the comment above. I will try to rewrite this code into python. If I have any problems, I will let you know.

[Tugcga]

Let me describe the solution in more detail.

You have to solve a specific task: for each input point, find the point in the navigation mesh that is closed to the input point. This task is completely independent of the existing functionality of the Path-finder module. You should solve this task separately and then pass the calculated point in the navigation mesh to the Path-finder algorithm (using the navmesh object). You don't need to change anything in the module code.

There are several ways to find the point in the navigation mesh that is closed to the input one. The naive algorithm is as follows. Simply iterate on the triangles of the navigation mesh, for each triangle find the point in the triangle that is closed to the input one, and then choose the point with the minimum distance. It's easy to implement, but this approach is not optimal. The navmesh may have many triangles, and then the task may take a long time. But this approach is simple. The way to find the closed point in the triangle is trivial (some linear algebra with cross and dot products of vectors).

Another way is to pack the triangles of the navigation mesh into the BVH tree. It is a bit more complicated, but as a result the process of finding the nearest triangle is much faster. This method is implemented in the AssemblyScript version of the module. For performance reasons, I use arrays instead of objects in this implementation. This makes the code look more complicated than it is.

[Tugcga]

I update the Python module. Now Pathfinder object and Navmesh object contains the method .sample(point), which returns coordinates of the point on navigation mesh closed to the input point.

[AleksanderKamienski]

Thank you. I see that you also made options for a non-triangular mesh (polygons_to_triangles function). Great, it will definitely come in handy.