Методы оптимизации

Метод трассировки лучей отличает высокий объем вычислений, причем по оценкам до 95% работы в сложных сценах уходит на проверки пересечения луча с объектами сцены. Для реальных сцен, содержащих многие тысячи и десятки тысяч объектов, простой перебор для определения ближайшей точки пересечения луча с объектами сцены просто неприемлем.

Существуют методы, позволяющие заметно сократить для каждого луча количество проверяемых объектов.

Предположим, что в рассматриваемой сцене имеется сложный объект. Поместим его внутрь достаточно простой выпуклой фигуры (например, сферы). Ясно, что если луч не пересекает эту фигуру, то он не может пересечь и охватываемый ею сложный объект. Более того, построенную вспомогательную фигуру пересечет лишь небольшая часть рассматриваемых лучей и только эти лучи нужно проверить на наличие пересечения с взятым объектом сцены. Это означает, что подобная двухэтажная проверка оказывается лучше, чем непосредственная проверка пересечения лучей со сложным объектом:

1. поиск точек пересечения со сферой прост и алгоритмически легко реализуем;

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

Тем самым выигрыш очевиден.

Можно пойти дальше – описать простую фигуру сразу вокруг нескольких объектов. Тогда если луч не пересекает ограничивающую фигуру, то он не сможет пересечь ни одного из содержащихся внутри объектов.

Следующий шаг – оптимизация случая, когда луч всё-таки пересекает ограничивающую фигуру.

Разобьем содержащиеся внутри неё объекты на группы и вокруг каждой из них опишем новую фигуру, содержащуюся в исходной. Это позволит вместо непосредственной проверки содержащихся внутри объектов проверить сначала ограничивающие их фигуры.

Продолжая подобный процесс, приходим к следующей организации сцены: вся сцена содержится внутри некоторой фигуры B1, все объекты разбиты на несколько групп, и вокруг каждой из них описано по ограничивающей простейшей фигуре B11,…,B1n1, все объекты, содержащиеся внутри каждой из этих фигур, снова разбиты на группы, вокруг каждой из которых описано по ограничивающей фигуре, и т. д.

В качестве ограничивающих тел обычно выбирают сферы или пересечение полупространств.

Количество проверок на пересечение для данного метода составляет O(log n), где n – общее количество объектов в сцене.

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

В отличие от метода дерева ограничивающих объемов, разбивающего объекты на группы, метод разбиения пространства проводит разбиение самого пространства.

Рассмотрим простейший вариант этого метода – метод равномерного разбиения пространства.

Опишем вокруг всей сцены прямоугольный паралепипед и разобьем его на 1*2*3 равных частей. Для каждой из этих частей составим список всех объектов, границы которых пересекают данный блок.

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

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

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