Trong khoa học máy tính, phương pháp gọi là phân chia không gian nhị phân (Binary Space Partitioning - BSP) được dùng để chia đệ quy một không gian thành hai tập lồi (convex sets) bằng cách dùng siêu phẳng (hyperplanes) làm phân vùng. Quá trình phân chia này tạo ra biểu diễn các đối tượng trong vùng dưới dạng cấu trúc dữ liệu cây gọi là cây BSP.
Phân chia không gian nhị phân được phát minh trong bối cảnh đồ họa 3D máy tính năm 1969, nơi cấu trúc cây BSP cho phép truy cập nhanh thông tin không gian về các đối tượng trong một cảnh (scene) hữu ích cho rendering, ví dụ: sắp xếp đối tượng từ trước ra sau (front-to-back) tương đối với người xem tại vị trí cho trước. Các ứng dụng khác của BSP bao gồm: thực hiện phép toán hình học với hình dạng (hình học rắn xây dựng - constructive solid geometry) trong CAD, phát hiện va chạm trong game 3D và robotics, ray tracing, và các ứng dụng khác liên quan đến xử lý cảnh không gian phức tạp.
Tổng quan
Phân chia không gian nhị phân được coi là quy trình chung chia đệ quy một cảnh thành hai cho đến khi phân vùng thỏa mãn một hoặc nhiều yêu cầu. Có thể xem nó như tổng quát hóa các cấu trúc cây không gian khác như k-d trees và quadtrees, nơi siêu phẳng phân chia không gian có thể có bất kỳ hướng nào, thay vì căn chỉnh với trục tọa độ như k-d trees hay quadtrees. Khi dùng trong đồ họa máy tính để render cảnh bao gồm đa giác phẳng, các mặt phẳng phân vùng thường được chọn trùng với mặt phẳng xác định bởi đa giác trong cảnh. Lựa chọn cụ thể của mặt phẳng phân vùng và tiêu chí kết thúc quá trình phân vùng thay đổi tùy thuộc vào mục đích của cây BSP. Ví dụ, trong rendering đồ họa máy tính, cảnh được chia cho đến khi mỗi nút của cây BSP chỉ chứa đa giác có thể render theo thứ tự tùy ý. Khi dùng culling mặt sau (back-face culling), mỗi nút do đó chứa một tập lồi các đa giác, trong khi render đa giác hai mặt, mỗi nút chỉ chứa đa giác trong một mặt phẳng đơn. Trong phát hiện va chạm hoặc ray tracing, cảnh có thể được chia thành các primitive mà trên đó kiểm tra va chạm hoặc giao điểm tia là đơn giản.
Tạo cây (Generation)
Cài đặt kinh điển (canonical) của cây BSP là để render đa giác (hai mặt, tức không có back-face culling) với thuật toán painter's algorithm (thuật toán họa sĩ). Mỗi đa giác được chỉ định một mặt trước và mặt sau (có thể chọn tùy ý) chỉ ảnh hưởng cấu trúc cây chứ không ảnh hưởng kết quả yêu cầu. Cây như vậy được xây dựng từ danh sách không sắp xếp tất cả đa giác trong một cảnh. Thuật toán đệ quy xây dựng cây BSP từ danh sách đa giác đó là:
- Chọn một đa giác A từ danh sách.
- Tạo nút N trong cây BSP, thêm A vào danh sách đa giác tại nút đó.
- Với mỗi đa giác khác trong danh sách:
- Nếu đa giác đó nằm hoàn toàn phía trước mặt phẳng chứa A, di chuyển nó sang danh sách nút phía trước A.
- Nếu nằm hoàn toàn phía sau, di chuyển sang danh sách nút phía sau A.
- Nếu bị cắt bởi mặt phẳng chứa A, tách nó thành hai đa giác và di chuyển chúng vào danh sách phía sau và phía trước tương ứng.
- Nếu nằm trong mặt phẳng chứa A, thêm vào danh sách đa giác tại nút N.
- Áp dụng thuật toán này cho danh sách đa giác phía trước A.
- Áp dụng thuật toán này cho danh sách đa giác phía sau A.