SharpNav

A managed C#  Navigation mesh library








Robert Rouhani

what is it?


  • Generates navigation meshes from triangle soup
    • Dynamic objects in realtime
  • Store and retrieve navigation meshes from file
    • For static levels
  • Finds paths from one point on the mesh to another
    • Actors of different sizes
  • Local steering and crowd handling

Why?

  • Nothing good out there in C#:
    • CritterAI - Unity-focused, native deps, no dynamic objects
    • SharpSteer - only does local steering
  • Pure C# means lots of target platforms:
    • Windows, Linux, OS X
    • iOS, Android, Windows Phone
    • Xbox 360, PS3
  • Lots of XNA/MonoGame questions about AI in 3d
    • Most often answered with a link to the A* algorithm
    • Lots of wheel reinventing


Recast and Detour


Written by Mikko Mononen

Recast and detour

  • Written in platform-independent C++
  • Well designed
  • Fast

Recast and Detour

  • Hard to bind via P/Invoke (C++ API)
  • Some platforms don't like/allow dynamic linking
  • P/Invoke has overhead
  • The "Compile Once, Run Everywhere" dream

Porting

  • C# is pretty close to native performance
    • Excluding tight math loops
  • Besides triangle voxelization, not much math
    • If necessary, use Mono.SIMD  for SSE instructions
    • Parallelization is easy with C# 4.0's Parallel  class
  • Object pooling to avoid GC pausing if necessary

The Algorithm at 10,000 ft



Voxelization
Region Generation
Contour Generation
Convex Polygon Generation
Detailed Mesh Generation

Voxelization


Voxelization

  • Conservative voxelization
    • If any part of the triangle touches the voxel, it is included
  • Calculate the triangle's voxel-aligned bounding box
  • For each voxel column, clip the triangle to the column via the Sutherland-Hodgman algoirthm
  • Snap lowest and highest vertex in clipped column to voxel grid
  • All voxels in that range are included

Voxelization


Region Generation


Region Generation

  • Open vertical spans are determined from voxelized world
  • Determine neighbor accessibility for each span
  • Based on number of neighbors, a distance field from walls and other obstructions can be created
  • Use the watershed algorithm to flood-fill walkable regions
  • Do some extra filtering to clean up regions

Region Generation


Contour Generation


Contour Generation

  • "Walk" along the edge of all the regions to generate the region's contour (outline)
  • Region-region edges are simplified by removing all the vertices along the edge except the first and last ones
  • Region-null edges use the Douglas-Peucker algorithm and a maximum deviation variable for simplification

Contour generation


Convex Polygon Generation

  • Triangulate the contours
  • Merge triangles that form convex polygons together

Convex Polygon Generation


Detail Mesh Generation


Detail Mesh Generation

  • Add vertices to the hull of polygons that deviate too much from the original voxelized world
  • Perform Delaunay triangulation on the polygon
  • Sample internal parts of the triangulated polygon and add more vertices/triangulate again

Detail Mesh Generation





Demo

Thanks




Professor Moorthy
Professor Goldschmidt
Sean O'Sullivan
RCOS




Questions?

SharpNav

By Robert Rouhani

SharpNav

  • 4,143