# Delaunay triangulation to navmesh

This topic is 2377 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

How go from a delaunay triangulation to a navmesh?

Let's for simplicity say we're working in 2d. Input is a list of line segments specified by two points p0, p1, with the ordering of p0, p1 chosen so that perp(p1 - p0) denotes a "normal" pointing to what is walkable in the map. Each line segment is guaranteed to be connected (aside from small numerical errors) on each side to another line segment, so that together they define one or more complex polygons that denote walkable areas.

Input to Delaunay triangulation would then be all points p0, p1 from the list of line segments (with duplicates removed), correct?

From that, we obtain a Delaunay triangulation containing triangles for both walkable and unwalkable areas, e.g. a map consisting of an unwalkable square inside a big walkable square generating two triangles for the inner square. There seems to be two error cases to deal with when turning this into a navmesh:

a. a triangle is entirely on unwalkable ground, which could be detected through a point-in-polygon test e.g. the triangle midpoint versus the list of line segments (that together form a complex polygon). In this case that triangle can simply be removed, and we're done.

b. the other option is that the triangle straddles both walkable and unwalkable ground. What to do in this case? First of all - how do we detect this case? Secondly, what do we do? A flipping of the triangle edge of the offending triangle and the one next to it (which must also be an offending triangle - always?) followed by removal of the unwalkable triangles would solve the walkability requirement, but is the Delaunay property guaranteed to still hold?

##### Share on other sites
Speaking for myself, I'd really benefit from a paint diagram to try and understand what you are asking.

I've luckily had artists build nav meshes for levels in the past, but it can be done automated. I think there was a good article in one of the game gems series on it, I'm sure google will turn up something.

Essentially as I hazily remember it, you first identify a floor area, then when you've got stuff on the floor in the way, you have to cut up the mesh and subtract the bit where the obstacle is. I'm sure it's quite fiddley to get right. Or you could have an obstacle list and use that alongside your mesh, but that's not the standard way of doing it.

And the delauney triangulation is nice to get a sensible layout of triangles, but I wouldn't necessarily get too hung up on keeping it delauney compliant once you start cutting it up.

1. 1
Rutin
27
2. 2
3. 3
4. 4
5. 5

• 11
• 11
• 10
• 13
• 20
• ### Forum Statistics

• Total Topics
632948
• Total Posts
3009393
• ### Who's Online (See full list)

There are no registered users currently online

×