Sign in to follow this  

Hertel-Mehlhorn NavMesh optimization: Long polygons

Recommended Posts


I have implemented the Hertel-Mehlhorn algorithm to optimize my navigation mesh. As you can see in the image there are many cells that are long and thin. This happens when I have large open spaces.
Is that a known behavior of H-M algorithm or do I do something wrong? Is it possible to somehow define a maximum width of a cell? Or are there other ways to deal with this?

(Please ignore that the diagonal obstacles produce a pixel-like effect, that's a topic for another post).

Thank you!

Share this post

Link to post
Share on other sites
You are applying the Hertel-Mehlhorn algorithm to a starting triangulation that is full of slivers: both the short sides and the long sides are all in the source data.
You apparently fail to merge polygons over what should be collinear segments (for example, each of the rectangular platforms should be one piece): look for accidentally nonplanar geometry (ouch!) or for subtly wrong geometric tests that don't like angles of exactly 180 degrees.

Share this post

Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this