2 ms·
Great project! Are vertex insertion and deletion also supported/accelerated? What compromises are keeping this constrained to 32-bit? It seems like you could
by hingler36 2mo 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.
- marmakoide 2mo agoNot 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 2mo ago64 bit cpus have 128 bit mul results if that’s what you mean
- delusional 2mo agoTriangulation 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/141d979b18e296ac7f7b6ba5e7d89d294c7372c9/src/topology.cpp#L837 https://github.com/morishuz/delaunay32/blob/141d979b18e296ac...
- morishuz 2mo agothanks! (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.