Trong khoa học máy tính, một phương pháp được gọi là phân vùng không gian nhị phân (BSP) được thực hiện để chia nhỏ đệ quy một không gian thành hai tập lồi bằng cách triển khai siêu mặt phẳng làm phân vùng. Quá trình chia nhỏ này dẫn đến việc 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 được gọi là cây BSP.
Phân vùng không gian nhị phân được phát minh trong bối cảnh đồ họa máy tính 3D vào năm 1969, trong đó cấu trúc của cây BSP cho phép thông tin không gian về các đối tượng trong cảnh hữu ích trong việc kết xuất, chẳng hạn như các đối tượng được sắp xếp từ trước ra sau với tôn trọng người xem tại một địa điểm nhất định, để được truy cập nhanh chóng. Các ứng dụng khác của BSPinclude:hoàn thành các phép toán hình học với các hình dạng (hình học rắn xây dựng) trong CAD, phát hiện va chạm trong trò chơi điện tử 3D và người máy, dò tia và các ứng dụng khác liên quan đến việc xử lý các cảnh không gian phức tạp.
Tổng quan
Phân vùng không gian nhị phân được coi như một quá trình chung chia một cách đệ 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. Nó có thể được xem như một sự tổng quát hóa của các cấu trúc cây không gian khác như cây k-d và cây phần tư, một trong đó các siêu mặt phẳng phân chia không gian có thể có bất kỳ hướng nào, thay vì được căn chỉnh với các trục tọa độ như chúng ở trong cây k-d hoặc góc phần tư. Khi được triển khai trong đồ họa máy tính để hiển thị các cảnh bao gồm các đa giác phẳng, các mặt phẳng phân vùng thường được chọn để trùng với các mặt phẳng được xác định bởi các đa giác trong cảnh. Sự lựa chọn cụ thể của mặt phẳng phân vùng và tiêu chí để hoàn thành quá trình phân vùng khác nhau tùy thuộc vào mục đích của cây BSP. Ví dụ, trong kết xuất đồ họa máy tính, cảnh được chia cho đến khi và trừ khi mỗi nút của cây BSP chỉ bao gồm các đa giác có thể hiển thị theo thứ tự tùy ý. Khi thực hiện chọn lọc mặt sau, mỗi nút bao gồm một tập hợp các đa giác lồi, trong khi khi hiển thị các đa giác hai mặt, mỗi nút của cây BSP chỉ bao gồm các đa giác trong một mặt phẳng duy nhất. Trong phát hiện va chạm hoặc theo dõi tia, một cảnh có thể được chia thành một số nguyên thủy mà các bài kiểm tra va chạm hoặc giao cắt tia là đơn giản.
Thế hệ
Việc triển khai hợp quy của cây BSP là để hiển thị đa giác (có hai mặt, nghĩa là không có mặt sau) với sự trợ giúp của thuật toán của họa sĩ. Mỗi đa giác được chỉ định với một mặt trước và một mặt sau có thể được chọn tùy ý và chỉ ảnh hưởng đến cấu trúc của cây chứ không ảnh hưởng đến kết quả cần thiết. Một cái cây như vậy được xây dựng từ một danh sách chưa được sắp xếp của tất cả cá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.
- Xây dựng một nút N trong cây BSP và thêm A vào danh sách các đa giác tại nút đó.
- Đối với đa giác là nhau của 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, hãy di chuyển đa giác đó đến danh sách các nút phía trước A.
- Nếu đa giác đó nằm hoàn toàn phía sau mặt phẳng chứa A, hãy di chuyển đa giác đó đến danh sách các nút phía sau P.
- Nếu đa giác đó giao với mặt phẳng bao gồm A, hãy chia đa giác đó thành hai đa giác và chuyển chúng đến danh sách các đa giác tương ứng nằm phía sau và phía trước P.
- Nếu đa giác đó nằm trong mặt phẳng chứa A, hãy thêm nó vào danh sách các đa giác tại nút N.
- Áp dụng thuật toán này cho danh sách các đa giác nằm trước A.
- Áp dụng thuật toán này cho danh sách các đa giác nằm sau A.