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?
Show differencesHistory of post edits
#1sb01234
Posted 14 April 2012 - 02:57 PM
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.
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 also triangles for the 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 cases:
a. either 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?
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.
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 also triangles for the 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 cases:
a. either 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?