INativeDisposable and Triangle Filter

[Bodyclock-Games]

Hi Andy, thanks very much for your work. I'm using BurstTriangulator as the foundation of procedural level system for Unity using a Node/Edge based Graph. All working great so far. Just a couple of thoughts I've had while working with it.
As I do a lot of post-processing and would like to chain the triangulator in the middle of a series of steps, I need to Dispose of it in the chain. So it would be very useful if it implemented INativeDisposable instead of just IDisposable. It's not difficult to implement so I've done it myself, but it would be good to have it in the base code.
The other point is : I use a set of initial points based on Poisson Disc Sampling. so the data is very clean but the narrow triangles created by the hull become problematic for my use case. I solved it by processing each triangle and halfedge and removing the ones that failed an angle threshold test. In my case if any triangle had any angle under 20 degrees it was removed. This obviously works for me because of regular spacing of the Poisson sampling. I wondered if it might be a useful addition to BurstTriangulator.
Thanks also for the Remove Safety Checks option, increased the performance by an order of magnitude.
Great job and thanks again.
Cheers
Chris

[andywiecko]

Hi @Bodyclock-Games
Thanks for the issue!

thanks very much for your work.

You're welcome! I'm glad the community is finding the package useful🙂

... So it would be very useful if it implemented INativeDisposable instead of just IDisposable. It's not difficult to implement so I've done it myself, but it would be good to have it in the base code.

Great idea! Would you be interested in opening a pull request with these changes? I've added this to the project board, and it will be included in a future release. Your requirement for INativeDisposable suggests to me that you're using the package for some custom logic. Are you familiar with the UnsafeTriangulator API?

The other point is : ...

I'm open to enhancing the package, but you may need to elaborate on this feature a bit more. We can discuss it further here.

Best,
Andrzej

[andywiecko]

Hi @Bodyclock-Games,
BurstTriangulator@v3.7.0 has been published, and this release includes your suggestion regarding INativeDisposable. Many thanks for reporting this!

Regarding the other case—the triangles filter—could you elaborate further? I'd love to improve the package and make it even more useful for the community.

Best,
Andrzej

[Bodyclock-Games]

Hi Andy, Sorry I haven't got back to you sooner. I solved the problem a different way and then forgot.
I'll give you a rundown of my use case and the issue in case it helps refine the product. I'm basically creating a Graph based terrain system in Unity. I create a series of connected Nodes and Edges.

The process is to create a set of Poisson Disc points constrained by a shape (rectangle, circle, ellipse) and then triangulate those.

The issue was at this stage I really wanted a concave hull, but the triangulation gave me a convex hull with a lot of thin triangles on the edge, especially on a square shape. Sadly my solution is so entrenched in the code it's hard to produce a graphical reproduction of the original output. The one below is already filtered.

I solved this (and it was actually the correct way to do it really) by creating centroids from your triangles, adding edges (to create voronoi cells) and filtering out any points and edges that were not part of a complete cell.

I then joined the centroids to the original points to be able to form a mesh.

So I think ultimately what I was asking was probably out of scope for Triangulator, and the workflow I came up with has some benefits.

Thanks for putting in INativeDisposable, I'll upgrade so I don't have to upgrade my code. :)

One comment I do have is that the reason I needed the INativeDisposable was the ownership of the Output arrays makes it a little awkward to chain dependencies in the Unity Job System in terms of disposal. Not a big deal but just requires a bit thought.

Thanks for the update and keep up the good work.

Cheers

Chris

[andywiecko]

Hi Chris,
Many thanks for the explanation!

The issue was at this stage I really wanted a concave hull, but the triangulation gave me a convex hull

Yes, for unconstrained triangulation, the result will always be a convex hull. Currently, to achieve a concave result, one needs to provide constraints and enable the holes and boundaries options.

So I think ultimately what I was asking was probably out of scope for Triangulator, and the workflow I came up with has some benefits.

Your issue got me thinking, and I believe this would be a great extension for the package in the future. I'll certainly work on this at some point. This could serve as another automatic option for generating 2D meshes.

I came across this paper: M. Duckham et al. (2008), which seems to describe the algorithm you're looking for—it offers better control. I've reported this on the project board. This will take some time, but I'll ping you once the feature is implemented.

Best,
Andrzej

[Bodyclock-Games]

Thanks Andy,
complex paper but yes that's what I was looking for. The solution I have also works for random shapes (see original image). I apply noise, remove any points under a threshold, triangulate that and run the filter. Keep me informed.

[andywiecko]

Hi Chris,
I've released version v3.8 which adds support for $\alpha$-shapes. This feature should help you easily resolve issues with concavities. Here's a quick example:

using var positions = new NativeArray<double2>(..., Allocator.Persistent);
using var triangulator = new Triangulator(Allocator.Persistent)
{
  Input = { Positions = positions },
  Settings = { UseAlphaShapeFilter = true, AlphaShapeSettings = { Alpha = 0.1f, ... }},
};

triangulator.Run();

You can find more details in the docs or my blog post. I hope you find it useful!

Best,
Andrzej

[Bodyclock-Games]

Hi Andy, looks good from your blog post. I’m traveling for the summer so will have limited opportunity to test it but as soon as I can I will and give you some feedback. Cheers Chris

…

On Thu, 1 May 2025 at 11:54, Andrzej Więckowski, Ph.D. < ***@***.***> wrote: *andywiecko* left a comment (andywiecko/BurstTriangulator#325) <#325 (comment)> Hi Chris, I've released version v3.8 <https://github.com/andywiecko/BurstTriangulator/releases/tag/v3.8.0> which adds support for $\alpha$-shapes. This feature should help you easily resolve issues with concavities. Here's a quick example: using var positions = new NativeArray<double2>(..., Allocator.Persistent);using var triangulator = new Triangulator(Allocator.Persistent){ Input = { Positions = positions }, Settings = { UseAlphaShapeFilter = true, AlphaShapeSettings = { Alpha = 0.1f, ... }},}; triangulator.Run(); You can find more details in the docs <https://andywiecko.github.io/BurstTriangulator/manual/examples/alpha-shape-filter.html> or my blog post <https://andywiecko.github.io/blog/04-alpha-shapes.html>. I hope you find it useful! Best, Andrzej — Reply to this email directly, view it on GitHub <#325 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AL4W76CSPUUYSMBWIXA5J2324H4PPAVCNFSM6AAAAABWXTWVTCVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZDQNBUGYZTSOJWGM> . You are receiving this because you were mentioned.Message ID: ***@***.***>