v3.5.0

❄️🎅🎄 Winter Update ❄️🎅🎄

Ho ho ho! This is the final release of BurstTriangulator for 2024, but don't worry—more updates are coming in 2025! Thank you all for your support; it’s wonderful to see the community actively using this package.

Looking ahead to next year, I'm excited to announce the planned release of the first BurstTriangulator addon package, which will introduce utilities for pathfinding in triangular meshes. Additionally, I plan to resume development of my PBD2D engine. Stay tuned for more updates, and I wish you all success with your fantastic projects!

Best,
Andrzej

✨ What's new?

🆕 Dynamic Triangulation Completed

This update introduces two essential methods for the UnsafeTriangulator, enabling full support for dynamic triangulation:

• DynamicSplitHalfedge allows point insertion by splitting a selected halfedge ᵈᵒᶜˢ,
• DynamicRemoveBulkPoint facilitates the removal of points from the mesh bulk ᵈᵒᶜˢ.

Learn more in the documentation.

📈 Enhanced refinement performance

The Bowyer-Watson point insertion algorithm has been refactored, resulting in an approximate 25% performance improvement during the refinement step and dynamic triangulation routines.

Performance Benchmarks:

In addition, a new benchmark has been introduced using Lake Superior as the input dataset—a commonly used test case for this package. This more general test suite provides better benchmarking for arbitrary input data compared to the original unit box refinement test case.

📝 Changelog

Added

• DynamicSplitHalfedge extension for UnsafeTriangulator, enabling point insertion by splitting a selected halfedge.
• DynamicRemoveBulkPoint extension for UnsafeTriangulator, facilitating the removal of points from the mesh bulk.

Changed

• Refactor Bower-Watson point insertion algorithm to achieve approximately a 25% performance improvement during the refinement step and dynamic triangulation routines.
• Optimized planting seeds job for slightly increased performance and reduced memory allocation.
• (Internal) Various refactors to improve code clarity and maintainability.

---

Full Changelog: v3.4.0...v3.5.0

v3.4.0

🎃 Halloween Update 🎃

✨ What's new?

🆕 Dynamic triangulation

This release introduces basic support for dynamic triangulation with the new DynamicInsertPoint extension. It allows for dynamically inserting a point into a triangulation within a specified triangle using barycentric coordinates. Future updates will expand functionality to include additional extensions for splitting a halfedge and removing specific points, as well as, updates will increase performance related to point insertion/removal.

Here's an example snippet showcasing triangulation followed by a dynamic point insertion:

var t = new UnsafeTriangulator<float2>();

using var positions = new NativeArray<float2>(..., Allocator.Persistent);
using var constraints = new NativeArray<int>(..., Allocator.Persistent);
var input = new InputData<float2> { Positions = positions, ConstraintEdges = constraints };

using var outputPositions = new NativeList<float2>(Allocator.Persistent);
using var triangles = new NativeList<int>(Allocator.Persistent);
using var halfedges = new NativeList<int>(Allocator.Persistent);
using var constrainedHalfedges = new NativeList<bool>(Allocator.Persistent);
var output = new OutputData<float2> { Positions = outputPositions, Triangles = triangles, Halfedges = halfedges, ConstrainedHalfedges = constrainedHalfedges };

t.Triangulate(input, output, args: Args.Default(autoHolesAndBoundary: true), Allocator.Persistent);

// Insert a new point in triangle with index 42 at the center (barycentric coordinates: [⅓, ⅓, ⅓]).
t.DynamicInsertPoint(output, tId: 42, bar: 1f / 3, allocator: Allocator.Persistent);

Learn more in the manual.

🆕 Online demo

To better demonstrate the package's capabilities, we've prepared a small online demo, available here.

📈 Enhanced refinement performance

To support dynamic triangulation, we refactored portions of the refinement process, resulting in a nearly 2x performance improvement after recent fixes and optimizations.

📈 Improved editor compatibility

TriangulationSettings is now better suited with UnityEditor, enhancing the user experience when configuring settings in the editor.

🔧 Important refinement fixes

This release addresses two key issues related to refinement.

1. Fixed a rare issue that could produce invalid results, especially in cases where the input data included clustered subsegments, which occasionally caused points to appear outside the triangulation domain.
2. Resolved an issue where refinement with constraints would ignore boundaries if no holes were present.

📝 Changelog

Added

• Dynamic triangulation support. Introduced DynamicInsertPoint extension for UnsafeTriangulator to support dynamic point insertion.
• A new demo scene to better illustrate the functionality in the documentation.

Changed

• Improved support for TriangulatorSettings in UnityEditor by adding a missing backing field, a setter, and editor-related attributes for properties.
• Refinement step optimization. Refactored the refinement step to enhance performance and simplify the code.

Fixed

• Refinement with constraints without holes. Corrected an issue where refinement with constraints would ignore boundaries when holes were absent.
• Invalid refinement results. Fixed a rare issue where refinement could produce invalid results, especially when input data included subsegment clusters, leading to points appearing outside the triangulation domain.

---

Full Changelog: v3.3.0...v3.4.0

v3.3.0

✨ What's new?

🆕 Ignored constraints for seed planting

This feature is especially useful when the user wants to include a constraint but does not wish to enable any planting hole mechanism for that edge. Consider the following example input:

using var positions = new NativeArray<double2>(..., Allocator.Persistent);
using var constraintEdges = new NativeArray<int>(..., Allocator.Persistent);
using var ignoreConstraint = new NativeArray<bool>(..., Allocator.Persistent);
using var triangulator = new Triangulator(Allocator.Persistent)
{
  Input = {
    Positions = positions,
    ConstraintEdges = constraintEdges,
    IgnoreConstraintForPlantingSeeds = ignoreConstraint,
  },
  Settings = { AutoHolesAndBoundary = true, },
};

triangulator.Run();

var triangles = triangulator.Output.Triangles;

In this example, the red constraint is set to true in IgnoreConstraintForPlantingSeeds. As a result, a hole is not generated from red constraint, and the edge remains part of the final triangulation.

📈 Faster hole planting

The complexity has improved from $\mathcal O(n^2)$ to $\mathcal O(n)$, making hole planting almost free compared to the Delaunay step.
Below is a benchmark for Constrained Delaunay triangulation with the auto-holes option enabled. As a test case, we use a square containing hole squares (denoted by #holes). Reference timings for the auto-holes option disabled are marked with a dashed line.

Co-authored-by: @HalfVoxel

🔧Fix overflow for int2

Overflow for int2 coordinates for large coordinates with differences around $\sim 2^{20}$ was resolved.
Example input which failed to triangulate correctly before this release can be seen below:

Co-authored-by: @HalfVoxel

🆕 Status error codes

New flags have been added to the Status enum for enhanced error handling during triangulation. Users can now catch errors during validation more effectively. Note: The Status enum is now decorated with the [Flags]. To check if no errors occurred, use

if (status != Status.OK)
{
    return;
}

Read more at project's documentation.

📝 Changelog

Added

• Ignored constraints for seed planting. Users can now ignore specific constraints during the seed planting process. This is especially useful when constraining edges without creating hole boundaries. This option can be set using Input.IgnoreConstraintForPlantingSeeds. Additionally, post-triangulation verification can be done with Output.IgnoredHalfedgesForPlantingSeeds, which provides a list of booleans indicating whether a given halfedge was ignored during seed planting.
• Status error codes. New flags have been added to the Status enum for enhanced error handling during triangulation. Users can now catch errors during validation more effectively. Note: The Status enum is now decorated with the [Flags]. To check if no errors occurred, use status == Status.OK.

Changed

• Faster hole planting. The complexity has improved from 𝒪(n²) to 𝒪(n), making hole planting almost free compared to the Delaunay step.
• Improved validation. All input data buffers are now validated. Additionally, some unconfigured settings can trigger log warnings.

Fixed

• Integer overflow for int2 coordinates. Resolved an overflow issue for large coordinates with differences around ~2²⁰.

---

Full Changelog: v3.2.1...v3.3.0

v3.2.1

🌿 Green Release¹

Hi!

It's me again! Today's small release focuses on updates to the API documentation, with many additional lines of code (~0.6k LOC) added for improvements.

Best,
Andrzej

📝 Changelog

Changed

• Significant updates to the API documentation.
• (Internal) Miscellaneous changes.

Deprecated

• The OutputData(Triangulator<T2>) constructor is now obsolete. It will be made internal in future versions.

Fixed

• Resolved a potential issue causing an infinite loop during the PlantingSeedStep with AutoHolesAndBoundary.

---

Full Changelog: v3.2.0...v3.2.1

1. I hope that you also have comments in green in your IDE. ↩

v3.2.0

✨ What's new?

As the holidays come to an end, we're excited to announce a new release of the Burst Triangulator!

🆕 New generic types support!

In this version, there is finally support for the int2 and fp2 (fixed-point Q31.32) types. These types are crucial as they ensure that the triangulation result is independent of the hardware architecture, making them suitable for use in scenarios such as lockstep simulations (e.g., in multiplayer RTS games).

The supported features for each type in this version are as follows:

type	delaunay	constraints	holes	refinement	preprocessors	notes
float2	✔️	✔️	✔️	✔️	✔️
Vector2	✔️	✔️	✔️	✔️	✔️	Via float2 reinterpret
double2	✔️	✔️	✔️	✔️	✔️
fp2	✔️	✔️	✔️	✔️	✔️	Requires additional package1
int2	✔️	✔️	🟡2	❌	🟡3	Support up to $\sim 2^{20}$

Below the benchmark:

📝 Changelog

Added

• Support for additional types: Vector2, int2, and fp2 (fixed-point in Q31.32 format). Note: fp2 requires an optional dependency. Refer to the manual for more details.
• (Internal) Introduced TrianglesComparer to simplify triangle assertions in tests.
• Args is now blittable and can be used in Burst-compiled static methods.
• Enhanced validation logs to include position information.

Changed

• (Internal) Various simplifications, minor performance improvements, refactoring, and additional code comments.

Deprecated

• AsNativeArray() and ManagedInput have been deprecated for safety reasons. Use AsNativeArray(out Handle handle) instead. Refer to the manual for more information.

Fixed

• Corrected the refinement of concentric shells segment splitting factor alpha.
• Fixed safety issues with AsNativeArray.
• Fully collinear input is now handled correctly.

Full Changelog: v3.1.0...v3.2.0

---

1. This feature is available through an optional dependency. Users must install com.danielmansson.mathematics.fixedpoint. More info in the documentation. ↩

2. In the current implementation, holes are fully supported with Settings.AutoHolesAndBoundary. However, manual holes with int2 coordinates may not guarantee that the given hole can be created. An additional extension is planned in the future to support holes with manual floating-point precision for int2. ↩

3. Support for Preprocessor.COM with translation only is available. ↩

v3.1.0

✨ What's new?

Managed input

You can now use managed arrays as triangulator input (i.e., standard C# arrays T2[]). Simply use new ManagedInput {} as the input object.

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

Alternatively, you can use the AsNativeArray extension to create a NativeArray<T> view for the managed array in place.

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

Constrained Halfedges

When performing constrained triangulation, you can determine whether a given halfedge is constrained by using Output.ConstrainedHalfedges.

var constrainedHalfedges = triangulator.Output.ConstrainedHalfedges;

This information can be particularly useful during post-processing by the user.

Native support

Native support for triangulation is now available. You can call triangulation routines in jobs via UnsafeTriangulator<T>.
Below one can find minimal working example using UnsafeTriangulator<T2>

using andywiecko.BurstTriangulator.LowLevel.Unsafe;

...

using var positions = new NativeArray<float2>(..., Allocator.Temp);
using var triangles = new NativeArray<int>(64, Allocator.Temp);
new UnsafeTriangulator<float2>().Triangulate(
    input: new() { Positions = positions },
    output: new() { Triangles = triangles },
    args: Args.Default(),
    allocator: Allocator.Persistent
);

This corresponds to the following managed approach with Triangulator<T2>

using var triangulator = new Triangulator(Allocator.Persistent)
{
    Input = { Positions = new float2[]{ ... }.AsNativeArray() }
};
triangulator.Run();
var triangles = triangulator.Output.Triangles;

To learn more about customization, read the documentation.

🔔 Announcements

🚀 Next Release Roadmap

In the next release, we plan to add a few very exciting features, including support for:

• Vector2 input
• int2 input
• fp2 input (fixed-point type in Q31.32 format)
• dynamic triangulation by point insertion

📦 New Extension Package!

We have started working on a new package based on BurstTriangulator! This package will be an extension of BurstTriangulator and will include utilities related to pathfinding. It aims to provide a highly efficient solution for triangle meshes!

❤ Sponsoring

GitHub Sponsoring is now available! If you're using the package and are interested in supporting our work, please consider becoming a sponsor!

📝 Change log

Added

• Native support with a low-level API for triangulation via UnsafeTriangulator<T>. This allows for customization of steps and calling triangulation directly from jobs.
• Extensions for UnsafeTriangulator<T>: Triangulate, PlantHoleSeeds, and RefineMesh.
• Support for managed input.
• Public ConstrainedHalfedges in triangulation output.

Fixed

• Edge-edge intersection for collinear non-intersecting edges (issue [#173]).

---

Full Changelog: v3.0.0...v3.1.0

v3.0.0

🏖️ Summer Update 🏖️

Hello and happy summer! I have great news: BurstTriangulator has finally been released with version v3.

This release introduces massive changes and opens the road for new incoming features! You can learn more about new features at project documentation.

Generic coordinates

The most significant change is the introduction of Triangulator<T2>, which allows for generic coordinates.
Currently, float2 and double2 are implemented. In the future int2 will also be implemented.
To run triangulation with selected T2, just add generic parameter to your code

using var positions = new NativeArray<float2>(..., Allocator.Persistent);
using var triangulator = new Triangulator<float2>(Allocator.Persistent)
{
  Input = { Positions = positions },
};

triangulator.Run();

Note

Triangulator is still accessible and by default it is based on double2 coordinates.

Below, you can see the benchmark for generic coordinates for Delaunay triangulation. float2 seems to be slightly faster than double2, however, any significant difference is noticeable only for very large inputs.

Auto holes

This release also introduces automatic hole detection and restoring boundary. If one sets Settings.AutoHolesAndBoundary to true, then holes will be created automatically depending on the provided constraints.

using var positions = new NativeArray<double2>(..., Allocator.Persistent);
using var constraintEdges = new NativeArray<int>(..., Allocator.Persistent);
using var triangulator = new Triangulator(Allocator.Persistent)
{
  Input = { 
    Positions = positions,
    ConstraintEdges = constraintEdges,
  },
  Settings = { AutoHolesAndBoundary = true, },
};

triangulator.Run();

var triangles = triangulator.Output.Triangles;

Warning

The current implementation of AutoHolesAndBoundary detects only 1-level islands. It will not detect holes in solid meshes inside other holes.

Performance

All these changes impact performance, and as the results, triangulation modes have better performance than previous releases. See the benchmarks below:

---

Stay tuned for more updates. 🙂
Happy triangulating! 📐

Best,
Andrzej

---

Change log

Added

• New online documentation (including manual and scripting API): https://andywiecko.github.io/BurstTriangulator/
• Verbose option in triangulation settings.
• Halfedges for triangulation output.
• AutoHolesAndBoundary option in triangulation settings. This option allows for automatic hole detection, eliminating the need for the user to provide hole positions. Holes are calculated using constraint edges.
• Support for generic coordinates. Users can specify the type of coordinates used in the triangulation with Triangulator<T2>. The API for this class is the same as Triangulator, except the input/output is of type T2. Supported coordinate types: float2, double2 (int2 will be implemented in the future).

Changed

• Increased performance for constrainedHalfedges generation.
• Circle based calculations now use RadiusSq instead of Radius. This results in increased performance in the refinement step, however, the final results may be slightly different.
• Breaking change: Moved most of the inner types (e.g., Status, TriangulatorSettings, etc.) to the global namespace. They can now be accessed directly using using andywiecko.BurstTriangulator;.
• Breaking change: The default coordinate type for Triangulator is now double2 instead of float2.
• (Internal) Greatly simplified job logic replaced with steps. Overall triangulation logic is now easier to follow and read. Some internal structs were removed or hidden inside steps.

Removed

• Obsolete settings: BatchCount, MinimumAngle, MinimumArea, MaximumArea, and ConstrainEdges.

Fixed

• Run triangulator on the main thread using the Run() method.

---

Full Changelog: v2.5.0...v3.0.0

v2.5.0

Changed

• Simplified PlantingSeedJob by removing generics and introducing an algorithm based on constraintEdges. This resulted in improved performance.
• Changed the triangulator to schedule a single job instead of multiple smaller ones.
• Greatly simplified the preprocessor transformations code. All transformations are now represented by the AffineTransform2D struct, and several jobs have been removed.

Deprecated

• Deprecated the Triangulator.Settings.ConstrainEdges property. To enable constrained edges, pass the corresponding array into input.
• Deprecated the Triangulator.Settings.BatchCount property. This property is no longer used, setting it has no effect.

Fixed

• Fixed constructing pointToHalfedges during constraint resolution. This resolves GitHub issue #111.

New Contributors 🎉

• @HalfVoxel made their first contribution in #110. Congratulations!

---

Full Changelog: v2.4.0...v2.5.0

v2.4.0

🎄 Xmas Update 🎄

Hello, and happy holidays! 🎅 This marks the final release of 2023, but exciting updates await in 2024!

In this release, significant improvements were made to the refinement algorithm, enhancing the overall quality of the mesh. The refined mesh now features non-uniform triangle density, with increased concentration near boundaries and reduced density in the mesh bulk.
See the example attached below:

Added

• Introduce ConcentricShellParameter in TriangulationSettings, serving as a constant for concentric shells segment splitting.
• Add RefinementThresholds in TriangulationSettings, including .Area and .Angle. Previous corresponding parameters are marked with obsolete.

Changed

• Enhance triangulation refinement for improved quality and performance. Replace the previous algorithm with a new one, similar to Shewchuk's terminator algorithm. The refined mesh now exhibits non-uniform triangle density, with increased density near boundaries and decreased density in the mesh bulk.
• Update README.md to include a comparison between different refinement settings.
• Remove the super-triangle approach (resulting in a slight performance boost). Perform refinement after removing holes and boundaries for better refinement quality.

Deprecated

• Mark MinimumArea, MaximumArea, and MinimumAngle as obsolete. Replace these parameters with the more versatile RefinementThresholds.

---

Full Changelog: v2.3.0...v2.4.0

v2.3.0

Changed

• Improved performance by adapting triangulation with mesh refinement to a half-edges approach.
• Simplified the refinement job contract.
• Merged several internal jobs for better efficiency.
• General project simplification for enhanced maintainability.

Removed

• Eliminated edgeToTriangles and triangleToEdges mappings.
• Removed the internal Triangle struct.

---

Full Changelog: v2.2.0...v2.3.0