Abstract: We propose a method to robustly and efficiently compute a navigation mesh for arbitrary and dynamic 3D environments based on curvature. This method addresses a number of known limitations in state-of-the-art techniques to produce navigation meshes that are tightly coupled to the original geometry, incorporate geometric details that are crucial for movement decisions and robustly handle complex surfaces. We integrate the method into a standard navigation and collision-avoidance system to simulate thousands of agents on complex 3D surfaces in real-time.