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.
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.
> 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.
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.
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
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.
@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 ?
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.
11 comments
[ 1.2 ms ] story [ 7.5 ms ] threadAre 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.
(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.
> For large point sets, Delaunay32 is over 10× faster than delaunator-cpp and around 4× faster than Fade2D.
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/
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.
@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 ?
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.