Problems with PolyMeshDetail

[lsteffens]

Hi, first thanks for your work on trying to bring navmesh generation to the c# sharp world. I hope you continue converting recast (and detour) to managed code including all the neat features of the c++ code like dynamic obstacles.

Now to my problems (I currently only use the recast part as I have my own working navmesh ai):

1. There are some problems with (at least) the generation of the mesh detail. Some polygons are not triangulated correctly (e.g. missing triangles in the detail mesh). The problem is not so visible if VertsPerPoly is set to 3 for generating the PolyMesh and then creating the PolyDetailMesh from there. But it's still there on complexer source meshes (I can send you one ... (1)).
2. An exception may be thrown in GetHeightData (in PolyMeshDetail.cs) as "compactField.Cells[ay * compactField.Width + ax]" gets out of range if ay (or ax) gets negative - and it sometimes will. I get around this error by checking if the calculated array position fits inside the array - but I think thats not the source of the problem but only a workaround to hide it (a bit) ;-)

I can send you a simple *.obj file (and a more complex one (1)) if you want to check the code and the problems I descibed.

BTW: both obj files have no problems in the original c++ version ...

Keep up the good work, Lars

[Robmaister]

Yeah, the triangulation issue with PolyMeshDetail is one of the last blocking issues before a 1.0 release, sorry about that! It's just a bit difficult to debug. I released a 0.9 version to get feedback and bugfixes like this.

As for 2, I believe that's related to the same bug. If you could email me the .obj files or something, that would be great, as it would give me more cases to test for.

Thanks for helping me out! :smile:

[lsteffens]

I've attached the two obj files (in one zip) - a simple one with a small "building" and a more complex one with terrain containing this building (+ some "tree" boxes).

Those are actually my collision meshes for a level so they are quite "lightweight".

You should change the agent height to 1.6 and agent radius to 0.3 to get through the gate ;-) - and maybe do some renaming in the UI as e.g. erode heightfield is agent radius - maybe just stick to the UI of the original c++ version which is very easy to understand.

If you then generate the navmesh in your SharpNav.Examples you should easily spot the missing triangles (in and out of the small building and some in the terrain).

Setting VertsPerPoly to 3 gives a better triangulation - but not perfect ...

  Another issue I found was that marking triangles above a certain slope does not work correctly. I use XNA so this maybe a issue specific for XNA Vector3.

changing ... (in MarkAboveSlope) return Vector3.Dot(n, Vector3.UnitY) <= angle; with return Math.Abs(Hope.Helper.HopeHelper.AngleBetweenVectors3(n, Vector3.UnitY)) >= angle;

and using this code snippet:

public static double AngleBetweenVectors3(Vector3 v1, Vector3 v2) {      return ((v1.X - v2.X) > 0 ? -1 : 1) * (float)Math.Acos((double)Vector3.Dot(Vector3.Normalize(v1), Vector3.Normalize(v2))); }

Gives me a working solution for the slope problem ... maybe it helps you.

You can certainly change the signed angle version to unsigned by not multipying by -1 ...

I'm happy to help you out clearing some bugs ... let me know if you need some specific testing.

Lars

[Robmaister]

Yeah, I really quickly used the dot product assuming it would be fine 0 < theta < pi/2 (small angle approximation). I'll probably switch to either the acos method or this atan2 method:

angle = atan2(norm(cross(a,b)),dot(a,b));

which should handle more edge cases. Thanks for pointing that out, I was eventually going to change it.

[Robmaister]

The bug that caused a lot of issues with PolyMeshDetail was fixed prior to the 1.0.0-alpha.1 release, in c36b8c931e4b736ca50a6e0d466ac9dc71334537.

It will still cause issues if you crank up the amount of detail you're adding, it'll cause some issues (shouldn't ever throw an exception though). @lsteffens feel free to do as much testing as you want with this pre-release and let me know if you find any bugs. A lot of the public API is going to change between now and the final 1.0.0 FYI.

[lsteffens]

Hi Robert,

I quickly tested the current alpha release by downloading the current alpha.1 sourcecode and compiling it mit OpenTK option.

The simple test file (obj) I send you was used to test the navmesh generation.

I set the settings.AgentWidth = 0.3f (should be named radius??) and settings.AgentHeight = 1.5f - BTW: the agent size settings should be made available in the example UI to make the testing easier.

Everything else is set to the default values in the example UI.

When you generate the navmesh you can see that polygons (PolyDetail) are missing around the room of the test scene - the contour Looks quite ok.

If you then set the cell size to 0.1 and the cell height to 0.1 you get a better nav mesh. but still polys missing before the entrance to the room.

To sum things up I would say that the nav mesh generation is much more robust than the first version I tested - I got no exceptions - good 😉

The contours view looks quite promissing and ok to me, but the polygonisation is not very consistent - with the original recast I can generate the navmesh from any of my test mesh objects with no problems at all.

BTW: I noticed that you left out XNA from the possible compile configurations - I hope this get’s back someday because this makes it harder for me to integrate nav mesh generation inside my XNA game/editor source.

Let me know if you need further assistence with testing.

Thanks,

Lars

Von: Robert Rouhani Gesendet: ‎Dienstag‎, ‎6‎. ‎Januar‎ ‎2015 ‎14‎:‎08 An: Robmaister/SharpNav Cc: lsteffens

The bug that caused a lot of issues with PolyMeshDetail was fixed prior to the 1.0.0-alpha.1 release, in c36b8c9.

It will still cause issues if you crank up the amount of detail you're adding, it'll cause some issues (shouldn't ever throw an exception though). @lsteffens feel free to do as much testing as you want with this pre-release and let me know if you find any bugs. A lot of the public API is going to change between now and the final 1.0.0 FYI.

— Reply to this email directly or view it on GitHub.

[Robmaister]

Thanks for the very quick response!

I need to do some renaming/refactoring of navmesh settings. I originally used the Recast names directly in the examples UI. I then pulled all those settings out into a separate class that I could pass to every step of the generation process. Those values were renamed, but all map to something on the UI.

I'll change AgentWidth to AgentRadius.

I'm very tempted to ditch Recast's implementation of triangulation/Delaunay hull generation and implement my own in C# since they implement their own kind of hashtable and I'm trying to wedge a Dictionary in there with as little modification as possible. I'm going to look more into fixing the existing code first, though.

The code base for everything up through contours should be final (or pretty damn close to final), though!

As for XNA, I had just assumed that anyone still using it would migrate over to MonoGame since XNA has been dead for about 2 years now. Additionally, it appears like it's going to be very difficult to get working on CI (impossible on Travis since it's linux, just now setting up AppVeyor but couldn't find anything about XNA) because it's not available as a single .dll or a NuGet package or anything. At it's existing state, I would be putting in a lot of effort to make something that would only be useful to a small number of people. That number would also be constantly shrinking.

So in short I'd recommend moving to MonoGame. It uses the Microsoft.Xna.Framework namespace too (almost API-compatible too), supports way more platforms than XNA, and is being actively developed.

I'll do some more testing with the .obj level you sent me as well.

[Robmaister]

Interesting, that polygon is breaking at the PolyMesh stage. There's also a bunch of dangling faces during PolyMeshDetail generation.

Also the agent width is in the UI as Erode Radius.

The one region that loops around like that is a great test case, though! I'll incorporate a contour like that into a unit test at some point.

[Robmaister]

Dangling faces, PolyMesh bugs, etc. all fixed.

If you still want XNA integration, it should be possible by changing an assembly reference with the MonoGame configuration. I might create a separate build configuration and NuGet package, but I won't be able to test it on Travis CI and Appveyor.