Thuật toán triangulation Delaunay có sẵn nhanh nhất cho GPU

Question

Thuật toán triangulation Delaunay có sẵn nhanh nhất cho GPU là gì? Hoặc tổng quát hơn, song song

Answer 1

Hãy cẩn thận với GPU: Các tam giác Delaunay yêu cầu thử nghiệm định hướng. Chúng không hoạt động đáng tin cậy với số học dấu chấm động và có thể khó để đối phó với vấn đề đó bằng cách sử dụng GPU. Việc quản lý bộ nhớ cũng rất quan trọng.

Bạn có thể muốn thử http://www.geom.at/fade2d/html/ là một trong số các triển khai luồng đơn lẻ nhanh nhất .

Answer 2

2D Delaunay triangulation

GPU-DT là việc thực hiện 2D Delaunay nhanh nhất cho GPU.

Nó xây dựng sơ đồ Voronoi kỹ thuật số trong 2D bằng cách sử dụng GPU Thuật toán dải song song. Tiếp theo nó sửa lỗi và nhân đôi điều này để có được một tam giác 2D. Cuối cùng, nó thực hiện cạnh song song trên GPU để có được tam giác 2D Delaunay.

3D Delaunay triangulation

gStar4D là một thực hiện nhanh chóng và mạnh mẽ của công nghệ 3D Delaunay cho GPU.

Tương tự như GPU-DT, thuật toán này xây dựng sơ đồ Voronoi kỹ thuật số 3D đầu tiên. Tuy nhiên, trong mô hình 3D, điều này không thể được phân tách thành một tam giác do các vấn đề hình học và hình học. Thay vào đó, gStar4D sử dụng thông tin vùng lân cận từ sơ đồ này để tạo các ngôi sao được nâng lên 4D và thực hiện sao splay trên chúng một cách hiệu quả trên GPU. Bằng cách giải nén thân tàu thấp hơn từ đó, tam giác 3D Delaunay thu được.

Giải pháp thay thế nhanh hơn là gDel3D, là thuật toán GPU-CPU lai.

Nó thực hiện chèn song song và lật trên GPU. Kết quả là gần Delaunay. Sau đó nó sửa lỗi kết quả này bằng cách sử dụng phương thức splaying sao bảo thủ trên CPU.

Tất cả các phương pháp này đều mạnh mẽ, vì vậy chúng có thể xử lý bất kỳ loại đầu vào thoái hóa nào.