Khi nào sử dụng Phân vùng không gian nhị phân, Quadtree, Octree?

Question

Gần đây tôi đã tìm hiểu về các cây phân vùng không gian nhị phân và ứng dụng của chúng cho đồ họa 3D và phát hiện xung đột. Tôi cũng đã sử dụng một cách ngắn gọn các tài liệu liên quan đến quadtrees và octrees. Khi nào bạn sử dụng quadtrees trên cây bsp hoặc ngược lại? Họ có hoán đổi cho nhau không? Tôi sẽ hài lòng nếu tôi đã có đủ thông tin để điền vào một bảng như thế này:

  | BSP | Quadtree | Octree 
------------+----------------+------- 
Situation A | X |   | 
Situation B |  |  X | 
Situation C |  |   | X 

gì là A, B, và C?

Answer 1

Không có câu trả lời rõ ràng cho câu hỏi của bạn. Nó phụ thuộc hoàn toàn cách dữ liệu của bạn được tổ chức.

Điều cần lưu ý:

Quadtrees hoạt động tốt nhất cho dữ liệu gần như hai chiều như hiển thị bản đồ trong hệ thống điều hướng. Trong trường hợp này nó nhanh hơn octrees vì ​​nó thích ứng tốt hơn với hình học và giữ cấu trúc nút nhỏ.

Octrees và BVHs (Phân cấp khối lượng biên) được hưởng lợi nếu dữ liệu là ba chiều. Nó cũng hoạt động rất tốt nếu các thực thể hình học của bạn được nhóm lại trong không gian 3D. (xem Octree vs BVH)

Lợi ích của Oc- và Quadtrees là bạn có thể ngừng tạo cây bất cứ khi nào bạn muốn. Nếu bạn muốn render đồ họa bằng cách sử dụng bộ gia tốc đồ họa, nó cho phép bạn chỉ tạo ra các cây trên một mức đối tượng và gửi từng đối tượng trong một cuộc gọi vẽ tới API đồ họa. Điều này thực hiện nhiều hơn tốt hơn so với gửi tam giác cá nhân (một cái gì đó bạn phải làm gì nếu bạn sử dụng BSP-Trees đến mức đầy đủ).

BSP-Cây là trường hợp đặc biệt thực sự. Chúng hoạt động rất tốt trong 2D và 3D, nhưng việc tạo ra các BSP-Trees tốt là một dạng nghệ thuật riêng của nó. BSP-Trees có nhược điểm là bạn có thể phải chia hình học thành các phần nhỏ hơn. Điều này có thể làm tăng tổng số đa giác của tập dữ liệu của bạn. Chúng rất đẹp để dựng hình, nhưng chúng tốt hơn nhiều cho việc dò tìm va chạm và dò tia.

Thuộc tính tốt đẹp của BSP-cây là chúng phân hủy một hình đa giác thành một cấu trúc có thể được hoàn trả hoàn hảo về phía trước (và ngược lại) từ bất kỳ vị trí camera nào mà không thực hiện sắp xếp thực tế. Thứ tự từ mỗi quan điểm là một phần của cấu trúc dữ liệu và được thực hiện trong quá trình biên dịch BSP-Tree.

Điều đó, bằng cách này, là lý do tại sao chúng phổ biến đến 10 năm trước. Quake đã sử dụng chúng vì nó cho phép trình xử lý đồ họa/phần mềm đồ họa không sử dụng bộ đệm z tốn kém.

Tất cả các cây được đề cập chỉ là họ cây. Có những cây thập cẩm lỏng lẻo, cây lai kd-tree và nhiều cấu trúc liên quan khác nữa.

Answer 2

Tôi không có nhiều kinh nghiệm với BSP, nhưng tôi có thể nói rằng bạn nên đi với octrees trên quadtrees khi cảnh bạn đang hiển thị cao. Đó là, chiều cao là hơn một nửa chiều rộng và chiều sâu - quy tắc nhỏ của ngón tay cái. Nói chung, octrees sẽ không mang lại một chi phí lớn hơn quadtrees và họ có tiềm năng để tăng tốc độ những thứ lên một chút khá. YMMV.

Answer 3

Thông thường những điều này không có câu trả lời rõ ràng. Tôi sẽ đề nghị rằng A, B, và C là kết quả của một hàm của kích thước không gian của bạn và số lượng thứ bạn đang phân biệt.

Answer 4

BSP là tốt hơn cho một không gian nhỏ hơn, đơn giản hơn mà bạn chỉ muốn thực hiện. Nếu bạn muốn tất cả các giao lộ cho một tia nhất định, bạn sẽ cần phải nâng cấp lên một quad/octree.

Đối với quadtree so với octree - bạn quan tâm đến bao nhiêu thứ nguyên? Hai chiều có nghĩa là một quadtree, bốn octree. Như đã nói, như quadtree có thể làm việc trong ba không gian, nhưng nếu bạn muốn mỗi kích thước cho một điều trị thích hợp, một octree là con đường để đi.

Answer 5

BSP tốt nhất cho môi trường đô thị.

Một quadtree là tốt nhất cho bạn khi sử dụng bản đồ chiều cao cho địa hình vv

Một octree là tốt nhất cho bạn khi có những khối hình học trong không gian 3d, chẳng hạn như một hệ thống năng lượng mặt trời.

Answer 6

BSP là một tùy chọn tốt để tăng tốc phát hiện va chạm, tùy thuộc vào hương vị bạn sử dụng. Chúng đặc biệt nhanh ở các điểm kiểm tra điểm và đường hoặc tia, hơi kém nhanh hơn và phức tạp hơn một chút đối với những thứ có âm lượng.

Đối với việc sử dụng chúng trong đồ họa, BSPs có khá nhiều lỗi thời. Octrees hoạt động tốt cho những thứ như chọn lọc toàn bộ khả năng hiển thị, cũng giống như cây AABB.

Answer 7

Sự khác biệt thực tế lớn nhất giữa BSP-Trees và các loại cây 3D khác là BSP-Trees có thể tối ưu hơn nhưng chỉ hoạt động trên hình ảnh tĩnh. Điều này là do BSP-Trees nói chung rất chậm để xây dựng, thường mất hàng giờ hoặc ngày cho một cấp độ trò chơi đô thị tĩnh điển hình. Hai (2) lý do chính mà BSP-Trees mất nhiều thời gian hơn để xây dựng là (a) chúng sử dụng các mặt phẳng phân tách không trục, mất nhiều thời gian hơn để tìm kiếm tối ưu, và (b) chúng chia nhỏ hình học trên các ranh giới trục. mặt phẳng phân chia chéo.

Các loại cây 3D khác (Octrees, Quadtrees, kd-tree, Bounding-Volume-Hierarchy) sử dụng khối lượng liên kết trục, và khối lượng (tùy chọn) được phép chồng lên nhau, vì vậy các đối tượng chứa không cần được cắt trên ranh giới khối lượng. Cả hai đều làm cho cây ít tối ưu hơn BSP-cây, nhưng nhanh hơn để xây dựng và dễ thay đổi hơn cho các đối tượng động.

ngoại suy những yếu tố này vào tình huống ... vùng

ngoài trời thường sử dụng cơ quan đại diện đất cao-field dựa, hoặc là heightmaps đơn giản hoặc kỹ thuật geo-mip-mapping phức tạp hơn như ROAM. Bản thân mặt đất không tham gia vào phân vùng không gian 3D, chỉ các vật thể được đặt trên mặt đất.

Thế giới có nhiều trường hợp hình học đơn giản và tương tự (nhà, cây, tiểu hành tinh, v.v.) thường sẽ sử dụng một cây không phải BSP (chẳng hạn như BVH), vì việc đặt hình học thành cây BSP nhân bản và tách hình dạng chi tiết cho mỗi trường hợp. Ngược lại, một lưới tĩnh tùy chỉnh lớn không có sự can thiệp, chẳng hạn như cảnh đô thị hoặc môi trường trong nhà phức tạp, thường sẽ sử dụng BSP-Tree để cải thiện hiệu suất thời gian chạy. Thực tế là BSP-Tree chia tách hình học trên các ranh giới nút là hữu ích để hiển thị hiệu suất, vì các nút BSP có thể được sử dụng như các lô kết xuất tam giác được sắp xếp trước. BSP-Tree cũng có thể được tối ưu hóa cho tắc nghẽn, tránh sự cần thiết phải vẽ các phần của BSP-Tree được biết là phía sau hình học khác.

Xem thêm: Octree vs BVH, Bounding Volume Hierarchy Tutorial, BSP Tutorial.