Nice work. Getting DT edge cases right can be quite some work.
Shameless plug: My own DT for int32 coordinates in Rust, and compiled to wasm with a bit of visualization. Click to add and remove sites, hit animate for a bit of lava lamp like vibes.
Looks very promising - I've been looking for a good delaunay library that supports constrained delaunay.
It looks like their performance benchmark is including multithreading, which although a useful feature, makes performance comparisons more difficult - would love to see a baseline single threaded performance as well.
the repo comes with a benchmark tool that you can run on your own machine, which already compares multi vs single threading as well as delaunator-cpp (which is only single threaded)
At one million points, Delaunay32 takes about 147–150 ms with one thread versus 540–555 ms for delaunator-cpp on my machine, so roughly 3.7× faster. Automatic eight-thread mode Delaunay32 takes about 53–54 ms.
Looking at his performance graph it looks like he does about 1 million points in around 320ms or so (if I managed to read his graph correctly), albeit for float2 values and using Unity Burst which does SIMD+multiple threads.
@author : I'm trying to wrap my head around the following question: are there any situations where the "int32 constraint" would be an issue?
My gut feeling says that fine a grid (4B steps) is likely to generate a good enough approximation to the exact answer for general problem (64 bit float) for most cases.
Am I wrong?
Also: can the algorithm easily be extended to int64 ?
yes, there are currently two modes for internal integer math: 64 and 128 bit. (the internal int math needs larger ranges than the inputs since we work with squares etc)
64bit integers works with an input coordinate range of 29,609. this is typically fine for raster image coordinates or floats that can allow for some quantization (only the triangles/edges are affected by this not the original points!)
if the input range is larger than 29,609, the algorithm switches to a 128bit implementation with a range of 1,940,470,527 which is close to, but still smaller than, what could theoretically be stored in an int32 value. hence that's why the input is currently only up to int32.
in theory it could be extended to 64bit input range but it comes with performance and portability trade-offs that currently don't seem worth it
Can you compare with what used to be, to the best of my knowlege, by far the fastest implementation, https://www.cs.cmu.edu/~quake/triangle.html ? It's not int specific though, but I would still be curious
Are vertex insertion and deletion also supported/accelerated?
What compromises are keeping this constrained to 32-bit? It seems like you could cut back on quantization error by increasing bits, but if you're doing some manual SIMD magic to get this performance I can understand sticking with 32 bits.
> Are vertex insertion and deletion also supported/accelerated?
no unfortunately not, since this is currently a fast batch triangulator, so vertex insertion/deletion requires rebuilding
>What compromises are keeping this constrained to 32-bit?
it isn’t SIMD-specific. the circle test involves squared coordinates and further multiplications. therefore, 32-bit coordinates inputs can already require 128-bit temporary results internally. Supporting 64-bit exactly would require roughly 256-bit intermediates and come at the cost of speed and portability, so i think 32bit is currently a good trade-off.
Not the author, but I assume that to make it work with 32 bits integer coordinates, some operation (like multiplications) need extension to 64 bits. If we want full hardware support on 64 bits CPUs, that's the limit.
Triangulation usually requires an incicrle operation at some point, and that requires doing multiplication on the result of multiplication, without loss of precision.
32-bit triangulation therefore requires 128-bit multiplication, in some rare degenerate cases.
For one million unconstrained points on the reference Apple M1 system, eight-thread Delaunay32 completes in roughly 50 ms.
Using that as the 1.0× baseline:
• Delaunay32, one thread: ~2.8× runtime.
• Fade2D, automatic threads: ~4.5×.
• Fade2D, one thread: ~6×.
• delaunator-cpp: ~11×.
• Triangle: ~11×.
I do see the smiley, but still: show a litle more appreciation man, this is really impressive work and deserves more than a "great, can you do it on one leg now?" comment.
Nice work. Getting DT edge cases right can be quite some work.
Shameless plug: My own DT for int32 coordinates in Rust, and compiled to wasm with a bit of visualization. Click to add and remove sites, hit animate for a bit of lava lamp like vibes.
https://hermes.leytron.de/delauney/
very nice!
Looks very promising - I've been looking for a good delaunay library that supports constrained delaunay.
It looks like their performance benchmark is including multithreading, which although a useful feature, makes performance comparisons more difficult - would love to see a baseline single threaded performance as well.
the repo comes with a benchmark tool that you can run on your own machine, which already compares multi vs single threading as well as delaunator-cpp (which is only single threaded)
At one million points, Delaunay32 takes about 147–150 ms with one thread versus 540–555 ms for delaunator-cpp on my machine, so roughly 3.7× faster. Automatic eight-thread mode Delaunay32 takes about 53–54 ms.
I haven't had a chance to dig into the repo at all, so that's excellent, thank you!
Very nice results. For my Unity C# code I use Andy's package: https://github.com/andywiecko/BurstTriangulator
Looking at his performance graph it looks like he does about 1 million points in around 320ms or so (if I managed to read his graph correctly), albeit for float2 values and using Unity Burst which does SIMD+multiple threads.
Impressive work.
@author : I'm trying to wrap my head around the following question: are there any situations where the "int32 constraint" would be an issue?
My gut feeling says that fine a grid (4B steps) is likely to generate a good enough approximation to the exact answer for general problem (64 bit float) for most cases.
Am I wrong?
Also: can the algorithm easily be extended to int64 ?
yes, there are currently two modes for internal integer math: 64 and 128 bit. (the internal int math needs larger ranges than the inputs since we work with squares etc)
64bit integers works with an input coordinate range of 29,609. this is typically fine for raster image coordinates or floats that can allow for some quantization (only the triangles/edges are affected by this not the original points!)
if the input range is larger than 29,609, the algorithm switches to a 128bit implementation with a range of 1,940,470,527 which is close to, but still smaller than, what could theoretically be stored in an int32 value. hence that's why the input is currently only up to int32.
in theory it could be extended to 64bit input range but it comes with performance and portability trade-offs that currently don't seem worth it
Wouldn't most of the triangles be small, and thus computable using a smaller number of bits because coordinates can be made relative to one corner?
Can you compare with what used to be, to the best of my knowlege, by far the fastest implementation, https://www.cs.cmu.edu/~quake/triangle.html ? It's not int specific though, but I would still be curious
for a one million points set i measured 4x faster when using single threaded and 11x when using multi-threaded delaunay32 vs triangle (on my Apple M1)
that's fantastic, thanks a lot. I had a use-case a while ago, so I might revisit and give delaunay32 a shot!
great. and do let me know if you have any feature requests, noticed bugs etc
Great project!
Are vertex insertion and deletion also supported/accelerated?
What compromises are keeping this constrained to 32-bit? It seems like you could cut back on quantization error by increasing bits, but if you're doing some manual SIMD magic to get this performance I can understand sticking with 32 bits.
thanks!
(i am the author of Delaunay32)
> Are vertex insertion and deletion also supported/accelerated?
no unfortunately not, since this is currently a fast batch triangulator, so vertex insertion/deletion requires rebuilding
>What compromises are keeping this constrained to 32-bit?
it isn’t SIMD-specific. the circle test involves squared coordinates and further multiplications. therefore, 32-bit coordinates inputs can already require 128-bit temporary results internally. Supporting 64-bit exactly would require roughly 256-bit intermediates and come at the cost of speed and portability, so i think 32bit is currently a good trade-off.
Not the author, but I assume that to make it work with 32 bits integer coordinates, some operation (like multiplications) need extension to 64 bits. If we want full hardware support on 64 bits CPUs, that's the limit.
Triangulation usually requires an incicrle operation at some point, and that requires doing multiplication on the result of multiplication, without loss of precision.
32-bit triangulation therefore requires 128-bit multiplication, in some rare degenerate cases.
In this repo the incircle is here: https://github.com/morishuz/delaunay32/blob/141d979b18e296ac...
64 bit cpus have 128 bit mul results if that’s what you mean
from the site
> For large point sets, Delaunay32 is over 10× faster than delaunator-cpp and around 4× faster than Fade2D.
For one million unconstrained points on the reference Apple M1 system, eight-thread Delaunay32 completes in roughly 50 ms.
Using that as the 1.0× baseline: • Delaunay32, one thread: ~2.8× runtime. • Fade2D, automatic threads: ~4.5×. • Fade2D, one thread: ~6×. • delaunator-cpp: ~11×. • Triangle: ~11×.
Neat, now do a 3D Delaunay tetrahedrization! :)
You can look into [HXT](https://gitlab.onelab.info/gmsh/gmsh/tree/master/contrib/hxt) for that. More specifically [this file](https://gitlab.onelab.info/gmsh/gmsh/-/blob/master/contrib/h...) which shows how create the Delaunay tetrahedralization of a set of point using the tetMesh library. It's a shameless plug since I am the author of the HXT core and tet meshing stuffs.
> Neat, now do a 3D Delaunay tetrahedrization! :)
I do see the smiley, but still: show a litle more appreciation man, this is really impressive work and deserves more than a "great, can you do it on one leg now?" comment.
I upvoted, I favorited, I starred the repo, and I even used a smiley.
What has OP done for me lately? :)
[dead]