11–20 of 26 posts
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.
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.
(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.
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.
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.
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/
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
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)
Earlier quoted context omitted.
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!
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.
@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 ?
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.