Navigation Meshes from Open GIS Data

A navigation mesh is an abstract structure used by pathfinding algorithms to compute shortest path in space. It is often used in video game AI to set objects trajectory. Game Engine such as Unity uses navigation meshes for instance to control non-player characters (NPC’s).

Currently working on crowd simulation, we have been using game engine to model crowd movement within our cities.

This include of course the use of navigation meshes for our pedestrian to walk on.

In this article, we are going to showcase how to produce naviation meshes using python and the Basisregistratie Grootschalige Topografie (BGT) dataset from the Dutch Kadaster, especially the wegdeel (road section) table that describes landuses (see below).

Query BGT

The first step has been to query the BGT dataset. For that, we stored BGT data locally in a PostgreSQL spatial database (to do so an open framework, nlextract, exist).

We first retrieve the relevant ways using geometries and land type.

WITH subset AS (
    /* Create a subset of the data within the bounding box for further use */
SELECT
    bgt_functie,
    bgt_fysiekvoorkomen,
    relatievehoogteligging,
    geometrie_vlak as geom
FROM
    bgt.wegdeel a
WHERE
    ST_Intersects(a.geometrie_vlak, ST_MakeEnvelope(202463.2722222761, 502554.4648402039, 203467.14590116503, 503221.6040946483,28992)) -- fill in bounding box of the area of interest
AND
    bgt_functie IN ('voetpad','voetgangersgebied','voetpad op trap','parkeervlak','overweg') -- <-- Change this to the types you need. You can find all types on: https://imgeo.geostandaarden.nl/def/imgeo-object/wegdeel
AND
    relatievehoogteligging = 0
)

Then we use this subset and tesselate the terrain geometry to obtain triangles. This way, we get closer to an actual mesh just like navigation meshes.

,triangles AS (
SELECT
ST_MakePolygon(ST_ExteriorRing((ST_Dump( --This is a workaround to get polygons instead of a TIN, remove if a TIN is what you want
   ST_Tesselate( -- The actual triangulation per polygon
    ST_SimplifyVW( -- Simplify to avoid to reduce vertices in corners
     ST_CurveToLine(a.geom) -- Change bezier curves (original format in BGT) to geometries
    ,1)
   )
  )).geom)) geom
FROM subset a
)
SELECT * FROM triangles;

Using python and Geopandas, we can run the previous query:

import geopandas as gpd
import psycopg2

# enter your DB connection details
conn = psycopg2.connect(host=host, port='5432',dbname=dbname,user='postgres',password=password)

sql_pede = your_query # the above query

pedestrian = gpd.GeoDataFrame.from_postgis(sql_pede, conn, geom_col='geom' )
pedestrian = pedestrian.explode() #explode geometry collections
pedestrian

Output

8274 rows × 1 columns

Generate mesh

In order to be used in a game engine, our mesh coordinates need to be reprojected into a relative coordinates system where the bottom left corner will be considered as the origin. For that, we simply use a translation provided by the shapely library

from shapely import affinity
from shapely.geometry import Point


def repro(poly,pivot):
    local_poly = affinity.translate(poly, xoff=-pivot.x, yoff=-pivot.y, zoff=0.0)
    local_poly = local_poly.simplify(0.01, preserve_topology=False) #to ensure simple and valid geometries
    return local_poly

pivot_pnt = Point((202500, 502500)) #set the origin point
pedestrian['geom'] = pedestrian['geom'].apply(lambda x: repro(x,pivot_pnt)) #reproject each geometries

The only step left is now to actually produce the navigation mesh into a format recognisable by game engines. We use trimesh, a library for loading and using triangular meshes with an emphasis on watertight surfaces. Full doumentation can be found here.

import trimesh
import numpy as np

meshes = []
#for each triangle in the pedestrian table
for triangle in pedestrian.geom:
    if not triangle.is_empty: # empty triangle can appears, especially is a simplification has been ran

        # The following line creates triangles from a polygon. 
        # In meshes objects, triangle are represented in term of vertices and faces, the two being linked by IDs
        # In the present case, the polygons are already triangles so the vertices will simply repeat the one
        # of the polygons. However, we still call that function in order to get faces with a consistent labelling
        vertices, faces = trimesh.creation.triangulate_polygon(triangle, engine='earcut')

        # Here we had a Z value to our vertices.
        vertices = np.column_stack((vertices, np.zeros(len(vertices))))
        # Of course if the data were 3D, one could simply use the following:
        # vertices = np.array(triangle_3D.exterior)

        # The two following line are specific to the Unity Game Engine where
        # y and z axes are swaped.
        #vertices = vertices.dot([[-1,0,0],[0,1,0],[0,0,1]])
        #vertices[:,[1, 2]] = vertices[:,[2, 1]]

        # Generate mesh from polygon
        mesh = trimesh.Trimesh(vertices=vertices, faces=faces)
        meshes.append(mesh)

#Concatenate all meshes to form the final navigation mesh
mesh = trimesh.util.concatenate(meshes)

Export as OBJ file for game engine

Finally, we can ouput some 3D OBJ file using trimesh function like so:

obj = trimesh.exchange.obj.export_obj(
                                mesh,
                                include_normals=True,
                                include_color=False,
                                include_texture=False,
                                return_texture=False,
                                write_texture=False,
                                resolver=None,
                                digits=8,
                            )
with open("navmesh.obj", 'w') as file:
    file.write(obj)

Final words

Here we have it. A navigation mesh that can be directly used in game engine such as Unity fully generated from open source solutions. The feature is useful for city digital twin and AR apps.