Математическое и алгоритмическое обеспечение для системы визуализации в САПР тема диссертации и автореферата по ВАК РФ 05.13.12, кандидат технических наук Котов, Дмитрий Сергеевич

• Котов, Дмитрий Сергеевич
• кандидат технических наук
• 2011

Оглавление диссертации кандидат технических наук Котов, Дмитрий Сергеевич

ВВЕДЕНИЕ.

1 АНАЛИЗ СОСТОЯНИЯ В ОБЛАСТИ АЛГОРИТМОВ И МЕТОДОВ ВИЗУАЛИЗАЦИИ В САПР.

1.1 Введение в системы визуализации для САПР.

1.2 Уравнение визуализации и метод глобального освещения.

1.3 Введение в трассировку лучей.

1.3.1 Радиометрические величины.

1.3.2 Свойства светимости.

1.3.3 Взаимодействие света с поверхностями.

1.3.4 Алгоритмы трассировки лучей.

1.3.5 Алгоритм обратной трассировки лучей.

1.4 Обзор методов и подходов решения уравнения визуализации.

1.4.1 Методы и подходы повышения скорости решения уравнения визуализации и отдельных его частей.

1.5 Обзор методов и подходов нахождения точки пересечения луча с треугольником.

1.5.1 Нахождение точки пересечения в 3(1 пространстве.

1.5.2 Нахождение точки пересечения в 2<1 пространстве.

1.6 Классификация стратегий выбора точек на плоскости создаваемого изображения.

1.6.1 Равномерная трассировка.

1.6.2 Адаптивная трассировка.

1.6.3 Иерархическая трассировка.

1.6.4 Стохастическая трассировка.

1.6.5 Со случайным распределением.

1.6.6 С разделением на ячейки.

1.6.7 Случайное распределение по Пуассону.

1.7 Методы и подходы ускорения трассировки лучей.

1.7.1 Структуры пространственной сортировки и разбиения.

1.7.1.1 Иерархия ограничивающих объёмов.

1.7.1.2 Регулярная сетка.

1.7.1.3 Восьмеричное дерево.

1.7.1.4 КБ-дерево.

1.7.2 Объединение лучей в наборы.

1.7.3 Трассировка лучей по Уиттeдy(T.Whitted) и метод распределённой трассировки лучей.

1.7.4 Обзор последних наработок в области ускорения трассировки лучей

1.8 Цель и постановка задачи исследований.

1.9 Выводы.

2 РАЗРАБОТКА МЕТОДОВ ПОВЫШЕНИЯ ЭФФЕКТИВНОСТИ И ПРОИЗВОДИТЕЛЬНОСТИ ПРОЦЕССА ВИЗУАЛИЗАЦИИ.

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

2.1.1 Алгоритм определения областей проявления ступенчатого эффекта цветовых переходов на изображении при визуализации трёхмерной сцены.

2.2 Метод хранения и повторного использования информации о вкладе ИС в освещение трёхмерной сцены.

2.3 подход компактного представления кб-дерева для систем трёхмерной визуализации.

2.4 Метод кластерной трассировки лучей для систем визуализации, основанных на трассировке лучей.

2.5 Выводы.

3 АЛГОРИТМЫ РЕАЛИЗАЦИИ ПРЕДЛОЖЕННЫХ МЕТОДОВ.

3.1 Алгоритм определения областей проявления ступенчатого эффекта цветовых переходов на изображении при визуализации трёхмерной сцены.

3.2 Алгоритм реализации подхода хранения и повторного использования информации о вкладе ИС в освещение трёхмерной сцены.

3.3 Алгоритм построения компактного kd-дерева для систем трёхмерной визуализации.

3.4 Алгоритм кластерной трассировки лучей.

3.5 Выводы.

4 ИССЛЕДОВАНИЯ РАЗРАБОТАННЫХ АЛГОРИТМОВ.

4.1 Структура и организация взаимодействия блоков разработанной системы визуализации для САПР.

4.2 Условия тестирования.

4.3 Исследование алгоритма определения областей проявления ступенчатого эффекта цветовых переходов на изображении при визуализации трёхмерной сцены.

4.4 Исследование метода хранения и повторного использования информации о вкладе ИС в освещение трёхмерной сцены.

4.5 Исследование затрат памяти и скорости трассировки лучей с использованием предложенной структуры компактного kd-дерева для систем трёхмерной визуализации.

4.6 Исследование алгоритма кластерной трассировки лучей.

4.7 Сравнение времени визуализации со временем визуализации при использовании существующих подсистем визуализации.

4.8 Выводы.

Введение диссертации (часть автореферата) на тему «Математическое и алгоритмическое обеспечение для системы визуализации в САПР»

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

Визуализация в САПР применяется при выполнении проектов в машиностроении, авиации, автомобилестроении, архитектуре, при производстве дизайнерских проектов в направлениях архитектуры, автомобиле- и машиностроения, в промышленном дизайне, а также в ряде других областей.

От времени получения визуального представления проектного решения зависят сроки выполнения проекта и эффективность применения САПР в целом.

Время, требуемое на получение одного кадра визуального представления проектного решения может занимать от нескольких десятков минут до 100 часов [1] и более. Количество кадров может достигать нескольких тысяч (десятков тысяч).

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

Для получения оценки проектных решений используют контроль ключевых характеристик проекта и визуальное представление проектного решения (<визуализация). Визуальное представление проектного решения на различных стадиях проектирования позволяет повысить эффективность оценки проектного решения.

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

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

- сокращение затрат времени на получение визуального представления проектного решения.

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

Процесс визуализации состоит из следующих стадий:

1) Интерпретация описания сцены1.

2) Оценка цвета каждого пикселя в создаваемом изображении.

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

1 Виртуальное многомерное пространство с настроенными определённым образом параметрами, содержащая описание трёхмерных поверхностей проекта

Оценка цвета пикселя в создаваемом изображении - это процесс, целью которого является получение значения цвета данного пикселя согласно модели распространения света, используемой в данной системе визуализации. Результатом выполнения данной стадии является совокупность значений цвета {светимости ) всех пикселей в создаваемом изображении, являющаяся отображением результата расчёта освещения виртуальной сцены проекта на плоскость взгляда наблюдателя . Цвет пикселя определяется совокупностью оценок светимостей во всех точках сцены, видимых через данный пиксель. В рамках работы над данной диссертацией примем, что цвет представлен в одной из существующих цветовых моделей (в рамках данной диссертации: RGB4).

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

С ростом требований к качеству и детальности визуального представления проектного решения доля времени, требуемого на выполнение стадий 1 и 3 в задаче визуализации стремится к столь ничтожно малой величине, что ею можно пренебречь.

Для решения задачи оценки цвета пикселя в создаваемом изображении необходимо произвести моделирование распространения света по

2 Светимость - отношение светового потока, исходящего от рассматриваемого малого участка поверхности,

1Ф к площади этого участка: М =-, где (1Ф - световой поток, испускаемый участком поверхности Б площадью ¿¡Б.

3 Плоскость изображения, создаваемого в ходе визуализации

4 Аддитивная модель представления цвета виртуальной сцене. Существует две группы методов моделирования распространения света:

1) Трассировка5 элементарных частиц(лучей) [2, 3].

2) Метод сканирования строк (растеризация) [4].

- Метод трассировки элементарных частиц предусматривает распространение элементарных частиц в виртуальной среде с учётом взаимодействия этих частиц с поверхностями трёхмерных моделей сцены проекта. В задаче моделирования распространения света такими

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

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

5 Операция нахождения ближайшего пересечения прямой, заданной трёхмерным вектором, с трёхмерной поверхностью сцены проекта

6 Фотон - элементарная частица света (см. Советский Энциклопедический Словарь)

7 Луч - вектор, имеющий координаты начала и направления методе принципиально8 отличается от существующей физической модели распространения света (как частицы и как волны), а поскольку моделирование распространения элементарных частиц по виртуальной сцене является обязательным условием реализации модели распространения света для соответствия корпускулярно-волновой теории, то метод растеризации при моделировании распространения света использовать нецелесообразно. В рамках работы над данной диссертацией метод растеризации рассматриваться не будет.

С ростом требований к качеству результата визуализации трёхмерной сцены всё большую актуальность приобретают методы визуализации, принадлежащие к семейству алгоритмов глобального освещения [6, 7]. Это определено в первую очередь тем, что алгоритмы данного семейства позволяют получить изображение, соответствующее критериям качества, применяемым к результату визуализации на конечных стадиях выполнения проекта при визуализации архитектурных и инженерных строений и сооружений, а также в проектах, создаваемых дизайнерами, инженерами и конструкторами при помощи САПР.

Одной из важнейших проблем финальной визуализации9 является проблема сокращения затрат времени визуализации. В отдельных случаях время, затрачиваемое на визуализацию одного кадра, составляет до 100 часов [1, 8], даже на современном специализированном аппаратном оборудовании. Решение данной проблемы позволит существенно сократить сроки выполнения проектов с использованием САПР.

Таким образом, задача сокращения времени получения визуального представления проектного решения является актуальной проблемой, поскольку её решение позволит повысить эффективность применения САПР

8 Моделирование распространения частиц (лучей) по виртуальной сцене не используется

9 Визуализация проектного решения, производящаяся на завершающих стадиях выполнения проекта в САПР в архитектурных, дизайнерских, инженерных и конструкторских проектах с применением САПР.

Цель работы и задачи исследований.

Целью данной диссертационной работы является повышение эффективности средств проектирования путём разработки методов, подходов и алгоритмов, позволяющих сократить время визуализации в сравнении с существующими алгоритмами, методами и подходами.

Для достижения поставленной цели необходимо решить следующие задачи:

1) Анализ существующих алгоритмов, методов и подходов организации решения уравнения визуализации, ускорения трассировки лучей.

2) Разработка новых, более эффективных методов численного решения уравнения визуализации, ускорения трассировки лучей.

3) Разработка информационного, математического и алгоритмического обеспечения системы визуализации для САПР.

Научная новизна работы. Новые научные результаты, полученные в работе, состоят в следующем:

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

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

3) Разработан подход компактного представления кс!-дерева для систем визуализации, позволяющий сократить затраты памяти на хранение кс1-дерева в ряде случаев.

4) Разработан метод пошаговой трассировки лучей с механизмом классификации, и динамическим объединением лучей в группы - метод кластерной трассировки лучей.

Практическая ценность работы. На основе предложенных алгоритмов, методов и подходов была разработана система визуализации для САПР, обладающая следующими, по сравнению с методами и подходами, применяющимися в существующих решениях, преимуществами:

- Меньшее на величину от 14,8 до 20,6% время устранения ступенчатого эффекта цветовых переходов в создаваемом изображении.

- Расчёт освещения, приходящего от ИС, выполняется быстрее на 1518%

- Меньший (до 44%) объем памяти, требуемой для хранения структуры к<1-дерева.

- Большая, до 30%, скорость визуализации с использованием предложенного компактного кс!-дерева.

- Большая, на величину до 170%, скорость визуализации с использованием метода кластерной трассировки лучей.

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

В ряде случаев разработанная система уступила в производительности методам и подходам, применяющимся в существующих на рынке решениях, на величину 3 - 20%, однако в большинстве случаев разработанная система оказалась быстрее на величину 15-170%. Также стоит отметить, что

10 ИС - источник света разработанная система имеет потенциал дальнейшего увеличения производительности, и разработанные методы можно использовать совместно с широким кругом существующих методов и подходов, применяемых при расчёте финальной визуализации. Разработанная система визуализации позволяет решать уравнение визуализации [6, 7](1.1), используя метод трассировки путей [9] с выбором направлений луча по алгоритму Monte-Carlo [10], и способна осуществлять устранение ступенчатого эффекта цветовых переходов на получаемом изображении с автоматическим определением областей применения фильтра устранения ступенчатого эффекта цветовых переходов. Описание сцены проекта, включая все необходимые настройки, экспортируется из САПР, с дальнейшим преобразованием во внутренний формат.

Реализация и внедрение результатов работы.

Работа по теме диссертации проводилась в лаборатории ВлГУ, г.Владимир, кафедры ВТ. Полученные результаты исследований в виде программного обеспечения внедрены в производство на предприятии ООО"АС-Студия" (см. Приложение А). На защиту выносятся.

1) Алгоритм определения областей проявления ступенчатого эффекта цветовых переходов на создаваемом изображении.

2) Метод сохранения и повторного использования информации об освещении трёхмерной сцены источниками света.

3) Подход компактного представления kd-дерева для систем трёхмерной визуализации.

4) Метод кластерной трассировки лучей.

5) Программная реализация и алгоритмические решения разработанной системы визуализации.

Апробация работы. Основные положения и результаты работы докладывались и обсуждались на следующих семинарах и конференциях:

- VTII Международная научно-техническая конференция "Физика и радиоэлектроника в медицине и экологии ФРЭМЭ'2008", Россия, г.Владимир - г.Суздаль, 2-4 июля 2008г.

- IX Международная конференция "Высокопроизводительные Параллельные Вычисления на Кластерных Системах", Россия, г.Владимир, ВлГУ, 2-3 ноября 2009г.

Публикации по работе. По теме диссертации опубликовано 7 печатных работ, из них 3 публикации в издании, рекомендованном ВАК (журнал "САПР и графика"), 2 тезиса докладов в сборнике докладов ФРЭМЭ'2008, 2 публикации в сборнике научных статей "Алгоритмы, методы и системы обработки данных" ВлГУ г.Муром.

Структура работы. Диссертационная работа состоит из введения, четырёх глав, заключения, списка использованных источников. Общий объём диссертации 197 страниц, в том числе 178 страниц основного текста, 14 страниц списка литературы, 1 страница приложения. Диссертация содержит 83 рисунка и 14 таблиц.

Заключение диссертации по теме «Системы автоматизации проектирования (по отраслям)», Котов, Дмитрий Сергеевич

4.8 Выводы

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

2) Рассмотрены возможности и область применения предложенного метода сохранения и повторного использования информации об освещении виртуальной сцены проекта от ИС. Показано, что прирост скорости составил 15-18% относительно существующих методов аналогичного назначения.

3) Рассмотрена возможность применения предложенного подхода компактного представления кс1-дерева в архитектурных, инженерных и конструкторских проектах в САПР. Показано, что применение данного подхода позволяет сократить затраты памяти на величину до 44% в сравнении существующими подходами, а прирост скорости визуализации с предложенным подходом составил до 30%.

4) Рассмотрены целесообразность, особенности, и области применения предложенного метода кластерной трассировки лучей для визуализации в САПР. Показано, что данный метод позволил получить на тестовых сценах прирост производительности на величину до 170%, а время составления кластеров зависит только от количества сортируемых лучей и не зависит (напрямую) от количества примитивов в сцене проекта, что позволяет использовать данный метод при финальных визуализациях.

5) Рассмотрена структура программного обеспечения системы визуализации для САПР. Разработана система визуализации для САПР, реализованная в виде подключаемого модуля к САПР Autodesk 3ds max.

Заключение

Анализ существующих методов, подходов и алгоритмов, применяемых при визуализации трёхмерных сцен позволил определить возможные пути оптимизации каждой из стадий процесса визуализации, а также всего процесса визуализации в общем. Среди рассмотренных методов и подходов выполнения отдельных стадий процесса визуализации была произведена оценка их сильных и слабых сторон, и выделены методы и подходы, наиболее перспективные с точки зрения дальнейшего масштабирования производительности системы визуализации для САПР. Для решения задачи оценки цвета пикселя в создаваемом изображении целесообразно применять метод трассировки элементарных частиц (лучей). Среди структур пространственного разбиения и сортировки одной из лучших является к<1-дерево, т.к. позволяет получить наименьшее время поиска ближайшего пересечения луча с примитивом, при затратах памяти, сравнимых с остальными рассмотренными структурами пространственного разбиения и сортировки. Среди методов поиска пересечения луча с треугольником для системы визуализации для САПР предпочтительными являются методы нахождения пересечения в 3(1 пространстве, т.к. методы нахождения точки пересечения с проецированием в 2(1 пространство имеют слишком большой расход памяти, что значительно снижает количество примитивов сцены, умещающихся в ОЗУ, что в свою очередь является существенным ограничивающим фактором, неприемлемым для систем визуализации для САПР. В ходе исследований рассмотренных алгоритмов, методов и подходов, было также установлено, что в ходе трассировки лучей в сцену ряд промежуточных данных можно сохранить и повторно использовать: в ходе визуализации некоторой последовательности кадров освещённость отдельных участков сцены проекта остаётся неизменной, и отличается от предыдущего кадра лишь трансформацией проекции на плоскость взгляда наблюдателя.

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

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

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

Исследование существующих алгоритмов, методов и подходов для систем визуализации для САПР показало, что получение результата визуализации, соответствующего критериям качества финальной визуализации, является достижимой задачей для большинства алгоритмов глобального освещения, но требует значительных затрат аппаратных и/или временных ресурсов. Сокращение времени визуализации является одной из наиболее приоритетных задач при построении системы визуализации для САПР.

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

В работе были получены следующие основные результаты:

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

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

3) Рассмотрены существующие методы и подходы представления и построения kd-дерева. Исследована зависимость скорости трассировки луча от качества разбиения пространства. Показано, что зависимость скорости трассировки луча от точности позиционирования секущей плоскости возрастает в направлении от корня дерева к его листьям. Показано, что при уменьшении точности позиционирования секущей плоскости в узлах начальных уровней приводит к незначительному падению скорости трассировки луча. Предложен подход представления kd-дерева, использующий для представления позиции секущей плоскости менее 32-х бит, где само значение позиции секущей плоскости представлено в виде процентного соотношения относительно размера узла дерева. В алгоритме построения предложенного kd-дерева используется модернизированный вариант алгоритма SAH, где максимальное количество секущих плоскостей-кандидатов ограничено некоторой заранее заданной величиной, а поиск минимальной стоимости разбиения производится среди всех трёх осей XYZ при нахождении позиции секущей плоскости для каждого листа. Сложность построения kd-дерева с использованием предложенного алгоритма составляет 0(N), вместо сложности 0(NlogN) в алгоритме SAH.

4) Исследованы существующие методы организации процесса трассировки лучей, рассмотрены методы пакетной и групповой трассировки лучей, рассмотрены существующие структуры пространственной сортировки и разбиения, применяемые в системах финальной визуализации в САПР.

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

181 нахождения когерентных вторичных лучей за время О (К) с дальнейшим выделением кластеров среди данных лучей и выполнением трассировки всего кластера лучей за один вызов функции траверса. Показано, что применение алгоритма кластерной трассировки лучей позволило сократить время визуализации.

Список литературы диссертационного исследования кандидат технических наук Котов, Дмитрий Сергеевич, 2011 год

1. Grant Rollings, "2,400 hours to make one second of action", The Sun, 07 Dec.2009

2. Cohen, M., and J. Wallace. 1993. Radiosity and Realistic Image Synthesis. Morgan Kaufmann

3. Ward, G. 1994. "The RADIANCE Lighting Simulation and Rendering System." Computer Graphics, pp. 459 472

4. Haeberli, P., and K. Akeley. 1990. "The Accumulation Buffer: Hardware Support for High-Quality Rendering" In Computer Graphics (Proceedings of SIGGRAPH 90) 24(4), pp. 309-318

5. Курс общей физики (Том 3. Оптика. Атомная физика. Физика атомного ядра и элементарных частиц) / Савельев И.В. // М.: 1998, 528 стр.

6. Kajiya, J. 1986, "The rendering equation", Proceedings of SIGGRAPH 1986, pp. 143-150

7. Philip Dutre, 2003, "Global Illuminaiton Comedium" Computer Graphics Department of Computer Science Katholieke Universitet Leuven, 68 pages

8. Дмитриев, К. От Монте-Карло к Квази Монте-Карло / К. Дмитриев // Труды 12-ой международной конференции по компьютерной графике и машинному зрению ГрафиКон'2002, Россия, Нижний Новгород, сентябрь 16-21,2002, с. 53-58.

9. Валиев, И.В. Физически корректная модель солнечного освещения, задаваемая изображением с большим динамическим диапазоном / Валиев И.В., Волобой А.Г., Галактионов В.А. // "Вестник компьютерных и информационных технологий", № 9, 2009, с. 10-17.

10. Волобой, А.Г. Анализ ошибок компьютерного моделирования глобального освещения / А.Г. Волобой, В.А. Галактионов, C.B. Ершов, Д.Д. Жданов, И.С. Потемин, JI.3. Шапиро // Препринт ИПМ им. М.В. Келдыша РАН, № 54, 2009, 23 с.

11. Галактионов В.А. Программные технологии синтеза реалистичных изображений / В.А. Галактионов // Автореферат диссертации на соискание ученой степени доктора физико-математических наук по специальности 05.13.11, Москва, ИПМ им. М.В. Келдыша РАН, 2007.

12. Волобой, А.Г. Моделирование естественного дневного освещения, задаваемого изображением с большим динамическим диапазоном / А.Г. Волобой, В.А. Галактионов, Э.А. Копылов, JI.3. Шапиро // "Программирование", № 5, 2006, с. 62-80.

13. Барладян Б.Х. Моделирование освещенности и синтез фотореалистичных изображений с использованием Интернет технологий / Б.Х. Барладян, А.Г.

14. Волобой, Н.И. Вьюкова, В.А. Галактионов, Н.Б. Дерябин // "Программирование", № 5, 2005, с.66-80.

15. Волобой А.Г. Алгоритмы моделирования и визуализации оптически сложных материалов на примере ткани / А.Г. Волобой, В.А. Галактионов, H.A. Лобалзо // "Программирование", № 4, 2010, с. 68-80.

16. Волобой, А.Г. Физически обоснованная модель распространения света в ткани и ее валидация / А.Г. Волобой, В.А. Галактионов, H.A. Лобалзо // Препринт ИПМ им. М.В. Келдыша РАН, № 63, 2008, 18 с.

17. Востряков, К.А. Высокочастотный кэш излучения / К.А. Востряков // Труды 19-ой международной конференции по компьютерной графике и зрению ГРАФИКОН-2009, Москва, МГУ, 5-9 октября, 2009, с. 360-363.

18. Востряков, К.А. Когерентные алгоритмы синтеза реалистичных изображений / Автореферат диссертации на соискание ученой степени кандидата физико-математических наук по специальности 05.13.11, Москва, ИПМ им.М.В. Келдыша РАН, 2009.

19. Барладян, Б.Х. Применение когерентной трассировки лучей в задачах физически аккуратной визуализации / Б.Х. Барладян, А.Г. Волобой, К.А. Востряков, В.А. Галактионов, JI.3. Шапиро // "Программирование", № 5, 2008, с. 67-80.

20. Волобой, А.Г. Средства визуализации распространения световых лучей в задачах проектирования оптических систем / А.Г. Волобой, В.А. Галактионов, А.Д. Жданов, Д.Д. Жданов // "Информационные технологии и вычислительные системы", № 4, 2009, с. 28-39.

21. Востряков К.А. Новый иерархический базис для освещения на полусфере // Труды 18-ой международной конференции по компьютерной графике и зрению, Россия, Московский Государственный Университет, июнь 23-27, 2008, с. 262-269.

22. Барладян, Б.Х. Алгоритм двухуровневой трассировки лучей и его развитие в Оптических элементах / Б.Х. Барладян, А.Г. Волобой, В.А. Галактионов, JI.3. Шапиро // Препринт ИПМ им. М.В. Келдыша РАН, № 46, 2008,21 с.

23. Волобой, А.Г. Визуализация результатов моделирования освещения в тонком красящем слое / А.Г. Волобой, С.В. Ершов, С.Г. Поздняков // Препринт ИПМ им. М.В. Келдыша РАН, № 66, 2010, 21 с.

24. Котов Д.С. Метод определения областей проявления ступенчатого эффекта цветовых переходов на изображении при визуализации трехмерной сцены Текст. / Д.С. Котов // САПР и графика 8'2009, стр.111112

25. Котов Д.С. Организация интерактивной работы со списком источников света в сцене Текст. / Д.С. Котов // Алгоритмы, методы и системы обработки данных: сборник научных статей, выпуск 13, 2008, ВлГУ, г.Муром, стр.71-77

26. Ward, Gregory J.; Francis M. Rubinstein and Robert D.Clear: "A Ray Tracing Solution for Diffuse Interreflection". Coputer Graphics 22 (4), pp.85-92, 1988

27. Ward, Gregory J., Paul S. Heckbert, "Irradiance Gradients". In Proceedings of the Third Eurographics Workshop on Rendering, pp.85-98, Bristol 1992

28. Ingo Wald, Heiko Friedrich, Gerd Marmitt, Philipp Slusallek and Hans-Peter Seidel "Faster Isosurface Ray Tracing using Implicit KD-Trees" IEEE Transactions on Visualization and Computer Graphics (2005), Vol.11(5), pp.562-572

29. Maxim Shevtsov, Alexei Soupikov and Alexander Reshetov Intel Corporation "Efficient acceleration structures layout for rendering on 32- and 64-bit many-core architectures" proceedings of GraphiCon'2009, 2 pages

30. Котов Д.С. Компактное представление KD-дерева в системах трехмерной визуализации Текст. / Д.С. Котов, В.Н. Ланцов // САПР и графика 1Г2010, стр.73-74

31. Н. Samet, "The Design and Analysis of Spatial Data Structures" Addison-Wesley, Reading, MA, 1990

32. Matthias Groß, Carsten Lojewski, Martin Bertram and Hans Hagen "Fast Implicit kd-Trees: Accelerated Isosurface Ray Tracing and Maximum Intensity Projection for Large Scalar Fields" CGIM07: Proceedings of Computer Graphics and Imaging (2007) 67-74

33. Котов Д.С. Технология упрощения геометрии на ранней стадии подготовки рендера Текст. / Д.С. Котов // Алгоритмы, методы и системы обработки данных: Сб. научных статей / ВлГУ, М, 2008. №13. С.78-82

34. Realtime Ray Tracing on current CPU architectures Carsten Benthin PhD, Computer Graphics Group, Saarland University, Germany, 2006

35. Котов Д.С. Кластерная трассировка лучей в системах визуализации Текст. / Д.С. Котов, В.Н. Ланцов // САПР и графика 3'2010, стр.84-85

36. Kirill Garanzha and Charles Loop "Fast Ray Sorting and Breadth-First Packet Traversal for GPU Ray Tracing" // EUROGRAPHICS 2010, Volume 29 (2010), Number 2

37. Теоретические основы САПР / Корячко В.П., Курейчик В.М., Норенков И.П. // М.: Энергоатомиздат, 1987, 400с.

38. Основы САПР (CAD,САМ,CAE) / Кунву Ли // 2004, 560 е., Питер, ISBN: 5-94723-770-9

39. Введение в современные САПР / Малюх В. // ДМК Пресс, 2010, 192с., ISBN: 978-5-94074-551-8

40. Инженерное проектирование и САПР электрических машин (1-е изд.) / Гольдберг О.Д. // Академия, 2008, 560с., ISBN: 978-5-7695-4088-2194

41. Основы автоматизированного проектирования / Норенков И.П. // М., Изд. МГТУ им. Баумана, 2002., 336с.

42. Моделирование и алгоритмизация в САПР / Судзиловский В. // Клуб 36 и 6, 2009, 267с., ISBN: 978-5-98697-139-1

43. Численные методы / Самарский A.A., Гулин A.B. // М.: Научный мир, 1989, 432с.

44. Введение в математическое моделирование / Семененко М.Г. // М.: Солон-Р, 2002, 112с.

45. Введение в математические основы САПР / Ушаков Д. // Новосибирск: Ледас, 2008, 180с.

46. Математическое моделирование в технике / Зарубин B.C. // М.: МГТУ им. Н.Э. Баумана, 2001, 496с.

47. Математические основы машинной графики / Роджерс Д. // Адаме Дж., М.: Мир, 2001, 606с.

48. SolidWorks Компьютерное моделирование в инженерной практике / Алямовский A.A. // М: БХВ, 2005, 800 с.

49. Инженерная и компьютерная графика / Романычева Э. Т., Соколова Т. Ю. // ДМК Пресс, 2001, 592 с.

50. САПР технологических процессов / Кондаков А. И. // ISBN 978-57695-3338-9, 272с., 2008г.

51. САПР в машиностроении / Берлинер Э.М., Таратынов О.В. // Форум-Инфра-М, 2010, 448с., ISBN: 978-5-91134-117-6.

52. Каталог САПР. Программы и производители. 2008-2009 2-изд. / Латышев П. // Солон-Пресс, 2008, 704с., ISBN: 978-5-91359-032-9.

53. Проектирование в системе КОМПАС-ЗБ VII / Ганин Н. // ДМК Пресс, 010, 776с., ISBN: 978-5-94074-543-3.

54. Эффективная работа: SolidWorks 2005 / Тику Ш. // Питер, 2006, 816 е., ISBN: 5469010236.

55. САПР на базе AutoCAD как это делается / Зуев С.А. // BHV-Санкт-Петербург, 2008, 1168 е., ISBN: 5-94157-344-8.

56. AutoCAD 2004. Разработка приложений и адаптация / Полещук H.H. // БХВ-Петербург, 2004, 624 е., ISBN:5-94157-424-Х.

57. Основы компьютерной графики: Autocad 2000-2006 / Ивашинников А.П. // Солон-пресс, 2005, 175с., ISBN: 5-98003-228-2.

58. ArchiCAD 8.О. Самоучитель. Архитектурно-строительное проектирование / Васильев П. // ТехБук, 2004, 338с.

59. Волобой, А.Г. Расчет освещенности и генерация реалистичных изображений для архитектурных моделей, разработанных в AutoCAD / А.Г. Волобой, В.А. Галактионов, JI.3. Шапиро // Учебно-методическое руководство, ИПМ им. М.В. Келдыша РАН, 2009, 20 с.

60. Autodesk AutoCAD 2007 и AutoCAD LT 2007. Библия пользователя / Финкелыптейн Э. // Диалектика, 2007, 1312 е., ISBN 978-5-8459-1000-4.

61. AutoCAD 2010. Полный курс для профессионалов / Климачева Т. Н. // Диалектика, 2009, 1088 е., ISBN 978-5-8459-1599-3.

62. AutoCad для конструкторов / Уваров A.C. // Горячая линия Телеком, 2006, 399с., ISBN: 5-93517-275-5.