Поговорим о деревьях.

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


В предыдущей теме я не стал приводить реальные цифры по работе октри, ограничившись лишь общими фразами, типа "мое октри быстрее". Это наверное некоторым не понравилось (мне бы точно не понравились "пустые" заявления, поэтому эту тему я как раз начну со сравнения скорости работы октри из GLScene (как классического октри) и модифицированной мною версии.

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

Модель «Город»	GLFreeForm+GL Octree	VBOMesh+uOctree
Количество полигонов	69596	69596
Время генерации дерева (5 уровней)	8958 мс	3204 мс
Время поиска (200000 рейкастов)	8602 мс	6976 мс

Модель «Будда»	GLFreeForm+GL Octree	VBOMesh+uOctree
Количество полигонов	293232	293232
Время генерации дерева (5 уровней)	638869 мс (~10 минут)	12854 мс (~13 секунд)
Время поиска (100000 рейкастов)	671745 мс (~11 минут)	7409 мс (~7.5 секунд)

Модель «Дракон»	GLFreeForm+GL Octree	VBOMesh+uOctree
Количество полигонов	871414	871414
Время генерации дерева	1226908 мс (~20 минут) 90219 мс для глубины 3	37530 мс (37.5 сек) 21192 мс для глубины 3
Время поиска (1000 рейкастов)	12211 / 18384 мс	312 / 3659 мс

Через слэш во "времени поиска" указано время для октри с глубиной 5 и 3 уровня соответственно.


Не сложно заметить, что при любом раскладе "мое" октри оказалось быстрее по всем пунктам, причем, имея огромное превосходство в скорости загрузки (особенно хорошо это заметно на модели Дракона), имеется так же существенный выигрыш в скорости рейкаста (от 20% до 90-кратного). Учитывая время, затрачиваемое на генерацию октри средствами Сцены, для некоторых моделей его вообще нереально построить, даже с ущербом для скорости рейкаста (если в игре будет сотня моделей подобных дракону, то генерация октри займет более трех часов). У моего октри это ощущается не столь критично, но даже 20 секунд это очень много.

Одна из основных проблем сценовского октри - даже если вы потратите эти три часа на его генерацию - результат не сохранится и при перезапуске вам придется повторить всю процедуру с нуля. Прелести этого я ощутил пока готовил тест с драконом к этой статье, как по закону подлости забывал то одно то другое, из-за чего пришлось перезапускать пример раза 3...
Чтоб сэкономить время и нервы я снабдил свое октри возможностью сохранять сгенерированное дерево. Для модельки дракона (obj занимает 65мб) сгенерированное октри глубиной 5 уровней весило 35мб и загружалось всего 160мс (первая загрузка 2с).

Теперь поговорим о самих деревьях, какие ни бывают, почему я выбрал именно октри и в чем отличия моей реализации от классического октри.
Как обычно, для экономии времени предлагаю ознакомиться с этим материалом:
http://www.flipcode.com/archives/Frustum_Culling.shtml - квадродерево с фрастум кулингом.
http://www.uraldev.ru/articles/index.php?id=6 - Неплохой материал по Октри
http://www.gamedev.ru/articles/?id=30128&page=1  - Статья по BSP
http://www.gamedev.ru/articles/?id=30114 -  материал по октри, затронуты важные моменты.
Ну и самый главный сайт по рейкасту: http://www.ray-tracing.ru/

Собственно большую часть информации можно почерпнуть из последней сылки, так как этот сайт целиком посвящен проблемам рейкаста, но он мне "разонравился", когда в разделе октри я прочел следующую фразу "Забудьте про это, октодерево неэффективно и сложно", и в подтверждение кинули ссылку на материал 2000 года... Видно автор с тех пор к этой проблеме и не возвращался, но материал по остальным видам деревьев вполне исчерпывающий.

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

QuadTree, Octree, BSP-tree, kd-Tree, BVH и прочие деревья отличаются лишь способом разбиения пространства., так для октарного дерева или квадродерева (двумерный аналог октарного дерева) предполагается что каждая размерность делится пополам. Для октарного дерева мы разбиваем пространство на 8 равных частей (для квадродерева 4 части), это и отличает его от других типов деревьев и это приписывается ему как недостаток.
В чем удобство такого дерева - легко рассчитать размер следующего блока, просто разделив размер стороны на 2. В чем недостаток - мы не берем во внимание содержимое этого подпространства, в результате может получиться что одна ветка вообще пустая, или данные расположены по краям области, как на рисунке ниже:

В результате, если при поиске пересечения луч пройдет по центру этой области, то он "заденет" сразу две ветви дерева, что повлечет за собой рекурсивную трассировку в следующих уровнях дерева, при том что  реально луч пройдет через пустоту. Чтоб уменьшить количество таких промахов, на основе анализа содержащихся данных, выбирается подходящая плоскость  разбиения. Эта плоскость иногда параллельная, боковым плоскостям, иногда выбирается произвольно, иногда это даже может быть какая-то выпуклая фигура. Октри среди всех этих способов разбиения является с одной стороны самым простым в реализации (к тому же быстрее всего строится), но и самым неудачным с точки зрения эффективности поиска, о чем и можно прочитать во многих "умных" статьях и публикациях. Чтоб избавиться от этой проблемы нужно генерировать октри большей глубины, что в свою очередь ведет к увеличению требований к оперативной памяти (при генерации октри для Дракона Сценовское октри "сожрало" порядка 450мб оперативной памяти) и увеличению времени генерации.

Вторая проблема классического октри (так же сделано в GLScene) - мы вначале разбиваем все пространство, потом ищем какой объект попадает в какой лист октри. Если посчитать количество листьев (последняя ветвь дерева октри) для октри с глубиной 5 уровней, то получим 8^5=32768 октанта, и для каждого из них нужно сделать выборку объектов/полигонов. Если количество объектов обычно исчисляется сотнями и тысячами, то количество полигонов уже исчисляется десятками и сотнями тысяч, при таком количестве полигонов выборка занимает очень много времени, что вы и могли видеть на модели Дракона. Еще одна проблема появляется с объектами/полигонами, принадлежащими сразу двум ветвям октри, в этом случае они просто копируются в обе ветви и в дальнейшем все для таких полигонов выполняются дважды, что так же не добавляет скорости.

Казалось бы - если все так плохо, то почему я не использовал другой вид дерева? К примеру kd-tree? У этих деревьев есть свой недостаток, в частности высокая сложность построения дерева, что отрицательно сказывается на производительности. Обычно всякие иерархические деревья используются не для разбивки объекта а для разбивки сцены, так как количество объектов на сцене и количество полигонов (включая полигоны невидимых объектов) может отличаться в сотни тысяч раз. Если запустить такой алгоритм на высокополигональной модели, то процесс подготовки дерева может занять часы а то и дни. Такой процесс приемлемый для каких-то сложных проектов, где катастрофически не хватает производительности CPU, но нам пока всего хватает, потому мы пойдем по более простому пути.

В поисках "золотой середины" я решил модифицировать алгоритм построения октри, отойдя от "классического" решения. В основе моего метода лежит октри, в частности - разбиение пространства на 8 равных участков, как и в классическом октри, но дальше, прежде чем перейти к следующей ветви, я перебираю все полигоны объекта и раскладываю их по 8 октантам первого уровня. Что это дает:

• Во-первых сделать выборку для 8 октантов проще чем для 32868, примерно в 4 тысячи раз :) 
• Во-вторых - уже на этом этапе я могу узнать какие ветки дерева будут пустыми и установить на них "заглушку", тем самым исключив дальнейшую генерацию пустых ветвей и избавившись от рейкаста по заведомо пустым участкам.
• В-третьих - на этом этапе я могу выделить "большие" полигоны/объекты, которые бы дублировались от уровня к уровню от октанта к октанту. Вместо этого, я создаю специальный список у родительской ветви и добавляю в нее все полигоны, занимающие площадь двух и более октантов. В результате, во время рейкаста, я только один раз прохожу по этим полигонам, вместо того, чтоб проверять одни и те же полигоны 32768 раз. Такая ситуация хорошо видна на модели "Город", там "земля" это один огромный полигон, мосты пересекают весь город, и небоскребы не дают разбить сцену по высоте.
• В-четвертых - при переходе к следующему уровню октри, при генерации дерева, я уже делаю выборку объектов не из всего объема а только из объектов, принадлежащих родителю. Таким образом, с каждым шагом, количество проверок уменьшается в 8 раз. Можно оценить эффективность такого подхода. Предположим что модель имеет 100к полигонов, равномерно распределенных по всему объему. Тогда при классическом подходе, для октри 5-го уровня, нам пришлось бы выполнить 100к*32к=3.2 миллиарда проверок. В случае описанного подхода мы имеем 100к*8октантов*5уровней=4 миллиона проверок, тоесть мы уменьшили количество проверок в 800 раз!!!
• В-пятых - раз мы имеем набор полигонов для каждого октанта, то мы можем легко вычислить их реально занимаемый объем (ААВВ), который всегда меньше исходного размера октанта. В результате, я заменяю ограничивающий объем с октанта на этот вычисленный ААВВ, и благодаря тому что он стал меньшего размера, шанс что мы избежим "ложного" попадания существенно возрастает, как и эффективность рейкаста. В тестах выше это давало 90-кратный прирост производительности. Собственно этот шаг напоминает kd-tree, но существенно проще и быстрее.

Недостатки у такого подхода так же имеются, в частности усложняется работа с динамическими объектами, так как при добавлении нового объекта или перемещении существующего придется спуститься по иерархии снизу-вверх, "открывая заглушки" (создавая октанты там, где их не было) и обновляя списки объектов каждого из задействованных октантов. Но никто не мешает для этих целей использовать классическое октри, мало того - мы можем сгенерировать быстро сгененировать/загрузить наше октри и просто экспортировать из него данные в классическое октри, тем самым избежав самой неэффективной процедуры.

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

По тексту я часто писал через косую черту: "полигоны/объекты". Выше весь разговор велся касательно рейкаста, как наиболее востребованной процедуры, работающей с полигонами, но далеко не единственного применения октри. Второе важное применение - отсечение невидимых объектов. Пока на сцене 1000 объектов - о проблеме отсечения невидимых мы даже не задумываемся, так как можно просто пройтись в цикле по всей тысяче. Когда объектов 10 тысяч - уже начинаешь чесать затылок, пытаясь понять где боттлнек, на CPU и GPU, когда их становится 20-50-100 тысяч, уже никакая оптимизация не поможет, нужно что-то более кардинальное. Вот в качестве такого решения и используется октри или квадродерево. Его задача - снизить количество проверок до приемлемого количества. Так, уже после третьего уровня октри, остается сделать всего порядка 1-5% проверок, относительно исходного количества объектов, что благоприятно сказывается на производительность.
Так как объекты могут быть крупными, то создавать октри с очень большой глубиной нет смысла, так как в результате вместо повышения производительности увеличится количество проверок и количество дублирующихся объектов, что наоборт, снизит производительность, да еще и за счет расхода оперативной памяти. Так же трехуровневое квадродерево можно строить на лету, на каждом кадре рендера, что существенно упрощает задачу для динамических объектов.

В приведенных в начале статьи ссылках были примеры использования октри как для рейкаста так и для проверки видимости через фрастум куллинг.
В будущих статьях, посвященным организации рендера и отсечению невидимых объектов через Frustum/Oclussion culling, я еще вернусь к вопросу октри, а пока пожалуй пора закончить.