Jump to content
  • Advertisement
Sign in to follow this  
sb01234

Delaunay triangulation to navmesh

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

If you intended to correct an error in the post then please contact us.

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 this post


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

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. smile.png

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!