Назад | Содержание | Вперед
Задача нахождения пересечения является основной в процессе трассировки. Напомним порядок трассировки: найти точку пересечения луча от наблюдателя с первым объектом, для определения степени освещенности объекта проверяем пересечения со всеми источниками света, рекурсивно вызываем процедуру в случае полупрозрачного и/или зеркального материала. Понятно, что оптимизация поиска пересечения даст наибольшее ускорение.
Геометрически нахождение пересечений с простыми объектами, такими как треугольник, плоскость, сфера, конус, цилиндр, не представляет собой сложной задачи. Энтузиасты даже находят аналитическое решения точки пересечения луча с тором (решая уравнение четвертой степени).
Рассмотрим методы нахождения пересечений. Самый простой способ – это полный перебор всех объектов. В случае увеличения количества элементов сцены (например стандартный чайник в 3ds max состоит из 1024 треугольников), время, затраченное на поиск, перестает удовлетворять самых терпеливых людей. Для избавления от необходимости полного перебора можно воспользоваться разными способами.
Достаточно компактный набор объектов (модель чего либо, тот же чайник и т.д.) можно поместить в так называемую оболочку. Чаще всего в роли оболочек используют сферы (эллипсы), или кубы (параллелепипеды). Самое главное то, чтобы внутри оболочки были все элементы набора. Теперь, зная что луч не пересекает оболочку можно смело исключить ее из рассмотрения. Внутри оболочки можно поместить другие оболочки. Получится что-то вроде дерева.
В демонстрационной программе реализовано пространственное разбиение в виде кубов (они на самом деле параллелепипеды, но написать куб легче). Ограничивающий объем (bounding box) разбивается по всем трем сторонам на равное количество кубов с одинаковыми параллельными сторонами (если разбивается на 32, то получаем 32*32*32 = 32768 всего кубов). Далее для всех объектов (в программе реализованы только треугольники) просчитывались кубы, в которые так или иначе попадают объекты.
Непосредственно поиск пересечения начинался с определения куба, в котором находится стартовая точка. Если точка находилась вне ограничивающего объема, то ищем пересечение с ним. Далее простой цикл. Пока не найдено пересечение в данном кубе и пока куб не выходит за границы ограничивающего объема, переходим к следующему кубу в данном направлении луча.
Равномерное разделение объектов хорошо работает, когда сами объекты распределены в пространстве равномерно. Если же в сцене наблюдаются большой разнос в пространстве совместно с большой плотностью в малых объектах (большие открытые пространства, космос и .д.) данный метод теряет свою эффективность.
Дальнейшее развитие этого метода приведет к построению восьмеричного дерева (occtree). Пространство разбивается на восемь равных кубов. Объекты рекурсивно добавляются в полученные кубы. Рекурсия заканчивается либо при определенной глубине, либо при малом количестве объектов (когда быстрее работает перебор, а не проход по дереву). Для нахождения пересечений используется рекурсивная функция. Если текущий куб не имеет поддеревьев, то пересечение находится перебором всех объектов в этом кубе. Иначе пересечение находится для восьми кубов, как в предыдущем случае.
Назад | Содержание | Вперед