1
\$\begingroup\$

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: Screenshot from SC2 editor, showing pathing mesh

\$\endgroup\$
11
  • \$\begingroup\$ I'd recommend walking us through the kinds of polygons you need to triangulate, and the constraints you need to honour, so we can help find effective solutions for that use case — whether constrained Delaunay triangulation is the best solution, or whether another algorithm could give better results for your case. \$\endgroup\$
    – DMGregory
    Jun 20 '20 at 17:42
  • \$\begingroup\$ As with Starcraft 2, this would be for map boundaries. Walls, cliffs, buildings, etc. The resulting triangles would be used with the funnel algorithm for pathing around within the map. \$\endgroup\$
    – Nairou
    Jun 20 '20 at 20:12
  • 3
    \$\begingroup\$ So you're making a navmesh? Including that in your question can help you get good answers appropriate to that use. For questions of geometry, including representative images is almost always a good idea. Don't assume everyone who might have useful info to share has seen the same SC2 GDC video you saw. \$\endgroup\$
    – DMGregory
    Jun 20 '20 at 20:31
  • \$\begingroup\$ @Topicstarter, can you link the Starcraft 2 GDC talk on the matter into the question plz? \$\endgroup\$
    – Kromster
    Jun 21 '20 at 5:39
  • 1
    \$\begingroup\$ @Kromster gdcvault.com/play/1014514/AI-Navigation-It-s-Not \$\endgroup\$
    – Nairou
    Jun 21 '20 at 14:10
2
\$\begingroup\$

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: removing intersecting edges

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

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.