Friday, October 23, 2009

Recast Detail Mesh Fixes

I just update the detail mesh generation code in SVN, which should improve the possible bad cases of the detail mesh generation.

One case where the detail mesh generation failed previously was the Delaunay triangulation which is used to generate the triangulation of per polygon detail surface mesh. This should be now fixed.

Next time around I will design a system which will dodge any kind of triangulation.

The algorithm is a little slower than the previous one and has worse big O behavior too. So large areas will take longer time to compute. If you have really horrible performance, I suggest using the tiled mesh generation so that larger polys will be split because of the tiling.

Another case where the detail polymesh was sometimes bugging out was how the height samples were picked from the voxelized representation. This should be improved now a bit, but I was not able to create a simple fix for the case where radius is zero. It is surprisingly complicated task to gather all the height samples which fall under a polygon. Most of the time it works ok, but some corner cases are just nightmare to get right.

So, if you have had problems with the detail meshes, grab the latest source from the SVN and give it a go.

[EDIT] I also added few convenience versions of rcRasterizeTriangles. One which accepts indices as unsigned shorts and another which can be used to rasterize non-indexed meshes.


  1. Sorry silly question,

    If the tiled mesh generation is used is the maximum poly size the size of the tile?

  2. This comment has been removed by the author.

  3. So, if you use a tile which is small this will increase the time to pathfind as it's got to asses more polygons when doing the A* ?

  4. Yes, that is correct :)

    There is a downside to the number of polygons too. Since the cost to navigate the polygons is calculated per polygon, large polygons can create detours where they should not.

    So the best practice is always to check your use case. If your paths are usually quite short, the A* cost might not be horrible, and you may get a little more accuracy. Know your data :)

  5. And a side note, the technique Recast uses for generating the mesh usually behaves much better when you do not have big open areas. It is both more robust and more fast. Too small tiles may become slow agin because more stuff needs to be rasteized.

    So a good maximum distance (from the edge of a navigable space) is somewhere around 64 voxels. So if you have big open fields, then it might be good idea to use tilesize of 64. Sprinkling just few obstacles there might solve the case as well.

    My current preference for tiled mesh is 32, which is good trade off between polygon count and tile generation speed.