Rendered at 09:05:56 GMT+0000 (Coordinated Universal Time) with Cloudflare Workers.
ur-whale 2 minutes ago [-]
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 ?
Remnant44 2 hours ago [-]
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.
morishuz 2 hours ago [-]
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.
Remnant44 46 minutes ago [-]
I haven't had a chance to dig into the repo at all, so that's excellent, thank you!
fp64 3 hours ago [-]
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
morishuz 2 hours ago [-]
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)
fp64 1 hours ago [-]
that's fantastic, thanks a lot. I had a use-case a while ago, so I might revisit and give delaunay32 a shot!
morishuz 1 hours ago [-]
great. and do let me know if you have any feature requests, noticed bugs etc
DennisL123 3 hours ago [-]
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.
> For large point sets, Delaunay32 is over 10× faster than delaunator-cpp and around 4× faster than Fade2D.
hingler36 10 hours ago [-]
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.
morishuz 2 hours ago [-]
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.
marmakoide 7 hours ago [-]
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.
cmovq 5 hours ago [-]
64 bit cpus have 128 bit mul results if that’s what you mean
delusional 4 hours ago [-]
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.
@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 ?
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.
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.
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/
> For large point sets, Delaunay32 is over 10× faster than delaunator-cpp and around 4× faster than Fade2D.
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.
(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.
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...