Welcome to Our Community

Welcome to our support forums. We hope you find the information you are looking for. Please note that some areas of these forums are not visible to guests, and require a forum account. Registration is free and easy, and we won't spam you or share your email address with anyone.

Sign Up
  1. This site uses cookies. By continuing to use this site, you are agreeing to our use of cookies. Learn More.

Finding the borders of a NavMesh

Discussion in 'Developer's Blog' started by StagPoint, Jan 11, 2015.

  1. StagPoint

    StagPoint Administrator
    Staff Member Verified Customer Beta Tester

    Joined:
    Dec 3, 2014
    Messages:
    20
    Likes Received:
    0
    I've been working on implementing the concepts from the paper Universal Power Law Governing Pedestrian Interactions in Unity recently, and of course any local navigation implementation needs to know about static obstacles. In my test cases I'm using Unity's built-in NavMesh for long-distance path generation, and "local navigation" for crowd interactions, etc.

    The built-in NavMesh has already determined which areas of the world are unwalkable, so it makes sense that we should be able to share that information with local navigation. Part of the solution is to determine the boundary edges of the existing NavMesh and treat those as static obstacles.

    For the curious, I figured I'd share the code I'm using to extract the boundary information from the NavMesh.

    The main code snippet is pasted below, and the attached .unitypackage contains all files needed. This demo component simply extracts the NavMesh boundary edges and draws them in yellow in the SceneView. Simply attach this component to an object in your scene to see it in action.

    find-navmesh-borders.png

    Code (C#):

    // Copyright (c) 2014-2015 StagPoint Consulting

    using System;
    using System.Collections;
    using System.Collections.Generic;

    using UnityEngine;

    /*
    * This component will render all NavMesh border edges in yellow in the SceneView.
    * It does this in order to demonstrate a fast and efficient way to determine all
    * outside border edges of a navmesh. This information may be useful for custom
    * navigation or terrain analysis, etc.
    */


    [ExecuteInEditMode]
    public class ShowNavmeshEdges : MonoBehaviour
    {

       private List<LineSegment> borderEdges = null;

       protected void OnEnable()
       {
         this.borderEdges = FindNavMeshBorders( NavMesh.CalculateTriangulation() );
       }

       protected void OnDrawGizmosSelected()
       {

         if( !this.enabled )
           return;

         Gizmos.color = Color.yellow;

         for( int i = 0; i < this.borderEdges.Count; i++ )
         {
           var edge = this.borderEdges[ i ];
           Gizmos.DrawLine( edge.start, edge.end );
         }

       }

       private static List<LineSegment> FindNavMeshBorders( NavMeshTriangulation mesh )
       {

         Vector3[] verts = null;
         int[] triangles = null;

         weldVertices( mesh, 0.01f, 2f, out verts, out triangles );

         var map = new Dictionary<uint, int>();

         Action<ushort, ushort> processEdge = ( a, b ) =>
         {

           if( a > b )
           {
             var temp = b;
             b = a;
             a = temp;
           }

           uint key = ( (uint)a << 16 ) | (uint)b;

           if( !map.ContainsKey( key ) )
             map[ key ] = 1;
           else
             map[ key ] += 1;

         };

         for( int i = 0; i < triangles.Length; i += 3 )
         {

           var a = (ushort)triangles[ i + 0 ];
           var b = (ushort)triangles[ i + 1 ];
           var c = (ushort)triangles[ i + 2 ];

           processEdge( a, b );
           processEdge( b, c );
           processEdge( c, a );

         }

         var borderEdges = new List<LineSegment>();

        foreach( var key in map.Keys )
         {

           var count = map[ key ];
           if( count != 1 )
             continue;

           var a = ( key >> 16 );
           var b = ( key & 0xFFFF );
           var line = new LineSegment( verts[ a ], verts[ b ] );

           borderEdges.Add( line );

         }

         return borderEdges;

       }

       private static void weldVertices( NavMeshTriangulation mesh, float threshold, float bucketStep, out Vector3[] vertices, out int[] indices )
       {

         // This code was adapted from http://answers.unity3d.com/questions/228841/dynamically-combine-verticies-that-share-the-same.html

         Vector3[] oldVertices = mesh.vertices;
         Vector3[] newVertices = new Vector3[ oldVertices.Length ];
         int[] old2new = new int[ oldVertices.Length ];
         int newSize = 0;

         // Find AABB
         Vector3 min = new Vector3( float.MaxValue, float.MaxValue, float.MaxValue );
         Vector3 max = new Vector3( float.MinValue, float.MinValue, float.MinValue );
         for( int i = 0; i < oldVertices.Length; i++ )
         {
           if( oldVertices[ i ].x < min.x )
             min.x = oldVertices[ i ].x;
           if( oldVertices[ i ].y < min.y )
             min.y = oldVertices[ i ].y;
           if( oldVertices[ i ].z < min.z )
             min.z = oldVertices[ i ].z;
           if( oldVertices[ i ].x > max.x )
             max.x = oldVertices[ i ].x;
           if( oldVertices[ i ].y > max.y )
             max.y = oldVertices[ i ].y;
           if( oldVertices[ i ].z > max.z )
             max.z = oldVertices[ i ].z;
         }

         // Make cubic buckets, each with dimensions "bucketStep"
         int bucketSizeX = Mathf.FloorToInt( ( max.x - min.x ) / bucketStep ) + 1;
         int bucketSizeY = Mathf.FloorToInt( ( max.y - min.y ) / bucketStep ) + 1;
         int bucketSizeZ = Mathf.FloorToInt( ( max.z - min.z ) / bucketStep ) + 1;
         List<int>[ , , ] buckets = new List<int>[ bucketSizeX, bucketSizeY, bucketSizeZ ];

         // Make new vertices
         for( int i = 0; i < oldVertices.Length; i++ )
         {

           // Determine which bucket it belongs to
           int x = Mathf.FloorToInt( ( oldVertices[ i ].x - min.x ) / bucketStep );
           int y = Mathf.FloorToInt( ( oldVertices[ i ].y - min.y ) / bucketStep );
           int z = Mathf.FloorToInt( ( oldVertices[ i ].z - min.z ) / bucketStep );

           // Check to see if it's already been added
           if( buckets[ x, y, z ] == null )
             buckets[ x, y, z ] = new List<int>(); // Make buckets lazily

           for( int j = 0; j < buckets[ x, y, z ].Count; j++ )
           {
             Vector3 to = newVertices[ buckets[ x, y, z ][ j ] ] - oldVertices[ i ];
             if( Vector3.SqrMagnitude( to ) < threshold )
             {
               old2new[ i ] = buckets[ x, y, z ][ j ];
               goto skip; // Skip to next old vertex if this one is already there
             }
           }

           // Add new vertex
           newVertices[ newSize ] = oldVertices[ i ];
           buckets[ x, y, z ].Add( newSize );
           old2new[ i ] = newSize;
           newSize++;

    skip:
           ;

         }

         // Make new triangles
         int[] oldTris = mesh.indices;
         indices = new int[ oldTris.Length ];
         for( int i = 0; i < oldTris.Length; i++ )
         {
           indices[ i ] = old2new[ oldTris[ i ] ];
         }

         vertices = new Vector3[ newSize ];
         for( int i = 0; i < newSize; i++ )
         {
           vertices[ i ] = newVertices[ i ];
         }

       }

    }
     

    Attached Files:

    #1
  2. StagPoint

    StagPoint Administrator
    Staff Member Verified Customer Beta Tester

    Joined:
    Dec 3, 2014
    Messages:
    20
    Likes Received:
    0
    Addendum: In some cases, you will want to make sure that the lines do not have their start and end positions flipped, so that you can correctly determine the line's "normal". The above code sample will flip some of the boundary edges. If that is not desirable, use the version of FindNavMeshBorders shown below, which will correctly maintain the original direction of the lines.

    As you can see from this snapshot, this version will keep the border edge's "normals" pointing back in toward the interior of the NavMesh:

    find-navmesh-borders-2.png

    Code (C#):
    private static ListEx<LineSegment> FindNavMeshBorders( NavMeshTriangulation mesh )
    {

       Vector3[] verts = null;
       int[] triangles = null;

       weldVertices( mesh, 0.01f, 2f, out verts, out triangles );

       var map = new Dictionary<uint, int>();
       var reversed = new Dictionary<uint, bool>();

       Action<ushort, ushort> processEdge = ( a, b ) =>
       {

         var swap = ( a > b );
         if( swap )
         {
           var temp = b;
           b = a;
           a = temp;
         }

         uint key = ( (uint)a << 16 ) | (uint)b;

         if( swap )
         {
           reversed[ key ] = true;
         }

         if( !map.ContainsKey( key ) )
           map[ key ] = 1;
         else
           map[ key ] += 1;

       };

       for( int i = 0; i < triangles.Length; i += 3 )
       {

         var a = (ushort)triangles[ i + 0 ];
         var b = (ushort)triangles[ i + 1 ];
         var c = (ushort)triangles[ i + 2 ];

         processEdge( a, b );
         processEdge( b, c );
         processEdge( c, a );

       }

       var borderEdges = new ListEx<LineSegment>();

       foreach( var key in map.Keys )
       {

         var count = map[ key ];
         if( count != 1 )
           continue;

         var a = ( key >> 16 );
         var b = ( key & 0xFFFF );
         var line = new LineSegment( verts[ a ], verts[ b ] );

         var isReversed = false;
         if( reversed.TryGetValue( key, out isReversed ) && isReversed )
         {
           line = new LineSegment( verts[ b ], verts[ a ] );
         }

         borderEdges.Add( line );

       }

       return borderEdges;

    }
     
    #2

Share This Page