Вот вам две картинк, для понимания сути процесса.
Первая это VHLT, вторая QBSP2. Точнее разница между ними только в одной функции ChoosePlaneFromList. Немного теории о том, как строится дерево. Слишком большие узлы (например на начальном этапе - вся карта), разрубаются тупо посередине, в противном случае дерево разбалансируется. Это уменьшит число нодов и лифов, но увеличит глубину рекурсии и среднее время доступа по дереву. Дальше, когда больших узлов уже не осталось (узел для простоты понимания - ббокс, коробка), мы выбираем секущую плоскость при помощи этой функции.
Для минимизации увеличения числа полигонов (после того, как секущая ноды их разделит), логично выбирать плоскость, которая сделает как можно меньше разрезов. Причём плоскость выбирается не произвольная, а из тех, что уже прилинкованы к данной ноде. Для удобства они сформированы в цепочки, каждая из которых относится к определённой плоскости. Т.е. surface_t - это цепочка face_t, у которых общая плоскость. Кол-во surface_t зависит от размера ноды, к концу построения BSP она всё меньше и меньше. Задача заключается в том, чтобы при помощи одного surface_t разрубить последовательно фейсы всех остальных surface_t и подсчитать кол-во разрубов. Чем их меньше - тем соответственно лучше. Второй критерий - предпочтение отдается аксиальным плоскостям, по вполне понятной причине - на квадратных фейсах легче лайтмапу контролировать, да и места она меньше занимает. Ну и вообще доступ к дереву быстрее. Поскольку идёт проверка NxN, задача требует весьма много времени, единственная оптимизация которой заключается в том, что вместо реального разрезания используется прикидка, что получится и применить к фейсу секущую. Ну видели вероятно функцию WindingOnPlaneSide. Она выдаёт варианты - плоскость сзади фейса, плоскость спереди фейса, плоскость рассекла фейс. Последний случай как раз и есть деление. На небольших картах халфы, даже безо всяких оптимизаций BSP работает быстро.
Но вы попробуйте тот же grass_test и будете очень удивлены, он и по три минуты может считать. Китайцу это не понравилось и он решил это дело ускорить. Для ускорения он построил простейшее BSP дерево из входных плоскостей (но без разрубания, а то бы получилось падение скорости), просто отсортировав их по принципу эти сзади, эти спереди.
Ну вообщем приблизительно. Прирост эта замута действительно даёт, по словам китайца до 90%. Заодно он же вывел формулу баланса дерева.
Всё бы ничего, но результат применения дерева вы видите на первом скриншоте. Если не сравнивать его со вторым, то можно смело сказать, что освещение в порядке. Но после сравнения, становится понятно, что на первом дикая грязь и артефакты. Это вот как раз результат применения китайских оптимизаций к построению BSP. К слову оно и виз замедляет (с 14 секунд до 40). Хотя лифов и нодов становится ощутимо меньше и глубина рекурсии тоже падает. Китайское дерево в этом плане очень неоднозначное, например оно хорошо экономит вертексы, что повышает фпс. Вообщем ставлю пока эксперименты.
Для тех кто считает, что грязь на первом скриншоте - норма, специально сообщаю, что это максимум что мне удалось вытянуть, малейшие изменения в SelectPartition и освещение мгновенно превращается в дикую грязь и несёт явные следы перехода. Пример - на третьем скриншоте. Тогда как классическая функция выбора плоскости абсолютно устойчива к различным параметрам и любым попыткам дебалансировки дерева - грязи нет. Меня эта грязь бесит еще со времён ZHLT, но там она была черезчур заметной, а китаец её просто загнал вглубь и она иногда лезет в виде мелких артефактов на ровном месте. А чтобы не так палевно было - взял и разблурил.