int32 좌표 전용 정확한 병렬 2D 들로네 삼각분할 라이브러리 Delaunay32 공개

정점 삽입/삭제도 지원하는지 궁금하고, 32비트로 제한한 이유가 뭔지 궁금함. 비트를 늘리면 양자화 오차를 줄일 수 있을 텐데 SIMD 최적화 때문에 32비트에 묶인 거라면 이해는 감

저자는 아니지만, 32비트 좌표로 동작하려면 곱셈 같은 연산이 64비트로 확장돼야 하는데, 64비트 CPU에서 하드웨어 지원 한계가 거기까지인 것 같음

내가 작성자인데, 현재는 배치 삼각분할기라서 정점 삽입/삭제는 지원 안 하고 다시 빌드해야 함. SIMD 때문이 아니라 원 판정에 제곱과 곱셈이 들어가서 32비트 입력도 내부적으로 128비트 임시 결과가 필요하고, 64비트를 정확히 지원하려면 256비트 중간값이 필요해서 속도와 이식성 면에서 32비트가 지금은 좋은 절충점이라고 생각함

3D 들로네 사면체분할도 만들어보면 좋겠음 ㅋㅋ

사이트 보니까 대용량 점집합에서 delaunator-cpp보다 10배 이상, Fade2D보다 4배 빠르다고 나와있음

나도 int32 좌표용 들로네 라이브러리를 Rust로 만들어서 wasm으로 컴파일하고 시각화까지 붙였음. 클릭으로 점 추가/삭제하고 애니메이트 누르면 용암램프 같은 느낌 남

저것도 괜찮아 보임

예전부터 사실상 가장 빠르다고 알려진 triangle(cs.cmu.edu)과 비교해볼 수 있는지 궁금함. int 전용은 아니지만 궁금해서

100만 점 기준으로 M1에서 측정했을 때 단일 스레드로 4배, 멀티스레드로 11배 정도 delaunay32가 triangle보다 빠름

제약 조건 있는 들로네(constrained delaunay)를 지원하는 좋은 라이브러리를 찾고 있었는데 유망해 보임. 근데 벤치마크가 멀티스레딩 포함이라 성능 비교가 어려운데, 단일 스레드 기준도 보고 싶음

리포에 벤치마크 도구가 있어서 직접 돌려보면 멀티 vs 싱글 스레드랑 delaunator-cpp(싱글 스레드 전용)까지 비교 가능함. 100만 점 기준 싱글 스레드로 147150ms, delaunator-cpp는 540555ms라 약 3.7배 빠르고, 8스레드 자동 모드는 53~54ms 나옴

int32 제약이 실제로 문제가 되는 상황이 있는지 궁금함. 40억 단계 정도면 64비트 float 기준 일반 문제에서도 충분히 근사가 잘 될 것 같은데 내 생각이 틀렸는지, 그리고 int64로 쉽게 확장 가능한지도 궁금함