Cấu trúc tăng tốc tốt cho các thử nghiệm hình cầu ray với các quả cầu di chuyển

Question

Tôi đang tìm cấu trúc tăng tốc thích hợp để thực hiện các thử nghiệm giao cắt ray-sphere (trong một trò chơi). các điều kiện sau được áp dụng:

-Có arround 100 lĩnh vực và 100 tia để thử nghiệm với nhau mỗi khung

-the lĩnh vực di chuyển trong mỗi khung hình, do đó, làm các tia

-Có thể được tia/lĩnh vực thêm/gỡ bỏ trong mỗi khung hình (nhưng hầu hết trong số họ sẽ giống nhau ở giữa hai khung hình, chỉ cần di chuyển nhẹ)

điều -whole là trong không gian 3D

một KD-Tree là rất tốt cho giao Ray thử nghiệm, nhưng kể từ khi hình cầu di chuyển, tôi phải xây dựng lại KD-Tree trong mỗi khung hình, tốn kém là

một cây Oct dễ bảo trì hơn, nhưng rất không hiệu quả đối với các thử nghiệm giao cắt tia.

100 tia chống lại 100 lĩnh vực dường như không có nhiều, nhưng tôi đang mã hóa về tài nguyên rất thấp, vì vậy tôi đang tìm kiếm một số khả năng tăng tốc cho rằng

Bất cứ ai có thể cho tôi một số gợi ý về điều đó?

Answer 1

100x100 = 10k, lực được tối ưu hóa không có vẻ không mạch lạc, đặc biệt là thử nghiệm giao cắt tia/hình cầu chỉ liên quan đến cộng/nhân. Bạn luôn có thể tính toán trước tất cả các vectơ tia chuẩn hóa trước vòng lặp chính.

Nếu bạn giả định rằng bạn sống trong vũ trụ bị giới hạn và mật độ không gian của các hình cầu và tia tương đối đồng đều, bạn có thể sử dụng lưới không gian cố định (cố định oct-tree) - một cái gì đó giống như lưới ô 16x16x16, hoặc more--, và:

• precompute cho mỗi lĩnh vực giao nhau các tế bào (dễ dàng để tính toán, chỉ liên quan đến vài thêm và so sánh), lưu trữ trong mỗi tế bào danh sách các lĩnh vực giao nhau,
• cho mỗi ray, trong vòng lặp:
  • tính danh sách các ô y crosses (một phương pháp dựa trên thuật toán của Bresenham có thể thực hiện thủ thuật)
  • thực hiện kiểm tra giao cắt cho tất cả các hình cầu trong danh sách ô này.

Bằng cách đó bạn không phải lưu trữ bất kỳ tia nào trong bất kỳ cây nào, chỉ hình cầu. Hiệu quả của phương pháp này phụ thuộc vào kích thước tế bào kích thước/kích thước hình cầu, nếu bạn không có quá nhiều phân tán về kích thước hình cầu thì đó có thể là một gợi ý tốt.

Nếu lĩnh vực không bắt chéo nhau kích thước khác và hình cầu có tối thiểu, thậm chí bạn có thể bị ràng buộc danh sách cầu trong danh sách di động (số thích hợp là trái như một exercice cho người đọc ...)

HTH