ikpil / dotrecast Goto Github PK
View Code? Open in Web Editor NEWDotRecast - a port of Recast & Detour, Industry-standard navigation mesh toolset for .NET, C#, Unity3D, games, servers
License: zlib License
DotRecast - a port of Recast & Detour, Industry-standard navigation mesh toolset for .NET, C#, Unity3D, games, servers
License: zlib License
Rider keeps telling me that Small Object Heap allocation is high for the DtCrowd.Update method.
Where the Update method is called every 0.3...
On the pictures above the compiler is complaining about 200mb-ish, but I've seen it complaining about almost 800mb. Do you have any idea of what could it be?
I've been investigating problems with incorrect pathing, e.g.
After some digging, I've found that the root cause is the logic that removes vertices on tile borders while building polymeshes.
There is a parameter that controls the max edge length while tracing contours, it correctly creates 'small' areas:
When later poly mesh is built, it builds a triangulation for each contour. However, there is a piece of code (see RcMeshs.BuildPolyMesh) that marks vertices on the tile borders for removal:
if ((cont.verts[v + 3] & RC_BORDER_VERTEX) != 0)
{
// This vertex should be removed.
vflags[indices[j]] = 1;
}
As a result, recast creates a huge polygons on tile borders:
Presumably this is done for better tile stitching? However, it creates problems for pathfinding (since the pathfinding considers edge midpoints, it thinks that going 'around' this polygon is 'shorter' than crossing long edge midpoint).
Removing this vertex removal bit fixes the triangulation (and consequently pathfinding), and doesn't seem to break stitching in my limited testing so far:
However, I don't quite understand all implications. I suspect this part is directly ported from recast?
So when creating a convex volume, it will crash the program if you accidentally only give 3 points for the volume, is this intended behavior, and if so could if instead just catch the exception instead of crash the program? P.S. I made a new issue for this so it can be closed when acted on, separate from our ongoing discussion
When using Temp Obstacles in the Demo I am able to generate a correct path when leveraging a path for individual agents (Test Navmesh).
Crowd Control seems to ignore Temp Obstacles as shown by the path generated below and walks right through it.
Or is there a setting I am misconfiguring for Crowd Control for it to ignore Temp Obstacles?.
This causes the entire list to be copied over. It's pretty slow, if we going to do this every game cycle.
if (s.Count == TIMING_SAMPLES)
{
s.RemoveAt(0);
}
This is Linq call and will cause memory allocation. Would be nice to avoid that, especially in a code that supposed to measure performance.
_executionTimings[name] = (long)s.Average();
I would replace List with some sort of cyclic buffer to avoid removing elements and replace Linq query with foreach cycle or even SIMD.
Hey, first I want to thank you for the great job you are doing, you even converted the demo tool!
I would like to know if you have any parameters related to performance with the original or did you not perform any yet?
There is a another project too, for performance reasons the guy decided to keep pointers (unsafe) and others things, but it's no longer an active project.
https://github.com/ryancheung/RecastSharp/tree/main
Cheers!
Hi!
I was just searching around to see if anyone had ported Recast/Detour to C# and came upon this project, which is looking great so far.
I just wanted to check if you're planning to publish it on NuGet for easier consumption?
Good thing, I have been searching for the C # version online for a long time. Thank you, moderator
Hey!
I've been using this mainly with Unity and it seems the X axis is inverted in comparison to Unity's coordinates. I have to do something like this every time I sent the position to my clients:
public static SVector3 toSVector3(this RcVec3f v, RcVec3f mapSize) => new() { X = mapSize.X - v.X, Y = v.Y, Z = v.Z };
Is there any way you can think of to invert this so we can avoid these conversions?
Hi,
I'm playing around with OpenGL and trying to generate a navMesh with DotRecast. I'm a bit stuck because the detail mesh is always null
after mesh generation.
I'm using a left hand coord system:
Im generating terrain mesh from a hightmap. The mesh is squared with a length of 800.0f (-400.0f to 400.0f) and a height between 0.0f and 40.0f. It has a grid of 256x256 cells divided into two triangular polygons each.
I'm converting my mesh to a right hand system before I pass it to the Geo provider:
public static class MeshConverter
{
public static MeshData<VertexPositionNormalTexture, uint> ConvertMeshToRightHandSystem(this MeshData<VertexPositionNormalTexture, uint> meshData)
{
var convertedVertices = new VertexPositionNormalTexture[meshData.Vertices.Length];
for (int i = 0; i < meshData.Vertices.Length; i++)
{
var vertex = meshData.Vertices[i];
// Swap X and Z for position and normal to convert the mesh for Recast
var newPosition = new Vector3D<float>(vertex.Position.Z, vertex.Position.Y, vertex.Position.X);
var newNormal = new Vector3D<float>(vertex.Normal.Z, vertex.Normal.Y, vertex.Normal.X);
convertedVertices[i] = new VertexPositionNormalTexture(newPosition, newNormal, vertex.TexCoords);
}
// The order of indices might need to be adjusted to correct the winding order.
// Since we have swapped axes, the orientation of triangles could be affected.
// For this specific case (just axis swap), it might not be necessary, but it should be tested.
var convertedIndices = new uint[meshData.Indices.Length];
for (int i = 0; i < meshData.Indices.Length; i += 3)
{
// Directly copy the indices as no direct impact on winding order is expected
convertedIndices[i] = meshData.Indices[i];
convertedIndices[i + 1] = meshData.Indices[i + 1];
convertedIndices[i + 2] = meshData.Indices[i + 2];
}
return new MeshData<VertexPositionNormalTexture, uint>(convertedVertices, convertedIndices);
}
}
And afterwards I try to generate the nav mesh:
var meshInRightHandSystem = mesh.ConvertMeshToRightHandSystem();
float[] vertexArray = meshInRightHandSystem.Vertices.SelectMany(v => new[] { v.Position.X, v.Position.Y, v.Position.Z }).ToArray();
int[] indexArray = meshInRightHandSystem.Indices.Select(i => (int)i).ToArray();
var geomProvider = new DemoInputGeomProvider(vertexArray, indexArray);
var partitionType = RcPartition.WATERSHED;
float tileSize = 800 / 256; // Die Größe eines Tiles, basierend auf der Größe deines Terrains und der Anzahl der Tiles
float cellSize = tileSize / 2; // Wie detailliert jedes Voxel sein sollte, kleinere Werte führen zu detaillierteren NavMeshes
float cellHeight = 0.2f; // Die Höhe jedes Voxels, kleinere Werte führen zu einem detaillierteren NavMesh
float agentHeight = 2.0f; // Die Höhe des Agenten, der das NavMesh nutzen wird
float agentRadius = 0.6f; // Der Radius des Agenten, der das NavMesh nutzen wird
float agentMaxClimb = 0.9f; // Die maximale Steigung, die der Agent überwinden kann
float agentMaxSlope = 45.0f; // Der maximale Neigungswinkel, den der Agent noch begehen kann
int regionMinSize = 8; // Die minimale Größe einer Region, die noch als begehbar betrachtet wird (in Voxeln)
int regionMergeSize = 20; // Die minimale Größe von Regionen, die zusammengeführt werden sollen (in Voxeln)
float edgeMaxLen = 12.0f; // Die maximale Länge der Kanten des NavMeshes (längere Kanten werden aufgeteilt)
float edgeMaxError = 1.3f; // Der maximale Fehler von Kantenverläufen im NavMesh
int vertsPerPoly = 6; // Die maximale Anzahl von Vertices pro Polygon
float detailSampleDist = 6.0f; // Der Abstand für die Detail-Mesh-Sampling, größer als 0 aktiviert das Detail-Mesh
float detailSampleMaxError = 1.0f; // Der maximale Sampling-Fehler für das Detail-Mesh
RcConfig recastConfig = new RcConfig(
true,
(int)tileSize,
(int)tileSize,
borderSize: 0,
partitionType,
cellSize,
cellHeight,
agentMaxSlope,
agentHeight,
agentRadius,
agentMaxClimb,
regionMinSize,
regionMergeSize,
edgeMaxLen,
edgeMaxError,
vertsPerPoly,
detailSampleDist,
detailSampleMaxError,
true,
true,
true,
SampleAreaModifications.SAMPLE_AREAMOD_GROUND,
true);
var recastBuilderConfig = new RcBuilderConfig(recastConfig, geomProvider.GetMeshBoundsMin(), geomProvider.GetMeshBoundsMax());
RcBuilder rcBuilder = new RcBuilder();
RcBuilderResult rcResult = rcBuilder.Build(geomProvider, recastBuilderConfig);
RcPolyMesh polyMesh = rcResult.GetMesh();
for (int i = 0; i < polyMesh.npolys; ++i)
{
polyMesh.flags[i] = 1;
}
RcPolyMeshDetail polyMeshDetail = rcResult.GetMeshDetail();
The poly mesh detail is always null
. What I am doing wrong?
I was messing around with the library and wanted to test a larger scene for an RTS example using a default cude in Blender that I scaled to 500x1x500.
I definitely expected a regression in performance but are these allocations correct or is there a known issue with the navmesh generatioon?
I collected some stacktraces of the memory from DotMemory here:
Single
s being allocated, mostly from DividePoly
.
System.Single[]
Objects : n/a
Bytes : 1603298776
>99.9% DividePoly • 1.49 GB / 1.49 GB • DotRecast.Recast.RcRasterizations.DividePoly(Single[], Int32, Int32, Int32, Int32, Int32, Int32, Single, Int32)
>99.9% RasterizeTri • 1.49 GB / - • DotRecast.Recast.RcRasterizations.RasterizeTri(Single[], Int32, Int32, Int32, Int32, RcHeightfield, RcVec3f, RcVec3f, Single, Single, Single, Int32)
>99.9% RasterizeTriangles • 1.49 GB / - • DotRecast.Recast.RcRasterizations.RasterizeTriangles(RcContext, Single[], Int32[], Int32[], Int32, RcHeightfield, Int32)
>99.9% BuildSolidHeightfield • 1.49 GB / - • DotRecast.Recast.RcVoxelizations.BuildSolidHeightfield(RcContext, IInputGeomProvider, RcBuilderConfig)
>99.9% Build • 1.49 GB / - • DotRecast.Recast.RcBuilder.Build(IInputGeomProvider, RcBuilderConfig)
>99.9% BuildRecastResult • 1.49 GB / - • DotRecast.Recast.Toolset.Builder.SoloNavMeshBuilder.BuildRecastResult(DemoInputGeomProvider, RcConfig)
>99.9% Build • 1.49 GB / - • DotRecast.Recast.Toolset.Builder.SoloNavMeshBuilder.Build(DemoInputGeomProvider, RcPartition, Single, Single, Single, Single, Single, Single, Int32, Int32, Single, Single, Int32, Single, Single, Boolean, Boolean, Boolean)
>99.9% Build • 1.49 GB / - • DotRecast.Recast.Toolset.Builder.SoloNavMeshBuilder.Build(DemoInputGeomProvider, RcNavMeshBuildSettings)
>99.9% OnNavMeshBuildBegan • 1.49 GB / - • DotRecast.Recast.Demo.RecastDemo.OnNavMeshBuildBegan(NavMeshBuildBeganEvent)
>99.9% OnMessage • 1.49 GB / - • DotRecast.Recast.Demo.RecastDemo.OnMessage(IRecastDemoMessage)
>99.9% OnWindowUpdate • 1.49 GB / - • DotRecast.Recast.Demo.RecastDemo.OnWindowUpdate(Double)
>99.9% <Run>b__0 • 1.49 GB / - • Silk.NET.Windowing.WindowExtensions+<>c__DisplayClass2_0.<Run>b__0()
>99.9% Run • 1.49 GB / - • Silk.NET.Windowing.Internals.ViewImplementationBase.Run(Action)
>99.9% Run • 1.49 GB / - • Silk.NET.Windowing.WindowExtensions.Run(IView)
>99.9% Run • 1.49 GB / - • DotRecast.Recast.Demo.RecastDemo.Run()
>99.9% StartDemo • 1.49 GB / - • DotRecast.Recast.Demo.Program.StartDemo()
>99.9% Main • 1.49 GB / - • DotRecast.Recast.Demo.Program.Main(String[])
► >99.9% [AllThreadsRoot] • 1.49 GB / - • [AllThreadsRoot]
#stacktrace
RcSpan
s being allocated by AddSpan
DotRecast.Recast.RcSpan
Objects : n/a
Bytes : 890084272
100% AddSpan • 848.85 MB / 848.85 MB • DotRecast.Recast.RcRasterizations.AddSpan(RcHeightfield, Int32, Int32, Int32, Int32, Int32, Int32)
100% RasterizeTri • 848.85 MB / - • DotRecast.Recast.RcRasterizations.RasterizeTri(Single[], Int32, Int32, Int32, Int32, RcHeightfield, RcVec3f, RcVec3f, Single, Single, Single, Int32)
100% RasterizeTriangles • 848.85 MB / - • DotRecast.Recast.RcRasterizations.RasterizeTriangles(RcContext, Single[], Int32[], Int32[], Int32, RcHeightfield, Int32)
100% BuildSolidHeightfield • 848.85 MB / - • DotRecast.Recast.RcVoxelizations.BuildSolidHeightfield(RcContext, IInputGeomProvider, RcBuilderConfig)
100% Build • 848.85 MB / - • DotRecast.Recast.RcBuilder.Build(IInputGeomProvider, RcBuilderConfig)
100% BuildRecastResult • 848.85 MB / - • DotRecast.Recast.Toolset.Builder.SoloNavMeshBuilder.BuildRecastResult(DemoInputGeomProvider, RcConfig)
100% Build • 848.85 MB / - • DotRecast.Recast.Toolset.Builder.SoloNavMeshBuilder.Build(DemoInputGeomProvider, RcPartition, Single, Single, Single, Single, Single, Single, Int32, Int32, Single, Single, Int32, Single, Single, Boolean, Boolean, Boolean)
100% Build • 848.85 MB / - • DotRecast.Recast.Toolset.Builder.SoloNavMeshBuilder.Build(DemoInputGeomProvider, RcNavMeshBuildSettings)
100% OnNavMeshBuildBegan • 848.85 MB / - • DotRecast.Recast.Demo.RecastDemo.OnNavMeshBuildBegan(NavMeshBuildBeganEvent)
100% OnMessage • 848.85 MB / - • DotRecast.Recast.Demo.RecastDemo.OnMessage(IRecastDemoMessage)
100% OnWindowUpdate • 848.85 MB / - • DotRecast.Recast.Demo.RecastDemo.OnWindowUpdate(Double)
100% <Run>b__0 • 848.85 MB / - • Silk.NET.Windowing.WindowExtensions+<>c__DisplayClass2_0.<Run>b__0()
100% Run • 848.85 MB / - • Silk.NET.Windowing.Internals.ViewImplementationBase.Run(Action)
100% Run • 848.85 MB / - • Silk.NET.Windowing.WindowExtensions.Run(IView)
100% Run • 848.85 MB / - • DotRecast.Recast.Demo.RecastDemo.Run()
100% StartDemo • 848.85 MB / - • DotRecast.Recast.Demo.Program.StartDemo()
100% Main • 848.85 MB / - • DotRecast.Recast.Demo.Program.Main(String[])
► 100% [AllThreadsRoot] • 848.85 MB / - • [AllThreadsRoot]
#stacktrace
There are a couple more that are also allocating a couple hundred MBs but these 2 are by far the most agressive it seems.
I'm in the memory profiler today checking in on my program and was surprised by the number of objects that DotRecast is creating and keeping live for what might be considered a relatively small scene -
Here you'll notice we have 500k live instances of RcSpan -
Is there any change we can make to DotRecast or our usage to reduce the object count footprint here? Maybe a different internal representation or perhaps a posteri pruning? Or perhaps there's a reference from the mesh construction process I can let go of? I currently keep a reference to RcBuilderResult so I can draw the above debug lines. Should I not hold on to that? If so, would there be a better way to draw debug info for the nav mesh than using RcBuilderResult? If not, can I prune RcBuilderResult somehow?
Since we're dealing with realtime games, we'd like to keep the GC sweep phase as cheap as possible.
Lastly, here's the related issue I filed locally -
Thank you for your greatly helpful project - it has already saved us tremendous amounts of time and effort!
my code like this:
var indexs = new List<int>(){ 7, 0, 1, 2, 3, 4, 6, 7, 1, 2, 4, 5, 5, 6, 1, 1, 2, 5}; var verts = new List<float>(){17307.352, -13128.241, 4000, 17307.352, 5071.7583, 4000, -8892.649, 5071.7583, 4000, -8892.649, -8428.24, 4000, -4592.6494, -8428.24, 4000, -4592.6494, -928.24164, 4000, 8307.351, -928.24164, 4000, 8307.351, -13128.241, 4000, 17307.352, -13128.241, 4000 }; SimpleInputGeomProvider geomProvider = new(verts, indexs); RcVec3f bmin = geomProvider.GetMeshBoundsMin(); RcVec3f bmax = geomProvider.GetMeshBoundsMax(); RcContext m_ctx = new(); RcConfig cfg = new( RcPartition.WATERSHED, m_cellSize, m_cellHeight, m_agentMaxSlope, m_agentHeight, m_agentRadius, m_agentMaxClimb, m_regionMinSize, m_regionMergeSize, m_edgeMaxLen, m_edgeMaxError, m_vertsPerPoly, m_detailSampleDist, m_detailSampleMaxError, true, true, true, new RcAreaModification(0x2, 0x07), true); RcBuilderConfig bcfg = new(cfg, bmin, bmax); RcBuilder rcBuilder = new(); RcBuilderResult rcResult = rcBuilder.Build(geomProvider, bcfg);
it throws System.ArgumentException:“'0' cannot be greater than -1.”
I don't know how it caused it?
First of all thanks for the port.
I refactored to use Vector3 instead of RcVec3f and the performance I had was like 4x faster on DtCrowd.
Parallel also improved a lot.
Why is RcVec3f being used instead?
Hi, I want to use DotRecast in a test project I am building, but purely on my (dotnet, C#) server. I am using Unity as my GameEngine and now I was wondering if there is an example project to export the data from Unity and import it into DotRecast.
What I have:
What I need help with:
program = _gl.CreateProgram();
uint vert_shdr = _gl.CreateShader(GLEnum.VertexShader);
_gl.ShaderSource(vert_shdr, vertex_shader);
_gl.CompileShader(vert_shdr);
_gl.GetShader(vert_shdr, GLEnum.CompileStatus, out var status);
if (status != (int)GLEnum.True)
{
throw new InvalidOperationException();
}
So I've got this error: rcBuildContours: Bad outline for region 6, contour simplification is likely too aggressive.
This is how raw vs simplified looks:
So yeah, the simplified polygon is self-intersecting, which is a problem. Looking at the code, however, I see this bit (rcContours.SimplifyContour):
I finally have a mostly working nav mesh result. The main issue seems to be that the navmesh is being generated on the ceiling of the object as seen in the image below.
Each cube in the image represents a point on the nav mesh.
Is there a setting I am missing to have it generate on the opposite Y axis?
In original recast nav demo, i can select "Temp obstacles" and create/save tile cache for future using. DotRecast, seems, has not that option in demo, but i see, that working with tile cache is present in the tests. Is DotRecast tile cache reader binary compatible with saved tile cache, generated by original recast? When i try to use reader, it crashes with exception "Could not allocate a tile".
Hey,
Are there any examples for Unity 3D? What projects are really needed for Unity? And to generate navmesh use unity itself to generate?
Cheers!
Would it even be possible to update the demo to make it more of a tool, in the sense where we could click to select single polygons in our generated navmesh and delete them, and if even possible an option to add or paint in new polygons?
on a 4k screen its really hard to read as the ui doesnt scale, can you please make it scale or the very least put in a 4k ui option
You can post your screenshots here!
I am finally working on integrating this into Stride3d and I am having trouble actually generating the mesh for debugging purposes.
As far as I can tell in your demos for Unity the methods used only require that the vertices are provided as far as I understand it. in the Unity example I see you are generating per poly but in my generated mesh some poly data has more than 3 points depending on the tile.
I didnt realize DrawAAConvexPolygon
was for drawing an arrow not the poly mesh.
In the code above you can see one of the polys has 24 verts or 8 Vector3 points. am I just meant to try and make my own indices or is there a way to get that data from the navmesh?
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.