How does heavily constrained delaunay triangulation work?

Question

In short: I'm trying to find an algorithm for performing a Delaunay triangulation of a heavily constrained polygon (for the purpose of pathfinding), with the understanding that most of the resulting triangles will be illegal (non-Delaunay) due to the constraints. Making the effort should still help reduce generation of long/thin triangles where possible.

I'm trying to understand how constrained Delaunay triangulation works, within the context of game maps where the available ground surface for navigation and pathing is defined by a polygon on a flat 2D plane. The polygon needs to be triangulated for use in pathfinding, such that moving from point A to point B passes through as few polygons as possible (so polygons need to be as large as possible).

I first looked into regular Delaunay triangulation, and there are multiple methods available, but they all assume a point cloud where the goal is to create ideal triangles without constraints.

Then I looked into constrained Delaunay triangulation, but there is very little available I could find beyond academic papers, and many of those simply perform a regular Delaunay triangulation, then cut triangles that intersect constraints and re-triangulate around them. This seems backwards and inefficient to me when literally ALL of the triangles I want to end up with will be constrained.

I saw a GDC video, where the Starcraft 2 devs talked about using constrained Delaunay triangulation, and you can kind of see it when you look at the pathing mesh in the Starcraft 2 editor (see below). However, very few of the generated triangles are legal, due to the number of constraints in the map layout. Still, I am assuming the Delaunay algorithm influenced the selection of points to triangulate, in order to get the best triangle coverage.

However, I can't find any further info on how this might work. How does one start with constraints, points connected by fixed lines, and then "fill in" the remaining lines to generate triangles that are a best-effort attempt to not be overly stretched or narrow?

Edit: Screenshot example from Starcraft 2 editor:

Answer 1

You're almost there. Once you have a delaunay triangulation of all the points (including constraint points) then:

foreach constraint edge:

1. Find all existing intersecting edges in the triangulation
2. 'Remove' these intersecting edges (see below)
3. Restore the delaunay triangulation

Regarding step 2), here is a description from Eric Nordeus that summarises this step:

"The idea here is that all possible triangulations for a set of points can be found by systematically swapping the diagonal in each convex quadrilateral formed by a pair of triangles. So we will test all possible arrangements and will always find a triangulation which includes the constrained edge."

The quadrilateral is formed from the 2 triangles that share the edge intersecting the constraint.

Get the 3 vertices for the triangle the intersecting edge is on and then get the 'opposite' edge of this edge (in the half edge data structure on the Habrador blog, the opposite edge has the same vertices, but they are swapped in order).

If these 4 points form a convex quad then you can flip the edge.

If the new flipped edge intersects the current constraint you push it back on the intersectingEdges list, otherwise you have a new edge that no longer intersects the constraint.

Here's a very simple diagram that hopefully helps illustrate the basic concept:

Here is some further reading, including better & more detailed descriptions on the above & some further experiments on constrained delaunay navmesh pathfinding by myself:

Eric Nordeus blog: constrained delaunay

Constrained Delaunay Navmesh someone posted on the Unity forums, complete with tutorial

My own blog post on using Constrained Delaunay Triangles as a navmesh including dynamic updating and pathfinding info