Releases: andywiecko/BurstTriangulator
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
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
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 withOutput.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: TheStatus
enum is now decorated with the[Flags]
. To check if no errors occurred, usestatus == 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 Release1
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
withAutoHolesAndBoundary
.
Full Changelog: v3.2.0...v3.2.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 |
Below the benchmark:
📝 Changelog
Added
- Support for additional types:
Vector2
,int2
, andfp2
(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()
andManagedInput
have been deprecated for safety reasons. UseAsNativeArray(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
-
This feature is available through an optional dependency. Users must install
com.danielmansson.mathematics.fixedpoint
. More info in the documentation. ↩ -
In the current implementation, holes are fully supported with
Settings.AutoHolesAndBoundary
. However, manual holes withint2
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 forint2
. ↩ -
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
inputint2
inputfp2
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
, andRefineMesh
. - 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 asTriangulator
, except the input/output is of typeT2
. Supported coordinate types:float2
,double2
(int2
will be implemented in the future).
Changed
- Increased performance for
constrainedHalfedges
generation. Circle
based calculations now useRadiusSq
instead ofRadius
. 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 usingusing andywiecko.BurstTriangulator;
. - Breaking change: The default coordinate type for
Triangulator
is nowdouble2
instead offloat2
. - (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
, andConstrainEdges
.
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 onconstraintEdges
. 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
inTriangulationSettings
, serving as a constant for concentric shells segment splitting. - Add
RefinementThresholds
inTriangulationSettings
, 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
, andMinimumAngle
as obsolete. Replace these parameters with the more versatileRefinementThresholds
.
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
andtriangleToEdges
mappings. - Removed the internal
Triangle
struct.
Full Changelog: v2.2.0...v2.3.0
v2.2.0
Changed
- Simplified constrained triangulation scheduling jobs pipeline.
- Adapted constrained triangulation for
half-edges
approach, which significantly improved performance. The algorithm no longer relies on triangulation mappings, such as edge-to-triangle and triangle-to-edge relationships (or circles). The complexity of the intersection searching algorithm has been reduced from a naive$O(n^2)$ solution to$O(n \log n)$ .
Fixed
- Resolved Sloan algorithm corner cases. In previous releases, constrained triangulation may get stuck. Constrained triangulation is now more robust.
Added
- Added constrained triangulation benchmark test. The results may be found at
README.md
.
Full Changelog: v2.1.0...v2.2.0
v2.1.0
Changed
- Replaced the classic Delaunay algorithm (without refinement/constraints) with an implementation based on
half-edges
(seedelaunator
anddelaunator-sharp
for more details). This change has led to a significant performance boost in unconstrained triangulation. SeeREADME.md
for more details. - Refactored some internal math utilities.
Full Changelog: v2.0.0...v2.1.0