BSP-деревья могут быть абстрагированы в любое N-мерное пространство, поскольку по определению N-мерная гиперплоскость разделит пространство на две части. Другими словами, для данной точки в N-мерном пространстве она должна находиться либо на гиперплоскости, либо в одном из пополам пространств, которые гиперплоскость создает в N-мерном пространстве.
Для 2D, дерево BSP будет создано путем рисования линии, а затем проверки, на какой стороне этой линии была точка. Это потому, что линия делит пополам 2D-пространство. Для 3D вам понадобится плоскость, которая обычно формируется из нормали к многоугольной поверхности, которую вы используете в качестве теста.
Итак, ваш алгоритм будет выглядеть примерно так:
- Создать очередь, содержащую все полисы из куба. Лучше было бы случайным образом добавлять polys в очередь, а не в каком-то порядке.
- Извлечь поли из начала очереди ... сделать это "корнем" дерева BSP.
- Создать нормаль из этого поли
- Вставьте еще один поли из очереди
- Проверьте, находятся ли все точки в этом поли перед или позади нормали, созданной из корня.
- Если они все впереди, то сделайте этого поли правым потомком корня. Если они все позади, сделайте это поли левым потомком корня.
- Если все точки в многоугольнике не находятся ни впереди, ни позади плоскости, определяемой нормалью корневого многоугольника, то вам нужно разделить многоугольник на две части для частей, которые находятся впереди и позади плоскости. Для двух новых полисов, созданных из этого разбиения, добавьте их в конец очереди и повторите с шага № 4.
- Вставьте еще один поли из очереди.
- Проверка этого поли на корень. Поскольку у корня есть дочерний элемент, после того, как вы проверите, находится ли поли перед или за корнем (имея в виду шаг # 7, который может потребовать разделения), протестируйте поли с дочерним узлом, который находится справа, если он находится в -front, или дочерний узел слева, если он позади. Если дочерний узел отсутствует, вы можете прекратить движение по дереву и добавить многоугольник к дереву как этот дочерний узел.
- Для любого дочернего узла, в который вы попадаете, где текущий поли не находится спереди или сзади, вам нужно выполнить разбиение на шаге № 7, а затем вернуться к шагу № 4.
- Продолжайте повторять этот процесс, пока очередь не станет пустой.
Код для этого алгоритма будет концептуально выглядеть примерно так:
struct bsp_node
{
std::vector<poly_t> polys;
bsp_node* rchild;
bsp_node* lchild;
bsp_node(const poly_t& input): rchild(NULL), lchild(NULL)
{
polys.push_back(input);
}
};
std::queue<poly_t> poly_queue;
//...add all the polygons in the scene randomly to the queue
bsp_node* bsp_root = new bsp_node(poly_queue.front());
poly_queue.pop();
while(!poly_queue.empty())
{
//grab a poly from the queue
poly_t current_poly = poly_queue.front();
poly_queue.pop();
//search the binary tree
bsp_node* current_node = bsp_root;
bsp_node* prev_node = NULL;
bool stop_search = false;
while(current_node != NULL && !stop_search)
{
//use a plane defined by the current_node to test current_poly
int result = test(current_poly, current_node);
switch(result)
{
case COINCIDENT:
stop_search = true;
current_node->polys.push_back(current_poly);
break;
case IN_FRONT:
prev_node = current_node;
current_node = current_node->rchild;
break;
case BEHIND:
prev_node = current_node;
current_node = current_node->lchild;
break;
//split the poly and add the newly created polygons back to the queue
case SPLIT:
stop_search = true;
split_current_poly(current_poly, poly_queue);
break;
}
}
//if we reached a NULL child, that means we can add the poly to the tree
if (!current_node)
{
if (prev_node->rchild == NULL)
prev_node->rchild = new bsp_node(current_poly);
else
prev_node->lchild = new bsp_node(current_poly);
}
}
После того, как вы завершили создание дерева, вы можете выполнить поиск дерева по порядку и отсортировать полигоны задом наперед. Не имеет значения, являются ли объекты прозрачными или нет, так как вы сортируете на основе самих полисов, а не их свойств материала.