Cấu trúc dữ liệu/phương pháp tiếp cận hiệu quả raytracing

Question

Tôi đang viết 3D raytracer như một dự án học tập cá nhân (Enlight) và đã gặp phải một vấn đề thú vị liên quan đến kiểm tra giao cắt giữa tia và cảnh vật thể.

Tình hình là:

• Tôi có một số nguyên thủy mà tia có thể giao nhau với (hình cầu, hộp, máy bay, vv) và các nhóm đó. Nói chung tôi gọi những vật thể này.
• Tôi muốn có thể cảnh đối tượng nguyên thủy với biến đổi affrary tùy ý bằng cách gói chúng trong một đối tượng Transform (quan trọng, điều này sẽ cho phép nhiều trường hợp cùng nguyên thủy) được sử dụng ở các vị trí khác nhau trong cảnh. không thay đổi)
• Đối tượng cảnh có thể được lưu trữ trong hệ thống phân cấp khối giới hạn (tức là tôi đang làm phân vùng không gian)
• Bài kiểm tra giao điểm của tôi hoạt động với Ray đối tượng đại diện cho phân đoạn một phần (vector bắt đầu, vector hướng chuẩn hóa, khoảng cách bắt đầu , khoảng cách kết thúc)

Vấn đề là khi một tia chạm vào hộp giới hạn của một đối tượng Transform, có vẻ như cách duy nhất để thực hiện kiểm tra giao cắt với các nguyên thủy được biến đổi chứa bên trong là biến đổi Ray thành không gian phối hợp được biến đổi. Điều này là dễ dàng đủ, nhưng sau đó nếu tia không trúng bất kỳ đối tượng chuyển đổi tôi cần phải quay trở lại ban đầu Ray để tiếp tục theo dõi. Kể từ khi chuyển đổi có thể được lồng nhau, điều này có nghĩa là tôi phải duy trì một ngăn xếp toàn bộ Ray s cho mỗi lần giao lộ được thực hiện.

Đây là khóa học trong vòng lặp bên trong của toàn bộ ứng dụng và nút cổ chai hiệu suất chính. Nó sẽ được gọi là hàng triệu lần một giây vì vậy tôi muốn giảm thiểu sự phức tạp/tránh phân bổ bộ nhớ không cần thiết.

Có cách nào thông minh để tránh phải phân bổ mới Ray s/giữ ngăn xếp Ray không?

Hoặc có cách nào thông minh hơn để làm điều này hoàn toàn không?

Answer 1

Hầu hết thời gian theo dõi tia, bạn có vài trăm (nghìn) vật thể và một vài tia sáng nữa. Có lẽ hàng triệu tia. Trong trường hợp đó, bạn nên xem loại tính toán nào bạn có thể chi tiêu cho các đối tượng để làm cho các tia sáng tương tác với chúng nhanh hơn/dễ dàng hơn.

Bộ nhớ cache sẽ rất hữu ích khi đề xuất boyfarrell. Nó có thể có ý nghĩa để không chỉ tạo ra các chuyển đổi chuyển tiếp và đảo ngược trên các đối tượng mà sẽ di chuyển chúng đến hoặc từ khung toàn cầu, mà còn để giữ một bản sao của đối tượng trong khung toàn cầu. Nó làm cho nó đắt tiền hơn để tạo ra các đối tượng hoặc di chuyển chúng (vì các thay đổi biến đổi và do đó làm các bản sao khung toàn cầu được lưu trong bộ nhớ cache) nhưng điều đó có lẽ không sao.

Nếu bạn cast N tia và có M đối tượng và N >> M thì nó đứng lên lý do rằng mọi đối tượng sẽ có nhiều tia đánh nó. Nếu chúng ta giả định mỗi tia chiếu vào vật thì mọi vật đều có tia N/M tấn công nó. Điều đó có nghĩa là chuyển đổi các tia N/M cho từng đối tượng, nhấn thử nghiệm và có thể đảo ngược nó trở lại. Hoặc N/M biến đổi cho mỗi đối tượng ở mức tối thiểu. Nhưng nếu chúng ta nhớ cache đối tượng đã chuyển đổi, chúng ta có thể thực hiện một phép biến đổi duy nhất cho mỗi đối tượng để tới khung toàn cục và sau đó không cần thêm bất kỳ thứ gì. Ít nhất là cho thử nghiệm hit.

Answer 2

Xác định nguyên thủy của bạn ở dạng cơ sở của chúng (thang điểm thống nhất, căn giữa 0,0,0, không xoay) và sau đó di chuyển chúng trong cảnh bằng cách sử dụng phép biến đổi. Cache kết quả của việc chuyển đổi hoàn toàn về phía trước và ngược lại trong mỗi đối tượng. (Đừng quên các vectơ thông thường, bạn sẽ cần chúng để phản xạ)

Điều này sẽ cho bạn khả năng kiểm tra lần truy cập bằng cách sử dụng toán đơn giản (bạn đảo ngược chuyển đổi tia thành không gian đối tượng và tính toán với đối tượng dạng cơ sở) và sau đó biến đổi điểm nhấn và vector phản xạ có thể trở lại không gian thế giới thực bằng cách sử dụng phép biến đổi khác.

Bạn sẽ cần phải tính toán giao lộ với tất cả các đối tượng trong cảnh và chọn lần truy cập gần nhất với nguồn gốc tia (nhưng không phải ở khoảng cách âm). Để tăng tốc độ này nhiều hơn, hãy đặt nhiều đối tượng vào "các hộp giới hạn" sẽ rất đơn giản để tính toán cú đánh và sẽ truyền tia sáng thực tới các vật thể kèm theo nếu trúng (nhưng tất cả các đối tượng vẫn sẽ sử dụng các ma trận precomputed của chúng).