Exact, parallel 2D Delaunay triangulation for int32 coordinates
1–10 of 26 posts
Re: Exact, parallel 2D Delaunay triangulation for int32 coordinates
#2Great 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.
Re: Exact, parallel 2D Delaunay triangulation for int32 coordinates
#3Great 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.
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.
Re: Exact, parallel 2D Delaunay triangulation for int32 coordinates
#4[dead]
Re: Exact, parallel 2D Delaunay triangulation for int32 coordinates
#5Neat, now do a 3D Delaunay tetrahedrization! :)
Re: Exact, parallel 2D Delaunay triangulation for int32 coordinates
#6Great 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.
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.
64 bit cpus have 128 bit mul results if that’s what you mean
Re: Exact, parallel 2D Delaunay triangulation for int32 coordinates
#7from the site
> For large point sets, Delaunay32 is over 10× faster than delaunator-cpp and around 4× faster than Fade2D.
Re: Exact, parallel 2D Delaunay triangulation for int32 coordinates
#8Great 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.
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...
Re: Exact, parallel 2D Delaunay triangulation for int32 coordinates
#9Nice 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.
Re: Exact, parallel 2D Delaunay triangulation for int32 coordinates
#10Can 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