NavMesh CalculateTriangulation() Produces Inaccurate Meshes

When using NavMesh.CalculateTriangulation(), the resulting mesh contains less vertices than the original navmesh. In the image below, mesh A is the output of the NavMesh.CalculateTriangulation() function. That mesh contains 4 vertices. Mesh B is the original mesh which was generated by Unity which clearly contains more than 4 vertices (i.e., because of the bend). Is there any way to get the raw navmesh geometry data that Unity is using under the hood or is this inaccurate approximation the only thing that is available (which is not very useful)?

 

i have same problem. are you solve it? if you solved, how you sovle it? ^^

 

For anyone who finds this thread, I think the reason it does this is because an agent on one vertex of figure A is expected to be able to walk in a straight line to any other point contained on figure A - It doesn't need to know about the slope change, it's controller will automatically step up that.

 

A shame, since the underlying real mesh is useful for AI purposes (topology, height). I stumbled across this when hunting bugs. Undocumented pain.

Now I need to calculate everything twice just so I can have the height data that's otherwise missing.

 

The actual structure is not volumetric. The real structure is potentially overlapping simple polygons built from voxelizing the input meshes, along with a compact height field map.

So the api actually does provide most of the useful information that the 'real' navmesh contains. Navmesh.CalculateTriangulation is not only not complete or accurate, it's misleading. It leads people to think there is actually some single volumetric mesh representation internally when there isn't.

 

Thanks for clarification. Should probably mention it in the manual under technical details. I've been gently pushing Unity to do more of that stuff. The devil really is in the details isn't it.

 

So how DO you get the volumetric mesh then? Combining the vertices of CalculateTriangles with SamplePosition on said navmesh to get the proper location of each vert?

 

I had forgotten about the detail mesh. There is actually a more detailed mesh that's separate from the navigation mesh. It's used for things like give me the closest point on the navmesh, but the navmesh is the only thing used for determining the actual paths.

So unless they just came up with a different way of building the detail information, which seems unlikely but I guess it's possible, there is a more detailed mesh available.

In any case to recreate it on your own, what's the use case? If it's purely for visuals then simply gathering up the input meshes and doing a combine would be one way. If for some reason you want to build up your own data on valid positions, then doing a SamplePosition at voxel height offsets, using the mesh they do provide to limit the range on the y axis, would give you something fairly close.

 

I'm asking it more out of curiosity than having an actual use for it myself, basically to ensure there's an answer for others here, for posterity's sake.
I assume this detail mesh can't be simply fetched from the navmesh and needs to be recreated if you need it?

 

So it's for related AI purposes (line of sight, height, cover and more). It's one of the most useful pieces of data ever and having access to the original height/detail mesh would be really useful without having to well, generate that myself.

 

Necro, but, there isn't a lot of (good )information about this stuff so just to clarify for anyone looking, NavMesh.CalculateTriangulation gives you the simplified mesh that is used for pathfinding. As far as I can tell the blue mesh is a more detailed mesh that contains more height information to place the agents, you can visualize all of the different data with this https://docs.unity3d.com/ScriptReference/AI.NavMeshEditorHelpers.DrawBuildDebug.html, I don't think you can actually access it though. It would be really nice if there were a "CalcuateTriangulationDetail".
A work around if to get a potentially more detailed result from "CalculateTriangulation" might be to have a very small tile size.

So TLDR the blue mesh in scene view is a more detailed mesh, CalculateTriangulation contains less height info.

 

Has anyone actually made a working solution for generating the detailed mesh that they could share? We have a lot of user-generated terrains in our game and are now trying to surface our AIs to players so they can make their own encounters and such, so we need to allow them to "bake" navmesh on their maps. We're trying to display this runtime-generated navmesh, but the simplified mesh is not really a good reference. Is there still no way to get the editor-style navmesh triangulation?

Thanks for any help!

 

HOWEVER, MY problem is more the triangulation. There are repeat vertices here. Anyone know how to condense it?

 

You have to do it by hand. Here's an algorithm I used to do it by checking whether vertices were very close to each other:

Code (CSharp):

1. public static void SimplifyMeshTopology(List<Vector3> vertices, List<int> indices, float weldThreshold)
2.         {
3.             Profiler.BeginSample("SimplifyNavMeshTopology");
4.             float startTime = Time.realtimeSinceStartup;
5.  
6.             int startingVerts = vertices.Count;
7.            
8.             // Put vertex indices into buckets based on their position
9.             Dictionary<Vector3Int, List<int>> vertexBuckets = new Dictionary<Vector3Int, List<int>>(vertices.Count);
10.             Dictionary<int, int> shiftedIndices = new Dictionary<int, int>(indices.Count);
11.             List<Vector3> uniqueVertices = new List<Vector3>();
12.             int weldThresholdMultiplier = Mathf.RoundToInt(1 / weldThreshold);
13.  
14.             // Heuristic for skipping indices that relies on the fact that the first time a vertex index appears on the indices array, it will always be the highest-numbered
15.             // index up to that point (e.g. if there's a 5 in the indices array, all the indices to the left of it are in the range [0, 4])
16.             int minRepeatedIndex = 0;
17.  
18.             for (int i = 0; i < vertices.Count; ++i)
19.             {
20.                 var currentVertex = Vector3Int.RoundToInt(vertices[i] * weldThresholdMultiplier);
21.                 if (vertexBuckets.TryGetValue(currentVertex, out var indexRefs))
22.                 {
23.                     indexRefs.Add(i);
24.                     shiftedIndices[i] = shiftedIndices[indexRefs[0]];
25.                     if (minRepeatedIndex == 0)
26.                     {
27.                         minRepeatedIndex = i;
28.                     }
29.                 }
30.                 else
31.                 {
32.                     indexRefs = new List<int> {i};
33.                     vertexBuckets.Add(currentVertex, indexRefs);
34.                     shiftedIndices[i] = uniqueVertices.Count;
35.                     uniqueVertices.Add(vertices[i]);
36.                 }
37.             }
38.            
39.             // Walk indices array and replace any repeated vertex indices with their corresponding unique one
40.             for (int i = 0; i < indices.Count; ++i)
41.             {
42.                 var currentIndex = indices[i];
43.                 if (currentIndex < minRepeatedIndex)
44.                 {
45.                     // Can't be a repeated index, skip.
46.                     continue;
47.                 }
48.                
49.                 indices[i] = shiftedIndices[currentIndex];
50.             }
51.            
52.             vertices.Clear();
53.             vertices.AddRange(uniqueVertices);
54.            
55.             Debug.Log($"Finished simplifying mesh topology. Time: {Time.realtimeSinceStartup - startTime}. initVerts: {startingVerts}, endVerts: {vertices.Count}");
56.             Profiler.EndSample();
57.         }