BSP деревья

Я не слишком хорошо разбираюсь в эволюции этих хитрых деревьев и наброски пока что смехотворные. Но на что-нибудь применимое в реальных условиях - сил у меня хватит. Правда будет это не сразу. Пока что я только начинаю резвиться. И лежать здесь буду как всегда только исходники. В теорию и математику я как всегда вдаваться не хочу. Теории чтобы всё это написать времени надо совсем немного, но очередная тупая работа отнимает всё время. Со временем всё допишу.

27.11.2007

Сегодня решил немного прошерстить данный минираздел. Удалил большую часть похожих друг на друга исходников. И вдарился в эксперименты (результаты которых будут позже).

Общий недостаток всех исходников, заключается в том, что выбор оптимального сплиттера не производится. Пара слов о выборе сплиттера. Процесс незамысловатый. В тот момент когда мы выбираем каким из полигонов разделить весь список полигонов пополам, для каждого из них составляется оценочное значение e=k1*s+k2*diff, где

s - количество полигонов, которые были разрезаны.
diff - разница между количеством полигонов перед и за плоскостью.
k1,k2 - коэффициенты (k1=8, k2=1)

Проверку достаточно выполнять в пределах текущего списка полигонов (не проверяя вложенных вариантов разбиения). И самое приятное, это то что не надо высчитывать эту оценку каждый раз заново. Достаточно составить эту оценку для полного списка полигонов, и в дальнейшем корректировать оценку каждого полигона, после разделения списка. Пересчёт оценок будет довольно простым (для ещё большей простоты, можно пожертвовать качеством). Возможно что используя это, можно создать и глубинный перебор вариантов, с примелемой скоростью.

Варианты исходников

2D

BSP2D.rar
Дерево в двухмерном варианте. Отрезками обозначены плоскости. Мышкой можно установить позицию наблюдателя. Номерами показывается порядок отрисовки преград, для того чтобы наблюдатель мог правильно видеть окружающий мир.

BSP# (New!)

bsp_cs.rar
Минимальная версия на C#. Портировал сегодня, ради интереса. Надо сказать что производительность данного языка лежит далеко в заднице. Он конешно может быть эффективнее чем простой Си, но у подобного явления есть очень хитрые причины, которые я обсуждать не буду. Вобщем скрипты они и есть скрипты, как над ними не извращайся. Для сборки необходима Visual Studio 2005(2008).

3D_Q

BSP3D_Q.rar
Простейший вариант на Си. Выбор оптимального сплиттера не производится. Повороты выполняются с помощью кватернионов. Геометрический процессор оперирует только треугольниками.

3D_L2

BSP3D_l2.rar Рабочий вариант BPS Leaf.

грани больше не распадаются на треугольники. Система оперирует целыми многоугольниками.
Выпуклые объемы попадающие в листья дерева, пока что выводятся рекурсивной процедурой (с заделом на будущие доработки).
Есть возможность задавать грани, которые видны только с одной стороны.
Уравнения плоскостей пока что составляются по первых трём точкам существующих многогранников. Поэтому система может работать некорректно, если исходные грани не являются выпуклыми полигонами.

Нежизнеспособные версии

3D_L3

BSP3D_l3.rar
Тоже самое, только добавлен загрузчик для 3ds файлов, который работает довольно криво. В большинстве случаев модель рисуется с заметными ошибками (я выяснил в чём тут проблема, но исправить пока руки не дошли). Высоко полигональную модель лучше и вовсе не открывать, её обрабока будет идти неопределённо долго. Так же чуть чуть изменена отрисовка листьев дерева, в некоторых случаях она рисуется без рекурсии. Производится упрощённый выбор оптимальных сплиттеров (без быстрого пересчёта, о котором я говорил в начале).

Полезный софт

3.DS info (просмотр структуры .3ds файлов)

3ds_info.rar
Служебная программа, которая открывает *.3ds файл и показывает его схематичную структуру. Очень полезно когда изчучаешь формат 3ds файлов или отлаживаешь загрузку. На дереве изображается дерево фрагментов: тип, название типа, размер без учёта заголовка. В статусной строке показан размер и положение фрагмента внутри файла (положение указывает на начало заголовка, чтобы получить содержимое фрагмента нужно прибавить 6 байт).