A single-file package which provides Delaunay triangulation of the given set of points with constraints and mesh refinement.

✨ Supported Features

• Delaunay triangulation ᵈᵒᶜˢ
• Constrained triangulation ᵈᵒᶜˢ
• Mesh refinement (angle and area parameters) ᵈᵒᶜˢ
• Holes and restoring boundary (manual and auto) ᵈᵒᶜˢ
• Support for Unity.Jobs pipeline ᵈᵒᶜˢ
• Input preprocessors ᵈᵒᶜˢ
• Input validation ᵈᵒᶜˢ
• Generic coordinates (float2, double2, Vector2, int2, and fixed-point Q31.32) ᵈᵒᶜˢ
• Native support (low level API) ᵈᵒᶜˢ
• Managed input support ᵈᵒᶜˢ

To view the documentation for the manual and scripting API access it online here or navigate to Documentation~/ and build this using docfx.json.

📐 Example results

As an illustrative example, we present the triangulation of Lake Superior with various refinement parameters. The top-left image shows the result without any refinement.

⏱️ Benchmark

The package utilizes the Burst compiler, which generates highly optimized native code using LLVM. Below, you'll find a performance comparison for classic Delaunay triangulation (without refinement or constraints). between this package and a few alternatives:

• delaunator-sharp
• CGALDotNet
• Triangle.NET

To see more benchmarks visit the documentation.

🚀 Quick start

Install the package and add using in your code

using andywiecko.BurstTriangulator;

and to triangulate unit box $[(0, 0), (1, 0), (1, 1), (0, 1)]$:

using var positions = new NativeArray<double2>(new[]
{
    new(0, 0), new(1, 0), new(1, 1), new(0, 1)
}, Allocator.Persistent);
using var triangulator = new Triangulator(Allocator.Persistent)
{
    Input = { Positions = positions }
};

triangulator.Run();

var triangles = triangulator.Output.Triangles;

📦 Dependencies

Required:

• Unity.Burst@1.8.7
• Unity.Collections@2.2.0

Optional:

• com.danielmansson.mathematics.fixedpoint@0.1.0

🤝 Contributions

Found a bug? Please open an issue. You can find a list of known issues here. Interested in contributing to the project? Feel free to open an issue or submit a pull request. For updates on current and future work related to this package, check out the package project.

⚖️ License

• The code in this repository is licensed under the MIT License.
• The documentation in this repository is licensed under the CC BY 4.0 License.