Hi

I was wondering if someone could help me. Currently making my first automated navmesh and I am trying to simplify the triangle into larger convex polygons. I am having issues finding good resources which explains how to do this, I have AI Wisdom 1 and all it does is give you 3 bullet points about Hertel-Mehlhorn algorithm. Does anyone have any good working examples of could point me in the direction of a good resource to explain how to do this.

Thanks

When the union of two adjacent polygons is convex, you can merge them. Both the test and the merging depend mostly on your geometrical data structure; The Hertel-Mehlhorn algorithm amounts simply to processing each side once in arbitrary order, without a principled scan and without backtracking, and testing locally by looking at the two vertices spanned by the candidate side (does removal of the edge make them reflex in the merged polygon?).

A description in three bullet points is more than enough; the pieces you need for implementation are simple:

• iterate through all interior edges (shared by two polygons) in the mesh
• given an interior edge, remove it and merge the two polygons that share it
• given an edge, find its vertices
• given an edge and one of its endpoints, find the previous and next edge around that vertex; the angle between them determines whether removing the middle edge would make the vertex reflex wrt the merged polygon.Note that you can apply some heuristic to the processing ordering of interior edges: random, smallest triangles first, and so on.