Tôi đang bối rối. Cũng không bối rối, nhiều như không muốn làm 6 chương trình thử nghiệm để xem thuật toán nào là tốt nhất. Vì vậy, tôi nghĩ rằng tôi muốn hỏi bạn bè chuyên gia của tôi ở đây tại SO để cho tôi những lợi ích của kinh nghiệm của họ.Thuật toán tốt nhất để phát hiện xung đột hiệu quả giữa các đối tượng
Kịch bản là cảnh 3D có diện tích khá lớn so với kích thước của các đối tượng bên trong. Có khả năng hàng ngàn đối tượng trong cảnh. Các đối tượng có kích thước khác nhau từ mười phần của một đơn vị lên đến khoảng 10 đơn vị, nhưng không lớn hơn (hoặc nhỏ hơn). Các đối tượng có xu hướng được nhóm lại với nhau, nhưng các cụm đó có khả năng xuất hiện ở bất kỳ đâu trong cảnh. Tất cả các đối tượng đều năng động và di chuyển. Các cụm có xu hướng di chuyển cùng nhau, nhưng khi vận tốc của chúng có thể không giống nhau. Ngoài ra còn có hình học tĩnh để xem xét. Mặc dù có số lượng lớn các đối tượng động, cũng có một số đối tượng tĩnh trong cảnh (các đối tượng tĩnh có xu hướng là một hoặc hai đơn đặt hàng lớn hơn các đối tượng động).
Bây giờ, điều tôi muốn là cấu trúc dữ liệu không gian để phát hiện va chạm hiệu quả cho tất cả các mục trong cảnh. Nó sẽ là tuyệt vời nếu thuật toán cũng hỗ trợ truy vấn hiển thị quá, cho đường dẫn rendering. Để đơn giản, giả sử rằng phát hiện va chạm ở đây là giai đoạn rộng (nghĩa là tất cả các đối tượng động chỉ là các hình cầu hoàn hảo).
Vì vậy, trong nghiên cứu của tôi, tôi có thể sử dụng một trong số:
(1) octree (2) Loose octree (3) Tuyến tính octree (+ lỏng) (4) KD Tree (5) BSP Cây (6) Hashing
Cho đến nay (6) là lần duy nhất tôi đã thử. Đó là thực sự hoàn toàn tuyệt vời về tốc độ (8192 mục va chạm kiểm tra trong dưới 1ms trên hệ thống của tôi) nếu các đối tượng trong cảnh đang trên trung bình đồng đều trải ra. Nó không phải là một thuật toán tốt như vậy nếu tất cả các đối tượng được biến thành một khu vực nhỏ hơn, mà tôi cho là có thể.
Có ai có một số thông tin chi tiết về cách sử dụng hoặc bất kỳ thủ thuật nào tôi có thể sử dụng để tăng tốc độ không? Tôi nghĩ rằng bất cứ điều gì xảy ra tôi chỉ có thể sử dụng một cây BSP riêng biệt cho hình học tĩnh. Tôi cho rằng "quả cầu" năng động là những gì tôi quan tâm nhất ở đây. Lưu ý: không có CUDA, đây chỉ là CPU: p.
Cảm ơn
EDIT: Ok, nhờ Floris, tôi đã tìm thêm thông tin về cây AABB. Có một cuộc thảo luận cũ về GameDev tại đây: http://www.gamedev.net/topic/308665-aabb-tree---wheres-the-poly-o_o/. Trông giống như một sự thỏa hiệp tốt.
EDIT cuối cùng: Quyết định không phát minh lại bánh xe. Có thể thư viện vật lý đạn sẽ làm tất cả điều này cho tôi (nó có cây AABB trong nó, có lẽ cũng được tối ưu hóa quá).
Bạn có thể bỏ qua KD-tree cho cảnh động. Công việc của cây KD trên các tập dữ liệu tĩnh, bạn sẽ phải xây dựng lại toàn bộ cây (phụ) mỗi lần một phần tử di chuyển – SingleNegationElimination
Có, có vẻ như nó quá chuyên sâu để sử dụng trong các cảnh động. – Robinson