This article was published for PREMIUM members, available by subscription. You can join here in a minute or less. If you're already a member, log-in from the top right menu.

Premium Teaser

Navigation Mesh Generation via Voxelization and Watershed Partitioning

Mikko Mononen on March 3, 2009

Learn how to turn a complex poly soup of triangles representing your game world into a simple but accurate mesh representation that you can use for navigation. The topics include voxelizing the polygons efficiently, ways to partition the voxels into areas, then turning these areas into triangle or convex polygons. Mikko demonstrates some real-world examples of his algorithm at work, and discuss possible improvements and extensions.