Будут ли BSP-деревья работать с отдельными прозрачными объектами?

BSP-деревья можно абстрагировать до любого N-мерного пространства, поскольку по определению N-мерная гиперплоскость делит пространство пополам на две части. Другими словами, для данной точки в N-мерном пространстве она должна находиться либо на гиперплоскости, либо в одном из пространств, разделенных пополам, которые гиперплоскость создает в N-мерном пространстве.

Для 2D дерево BSP будет создано путем рисования линии, а затем проверки того, на какой стороне этой линии находится точка. Это потому, что линия делит двумерное пространство пополам. Для 3D вам понадобится плоскость, которая обычно формируется из нормали к многоугольной поверхности, которую вы используете в качестве теста.

Таким образом, ваш алгоритм будет примерно следующим:

1. Создайте очередь, содержащую все полигоны из куба. Было бы лучше добавлять полигоны в очередь случайным образом, а не в каком-то порядке.
2. Вытащите полигон из начала очереди... сделайте его "корнем" BSP-дерева.
3. Создайте нормаль из этого полигона
4. Вытащите еще один полигон из очереди
5. Проверьте, все ли точки в этом полигоне находятся впереди или позади нормали, созданной из корня.
6. Если они все впереди, то сделайте этот полигон правым дочерним элементом корня. Если они все позади, сделайте этот полигон левым дочерним элементом корня.
7. Если все точки многоугольника не находятся впереди или позади плоскости, определяемой нормалью корневого многоугольника, тогда вам нужно будет разделить полигон на две части для частей, которые находятся впереди и позади плоскости. Для двух новых полигонов, созданных из этого разделения, добавьте их в конец очереди и повторите, начиная с шага №4.
8. Вытащите еще один полигон из очереди.
9. Протестируйте этот полигон против корня. Поскольку у корня есть дочерний узел, как только вы проверите, находится ли полигон впереди или позади корня (имея в виду шаг № 7, который может потребовать разделения), проверьте полигон на дочернем узле, который находится справа, если он находится в -front или дочерний узел слева, если он сзади. Если дочерней вершины нет, то можно перестать двигаться по дереву и добавить полигон как к дереву в качестве дочерней.
10. Для любого дочернего узла, с которым вы столкнулись, где текущий полигон не находится впереди или позади, вам нужно будет выполнить разделение на шаге № 7, а затем вернуться к шагу № 4.
11. Продолжайте повторять этот процесс, пока очередь не станет пустой.

Код для этого алгоритма концептуально будет выглядеть примерно так:

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);
    }
}

После того, как вы завершили создание дерева, вы можете выполнить поиск в дереве по порядку и отсортировать полигоны от конца к началу. Неважно, прозрачны объекты или нет, поскольку вы сортируете их по самим полигонам, а не по свойствам их материалов.