Подоба А.А, Бровков В.Г.

Одесский национальный политехнический университет.

Исследование методов организации данных в задачах визуализации 3D-обьектов. Метод QuadTree

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

Шаги, которые необходимо предпринять для отображения трёхмерного обьекта:

1) Пересчитать координаты камеры

2) Пересчитать координаты трёхмерного объекта относительно камеры

3) Определить, какие обьекты следует отображать, а какие - нет

4) Выполнить процедуру clipping’a относительно камеры

5) Перевести координаты обьектов в экранные

6) Отрисовать объекты на экране

При больших размерах сцены и открытых ландшафтах, когда необходимо просчитывать все обьекты, которые могут попасть в камеру,обработка происходит за линейное O(n) время. Это значит, что в случае, когда на открытом пространстве сцены присутствует 1024 обьекта – все обьекты будут просчитаны. Это очень повлияет на отрисовку сцены и появится необходимость уменьшить время вычисления – это повлияет на скорость отрисовки сцены на экране.

Было введено понятие quadtrees (дословный перевод этого термина звучит как: «деревья квадратов»). Этот метод оптимизации позволяет уменьшить время до O(4*lg2(n)). Пример: если на сцене присутствует 1024 обьекта – то время уменьшается до 40 временных единиц на объект (с 1024 временных единиц на объект). Если на сцене 30000 – время около 60 временных единиц на объект.

Давайте представим себе наш ландшафт как большую сетку, простирающуюся в плоскости x/z. Смотрите на рисунок 1. Здесь мы имеем камеру, размещенную в правой нижней части ландшафта, с видимым пространством в виде синего треугольника, видимое пространство камеры охватывает несколько ячеек в синем треугольнике в направлении взгляда камеры. Таким образом, без всяких оптимизаций рендеринг нашего ландшафта будет выглядеть так:    

Рисунок 1.

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

Рисунок 2.

Как вы видите на рисунке 3, сейчас мы имеем 4 подраздела ландшафта (2, 3, 4, 5). Делить на разделы необходимо до тех пор, пока, к примеру, один раздел не будет равен размеру одной ячейки. Так, в нашем следующем рисунке мы будем делить первый раздел на четыре меньших части.    

Рисунок 3.

И снова делим один из полученных разделов на 4 части :    

Рисунок 4.

И вновь делим полученный в результате деления раздел на 4 части:    

Рисунок 5.

Итак, в результате деления мы получили наши разделы, каждый из которых равен одной синей ячейке. В конечном счете целое дерево будет разделено. Так, чтобы создать quadtree, вы делите один раздел на четыре, потом полученный один из четырех разделов делим еще на четыре и так далее, пока величина раздела не достигнет некой заданной величины. Этот минимальный размер, на котором должно остановиться деление, мы задаем сами. При построении дерева мы должны регулировать такие факторы:

1) Максимальная вложенность - уровень разбивки (LEVEL_Splitting). Это глубина дерева, по достижению которой мы останавливаем процесс разбивки (обычно от 8 до 16)

2) MINIMUM_WIDTH – минимальная ширина ячейки-quad, физические размеры которой зависят от самого малого объекта на сцене. При достижении этой величины для стороны квадрата мы также останавливаем процесс разбивки. Необходимость может возникнуть из-за того, что два обьекта с одинаковыми AxisAlignedBoundingBox расположены друг над другом и процесс разбивки не остановится.

3) Минимально допустимое количество объектов, которое может содержать один quad.

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