Thuật toán để tạo lưới tam giác từ một đám mây điểm

Question

Trong một số chương trình mô phỏng, chúng tôi tạo ra các bề mặt đối tượng theo điểm, mỗi điểm có tọa độ 3D và vectơ biểu diễn bình thường với bề mặt tại điểm đó. Đối với mục đích trực quan, chúng tôi muốn tạo ra một lưới bao gồm các hình tam giác; mỗi ba điểm gần tạo thành một hình tam giác với bình thường của nó. Sau đó, chúng tôi có thể gửi thông tin này đến một số chương trình trực quan hóa tiêu chuẩn, hiển thị bề mặt như VMD (Visual Molecular Dynamics).

Chúng tôi tự hỏi đó là thuật toán nhanh nhất/có sẵn để thực hiện việc này.

Answer 1

Hãy xem Jonathan Shewchuk 's làm việc, đặc biệt là trên giấy tờ nổi tiếng của ông (cùng với các đồng nghiệp của ông) và triển khai của:

• Streaming Computation of Delaunay Triangulations

• A Two-Dimensional Quality Mesh Generator and Delaunay Triangulator

Có cũng triển khai nhanh các đám mây điểm chưa được thực hiện trong Thư viện điểm đám mây (PCL). Kiểm tra bản trình bày của họ trên Fast triangulation of unordered point clouds.

Answer 2

Thuật toán poisson của Misha Kazhdan có thể hoạt động tốt trên dữ liệu của bạn. Trang phần mềm của nó là here. Lưu ý rằng cũng tồn tại một phiên bản CGAL. Hướng dẫn sử dụng là here và sẵn sàng sử dụng Windows demo here (miễn là bạn đã cài đặt các dlls) này.

Answer 3

Lưu ý rằng các tam giác Delaunay có thể không phù hợp với ứng dụng của bạn trong các tam giác Delaunay không phù hợp với các vấn đề 3D thực sự (tức là khi các điểm được phân phối tốt trong R3). Chúng phù hợp hơn với các vấn đề đa tạp 2D (tức là địa hình, v.v.).

Để tạo các bề mặt trong R3, hãy xem công việc của Hugues Hoppe và công trình "tái tạo bề mặt" của ông.

Tái tạo bề mặt được sử dụng để tìm một bề mặt được chia lưới để vừa với đám mây điểm; tuy nhiên, phương pháp này mang lại số lượng tam giác cao. Nếu đây là vấn đề, bạn có thể áp dụng kỹ thuật giảm lưới để giảm số lượng đa giác theo cách giảm thiểu lỗi. Ví dụ, bạn có thể xem xét phương pháp decimation của OpenMesh.

Hugues Hoppe

OpenMesh